Pattern matching using similarity measures

Michiel Hagedoorn
Max-Planck-Institut fur Informatik, Saarbrucken, Germany
Consider the following problems:
  1. 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.
  2. 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.