Page 294 -

282 6 Structural Pattern Recognition

Relaxation techniques are quite attractive for assessing tree or graph
dissimilarity, since they can be executed quickly and easily incorporate any
constraints, namely those derived from the attributes. In some situations of tree or
graph matching it is sufficient to perform discrete relaxation, much in the same
way as we did in the previous sections. Consider for instance the scene situations
shown in Figure 6.27. These can be represented by the trees of Figure 6.28, where
a descendent node means "above". We can now perform discrete relaxation using
the compatibilities of the neighbour nodes also shown in Figure 6.28. The
probability matrix of the assignments evolves as shown in Table 6.7. A
homomorphism of scene (a) relative to scene (b) is detected.

Figure 6.28. Trees describing the scene situations of Figure 6.27, with the
compatibility table.

Table 6.7. Probability matrix of the tree matching problem shown in Figure 6.28.
po p(1) p(2)

The Hopfield network approach can also be used for determining the graph
homomorphisms, in the same way as explained in the previous section (see
Exercise 6.24).
For attributed relational graphs such as those exemplified in Figure 6.4, one
would have to compute similarities for the node properties (v, h, u, d, c, b) and for
the relational properties (a, e, I, t). These would influence, through appropriate
weighting, the compatibilities among the graph nodes. Work along these lines for