Local Similarity Based Point-Pattern Matching
Veli Mäkinen and Esko Ukkonen
Department of Computer Science, P.O Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland.
We study local similarity based distance
measures for point-patterns. Such measures
can be used for matching point-patterns under
non-uniform transformations - a problem that
naturally arises in image comparison problems.
A general framework for the matching problem is introduced.
We show that some of the most obvious instances of this framework
lead to NP-hard optimization problems and are not approximable within any
We also give a relaxation of the framework that is
solvable in polynomial time and works
well in practice in our experiments with two-dimensional
protein electrophoresis gel images.