Laplace Spectra for Shape Recognition

by M. Reuter.

Books on Demand, ISBN 3-8334-5071-1, July 2006.

In dieser Arbeit wird ein Verfahren eingeführt, einen numerischen Fingerabdruck bzw. eine Signatur (die "Shape-DNA") einer beliebigen 2d- oder 3d-Mannigfaltigkeit (Fläche oder Körper) zu berechnen. Hierzu werden die Eigenwerte bzw. das Spektrum des zugehörigen Laplace-Beltrami-Operators ermittelt. Es ist ein neuer Ansatz, dieser Laplace-Beltrami-Spektren als Fingerabdrücke von Flächen und Körpern zu nutzen.

Da es sich bei dem Spektrum um eine Isometrieinvariante handelt, ist es unabhängig von der Beschreibung des Objekts, insbesondere von der Parametrisierung und der räumlichen Lage. Darüber hinaus lassen sich die Eigenwerte normalisieren, so dass uniforme Skalierungen des geometrischen Objekts leicht rückgängig gemacht werden können. Somit ist es allein durch den Vergleich der Spektren möglich, die Isometrie zweier Objekte zu überprüfen, ohne sie vorher in Deckung bringen zu müssen (Registrierung, Lokalisierung).

Diese Arbeit beschreibt die Berechnung und den Vergleich der Spektren von Objekten, die in verschiedenen Repräsentationen vorliegen können. Wir behandeln z.B. Objekte, die aus NURBS oder anderen parametrisierten Flächen zusammengesetzt sein können. Weiterhin betrachten wir polygonale Netze (z.B. 3d-Triangulierungen), solide Polyeder und gekrümmte Körper wie z.B. die Kugel oder den Zylinder. Indem wir die Isometrieinvarianz des Laplace-Beltrami-Operators ausnutzen, gelingt es uns die Eigenwerte von glatt berandeten Gebieten zu berechnen, ohne Diskretisierungsfehler durch eine Randapproximation zu erhalten.

Weiterhin wird eine Methode vorgestellt, glatt berandete Gebiete mit Hilfe der Medialen Achse zu parametrisieren. Dieses Verfahren führt zu einer besonders genauen Lösung von Differenzialgleichungen nach der Finite-Element-Methode. Die Genauigkeit dieser Methode wird an verschiedenen Objekten mit bekannten Spektren verifiziert. Darüber hinaus werden Beispiele von nicht-isometrischen aber isospektralen Körpern aufgeführt, die nicht durch ihr Spektrum unterschieden werden können, und es wird belegt, dass das Spektrum ihrer Mantelflächen genug Unterscheidungskraft besitzt, um sie auseinander zu halten.

Außerdem wird die schnelle Konvergenz der "Heat-Trace"-Reihe bewiesen und es wird demonstriert, dass es möglich ist, geometrische Daten wie z.B. das Volumen, die Randlänge und sogar die Euler-Charakteristik eines Objekts aus seinen numerisch berechneten Eigenwerten zu extrahieren. Diese Tatsache bestätigt nicht nur die Genauigkeit der berechneten Eigenwerte, sondern unterstreicht die geometrische Bedeutung des Spektrums.

Schließlich wird gezeigt, dass endliche Teilspektren für den Formvergleich von Flächen und Dreiecksnetzen in unterschiedlichen Auflösungen genutzt werden können. Mittels der hier vorgestellten "Shape-DNA" ist eine Realisierung von  Kopierschutzverfahren, Datenbankabfragen sowie Qualitätskontrollen von digital repräsentierten Flächen und Körpern möglich.