In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C. Tournaire O. (Eds). IAPRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3. 2010 
177 
Merging is similar to region growing in computer vision 
problems, in which Weingaiten(2004), proposed a dynamic list 
structure of cubes and the computation complexity is O(n) after 
sorting. In our design, we adopted the dynamic linked list tree 
structure to present the data set plane merging in 0(n) without 
sorting. By run-time encoding of planes, we only pass the 
normal vectors and the point of geometric center according to 
the index to the merging decision maker. The merging of 
planar patches is based on two criterions: proximity and the 
surface normal disparity (Stamos and Allen 2000). The 
proximity matrix is created by combining one dimension 
distance vectors of individual point to planes. denotes the 
distance from the geometric center of i-th patch to j-th patch. 
D\ i D n •••" 
Taking advantage of the symmetric property, we can reduce the 
matrix memory access by creating the mutual distance matrix 
M such as 
M = P + P T , (11) 
where the superscript T denotes the matrix transpose. For each 
element //?;, in M, a threshold value 1 is chosen to merge the 
similar patches. Thus, a set m is then obtained according to 
m = Vm..</ (12) 
The final step is to merge the planar patches with similar 
surface normal vectors. 
2.4 Boundary Extraction Based on Planar Convex-hull 
In definition, the convex hull for a points set X in a real vector 
space V is the minimal convex set containing X. For a planar 
convex-hull, the boundary can be used to present an edge of 
some plane. In a 2D points set, there exists a convex for all the 
point in R~. After a plane in R' is rotated to x-y plane, the 3D 
planar edge detection problem is reduced to a 2D convex hull 
problem. By experiment, the computation cost of 3D convex 
hull is two times larger than in 2D space. The following 
procedure shows the detail to extract the edges of each merged 
planes. 
Step 1. For each points P" (/ = 1 ...M), we can evaluate the 
orthographic projected points P e R' on the distributed plane 
0 fi alone the direction of N“. In the 3D-Euclid space, Pmust 
be constrained by the following condition: 
P'f-N" = C“,V/' e [l,Af] > (12) 
where C 1 is a constant. Figure 3 show's the projection of P,"to 
p 7 
Step 2. For constructing the planar convex-hull in R~. it is 
desired to find a rigid transformation (a rotation matrix 
O"(0, <$<^)<eS03 and a translation vector t"(//, t- a )) which is 
able to transform P ’" from 0" to P, aT on x-y plane, such as 
P“ 7 - z = 0 -»(O" • P'“+t")-z = 0, (13) 
where z = [0,0,1] is an unit vector along Z axis. The 
corresponding ®" and t" can be determined by solving the 
above equation through “Levenberg Marquardf algorithm and 
“Rodrigues” algebra. Then, the points P,“ 7 have the form [p x aT , 
p " T , p” r =0] since Pj aT e [x-y plane]. We can choose the first 
two elements to create new points P" = [ p xl aT , p y !' J ] g R‘. A 
new set P" which contains P" (/' = 1...A/) is established for 
developing the planar convex-hull. 
Step 3. There are various convex-hull algorithms considering 
many aspects of constraints, including floating number 
precision, computational cost, and the implementation 
complexity. The one we adopt is the “2D qliull” (Barber 1996), 
the complexity of qhull is 0(/?log(/?)), it works with double 
precision numbers, and it is fairly robust. The basic idea is 
applying “Divide-and-Conquer” method after sorting the points 
set in the fashion: 
(x 0 ,,v 0 )<(*„) or (x 0 = x,, To <>’,)• (14) 
The merge component takes linear time O(n), therefore, the 
overall complexity is 0(A7log(/?)). The procedure below' shows 
the detail of merge algorithm: 
Algorithm 2DConvexHullMerge(H L .Hr) 
Function arguments: H L \ left convex polygon, H R . right convex 
polygon 
1. Pi = fmdMaxX(Hi); 
2. Qi =findMinX(H R ); 
3. while ( not tangent(Pi, ()■,)) 
4. = fmdMaxX{H L -{/*, }); 
5. Q i+I = jindMinX(H R - { O,}); 
6. end w hile 
7. Hull = mergeTwoHull(Hi,H R ); 
8. return createCounterClockHuII(Y{u\Y); 
In order to draw the planar polygon more easily, it is important 
to produce a counter-clockwise permuted hull. From above, the 
geometric boundary of a plane can be extracted by applying 2D 
qhull algorithm. In most cases, the boundary can be considered 
as a good approximation to the real geometry shape; it can be a 
good starting point w'hen there is an occlusion happened in the 
LiDAR data which hull helps to complement some point loss. 
The overall algorithm proposed in this paper can be 
summarized in the following pipeline. 
I Laser scan I 
i , , 
|Segmentationf-jT Planar patch extraction j|Project P" to planeQ^I 
[Create new points P a e R~|(-(Project P ‘> X ~ Y plane | 
["Create planar convex-hull }—jfEdpc detection | 
Figure 4. Processing pipeline