The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments
Abstract
Many current recognition systems use constrained search to locate objects in cluttered environments. Earlier analysis of one class of methods has shown that the expected amount of search is quadratic in the number of model and date features, if all the data is known to come from a single object, but is exponential when spurious data is included. To overcome this, many methods terminate search once an interpretation that is'good enough' is found. This paper formally examines the combinations of this approach, showing that choosing correct termination procedures can dramatically reduce the search. In particular, conditions are provided for the object model and the scene clutter such that the expected search is polynomial. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA209690
Entities
People
- W. E. Grimson
Organizations
- Massachusetts Institute of Technology