Elastic Shape Matching: Theoretical Models and their Algorithmic Complexity

几何形状匹配问题是计算几何领域的核心研究课题之一。在这类问题中，给出了两个几何对象(一个“图案”和一个“模型”)、一个变换类和一个相似性度量，其中一个从给定的类中寻找一个变换，使得通过该变换变换到模型的图案的相似性度量最大化。在这样的问题中，模式不是通过单一的变换来变换的，而是通过所谓的变换集合来变换的。变换集成允许图案的非均匀变形-图案的不同部分可以通过不同的映射进行变换。它们还允许结合图案的时间依赖性以及其形状随时间的变化。该项目详细考虑了以下问题：-弹性形状匹配问题的结构和代数复杂性研究-高效算法策略(精确的、近似的、参数化的)和检索数据结构的设计和分析-变换集合的相似性度量-弹性模式的空间和时间内插。

Geometric shape matching problems are one of the core research topics in the field of computational geometry. In such a problem one is given two geometric objects (a "pattern" and a "model"), a transformation class, as well as a similarity measure, and one seeks a transformation from the given class such that the similarity measure of the pattern transformed by this transformation to the model is maximized.In this project we introduce the concept of elastic (or non-uniform) geometric shape matching problems. In such a problem the pattern is not transformed by a single transformation, but by a so-called transformation ensemble. Transformation ensembles allow for non-uniform deformations of the pattern - different parts of the pattern can be transformed by different mappings. They also allow to incorporate temporal dependencies of the pattern as well as changes of its shape over time. Consequently it is possible to compute matchings that are valid within a certain time frame even if the reference objects change during this frame.In detail the project consides the following questions:- structural and algebraic complexity studies of elastic shape matching problems- design and analysis of efficient algorithmic strategies (exact, approximate, parametrized) and retrieval data structures - similarity measures for transformation ensembles- spacial as well as temporal interpolation of elastic patterns.