129 
The simplicity of this algorithm makes it easy to implement. Besides, it does not require any data pre-processing or local 
feature extraction. This facts allow to handle reasonably noise effects that occur in our range finder system. The algorithm 
converges after a few iterations as showed in (Besl, 1992). Most of the computing time of the algorithm is spent in the closest 
point search part (1) whose cost is O(Np*Ny), when not using optimised searching techniques. The calculation (2) and 
application (3) of the transformation grow both linearly with Np. 
We will now show some experiments to demonstrate the usefulness of the closest point matching algorithm for free form 
object recognition. First, there will be a summary of experiments in the plane with puzzle pieces. Then, we will do a 
systematic investigation of the algorithm in 3-D space using a synthetic object. 
3. EXPERIMENTAL RESULTS IN 2-D SPACE 
We first present experiments in the 2-D space with puzzle pieces in order to better visualise the behaviour of the algorithm in 
two dimensions. The puzzle pieces are acquired with a b/w camera. After a thresholding of the image and the extraction of 
ing the contour we obtain a set of points describing the border of the puzzle piece. Such sets and subsets of puzzle pieces are 
s of fed into the closest point matching algorithm. Figure 1 shows some examples of the matching of puzzles and parts of puzzles 
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
ads placed at different positions and different orientations. The example illustrates the correct matching of a complete piece and 
of a subpart as well as an incorrect match of a subpart. We observe that the test pieces converge in few iterations towards 
gs the model. However, the selection of the starting position becomes crucial to a successful registration. 
e 
1m, 
atic 
da 
gli, test 
ipe : 
| i C h T AAA AR m Oo d e | 
Fig. 1: Matching iterations of puzzle pieces 
inly To get a global view of the influence of translation and rotation we place successively the test piece in several different 
the positions around the original puzzle. Moreover the so placed test piece will be rotated around its center of mass. Figure 2 
ind plots the results for all rotations and sixteen positions arranged in a grid. The black sectors at every grid position indicate the 
ace angles for which the matching has been successful. 
ing 
ect 
a [s 
ble Pes 
his 
on. 
er ® DDD 
O 
z eoe 
en 
the 
= SB DD 
of example 
94) 
the Fig. 2: Convergence zone for a puzzle piece placed and rotated differently 
We observe that the translation between two pieces to be superposed is of minor influence to the convergence. However, if 
the rotation angle between the test and the model piece exceeds a certain value the registration fails. The convergence zone 
for the rotation angle is about between +/- 30 degrees. 
Kn Since the computing time of the closest point matching algorithm grows with O(Nx*Np), we are interested in using as few 
points as possible. Experiments with subsampled data confirmed that good convergence is available for reduction factors up 
to eight, which allows to represent a puzzle border by only 60 points (Hügli, 1994a). 
In object recognition it is important to know if the final distance between two different objects is significantly larger than 
between two representations of the same object. This fact must be satisfied to allow reliable decision. Experiments with 
puzzle pieces of different shapes showed that a threshold can be set for the final distance to separate reliably the object 
classes (Hügli, 1994a). 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences", Zurich, March 22-24 1995