STRUCTURAL INDEXING - EFFICIENT 2-D OBJECT RECOGNITION

We address the problem of recognition of multiple flat objects in a cluttered environment from an arbitrary viewpoint. The models are acquired automatically and approximated by polygons with multiple line tolerances for robustness. Groups of consecutive segments (super segments) are then encoded and entered into a table. This provides the essential mechanism for indexing and fast retrieval. Once the database of all models is built, the recognition proceeds by segmenting the scene into a polygonal approximation; the code for each super segment retrieves model hypotheses from the table. Hypotheses are clustered if they are mutually consistent and represent the instance of a model. Finally, the estimate of the transformation is refined. This methodology allows us to recognize models in the presence of noise, occlusion, scale, rotation, translation, and a restricted range of weak perspective. We show that the complexity can be bounded by O(n) less-than-or-equal-to O(recognition) less-than-or-equal-to O(n2 . m3), where n is the number of features in the scene, and m is the number of models in the database.