Polyhedra recognition by hypothesis accumulation

A new method is presented for the recognition of polyhedra in range data. The method is based on a hypothesis accumulation scheme which allows parallel implementations. The different objects to be recognized are modeled by a set of local geometrical patterns. Local patterns of the same nature are extracted from the scene. For the recognition of an object, local scene and model patterns having the same geometrical characteristics are matched. For each of the possible matches, the geometric transformations (i.e., rotations and translations) are computed, which allows the overlapping of the model elements with those from the scene. This transformation permits the establishment of a hypothesis on the location of the object in the scene and the determination of a point in the transformation space. The presence of an object similar to a model involves the generation of several compatible hypotheses and creates a compact cluster in the transformation space. The recognition of the object is based on the detection of this cluster. The cluster coordinates give the values of the rotations and the translations to be applied to the model such that it corresponds to the object in the scene. The exact location of this object is given by the transformed model.