A Scalable graph-cut algorithm for N-D grids
Authors:
- 1 June 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 1-8
Abstract
Global optimisation via s-t graph cuts is widely used in computer vision and graphics. To obtain high-resolution output, graph cut methods must construct massive N-D grid-graphs containing billions of vertices. We show that when these graphs do not fit into physical memory, current max-flow/min-cut algorithms-the workhorse of graph cut methods-are totally impractical. Others have resorted to banded or hierarchical approximation methods that get trapped in local minima, which loses the main benefit of global optimisation. We enhance the push-relabel algorithm for maximum flow [14] with two practical contributions. First, true global minima can now be computed on immense grid-like graphs too large for physical memory. These graphs are ubiquitous in computer vision, medical imaging and graphics. Second, for commodity multi-core platforms our algorithm attains near-linear speedup with respect to number of processors. To achieve these goals, we generalised the standard relabeling operations associated with push-relabel.Keywords
This publication has 17 references indexed in Scilit:
- Optimizing Binary MRFs via Extended Roof Duality2007
- Global Optimization for Shape Fitting2007
- Minimizing Nonsubmodular Functions with Graph Cuts-A ReviewIEEE Transactions on Pattern Analysis and Machine Intelligence, 2007
- Multi-View Stereo via Graph Cuts on the Dual of an Adaptive Tetrahedral Mesh2007
- Graph Cuts and Efficient N-D Image SegmentationInternational Journal of Computer Vision, 2006
- Multi-View Stereo via Volumetric Graph-Cuts2005
- A multilevel banded graph cuts method for fast image segmentation2005
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956