The Effect of Indexing on the Complexity of Object Recognition
Abstract
Many current recognition systems use constrained search to locate objects in cluttered environments. Previous formal analysis has shown that the expected amount of search is quadratic in the number of model and data features, if all the data is known to come from a single object, but is exponential when spurious data is included. If one can group the data into subsets likely to have come from a single object, then terminating the search one a 'good enough' interpretation is found reduces the expected search to cubic. Without successful grouping, terminated search is still exponential. These results apply to finding instances of a known object in the data. In this paper, we turn to the problem of selecting models from a library, and examine the combinatorics of determining that a candidate object is not present in the data. We show that the expected search is again exponential, implying that naive approaches to indexing are likely to carry an expensive overhead, since an exponential amount of work is needed to weed out each of the incorrect models. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1990
- Accession Number
- ADA225761
Entities
People
- L. Grimson
- W. Eric
Organizations
- Massachusetts Institute of Technology