An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision

The paper provides an experimental comparison of the efficiency of minimum cut/maximum flow algorithms as applied to exact or approximate energy minimization problems in low-level computer vision. It benchmarks the running times of several standard combinatorial optimization algorithms—including Goldberg-Tarjan style push-relabel methods and Ford-Fulkerson style augmenting-paths methods—as well as a new algorithm developed by the authors, using typical graphs arising in image restoration, stereo, and segmentation.

The study finds that in many cases the authors' new algorithm runs several times faster than any of the other methods, making near real-time performance possible for these vision tasks. By evaluating practical efficiency specifically within the context of computer vision rather than the general combinatorial optimization setting, the work gave the field a well-grounded, benchmarked choice of graph-cut solver, and an implementation was made available for research.