Accession Number:

ADA209690

Title:

The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments

Descriptive Note:

Memorandum rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s):

Report Date:

1989-05-01

Pagination or Media Count:

32.0

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 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.

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE