Shape Matching With Reference Points

Abstract

Shape matching is an important topic in computational geometry, computer vision, image retrieval, object recognition and robotics. For a fixed distance measure D and a class of transformations T we can describe the problem as follows: Given two shapes A and B in R^d, find a transformation T^* in T, such that the distance between A and T^*(B) is minimal among all transformations in T. Usually finding such a transformation is computationally expensive, if at all possible. Thus we concentrate on approximation algorithms. We follow an approach by Alt, Behrends and Blömer, and Alt, Aichholzer and Rote. They use mappings called reference points to fix the relative position between the two sets. A reference point is a Lipschitz continuous mapping from the set of shapes into R^d which is equivariant under the considered class of transformations. This approach reduces the degrees of freedom of the underlying problem by the dimension d. In this thesis we study approximation algorithms for shape matching with respect to various metrics, e.g., the Hausdorff distance, the Earth Mover's Distance, the Monge-Kantorovich Distance and the bottleneck distance. We investigate translations, rigid motions, i.e., combinations of translations and rotations, and similarities, i.e., combinations of rigid motions and scalings. The basic structure of the approximation algorithms is the same for all metrics and we describe our approach in an abstract reference point framework. We first determine the relative position of the two shapes to each other by computing their reference points. We then translate the shapes such that the reference points coincide. Next we determine a rotation for one of the shapes such that the distance of the two shapes is at most a constant times their optimal distance. Similarities can always be dealt with by finding an approximate scaling before finding the rotation.

Die geometrische Mustererkennung ist ein wichtiges Thema unter anderem in der algorithmischen Geometrie, beim computerunterstützten Sehen und in der Robotik, um nur einige Anwendungsgebiete zu nennen. Für eine feste Abstandsfunktion und eine feste Klasse von Transformationen T kann das Problem wie folgt beschrieben werden: Gegeben seien zwei Muster A und B, finde eine Transformation T^* in T, so dass der Abstand zischen A und T^*(B) minimal ist unter allen Transformationen T in T. Die betrachteten Muster in dieser Arbeit sind im Wesentlichen kompakte Teilmengen, gewichtete Punktmengen, Punktmengen mit einer festen Anzahl von Punkten und Wahrscheinlichkeitsmaße. Unabhängig von der Wahl einer dieser speziellen Muster ist das Finden einer optimalen Transformation aufwendig, falls überhaupt möglich. Daher konzentrieren wir uns auf Näherungsalgorithmen. Der Ansatz dieser Arbeit basiert auf Referenzpunkten. Dieser Ansatz wurde unter anderem von Alt, Behrends und Blömer und Alt, Aichholzer und Rote gewählt. Die Autoren dieser beiden Arbeiten benutzen spezielle Abbildungen, sogenannte Referenzpunkte, um eine relative Position der beiden Muster zueinander zu bestimmen. Dieses reduziert die Freiheitsgrade des zugrundeliegenden Problems um die Dimension des Raumes. Ein Referenzpunkt ist eine Lipschitz-stetige Funktion definiert auf der Menge der Muster, die in den R^d abbildet. Zusätzlich bleibt die relative Position des Referenzpunktes bei Anwendung einer Transformation erhalten. In dieser Dissertation beschäftigen wir uns mit Näherungsalgorithmen für die Mustererkennung bezüglich verschiedener Abstandsmaße. Im Wesentlichen sind dies der Hausdorff-Abstand, der diskrete und kontinuierliche Transportabstand und der Engpass-Abstand. Dabei werden Näherungsalgorithmen für die verschiedenen Maße bezüglich Verschiebungen, starren Bewegungen, d.h. Verschiebungen und Drehungen, und positiven Ähnlichkeitsabbildungen, d.h. starren Bewegungen in Verbindung mit positiven Streckungen, betrachtet. Die Grundstruktur der Näherungsalgorithmen für die verschiedenen Abstandsmaße und unterschiedlichen Transformationen ist jeweils ähnlich und wird in einem allgemeinen Rahmen beschrieben. Zuerst wird die relative Position der beiden Muster zueinander durch Berechnung der Referenzpunkte der beiden Mengen bestimmt. Anschließend werden die Muster so verschoben, dass die beiden Referenzpunkte übereinstimmen. Im Anschluss bestimmen wir eine Drehung für eine der beiden Mengen, sodass der Abstand der beiden Mengen, den Wert einer optimalen Lösung höchstens um einen konstanten Faktor übersteigt. Streckungen werden betrachtet, indem vor dem Finden einer Drehung eine Streckung bestimmt wird, die einer optimalen Streckung sehr nahe kommt.