Record Details

Hierarchical Logcut : A Fast And Efficient Way Of Energy Minimization Via Graph Cuts

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Hierarchical Logcut : A Fast And Efficient Way Of Energy Minimization Via Graph Cuts
 
Creator Kulkarni, Gaurav
 
Subject Computer Vision
Hierarchical Logcut
Graph Cut
Combinatorial Optimization
Markov Random Field (MRF)
Stereopsis
Heuristic Logcut Algorithm
Graph Cut Algorithm
Combinatorial Optimization Algorithm
Sequential Bit Plane Correction (SBPC) Algorithm
Graph Cut Optimization
Logcut Algorithm
Computer Science
 
Description Graph cuts have emerged as an important combinatorial optimization tool for many problems in vision. Most of the computer vision problems are discrete labeling problems. For example, in stereopsis, labels represent disparity and in image restoration, labels correspond to image intensities. Finding a good labeling involves optimization of an Energy Function. In computer vision, energy functions for discrete labeling problems can be elegantly formulated through Markov Random Field (MRF) based modeling and graph cut algorithms have been found to efficiently optimize wide class of such energy functions.
The main contribution of this thesis lies in developing an efficient combinatorial optimization algorithm which can be applied to a wide class of energy functions. Generally, graph cut algorithms deal sequentially with each label in the labeling problem at hand. The time complexity of these algorithms increases linearly with number of labels. Our algorithm, finds a solution/labeling in logarithmic time complexity without compromising on quality of solution.
In our work, we present an improved Logcut algorithm [24]. Logcut algorithm [24]
deals with finding individual bit values in integer representation of labels. It has logarithmic time complexity, but requires training over data set. Our improved Logcut (Heuristic-Logcut or H-Logcut) algorithm eliminates the need for training and obtains comparable results in respect to original Logcut algorithm.
Original Logcut algorithm cannot be initialized by a known labeling. We present a
new algorithm, Sequential Bit Plane Correction (SBPC) which overcomes this drawback of Logcut algorithm. SBPC algorithm starts from a known labeling and individually corrects each bit of a label. This algorithm too has logarithmic time complexity. SBPC in combination with H-Logcut algorithm, further improves rate of convergence and quality of results.
Finally, a hierarchical approach to graph cut optimization is used to further improve on rate of convergence of our algorithm. Generally, in a hierarchical approach first, a solution at coarser level is computed and then its result is used to initialize algorithm at a finer level. Here we have presented a novel way of initializing the algorithm at finer level through fusion move [25]. The SBPC and H-Logcut algorithms are extended to accommodate for hierarchical approach. It is found that this approach drastically improves the rate of convergence and attains a very low energy labeling.
The effectiveness of our approach is demonstrated on stereopsis. It is found that the algorithm significantly out performs all existing algorithms in terms of quality of solution as well as rate of convergence.
 
Contributor Ramakrishnan, K R
 
Date 2013-06-10T10:19:17Z
2013-06-10T10:19:17Z
2013-06-10
2010-06
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2038
http://etd.ncsi.iisc.ernet.in/abstracts/2634/G24424-Abs.pdf
 
Language en_US
 
Relation G24424