Research: Graph Cuts






Misc Work


About Me

Graph cuts or maximum flow (minimum cut) algorithm form the first part of my thesis work. These algorithms forms the basis of many optimization algorithms in computer vision. Many MRF-MAP optimization algorithms like (alpha-expansion, fast-pd) also uses these algorithms in their inner iterations. The work was published at ECCV 2010 held in Crete, Greece.

I plan to release source and binary version of implementation soon at this page.


An Efficient Graph Cut Algorithm for Computer Vision Problems

Download PDF


Graph cuts has emerged as a preferred method to solve a class of energy minimization problems in computer vision. It has been shown that graph cut algorithms designed keeping the structure of vision based flow graphs in mind are more efficient than known strongly polynomial time max-flow algorithms based on preflow push or shortest augmenting path paradigms [1]. We present here a new algorithm for graph cuts which not only exploits the structural properties inherent in image based grid graphs but also combines the basic paradigms of max-flow theory in a novel way. The algorithm has a strongly polynomial time bound. It has been bench-marked using samples from Middlebury [2] and UWO [3] database. It runs faster on all 2D samples and is at least two to three times faster on 70% of 2D and 3D samples in comparison to the algorithm reported in [1].


@incollection {springerlink:10.1007/978-3-642-15558-1_40,
author = {Arora, Chetan and Banerjee, Subhashis and Kalra, Prem and Maheshwari, S.},
affiliation = {Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, India},
title = {An Efficient Graph Cut Algorithm for Computer Vision Problems},
booktitle = {Computer Vision ECCV 2010},
series = {Lecture Notes in Computer Science},
editor = {Daniilidis, Kostas and Maragos, Petros and Paragios, Nikos},
publisher = {Springer Berlin / Heidelberg},
isbn = {},
pages = {552-565},
volume = {6313},
url = {},
note = {10.1007/978-3-642-15558-1_40},
year = {2010}

Home  |  Products   |   Research   |   Misc Work   |   Software   |   About Me