MINIMIZATION OF MRF ENERGY WITH RELAXATION LABELING

Recently, there has been increasing interest in Markov random field (M RF) modeling for solving a variety of computer vision problems formula ted in terms of the maximum aposteriori (MAP) probability. When the la bel set is discrete, such as in image segmentation and matching, the m inimization is combinatorial. The objective of this paper is twofold: Firstly, we propose to use the continuous relaxation labeling (RL) as an alternative approach for the minimization. The motivation is that i t provides a good compromise between the solution quality and the comp utational cost. We show how the original combinatorial optimization ca n be converted into a form suitable for continuous RL. Secondly, we co mpare various minimization algorithms, namely, the RL algorithms propo sed by Rosenfeld et al., and by Hummel and Zucker, the mean field anne aling of Peterson and Soderberg simulated annealing of Kirkpatrick, th e iterative conditional modes (ICM) of Besag and an annealing version of ICM proposed in this paper. The comparisons are in terms of the min imized energy value (i.e., the solution quality), the required number of iterations (i.e., the computational cost), and also the dependence of each algorithm an heuristics.