Hybrid Approaches for MRF Optimization: Combination of Stochastic and Deterministic Methods

Abstract

Markov Random Field (MRF) models are of fundamental importance in computer vision. Many vision problems have been successfully formulated in MRF optimization. They include stereo matching, segmentation, denoising, and inpainting, to mention just a few. To solve them effectively, numerous algorithms have been developed. Although many of them produce good results for relatively easy problems, they are still unsatisfactory when it comes to more difficult MRF problems such as non-submodular energy functions, strongly coupled MRFs, and high-order clique potentials.

In this dissertation, several optimization methods are proposed. The main idea of proposed methods is to combine stochastic and deterministic optimization methods. Stochastic methods encourage more exploration in the solution space. On the other hand, deterministic methods enable more efficient exploitation. By combining those two approaches, it is able to obtain better solution. To this end, two stochastic methodologies are exploited for the framework of combination: Markov chain Monte Carlo (MCMC) and stochastic approximation.

First methodology is the MCMC. Based on MCMC framework, population based MCMC (Pop-MCMC), MCMC with General Deterministic algorithms (MCMC-GD), and fusion move driven MCMC (MCMC-F) are proposed. Although MCMC provides an elegant framework of which global convergence is provable, it has the slow convergence rate. To overcome, population-based framework and combination with deterministic methods are used. It thereby enables global moves by exchanging information between samples, which in turn, leads to faster mixing rate. In the view of optimization, it means that we can reach a lower energy state rapidly.

Second methodology is the stochastic approximation. In stochastic approximation, the objective function for optimization is approximated in stochastic way. To apply this approach to MRF optimization, graph approximation scheme is proposed for the approximation of the energy function. By using this scheme, it alleviates the problem of non-submodularity and partial labeling. This stochastic approach framework is combined with graph cuts which is very efficient algorithm for easy MRF optimizations. By this combination, fusion with graph approximation-based proposals (GA-fusion) is developed.

Extensive experiments support that the proposed algorithms are effective across different classes of energy functions. The proposed algorithms are applied in many different computer vision applications including stereo matching, photo montage, inpaining, image deconvolution, and texture restoration. Those algorithms are further analyzed on synthetic MRF problems while varying the difficulties of the problems as well as the parameters for each algorithm.