Accession Number:

ADA196224

Title:

The Combinatorics of Object Recognition in Cluttered Environments Using Constrained Search

Descriptive Note:

Memorandum rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s):

Report Date:

1988-02-01

Pagination or Media Count:

43.0

Abstract:

The problem of recognizing rigid objects from noisy sensory data has been successfully attacked in previous work by using a constrained search approach. Empirical investigations have shown the method to be very effective when recognizing and localizing isolated objects, but less effective when dealing with occluded objects where much of the sensory data arises from objects other than the one of interest. When clustering techniques such as the Hough transform are used to isolate likely subspaces of the search space, empirical performance in cluttered scenes improves considerably. This note establishes formal bounds on the combinatorics of this approach. Under some simple assumptions, the expected complexity of recognizing isolated objects is quadratic in the number of model and sensory fragments, but the expected complexity of recognizing objects in cluttered environments is exponential in the size of the correct interpretation. Formal bounds are provided on the efficacy of using the Hough transform to preselect likely subspaces, showing that problem remains exponential, but that in practical terms, the size of the problem is significantly decreased. Keywords Object recognition, Hough transform, Combinatoric complexity, Image processing.

Subject Categories:

  • Computer Programming and Software
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE