This paper addresses the robust recognition of planar polygonal objects situated in 3D space over highly textured backgrounds, where each object is modeled by a set of "five-lines" projective invariants. The main contributions of this work are the following: the establishment of the discriminative ability of an indexing space based on five-lines invariants, the presentation of a robust mechanism for extracting relevant line segments on which invariants are computed, the use of these invariants for geometric hashing amongst possible objects from the model base, and the verification of hypotheses through a purposive search for missing line segments. Finally, experiments verify that the indexing complexity remains linear when the size of the model base increases linearly. Experiments are presented using a model base of 10 shapes, with about 10 views for each shape acquired from various points of view.