Fast Graph Cuts using Shrink-Expand Reparameterization

Parikshit Sakurikar, P. J. Narayanan
Center for Visual Information Technology, International Institute of Information Technology, Hyderabad, India
IEEE Workshop on the Applications of Computer Vision (WACV), 2012


   title={Fast Graph Cuts using Shrink-Expand Reparameterization},

   author={Sakurikar, P. and Narayanan, PJ},



Download Download (PDF)   View View   Source Source   



Global optimization of MRF energy using graph cuts is widely used in computer vision. As the images are getting larger, faster graph cuts are needed without sacrificing optimality. Initializing or reparameterizing a graph using results of a similar one has provided efficiency in the past. In this paper, we present a method to speedup graph cuts using shrink-expand reparameterization. Our scheme merges the nodes of a given graph to shrink it. The resulting graph and its mincut are expanded and used to reparameterize the original graph for faster convergence. Graph shrinking can be done in different ways. We use a block-wise shrinking similar to multiresolution processing of images in our Multiresolution Cuts algorithm. We also develop a hybrid approach that can mix nodes from different levels without affecting optimality. Our algorithm is particularly suited for processing large images. The processing time on the full detail graph reduces nearly by a factor of 4. The overall application time including all book-keeping is faster by a factor of 2 on various types of images.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: