Page 261 -

6.2 Structural Representations 249

Primitives

v h u d c b I
e l (bending) 1
Relations

I a 1 (above' a
1 I I (left of) t (branching) e
h
a b
Figure 6.4. Primitives and relations used to describe capital letters (a) and labelled
digraphs for the letters R and E (b).

6.2.3 Trees
A tree is an undirected graph with no closed loops (acyclic graph) and with a
special node, the root node, with in-degree of zero and every other node with out-
degree 2 1, except the terminal or leaf nodes, which have out-degree zero.
Trees provide a useful representation of hierarchical structures, namely when
such structures have a recursive nature. Notice that we have already used trees for
hierarchical classifiers in previous chapters.

IR
d (drawer)

b (body) b (bottom)

0 (border) Jm
a (left door) (right door) e (empty) b i (inside) (left) (right)

Figure 6.5. Primitives (a) and relations (b) used to describe furniture, as in Figure
6.6.

As an illustration of trees used for the description of hierarchical structures, we
consider the task of recognizing pieces of furniture, based on the set of primitives
and the set of relations shown in Figure 6.5. Each relation is applied hierarchically.
For instance, we can apply the relations "leftw-"right" to any sub-pattern previously
labelled as "bottom". Figure 6.6 shows how a tree using these primitives and