Page 284 -

272 6 Structural Pattern Recognition

The quantities qy are in [-I, 11 and can be used to update the Py, satisfying the
constraints that they are nonnegative and add up to one for each object, in the
following way:

The most important decisions one must make when applying probabilistic
relaxation relate to the choice of compatibility measures and the estimation of the
$').
Let us consider the so-called image registration problem. This is a pattern
recognition problem, where we want to establish a correspondence between two
different patterns (images) A and B using two sets of points, called control points.
The control points correspond to n points of A and m points of B, respectively,
which share k common points, with k unknown. They are chosen so that they
reflect clearly identifiable segments of the images. In an application to satellite
images registration (Ton and Jain, 1989), the control points are centroids of clearly
identifiable regions and have attributes that are the type and the size of the
respective region. A matrix of nxm probabilities PY can then be established to
represent the probability of matching each pair of points. The initial estimates are:

,
(0, btherwise.

The compatibility factors use both the probability estimates and the relative
distances among the points:

From these compatibility factors, one can compute the support that the other
points lend to the assignment (Ai, Bj), at iteration r, as: