Page 288 -

276 6 Structural Pattern Recognition

For this purpose, we start by defining a function t(xi, xh) that reflects the
transformation that must be applied to xi in order to obtain xh. For some
applications, function t(x, xh) just computes a matching score resembling the
transforming function used in (6-22c).
Next, we compute the compatibility coefficients for the assignments xi -+ yj and
xh -+ yk as follows:

Therefore, full compatibility only exists if the matching between candidate
segments in the prototype drawing is the same as between candidate segments in
the unknown drawing.
Let us use a Boolean matrix M with n lines and m columns for the
representation of the possible assignments of line segments of X to line segments
of Y. Possible assignments are represented by mv=l, impossible assignments by
my*. A matching of X with a subset of Y corresponds to a nxm matrix X,
generated from M, such that:

since in any matching, a segment of X can only be assigned to one segment of Y.
The optimal assignment corresponds to:

This is a quadratic assignment problem that can be solved using a probabilistic
relaxation method (see Kuner and Ueberreiter, 1988). Initially, a probability mamx
is initialised with a constant value, e.g. lln. Next, the basic relaxation algorithm
expressed by formulas (6-24) and (6-25) is applied until there is no significant
difference between the probability matrices P in successive iterations. Matrix P
represents then the probabilities of the assignments, with the higher values Pij
representing the best assignments xi + 3. One then proceeds to solve the much
simpler linear assignment problem:

rm 1
max F'yxii with the constraints (6-33b).
i=l j=1