«1 2004
stance
(n and
uickly
ds are
erwise
only a
erwise
der to
? opti-
luated
regis-
Stance
nota
stribu-
sumed
lers in
Iber of
corre-
lly as-
ble in
? error
lla and
ameter
nding
idence
ctor in
(7)
he Ath
corre-
imples
nding
ne-to-
zreater
uld be
nethod
impor-
1es are
od, al-
1 Ibis
ial val-
work-
ons for
l from
(8)
(9)
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
threshold description
k number of neighbourhood
piter=0 a
n initial sampling threshold
for the change of curvature
TEN initial threshold for the difference
in changes of curvature
miter=0
SE al initial threshold for the angle
between normal vectors
Ap A Se Tuter=k
AT ample increment for Ir
ANT. increment for T2t67—^
AT innro | iter de
INI or mal increment for 777777
d CM threshold for starting Chen and Medioni's method
Te threshold for stopping the registration
Table 1: The threshold values are used in the propose
method.
where « M. > and « Mj, »,,,, are the mean and rms
of the change of curvature of C".
3 EXPERIMENTAL RESULTS
Three examples were tested with the proposed method:
a simulated point cloud and two real point clouds cap-
tured with two different laser scanners. All datasets have
partially overlapped. The proposed method was imple-
mented in C++ and tested on a PC with Intel Pentium III
450MHz and 516MB RAM. Our program is not yet opti-
mized so there is room for improvement in terms of pro-
cessing speed. For neighbourhood search, we used a kd-
tree search library developed by Arya ct al. (1998) and
LAPACK (1999) was used for covariance analysis.
3.1 Simulated data
Figure 1: Before the registration of the point clouds of the
parts of a cube
The simulated point clouds are parts of a cube, having di-
mensions of [mx mx Im, and partially overlapped. The
number of points in the point clouds are 2640 and 4048.
One point cloud was translated with (x,y,z)=(0.2m, 0.1m,
0.5m) and rotated 30° around z-axis from registered state
as shown in Figure 1. Zero-mean Gaussian noise with var-
ious standard deviations was added independently to each
point of the point clouds. In the case of zero standard de-
viation, i.e. no noise, all points in the overlapping region
have exact corresponding points.
Many different error metrics have been defined to mea-
sure how well two point clouds are registered (Simon,
2
1996, Maas, 2000, Rusinkiewicz and Levoy, 2001). These
include the change of rotation angles or translation, the
distances between corresponding points, the distances be-
tween points and their corresponding surfaces, and so on.
Whether the registration error, e, is reasonable, too opti-
mistic or pessimistic, depends mainly on the number of
outliers that are used to register the point clouds. In addi-
tion, the redundancy of correspondence, the spatial density
of data and the percentage of the overlapping regions are
important factors. Two parameters that represent the er-
ror of registration were measured: the distances between
corresponding points and the distances of points from their
corresponding surfaces. Figure 2 shows these measures
for the simulated dataset. As expected, more iterations
are needed in order to minimise registration error, as more
noise is added to the point clouds. The magnitude of the
distances between corresponding points is about four times
greater than the distances between points and their corre-
sponding surfaces. [t means that the success rate to find the
correct point-to-point correspondence is much smaller than
that to find the correct point-to-surface correspondence.
This is not surprise if we consider that the test point clouds
are parts of a cube, i.e. most of overlapping regions of the
point clouds possess low curvature area. Therefore, we use
the distance between point and its corrésponding surface as
the error metric of our method. Although we use this as er-
ror metric, the distance between corresponding points will
still provide good information to increase the efficiency of
our algorithm since we may remove outliers based on that
information.
The scales of selected corresponding points in each itera-
tion of the registration of simulated point clouds with var-
ious standard deviations of zero-mean Gaussian noise are
shown in Figure 3. In early stage of registration, scales are
much greater than unity since we do not have good a priori
alignment. After about five iterations, all scales of the dif-
ferent levels of noise become approximately unity, which
is a good indication of success in finding correspondences.
However, there are some differences between the scales in
the presence of noise as shown in Figure 3(b).
3.2 Real point clouds
The second example is the registration of two real
point clouds from a Buddha statue (Ayuthaya, Thailand),
scanned with Riegl LMS-Z210 that has angular sampling
interval is 0.018? (Riegl, 2004). Figure 4 shows the point
clouds as before and after registration using our method.
The third example is a scene containing a building and
trees measured by Mensi GS200 whose angular sampling
interval is 0.0025° (Mensi, 2004). In this example, three
point clouds are registered as shown in Figure 5.
The results of registration are listed in Table 2. In case of
the simulated data without noise, the registration error af-
ter seven iterations is 0.04mm. In the cases of simulated
point clouds with zero-mean Gaussian noise, registration
errors are similar with the standard deviations of Gaussian
noise. The execution time of à = 0.06 is faster than the
other cases. All registration errors of both simulated and
