LIDAR DATA SEGMENTATION AND CLASSIFICATION BASED ON 
OCTREE STRUCTURE 
Miao Wang*' Yi-Hsing Tseng 
Department of Geomatics, National Cheng Kung University, No.1 University Road, Tainan 701, Taiwan, R.O.C. 
“ monsterr@seed.net.tw 
NE ii 
" tseng(ümail.ncku.edu.tw 
KEY WORDS: Lidar, Laser Scanning, Feature Extraction, Organization, Segmentation, Classification 
ABSTRACT: 
Lidar (or laser scanning) has become a viable technique for the collection of a large amount of accurate 3D point data densely 
distributed on the scanned object surface. The inherent 3D nature of the sub-randomly distributed point cloud provides abundant 
spatial information. To explore valuable spatial information from laser scanned data becomes an active research topic. The sub- 
randomly distributed point cloud should be segmented and classified before the extraction of spatial information and the first step in 
the processing of the spatial data extraction is an organization of the lidar data. This paper proposes a new algorithm to split and 
merge the lidar data based on the octree structure. After the process a lidar data set can be segmented to 3D plane clusters and 
classified by the plane attributes derived from each 3D plane, such as area, gradient, intensity etc. Some example and analysis of 
practical data set will be performed for segmentation and classification using the proposed methods here. The test result shows the 
potential of applying this method to extracting spatial information from lidar data. 
I. INTRUDUCTION 
Lidar (or laser scanning) has become a viable technique in 
recent decades. The ability of collecting a large amount of 
accurate 3D point data densely distributed on the scanned 
object surface has brought us a new research topic (Ackermann, 
1999). The inherent 3D nature of the sub-randomly distributed 
point cloud contains abundant space information and can be 
further extracted for digital elevation model generation, 3D 
building model reconstruction, and trees detection (Haala and 
Brenner, 1999; Maas and Vosselman, 1999: Priestnall, et al., 
2000; Vosselman and Dijkman, 2001). To explore valuable 
spatial information from lidar data becomes an active topic. 
J 
Lidar data record 3D surface information in detail. To explore 
valuable spatial information from the huge amount of 3D data is 
difficult and time consuming. Segmentation is generally 
prerequisite for spatial feature extracting. Most segmentation 
techniques were developed from 2.5D grid data or image data 
(Masaharu and Hasegawa, 2000; Geibel and Stilla, 2000). Sub- 
randomly distributed point cloud is transformed into a grid data 
set through an interpolation procedure to apply an image-based 
segmentation and Classification (S/C), but some important 
spatial information may be lost (Axelsson, 1999; Gamba and 
Casella, 2000). Eventually, new S/C methods suitable for lidar 
data are needed for practical application. 
An octree-structure-based split-and-merge segmentation method 
for organizing lidar point cloud into clusters of 3D planes is 
proposed here. The method is hierarchically splitting the point 
cloud set on the octree structure until the points contained in 
each sub-node are coplanar, or say distributed in a 3D plane or 
less than 3 points. The neighbouring 3D planes with similar 
attribute are merged after splitting to form larger planes. 
The segmented 3D planes than can be classified according to 
the attributes derived from each 3D plane. The proposed 
method would suitably work for airborne lidar data as well as 
ground-based laser scanning data. Some results on both kind of 
lidar are presented in this paper finally. 
2. OCTREE-STRUCTURE-BASED SEGMENTATION 
The principle of the method is to segment point cloud into 3D 
planes. A split and merge segmentation based on the octree 
structure (Fig. 1.a) is developed. 
2.1 Split process 
The split process starts from the whole data set as a root node. 
The data set space will be divided into 8 equal sub-spaces, if the 
data set could not pass the distance and area threshold. The split 
generates 8 sub-nodes (Figure 1.b) representing the split spaces. 
Each sub-node will be split continuously until the scan points 
contained in the split space of the sub-node are distributed close 
to a 3D best-fit plane or less than 3 points. 
  
9 
t2 
  
  
  
  
  
  
  
(a) 
Laver 0 Source 
Laver ] 
Layer 2 
  
(b) 
Figure 1. Octree structure (a) divided sub-spaces (b) the tree 
representation 
Internal 
22 Ca 
The bes 
squares 
distance 
space, a 
The dis 
can be c 
Then, tl 
the dist: 
values 
calculat 
we use 
paramet 
At first 
which h 
To avoi 
paramet 
predeter 
cloud. | 
represer 
the disti 
done by 
if x din 
first typ 
Zn 
3 
X 
Figure 2 
Because 
be calci 
linear 
paramet 
X = Ay 
equatior