A hybrid approach for MRF optimization problems: Combination of stochastic sampling and deterministic algorithms

In computer vision, many applications have been formulated as Markov Random Field (MRF) optimization or energy minimization problems. To solve them effectively, numerous algorithms have been developed, including the deterministic and stochastic sampling algorithms. The deterministic algorithms include Graph Cuts, Belief Propagation, and Tree-Reweighted Message Passing while the stochastic sampling algorithms include Simulated Annealing, Markov Chain Monte Carlo (MCMC), and Population-based Markov Chain Monte Carlo (Pop-MCMC). 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 paper, we propose a new hybrid algorithm which successfully combines the stochastic sampling and deterministic algorithms to solve such challenging MRF problems. By combining those two different approaches in a unified framework, we can utilize the advantages from both approaches. For example, the deterministic algorithms guide the solution to rapidly move into lower energy state of the solution space. The stochastic sampling algorithms help the solution not to be stuck in local minima and explore larger area. Consequently, the proposed algorithm substantially increases the quality of the solutions. We present a thorough analysis of the algorithm in synthetic MRF problems by controlling the hardness of the problems. We also demonstrate the effectiveness of the proposed algorithm by the experiments on real applications including photomontage and inpainting.