Probabilistic matching of solid shapes in arbitrary dimension

Abstract

Determining the similarity between objects is a fundamental problem in computer vision and pattern recognition, but also in other fields of computer science. This thesis concentrates on the matching problem, which has received a lot of attention in Computational Geometry. Given a class of shapes S, a set of transformations T, mapping shapes onto shapes, and a distance measure d on S, the matching problem with respect to S, T, and d is defined as follows: Given two shapes A, B in S, compute a transformation t* in T that minimizes d(t*(A),B). We consider solid shapes, i.e., full-dimensional shapes, in arbitrary dimension and assume that they are given by an oracle that generates uniformly distributed random points from the shapes. This is a very rich class of shapes that contains the class of finite unions of simplices as a subclass. We study matching under translations and rigid motions (translation and rotation). Throughout this work, the volume of the symmetric difference is used as distance measure for the matching problem. Maximizing the volume of the overlap is equivalent to minimizing the volume of the symmetric difference under translations and rigid motions. We study a probabilistic approach to the shape matching problem. The main idea is quite simple. Given two shapes A and B, repeat the following random experiment very often: Select random point samples of appropriate size from each shape and compute a transformation that maps the point sample of one shape to the sample of the other shape. Store this transformation. In each step, we extend the collection of random transformations by one. Clusters in the transformation space indicate transformations that map large parts of the shapes onto each other. We determine a densest cluster and output its center. This thesis describes probabilistic algorithms for matching solid shapes in arbitrary dimension under translations and rigid motions. The algorithms are a priori heuristics. The main focus is on analyzing them and on proving that they maximize the volume of overlap approximately by solving the following instance of the matching problem. Given two solid shapes A and B, an error tolerance eps in (0,1), and an allowed probability of failure p in (0,1), the problem is to compute a transformation t* such that with probability at least 1-p, we have that the volume of the intersection of t*(A) and B is at least as large as the volume of the intersection of t(A) and B minus an error of e times the volume of A for all transformations t, in particular for transformations maximizing the volume of overlap. The approach is mainly of theoretical interest. Still, the algorithms are so simple that they can easily be implemented, which we show by giving experimental results of a test implementation for 2-dimensional shapes.

Die zentrale Frage in der Musteranpassung ist, ob zwei gegebene Objekte A und B sich ähneln. Methoden, die diese Frage lösen, haben zahlreiche Anwendungen in verschiedenen Gebieten der Informatik. Muster können aufgrund verschiedener Merkmale verglichen werden, zum Beispiel aufgrund der Farbe, der Textur oder aufgrund von ausgezeichneten Punkten. In dieser Arbeit werden Muster aufgrund geometrischer Merkmale verglichen, wie es in der Algorithmischen Geometrie üblich ist. Seien eine Menge von Mustern S, eine Menge von Transformationen T, die Muster auf Muster abbilden, und ein Abstandsmaß d gegeben. Das Musteranpassungsproblem bezüglich S, T und d besteht darin, für gegebene Muster A, B in S eine Transformation t* in T zu berechnen, die den Abstand d(t*(A),B) minimiert. Wir betrachten volldimensionale Muster in beliebiger Dimension und nehmen an, dass die Muster durch ein Orakel gegeben sind, das gleichverteilte Zufallspunkte aus ihnen erzeugt. Diese Klasse von Mustern ist sehr allgemein, da sie die Klasse der endlichen Vereinigungen volldimensionaler Simplizes als Teilklasse enthält. Als Transformationsklassen betrachten wir Translationen und starre Bewegungen. Als Abstandsmaß verwenden wir das Volumen der symmetrischen Differenz. Für Translationen und starre Bewegungen ist das Maximieren des Volumen des Durchschnitts äquivalent zum Minimieren des Volumens der symmetrischen Differenz. In dieser Arbeit wird ein probabilistischer Ansatz für das Musteranpassungsproblem verfolgt. Die zentrale Idee ist relativ einfach. Für zwei gegebene Muster A und B wird das folgende Zufallsexperiment sehr oft wiederholt: Aus beiden Mustern wird eine gewisse Anzahl an Zufallspunkten erzeugt. Dann wird eine Transformation berechnet, die die Zufallspunkte aus A auf die Zufallspunkte aus B abbildet. Diese Transformation wird gespeichert. In jedem Schritt wird eine Zufallstransformation zur Menge der gespeicherten Transformationen hinzugefügt. Häufungen im Transformationsraum zeigen Transformationen an, die große Teile der Muster aufeinander abbilden. Es wird die dichteste Häufung im Transformationsraum gesucht und ihr Mittelpunkt als Ergebnis ausgegeben. Wir beschreiben probabilistische Algorithmen zur Anpassung volldimensionaler Muster in beliebiger Dimension unter Translationen und starren Bewegungen. A priori sind diese Algorithmen Heuristiken. Der Schwerpunkt der Arbeit liegt darauf, die Algorithmen zu analysieren und zu beweisen, dass sie das Volumen des Durchschnitts approximativ maximieren. Genauer gesagt lösen die Algorithmen folgendes Problem: Gegeben zwei Muster A und B, eine Fehlerschranke e in (0,1) und eine erlaubte Fehlerwahrscheinlichkeit p in (0,1), berechne eine Transformation t*, so dass mit Wahrscheinlichkeit mindestens 1-p gilt, dass das Volumen des Durchschnitts von t*(A) und B mindestens so groß ist wie das Volumen des Durchschnitts von t(A) mit B minus eines Fehler von e mal dem Volumen von A für alle Transformationen t. Das gilt insbesondere für Transformationen, die das Volumen des Durchschnitts maximieren. Unser Ansatz ist zwar hauptsächlich von theoretischem Interesse, dennoch sind die vorgestellten Algorithmen so einfach, dass sie leicht implementiert werden können, was wir durch experimentelle Ergebnisse einer Testimplementation für zweidimensionale Muster belegen.