After [13, 25, 15, 16, 3, 6] minimum cut/maximum flow algorithms on graphs emerged as an increasingly
useful tool for exact or approximate energy minimization in low-level vision.
The combinatorial optimization literature provides many min-cut/max-flow
algorithms with different polynomial time complexity. Their practical
efficiency, however, has to date been studied mainly outside the scope
of computer vision. The goal of this paper is to provide an experimental
comparison of the efficiency of min-cut/max flow algorithms for energy
minimization in vision. We compare the running times of several standard
algorithms, as well as a new algorithm that we have recently developed.
The algorithms we study include both Goldberg-Tarjan style "push-relabel"
methods and algorithms based on Ford-Fulkerson style augmenting paths.
We benchmark these algorithms on a number of typical graphs in the contexts
of image restoration, stereo, and segmentation. In many cases
our new algorithm works several times faster than any of the other methods
making near real-time performance possible. An implementation of our
max-flow/min-cut algorithm is available upon request for research purposes.