Skip to content

Latest commit

 

History

History
70 lines (64 loc) · 4.72 KB

2004-an-experimental-comparison-of-min-cut-max-flow-algorithms-for-energy-minimization-in-vision.md

File metadata and controls

70 lines (64 loc) · 4.72 KB
title authors fieldsOfStudy meta_key numCitedBy reading_status ref_count tags urls venue year
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Yuri Boykov
V. Kolmogorov
Computer Science
2004-an-experimental-comparison-of-min-cut-max-flow-algorithms-for-energy-minimization-in-vision
3581
TBD
58
gen-from-ref
other-default
paper
IEEE Transactions on Pattern Analysis and Machine Intelligence
2004

semanticscholar url

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

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.

Paper References

  1. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision.
  2. What energy functions can be minimized via graph cuts?
  3. A maximum-flow formulation of the N-camera stereo correspondence problem
  4. Computing geodesics and minimal surfaces via graph cuts
  5. An Optimal Graph Theoretic Approach to Data Clustering - Theory and Its Application to Image Segmentation
  6. Multi-camera Scene Reconstruction via Graph Cuts
  7. Random sampling in cut, flow, and network design problems
  8. Image segmentation by nested cuts
  9. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
  10. Stereo Without Epipolar Lines - A Maximum-Flow Formulation
  11. Segmentation by grouping junctions
  12. Graphcut textures - image and video synthesis using graph cuts
  13. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms
  14. MRF solutions for probabilistic optical flow formulations
  15. Computing visual correspondence with occlusions using graph cuts
  16. Faster shortest-path algorithms for planar graphs
  17. Exact voxel occupancy with graph cuts
  18. Markov random fields with efficient approximations
  19. A new approach to the maximum flow problem
  20. Minimal Surfaces for Stereo
  21. Level set methods and dynamic implicit surfaces
  22. Large Occlusion Stereo
  23. Fusion of color, shading and boundary information for factory pipe segmentation
  24. A new Bayesian framework for object recognition
  25. Exact Optimization for Markov Random Fields with Convex Priors
  26. On Implementing the Push-Relabel Method for the Maximum Flow Problem
  27. Flow in Planar Graphs with Multiple Sources and Sinks
  28. On Implementing Push-Relabel Method for the Maximum Flow Problem
  29. Incorporating Spatial Priors into an Information Theoretic Approach for fMRI Data Analysis
  30. Geometric partial differential equations and image analysis
  31. Occlusions, Discontinuities, and Epipolar Lines in Stereo
  32. Exact Maximum A Posteriori Estimation for Binary Images
  33. Algorithm for solution of a problem of maximal flow in a network with power estimation
  34. Combinatorial optimization
  35. Level Set Methods and Fast Marching Methods
  36. Medical Image Computing and Computer-Assisted Intervention - MICCAI 2006, 9th International Conference, Copenhagen, Denmark, October 1-6, 2006, Proceedings, Part II
  37. Geometric Level Set Methods in Imaging, Vision, and Graphics
  38. An Experimental Comparison of Stereo Algorithms
  39. Fast approximate energy minimization via graph cuts