Authors
Yuri Boykov, Vladimir Kolmogorov
Publication date
2004/7/26
Journal
IEEE transactions on pattern analysis and machine intelligence
Volume
26
Issue
9
Pages
1124-1137
Publisher
IEEE
Description
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 …
Total citations
Scholar articles
Y Boykov, V Kolmogorov - IEEE transactions on pattern analysis and machine …, 2004