Efficient Algorithms for Shape and Pattern Matching

Abstract

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: <br /> How can we model objects? <ul><li>What is a suitable class of admissible transformations? </li> <li>How can we define similarity between objects? </li> </ul> Finding answers to these questions usually depends on the application scenario as well as the availability of appropriate algorithms. <br /> 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. <br /> 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. <br /> 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. <br /> 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. <br /> 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.<br /> 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. <br /> 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.

<strong>Effiziente Algorithmen zur Erkennung von Muster und Formen </strong><br /> Probleme der Muster- und Formenerkennung treten natürlicherweise in zahlreichen Anwendungen auf: gegeben ein Referenzmuster P und ein Anfragemuster Q, können wir Q derart transformieren, dass die transformierte Version von Q dem Refernz-Muster P ähnlich ist? Dieses generelle Problem wirft weitere Fragen auf: <ul><li>Wie können wir Onjekte modellieren?</li> <li>Was ist eine passende Klasse von Transformationen?</li> <li>Wie können wir ähnlichkeit von Objekten definieren? </li> </ul> Die Beantwortung dieser Fragen hängt typischerweise von der Anwendung ab sowie von dem Vorhandensein entsprechender Algorithmen. <br /> In dieser Arbeit wird ein allgemeiner Ansatz für eine bestimmte Klasse derartiger Mustererkennungsprobleme vorgestellt. Dabei stehen geometrische Muster im Vordergrund, d.h., Objekte sind in einem Euklidischen Vektorraum enthalten. In unserem allgemeinen Szenario können Objekte als Mengen oder Folgen von Punkten aufgefasst werden. Typsiche Klassen von Transformationen identifizieren wir mit Gruppen, während wir die Ähnlichkeit von Objekten auf der Grundlage von gewissen Distanzfunktionen ermitteln. <br /> Das Konzept G-invertierter Listen - eine Verallgemeinerung invertierter Listen, die üblicherweise beim Volltext-Retrieval Anwendung finden - werden als Ausgangspunkt verwendet, um einen generischen Ansatz zur geometrischen Mustererkennung zu entwickeln. Dazu werden zunächst Beziehungen hergestellt zwischen G-invertierten Listen und Pattern Matching bezüglich der gerichteten Hausdorff-Distanz. Die im Rahmen dieser Beziehungen auftretenden Transporter-Mengen sind eine wichtige Grundlage für die im weiteren Verlauf der Arbeit entwickelten Matching-Algorithmen. <br /> Aufbauend auf dem Konzept der Transportermengen, wenden wir uns dem Problem zu, Aussagen über Durchschnitte von Transportermengen treffen zu können. Dabei spielen algebraische und algebraisch-geometrische Gesichtspunkte eine zentrale Rolle. Schliesslich erlauben uns die so gewonnenen Einsichten, Transportermengen in Beziehung zu setzen zu Pattern-Matching-Problemen, bei denen gewisse Distanzfunktionen zu berücksichtigen sind. Dies führt auf den Begriff relationaler Distanzmaße, zu denen Beispielsweise die Hausdorff- und die Bottleneck-Distanz zählen. Das Haputergebnis besteht nun in einem Algorithmus, welcher es erlaubt, geometrische Muster unter beliebigen linearen algebraischen Gruppen bezüglich eines beliebigen relationel Distanzmaßes zu erkennen. Wie sich herausstellt, umfasst die Klasse der linearen algebraischen Gruppen - d.h., Gruppen, die auch Varietäten sind - Transformationen wie starre Bewegungen, Ähnlichkeitstransformationen oder affin-lineare Transformationen, wie sie in üblichen Anwendungen auftreten. <br /> Des weiteren werden gewisse Eigenschaften relationaler Distanzmaße charakterisiert, die es erlauben, schneller Pattern-Matching-Algorithmen zu formulieren, wobei diese asymptotische Laufzeitverbesserungen zu approximativen Algorithmen führen. Diese verbesserten Algorithmen beruhen auf Verallgemeinerungen von bekannten Konzepten zur Laufzeitverbesserung von Pattern-Matching-Algorithmen. Weiter wird ein Algorithmus vorgestellt zum Matchen unter der root-mean-square Hausdorff-Distanz (die kein relationales Distanzmaß ist) unter beliebigen linearen algebraischen Gruppen. Diese Ergebnisse lassen sich verallgemeinern auf ein ganze Klasse von Distanzmaßen, die durch das Austauschen gewisser Normen, die bei vielen relationalen Distanzmaßen auftreten, entstehen. <br /> Der praktische Nutzen der Transportermengen-basierten Algorithmen ist beschränkt auf Transformationsgruppen, deren zugehörigen Varietäten eindimensional sind; für höherdimensionale Gruppen ist der prkatische Nutzen begrenzt, da Techniken aus der rellen algebraischen Geometrie verwendet werden, die in mehr als einer Variablen schwierig zu implementieren sind. Für die Gruppe starrer Bewegungen in drei dimensionen lassen sich jedoch bekannte Ansätze aus der geometrischen Mustererkennung verallgemeinern, so dass auch diese Pattern-Matching unter beliebigen relationalen Distanzmaßen erlauben. Auch bei diesen Algorithmen lassen sich dieselben Eigenschaften relationaler Distanzmaße verwenden, um schnellere Matching-Algorithmen zu entwickeln. <br /> Als weiteres relationales Distanzmaß führen wir die eine diskrete Version der Fréchet-Distanz als Distanzmaß zwischen Polygonkurven ein. Nachdem einige kombinatorische Strukturen eingeführt werden, die diesem Distanzmaß zugrundeliegen, zeigen wir, dass die diskrete Fréchet-Distanz eine Pseudo-Metrik ist. Darüber hinaus wird gezeigt, dass die diskrete Version der Fréchet-Distanz nach oben und unten beliebig dicht beschränkt ist durch die kontinuierliche Version, indem wir gewisse überabgetastete Polygonkurven betrachten. Aufgrund dieser Schranken liefert jeder Algorithmus zum Matchen unter der diskreten Fréchet-Distanz einen approximativen Algorithmus zum Matchen unter der kontinuiertlichen Fréchet-Distanz. Da die diskrete Fréchet-Distanz ein relationales Distanzmaß ist, ergeben sich Matching-Algorithmen unmittelbar aus den obigen Ergebnissen dieser Arbeit. Des weiteren zeigen wir, dass die diskrete Fréchet-Distanz eng verwandt ist mit der Dynamic-Time-Warping-Distanz, die aus dem Kontext von Sprachsignalverarbeitung sowie vom Computersehen und der Handschriftenerkennung her bekannt ist. Diese Beziehungen sind dieselben wie zwischen der Hausdorff-Distanz und der root-mean-square-Hausdorff-Distanz. Daher lassen sich die Ideen zum Matchen bezüglich der root-mean-square-Hausdorff-Distanz übertragen auf das Matchen unter der Dynamic-Time-Warping-Distanz. Für dieses Problem waren bisher nur Algorithmen unter der Gruppe der Translationen bekannt, während die hier erzielten Ergebnisse (die eher theoretischer Natur sind) die ersten Ergebnisse unter größeren Gruppen - nämlich unter beliebigen linearen algebraischen Gruppen - darstellen. <br /> Viele der hier beschriebenen Algorithmen lassen sich implementieren und wurden in der Praxis getestet. Eine Beschreibung dieser Implementierungen sowie die resultierenden Laufzeiten werden im letzten Teil der Arbeit diskutiert.