Premium
Computational limitations of model‐based recognition
Author(s) -
Schweitzer Haim,
Kulkarni Sanjeev R.
Publication year - 1998
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/(sici)1098-111x(199805)13:5<431::aid-int4>3.0.co;2-n
Subject(s) - computer science , 3d single object recognition , cognitive neuroscience of visual object recognition , object (grammar) , artificial intelligence , rotation (mathematics) , translation (biology) , projection (relational algebra) , set (abstract data type) , transformation (genetics) , object model , perspective (graphical) , pattern recognition (psychology) , computational complexity theory , machine learning , data mining , algorithm , biochemistry , chemistry , messenger rna , gene , programming language
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. © 1998 John Wiley & Sons, Inc.