{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T10:22:04Z","timestamp":1789726924302,"version":"4.0.1"},"reference-count":55,"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":[[2012,1]]},"abstract":"<jats:p>This study investigates a convex relaxation approach to figure-ground separation with a global distribution matching prior evaluated by the Bhattacharyya measure. The problem amounts to finding a region that most closely matches a known model distribution. It has been previously addressed by curve evolution, which leads to suboptimal and computationally intensive algorithms, or by graph cuts, which result in metrication errors. Solving a sequence of convex subproblems, the proposed relaxation is based on a novel bound of the Bhattacharyya measure which yields an algorithm robust to initial conditions. Furthermore, we propose a novel flow configuration that accounts for labeling-function variations, unlike existing configurations. This leads to a new max-flow formulation which is dual to the convex relaxed subproblems we obtained. We further prove that such a formulation yields exact and global solutions to the original, nonconvex subproblems. A comprehensive experimental evaluation on the Microsoft GrabCut database demonstrates that our approach yields improvements in optimality and accuracy over related recent methods.<\/jats:p>","DOI":"10.1137\/110850372","type":"journal-article","created":{"date-parts":[[2012,12,4]],"date-time":"2012-12-04T16:55:29Z","timestamp":1354640129000},"page":"1333-1354","source":"Crossref","is-referenced-by-count":25,"title":["A Convex Max-Flow Approach to Distribution-Based Figure-Ground Separation"],"prefix":"10.1137","volume":"5","author":[{"given":"Kumaradevan","family":"Punithakumar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ismail Ben","family":"Ayed","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuo","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Boykov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,12,4]]},"reference":[{"key":"atypb1","first-page":"363","volume":"34","author":"Aherne F.","year":"1998","journal-title":"Kybernetika (Prague)"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036139902408928"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"D. Batra, A. Kowdle, D. Parikh, J. Luo, and T. Chen,<i>iCoseg: Interactive co-segmentation with intelligent scribble guidance<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2010.","DOI":"10.1109\/CVPR.2010.5540080"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"I. Ben Ayed, H.M. Chen, K. Punithakumar, I. Ross, and S. Li,<i>Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the Bhattacharyya measure<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2010.","DOI":"10.1109\/CVPR.2010.5540045"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"I. Ben Ayed, Shuo Li, and I. Ross,<i>Tracking distributions with an overlap prior<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.","DOI":"10.1109\/CVPR.2008.4587428"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0249-6"},{"key":"atypb7","unstructured":"D. P. Bertsekas,<i>Constrained Optimization and Lagrange Multiplier Methods<\/i> Comput. Sci. Appl. Math., Academic Press, New York, 1982."},{"key":"atypb8","unstructured":"D. P. Bertsekas,<i>Nonlinear Programming<\/i> Athena Scientific, Nashua, NH, 1999."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-7934-5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2001.937505"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.60"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-007-0002-0"},{"key":"atypb14","first-page":"136","author":"Chambolle A.","year":"2005","journal-title":"Heidelberg"},{"key":"atypb15","unstructured":"A. Chambolle, D. Cremers, and T. Pock,<i>A Convex Approach for Computing Minimal Partitions<\/i> Technical report TR-2008-05, Department of Computer Science, University of Bonn, Bonn, Germany, 2008."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/040615286"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"T. F. Chan and J. Shen,<i>Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods<\/i> SIAM, Philadelphia, 2005.","DOI":"10.1137\/1.9780898717877"},{"key":"atypb18","unstructured":"S. Chen and R. J. Radke,<i>Level set segmentation with both shape and intensity priors<\/i> in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009."},{"key":"atypb19","first-page":"144","author":"Cho M.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1195991"},{"key":"atypb21","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,<i>Introduction to Algorithms<\/i> 2nd ed., MIT Press, Cambridge, MA, 2001."},{"key":"atypb22","unstructured":"J. Cui, Q. Yang, F. Wen, Q. Wu, C. Zhang, L. V. Gool, and X. Tang,<i>Transductive object cutout<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008."},{"key":"atypb23","first-page":"5","volume":"25","author":"Deheuvels P.","year":"1977","journal-title":"Rev. Statist. Appl."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2003.821445"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"A. C. Gallagher and T. Chen,<i>Clothing cosegmentation for recognizing people<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.","DOI":"10.1109\/CVPR.2008.4587481"},{"key":"atypb27","unstructured":"E. Giusti,<i>Minimal Surfaces and Functions of Bounded Variation<\/i> Australian National University, Canberra, Australia, 1977."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-009-9331-z"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum and V. Singh,<i>An efficient algorithm for co-segmentation<\/i> in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009.","DOI":"10.1109\/ICCV.2009.5459261"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1996.10476701"},{"key":"atypb31","first-page":"332","author":"Klodt M.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"V. Kolmogorov and Y. Boykov,<i>What metrics can be approximated by geo-cuts, or global optimization of length\/area and flux<\/i> in Proceedings of the Tenth IEEE International Conference on Computer Vision, 2005.","DOI":"10.1109\/ICCV.2005.252"},{"key":"atypb33","first-page":"150","author":"Lellmann J.","year":"2009","journal-title":"Heidelberg"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"V. Lempitsky, P. Kohli, C. Rother, and T. Sharp,<i>Image segmentation with a bounding box prior<\/i> in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009, pp. 277-284.","DOI":"10.1109\/ICCV.2009.5459262"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2007.908073"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"L. Mukherjee and V. Singh,<i>Scale invariant cosegmentation for image groups<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2011.","DOI":"10.1109\/CVPR.2011.5995420"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"L. Mukherjee, V. Singh, and C. R. Dyer,<i>Half-integrality based algorithms for cosegmentation of images<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009.","DOI":"10.1109\/CVPRW.2009.5206652"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0234-0"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177704472"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"V.Q. Pham, K. Takahashi, and T. Naemura,<i>Foreground-background segmentation using iterated distribution matching<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2011.","DOI":"10.1109\/CVPR.2011.5995356"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"T. Pock, A. Chambolle, D. Cremers, and H. Bischof,<i>A convex relaxation approach for computing minimal partitions<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009.","DOI":"10.1109\/CVPRW.2009.5206604"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/BF00934777"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.97"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"R. T. Rockafellar and R. J.B. Wets,<i>Variational Analysis<\/i> Grundlehren Math. Wiss. 317, Springer-Verlag, Berlin, 1998.","DOI":"10.1007\/978-3-642-02431-3"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015720"},{"key":"atypb46","unstructured":"C. Rother, T. Minka, A. Blake, and V. Kolmogorov,<i>Cosegmentation of image pairs by histogram matching-incorporating a global constraint into MRFs<\/i> in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006."},{"key":"atypb47","first-page":"1605","author":"Russell B. C.","year":"2006","journal-title":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592050"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"S. Vicente, V. Kolmogorov, and C. Rother,<i>Joint optimization of segmentation and appearance models<\/i> in Proceedings of the 12th IEEE International Conference on Computer Vision, 2009.","DOI":"10.1109\/ICCV.2009.5459287"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"S. Vicente, V. Kolmogorov, and C. Rother,<i>Cosegmentation revisited: Models and optimization<\/i> in Proceedings of the 11th European Conference on Computer Vision, Springer-Verlag, Berlin, Heidelberg, 2010.","DOI":"10.1007\/978-3-642-15552-9_34"},{"key":"atypb51","first-page":"2217","author":"Vicente S.","year":"2011","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"J. Yuan, E. Bae, and X.C. Tai,<i>A study on continuous max-flow and min-cut approaches<\/i> in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2010.","DOI":"10.1109\/CVPR.2010.5539903"},{"key":"atypb53","unstructured":"J. Yuan, E. Bae, X.C. Tai, and Y. Boykov,<i>A Study on Continuous Max-Flow and Min-Cut Approaches. PartI:Binary Labeling<\/i> Technical report CAM 10-61, UCLA, Los Angeles, CA, 2010."},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"J. Yuan, E. Bae, X.C. Tai, and Y. Boykov,<i>A continuous max-flow approach to Potts model<\/i> in Proceedings of the 11th European Conference on Computer Vision, Springer-Verlag, Berlin, Heidelberg, 2010.","DOI":"10.1007\/978-3-642-15567-3_28"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.31"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110850372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:30:59Z","timestamp":1787322659000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110850372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110850372"],"URL":"https:\/\/doi.org\/10.1137\/110850372","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}