Elastische Registrierung dreidimensionaler Formen durch kombinatorische Optimierung
Final Report Abstract
Zentrales Thema des beantragten Projektes war die Entwicklung von Algorithmen für die Registrierung von Formen. Dieses Problem ist eine zentrale Komponente vieler sinnvoller Maße von Formähnlichkeit. Im Gegensatz zu den meisten Arbeiten in diesem Feld haben wir uns nicht auf isometrische Formen eingeschränkt, sondern explizit auch elastische Deformationen berücksichtigt, wie beispielsweise die Streckung oder Stauchung von Teilen einer Form. Dieser Aspekt ist wichtig, da beispielsweise zwei Handformen als ähnlich angesehen werden können, auch wenn ein Finger vergleichweise kürzer ist oder ganz fehlt und die gesuchte Transformation zwischen den beiden Formen damit keine Isometrie mehr ist. Mathematisch lag die zentrale Herausforderung in der Überbrückung zwischen kontinuierlichen Optimierungsproblemen (über dem Raum der orientierungserhaltenden Diffeomorphismen) und den für die konvexe Relaxation vorgeschlagenenen diskreten kombinatorischen Optimierungsproblemen, bei denen man typischerweise auf Integer-lineare Programme stößt, mit Binärvariablen auf dem Raum der Paare von Dreiecken von je einer der beiden Formen (die entsprechende Binärvariable ist 1, wenn die Dreicke korrespondieren und 0 sonst). Wir haben eine Vielzahl der Herausforderungen angegangen, sind aber in manchen Punkten von den Arbeitspaketen des ursprünglichen Antrages abgewichen. Konkret haben wir uns weniger auf die mathematische Analyse existierender Algorithmen konzentriert und dafür stärker auf die Entwicklung neuer Algorithmen - beispielsweise auf Basis von geometrischer Maßtheorie oder mit Hilfe von Markov’schen Zufallsfeldern. Dabei haben wir eine Reihe von Fortschritten erzielt: • Wir haben neue kombinatorische Lösungen für die Berechnung höherdimensionaler dichter Korrespondenz entwickelt. Insbesondere mit Methoden der geometrischen Maßtheorie konnten wir konvexe Formulierungen für das genannte Problem entwickeln. • Wir haben das Form-Korrespondenz und Form-Ähnlichkeitsproblem mit Hilfe geeigenter Machine Learning Verfahren gelöst und damit insbesondere 3D Shape Retrieval auf einer Reihe von Datensätzen demonstrieren können. • Wir haben das Problem der 2D-zu-3D Formregistrierung erstmalig als kombinatorisches Problem beweisbar optimal gelöst. Eine dichte elastische Korrespondenz lässt sich in polynomieller Laufzeit berechnen. Die Korrespondenzkosten lassen sich als Ähnlichkeitsmaß für Retrieval-Experimente einsetzen.
Publications
- Dense elastic 3d shape matching. In Global Optimization Methods, volume 8293 of Lect. Not. Comp. Sci., pages 1–18. Springer, 2014
F. R. Schmidt, T. Windheuser, U. Schlickewei, and D. Cremers
(See online at https://doi.org/10.1007/978-3-642-54774-4_1) - Dense non-rigid shape correspondence using random forests. In Int. Conf. on Computer Vision and Pattern Recognition (CVPR), 2014
E. Rodola, S. Rota Bulo, T. Windheuser, M. Vestner, and D. Cremers
(See online at https://doi.org/10.1109/CVPR.2014.532) - A convex solution to spatially-regularized correspondence problems. In European Conference on Computer Vision, October 2016
T. Windheuser and D. Cremers
(See online at https://doi.org/10.1007/978-3-319-46475-6_52) - Applying random forests to the problem of dense non-rigid shape correspondence. In Perspectives in Shape Analysis, pages 231–248. Springer, 2016
M. Vestner, E. Rodolà, T. Windheuser, S. Bulò, Rota Bulo, and D. Cremers
(See online at https://doi.org/10.1007/978-3-319-24726-7_11) - Efficient globally optimal 2d-to-3d deformable shape matching. In Int. Conf. on Computer Vision and Pattern Recognition (CVPR), May 2016
Z. Laehner, E. Rodola, F. R. Schmidt, M. M. Bronstein, and D. Cremers
(See online at https://doi.org/10.1109/CVPR.2016.240) - Non-rigid 3d shape retrieval via large margin nearest neighbor embedding. In European Conference on Computer Vision, October 2016
I. Chiotellis, R. Triebel, T. Windheuser, and D. Cremers
(See online at https://doi.org/10.1007/978-3-319-46475-6_21)
