TY - JOUR
T1 - Computational limitations of model-based recognition
AU - Schweitzer, Haim
AU - Kulkarni, Sanjeev R.
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1998/5
Y1 - 1998/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0032069776&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032069776&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1098-111X(199805)13:5<431::AID-INT4>3.0.CO;2-N
DO - 10.1002/(SICI)1098-111X(199805)13:5<431::AID-INT4>3.0.CO;2-N
M3 - Article
AN - SCOPUS:0032069776
VL - 13
SP - 431
EP - 443
JO - International Journal of Intelligent Systems
JF - International Journal of Intelligent Systems
SN - 0884-8173
IS - 5
ER -