Computational limitations of model-based recognition

✍ Scribed by Haim Schweitzer; Sanjeev R. Kulkarni

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 136 KB
• Volume: 13
• Category: Article
• ISSN: 0884-8173
• DOI: 10.1002/(sici)1098-111x(199805)13:5<431::aid-int4>3.0.co;2-n

✦ Synopsis

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.