A. Mosig,
Matching Polygonal Curves using Group Theory,
Poster presented
at the NATO Advanced Study on Computational Noncommutative Algebra and
Applications, Tuscany, Italy, 2003.
Methods for matching geometric patterns have been studied extensively
in the past years, including their apllications ranging from machine
vision and image databases to computational chemistry and drug
design. In our poster we propose a method for matching polygonal
curves in two dimensions. As a measure of similarity, we use the
Frechet distance, which is based on certain optimal reparametrizations
of the curves. We consider the case that the curves can be
transformed by the group of rigid motions or the group generated by
uniform scalings and translations.
Our poster gives an overview of the different steps leading to an
efficient matching algorithm. As a first step, we provide results on
discretizing the set of reparametrizations to be examined. This
discretization result is the basis of our approximate matching
algorithm that models the set of all possible reparametrizations as an
acyclic digraph. Each edge is then assigned a certain transporter
subset of the transformation group. Finding a path from the graph's
source to the sink with the property that the intersection of the
transporter subsets along the path's edges is non-empty finally
solves the matching problem. In order to solve this intersection
problem efficiently, we propose a method that simplifies the
transporters to be intersected. Furthermore, we present visualizations
of the transformation groups' transporter subsets and their
intersections as well as relations to other pattern matching problems.