128 
RECOGNITION OF 3-D OBJECTS WITH A CLOSEST POINT MATCHING ALGORITHM 
Ch. Schütz and H. Hügli, University of Neuchätel 
Tivoli 28, 2000 Neuchätel, Switzerland 
Phone: ++41 38 30 16 53 
Fax: ++41 38 30 18 45 
Email: schutz@imt.unine.ch 
KEY WORDS: 3-D free form object recognition, pose estimation, range imaging. 
ABSTRACT: 
This paper is a contribution to the recognition of arbitrary 3-D shapes from range images. Recently, a closest point matching 
algorithm was proposed that is in a position to match 3-D shapes without the need of an explicit object description in terms of 
primitives. The advantage is that the comparison works directly on the 3-D coordinates of the surface points and needs 
neither segmentation nor feature extraction. Arbitrary shapes can potentially be matched with it. 
In this paper we present a number of 3-D object recognition experiments conducted for assessing the capability of this 
approach to recognise objects measured by range images. The experiments performed with the designed methods show the 
fast convergence and reliable recognition of objects. We also address some of the key issues of this matching algorithm, 
which are the strong dependence on the initial conditions, like position of the object to be recognised, and the quadratic 
computing complexity. 
1. INTRODUCTION 
The work described in this paper was carried out in the context of knowledge based 3-D object recognition. We developed a 
hybrid recognition system, which combines range and intensity images to generate and verify object hypothesises (Hügli, 
1994b). The range images are acquired with a range finder working on the principle of space coding with projected stripe 
pattern and triangulation. One application of our vision system is to recognise known objects in a robot environment, which 
permits to update a virtual representation of the robots workspace (Natonek, 1995). 
In our system the model and test objects are represented by a set of 3-D points, called a dense 3-D map. There exist mainly 
two approaches for geometricly matching dense 3-D maps (Zhang, 1994). The first one is based on the description of the 
dense 3-D map in terms of geometric primitives. Primitives of the model and the test are organised in a graph structure and 
mapped one onto the other with a graph matching method. The second approach considers the dense 3-D map as a surface 
and tries to find a transformation between the model and the test. The primitive-based approach exploits symbolic matching 
criteria and allows important changes in orientation and positioning between model and test, usually essential in object 
recognition. Unfortunately this approach depends largely on a robust and precise detection of primitives which remains a 
problem with current known methods (Zhang, 1994) (Maitre, 1994). In contrast the surface-based approach uses all available 
information and does not need data segmentation. It can be easily applied to free form objects. The techniques for this 
approach usually need a priori knowledge of the transformation between test and model to perform a successful recognition. 
This approach has been used in visual navigation (Zhang, 1994) and object modelling (Chen, 1992) where motions between 
two surfaces to match are small while the primitive-based approach has been widely applied in object recognition. 
Recently, an interesting technique for the registration of dense 3-D maps has been proposed (Besl, 1992). It uses a surface- 
based approach and needs, as one would expect, a priori knowledge to give a rough estimate of the transformation between 
the test and model object. Closest points between the two surfaces to match are coupled and used to calculate the 
transformation, which minimises the mean square error of the distances. The test object is then moved and rotated by the 
resulting transformation. This procedure is applied several times until the error falls below a threshold or the number of 
iteration exceeds a predefined constant. Other researchers have used similar algorithms (Zhang, 1994) (Feldmar, 1994) 
(Chen, 1992) to estimate motions, register surfaces and build models. We show some experiments to investigate the 
usefulness of the closest point matching algorithm for the recognition of objects measured by range images. 
2. CLOSEST POINT MATCHING ALGORITHM 
The algorithm, we use, was proposed in (Besl, 1992). It aims to find the transformation consisting of rotation R and translation 
t between two dense 3-D maps, referred as a model X and a test P. X and P are represented by their coordinates in space. 
Here follows a short description of the algorithm. 
* input: Two dense 3-D maps X and P containing respectively Nx and Np 3-D points. 
* output: Transformation (R, t) between X and P found by the algorithm. 
* iteration: 
(1) Build the set Qj of closest point pairs with q - (p, x): V p e Pjfind x e X with Ilp - xll 2 min(Ilp - xj), / e [1, ..., Nx ]. 
(2) Find the transformation (Rj, t) that minimises the mean square error e£Rj tj)-1/Np-XIIR; pk t; - xdl? 
with (pk, Xk) = qk, using the quaternion method (Faugeras, 1986). 
(3) Apply the transformation, Pj,1 = (R; t)(P). 
until e; is below a threshold c or /is greater than a limit p. 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences", Zurich, March 22-24 1995