Elastic Geometric Shape Matching

Titelangaben

Sommer, Luise:
Elastic Geometric Shape Matching.
Bayreuth , 2021 . - XII, 176 S.
( Dissertation, 2022 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)
DOI: https://doi.org/10.15495/EPub_UBT_00006494

Volltext

Link zum Volltext (externe URL):

Angaben zu Projekten

Abstract

In computational geometry, geometric shape matching (GSM) problems are among the classical and well-studied geometric optimization problems. In a conventional GSM problem, the pattern P and the model Q, both from a class S of geometric shapes, are given, along with a suitable distance measure d. The task is to compute a single transformation t from an admissible transformation class T acting on S that minimizes the distance between the transformed pattern and the model according to the distance measure d.
Problems of this flavor have many applications such as traffic sign recognition, character recognition, human-computer-interaction, etc., in different scientific fields such as robotics, computer aided medicine and drug design. Yet in cases where local distortions or complex deformations occur, a single transformation from a simple transformation class is not enough to match the pattern well to the model. A more flexible approach is needed.
Elastic geometric shape matching (EGSM) is a generalization of the conventional GSM and was designed with the intention of ensuring a both globally consistent and locally precise mapping in cases where the classical GSM approach is too restrictive.
In an EGSM problem, one is given a pattern P and a model Q along with a graph G. The pattern P is partitioned into subshapes and instead of a single transformation, a so-called transformation ensemble is computed. A transformation ensemble consists of a set of transformations, one for each subshape of P, that are individually applied to the subshapes of P with the goal to minimize the distance of the transformed pattern to the model according to a suitable distance measure. Additionally, some of the transformations are enforced to be similar with respect to a suitable similarity measure defined for the transformation class at hand. In doing so, the consistency and “continuity” of the ensemble, and consequently, also of the transformed pattern, is ensured. The graph G is called neighborhood graph, and encodes which transformations need to be similar.
There is a vast number of variations of EGSM problems, depending on how the different options for, eg., S, T , the distance measures, and structure of G, are chosen to match the application at hand. In particular, just slight changes in the problem setup may result in the need of completely different strategies to compute a solution. In this thesis, we analyze the computational complexity of several EGSM problem variants under translations under the L1-, the L2- and under polygonal norms for different distance measures and graph classes. Additionally, we present exact and approximative algorithms to solve the considered problem variants.

Abstract in weiterer Sprache

Geometrische Musteranpassungsprobleme (GSM Probleme) gehören zu den klassischen und gut untersuchten geometrischen Optimierungsproblemen in der algorithmischen Geometrie. In einem konventionellen GSM Problem sind das Muster P und das Modell Q, beide aus einer Klasse S von geometrischen Objekten, zusammen mit einem geeigneten Abstandsmaß d gegeben. Das Ziel besteht darin, eine einzelne Transformation t aus einer zulässigen, auf S wirkenden, Transformationsklasse T zu berechnen, die den Abstand zwischen dem transformierten Muster und dem Modell bezüglich des Abstandsmaßes d minimiert.
Probleme dieser Art haben viele Anwendungen, wie zum Beispiel Verkehrszeich- enerkennung, Texterkennung und Mensch-Computer-Interaktion, in verschiede- nen wissenschaftlichen Bereichen wie der Robotik, der computergestützten Medizin und der Wirkstoffentwicklung. Allerdings ist in den Fällen, in denen lokale Verzerrungen oder komplexe Deformierungen auftreten, eine einzelne Transformation aus einer einfachen Transformationsklasse nicht genug, um das Muster gut auf das Modell abzubilden. Ein flexiblerer Ansatz wird benötigt. Elastische Musteranpassung (EGSM) ist einer Verallgemeinerung der konventionellen GSM und wurde mit der Absicht entwickelt, eine sowohl global konsistente als auch lokal präzise Abbildung in den Fällen sicherzustellen, in denen der klassiche GSM Ansatz zu sehr einschränkt.
In einem EGSM Problem sind ein Muster P und ein Modell Q zusammen mit einem Graphen G gegeben. Das Muster P ist in Teilmuster unterteilt und anstatt einer einzelnen Transformation wird ein sogenanntes Transformation- sensemble berechnet. Ein Transformationsensemble besteht aus einer Menge von Transformationen, eine für jedes Teilmuster von P, die individuell auf die Teilmuster von P mit dem Ziel angewendet werden, den Abstand zwischen dem transformierten Muster und dem Modell bezüglich eines geeigneten Abstandsmaßes zu minimieren. Zusätzlich sollen einige der Transformationen ähnlich bezüglich eines geeigneten Ähnlichkeitsmaßes sein, das für die gegebene Transformationsklasse definiert wurde. So werden die Kontinuität und die “Stetigkeit” des Ensembles, und damit auch die des transformierten Musters, sichergestellt. Der Graph G wird Nachbarschaftsgraph genannt, weil er kodiert, welche Transformationen sich ähnlich sein sollen.
Es gibt eine erhebliche Anzahl an Variationen von EGSM Problemen, abhängig davon wie beispielsweise S, T , die Abstandsmaße und die Struktur von G gewählt werden, um das Problem auf die konkrete Anwendung anzupassen. Genauer gesagt können schon kleine Veränderungen der Problemstellung dazu
führen, dass gänzlich unterschiedliche Strategien zur Lösungsfindung benötigt werden. In dieser Arbeit analysieren wir die algorithmische Komplexität einiger EGSM Probleme unter Translationen unter der L1-, der L2- und unter Polygonalnormen für verschiedene Abstandsmaße und Graphklassen. Darüber hinaus präsentieren wir exakte und approximative Algorithmen zur Lösung der betrachteten Problemvarianten.