International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
of a cloud has a set of evenly-distributed neighbourhood
points. This problem can be overcome by using the angle
criterion between the neighbour points as Linsen (2001)
did for the triangulation of point clouds. Furthermore, we
could use a method in which each point has different num-
ber of neighbourhood pairs. The angle criterion has been
used in this paper but using different number of neighbour-
hood for each point was not implanted. Therefore, a larger
number of neighbourhood points has been used.
2.3 Algorithm description
The amount of data to process in order to find correspon-
dence is very large, which limits the robustness of regis-
tration algorithms. The higher curvature points may have
more valuable information than the lower curvature points
since they could be edges or corners. Therefore, in the
early stages of iteration, we only take into account higher
curvature points and then, as iteration proceeds, lower cur-
vature points also are included to improve the registration.
Our method for the registration of three-dimensional, par-
tially overlapping and unorganised point clouds without
good a priori alignment can be briefly described as follows:
I. Find the & neighbourhood points of every point in
C! and C7. Estimate the geometric primitives of the
points.
2. Take initial sample points, p! , whose
(le ner}
Jz P HII is greater t1 eru Oo
change of curvature is greater than 775, where
Tter--; 1$ the number of sample in ith iteration.
a. p; isthe
nue Mt semi
^ 3 "ac . . ] 1
3. Find corresponding points of py r
corresponding point of pl if
0(pj ' p;) = qterzi
“normal
where Tir=t and T= are the thresholds for the
angle between the normal vectors and the difference
in the changes of geometric curvature between the
corresponding points, respectively.
4. Calculate the approximate transformation, Titer=is
and transform C. Rotate the normal vectors of all
points of C? as well.
Un
Update the threshold values in order to apply a more
strict criterion for determination of possible corre-
sponding points as follow.
quiter—i+l npuier-:i A
T EY Em AL sma
normal * normal
miter=i+1 _ rpviter=i "m
T Tum T. =. AT...
riter=i+1 ter —i AT
7 EE T 2 = AT Sample
sample sample
6. Calculate the registration error, €''*"7, which is de-
fined as the rms distance of points and their cor-
responding surfaces in our method. f c" is
greater than threshold, then go to step 2. Other-
wise stop the registration. In addition, if «=? is
smaller than 7, .,,, for example, the average distance
of a point from its neighbourhood, then Chen and
Medioni’s method is used since it converges quickly
than Horn's algorithm does if the point clouds are
close (Rusinkiewicz and Levoy, 2001). Otherwise
Horn's method is used.
If the initial alignment is close to the correct one, only a
small number of points need to be searched. Otherwise
a large number of points must be searched in order to
find correct correspondence of sample points. The opti-
mal number of points being searched could be evaluated
from the statistical properties of the distribution of regis-
tration error metric (Zhang, 1994). However, the distance
distribution of the corresponding points is usually not a
unimodal Gaussian but bimodal or multimodal distribu-
tions. Furthermore, good initial alignment is not assumed
in the proposed method, it is difficult to remove outliers in
the early stages of iteration. Therefore, a large number of
points need to be searched in order to determine the corre-
spondence of two point clouds.
2.4 Scale of selected corresponding points
The scale of selected corresponding points is usually as-
sumed to be unity and this assumption is reasonable ın
most cases (Horn, 1987). It can be also used as the error
metric to represent the quality of registration (Crosilla and
Beinat, 2002). The scale can be interpreted as a parameter
for the quality in the determination of the corresponding
points. For example, if we have incorrect correspondence
information, then the scale is not unity. The scale factor in
kth iteration, Siter—æ, Can be expressed as
S en NET F pi ; Lien (CP(p} : C?)) (7)
ESS SE er OP OP
where T:rer=z is the calculated transformation of the Ath
iteration, C.P(pl. C?) is the position vector of the corre-
sponding point of p] ,and n;;2,—, 1s the number of samples
in the kth iteration. Although the scale of corresponding
points is unity, it does not guarantee that we have one-to-
one matched correspondence. If the scale is much greater
or smaller than unity, the calculated translation could be
incorrect.
2.5 Threshold values
The list of threshold values used in the proposed method
is shown in Table 1. 77'*"^? and AT arc the most impor-
tant and critical thresholds. The other threshold values are
not critical to the success rate of the proposed method, al-
though they affect the robustness of the registration. It is
difficult to state explicitly which values are the optimal val-
ues since they depend on dataset. Currently we are work-
ing on finding the optimal and generalized expressions for
these thresholds. Our suggestions of 7//*" ^? and AT from
the experiences with the proposed method are
A. - poa ps A
EUM SLM:
Jes 0 to ec z E C. (8)
€ 2 t M qx 2 | 2. D od
AT... SEINS À LA "ums 7 Mz rms (9)
Internat
thresh
k
ter:
san]
Titer:
1 ec
miter=
norm
1
AT sari
AI
=
A Tor
mr
SCA
Te
Table 1
method.
where «
of the c]
3 EXI
Three e
a simul
tured w
partially
mented
450MH
mized s
cessing
tree sea
LAPAC
31" Si
Figure 1
parts of
The sim
mension
number
One poi
0.5m) ai
as show:
ious star
point of
viation,
have exz
Many d
sure ho
