The problem of shape and pattern matching is a problem that raises
naturally in many applications: suppose we have a reference pattern
P and a query pattern Q, can we transform Q so
that the transformed version of Q is similar to P? This
general problem usually entails further questions:
In this thesis, a general approach to a certain class of such pattern
matching tasks is proposed. The focus is set on geometric
patterns, i.e., the patterns are objects contained in a Euclidean
vector space. In our setting, objects are modeled as sets or sequences
of points. Typical classes of transformations are identified as
groups, while object similarity is measured by the means of certain
distance functions.
The concept of G-inverted lists introduced as a generalization
of techniques known from full text retrieval is used as a starting
point for developing a generic approach to geometric pattern
matching. To this end, relations between G-inverted lists and
pattern matching with respect to the directed Hausdorff distance are
studied. The notion of transporter sets that occurs in this
context is a major foundation for the results and matching algorithms
developed throughout this thesis.
After studying intersections of such transporter sets from an
algebraic and algebraic geometry point of view, relations between
transporter sets and matching point sets with respect to certain
distance measures are described. This motivates the introduction of
relational distance measures, examples of which are the Hausdorff- and
the bottleneck distance. As the major result, generic matching
algorithms are developed that work for matching with respect to
arbitrary relational distance measures under an arbitrary linear
algebraic group. As it turns out, the class of linear algebraic groups
- i.e., groups that are also affine varieties - contains
transformations such as rigid motions, similarity motions or affine
motions that are relevant in typical applications.
Furthermore, we discuss certain properties of relational distance
measures that allow us to state faster matching algorithms, sometimes
at the cost of obtaining only an approximate solution of the problem.
These improved algorithms generalize a number of ideas that were used
to speed up matching algorithms for special distance measures and
special transformation groups. Furthermore, we provide an algorithm
for matching with respect to the root-mean-square Haudorff
distance (which does not belong to the class of relational distance
measures) under arbitrary linear algebraic groups. These results
generalize to a whole class of non-relational distance measures that
evolve from relational distance measures by exchanging a certain norm
that is part of many relational distance measures.
The practical value of the algorithms based on transporter sets is
limited for large transformation groups of high dimension by the fact
that it relies on techniques from real algebraic geometry. These are
generally hard to implement for polynomials invloving more than one
variable. For the group of rigid motions in three dimensions, however,
one can apply ideas known for matching with respect to the directed
Hausdorff distance and generalize these for matching with respect to
arbitrary relational distance measures. Again, one can make use of
certain properties of relational distance measures for speeding up the
matching algorithms.
As another relational distance measure, a discrete version of the
Frechet distance is introduced. After providing some combinatorial
structures underlying this distance measure, we show that the discrete
Frechet distance is a pseudo-metric. In addition, it is shown that
this discrete version is upper bounded and lower bounded by the
continuous version of the Frechet distance arbitrarily tight by
considering oversampled versions of polygonal curves. Due to these
bounds, any algorithm for matching with respect to the discrete
Frechet distance yields an approximation algorithm for matching with
respect to the continuous Frechet distance. Since the discrete Frechet
distance is a relational distance measure, matching algorithms result
from the generic approaches described above. Furthermore, we show that
the discrete Frechet distance is related to the Dynamic Time Warping
Distance (studied in the context of speech processing, computer vision
and handwriting recognition) in the same way as the root-mean-square
Hausdorff distance is related to the Hausdorff distance. Hence, we can
use the ideas for matching w.r.t. the root-mean-square Hausdorff
distance in order to design algorithms for matching with respect to
the Dynamic Time Warping distance. This problem has been addressed
before only under the group of translations, and the (rather
theoretically relevant) results obtained in this thesis are the first
ones for matching with repsect to larger groups than pure translations
or rigid motions in the plane.
Many of the algorithms described here can be implemented and have been
tested in practice. A description of these implementations as well as
some of the running times obtained in practice are presented in the
final part of this thesis.