Minimization of MRF Energy with Relaxation Labeling
Recently, there has been increasing interest in Markovrandom field (MRF) modeling for solving a variety of computer visionproblems formulated in terms of the maximum a posteriori(MAP) probability. When the label set is discrete, such as in imagesegmentation and matching, the minimization is combinatorial. Theobjective of this paper is twofold: Firstly, we propose to use thecontinuous relaxation labeling (RL) as an alternative approach forthe minimization. The motivation is that it provides a goodcompromise between the solution quality and the computational cost.We show how the original combinatorial optimization can be convertedinto a form suitable for continuous RL. Secondly, we compare variousminimization algorithms, namely, the RL algorithms proposed byRosenfeld et al., and by Hummel and Zucker, the mean field annealing ofPeterson and Soderberg, simulated annealing of Kirkpatrick, theiterative conditional modes (ICM) of Besag and an annealing versionof ICM proposed in this paper. The comparisons are in terms of theminimized energy value (i.e., the solution quality), the requirednumber of iterations (i.e., the computational cost), and also thedependence of each algorithm on heuristics.