A study on continuous max-flow and min-cut approaches
Authors:
- 1 June 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 2217-2224
Abstract
We propose and study novel max-flow models in the continuous setting, which directly map the discrete graph-based max-flow problem to its continuous optimization formulation. We show such a continuous max-flow model leads to an equivalent min-cut problem in a natural way, as the corresponding dual model. In this regard, we revisit basic conceptions used in discrete max-flow / min-cut models and give their new explanations from a variational perspective. We also propose corresponding continuous max-flow and min-cut models constrained by priori supervised information and apply them to interactive image segmentation/labeling problems. We prove that the proposed continuous max-flow and min-cut models, with or without supervised constraints, give rise to a series of global binary solutions λ*(x) ϵ {0,1}, which globally solves the original nonconvex image partitioning problems. In addition, we propose novel and reliable multiplier-based max-flow algorithms. Their convergence is guaranteed by classical optimization theories. Experiments on image segmentation, unsupervised and supervised, validate the effectiveness of the discussed continuous max-flow and min-cut models and suggested max-flow based algorithms.Keywords
This publication has 13 references indexed in Scilit:
- A convex relaxation approach for computing minimal partitions2009
- Fast Global Minimization of the Active Contour/Snake ModelJournal of Mathematical Imaging and Vision, 2007
- Global Optimization for Shape Fitting2007
- Convergent Tree-Reweighted Message Passing for Energy MinimizationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- Algorithms for Finding Global Minimizers of Image Segmentation and Denoising ModelsSIAM Journal on Applied Mathematics, 2006
- Globally minimal surfaces by continuous maximal flowsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- What metrics can be approximated by geo-cuts, or global optimization of length/area and flux2005
- What energy functions can be minimized via graph cuts?IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Maximal flow through a domainMathematical Programming, 1983