{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:54:19Z","timestamp":1787320459272,"version":"build-2736575974"},"reference-count":75,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We study convex relaxations of the image labeling problem on a continuous domain with regularizers based on metric interaction potentials. The generic framework ensures existence of minimizers and covers a wide range of relaxations of the original combinatorial problem. We focus on two specific relaxations that differ in flexibility and simplicity\u2014one can be used to tightly relax any metric interaction potential, while the other covers only Euclidean metrics but requires less computational effort. For solving the nonsmooth discretized problem, we propose a globally convergent Douglas\u2013Rachford scheme and show that a sequence of dual iterates can be recovered in order to provide a posteriori optimality bounds. In a quantitative comparison to two other first-order methods, the approach shows competitive performance on synthetic and real-world images. By combining the method with an improved rounding technique for nonstandard potentials, we were able to routinely recover integral solutions within $1\\%$\u2013$5\\%$ of the global optimum for the combinatorial image labeling problem.<\/jats:p>","DOI":"10.1137\/100805844","type":"journal-article","created":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T18:06:45Z","timestamp":1321985205000},"page":"1049-1096","source":"Crossref","is-referenced-by-count":88,"title":["Continuous Multiclass Labeling Approaches and Algorithms"],"prefix":"10.1137","volume":"4","author":[{"given":"J.","family":"Lellmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Schn\u00f6rr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,11,22]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Ambrosio, N. Fusco, and D. Pallara,\n                      Functions of Bounded Variation and Free Discontinuity Problems\n                      , The Clarendon Press, Oxford University Press, New York, 2000.","DOI":"10.1093\/oso\/9780198502456.001.0001"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.12"},{"key":"R3","unstructured":"K. J. Arrow, L. Hurwicz, and H. Uzawa,\n                      Studies in Linear and Non-Linear Programming\n                      , Stanford University Press, Stanford, CA, 1958."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-009-0149-y"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"E. Bae and X.C. Tai,\n                      Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation\n                      , in Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci. 5567, Springer-Verlag, Berlin, 2009, pp. 1\u201313.","DOI":"10.1007\/978-3-642-02256-2_1"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-010-0406-y"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/090756855"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"B. Berkels,\n                      An unconstrained multiphase thresholding approach for image segmentation\n                      , in Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci. 5567, Springer-Verlag, Berlin, 2009, pp. 26\u201337.","DOI":"10.1007\/978-3-642-02256-2_3"},{"key":"R9","unstructured":"I. Borg and P. J. F. Groenen,\n                      Modern Multidimensional Scaling. Theory and Applications\n                      , 2nd ed., Springer, New York, 2005."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Y. Boykov,\n                      Computing geodesics and minimal surfaces via graph cuts\n                      , in Proceedings of the Ninth IEEE International Conference on Computer Vision, 2003, pp. 26\u201333.","DOI":"10.1109\/ICCV.2003.1238310"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.60"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. P. Boyle and R. L. Dykstra,\n                      A method for finding projection onto the intersection of convex sets in Hilbert spaces\n                      , in Advances in Order Restricted Statistical Inference, Lecture Notes in Statist. 37, Springer, Berlin, 1986, pp. 28\u201347.","DOI":"10.1007\/978-1-4613-9940-7_3"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. Braides,\n                      $\\Gamma$-convergence for Beginners\n                      , Oxford University Press, Oxford, UK, 2002.","DOI":"10.1093\/acprof:oso\/9780198507840.001.0001"},{"key":"R15","unstructured":"A. Chambolle, D. Cremers, and T. Pock,\n                      A Convex Approach for Computing Minimal Partitions\n                      , Technical report 649, CMAP, Ecole Polytechnique, Palaiseau, France, 2008."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0238-9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/040615286"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/24\/6\/065014"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Delaunoy, K. Fundana, E. Prados, and A. Heyden,\n                      Convex multi-region segmentation on manifolds\n                      , in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009, pp. 662\u2013669.","DOI":"10.1109\/ICCV.2009.5459174"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0084194-4"},{"key":"R22","unstructured":"V. Duval, J.F. Aujol, and L. Vese,\n                      A projected gradient algorithm for color image decomposition\n                      , CMLA Preprint 2008-21, ENS Cachan, Cachan, France, 2008."},{"key":"R23","unstructured":"J. Eckstein,\n                      Splitting Methods for Monotone Operators with Application to Parallel Optimization\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1989."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01236935"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614077"},{"key":"R27","unstructured":"D. Goldfarb and S. Ma,\n                      Fast Multiple Splitting Algorithms for Convex Optimization\n                      , preprint, 2009; available online from http:\/\/www.arxiv.org\/abs\/0912.4570."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1964-11178-2"},{"key":"R29","unstructured":"T. Goldstein, X. Bresson, and S. Osher,\n                      Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction\n                      , CAM Report 09-06, UCLA, Los Angeles, CA, 2009."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(85)90187-9"},{"key":"R31","unstructured":"A. Graham,\n                      Kronecker Products and Matrix Calculus with Applications\n                      , Wiley, New York, 1981."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1233908"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00096-A"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg and E. Tardos,\n                      Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 14\u201323.","DOI":"10.1109\/SFFCS.1999.814572"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0233-1"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"V. Kolmogorov and Y. Boykov,\n                      What metrics can be approximated by geo-cuts, or global optimization of length\/area and flux\n                      , in Proceedings of the Tenth IEEE International Conference on Computer Vision, 2005, pp. 564\u2013571.","DOI":"10.1109\/ICCV.2005.252"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1061"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"J. Lellmann, F. Becker, and C. Schn\u00f6rr,\n                      Convex optimization for multi-class image labeling with a novel family of total variation based regularizers\n                      , in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009, pp. 646\u2013653.","DOI":"10.1109\/ICCV.2009.5459176"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"J. Lellmann, D. Breitenreicher, and C. Schn\u00f6rr,\n                      Fast and exact primal-dual iterations for variational problems in computer vision\n                      , in Proceedings of the 11th European Conference on Computer Vision, Lecture Notes in Comput. Sci. 6312, Springer-Verlag, Berlin, 2010, pp. 494\u2013505.","DOI":"10.1007\/978-3-642-15552-9_36"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"J. Lellmann, J. Kappes, J. Yuan, F. Becker, and C. Schn\u00f6rr,\n                      Convex multi-class image labeling by simplex-constrained total variation\n                      , in Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci. 5567, Springer-Verlag, Berlin, 2009, pp. 150\u2013162.","DOI":"10.1007\/978-3-642-02256-2_13"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"J. Lellmann, F. Lenzen, and C. Schn\u00f6rr,\n                      Optimality bounds for a variational relaxation of the image partitioning problem\n                      , in Proceedings of the 8th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, Springer-Verlag, Berlin, 2011, pp. 132\u2013146.","DOI":"10.1007\/978-3-642-23094-3_10"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(66)90114-5"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01835-7"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/BF00938486"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160420503"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"K. Murota,\n                      Discrete Convex Analysis\n                      , Monogr. Discrete Math. Appl. 10, SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718508"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"C. Nieuwenhuis, E. T\u00f6ppe, and D. Cremers,\n                      Space-varying color distributions for interactive multiregion segmentation: Discrete versus continuous approaches\n                      , in Proceedings of the 8th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, 2011, pp. 177\u2013190.","DOI":"10.1007\/978-3-642-23094-3_13"},{"key":"R50","unstructured":"C. Olsson,\n                      Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms\n                      , Ph.D. thesis, Faculty of Engineering, Centre for Mathematical Sciences, Lund University, Lund, Sweden, 2009."},{"key":"R51","doi-asserted-by":"crossref","unstructured":"N. Paragios, Y. Chen, and O. Faugeras, eds.\n                      Handbook of Mathematical Models in Computer Vision\n                      , Springer, New York, 2006.","DOI":"10.1007\/0-387-28831-7"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"T. Pock, A. Chambolle, D. Cremers, and H. Bischof,\n                      A convex relaxation approach for computing minimal partitions\n                      , in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009, pp. 810\u2013817.","DOI":"10.1109\/CVPR.2009.5206604"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"T. Pock, D. Cremers, H. Bischof, and A. Chambolle,\n                      An algorithm for minimizing the Mumford-Shah functional\n                      , in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009, pp. 1133\u20131140.","DOI":"10.1109\/ICCV.2009.5459348"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/090757617"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01141092"},{"key":"R56","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"R57","unstructured":"R. T. Rockafellar and R. J.B. Wets,\n                      Variational Analysis\n                      , 2nd ed., Springer, Berlin, 2004."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1109\/83.541429"},{"key":"R60","doi-asserted-by":"crossref","unstructured":"S. Setzer,\n                      Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage\n                      , in Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci. 5567, Springer-Verlag, Berlin, 2009, pp. 464\u2013476.","DOI":"10.1007\/978-3-642-02256-2_39"},{"key":"R61","unstructured":"S. Setzer,\n                      Splitting Methods in Image Processing\n                      , Ph.D. thesis, Department of Mathematics and Computer Science, University of Mannheim, Mannheim, Germany, 2009."},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592050"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598336745"},{"key":"R64","doi-asserted-by":"crossref","unstructured":"R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother,\n                      A comparative study of energy minimization methods for Markov random fields\n                      , in Proceedings of the 9th European Conference on Computer Vision, Lecture Notes in Comput. Sci. 3952, Springer-Verlag, Berlin, 2006, pp. 19\u201326.","DOI":"10.1007\/11744047_2"},{"key":"R65","doi-asserted-by":"crossref","unstructured":"W. Trobin, T. Pock, D. Cremers, and H. Bischof,\n                      Continuous energy minimization via repeated binary fusion\n                      , in Proceedings of the 10th European Conference on Computer Vision, Lecture Notes in Comput. Sci. 5305, Springer-Verlag, Berlin, 2008, pp. 677\u2013690.","DOI":"10.1007\/978-3-540-88693-8_50"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008714607737"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1137\/070696143"},{"key":"R68","doi-asserted-by":"crossref","unstructured":"M. Werlberger, T. Pock, M. Unger, and H. Bischof,\n                      A variational model for interactive shape prior segmentation and real-time tracking\n                      , in Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, Lecture Notes in Comput. Sci. 5567, Springer-Verlag, Berlin, 2009, pp. 200\u2013211.","DOI":"10.1007\/978-3-642-02256-2_17"},{"key":"R69","unstructured":"G. Winkler,\n                      Image Analysis, Random Fields and Markov Chain Monte Carlo Methods\n                      , Springer, Berlin, 2006."},{"key":"R70","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds.\n                      Handbook of Semidefinite Programming. Theory, Algorithms, and Applications\n                      , Kluwer Academic Publishers, Boston, 2000.","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1007\/BF02677683"},{"key":"R72","unstructured":"C. Zach, D. Gallup, J.M. Frahm, and M. Niethammer,\n                      Fast global labeling for real-time stereo using multiple plane sweeps\n                      , in Proceedings of the Vision, Modeling, and Visualization Conference 2008, Konstanz, Germany, Aka GmbH, Heidelberg, 2008, pp. 243\u2013252."},{"key":"R73","doi-asserted-by":"crossref","unstructured":"C. Zach, M. Niethammer, and J.M. Frahm,\n                      Continuous maximal flows and Wulff shapes: Application to MRFs\n                      , in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009, pp. 1911\u20131918.","DOI":"10.1109\/CVPR.2009.5206565"},{"key":"R74","unstructured":"M. Zhu and T. Chan,\n                      An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration\n                      , CAM Report 08-34, UCLA, Los Angeles, CA, 2008."},{"key":"R75","doi-asserted-by":"crossref","unstructured":"W. P. Ziemer,\n                      Weakly Differentiable Functions. Sobolev Spaces and Functions of Bounded Variation\n                      , Springer, New York, 1989.","DOI":"10.1007\/978-1-4612-1015-3"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100805844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:36Z","timestamp":1787316996000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100805844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":75,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100805844"],"URL":"https:\/\/doi.org\/10.1137\/100805844","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}