A Scalable graph-cut algorithm for N-D grids

Andrew Delong, Yuri Boykov
Univ. of Western Ontario, London, ON
IEEE International Conference on Computer Vision and Pattern Recognition In IEEE International Conference on Computer Vision and Pattern Recognition, Vol. 0 (June 2008), pp. 1-8.


   title={A scalable graph-cut algorithm for nd grids},

   author={Delong, A. and Boykov, Y.},

   booktitle={Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on},





Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: