{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T03:09:15Z","timestamp":1787368155293,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Maximum flow (and minimum cut) algorithms have had a strong impact on computer vision. In particular, graph cut algorithms provide a mechanism for the discrete optimization of an energy functional which has been used in a variety of applications such as image segmentation, stereo, image stitching, and texture synthesis. Algorithms based on the classical formulation of max-flow defined on a graph are known to exhibit metrication artifacts in the solution. Therefore, a recent trend has been to instead employ a spatially continuous maximum flow (or the dual min-cut problem) in these same applications to produce solutions with no metrication errors. However, known fast continuous max-flow algorithms have no stopping criteria or have not been proved to converge. In this work, we revisit the continuous max-flow problem and show that the analogous discrete formulation is different from the classical max-flow problem. We then apply an appropriate combinatorial optimization technique to this combinatorial continuous max-flow (CCMF) problem to find a null-divergence solution that exhibits no metrication artifacts and may be solved exactly by a fast, efficient algorithm with provable convergence. Finally, by exhibiting the dual problem of our CCMF formulation, we clarify the fact, already proved by Nozawa in the continuous setting, that the max-flow and the total variation problems are not always equivalent.<\/jats:p>","DOI":"10.1137\/100799186","type":"journal-article","created":{"date-parts":[[2011,9,16]],"date-time":"2011-09-16T02:23:43Z","timestamp":1316139823000},"page":"905-930","source":"Crossref","is-referenced-by-count":25,"title":["Combinatorial Continuous Maximum Flow"],"prefix":"10.1137","volume":"4","author":[{"given":"Camille","family":"Couprie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo","family":"Grady","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hugues","family":"Talbot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"Najman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,9,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.12"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.82"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882364"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Boykov and M. P. Jolly,\n                      Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images\n                      , in Proceedings of ICCV'01, Vol. 1, 2001, pp. 105\u2013112.","DOI":"10.1109\/ICCV.2001.937505"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Boykov and V. Kolmogorov,\n                      Computing geodesics and minimal surfaces via graph cuts\n                      , in Proceedings of ICCV'03, 2003, pp. 26\u201333.","DOI":"10.1109\/ICCV.2003.1238310"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Buades, B. Coll, and J. M. Morel,\n                      A non-local algorithm for image denoising\n                      , in Proceedings of CVPR 2005, Vol. 2, 2005, pp. 60\u201365.","DOI":"10.1109\/CVPR.2005.38"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007979827043"},{"key":"R10","unstructured":"A. Chambolle, D. Cremers, and T. Pock,\n                      A Convex Approach for Computing Minimal Partitions\n                      , Technical report 649, Ecole Polytechnique CMAP, Palaiseau Cedex, France, 2008."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMIV.0000011325.36760.1e"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/040615286"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-006-0644-3"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2008.924284"},{"key":"R16","unstructured":"C. L. Fefferman,\n                      Existence and Smoothness of the Navier\u2013Stokes Equation\n                      , http:\/\/www.claymath.org\/millennium\/Navier-Stokes_Equations\/navierstokes.pdf http:\/\/www.claymath.org\/millennium\/Navier-Stokes_Equations\/navierstokes.pdf."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/060669358"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/040608982"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/080725891"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2009.2028258"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"L. Grady, T. Schiwetz, S. Aharon, and R. Westermann,\n                      Random walks for interactive organ segmentation in two and three dimensions: Implementation and validation\n                      , in Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention, 2005, pp. 773\u2013780.","DOI":"10.1007\/11566489_95"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"L. Grady and E. L. Schwartz,\n                      Faster graph-theoretic image processing via small-world and quadtree topologies\n                      , in Proceedings of CVPR, Vol. 2, 2004, pp. 360\u2013365.","DOI":"10.1109\/CVPR.2004.1315186"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"L. J. Grady and J. R. Polimeni,\n                      Discrete Calculus: Applied Analysis on Graphs for Computational Science\n                      , Springer, London, 2010.","DOI":"10.1007\/978-1-84996-290-2"},{"key":"R26","unstructured":"A. N. Hirani,\n                      Discrete Exterior Calculus\n                      , Ph.D. thesis, California Insitute of Technology, Pasdena, CA, 2003."},{"key":"R27","unstructured":"M. Iri,\n                      Theory of flows in continua as approximation to flows in networks\n                      , in Survey of Mathematical Programming, North\u2013Holland, Amsterdam, 1979, pp. 263\u2013278."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1233908"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF00133570"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. Kruger and R. Westermann,\n                      Linear algebra operators for GPU implementation of numerical algorithms\n                      , in Proceedings of SIGGRAPH 2003, 2003, pp. 908\u2013916.","DOI":"10.1145\/1201775.882363"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9590.2006.00357.x"},{"key":"R33","unstructured":"Y. Nesterov,\n                      Gradient Methods for Minimizing Composite Objective Function\n                      , CORE discussion papers 2007076, Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE), Louvain-a-Neuve, Belgium, 2007."},{"key":"R34","first-page":"805","volume":"27","author":"Nozawa R.","year":"1990","journal-title":"Osaka J. Math","ISSN":"https:\/\/id.crossref.org\/issn\/0030-6126","issn-type":"print"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582067"},{"key":"R36","unstructured":"N. Paragios,\n                      Geodesic Active Regions and Level Set Methods: Contributions and Applications in Artificial Vision\n                      , Ph.D. thesis, INRIA Sophia Antipolis, Sophia Antipolis Cedex, France, 2000."},{"key":"R37","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 ICCV'09, 2009, pp. 1133\u20131140.","DOI":"10.1109\/ICCV.2009.5459348"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"T. Pock, T. Schoenemann, G. Graber, H. Bischof, and D. Cremers,\n                      A convex formulation of continuous multi-label problems\n                      , in Proceedings of ECCV'08, 2008, pp. 792\u2013805.","DOI":"10.1007\/978-3-540-88690-7_59"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015720"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"J. A. Sethian,\n                      Level Set Methods and Fast Marching Methods\n                      , Cambridge University Press, Cambridge, UK, 1999.","DOI":"10.1137\/S0036144598347059"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"J. H. D. Shulman and J. Y. Herv\u00e9,\n                      Regularization of discontinuous flow fields\n                      , in Proceedings of the Workshop on Visual Motion, 1989, pp. 81\u201386.","DOI":"10.1109\/WVM.1989.47097"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592050"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-009-9471-6"},{"key":"R45","unstructured":"M. Unger, T. Pock, and H. Bischof,\n                      Interactive Globally Optimal Image Segmentation\n                      , Technical report ICG-TR-08\/02, Graz University of Technology, Graz, Austria, 2008."},{"key":"R46","doi-asserted-by":"crossref","unstructured":"M. Unger, T. Pock, W. Trobin, D. Cremers, and H. Bischof,\n                      TVSeg - Interactive total variation based image segmentation\n                      , in Proceedings of BMVC'08, 2008.","DOI":"10.5244\/C.22.40"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"},{"key":"R48","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 VMV'08, 2008, pp. 243\u2013252."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/090746379"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100799186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:24Z","timestamp":1787318724000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100799186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100799186"],"URL":"https:\/\/doi.org\/10.1137\/100799186","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}