Polyhedral Representation and Adjacency Graph in n-dimensional Digital Images

This paper addresses the problem of recognizing 3D objects from 2D intensity images. It describes the object recognition system named RIO (relational indexing of objects), which contains a number of new techniques. RIO begins with an edge image obtained from a pair of intensity images taken with a single camera and two different lightings. From the edge image, a set of new high-level features and relationships are extracted, and a technique called relational indexing is used to efficiently recall 2D view-class object models that have similar relational descriptions from a potentially large database of models. Once a model has been hypothesized, pairs of 2D-3D corresponding features, including point pairs, line-segment pairs, and ellipse-circle pairs, are used in a new linear pose estimation framework to produce a hypothesized transformation from a 3D mesh model of the object to the image. The transformation is either accepted or rejected by a verification procedure that projects the 3D model wireframe to the image and computes a Hausdorff-like distance measure between the projected model and the edge image. The resultant object recognition system is able to recognize 3D objects having planar, cylindrical, and threaded surfaces in complex, multiobject scenes.