A NEW ALGORITHM FOR 
3D SURFACE MATCHING 
D. Akca 
Institute of Geodesy and Photogrammetry, Swiss Federal Institute of Technology (ETH) Zurich 
ETH Hoenggerberg, CH-8093 Zurich, Switzerland. E-mail: devrim.akca@geod.baug.ethz.ch 
KEY WORDS: Surface matching, Least Squares Matching, Point clouds, Registration, Laser scanning. 
ABSTRACT: 
A new algorithm for least squares matching of overlapping 3D 
device, the photogrammetric method or other techniques, 
matching and its solution method was first addressed by Gruen 
have been some studies on the 
known as DEM matching. Furthermore 
mathematically with least squares image matching. 
proposed method estimates the transformation parameters between two or more 
distances instead of Z-differences between the surfaces by least squares. 
arbitrarily oriented surface patches. An observation equation is written for each surface eleme 
each sampled point. The geometric relationship between the conjugz 
transformation. The Least Squares observations of the adjustment are 
Euclidean distances between the template and search surface elements. The 
1e functional model gives control over the estimation parameters. The 
1e convergence behavior, and statistical analysis of the theoretical 
e, some experimental results based on registration of close-range 
stochastic quantities using proper weights. This extension of tl 
details of the mathematical modelling of the proposed method, tl 
precision of the estimated parameters are explained. Furthermor 
laser scanner and photogrammetric point clouds are presented. 
strength from the least squares image matching concept and offers 
absolute orientation of stereo models using DEMs as control inform 
. techniques for 2.5D DEM surface matching have been developed, which correspond 
2.5D surfaces have limited value, especially in close range applications. Our 
surfaces, digitized/sampled point by point using a laser scanner 
is proposed. In photogrammetry, the problem statement of surface patch 
(1985a) as a straight application of Least Squares Matching. There 
ation. These works have been 
fully 3D surface patches, minimizing the Euclidean 
This formulation gives the opportunity of matching 
nt on the template surface patch, i.e. for 
ate surface patches is defined as a 7-parameter 3D similarity 
defined by the observation vector whose elements are 
unknown transformation parameters are treated as 
This new surface matching technique derives its mathematical 
high level flexibility for any kind of 3D surface correspondence 
problem, as well as statistical tools for the analysis of the quality of the final results. 
1. INTRODUCTION 
Laser scanners can measure directly 3D coordinates of huge 
amounts of points in a short time period. Since the laser scanner 
is a line-of-sight instrument, in many cases the object has to be 
scanned from different viewpoints in order to completely 
reconstruct it. Because each scan has its own local coordinate 
system, all the local point clouds must be transformed into a 
common coordinate system. This procedure is usually referred 
to as registration. Actually the registration is not a specific 
problem to the laser scanner domain. Since the problem is more 
general than the given definition, the emphasis of our work is to 
investigate the most general solution of the registration problem 
on a theoretical basis. 
In the past, several efforts have been made concerning the 
registration of 3D point clouds, especially in the Computer 
Vision area. One of the most popular methods is the Iterative 
Closest Point (ICP) algorithm developed by Besl and McKay 
(1992), Chen and Medioni (1992), and Zhang (1994). The ICP 
is based on the search of pairs of nearest points in the two sets, 
and estimating the rigid transformation, which aligns them. 
Then, the rigid transformation is applied to the points of one 
set, and the procedure is iterated until convergence. The ICP 
assumes that one point set is a subset of the other. When this 
assumption is not valid, false matches are created, that 
negatively influence the convergence of the ICP to the correct 
solution (Fusiello et al, 2002). Several variations and 
improvements of the ICP method have been made (Masuda and 
Yokoya, 1995, Bergevin et al., 1996), but several problems still 
remain. From a computational expense point of view it is highly 
time consuming due to the exhaustive search for the nearest 
point (Sequeira, et al., 1999). Another problem is that it 
requires every point in one surface to have a corresponding 
point on the other surface. An alternative approach to this 
search problem was proposed by Chen and Medioni (1992). 
They used the distance between the surfaces in the direction 
normal to the first surface as a registration evaluation function 
instead of point-to-nearest point distance. This idea was 
originally proposed by Potmesil (1983). In (Dorai et al., 1997) 
the method of Chen and Medioni was extended to an optimal 
weighted least-squares framework. Zhang (1994) proposed a 
thresholding technique using robust statistics to limit the 
maximum distance between points. Masuda and Yokoya (1995) 
used the ICP with random sampling and least median square 
error measurement that is robust to a partially overlapping 
scene. Okatani and Deguchi (2002) propose the best 
transformation of two range images to align each other by 
taking into account the measurement error properties, which are 
mainly dependent on both the viewing direction and the 
distance to the object surface. The ICP algorithm always 
converges monotonically to a local minimum with respect to the 
mean-square distance objective function (Besl and McKay, 
1992). Even if good initial approximations for the 
transformation parameters are provided, in some cases it might 
converge to a wrong solution due to its closest point (or tangent 
plane) search scheme. It does not use the local surface gradients 
in order to direct the solution to a global minimum. Another 
deficiency of the ICP method is to be not able to handle multi- 
scale range data. Several reviews and comparison studies about 
the ICP variant methods are available in the literature (Jokinen 
and Haggren, 1998, Williams et al., 1999, Campbell and Flynn, 
2001). 
Since 3D point clouds derived by any method or device 
represent the object surface, the problem should be defined as à 
surface matching problem. In Photogrammetry, the problem 
statement of surface patch matching and its solut 
was first addressed by Gruen (1985a) as a straight extension ol 
Least Squares Matching (LSM). 
960 
ion method 
al 
an 
ma 
par 
3D 
lase 
sur] 
finc 
esta 
Our 
(LS 
two 
dist 
forn 
orie 
fo I 
eacl 
conj 
simi