Geometrische Optimierung beweglicher und formbarer Objekte

In der geometrischen Datenverarbeitung gibt es eine Vielzahl von Anwendungsgebieten für geometrische Optimierungsalgorithmen, welche die Positionierung oder Verformung eines geometrischen Objekts (Kurve, Fläche, triangulierte Punktwolke, ...) beinhalten. Bei diesen Algorithmen kann eine geeignete Darstellung der Distanzfunktion von geometrischen Objekten sehr nützlich sein, damit zum Beispiel der kürzeste Abstand zwischen Objekten, oder das Ausmaß einer Überlappung effizient berechnet werden können. Die Darstellung der Distanzfunktion ist auch deshalb besonders wichtig, weil die Bestimmung des Abstands zwischen geometrischen Objekten bei den betrachteten Algorithmen den zeitintensivsten Teil darstellt. Deshalb ist ein detailliertes Studium der Geometrie der Distanzfunktion eines Objektes ein wichtiger Teil der geplanten Forschungsarbeiten. Die Distanzfunktion soll hierbei in Hinblick auf das Laufzeitverhalten der Optimierungsalgorithmen hierarchisch und adaptiv repräsentiert werden. Eine der Anwendungen betrifft das sogenannte Registrierungsproblem im Computer Vision. Dies behandelt die Aufgabe, ein oder mehrere Objekte so im Raum zu bewegen, dass diese (in Überlappungsbereichen) bestmöglich zueinander passen, oder dass sie mit anderen gegebenen Objekten übereinstimmen. Unser Ziel liegt darin, Alternativen zu bestehenden iterativen Algorithmen aufzuzeigen, welche flexibler sind und schneller konvergieren und somit auch in der industriellen Qualitätskontrolle einsetzbar sind. Ein weiteres Positionierungsproblem aus dem Gebiet der Robotik betrifft die Planung der Bewegung eines Roboters, bei der gegebene Positionen anzufahren und Hindernisse zu umgehen sind. Hier verfolgen wir neue Unterteilungsalgorithmen zum Design solcher Bewegungsvorgänge. Dabei können neue Methoden zur Konstruktion interpolierender oder approximierender Spline-Kurven auf Mannigfaltigkeiten eingesetzt werden. Läßt man in den betrachteten Optimierungsalgorithmen auch Deformationen der Objekte zu, so können diese Algorithmen auch für die Approximation von Flächen (oder Punktwolken) durch B-Spline- oder Subdivision- Flächen verwendet werden. Dies hat den Vorteil, keine Flächenparameter zu den vorgegebenen Datenpunkten abschätzen zu müssen. Es ist auch möglich, die approximierenden Flächen auf konvexe Flächen einzuschränken oder mit speziellen Flächentypen, wie Schieb- oder Regelflächen, zu approximieren. Wichtige Anwendungen der neuen Approximationsalgorithmen findet man zum Beispiel bei der Flächenrückführung in CAD-Systeme oder in der Computergraphik.

Digitale Fotoapparate zum Aufnehmen von gewöhnlichen zweidimensionalen (2D) Bildern sind heutzutage weitverbreitet und finden sich auch schon standardmäßig in Mobiltelefonen und anderen tragbaren elektronischen Geräten. Es gibt jedoch mittlerweile Apparate mit denen Objekte auch dreidimensional (3D) erfaßt werden können. Diese sind sehr viel teurer als ihre 2D-Gegenstücke und momentan fast nur an Universitäten oder in Firmen zu finden. Dasselbe gilt auch für die Software zum Verarbeiten der Daten. Während Bildbearbeitungssoftware für Digitalfotos sehr ausgereift und sogar gratis zu haben ist, wird an der Entwicklung von Software zur Bearbeitung von 3D-Daten noch intensiv geforscht um die Funktionalität zu verbessern und zu erweitern. Forschern im FWF Projekt "Geometrische Optimierung mit beweglichen und formbaren Objekten" ist es gelungen einige der grundlegenden Fragen im Zusammenhang mit der Ver- und Bearbeitung von geometrischen 3D-Daten zu lösen. Eine Klasse von 3D-Kameras tastet die Oberfläche von Objekten mit Laserlicht ab und erzeugt so eine 3D-Messpunktwolke. Für die meisten Objekte reicht eine einzelne Aufnahme nicht aus. Um komplexe Objekte vollständig erfassen zu können sind manchmal hunderte oder sogar tausende von Aufnahmen nötig. Eine fundamentale Aufgabe ist es die einzelnen Datensätze passend zusammenzusetzen. Momentan wird dafür noch Benutzerinteraktion benötigt, was sehr zeitaufwendig sein kann. Mit der immer größer werdenden Menge an verfügbaren Daten werden vollautomatische Methoden dringend benötigt. Eine weiterer Bearbeitungsschritt ist die automatische Erstellung von Flächenmodellen aus den Punktwolken. Die intensive Grundlagenforschung im FWF Projekt hat zu sehr vielversprechenden Ergebnissen in den erwähnten Bereichen geführt. Diese Resultate bilden eine wichtige Grundlage für die zukünftige Entwicklung von besserer Software zur Ver- und Bearbeitung von geometrischen 3D-Daten.