Page 290 -

278 6 Structural Pattern Recognition

(6-31a) and (6-31b), it is convenient to set some tolerance for all components of
t(xi, ~k).

a 2 b 5
Figure 6.23. Line drawings for illustration of discrete matching with a Hopfield
network: (a) prototype; (b) "unknown" drawing.

The compatibility matrix corresponding to the Hopfield net weights is a sparse
matrix, since it is filled with -1 (incompatible assignment) for all elements Wpk
such that h=i or kj (shaded cells in Table 6.6). Also, since it is a symmetric
matrix, one only has to fill in half of the matrix values. Table 6.6 shows part of the
compatibility matrix using the binary set {I, 0). The Hopfield weight matrix will
be filled with -1 instead of 0, and nxm =18 instead of 1. For instance, since (x2, x3)
is compatible with (y4, y6), the weight W2436 will be filled in with 18.

Table 6.6. Compatibility matrix for the example of Figure 6.23. Parts of the matrix
not shown are filled in with zeros.

With the Hopfield network inputs set initially with ones, the net will iterate to
the outputs shown in Figure 6.24a. which give a picture of all feasible assignments.
We now solve the linear assignment problem (6-34), also using the Hopfield net.
Since x3 + y6 is the only feasible assignment for x3, we investigate other
assignments satisfying (6-33b). One such assignment is shown in Figure 6.23b and