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 R¹, translations in R², and combined translations and rotations in R². 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.

Date Published: 8 July 1994
PDF: 12 pages
Proc. SPIE 2299, Mathematical Methods in Medical Imaging III, (8 July 1994); doi: 10.1117/12.179249

Published in SPIE Proceedings Vol. 2299:
Mathematical Methods in Medical Imaging III
Fred L. Bookstein; James S. Duncan; Nicholas Lange; David C. Wilson, Editor(s)