Translator Disclaimer
8 July 1994 Point set pattern matching using the Procrustean metric
Author Affiliations +
A fundamental problem in computer vision is to determine if an approximate version of a geometric pattern P occurs in an observed set of points B. The pattern and the background are modeled as point sets Pequals{p$1,....,p$m} and Bequals{b$1,....,b$n} on the line or in the plane. We wish to find a transformation T, from a family of transformations , such that the distance between T(P) and B is minimized. The distance between T(P) and B is the sum of the distances squared between T(p$i) and the closest point in B. This is the Procrustean metric where the set of allowable mappings between P and B is the space F of all functions from P into B. The algorithms in this paper also apply when the metric is the sum of the distances between points in P and B. We present algorithms that minimize the Procrustean metric for the following families of transformations: translations in R1, translations in R2, and combined translations and rotations in R2. We prove that fixed point algorithms for computing the Procrustean metric converge to a fixed point and show a worst case lower bound on the number of fixed points.
© (1994) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jonathan Phillips "Point set pattern matching using the Procrustean metric", Proc. SPIE 2299, Mathematical Methods in Medical Imaging III, (8 July 1994);

Back to Top