{vmakinen,ukkonen}@cs.Helsinki.FI Department of Computer Science, P.O Box 26 (Teollisuuskatu 23) FIN-00014 University of Helsinki, Finland.
Abstract.
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
constant factor.
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.