Toward global solution to MAP image estimation: Using Common structure of local solutions

Abstract

The maximum a posteriori (MAP) principle is often used in image restoration and segmentation to define the optimal solution when both the prior and likelihood distributions are available. MAP estimation is equivalent to minimizing an energy function. It is desirable to find the global minimum. However, the minimization in the MAP image estimation is non-trivial due to the use of contextual constraints between pixels. Steepest descent methods such as ICM quickly finds a local minimum but the solution quality depends much on the initialization. Some initializations are better than others. In this paper, we present an iterative optimization algorithm, called the Comb algorithm, for approximating the global minmum. The Comb maintains a number of best local minima found so far. It uses the Common structure of Best local minima (hence “Comb”) to derive new initial configurations. Because the derived configurations contain some structure resembling that of the global minimum, they may provide good starting points for local search to approach the global minimum. Experimental comparisons show that the Comb produces solutions of quality much better than ICM and comparable to simulated annealing.