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.