{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:39:05Z","timestamp":1740123545274,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Vis"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many problems in imaging and low-level vision can be formulated as nonconvex variational problems. A promising class of approaches to tackle such problems are convex relaxation methods, which consider a lifting of the energy functional to a higher-dimensional space. However, they come with increased memory requirements due to the lifting. The present paper is an extended version of the earlier conference paper by Ye et al. (in: DAGM German conference on pattern recognition (GCPR), 2021) which combined two recent approaches to make lifting more scalable: product-space relaxation and sublabel-accurate discretization. Furthermore, it is shown that a simple cutting-plane method can be used to solve the resulting semi-infinite optimization problem. This journal version extends the previous conference work with additional experiments, a more detailed outline of the complete algorithm and a user-friendly introduction to functional lifting methods.<\/jats:p>","DOI":"10.1007\/s11263-022-01704-7","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:02:51Z","timestamp":1667044971000},"page":"346-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Cutting-Plane Method for Sublabel-Accurate Relaxation of Problems with Product Label Spaces"],"prefix":"10.1007","volume":"131","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6627-8783","authenticated-orcid":false,"given":"Zhenzhang","family":"Ye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bjoern","family":"Haefner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yvain","family":"Qu\u00e9au","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"M\u00f6llenhoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Cremers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"issue":"1","key":"1704_CR1","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10107-018-1248-6","volume":"175","author":"F Bach","year":"2019","unstructured":"Bach, F. (2019). Submodular functions: From discrete to continuous domains. Mathematical Programming, 175(1), 419\u2013459.","journal-title":"Mathematical Programming"},{"issue":"1","key":"1704_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11263-010-0390-2","volume":"92","author":"S Baker","year":"2011","unstructured":"Baker, S., Scharstein, D., Lewis, J. P., Roth, S., Black, M. J., & Szeliski, R. (2011). A database and evaluation methodology for optical flow. International Journal of Computer Vision, 92(1), 1\u201331.","journal-title":"International Journal of Computer Vision"},{"key":"1704_CR3","doi-asserted-by":"crossref","unstructured":"Bauermeister, H., Laude, E., M\u00f6llenhoff, T., Moeller, M., & Cremers, D. (2021). Lifting the convex conjugate in Lagrangian relaxations: A tractable approach for continuous Markov random fields. arXiv:2107.06028","DOI":"10.1137\/21M1433241"},{"issue":"2","key":"1704_CR4","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF00934096","volume":"19","author":"JW Blankenship","year":"1976","unstructured":"Blankenship, J. W., & Falk, J. E. (1976). Infinitely constrained optimization problems. Journal of Optimization Theory and Applications, 19(2), 261\u2013281.","journal-title":"Journal of Optimization Theory and Applications"},{"issue":"1","key":"1704_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"SP Boyd","year":"2011","unstructured":"Boyd, S. P., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1\u2013122.","journal-title":"Foundations and Trends in Machine Learning"},{"key":"1704_CR6","unstructured":"Caillaud, C., & Chambolle, A. (2020). Error estimates for finite differences approximations of the total variation. preprint hal-02539136."},{"issue":"2","key":"1704_CR7","first-page":"517","volume":"10","author":"G Carlier","year":"2003","unstructured":"Carlier, G. (2003). On a class of multidimensional optimal transportation problems. Journal of Convex Analysis, 10(2), 517\u2013530.","journal-title":"Journal of Convex Analysis"},{"issue":"263\u2013340","key":"1704_CR8","first-page":"227","volume":"9","author":"A Chambolle","year":"2010","unstructured":"Chambolle, A., Caselles, V., Cremers, D., Novaga, M., & Pock, T. (2010). An introduction to total variation for image analysis. Theoretical Foundations and Numerical Methods for Sparse Recovery, 9(263\u2013340), 227.","journal-title":"Theoretical Foundations and Numerical Methods for Sparse Recovery"},{"issue":"4","key":"1704_CR9","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1137\/110856733","volume":"5","author":"A Chambolle","year":"2012","unstructured":"Chambolle, A., Cremers, D., & Pock, T. (2012). A convex approach to minimal partitions. SIAM Journal on Imaging Sciences, 5(4), 1113\u20131158.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR10","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., & Pock, T. (2011). A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40, 120\u2013145.","journal-title":"Journal of Mathematical Imaging and Vision"},{"issue":"3","key":"1704_CR11","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/s10851-012-0396-1","volume":"47","author":"D Cremers","year":"2013","unstructured":"Cremers, D., & Strekalovskiy, E. (2013). Total cyclic variation and generalizations. Journal of Mathematical Imaging and Vision, 47(3), 258\u2013277.","journal-title":"Journal of Mathematical Imaging and Vision"},{"issue":"1","key":"1704_CR12","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10479-005-5724-z","volume":"134","author":"P de Boer","year":"2005","unstructured":"de Boer, P., Kroese, D. P., Mannor, S., & Rubinstein, R. Y. (2005). A tutorial on the cross-entropy method. Annals of Operations Research, 134(1), 19\u201367.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"1704_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"AP Dempster","year":"1977","unstructured":"Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1), 1\u201322.","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"},{"key":"1704_CR14","doi-asserted-by":"crossref","unstructured":"Fix, A., & Agarwal, S. (2014). Duality and the continuous graphical model. In European conference on computer vision (ECCV).","DOI":"10.1007\/978-3-319-10578-9_18"},{"issue":"1","key":"1704_CR15","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1137\/20M1333377","volume":"53","author":"N Ghoussoub","year":"2021","unstructured":"Ghoussoub, N., Kim, Y.-H., Lavenant, H., & Palmer, A. Z. (2021). Hidden convexity in a problem of nonlinear elasticity. SIAM Journal on Mathematical Analysis, 53(1), 1070\u20131087.","journal-title":"SIAM Journal on Mathematical Analysis"},{"issue":"3","key":"1704_CR16","doi-asserted-by":"publisher","first-page":"1626","DOI":"10.1137\/120862351","volume":"6","author":"B Goldluecke","year":"2013","unstructured":"Goldluecke, B., Strekalovskiy, E., & Cremers, D. (2013). Tight convex relaxations for vector-valued labeling. SIAM Journal on Imaging Sciences, 6(3), 1626\u20131664.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR17","doi-asserted-by":"crossref","unstructured":"G\u00f6rlitz, A., Geiping, J., & Kolb, A. (2019). Piecewise rigid scene flow with implicit motion segmentation. In International conference on intelligent robots and systems (IROS).","DOI":"10.1109\/IROS40897.2019.8968018"},{"issue":"1\u20133","key":"1704_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0004-3702(81)90024-2","volume":"17","author":"BK Horn","year":"1981","unstructured":"Horn, B. K., & Schunck, B. G. (1981). Determining optical flow. Artificial Intelligence, 17(1\u20133), 185\u2013203.","journal-title":"Artificial Intelligence"},{"issue":"10","key":"1704_CR19","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1109\/TPAMI.2003.1233908","volume":"25","author":"H Ishikawa","year":"2003","unstructured":"Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 1333\u20131336.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"1704_CR20","doi-asserted-by":"crossref","unstructured":"Kappes, J., Andres, B., Hamprecht, F., Schnorr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B., Lellmann, J., Komodakis, N., & Rother, C. (2013). A comparative study of modern inference techniques for discrete energy minimization problems. In IEEE conference on computer vision and pattern recognition (CVPR).","DOI":"10.1109\/CVPR.2013.175"},{"issue":"3","key":"1704_CR21","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J-B Lasserre","year":"2000","unstructured":"Lasserre, J.-B. (2000). Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3), 796\u2013817.","journal-title":"SIAM Journal on Optimization"},{"key":"1704_CR22","doi-asserted-by":"crossref","unstructured":"Laude, E., M\u00f6llenhoff, T., Moeller, M., Lellmann, J., & Cremers, D. (2016). Sublabel-accurate convex relaxation of vectorial multilabel energies. In European conference on computer vision (ECCV).","DOI":"10.1109\/CVPR.2016.428"},{"key":"1704_CR23","doi-asserted-by":"crossref","unstructured":"Lellmann, J., Kappes, J., Yuan, J., Becker, F., & Schn\u00f6rr, C. (2009). Convex multi-class image labeling by simplex-constrained total variation. In International conference on scale space and variational methods in computer vision (SSVM) (pp. 150\u2013162).","DOI":"10.1007\/978-3-642-02256-2_13"},{"issue":"3","key":"1704_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s11263-013-0621-4","volume":"104","author":"J Lellmann","year":"2013","unstructured":"Lellmann, J., Lellmann, B., Widmann, F., & Schn\u00f6rr, C. (2013). Discrete and continuous models for partitioning problems. International Journal of Computer Vision, 104(3), 241\u2013269.","journal-title":"International Journal of Computer Vision"},{"issue":"4","key":"1704_CR25","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.1137\/100805844","volume":"4","author":"J Lellmann","year":"2011","unstructured":"Lellmann, J., & Schn\u00f6rr, C. (2011). Continuous multiclass labeling approaches and algorithms. SIAM Journal on Imaging Sciences, 4(4), 1049\u20131096.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR26","doi-asserted-by":"crossref","unstructured":"Lellmann, J., Strekalovskiy, E., Koetter, S., & Cremers, D. (2013). Total variation regularization for functions with values in a manifold. In International conference on computer vision (ICCV).","DOI":"10.1109\/ICCV.2013.366"},{"key":"1704_CR27","first-page":"416","volume":"2","author":"D Martin","year":"2001","unstructured":"Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2001). A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In International conference on computer vision, 2, 416\u2013423.","journal-title":"In International conference on computer vision"},{"key":"1704_CR28","doi-asserted-by":"crossref","unstructured":"M\u00f6llenhoff, T., & Cremers, D. (2017). Sublabel-accurate discretization of nonconvex free-discontinuity problems. In International conference on computer vision (ICCV).","DOI":"10.1109\/ICCV.2017.134"},{"key":"1704_CR29","doi-asserted-by":"crossref","unstructured":"M\u00f6llenhoff, T., & Cremers, D. (2019). Lifting vectorial variational problems: A natural formulation based on geometric measure theory and discrete exterior calculus. In IEEE conference on computer vision and pattern recognition (CVPR).","DOI":"10.1109\/CVPR.2019.01137"},{"key":"1704_CR30","doi-asserted-by":"crossref","unstructured":"M\u00f6llenhoff, T., Laude, E., Moeller, M., Lellmann, J., & Cremers, D. (2016). Sublabel-accurate relaxation of nonconvex energies. IEEE conference on computer vision and pattern recognition (CVPR).","DOI":"10.1109\/CVPR.2016.428"},{"issue":"1\u201318","key":"1704_CR31","first-page":"65","volume":"1818","author":"Y Ollivier","year":"2017","unstructured":"Ollivier, Y., Arnold, L., Auger, A., & Hansen, N. (2017). Information-geometric optimization algorithms: A unifying picture via invariance principles. Journal of Machine Learning Research, 1818(1\u201318), 65.","journal-title":"Journal of Machine Learning Research"},{"key":"1704_CR32","unstructured":"Peng, J., Hazan, T., McAllester, D., & Urtasun, R. (2011). Convex max-product algorithms for continuous MRFs with applications to protein folding. In International conference on machine learning (ICML)."},{"key":"1704_CR33","doi-asserted-by":"crossref","unstructured":"Pock, T., & Chambolle, A. (2011). Diagonal preconditioning for first order primal\u2013dual algorithms in convex optimization. In International conference on computer vision (ICCV).","DOI":"10.1109\/ICCV.2011.6126441"},{"key":"1704_CR34","unstructured":"Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2009). An algorithm for minimizing the piecewise smooth Mumford\u2013Shah functional. In International conference on computer vision (ICCV)."},{"issue":"4","key":"1704_CR35","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/090757617","volume":"3","author":"T Pock","year":"2010","unstructured":"Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2010). Global solutions of variational models with convex regularization. SIAM Journal on Imaging Sciences, 3(4), 1122\u20131145.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR36","doi-asserted-by":"crossref","unstructured":"Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008). A convex formulation of continuous multi-label problems. In European conference on computer vision (ECCV).","DOI":"10.1007\/978-3-540-88690-7_59"},{"issue":"1\u20134","key":"1704_CR37","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","volume":"60","author":"LI Rudin","year":"1992","unstructured":"Rudin, L. I., Osher, S., & Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear phenomena, 60(1\u20134), 259\u2013268.","journal-title":"Physica D: Nonlinear phenomena"},{"key":"1704_CR38","unstructured":"Schaul, T. (2011). Studies in continuous black-box optimization (Unpublished doctoral dissertation) Technische Universit\u00e4t M\u00fcnchen."},{"issue":"3","key":"1704_CR39","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1137\/080744189","volume":"3","author":"F Steinke","year":"2010","unstructured":"Steinke, F., Hein, M., & Sch\u00f6lkopf, B. (2010). Nonparametric regression between general Riemannian manifolds. SIAM Journal on Imaging Sciences, 3(3), 527\u2013563.","journal-title":"SIAM Journal on Imaging Sciences"},{"issue":"1","key":"1704_CR40","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/130908348","volume":"7","author":"E Strekalovskiy","year":"2014","unstructured":"Strekalovskiy, E., Chambolle, A., & Cremers, D. (2014). Convex relaxation of vectorial problems with coupled regularization. SIAM Journal on Imaging Sciences, 7(1), 294\u2013336.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR41","volume-title":"Optimal transport: Old and new","author":"C Villani","year":"2008","unstructured":"Villani, C. (2008). Optimal transport: Old and new. Berlin: Springer."},{"key":"1704_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31351-7_3","volume-title":"Lifting methods for manifold-valued variational problems","author":"T Vogt","year":"2020","unstructured":"Vogt, T., Strekalovskiy, E., Cremers, D., & Lellmann, J. (2020). Lifting methods for manifold-valued variational problems. Handbook of variational methods for nonlinear geometric data: Springer."},{"issue":"4","key":"1704_CR43","doi-asserted-by":"publisher","first-page":"2226","DOI":"10.1137\/130951075","volume":"7","author":"A Weinmann","year":"2014","unstructured":"Weinmann, A., Demaret, L., & Storath, M. (2014). Total variation regularization for manifold-valued data. SIAM Journal on Imaging Sciences, 7(4), 2226\u20132257.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"1704_CR44","doi-asserted-by":"crossref","unstructured":"Ye, Z., Haefner, B., Qu\u00e9au, Y., M\u00f6llenhoff, T., & Cremers, D. (2021). Sublabel-accurate multilabeling meets product label spaces. In DAGM German conference on pattern recognition (GCPR).","DOI":"10.1007\/978-3-030-92659-5_1"},{"key":"1704_CR45","unstructured":"Zach, C. (2013). Dual decomposition for joint discrete-continuous optimization. In International conference on artificial intelligence and statistics (AISTATS)."},{"key":"1704_CR46","unstructured":"Zach, C., Gallup, D., Frahm, J.-M., & Niethammer, M. (2008). Fast global labeling for real-time stereo using multiple plane sweeps. In Proceedings of the vision, modeling and visualization workshop (VMV)."},{"key":"1704_CR47","doi-asserted-by":"crossref","unstructured":"Zach, C. & Kohli, P. (2012). A convex discrete-continuous approach for Markov random fields. In European conference on computer vision (ECCV).","DOI":"10.1007\/978-3-642-33783-3_28"}],"container-title":["International Journal of Computer Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-022-01704-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11263-022-01704-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11263-022-01704-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T20:46:26Z","timestamp":1728247586000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11263-022-01704-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,29]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1704"],"URL":"https:\/\/doi.org\/10.1007\/s11263-022-01704-7","relation":{},"ISSN":["0920-5691","1573-1405"],"issn-type":[{"type":"print","value":"0920-5691"},{"type":"electronic","value":"1573-1405"}],"subject":[],"published":{"date-parts":[[2022,10,29]]},"assertion":[{"value":"14 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}