8.2.2
In this section, the relaxation labeling (RL) method is described as an approach for minimizing an energy
with a discrete label set. RL is originally proposed as a class
of parallel iterative numerical procedures which uses contextual
constraints to reduce ambiguities in image analysis
[Rosenfeld et al. 1976]. It has been widely used in image and
vision community. It is known that RL has a polynomial complexity yet
empirically produces good results.
Formally, Faugeras and Berthod (1981) define a class of global criteria in terms of transition probabilities. Peleg (1980) interprets RL in terms of Bayes analysis. Haralick (1983) illustrates RL as minimizing the expected loss from a Bayes viewpoint. Hummel and Zucker (1983) formulate the probabilistic relaxation approach as a global optimization problem in which a so called average local consistency is defined and maximized. They show that, computationally, finding consistent labeling is equivalent to solving a variational inequality. Using the notion of continuous RL, the combinatorial minimization is converted into a real minimization subject to linear constraints, and the combinatorial minimization is performed by constrained real minimization.
A development in relaxation labeling is the use of contextual constraints about the observed data. Li formulates an objective function for relaxation labeling in which contextual constraints from both the prior knowledge and the observation are considered [Li 1992a,Li 1992b,Li 1992c]. Kittler et al. (1993) later justify the formulation from probabilistic view point.