Point set pattern matching using the Procrustean metric

Jonathan Phillips

doi:10.1117/12.179249

8 July 1994 Point set pattern matching using the Procrustean metric

Jonathan Phillips

Proceedings Volume 2299, Mathematical Methods in Medical Imaging III; (1994) https://doi.org/10.1117/12.179249
Event: SPIE's 1994 International Symposium on Optics, Imaging, and Instrumentation, 1994, San Diego, CA, United States

Abstract

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.

Citation Download Citation

Jonathan Phillips "Point set pattern matching using the Procrustean metric", Proc. SPIE 2299, Mathematical Methods in Medical Imaging III, (8 July 1994); https://doi.org/10.1117/12.179249

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available