Page 260 -

248 6 Structural Pattern Recognition

Strings are useful for representing concatenated structures, for instance, segment
joining in signal descriptions. Even in some apparently complex relations of
primitives, describing 2D and 3D structures, it is still possible to use strings, as we
will see in section 6.3.4.
Sometimes the ordered sequence of primitives expressed by a string does not
contain enough information to achieve pattern discrimination. For instance, when
analysing signals, such as electrocardiograms or heart rate tracings, not all peaks
described by strings such as x = ud or x = du are relevant, i-e., meet the
requirements necessary for attributing them to a certain class of waves. Extra
conditions often have to be imposed on the duration and amplitude of the peaks.
We deal with this requirement through the formalism of attributed strings, i.e.,
strings that have an associated attribute vector:

For waveforms described by line segments the attribute vector usually has two
elements, namely duration and height of each segment. In some cases there are
categorical attributes (eg, colour), and the attribute vector will contain labels (e.g.,
red). In the case of strings with single labels, we will refer to them as labelled
strings.

6.2.2 Graphs

A graph G is an ordered pair:

where N, the node set, is a set of nodes, and R, the edge set, is a set of binary
relations defined in NxN.
The elements of R represent arcs (or edges) connecting nodes of N. An arc of G
is denoted (a, b) with a, b E N
A directed graph, or digraph, is a graph where each arc has a direction,
emanating from a node and incident onto either another node or the same node. An
arc from a digraph, represented by the pair (a, b), means that a is the emanating
node and b is the incident node. Generally, in a digraph, (a, b) will mean a different
relation than (b, a).
The number of nodes b, such that (a, b) E G, i.e., the number of emanating arcs
from a, is the out-degree of node a. The number of nodes a, such that (a, b) E G,
i.e., the number of arcs incident in b, is the in-degree of node b.
Graphs are a very flexible way of expressing relations among primitives. As
there are attributed and labelled strings, we can similarly have attributed or labelled
graphs. Figure 6.4 illustrates the use of digraphs in character recognition. At the
left side of the figure, primitives and relations describing capital letters are
indicated. At the right side of the figure, two examples are shown of digraphs using
these primitives and relations, for the letters "R" and "EM.