# Catalogue of Artificial Intelligence Techniques

## Relaxation Labelling

**Keywords:**
blocks
world, confidence measures, filtering algorithm, line labelling

### Categories: Vision

Author(s): **Jon Mayhew**

Relaxation labelling is a technique for assigning globally consistent labels or values to nodes in a network subject to local constraints, by iteratively propagating the effects of Constraints through the net. It has its mathematical origins as a technique in numerical analysis for the solution of difference equations and recent developments have shown it to be related to various optimisation techniques e.g., linear programming. The first significant application of relaxation labelling to a vision problem was Waltz's filtering algorithm in the blocks world line labelling domain. Consider the problem of assigning labels to objects to satisfy certain consistency requirements. Unlike a tree representation where each context is explicitly a path, the space may be represented as a graph in which each node carries a set of possible labels. The task is to find a single labelling for each node that satisfies the set of constraints. In general, after an initialisation stage in which each node has been assigned a list of labels and their associated confidence measures, the labels and confidences of neighbouring nodes are compared and, guided by the requirement to minimise local inconsistency (often a smoothness constraint), labels are deleted or their confidences adjusted. This process of comparison and adjustment iterates until it converges to some criterion of global consistency. Because both the assignment and updating processes can be done independently at each node, the computation is inherently parallel. Apart from Waltz's classical application, relaxation labelling has been used in the computation of Optical Flow, the recovery of surface orientation from Shading Information, and the recovery of the orientation structure of images, Stereopsis and Structure from Motion. The convergence properties of some relaxation operators are not always transparent. The most successful and scientifically useful applications have been when the theoretical analysis of a vision problem reveals a mathematical structure that can be directly exploited in the design of the relaxation algorithm rather than when a `general operator' has been fitted in an ad hoc fashion to a vision labelling task. See also propagation in Cellular Arrays.

### References:

- Ballard, D.H. and Brown, C.M.,
*Computer Vision*, Prentice-Hall, Englewood Cliffs, N.J., 1982, pp.408--430.

### Comments:

No comments.