An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision
An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision
复制标题
DOI：
10.1109/tpami.2004.60
复制
发表时间：
2004-09-01
影响因子：
23.6
通讯作者：
Kolmogorov, V
中科院分区：
文献类型：
--
作者：
Boykov, Y;Kolmogorov, V
在[15]、[31]、[19]、[8]、[25]、[5]之后，图上的最小割/最大流算法成为低级视觉中精确或近似能量最小化的越来越有用的工具。组合优化文献提供了许多具有不同多项式时间复杂度的最小割/最大流算法。然而，迄今为止，它们的实际效率主要在计算机视觉范围之外进行研究。本文的目的是提供视觉应用中最小割/最大流算法效率的实验比较。我们比较了几种标准算法以及我们最近开发的新算法的运行时间。我们研究的算法包括 Goldberg-Tarjan 风格的“push-relabel”方法和基于 Ford-Fulkerson 风格的“增强路径”的算法。我们在图像恢复、立体和分割背景下的许多典型图上对这些算法进行了基准测试。在许多情况下，我们的新算法的运行速度比任何其他方法快几倍，从而实现近乎实时的性能。我们的最大流/最小割算法的实现可根据请求用于研究目的。
After [15], [31], [19], [8], [25], [5], 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/maxflow 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.