Page 256 -

244 6 Structural Pattern Recognition

where an appropriate norm, usually the Chebychev norm or the Euclidian norm, is
used to evaluate the deviations of s(xj) from h,(x,).
A piecewise linear approximation of this kind is implemented in the SigParse
program using the following simple algorithm:

1. Specify a maximum error, Em,,, for every line segment.
2. Start the approximation search with the first signal sample xl, which initiates the
first line segment, i=l.
3. Set the number of signal samples to regress, k=l.
4. Generate a line regressing k signal samples, from xi to x~+~.I.
5. Evaluate E for the regressing line. If E is smaller than Em,,, increase k and go to
4, otherwise start a new line segment, increase i, and go to 3.

Figure 6.1 shows a piecewise linear approximation obtained with SigParse for
an electrocardiographic (ECG) signal. The original signal has 702 samples. The
approximation using the Chebychev norm with Em,, =17 pV (in a 682 pV pp.
ECG) has only 21 segments.

Figure 6.1. Piecewise linear approximation (black) of an ECG signal (grey). The
line segments are labelled according to specified slope thresholds.

Sometimes it may be desirable to minimize the number of line segments by a
careful adjustment of the segment ends, guaranteeing that an error norm is not
exceeded, as described in Pavlidis (1973). In this case, the whole signal must be