Probabilistic matching of planar shapes

Abstract

In this thesis we study a probabilistic approach for the shape matching problem. The studied approach is based on an intuitive definition of the shape matching task: Given two shapes A and B find that transformation within the class of allowable transformations which maps B to A in a best possible way. A mapping is considered to be good if large parts of the two shapes coincide within some tolerance distance delta. We assume that the shapes are modeled by finite sets of rectifiable curves in the plane. As possible classes of transformations we consider sub-classes of affine transformations: translations, rigid motions (translations and rotations), similarity maps (translation, rotation, and scaling), homotheties (translation and scaling), shear transformations, and affine maps. The major idea of the probabilistic algorithm is to take random samples of points from both shapes and give a "vote" for that transformation matching one sample with the other. If that experiment is repeated frequently, we obtain by the votes a certain probability distribution in the space of transformations. Maxima of this distribution indicate which transformations give the best match between the two figures. The matching step of the algorithm is, therefore, a voting scheme. In this thesis we analyze the similarity measure underlying the algorithm and give rigorous bounds on the runtime (number of experiments) necessary to obtain the optimal match within a certain approximation factor with a prespecified probability. We perform a generic analysis of the algorithm for arbitrary transformation classes, as well as an in-depth analysis for different sub-classes of affine transformations. It is also shown that the density function of the vote distribution is exactly the normalized generalized Radon transform in the cases of translations and rigid motions. We consider the theoretical analysis as the major contribution of this thesis, since it leads to a better understanding of this kind of heuristic techniques.

In dieser Arbeit wird ein probabilistischer Ansatz zum Vergleichen von Formen untersucht. Der Ansatz entspricht der intuitiven Vorstellung von "Formanpassung": zwei Formen werden als ähnlich empfunden wenn es eine Transformation aus der Menge der erlaubten Transformationen gibt, die die beiden Formen gut zur Deckung bringt. Dabei bedeutet "gute Deckung" dass große Teile einer Form sich in der räumlichen Nähe der anderen Form befinden. Die Formen, für die wir den Ansatz untersuchen, werden als endliche Mengen von Kurvensegmenten endlicher Länge dargestellt. Als Menge der erlaubten Transformationen betrachten wir Unterklassen der affinen Abbildungen: Translationen (Parallelverschiebungen), starre Bewegungen (Translationen und Drehungen), Ähnlichkeitsabbildungen (Translationen, Drehungen und Skalierungen), Homothetien (Translationen und Skalierungen), Scherungen und affine Abbildungen selbst. Die Grundidee des Algorithmus ist folgende: Nimm zufällige Punktproben aus jeder der Formen und zeichne eine "Stimme" für die Transformation auf, die die Probe der einen Form auf die Probe der anderen Form abbildet. Nach mehrfacher Wiederholung des Experiments zeichnet sich im Transformationsraum eine gewisse Verteilung der Stimmen aus. Die Maxima dieser Verteilung deuten "gute" Transformationen an, wobei eine gute Transformation eine ist, die große Teile der Formen zur Deckung bringt. In dieser Arbeit untersuchen wir das dem Algorithmus zu Grunde liegende Ähnlichkeitsmaß und bestimmen die notwendige Anzahl an Experimenten um eine gute Anpassung von Formen innerhalb einer vorgegebenen Approximationsschranke mit vorgegebener Erfolgswahrscheinlichkeit zu bestimmen. Der durchgeführte Analyse ist generisch und gilt für beliebige Transformationsklassen. Zusätzlich führen wir eine ausführliche Analyse für die oben genannten Transformationsklassen durch. Weiterhin zeigen wir, dass die vom Experiment induzierte Wahrscheinlichkeitsdichtefunktion im Transformationsraum genau der verallgemeinerten Radon-Transformation für Translationen und starre Bewegungen entspricht. Die theoretische Analyse betrachten wir als den Hauptbeitrag dieser Arbeit, denn sie führt zum besseren Verständnis einer Klasse von Heuristiken die unter dem Sammelnamen "Abstimmungsmethoden" bekannt ist.