Page 300 -

288 6 Structural Pattern Recognition

scheme that will be able to determine whether a cupboard includes a given assembly of
modules or not.

6.18 Consider the tree description of cupboards as in the previous Exercise.
a) Show that the cupboards can also be described by a string grammar using the
symbols of the primitives, plus:
Symbol operators: t (left of) ; 1' (top of)
Parentheses indicating the precedence order of the operations: ( )
b) Interpret: (sl'd) t (19); ((sl's) t e) 1' ((dd) t (ll'r)).
c) The string grammar description of cupboards can discard the parentheses by using a
reverse Polish notation, where the string is scanned from right to left, and whenever
an operator is encountered, the corresponding operation is performed upon the
previous operands. An example of this notation is t l' s d T' I I for the first string of
b). Using this notation, what string corresponds to the second string of b)?
d)Perform string matching experiments using strings in reverse Polish notation to
describe cupboards.

6.19 Develop a probabilistic relaxation scheme for the classification of profile silhouettes of
tanks, using the line segment description presented in section 6.4.1 and available in the
Tanb dataset.
6.20 A common operation performed on ECG signals consists of temporal alignment of the
respective QRS wave sequences (see description in A.4) in order to obtain averaged
waves. Consider the string descriptions of QRS wave sequences, using h, u, d, U and
D primitives, obtained by the SigParse program for the ECGs of the ECG Signals
dataset. Perform temporal alignment experiments of QRS waves using:
a) String matching.
b) Probabilistic relaxation.

6.21 Recompute the probability matrix P of Table 6.4, assuming that the distance between
the centroids of A,, A? (Figure 6.21) is 2.2.

6.22 Consider the aerial images of tanks, included in the Tanks dataset, with two prototype
images TU4 and TU5.