Lagrangian-based methods for finding MAP solutions for MRF models

Finding maximum a posteriori (MAP) solutions from noisy images based on a prior Markov random field (MRF) model is a huge computational task. In this paper, we transform the computational problem into an integer linear programming (ILP) problem. We explore the use of Lagrange relaxation (LR) methods for solving the MAP problem. In particular, three different algorithms based on LR are presented. All the methods are competitive alternatives to the commonly used simulation-based algorithms based on Markov Chain Monte Carlo techniques. In all the examples (including both simulated and real images) that have been tested, the best method essentially finds a MAP solution in a small number of iterations. In addition, LR methods provide lower and upper bounds for the posterior, which makes it possible to evaluate the quality of solutions and to construct a stopping criterion for the algorithm. Although additive Gaussian noise models have been applied, any additive noise model fits into the framework.