EuroGIGA_Berechnung der Medial Axis

Die in diesem Projekt geplanten Forschungsaktivitäten sind den beiden Themen Mittelachse (Medial Axis) und der orientierten (vorzeichenbehafteten) Abstandsfunktion gewidmet, welche in enger Verbindung stehen. Die Mittelachse (Medial Axis), die 1967 von Blum eingeführt wurde, stellt eine sehr interessante Möglichkeit für die Beschreibung der Gestalt von Objekten dar. Sie fand Anwendungen in zahlreichen Gebieten, die von der Gestalterkennung in der Computer Vision bis zur Berechnung getrimmter Parallelkurven und -flächen im Computer Aided Design reichen. Das schwierige Problem der schnellen und stabilen Ermittlung der Mittelachse eines Freiformobjektes ist daher von grundlegender Bedeutung. In einer kürzlich erschienen Arbeit formulierten wir einen Algorithmus zur Berechnung der Mittelachse, der sowohl effizient als auch für eine robuste Implementierung geeignet ist. Wir konnten darüber hinaus zeigen, dass die Mittelachsen allgemeiner ebener Gebiete näherungsweise durch die Betrachtung der Mittelachsen von Gebieten mit stückweise kreisförmigen Randkurven berechnet werden können, wobei ein Konvergenzresultat verfügbar ist. In diesem Projekt ist geplant, diese Ergebnisse auf dreidimensionale Objekte zu verallgemeinern. Gegenwärtig arbeiten wir an der robusten Berechnung der Mittelachse für Objekte mit triangulierten Randflächen bezüglich einer stückweise linearen Approximation der euklidischen Metrik. Obwohl wir bereits vielversprechende Resultate erzielt haben, gibt es noch eine Reihe offener Fragen. Diese schließen die Frage nach der Formulierung eines effizienten Algorithmus sowie nach der Ermittlung des stabilsten Teils der Mittelachse ein. Um das Problem der Robustheit zu lösen ist geplant, die Berechnung der Mittelachse im Rahmen der Theorie der inversen Probleme zu behandeln. Dieser allgemeine Rahmen erlaubt es, stabile Lösungen für schlecht gestellte Probleme zu berechnen, bei denen das unbekannte Objekt aus (möglicherweise fehlerbehafteten) Beobachtungen rekonstruiert werden soll, wobei die Daten und das Objekt durch einen Operator miteinander verknüpft sind. Um diesen Zugang verwenden zu können, werden wir das Objekt mit seiner orientierten Abstandsfunktion identifizieren, die sich elegant aus der Mittelachse und der Information über die Radien der zugehörigen maximalen Kreise bzw. Kugeln erzeugen lässt. Eine weitere mögliche Anwendung dieses engen Zusammenhangs zwischen maximalen Kreisen und Kugeln und der orientierten Abstandsfunktion ist die Rekonstruktion dreidimensionaler Objekte aus (möglicherweise fehlerbehafteten) Punktdaten. In diesem Zusammenhang werden wir Approximationen der orientierten Abstandsfunktion einsetzen, die durch eine relative kleine Anzahl von maximalen einbeschriebenen Kugeln bestimmt sind, die also einer Teilmenge der Knoten des Voronoi-Diagramms entsprechen. Mit Hilfe dieser Approximationen werden wir korrekt orientierte Normalenvektoren der Daten ermitteln und diese benutzen, um eine Beschreibung der Randfläche zu erzeugen.

Die Arbeit in diesem Teilprojekt war drei Hauptthemen gewidmet. Der erste Teil beschäftigt sich mit effizienten Beschreibungsformen für dreidimensionale Objekte. Zunächst wurde ein neuer Berechnungsalgorithmus für ein bekanntes topologisches Skelett, den so genannten Reeb-Graphen, vorgestellt. Im Gegensatz zu bestehenden Algorithmen benötigt der neue Algorithmus nur ein Oberflächennetz des Objekts statt eines Volumennetzes. Solch ein Oberflächennetz besteht typischerweise aus deutlich weniger Elementen als ein Volumennetz ähnlicher Auflösung. Zudem entfällt die aufwändige Konstruktion eines Volumennetzes, falls das Objekt durch sein Oberflächennetz gegeben ist. Jedoch müssen gewisse Voraussetzungen erfüllt sein, um diese Konstruktion zu erlauben. Für einen konkreten Fall wird der vorgestellte Algorithmus in der Simulation von Tauchlackierprozessen in der Automobilindustrie verwendet. Als Erweiterung des Reeb-Graphen wurde der Reeb-Raum betrachtet. Während der Reeb Graph anhand einer skalaren Funktion auf dem betrachteten Bereich definiert wird, werden für den Reeb-Raum mehrere Funktionen verwendet. Der Reeb-Raum eines Objekts induziert eine Skelettstruktur, die aus mehreren verbundenen Oberflächenstücken besteht und die ungefähre Struktur des Objekts widerspiegelt. In der Literatur sind diverse andere solcher Skelettstrukturen bekannt, zum Beispiel die Mittelachse. Diese weist zwar einige wünschenswerte Charakteristika auf, doch ist ihre Berechnung im dreidimensionalen Fall sehr schwierig. Deshalb könnte der Reeb-Raum hier als effizientere Alternative dienen. Wir haben einen ersten Algorithmus vorgestellt, mit dem eine abstrakte Darstellung des Reeb-Raums berechnet werden kann, welche wir den geschichteten Reeb-Graphen nennen. Wie für den Reeb-Graphen verwendet unser Algorithmus nur ein Oberflächennetz des Objekts. Im zweiten Teil dieser Arbeit wurde ein neues Distanzmaß in der Ebene vorgestellt. Als Eingabe verwendet es Distanzen zwischen gewissen Punkten, wie zum Beispiel die Fahrzeiten zwischen bestimmten Städten. Über eine Einbettung in den höherdimensionalen Raum wird daraus ein globales Distanzmaß berechnet. Im gegebenen Beispiel würde dieses näherungsweise die Fahrzeiten zwischen beliebigen zwei Orten angeben. Der dritte Teil beschäftigt sich mit der Mittelachse von ebenen Gebieten. Die Mittelachse bildet ein aus Kurvensegmenten bestehendes Skelett des betrachteten Gebiets. Für Gebiete mit zerklüfteter Randkurve hat die Mittelachse jedoch deutlich mehr Äste, als nötig wären, um die Struktur des Gebiets wiederzugeben. Wir haben einen Algorithmus vorgestellt, der die Randkurve auf eine speziell geeignete Weise glättet, was zu einer deutlichen Vereinfachung der Mittelachse führt.