UAL 
alia 
n a very 
nethods. 
?Cessary 
Existing 
. priori 
t clouds 
ndence. 
ture and 
possible 
and two 
C2 and 
nt cloud 
and nor- 
rely. Let 
nt cloud 
ponding 
e briefly 
tinc. 
lgorithm 
yuds and 
possible 
mes and 
   
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
Another algorithm is Chen and Medioni's that is a point- 
to-surface algorithm whereas the ICP is a point-to-point al- 
gorithm (Chen and Medioni, 1992). It minimises the sum 
of the square distances of a point to its corresponding sur- 
face. This algorithm is generally faster than the ICP. How- 
ever, the point clouds need to be more closely aligned to 
each other initially than with the ICP. 
The ICP, its variants, and Chen and Medioni’s algorithm 
assume that the closest point in point cloud C? is a good 
estimate of the correct corresponding point in Ci. If two 
point clouds are not approximately aligned using a pri- 
ori georeferencing information, this assumption is not cor- 
rect. Although initial alignment can be provided from 
other means like surveying of the laser scanner locations, it 
is not always possible. Finding corresponding points and 
good registration of the point clouds are more difficult if 
they only partially overlap. In addition, these adjustment 
algorithms provides a closed-form solution, i.e. no itera- 
tion, which is one of reasons for their popularity, although 
closed-form methods can not provide statistical informa- 
tion of individual parameter of rigidbody transformation 
as conventional least square methods do. 
2 PROPOSED METHOD 
Geometric primitives, such as surface normal vector, cur- 
vature, and the change of curvature and so on, may provide 
additional and useful information to recover the correspon- 
dence of two point clouds. A method to find the correspon- 
dence of two point clouds using geometric primitives and 
a local search algorithm is proposed. Geometric curvature 
and the change of curvature is invariant to three dimen- 
sional rigid motion and surface normal vector can be ro- 
tated according to the computed transformation by Horn's 
or Chen and Medioni's algorithm. The angle between nor- 
mal vectors and the difference between the changes of cur- 
vature of a point and its corresponding points are our crite- 
ria for selection of corresponding point pair. 
The angle between approximate normal vectors of pl and 
p; can be expressed as 
oni 
Ü (pip?) = cos” (ny, nz). (1) 
where n,: and n, are the respective approximate normal 
i J 
vectors of the points. The difference in changes of curva- 
ture between two points can be written 
B(p; : pj) = |Mec(P; ) - M« (DIN: ©) 
where M,.(pl) and M. (p?) are the approximate changes 
of curvature of p? and pj. The normal vector of a point is 
estimated by covariance analysis of the point and its neigh- 
bourhood points and the change of curvature is estimated 
as the ratio of'eigenvalues of the covariance matrix. 
2.1 Normal vector estimation 
The normal vector of a point is estimated by one of the 
eigenvectors of the covariance matrix of a point and its 
22 
neighbourhood. The covariance of a point and its k neigh- 
bour points, COV (p}), is expressed as 
1 
FOOL nm PHP cent T 
COY (Di ) a k (Pj Pneighbour{j=1---k,p! } ) 
1 cent ia 
(bi E Pnoighbour{j= kpl} ) (3) 
= cent : d : T. bs . 
where CR the cetroid of p; and its k 
neighbourhood points. COV (pl) is a 3 x 3, real, pos- 
itive, and semi-definite matrix, the eigenvalues of which 
are always greater than or equal to zero. The eigenvec- 
tor of the minimum eigenvalue is the approximate normal 
vector of the surface formed by p] and its k neighbour- 
hood points (Hoppe et al., 1992). The other eigenvectors 
are the tangential vectors of the surface. If the minimum 
eigenvalue is close to zero, then the surface consisting of 
a point and its neighbourhood is flat. This method is the 
first order approximation of the normal vectors of the sur- 
face. If the level of noise is large or the number of points 
in the neighbourhood, k, is too small, it could provide an 
incorrect normal vector. 
2.2 Change of geometric curvature estimation 
The change of geometric curvature at a point can be esti- 
mated from the eigenvalues of the covariance matrix. Each 
eigenvalue represents the spatial variations along the direc- 
tion of the eigenvector. Let A; and rv; be the eigenvalues 
and eigenvectors of the covariance matrix, COV (p}), with 
the condition of 4; X A9 X As. The change of curva- 
ture is a parameter of how much the surface formed by a 
point and its neighbourhood deviates from the tangential 
plane formed by vs and v3. The ratio of the minimum 
eigenvalue and the sum of the eigenvalues approximates 
the change of geometric curvature, 
Mec(pi) = CE (4) 
Sd ^i 
Additionally, the geometric curvature, Miu, (pl), of a 
point can be estimated by the normal vectors of the point 
and its neighbourhood 
k 
I'~— : 
Meurulpi) = L s |n, E Uneighbour{j.p! } |] (5) 
= 
where n,: and n are the normal vectors of 
neighbour (3,pl 
pl and its jth neighbourhood, (Linsen, 2001). The change 
of curvature, M...(p}), can be expressed 
k 
1 Ader | 
Mec (pi) mm k NS | Murs (pi) a Muro  hetghbeurtint } ) | . 
j=1 
(6) 
Both methods can provide a good approximation to the 
change of curvature. However, the quality of estimation 
depends on how well the neighbourhood points are dis- 
tributed. Since our algorithm is for the registration of unor- 
ganised point clouds, there is no guarantee that every point