Abstract
Variational relaxations can be used to compute approximate minimizers of optimal partitioning and multiclass labeling problems on continuous domains. While the resulting relaxed convex problem can be solved globally optimal, in order to obtain a discrete solution a rounding step is required, which may increase the objective and lead to suboptimal solutions. We analyze a probabilistic rounding method and prove that it allows to obtain discrete solutions with an a priori upper bound on the objective, ensuring the quality of the result from the viewpoint of optimization. We show that the approach can be interpreted as an approximate, multiclass variant of the coarea formula.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Zach, C., Gallup, D., Frahm, J.M., Niethammer, M.: Fast global labeling for real-time stereo using multiple plane sweeps. Vis. Mod. Vis. (2008)
Lellmann, J., Kappes, J., Yuan, J., Becker, F., Schnörr, C.: Convex multi-class image labeling by simplex-constrained total variation. In: Tai, X.-C., Mørken, K., Lysaker, M., Lie, K.-A. (eds.) SSVM 2009. LNCS, vol. 5567, pp. 150–162. Springer, Heidelberg (2009)
Pock, T., Chambolle, A., Cremers, D., Bischof, H.: A convex relaxation approach for computing minimal partitions. Comp. Vis. Patt. Recogn. (2009)
Ambrosio, L., Fusco, N., Pallara, D.: Functions of Bounded Variation and Free Discontinuity Problems. Clarendon Press, Oxford (2000)
Lellmann, J., Becker, F., Schnörr, C.: Convex optimization for multi-class image labeling with a novel family of total variation based regularizers. In: Int. Conf. Comp. Vis. (2009)
Kleinberg, J.M., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. Found. Comp. Sci., 14–23 (1999)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. Patt. Anal. Mach. Intell. 23, 1222–1239 (2001)
Olsson, C., Byröd, M., Overgaard, N.C., Kahl, F.: Extending continuous cuts: Anisotropic metrics and expansion moves. In: Int. Conf. Comp. Vis. (2009)
Bertsimas, D., Weismantel, R.: Optimization over Integers. Dynamic Ideas (2005)
Chan, T.F., Esedoḡlu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. J. Appl. Math. 66, 1632–1648 (2006)
Alberti, G., Bouchitté, G., Dal Maso, G.: The calibration method for the Mumford-Shah functional and free-discontinuity problems. Calc. Var. Part. Diff. Eq. 16, 299–333 (2003)
Pock, T., Cremers, D., Bischof, H., Chambolle, A.: Global solutions of variational models with convex regularization. J. Imaging Sci. 3, 1122–1145 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lellmann, J., Lenzen, F., Schnörr, C. (2011). Optimality Bounds for a Variational Relaxation of the Image Partitioning Problem. In: Boykov, Y., Kahl, F., Lempitsky, V., Schmidt, F.R. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2011. Lecture Notes in Computer Science, vol 6819. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23094-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-23094-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23093-6
Online ISBN: 978-3-642-23094-3
eBook Packages: Computer ScienceComputer Science (R0)