Statistisches Formenwissen für die 3D-Rekonstruktion
Final Report Abstract
Zentrales Thema des beantragten Projektes war die Entwicklung von Modellen der Formähnlichkeit für drei-dimensionale Formen und die Entwicklung von Algorithmen zur Integration statistischen 3D Formenwissens in die 3D Rekonstruktion. Im Rahmen des Projektes wurde deutlich, dass die Modellierung von 3D Formähnlichkeit – inbesondere die Frage der Berechenbarkeit leistuntsfähiger Ähnlichkeitsmaße – eine enorm schwierige Herausforderung ist. Dieser Frage ist sehr viel mehr Aufmerksamkeit gewidmet worden als ursprünglich eingeplant. Bezüglich der obigen Fragestellungen haben wir im Rahmen des geförderten Projektes eine Reihe von Fortschritten erzielt. Die wichtigste im Rahmen des Projektes enstandene Arbeit ist ein Verfahren, welches es erlaubt, die Ähnlichkeit zweier 3D Formen effizient zu quantifizieren. In dieser Arbeit zeigen wir, dass sich die Ähnlichkeit zweier 3D Formen mit Hilfe von elastischen Thina Shell Energien quantifizieren lässt. Insbesondere zeigen wir, dass die Berechnung der optimalen Korrespondenz sich durch Linear Programming Relaxationen effizient berechnen lässt. Das Verfahren berechnet also gleichzeitig die Ähnlichkeit zweier 3D Formen als auch eine dichte Korrespondenz zwischen beiden Formen. Eine effiziente Optimierung mit GPU-beschleunigten Primal-Dual-Algorithmen und Coarse-to-Fine Multiresolution Strategie wurde in einer Publikation dargestellt. Eine weitere zentrale Herausforderung dieses Projektes war die schnelle Generierung von 3D Formen aus Bildern. In diesem Kontext haben wir eine Reihe von Verfahren entwickelt, um aus Bilddaten 3D Formen zu berechnen. Beispielhaft sei als Ergebnis hier das Verfahren genannt, welches es erlaubt, interaktiv aus 20-30 kalibrierten Bildern relativ gute 3D Modelle in wenigen Sekunden zu berechnen. Durch das entwickelte Verfahren lassen sich anschliessend feinskalige Strukturen rekonstruieren. Bezüglich der Integration von Formenwissen in die Rekonstruktion haben wir ein Verfahren entwickelt, welches das Problem für 2D planare Formen in Polynomzeit optimal löst. Die Verallgemeinerung eines solchen Algorithmus für 3D Formen steht allerdings noch aus. Es ist zu erwarten, dass sich hierfür keine polynomzeit-optimale Lösung finden wird. Die im Rahmen des Projektes entwickelten Verfahren lassen sich in mancher Hinsicht erweitert oder in konkrete Anwendungen einbringen. Eine weitere Arbeit erlaubt eine gleichzeitige Berechnung von Formähnlichkeit und ein dichtes Matching zwischen zwei 3D Formen. Hier ergeben sich vielfältige Erweiterungen und Anwendungen: Erstens lässt sich das Maß der Formähnlichkeit nutzen, um für 3D Formen Clustering und Retrieval aus Datenbanken zu bestimmen. Zweitens lässt sich das dichte Matching nutzen, um 3D Formen zu interpolieren. Dadurch ensteht eine Familie von bisher nicht beobachteten Zwischenformen. Des weiteren läßt sich das dichte Matching verwenden, um ein Label Transfer zu realisieren: Gegeben eine gelabelte menschliche Form (Kopf, Nase, Hals, Arme, Hände, etc sind gelabelt), kann man eine neue 3D Form mit dem Algorithmus auf die gelabelte matchen und anschließend die Label übertragen. Dadurch ließe sich eine bisher nicht gesehene 3D Form automatisch klassifizieren und semantisch analysieren. Unsere Arbeit erlaubt die gleichzeitige 3D Rekonstruktion und Silhouettenbestimmung aus kalibrierten Bildern. Insbesondere die Silhouetten des 3D Objektes in den Einzelbildern ist eine wichtige Voraussetzung für viele andere Algorithmen – beispielsweise für die Berechnung visueller Hüllen. Daher ist zu erwarten, dass dieses Verfahren in einer Vielzahl anderer Algorithmen Anwendung finden wird. Ein weiteres Verfahren erlaubt in Polynomzeit das Finden elastisch deformierter Konturen in Bildern. Das Verfahren ist enorm praxistauglich, da es hochgradig robust und echtzeitfähig ist. Die Erweiterung dieses Verfahrens für Formen im Dreidimensionalen ist eine bisher ungelöste Herausforderung. Leider ist allerdings zu erwarten, dass sich die 3D Verallgemeinerung nicht mehr optimal lösen läßt, sondern nur noch Approximationen möglich sind, die vermutlich mit relativ großem Laufzeit- und Speicheraufwand einher gehen.
Publications
-
Matching non-rigidly deformable shapes across images: A globally optimal solution. In: Int. Conf. on Computer Vision and Pattern Recognition (CVPR), Anchorage, Alaska, June 2008
T. Schoenemann and D. Cremers
-
A combinatorial solution for model-based image segmentation and real-time tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(7):1153–1164, 2010
T. Schoenemann and D. Cremers
-
Geometrically consistent elastic matching of 3d shapes: A linear programming solution. In: IEEE Int. Conf. on Computer Vision (ICCV), 2011
T. Windheuser, U. Schlickewei, Frank R. Schmidt, and D. Cremers
-
Large-scale integer linear programming for orientation-preserving 3d shape matching. In: Computer Graphics Forum (Proceedings Symposium Geometry Processing). Eurographics, 2011
T. Windheuser, U. Schlickewei, Frank R. Schmidt, and D. Cremers
-
Multiview stereo and silhouette consistency via convex functionals over convex domains. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(6):1161–1174, 2011
D. Cremers and K. Kolev
-
Fast joint estimation of silhouettes and dense 3D geometry from multiple images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(3):493–505, 2012
K. Kolev, T. Brox, and D. Cremers