Page 293 -

6.4 Structural Matching 281

Once the match graph is built, as shown in Figure 6.26 for the two graphs of
Figure 6.25, one proceeds to determine its cliques. A clique is a totally connected
sub-graph between any two different nodes, where totally connected means that
there is a path linking any given pair of nodes. In our case, we are interested in
maximal cliques involving different nodes of the source graphs. These are shown
with solid line in Figure 6.26, representing the two known homomorphisms.
As seen in this example, finding isomorphisms or homomorphisms between
graphs or trees can be a hard task in non-trivial situations, since it demands
searching for compatible node adjacencies in the space of all possible node
correspondences. This usually amounts to a long time-consuming task, for
anything except a very small number of nodes. Existing algorithms that perform
this search require a time that is approximately factorial-bound with the maximum
number of nodes for the target correspondence. No polynomial-bound algorithms
are known. The situation worsens when one has to assess not only node adjacency,
but also attribute compatibility. For instance, if instead of the digraphs of Figure
6.25 we consider the digraphs of Figure 6.4, no homomorphism exists. However,
an evident homomorphism exists between the digraphs of "F" and "EM.
Practical applications of pattern recognition, with patterns described by trees or
graphs, resort to faster methods of assessing the structural dissimilarity, namely to
the idea of edit cost as explained in section 6.4.1 or to discrete relaxation as
explained in section 6.4.3.
Tree matching based on edit operations is conceptually similar to the string
matching method described in section 6.4.1. The following five edit operations are
used:

1. Insertion of a node
2. Deletion of a node
3. Substitution of a node label
4. Splitting a node
5. Merging two nodes

Algorithms that assess tree dissimilarity using these edit operations are
described in Sanfeliu (1990). These algorithms have a time complexity of the order
of nm2, where n and m are the number of nodes of the trees to be matched.

Figure 6.27. Two scene situations in a "block world", with primitives small block,
b, and large block, B.