Mosig, Axel: Efficient Algorithms for Shape and Pattern Matching. - Bonn, 2004. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc:
author = {{Axel Mosig}},
title = {Efficient Algorithms for Shape and Pattern Matching},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2004,
note = {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:
How can we model objects?
  • What is a suitable class of admissible transformations?
  • How can we define similarity between objects?
Finding answers to these questions usually depends on the application scenario as well as the availability of appropriate algorithms.
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.},

url = {}

The following license files are associated with this item: