■ 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
into the common centre - center of Gaussian sphere. The grid of 
meridians and parallels was applied to the Gaussian sphere and 
was used for EGI generation. The value of each EGI pixel is 
equal to 1 if any normal vector points to the corresponding grid 
square. Therefore EGI is a binary image. Orientation histogram 
H is based on EGI but each pixel of the histogram contains a 
count of all normal vectors which are points to the grid square. 
Assume that each normal vector of the scan surface directs 
towards the scanner. 
Figure 1. The points on the cube surface (A) Orientation 
histogram (B). Each local maximum on the image corresponds 
to the cube plane. The angular step of discretization is 3°. 
Orientation histogram is invariant to the translation but it 
depends on the rotation of 3D object. We can obtain the 
orientation histogram H' of rotated object using initial 
histogram H . Let’s define a rotation procedure for the 
orientation histogram as the rotation of all single vectors 
corresponding to each histogram pixel. By placing rotated 
single vectors into the center of Gaussian sphere we can 
calculate new orientation histogram: 
where 
H'=R H, 
, - rotation matrix. 
(1) 
R! e SO{3) 
Thus we can fast generate orientation histograms for any 
rotations of 3D object based on one orientation histogram H . 
Define a correlation function c(//,,//,) for two orientation 
histograms and ^ : 
С(Я,,Я 2 ) = 
V v 
Ы ,=i 
(2) 
ÏX",«-./rVV 
¡=1 j=1 i=l i=\ 
4. REGISTRATION ALGORITHM 
The pre-alignment algorithm for two point clouds f and p 2 
consists of an estimation of shift vector T and rotation matrix 
R between local coordinate systems for each scan. Our 
algorithm includes two steps: angular orientation of two clouds 
and its relational shift. 
4.1 Estimation of the angular orientation 
Estimation of the angular orientation consists of the following 
steps: 
1. Generate two orientation histograms h x and // for scans 
P x and P 2 respectively; 
2. Search the maximum of correlation function C{H X ,H\) 
for all possible values of rotation matrix R . 
The value of rotation matrix R Cmm , corresponded to the 
maximum of correlation function, is a required angular scans 
orientation value. 
4.2 Estimation of the shift translation 
Firstly the rotation procedure is applied for cloud p using 
values of rotation matrix 
R n\ ¡1 ' 
A — R C max Rj 
(3) 
Than the binary voxel presentation y and V 2 for scans /> and 
P 2 should be calculated using 3D discretization procedure 
[Chibunichev 2007]. The element of V is equal to 1 if at least 
one scan point is inside this voxel and is equal to 0 otherwise. 
Estimation of the shift between scans coordinate systems is 
defined by maximum of the correlation function: 
<3(0= ¡V,(p)V 2 (p-r)dp 
(4) 
peR 1 
The convolution integral (4) can be calculated by using 
traditional Fourier transform on R3 (see appendix A). This 
solution gives us such a value of the shift parameter that 
guarantees the maximal coincidence of nonzero elements of 
V x and V 2 
if- 
Figure 2. The graph of dependence of the correlation function C{H X H 2 ) on the rotation angle К on Z axis (A), initial not 
oriented point clouds (B), pre-alignment results using orientation histograms (C), Sanmarina Church (Greece), ISPRS, Working 
Group V/3, standard, real world datasets. 
602