Accession Number:

ADA459522

Title:

Computational Limitations of Model Based Recognition

Descriptive Note:

Corporate Author:

TEXAS UNIV AT DALLAS RICHARDSON

Report Date:

1991-02-01

Pagination or Media Count:

15.0

Abstract:

Reliable object recognition is an essential part of most visual systems. Model based approaches to object recognition use a database a library of modeled objects for a given set of sensed data the problem of model based recognition is to identify and locate the objects from the library that are present in the data. We show that the complexity of model based recognition depends very heavily on the number of object models in the library even if each object is modeled by a small number of discrete features. Specifically, deciding whether a discrete set of sensed data can be interpreted as transformed object models from a given library is NP-complete if the transformation is any combination of translation, rotation, scaling, and perspective projection. This suggests that efficient algorithms for model based recognition must use additional structure in order to avoid the inherent computational difficulties.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE