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 has 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 fit into the framework.