Continuous Relaxation and Local Maxima Selection: Conditions for Equivalence

1. MOTIVATION

The study of speech and image understanding systems has largely been empirical. Represen­ tations have often been designed for task domains, while algorithms were designed to make use of these representations, as well as heur­ istic considerations about how the algorithm should behave. Thus it has been very difficult to compare different algorithms except for the results of a few examples, to state equivalences between algorithms in anything like certain terms, or to determine the theoretical requir­ ~mcnts for solving a particular problem.

A number of common problems facing the desig­ ners of such systems have begun to emerge, however, which suggests that it may be possible to study the power of algorithms in terms of their ability to solve these problems. One such problem is the reduction of local ambigu­ ities, and relaxation labeling processes are a class of algorithms that have been proposed for dealing with it [1). While many recent applic­ ations offer some insight into the relaxation computation (for a review, see (2]) a formal analysis aimed at specifying this computation more precisely is required. It is impossible, for example, to know whether two different algorithms are really equivalent (in the sense that they are implementing the same abstract computation) simply by comparing their results on a small number of experiments. Rather, the relationships between them must be expressed in an analytical fashion so that they will hold for all experiments. This paper is the begin­ ning of such an analysis for continuous relax­ ation processes. It specifies the relaxation computation in terms of another, much more widely used algorithm - local maxima selection­ together with a set of conditions that are sufficient for guaranteeing convergence and

CONTINUOUS RELAXATION AND LOCAL MAXIMA SELECTION Conditions for Equivalence*+

Steven w. Zucker, Yvan G. Leclerc, John L. Mohammed Computer Vision and Graphics Laboratory Department of Electrical Engineering McGill University Montreal, Quebec, Canada

It is also a good rule not to put overmuch confidence in the observational results that are put forward until they are confirmed by theory.

Sir Arthur Eddington, 1934

equivalence between the two.

The specific reasons for studying the relation­ ships between relaxation and local maxima selec­ tion are manifold. From the relaxation point of view, maxima selection provides a model for the decision process, or part of the decision process, that relaxation is implementing. In other words, if we consider the dynamics of a relaxation process as being composed of two stages, one in which a proper ordering of the labels is obtained given the compatibility relations and the initial state, and the other in which certain of these labels are selected, then maxima selection provides a non-iterative model for the second stage. From a practical point of view, when conditions sufficient for equivalence between the two algorithms are met, they can serve as stopping criteria for the relaxation process. More generally, however, these results show that when circumstances are structured well enough, the cooperative relax­ ation algorithm acts the same as if it were decomposed into a purely local maxima selection process. This is exactly the kind of r elation­ ship that is desirable between two algorithms: when the stronger one is necessary, it is func­ tional; otherwise, it reduces to the weaker

one.

There is another, mo·re abstract application of the theory that we are beginning to develop here. It derives from the decomposition result just alluded to (which is stated more formally in Sec. 3), and pertains to inferences about how local or global a given algorithm must be. In particular, cooperation can be viewed as one way in which information can be propagated between the local parts of an algorithm, hense making it more global [3). One surprising interpretation of our result is that circum­ s tances exist in which this propagation is irr e l evant. In other words, although a (globally) cooperative mechanism has been used in designing an algorithm for a given problem, the inherent structural complexity of the problem (in that representation) is still only local. Conditions such as those stated in the Equivalence Theorem (Sec. 3) provide a first step toward dete rmining such requirements analy­ .tically. In turn, these computational requ­ irements may imply certain constraints on the parti cular mechanisms and machinery that actually perform such functions (4].

*This research was supported by NRC grant No. A4470.

+ For a much more extensive discussion for these ideas, together with references, see TR-78-lSF. Dept. of Elect. Eng., McGill University.

2. BACKGROUNQ.

The class of problems for which both relaxation and local maxima selection are applicable is one in which global labeling problems can be represented as networks of local ones. In other words, given a set of possible labels for each node in a ne twork, the problem is to select a single label (or a smaller set of labels) to attach to each node. These labels might indicate, e.g., asse rtions about the presence of oriented line segments in an image (5). The nodes in the network would then corr­ espond to the spatial positions to be labeled, while edges would indicate which nodes were spatial neighbours. Or, the labels might indic­ ate disparity values [6). We shall denote such labels by the variable A, and the full set of labels (at a node i) by. Ai.

For continuous relaxation processes, acertain­ ty measure is distributed ove r the labe l set at each node .· We shall denote the certainty with which label A i s associated with node i by pi (A). They satisfy L p(A)=l and Adl. .

l.

0 < p. (A) < l. In the line labeling example, - l. - s uch a measure may be obtained from scaled feature (i. e ., line) de tector responses . Note that ambiguity enters the problem because feature detectors do not r espond unique ly; i. e. , many labe ls appear to be possible when looking only at the individual detector r esponses.

