Object recognition by geometric hashing

Candidate: Lamdan,Yehezkel

Abstract

This thesis proposes a general and efficient model-based object recognition scheme. The scheme addresses the problem of identifying instances of model objects in single images. The model objects are two or three dimensional, and their instances in the scene might be overlapping and partially occluded by other unknown objects. The camera viewpoint is unknown and assumed to be arbitrary. The images can be two dimensional intensity images or three dimensional range images. The scheme deals uniformly with all feasible imaging transformations, from the simplest case of pure translation to the most complex case of the perspective transformation. The proposed method is based on geometric hashing. It hypothesizes model to scene transformations based on corresponding model and scene feature subsets. These subsets have the minimal cardinality, which still allow to recover the imaging transformation for a given transformation type. In order to prune the search space of all model and scene feature subset pairs, a hashing scheme is used. It is based on geometrical relations among the object features, which are invariant under the given transformation type. The recognition algorithm has two major steps. First, a hash-table, encoding the geometrical invariants of the model features, is prepared. This stage is independent of the scenes to be later processed, and can be executed off-line. In the second stage, an efficient matching algorithm is performed, which utilizes the previously prepared hash-table. The efficacy of the recognition is achieved by considering only those model and scene subsets, which are 'similar' under the given transformation type. The algorithm was tested in 'real-life' situations for the important cases of recognizing flat and solid objects in the 3D world, using the weak perspective approximation to the perspective transformation.