Computational Limitations of Model Based Recognition

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1991
Accession Number
ADA459522

Entities

People

  • Haim Shvaytser
  • Sanjeev R. Kulkarni

Organizations

  • University of Texas at Dallas

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Air Force
  • Computer Vision
  • Controlled Environment
  • Coordinate Systems
  • Equations
  • Identification
  • Information Operations
  • Information Processing
  • Military Research
  • Object Recognition
  • Polynomials
  • Recognition
  • Rotation
  • Standards
  • Translations
  • Vascular System Injuries

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Image Processing and Computer Vision.
  • Neural Network Machine Learning.