Elastic Shape Matching: Theoretical Models and their Algorithmic Complexity
Final Report Abstract
Der Ausdruck "geometrische Musteranpassung" (GSM) beschreibt eine Menge von Problemen in der Informatik, die im Kern verschiedener Forschungsfelder und wissenschaftlicher sowie wirtschaftlicher Anwendungen liegen. Geometrische Musteranpassungsprobleme werden im Zusammenhang mit Biochemie (z.B. Wirkstoffentwicklung), Computergrafik (z.B. virtuelle/erweiterte Realität), Robotik und Mensch-Computer-Interaktion, sowie Medizin (z.B. computergestützte Chirurgie) erforscht, um nur einige zu nennen. GSM fällt in die Kategorie der Algorithmenforschung in der algorithmischen Geometrie, einem etablierten Gebiet in der theoretischen Informatik, dem ein erhebliches Maß an Aufmerksamkeit in der Community zuteil wurde. Forschung in der algorithmischen Geometrie untersucht die algorithmische Komplexität von geometrischen Problemen, also von Problemen, die mit geometrischen Grundformen und Strukturen einhergehen und deren Lösung geometrisches Denken voraussetzt. Einfach gesagt ist GSM die Aufgabe, zu berechnen, wie ähnlich sich zwei geometrische Formen sind. Musteranpassungsalgorithmen werden verwendet, um geometrische Objekte (oder Mengen solcher Objekte) zu vergleichen, indem eine einzige Transformation aus einer geeigneten Klasse zulässiger geometrischer Transformationen verwendet wird, um beide Objekte basierend auf den geometrischen Eigenschaften der spezifischen Instanzen aufeinander abzubilden. In vielen Anwendungen, wie zum Beispiel der Registrierung von Weichgewebe während einer computergestützten Operation, wo lokale Verzerrungen und komplexe Deformierungen vorkommen können und Genauigkeit und belegbare Fehlerschranken entscheidend sind, sind GSM Probleme zu restriktiv, weil eine einzige Transformation nicht ausreichend ist, um die gegebenen geometrischen Formen gut aufeinander abzubilden. Ein flexiblerer Ansatz ist nötig. Wir führten einen neue Art von GSM ein, indem wir Modelle für elastische Musteranpassung (ESM) definierten und die algorithmischen Grundlagen dafür bereit stellten. Während die zentralen Aufgaben von GSM, wie das Messen der Ähnlichkeit zweier geometrischer Objekte, das Zurückgewinnen ähnlicher Objekte und das Angleichen verschiedener Räume, beibehalten werden, basiert ESM auf einer fundamental anderen und neuartigen Modellierung dieser Probleme, da mehr als eine Transformation verwendet wird, um die gegebenen geometrischen Objekte aufeinander abzubilden. Zusätzlich wird den vorliegenden Transformationen eine Ähnlichkeit abhängig von einem geeigneten Ähnlichkeitsmaß zueinander vorgegeben. Dieses Modell erlaubt es, sich von bisherigen Annahmen und Einschränkungen zu trennen und bindet wichtige Aspekte dieser Problemklasse mit ein, die bisher nur unabhängig voneinander betrachtet wurden, sofern das uüberhaupt geschah. ESM bietet einen flexibleren Weg, um Probleme zu modellieren, die in praktischen Anwendungen auftauchen, da es für viele Szenarien Lösungen ermöglicht, die sowohl lokal als auch global konsistent sind. Während dieses Projektes modellierten und erforschten wir die theoretischen (algorithmischen) Grundlagen von ESM, indem wir die algorithmische Komplexität seiner verschiedenen Varianten untersuchten. Wir konnten exakte, effiziente (d.h. Polynomialzeit-) Algorithmen und Heuristiken für einige Varianten dieser Probleme entwickeln und gaben effiziente Approximationsalgorithmen für Problemvarianten an, von denen wir annahmen oder beweisen konnten, dass sie algorithmisch schwer sind (im Sinne von NP-schwer).
Publications
- Elastic Geometric Shape Matching for Point Sets under Translations. In Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 578–592, 2015
Christian Knauer and Fabian Stehn
(See online at https://doi.org/10.1007/978-3-319-21840-3_48) - Elastic Geometric Shape Matching for Translations under Manhattan Norm. In Proceedings of the 31th European Workshop on Computational Geometry (EuroCG), 2015
Christian Knauer, Luise Sommer, and Fabian Stehn
(See online at https://doi.org/10.1016/j.comgeo.2018.01.002) - An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods. In Computational Science and Its Applications – ICCSA 2018, pages 425–443, 2018
Christian Knauer, Luise Sommer, and Fabian Stehn
(See online at https://doi.org/10.1007/978-3-319-95165-2_30) - Elastic Geometric Shape Matching for Translations under the Manhattan Norm. In Computational Geometry: Theory and Applications, 2018
Christian Knauer, Luise Sommer, and Fabian Stehn
(See online at https://doi.org/10.1016/j.comgeo.2018.01.002) - Elastic Geometric Shape Matching. PhD Thesis, Universität Bayreuth, 2021
Luise Sommer
