Labeled point pattern matching by Delaunay triangulation and maximal cliques

摘要

In many problems of pattern recognition, objects in an image may be efficiently represented by a set of labeled points. This paper describes a method for matching labeled point patterns with one of the prototypes. The Delaunay triangulation is used to partition a point pattern into a set of triangles, and the largest maximal clique of the consistency graph for each triangle is used to obtain the largest set of mutually consistent point pairs. The proposed method is invariant under affine transformation of point patterns, and allows for additions and deletions of points and some random perturbations in their relative locations. The method is applied to the matching of constellations.