A tiered move-making algorithm for general pairwise MRFs

A large number of problems in computer vision can be modeled as energy minimization problems in a markov random field (MRF) framework. Many methods have been developed over the years for efficient inference, especially in pairwise MRFs. In general there is a trade-off between the complexity/efficiency of the algorithm and its convergence properties, with certain problems requiring more complex inference to handle general pairwise potentials. Graphcuts based α-expansion performs well on certain classes of energies, and sequential tree reweighted message passing (TRWS) and loopy belief propagation (LBP) can be used for non-submodular cases. These methods though suffer from poor convergence and often oscillate between solutions. In this paper, we propose a tiered move making algorithm which is an iterative method. Each move to the next configuration is based on the current labeling and an optimal tiered move, where each tiered move requires one application of the dynamic programming based tiered labeling method introduced in Felzenszwalb et. al. [2]. The algorithm converges to a local minimum for any general pairwise potential, and we give a theoretical analysis of the properties of the algorithm, characterizing the situations in which we can expect good performance. We evaluate the algorithm on many benchmark labeling problems such as stereo, image segmentation, image stitching and image denoising, as well as random energy minimization. Our method consistently gets better energy values than α-expansion, LBP, quadratic pseudo-boolean optimization (QPBO), and is competitive with TRWS.