An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision

Yuri Boykov, Vladimir Kolmogorov

In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), LNCS 2134, pp. 359-374, Sophia Antipolis, France, 2001


After ...(list of references) 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-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 interactive segmentation. In many cases our new algorithm works several times faster than any of the other methods making near real-time performance possible.

WHOLE PAPER: pdf file (359 Kb)

IMPROVED VERSION!!!: Our PAMI'04 paper describes an improved version of our new max-flow algorithm and contains significantly more experiments on applications in vision. Check out our new max-flow algorithm implementation.