The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Pagination or Media Count:
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 isgood 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.