Page 287 -

6.4 Structural Matching 275

Formula (6-30) estimates possible assignments for Ai by checking that each
assignment is compatible with the surviving assignments of Ai's neighbours.
Let us apply discrete relaxation to the matching of the prototype shape of Figure
6.18 with shapes (b) and (d).
In this example we only distinguish whether the lines are horizontal or vertical,
and consider that an assignment i:j is compatible if they are of the same type.
Further, ig is compatible with h:k if h is an immediate neighbour of i, such that it is
possible to find a translation i:j that superimposes h over k. With these
compatibility rules, we can list the compatible assignments as shown in Figure 6.22
for each pair i2. For instance, for the matching (a), the assignment 1:1 is
compatible with 2:2; for the assignment 1:3, one does not find any compatible
primitives, since the neighbour segment 2 of the first shape is not compatible with
the neighbour segment 4 of the second shape.
Starting with a matrix [Pi,] filled in with ones, we can now apply the
compatibility rules to arrive at the final matrix shown in Table 6.5 for the matching
situation of Figure 6.22a. It is clear that a total match is reached (1:1, 2:2, 3:3) . For
the shape matching situation of Figure 6.22b, only the partial match (1:1, 2:2) is
obtained.
Notice that for complex shapes, the computation of the compatibilities can be
cumbersome. We will see in the next section a method to expedite their
computation.

Table 6.5. Probability matrix for the matching situation of Figure 6.22a.

6.4.4 Relaxation Using Hopfield Networks

Relaxation methods can be implemented using neural networks. In particular, a
modified version of the Hopfield network has been found useful in several
applications of relaxation methods, namely in line drawing matching (Kuner and
Ueberreiter, 1988) and in hierarchical recognition of three-dimensional objects
such as machine parts (Lin et al., 199 1).
We will now describe how this approach is applied using the line drawings
example. Imagine that we have two line drawings X and Y, constituted by line
segments xi (i = 1,. . ., n) and yj (j = 1 ,..., m). The line drawing X is considered the
prototype drawing that we want to match with a subset of the line drawing of Y.