Measuring similarity between polygonal shapes is an important problem in pattern recognition and machine intelligence. Often, the recognition is done by attracting a set of features that represent an unknown object and comparing this set with sets of features extracted from objects of known identification (prototypes). The prototype that is closest to the unknown object, when measured in a suitable metric, is assigned as the label for the unknown object. We consider the problem of comparing polygonal shapes based on their `annular profiles.' We show that the annular profile of a polygon Q of n sides induced by a given placement of an annular panel of size k can be computed in O(log k + W) time when Q is simple and in O(n log k + W) time when Q has holes. We show that profile query problem (PQP) can be answered in O(log n) time, given O(n) space and O(n²) pre-processing time. By relating the Voronoi diagrams of the edges and vertices of Q, we prove that all non-simple panels of Q can be computed in (Omega) (n⁵) time. We conclude by discussing the problem of constructing polygon from its annular profiles.

Date Published: 4 January 1995
PDF: 11 pages
Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198604

Published in SPIE Proceedings Vol. 2356:
Vision Geometry III
Robert A. Melter; Angela Y. Wu, Editor(s)