Computer Science – Computer Vision and Pattern Recognition
Scientific paper
2010-10-13
SIAM Journal on Imaging Sciences 4 (2011) 905-930
Computer Science
Computer Vision and Pattern Recognition
26 pages
Scientific paper
10.1137/100799186
Maximum flow (and minimum cut) algorithms have had a strong impact on computer vision. In particular, graph cuts 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 artefacts 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 artefacts 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.
Couprie Camille
Grady Leo
Najman Laurent
Talbot Hugues
No associations
LandOfFree
Combinatorial Continuous Maximal Flows does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Combinatorial Continuous Maximal Flows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Continuous Maximal Flows will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-227222