next up previous index
Next: Maximization Formulation Up: Relaxation Labeling Previous: Relaxation Labeling

Representation of Continuous RL

In continuous RL, the labeling state for each site is represented as a position vector; for i, it is

subject to the following feasibility constraints

 

This was interpreted as a fuzzy assignment model   [Rosenfeld et al. 1976]. The real value reflects the strength with which i is assigned label I. Each lies in a hyperplane in the non-negative quadrant portion (simplex) of the multi-dimensional real space as shown in the shaded area of Fig.8.3. The feasible labeling assignment space is

 

The set is called a labeling assignment.   The feasible space for labeling assignments is the following product

 

  The final solution must be unambiguous

 

with meaning that i is unambiguously labeled I. This gives the unambiguous spaces for as  

 

So every in is one of the vectors , and corresponding to the ``corners'' of the simplex ( cf. Fig.8.3). The unambiguous labeling assignment space is

 

which consists of the corners of the space . Non-corner points in the continuous space provide routes to the corners of , i.e. the points in the discrete space . An unambiguous labeling assignment is related to the corresponding discrete labeling by

The unambiguity may be satisfied automatically upon convergence of some iterative algorithms or if not, has to be enforced e.g. using a maximum selection (winner-take-all) operation. However, the forced unambiguous solution is not necessarily a local minimum. How to ensure the result of a continuous RL algorithm to be an unambiguous one has been largely ignored in the literature.

  
Figure 8.3: The labeling space for with three labels. The feasible space is shown as the shaded area (simplex) and the unambiguous space consists of the three corner points.