Computational limitations of model-based recognition

Haim Schweitzer, Sanjeev R. Kulkarni

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 to avoid the inherent computational difficulties.

Original languageEnglish (US)
Pages (from-to)431-443
Number of pages13
JournalInternational Journal of Intelligent Systems
Issue number5
StatePublished - May 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Human-Computer Interaction
  • Artificial Intelligence


Dive into the research topics of 'Computational limitations of model-based recognition'. Together they form a unique fingerprint.

Cite this