Abstract

Monte Carlo methods and their subsequent simulated an- nealing are able to minimize general energy functions. However, the slow convergence of simulated annealing compared with more recent deter- ministic algorithms such as graph cuts and belief propagation hinders its popularity over the large dimensional Markov Random Field (MRF). In this paper, we propose a new efficient sampling-based optimization algorithm called WA (Window Annealing) over squared lattice MRF, in which cluster sampling and annealing concepts are combined together. Unlike the conventional annealing process in which only the tempera- ture variable is scheduled, we design a series of artificial ”guiding” (aux- iliary) probability distributions based on the general sequential Monte Carlo framework. These auxiliary distributions lead to the maximum a posteriori (MAP) state by scheduling both the temperature and the proposed maximum size of the windows (rectangular cluster) variable. This new annealing scheme greatly enhances the mixing rate and con- sequently reduces convergence time. Moreover, by adopting the integral image technique for computation of the proposal probability of a sampled window, we can achieve a dramatic reduction in overall computations. The proposed WA is compared with several existing Monte Carlo based optimization techniques as well as state-of-the-art deterministic methods including Graph Cut (GC) and sequential tree re-weighted belief propa- gation (TRW-S) in the pairwise MRF stereo problem. The experimental results demonstrate that the proposed WA method is comparable with GC in both speed and obtained energy level.