In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C.. Tournaire O. (Eds). IAPRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3, 2010 
2. While N pn >0 
3. point <— readPoint(p) 
4. boundp <— getBoundaiy(pomt,I) 
5. if (sizeof(C s ) = 0) 
6. C s «— assign(point, boundp) 
7. end if 
8. C s +— JitPointToCube(point, boundp) 
9. End while 
10. rewoveCvbe(Cf,. T s ) 
Line 1: points are read sequentially; 
Line 2: compute the cube boundary of the point : 
x min - floor(/v7), x_max= ceiling) p/I), 
yjnin = floor(p/l), y_max= ceiling(pjl). 
zjvin = floor ip VI), z_tnax= ceiling(pJl), 
Line 5-7: If there is no existed cube enclose the current point, 
a new cube is created and the point is assigned to it 
Line 8: If there is an existed enclosed cube, then the current 
point is assigned to it. 
Line 9: Iterate through every point. 
Line 10: Remove cubes which enclosed points are less than a 
threshold. 
The following figure shows an example of cube assignment 
process base on function “cubeAssign", 
4 
":i:S 
Figure 1. Cube assignment 
Suppose there are 8 points to begin with. The numerals indicate 
the order of data appeared in the file. The first two cubes “Cube 
1" and “Cube 2” are created to enclose point 1 and point 2, 
respectively. Since point 3 is within the range of "'Cube 2", a 
new "Cube 5” has to be created to enclose point 4. The same 
process is repeated until every point is assigned to an enclosed 
cube. 
At the end of cube assignment, a point which assigned to cube a 
can be denoted as 
2,2 Planar Patches Extraction and Visualization 
In this section, the local planar patch will be extracted from the 
points cloud and available for visualization in corresponding 
RGB color space. The so-called planar patch can be explained 
as the best-fit plane of the 3D points within a cube. Suppose 
there are M points (P“=[.r,°, y". distributed in the 
cube a (a = 1 ~ K). The vector № = [«/, n/, n. a ] with unit 
length, which is the normal vector, N, of the local planar patch, 
0", can be found by minimizing the objective function S 
S = ]T(N a • P,“ +1) 2 
;=i 
M 
(2) 
= X<«+»>f+»--“+i) 2 
The minimum solution to S can be solved directly by least 
square method. As presented in (Weingarten, 2004). the 
function S has to be partial differentiated with respect to n x a , n } u , 
n. a and set to 0. The optimal N can be evaluated as follow: 
№ = A"*' b" , 
where 
(3) 
A" 
b“ 
S>“ ! 
1« 
2>r--r 
-2> 
-2> 
-2> 
2>f*r 
2>f 2>r--f 
Ъ’^г I-'," 2 
(4) 
(5) 
From now on, the planar patch of each cube is found. The 
maximum and the minimum value n max , »„„„can be selected as 
I "max >nlje{X,y,z},j<=[l,K] 
("min <«/,/' e {x, y,z}, j e[l,jq 
p;=o’i'Pb'Pi)- 
о) 
where /7 is the point index within the cube. The following figure 
shows all the points are partitioned by stack-up cubes. 
н«К*. Vi 
These two extreme values can be applied to bound the range of 
visualization color in RGB format. In a specified cube a, all the 
points can be colorized by 
R ° =("**-"mm)/("max “"min) 
< G a = (n —» )/(» — n ) 
B a ={n,„ -«•)/(»,. —П ■ ) 
v za mm / v max mm / 
(9) 
Based on the framework described above, the distributed plane 
is found, and the points can be visualized by corresponding 
color from well segmented 3D point data. 
2.3 Merging of Planar Patches 
Figure 2. Segmented points data with cube. 
Each of the cube and the surrounded points are well clustered. It 
is efficient for further analysis such as plane or boundary 
extraction and polygon reconstruction. A planar patch (a 
surface supported by local points) is a basic component to 
formal a globalized planar surface. 
The geometry features and the proposed visualization features 
are extracted through the above methods. Furthermore, in order 
to reduce the computation cost in the following boundary 
extraction and to describe the geometry features in a more 
semantic and realistic fashion, it is essential to merge the planar 
patches 
176