UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

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

Boykov, Y.; Kolmogorov, V.; (2004) An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence , 26 (9) pp. 1124-1137. 10.1109/TPAMI.2004.60. Green open access

[img]
Preview
PDF
13383.pdf

Download (3MB)

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.

Type: Article
Title: An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Open access status: An open access version is available from UCL Discovery
DOI: 10.1109/TPAMI.2004.60
Publisher version: http://dx.doi.org/10.1109/TPAMI.2004.60
Language: English
Additional information: ©2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
UCL classification: UCL > School of BEAMS > Faculty of Engineering Science > Adastral Park
URI: http://discovery.ucl.ac.uk/id/eprint/13383
Downloads since deposit
5,508Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item