Line-based object recognition using Hausdorff distance: from range images to molecular secondary structures

Object recognition algorithms are fundamental tools in automatic matching of geometric shapes within a background scene. Many approaches have been proposed in the past to solve the object recognition problem. Two of the key aspects that distinguish them in terms of their practical usability are: (i) the type of input model description and (ii) the comparison criteria used. In this paper we introduce a novel scheme for 3D object recognition based on line segment representation of the input shapes and comparison using the Hausdorff distance. This choice of model representation provides the flexibility to apply the scheme in different application areas. We define several variants of the Hausdorff distance to compare the models within the framework of well defined metric spaces. We present a matching algorithm that efficiently finds a pattern in a 3D scene. The algorithm approximates a minimization procedure of the Hausdorff distance. The output error due to the approximation is guaranteed to be within a known constant bound. Practical results are presented for two classes of objects: (i) polyhedral shapes extracted from segmented range images and (ii) secondary structures of large molecules. In both cases the use of our approximate algorithm allows to match correctly the pattern in the background while achieving the efficiency necessary for practical use of the scheme. In particular the performance is improved substantially with minor degradation of the quality of the matching.