Page 289 -

6.4 Structural Matching 277

This relaxation assignment can be solved with a modified Hopfield net in the
following way:

1. Set a two-dimensional Hopfield network with the rows representing the
segments (objects) of X and the columns the segments (objects) of Y. Each node
of the net, now denoted xii, represents an assignment xi -+ 4;
2. Compute the connection weights of the net as wvhk = ~(kj, h:k), which
correspond to the weight that links neuron xu with xhk;
3. Initialise the inputs with a matrix M of possible assignments, my = lln, and set a
total compatibility factor q=O;
4. Perform the output updating of the network in a full parallel way:

5. With the probability matrix obtained, solve the linear assignment problem
(6-34) and evaluate the new value of q, q', using the objective function of
(6-33a).
6. If q'c q set P = M and stop, otherwise set M = P, q = q' and go to step 4.

The Hopfield program (Appendix B) allows one to perform experiments of a
Hopfield net in the particular case of discrete relaxation. Let us consider the simple
example shown in Figure 6.22a. In order to derive the optimal assignment, we start
by setting a network of 3x4 neurons. Next, since we are using the values ( 1, -1 ),
instead of (1, 0) for the discrete Hopfield net, we set all the weights to -1
(corresponding to incompatibility) except for the compatible assignments, where
we set the corresponding weight to the value nxm =12, therefore insuring a positive
result if at least one of the products c(i:j, h:k)mhk is positive. We initialise the net
with a grid filled in with ones and get the final solution shown in Table 6.5, where
the final assignment is easily derived.
Let us now consider a less trivial example of having to find the compatible
assignment between the line drawings shown in Figure 6.23. We start by defining
the function that reflects the transformation that must be applied to segment xi in
order to obtain segment xh. For this purpose, we may choose the following
vectorial function:

t(x,,xk)=b,i, q a]', with (6-36)

dmi, : minimum distance between segments;
r : ratio of the segments lengths;
a : angle between segments, in 10, 180°].

With this function it is easy to see, for instance, that the pair (x2, x3) is
compatible with (y4, y6) but not with (ys, y6). When applying the comparisons