Searching geometric libraries using generalized ε-congruence
Jonathan B. Phillips · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
In computer vision, one of the major problems is how to identify an observed object in an image by comparing it to a set of models in a library. The comparison is made using a shape metric which measures the similarity between different shapes. The observed object is classified as the library object with which it minimizes the shape metric. This paper looks at algorithms for efficiently searching a geometric library to identify an observed object in the image. All objects are modeled as points and (epsilon) -congruence is used as the shape metric. Algorithms are presented for searching two classes of geometric libraries, ordered linear libraries and convex linear libraries. The complexity of the algorithms is expressed in terms of the number of objects in the library, the size of the objects, the error in the optimal match, and the geometric structure.