Algorithmen zum Vergleich geometrischer Muster

Abstract

Das geometrische Mustererkennungsproblem besteht darin, zu zwei gegebenen Mustern P und Q aus einer Menge von zulässigen Mustern Π und einem Abstandsmaß δ für solche Muster eine Transformation τ aus einer Menge von zulässigen Transformationen T zu finden, so daß der Abstand δ(τ(P),Q) möglichst klein wird. In der Dissertation werden effiziente Algorithmen für verschiedenen Varianten dieser Problemstellung vorgestellt; die Ergebnisse lassen sich anhand der Art der zulässigen Muster gruppieren: Punktmuster im Rd: Im ersten Teil betrachten wir Punktmuster; die Figuren sind Mengen von m bzw. n Punkten im Rd. Kongruenztest: Wir geben einen Algorithmus an, der in O(n ⌈d/3 ⌉ log n) Zeit (m < n) entscheidet, ob es eine Kongruenzabbildung gibt, die P auf Q abbildet (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem das Abstandsmaß die triviale Metrik ist). Hausdorff-Abstand: Wir beschreiben den ersten nicht-trivialen Algorithmus zur Berechnung des gerichteten Hausdorff-Abstandes h(P,Q) von einer Menge von Punkten P zu einer Menge von semialgebraischen Mengen konstanter Beschreibungskomplexität Q (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem die Identität die einzige zulässige Transformation ist); die Laufzeit ist Oε(m nε log m+m1+ε-1/(2d-2) n). Planare Kurven: Der zweite Teil beschäftigt sich mit Mustererkennungsproblemen für polygonale Kurven in der Ebene; die Figuren sind Polygonzüge P,Q mit m bzw. n Ecken und als Abstandsmaß betrachten wir den Frechét-Abstand F(P,Q) von P und Q. Matching unter Translationen: Wir entwickeln den ersten Algorithmus, der das Matchingproblem für Polygonzüge bezüglich des Frechét-Abstandes unter Translationen löst; die Laufzeit ist O((m n)3(m+ n)2). Außerdem geben wir einen O(ε-2 m n) Approximationsalgorithmus der Güte (1+ε) für dieses Problem an, indem wir Referenzpunktmethoden verallgemeinern. Weiterhin zeigen wir, daß es für affine Abbildungen keine solchen Referenzpunkte gibt. Hausdorff- vs. Frechét-Abstand: Wir zeigen, daß für eine gewisse Klasse von Kurven ein linearer Zusammenhang zwischen dem Frechét- und dem Hausdorff-Abstand besteht. Für diese Art von Kurven geben wir einen O((m+ n) log2(m+ n) 2α(m+ n)) Approximationsalgorithmus zur Berechnung von F(P,Q) an. Schließlich beschreiben wir den ersten nicht- trivialen Algorithmus um solche Kurven zu erkennen; die Laufzeit ist O(n log2 n). Einfache polyedrische Flächen im R3: Im letzten Teil betrachten wir Muster die sich aus Mengen P und Q von m bzw. n disjunkten Dreiecken im R3 zusammensetzen. Hausdorff-Abstand: Wir entwickeln einen Algorithmus, der H(P,Q), den Hausdorff-Abstand zwischen P und Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) Zeit berechnet.

The geometric shape matching problem reads as follows: given two shapes P and Q from a set of valid shapes Π and a distance measure δ for these shapes, find a transformation τ from a set of valid transformations T, such that the distance δ(τ(P),Q) is as small as possible. In this thesis we present efficient algorithms for variants of this problem; the results can be grouped according to the shapes considered: Point patterns in Rd: In the first part we consider point patterns; the shapes are point sets consisting of m and n points in Rd, respectively. Congruence test: We present an algorithm to decide in O(n ⌈d/3 ⌉ log n) time (m < n), whether there is a congruence, that maps P onto Q (this can be considered as a special case of the shape matching problem where the distance measure is the discrete metric). Hausdorff-distance: We give the first non-trivial algorithm to compute the directed Hausdorff- distance h(P,Q) from a set of points P to a set Q of semialgebraic sets of constant description complexity each (this can be considered as a special case of the shape matching problem where the identity is the only valid transformation); the runtime is Oε(m nε log m+m1+ε-1/(2d-2) n). Planar curves: The second part deals with the shape matching problem for polygonal curves in the plane; the shapes are polygonal chains P,Q with m and n vertices, respectively. The distance measure is the Frechét-distance F(P,Q) of P and Q. Matching under translations: We give the first algorithm for matching polygonal chains with respect to the Frechét-distance under translations; the runtime is O((m n)3(m+ n)2). Furthermore we describe an O(ε-2 m n) approximation algorithm of quality (1+ε) by generalizing reference-point based methods. Finally we prove that reference-points for affine maps do not exist. Hausdorff- vs. Frechét-distance: We show that the Frechét- and the Hausdorff- distance are linearly related for a certain class of curves. For curves of that type we describe an O((m+ n) log2(m+ n) 2α(m+ n)) time approximation algorithm to compute F(P,Q). We conclude with the first non-trivial algorithm to detect such curves; it runs in O(n log2 n) time. Simple polyhedral surfaces in R3: In the last part we consider shapes that are composed of sets P and Q of m and n disjoint triangles in R3. Hausdorff-distance: We develop an algorithm that computes H(P,Q), the Hausdorff-distance between P and Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) time.