Indexing without invariants in 3D object recognition

We present a method of indexing three-dimensional objects from single two-d imensional images. Unlike most other methods to solve this problem, ours do es not rely on invariant features. This allows a richer set of shape inform ation to be used in the recognition process. We also suggest the kd-tree as an alternative indexing data structure to the standard hash table. This ma kes hypothesis recovery more efficient in high-dimensional spaces, which ar e necessary to achieve specificity in large model databases. Search efficie ncy is maintained in these regimes by the use of Best-Bin First search, a m odified kd-tree search algorithm which locates approximate nearest-neighbor s. Neighbors recovered from the index are used to generate probability esti mates, local within the feature space, which are then used to rank hypothes es for verification. On average, the ranking process greatly reduces the nu mber of verifications required. Our approach is general in that it can be a pplied to any real-valued feature vector. In addition, it is straightforwar d to add to our index information from real images regarding the true proba bility distributions of the feature groupings used for indexing. In this pa per, we provide experiments with both synthetic and real images, as well as details of the practical implementation of our system, which has been appl ied in the domain of telerobotics.