Tree-based iterated local search for Markov random fields with applications in image analysis
This addresses a fundamental computational bottleneck in probabilistic graphical models for researchers and practitioners in computer vision and image analysis, though it appears incremental as it builds on existing tree-based and local search techniques.
The paper tackles the computationally intractable problem of finding maximum a posteriori assignments for general Markov random fields by proposing a tree-based iterated local search method. The method shows competitive performance against state-of-the-art approaches in simulations and real-world computer vision tasks like stereo matching and image denoising, with significant computational gains.
The \emph{maximum a posteriori} (MAP) assignment for general structure Markov random fields (MRFs) is computationally intractable. In this paper, we exploit tree-based methods to efficiently address this problem. Our novel method, named Tree-based Iterated Local Search (T-ILS) takes advantage of the tractability of tree-structures embedded within MRFs to derive strong local search in an ILS framework. The method efficiently explores exponentially large neighborhood and does so with limited memory without any requirement on the cost functions. We evaluate the T-ILS in a simulation of Ising model and two real-world problems in computer vision: stereo matching, image denoising. Experimental results demonstrate that our methods are competitive against state-of-the-art rivals with a significant computational gain.