Fast algorithm for point pattern matching: Invariant to translations, rotations and scale changes

Based on 2-D cluster approach, a fast algorithm for point pattern matching is proposed to effectively solve the problems of optimal matches between two point pattern under geometrical transformation and correctly identify the missing or spurious points of patterns. Theorems and algorithms are developed to determine the matching pairs support of each point pair and its transformation parameters (scaling s and rotation theta) on a two-parameter space (s,theta). Experiments are conducted both on real and synthetic data. The experimental results show that the proposed matching algorithm can handle translation, rotation, and scaling differences under noisy or distorted condition. The computational time is just about 0.5 a for 50 to 50 point matching on Sun-4 workstation. Copyright (C) 1997 Pattern Recognition Society.