Combinatorial continuous maximum flow

DOI10.1137/100799186MaRDI QIDQ3113797zbMATH OpenOpenAlexFDO

Authors Camille Couprie, Leo Grady, Hugues Talbot, Laurent Najman

Publication date 25 January 2012

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.2733

zbMATH Keywords

discrete calculusimage segmentationinterior point methodsminimal surfacestotal variation minimization

Mathematics Subject Classification ID

PDEs in connection with mathematical programming (35Q90) PDEs in connection with control and optimization (35Q93) Computing methodologies for image processing (68U10) Convex programming (90C25) Programming involving graphs or networks (90C35) Interior-point methods (90C51)

Abstract: 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.

Recommendations

• A spatially continuous max-flow and min-cut framework for binary labeling problems
• Maximum flows and minimum cuts in the plane
• Maximum flows and minimum cuts in the plane
• scientific article; zbMATH DE number 1849127
• Maximum flows by incremental breadth-first search

Cited in

(12)

• Combinatorial approaches to multiflow problems
• Computing the effective crack energy of heterogeneous and anisotropic microstructures via anisotropic minimal surfaces
• Discrete and continuous models for partitioning problems
• A spatially continuous max-flow and min-cut framework for binary labeling problems
• Investigations on the influence of the boundary conditions when computing the effective crack energy of random heterogeneous materials using fast marching methods
• Maximum flows by incremental breadth-first search
• Theoretical Analysis of Active Contours on Graphs
• Maximum flows and minimum cuts in the plane
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Combinatorial acyclicity models for potential‐based flows
• A fast Fourier transform based method for computing the effective crack energy of a heterogeneous material on a combinatorially consistent grid
• Global binary optimization on graphs for classification of high-dimensional data

This page was built for publication: Combinatorial continuous maximum flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3113797)