Christian Knauer:
Algorithms for Comparing Geometric Patterns
Kurzbeschreibung
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.