The two factors that determine the time complexity associated with model-driven interpretation of range maps are: I) the particular strategy used for the generation of object hypotheses; and 2) the manner in which both the model and the sensed data are organized, data organization being a primary determinant of the efficiency of verification of a given hypothesis. In this report, we present 3D-POLY, a working system for recognizing objects in the presence of occlusion and against cluttered backgrounds. The time complexity of this system is only O(n2) for single object recognition, where n is the number of features on the object. The most novel aspect of this system is the manner in which the feature data are organized for the models. We use a data structure called the feature sphere for the purpose. We will present efficient algorithms for assigning a feature to its proper place on a feature sphere, and for extracting the neighbors of a given feature from the feature sphere representation. For hypothesis generation, we use local feature sets, a notion similar to those used before us by Bolles, Shirai and others. The combination of the feature sphere idea for streamlining verification and the local feature sets for hypothesis generation results in a system whose time complexity has a polynomial bound. In addition to recognizing objects in occluded environments, 3D-POLY also possesses model learning capability. Model learning consists of looking at a model object from different views and integrating the resulting information. The 3D-POLY system also contains utilities for range image segmentation and classification of scene surfaces.

Date of this Version