Pattern matching using similarity measures
Michiel Hagedoorn
Max-Planck-Institut fur Informatik, Saarbrucken, Germany
Consider the following problems:
- We have two geometric patterns, and we want to find a transformation
(for example, translation, scaling & rotation) under which the two
patterns are most similar.
- We have a database of geometric patterns, and given some query
pattern we want to find a database pattern that is most similar to
the query pattern.
Problems 1 and 2 come up in applications such as image alignment and
content-based image retrieval, respectively.
In both problems, we can use a _similarity measure_ to model the
notion of similarity.
In my talk, I formalize nice-to-have properties for similarity measures
such as invariance under geometric transformations and robustness for
deformations, blurring, cracks, and noise. I discuss existing similarity
measures, including the Hausdorff metric. In addition, I introduce new
similarity measures that are well suited for patterns that are obtained
by image segmentation or edge detection. Finally, I address algorithmic
aspects of pattern matching using similarity measures.