Perhaps the most common algorithm for selecting a label from among this initially ambiguous se t is to perform local maxima selection (i.e., to pick the label with the maximal certainty at each node ). Such an algorithm would be appropriate for our line example, if we knew that the line detector always responded most s trongly at the correct orientation. Thi s is, of course, not the case for r eal images, in which many different noise sources can corrupt the detectors' r esponses. Thus more powerful techniques seem to be nece s sary in general. However, as we shall show, there arc ins tance s in which such weaker techniques are appropriate.

The strength behind r elaxation processes lies in their use of contextual information through­ out the ambiguity r eduction process. This context is based on an a priori notion of con­ sistency or compatibility between labe l s on neighboring nodes, so that now some degree of ~ooperation takes place be tween nodes during the label selection process. In the line l abe l­ ing example, label compatibility is an abstract way to introduce models for good continuation of orientation (i.e., orientation should vary smoothly along lines and curves) and of inten­ sity (i. e ., intensi ty values should vary smoth­ ly along the line and over the background) ; see [7). In this paper, howeve r, since we arc dis­ cussing the relaxation mechanism in the abstrac~ we shall only conside r compatibilities as func­ tions over n-tupl cs (usually pairs) of labe l s on neighboring nodes into [0.1). For example, r . . (A, A') indicates the compatibility between l~e l A on i and A' on its neighbor j, where 0 corresponds to perfect incompatibility and 1 to perfect compatibility.

Given an initial labeling p~(A ), A £ Ai' i £ I,

the relaxation process iteratively updates each label's certainty factor by an amount propor­ tional to an estimate of its consistency with the labeling over its neighborhood. If this neighbourhood consistency estimate indicates that a label is compatible with its neighbour­ hood labelings, then its consistency factor is increased; otherwise , it is decreased. Since many labelings may be partially consistent, the update is normalized with respect to the average neighbourhood consistency at each iter­ ation. Thus we have updating rules of the form:

k where Qi(A) is the current consistency estimate between labe l A on node i and the labe ling

over its neighbourhood.

The neighbourhood consistency is computed as a function of the current neighbourhood labeling and the compatibility func tions. For computational reasons, this estimate has been decom­ posed into two parts: one in which an operation is performed to determine the pair (or n~ary) label consistency estimates; and the other in which these partial estimates are combined into a single :neighbourhood estimate. The most widely used estimate is [1):

Mhere Ji is the set of nodes neighbouring i and the C .. terms weight the total interaction ~J between nodes i and j. The choice of arithmetic averages in (3), however, is only heuristic. The essential point is that the neighbourhood consistency estimate is a function of the labeling over the entire neighbourhood. To emphasize this generality, we shall rewrite (3) in a more general form, and prove all of our results using this form.

The general form that we shall consider , is:

where Mean is any standard mean (or averaging) operator; and Norm is an operator that computes the norm (or length) of a vector.

3 CONSISTENTLY ORDERED LABELINGS AND THE EQUIVALENCE THEOREM

The traditional way of viewing continuous relax­ ation is as numerical process for updating certainty measures. However, if we consider these certainty measures as defining a partial ordering over the labels at each node, then another way of viewing relaxation labeling is as a process that changes this partial ordering. This is the point of view that we shall adopt for the remainder of this paper, because it suggests a study of the iteration at which the partial ordering of the labels at each node becomes fixed for all further iterations. We shall say, at this iteration, that the system has become consistently ordered. Th~ particular partial ordering that we shall concentrate on is the one specifying the r e lationship hetween the maximal and all of the non-maximal labels at each node.

There are many possible dynamical situations that can give rise to consistently-ordered labelings. Perhaps the most common situation is for the maximal labels to mutually support one anothe r, thus driving the weaker labels to zero. It is this situation that we shall now attempt to characterize because, as we shall prove, it leads to a formal correspondence between relaxation and local maxima selection.

To define the above notions more exactly, i ·t i s necessary to introduce some notation: Let

• (i) II. be the full set of labels attached to ~ node i.
• (ii) M~ be the set of labels attached to node i ~ that have the greatest certainty at iter­ ation k;
• (iii) N~ be the set of labels attached to node i ~ with non-zero, non-maximal certainties at iteration k;
• (iv) z~ be the set of labels attached to node i ~ with zero certainty at ite ration k.

Equivalence Theorem

If, for a given relaxation process, the con­ ditions

hold for every nod~ i £ I, then

• (a) the labeling £ c in that process is con­ sistently ordered everywhere, and
• (b) the relaxation process will converge t o a final labeling with

otherwise

k k where #M. 0 denotes the number of labels in M. 0 · ~ ~ For the proof of this theorem, toge the r with applications and interpre tations, see the TR cited in the footnote on the title page.