Page 255 -

6 Structural Pattern Recognition

In the preceding chapters several methodologies of pattern classification and
regression were presented, all based on a numerical similarity measure. Structural
pattern recognition has a completely different approach, as briefly mentioned in
section 1.4. Its main concern is the structure of a pattern, i.e., how a pattern can be
described and interpreted as an organization of simple sub-patterns, usually
designated as pattern primitives.
Structural pattern recognition has two main classes of methods: syntactic
analysis and structural matching methods. Syntactic analysis methods are based on
the use of formal language theory. Structural matching methods use specific
techniques based on mathematical relations among the primitives.
Error bounds and generalization capability of structural recognition methods are
problem-dependent. The performance of a syntactic analyser or of a structural
matching method has to be assessed in a test set of patterns in the usual way.
Structural pattern recognition is often used in combination with statistical
classification andlor neural network methods in hybrid approaches in order to
achieve complex pattern recognition tasks, namely in applications of two-
dimensional and three-dimensional object recognition.

6.1 Pattern Primitives

As the 'first step to describing and analysing pattern structures, they are
decomposed into simple and well-defined elements, called primitives. The choice
of primitives depends on the application, and can be of varied nature (see the
bibliography section). In the following, we limit our discussion to methods of
primitive extraction that can be applied to a large class of situations and are,
therefore, quite popular.

6.1.1 Signal Primitives

Usually signals are decomposed into line segments or other simple curves. A
piecewise linear approximation of a signal is by far the most popular method of
signal decomposition. Suppose that we have a signal s(x) that we want to
approximate by a piecewise linear function h(x) with d segments hi. The
approximation error is: