Page 291 -

6.4 Structural Matching 279

has a final state shown in Figure 6.23~. with q=2, which corresponds to the partial
assignment {xg -+ y6, xz -+ y5). The maximum value of q=3 is only obtained with
the full compatible assignments {x3 -+ ys, x2 -+ y3. XI -+ y4) or {x3 -+ Y6, x2 -+ y4,

Figure 6.24. Hopfield net illustrating the probabilities associated with the
assignments corresponding to the example shown in Figure 6.23. (a) Feasible
assignments as solutions to the quadratic problem; (b) A candidate assignment; (c)
final assignment corresponding to the previous situation (q=2).

The basic ideas that have just been described, concerning the application of a
discrete Hopfield network for discrete relaxation matching, can be generalized for
more complex probabilistic relaxation tasks, using a modified version of the
continuous Hopfield network. In the work of Lin et al. (1991), the hierarchical
recognition of machine parts using such modified Hopfield networks is described.
The hierarchical process uses: at the first stage, a Hopfield network whose weights
correspond to surface matching scores, picking up possible candidates from a
database of machine parts; at the second stage, a Hopfield network performs vertex
matching in order to achieve a finer selection.

6.4.5 Graph and Tree Matching

Consider two graphs (or trees) GI=(NI, Rl) and G2=(N2, R2), describing the
structural relations of two patterns. A homomorphism from GI to G2 is any function
f establishing a correspondence between the nodes of N1 and the nodes of N2 such
that any pair of adjacent nodes in GI corresponds, throughf, to adjacent nodes in
N2. Let (a, b) represent two adjacent nodes of NI. Then a homomorphism f
satisfies:

(a, b) E RI * (Xa)f(b)) E R2. (6-37)

Consider the two digraphs represented in Figure 6.25. When assessing node
adjacency, we have to take into consideration the direction of the arc connecting
the nodes. There are two easily found homomorphisms between both digraphs.