Page 286 -

274 6 Structural Pattern Recognition

In this case, the updating of the probabilities is quite easily done by hand. For
instance, the first updating of PI, depends only on the compatibilities of (A2, Bz)
and of (A2, B4), with:

The maximum value of these compatibilities for A2, updates PI, = 0.8 to
PI I= 0.8x0.5788 = 0.463.
This basic probabilistic relaxation scheme can also be applied to other pattern
recognition tasks, including object classification, as exemplified in Exercise 6.22.

6.4.3 Discrete Relaxation Matching
In some situations it is not adequate to assign probabilities to the object labelling,
since the only decision is whether the label is possible or not, i.e., PV is either 1 or
0. Usually, in these situations the compatibilities are also qualitative in nature: the
Ai + Ej assignment is either compatible (c=l) or not (c=O). An example of such a
situation is in graph matching, where correspondence between nodes is either
possible or impossible.
There is a variant of the basic relaxation algorithm, called discrete relaxation,
appropriate for these kinds of situations. In discrete relaxation, for every Ah
relevant to Ai, there must be at least one label k, such that c(i2; h:k)=l with Phk =l;
otherwise the assignment Ai + Ej is impossible. Initially, the F', (0)
are all set to one.
At subsequent iterations, Pv remains 1 if for every relevant Ah there is an
assignment such that c(iy; h:k)Ph~l; otherwise Pij becomes 0. This is equivalent to
the following formula:

Figure 6.22. Discrete relaxation applied to two simples examples of compatible (a)
and incompatible (b) shapes.