A Scalable Graph-Cut Algorithm for N-D Grids

Andrew Delong and Yuri Boykov

In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Anchorage, June 2008.

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 [Goldberg-Tarjan'88] 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.


WHOLE PAPER: pdf file (768Kb)
IMPLEMENTATION: here