An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Top Cited Papers
- 26 July 2004
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 26 (9) , 1124-1137
- https://doi.org/10.1109/tpami.2004.60
Abstract
Minimum cut/maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor 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 applications 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.Keywords
This publication has 27 references indexed in Scilit:
- What energy functions can be minimized via graph cuts?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Exact optimization for markov random fields with convex priorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Graphcut texturesPublished by Association for Computing Machinery (ACM) ,2003
- Fast approximate energy minimization via graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in VisionPublished by Springer Nature ,2001
- Random Sampling in Cut, Flow, and Network Design ProblemsMathematics of Operations Research, 1999
- On Implementing the Push—Relabel Method for the Maximum Flow ProblemAlgorithmica, 1997
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- An optimal graph theoretic approach to data clustering: theory and its application to image segmentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- A new approach to the maximum-flow problemJournal of the ACM, 1988