Page 281 -

6.4 Structural Matching 269

instance, the dissimilarity between the prototype and shape (b) is only smaller than
the dissimilarity corresponding to shapes (c) or (d) when the substitution cost is
sufficiently high compared with the insertion cost. In practical applications, some
tuning of elementary costs may therefore be necessary in order to obtain the best
results.

h
ci = 1 ci = 1/2
prototype u fl d c', = 1 c', = 1
c, = 2 c, = 3

0 0

1.3 1.3

4 3.3

2 2.2

Figure 6.18. Levenshtein distance between a prototype pattern and each of four
patterns, (a) to (d). Edit costs are shown at the top.

Despite the difficulties of string matching, this technique can often achieve
surprisingly good results in pattern recognition applications. The basic idea
consists of obtaining the matching score of an unknown pattern relative to the
prototypes, choosing the classification corresponding to the closest prototype. Of
course, a generalization of this principle using k-nearest neighbour classification is
also possible.
We now illustrate the application of string matching with the recognition of toy
models of tanks (Tanks dataset). Figure 6.19 shows profile views of three tank
prototypes. Figure 6.20 shows one of the prototypes seen at variable distance and
orientation, corresponding to the unknown pattern we wish to classify.
String matching is performed using the Levenshtein distance algorithm (String
Match.xls) with the following modifications: first, because all primitives are
attributed line segments, we do not have in this case different string symbols, and a
substitution cost is always computed according to (6-21c); second, we now have to
deal with an angular attribute measured in [- 180", 180°]. We choose a dissimilarity
function fluo, ab), which yields a zero cost for angular differences of 0" or 360"
and positive increasing cost for other angular differences, up to a maximum of one