Untersuchung der Formbeschreibung von 3D-Objekten mittels einer 3D-Kurve

 

Mathematik  |  Informatik

 

Amer Monir, 2000 | Oberwil, BL

 

In dieser Arbeit wurde ein Suchalgorithmus für 3D-Objekte selbständig in Python implementiert, untersucht und verbessert. Der Algorithmus wurde von E. Ait Lmaati et al. unter dem Titel „A 3-D Search engine based on Fourier series“ veröffentlicht. Bei dem Algorithmus werden die 3D-Objekte mithilfe der kontinuierlichen Hauptkomponentenanalyse normalisiert. Daraufhin wird das Modell durch eine zu einer kugelförmigen Spirale homöomorphe 3D-Kurve überzogen. Aus einer approximierten 2D-Funktion, welche die Abstände zwischen dem Schwerpunkt des Objekts und der 3D-Kurve angibt, wird die Fourier-Reihe berechnet. Die Fourier-Koeffizienten bilden den „Feature Vector (FV)“, welcher als Mass für die Ähnlichkeit der Objekte agiert. In der Arbeit wurden die Grundkonzepte des Algorithmus erklärt und einfach veranschaulicht. Untersucht wurde das genaue Verhalten des Algorithmus. Hierfür wurden die „Princeton Shape Benchmark“ und „ShapeNet“ Datensätze verwendet. Abschliessend wurde ein Ansatz zur Verbesserung der Definition der 3D-Kurve vorgeschlagen und umgesetzt.

Fragestellung

Das Ziel der Arbeit war es, das Verhalten des Suchalgorithmus zu untersuchen, indem die Faktoren identifiziert werden, welche zu guten bzw. schlechten Ergebnissen bei der Suche nach unterschiedlich geformten Objekten führen. Auf dieser Grundlage sollten Ansätze zur Verbesserung des Algorithmus vorgeschlagen und umgesetzt werden.

Methodik

Für die Untersuchung wurden der PSB- (1814 Modelle mit über 150 Kategorien) und der SN-Datensatz (52000 Modelle mit 55 Kategorien) verwendet. Als allgemeine Bewertungskriterien wurden Werte für Genauigkeit und Trefferquote des Algorithmus bei Modellanfragen innerhalb der Datensätze berechnet. Für diese Berechnung wird überprüft, ob die Ergebnisse der Suchanfrage zur gleichen Kategorie wie das Query gehören. Der Schwerpunkt der Arbeit lag aber bei der Untersuchung von konkreten Suchergebnissen. Für die Identifizierung der Faktoren, welche einen Einfluss auf die Ergebnisse hatten, wurden die 3D- und die 2D-Kurve, welche zur Extrahierung vom FV verwendet wird, visualisiert. Dies diente dem Zweck, die Kurven von Modellen zu vergleichen, welche vom Suchalgorithmus gemäss ihrer FVs als ähnlich angesehen wurden, um dadurch das Verhalten des Algorithmus besser zu verstehen. Anhand dessen wurde die kugelförmige Spirale so optimiert, dass sie die gleiche Ausdehnung wie das Modell hat und die Punkteverteilung ihr entlang homogenisiert wurde.

Ergebnisse

Beim PSB wies der Algorithmus bei Suchanfragen mit einem Suchradius von einem Nachbar eine mittlere Genauigkeit von 47%. Beim SN war es 73%. Jedoch nahm die Genauigkeit mit grösser werdenden Suchradius in beiden Fällen signifikant ab, wohingegen die Trefferquote nur langsam zunahm. Nach der Optimierung der 3D-Kurve verbesserte sich die Genauigkeit in beiden Datensätzen schätzungsweise um 2-3%. Die weiteren Untersuchungen zeigten, dass das Spannen einer Spirale über der Oberfläche der Modelle nicht sehr günstig ist: Diese rotiert in ihre Bewegungsrichtung um das Modell und überquert somit unterschiedliche Regionen in kleinen Intervallen. Dadurch dass die 2D-Abstandfunktion dann approximiert wird, verschmelzen die geometrischen Informationen zu den unterschiedlichen Regionen zusammen. Hinzu kommt, dass Fourier-Reihen komplexe Formen wie Ecken oder Löcher weniger gut repräsentieren können. Nichtsdestotrotz ist der Algorithmus gut darin, die allgemeine geometrische Form zu erkennen. Denn selbst bei falschen Ergebnissen in den Suchanfragen wiesen die Modelle ähnliche geometrische Formen auf.

Diskussion

Die Untersuchung konkreter Beispiele war Zielführend. Sie hat jedoch einen grossen Nachteil; und zwar beruhen die gewonnenen Erkenntnisse lediglich auf Beobachtungen und nicht auf nummerischen Werten oder mathematischen Konzepten. Dies schwächt die Aussagekraft. Die Berechnung der Genauigkeit anhand von Modellkategorien ist ebenfalls nicht ganz geeignet. Denn die gegebenen Kategorien berücksichtigten nicht, wie ähnlich die geometrischen Formen der Modelle sind. Die Ergebnisse liefert aber trotzdem gute Einblicke in das Verhalten der 3D-Kurve.

Schlussfolgerungen

Der Algorithmus ist sehr stark von der spiralförmigen 3D-Kurve abhängig, und von ihr beim Erfassen von Modelloberflächen durch das Vermischen geometrischer Informationen teilweise eingeschränkt. Hierzu wäre es interessant alternative Methoden zur Erzeugung der 3D-Kurve zu untersuchen, um diese Einschränkungen zu umgehen. Die vorgeschlagene Verbesserung ermöglichte dem Algorithmus geometrisch ähnliche Objekte, abgesehen davon, ob sie zur gleichen Kategorie gehören oder nicht, effektiver zu erkennen.

 

 

Würdigung durch die Expertin

Kahlina Dragica

Amer Monir hat einen 2010 veröffentlichten Algorithmus zur Kategorisierung von 3D-Modellen neu in Python programmiert und optimiert, z.T. mit eigenen Lösungsansätzen, wo die ursprüngliche Veröffentlichung zu vage blieb. In der ersten Untersuchung war die Trefferquote niedriger als erwartet. Nach einer Analyse hat Amir Monir verschiedene mögliche Schwachpunkte im Algorithmus und in der 3D-Modelldatenbank aufgezeigt. Mit seiner Verbesserung des Algorithmus und einer anderen Datenbank konnte er die Trefferquote erhöhen. Damit hat er den ursprünglichen Algorithmus erweitert und Möglichkeiten für weitere Verbesserungen aufgezeigt.

Prädikat:

sehr gut

 

 

 

Gymnasium Oberwil
Lehrer: Hans Adrian-Schmassmann