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.

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.