further research of this method on the application of airborne 
LiDAR point cloud data. 
In addition, the experiment of hidden targets extraction was not 
mentioned in these papers. This method is based on LiDAR 
point cloud data organized by KD-tree, after target 
segmentation, Hu invariable moments and flight characteristics 
could be also combined to improve the airplane target 
recognition, even hidden airplanes mainly under the cover of 
canopy. 
The first step of hidden targets detection is target segmentation. 
Compared to other image segmentation methods, the 
segmentation based on KD-tree can deal with 3D point cloud 
data directly. The proposed algorithm firstly uses KD-tree to 
organize and manage point cloud data, and then utilizes 
clustering method to segment objects. Based on the result of 
segmentation, the prior knowledge and invariant recognition 
moment is utilized to identify target of interest. 
The outcomes of this test verified the practicality and feasibility 
of the method derived in this paper. The accuracy rate is 0.937, 
error ratio is 0.063. The approach in this paper could also be 
applied in other kinds of covered targets extracting. These could 
be applied in target measuring and modelling of subsequent 
data processing. 
2. SEGMENTATION BASED ON KD-TREE 
In data processing, target segmentation is to classify points have 
same properties (such as height, intensity, etc.) into one class, 
and it is also the premise of target recognition, fitting and 
measurement. The proposed algorithm firstly uses KD-tree to 
organize and manage point cloud data, and then uses clustering 
method to segment objects. 
2.1 KD-tree 
This paper employs KD-tree to store and manage LiDAR point 
cloud data. In this way, each point’s neighbour-finding could be 
queried by KD-tree which is actually a K-dimensional binary 
tree of every node (Moore, 1991). In this section, KD-tree is 
three dimension, and built as follows: choose the splitting 
dimension as the longest dimension of the current 
hyperrectangle, and then choose the point closest to the middle 
of the hyperrectangle along this dimension. This strategy gives 
consideration to both tree’s balance and segmented units’ 
regularity. Moreover, in order to avoid empty branch, the tree’s 
top floors could still follow the standard rules. 
2.2 Targets Clustering 
After organizing point cloud data by KD-tree, query to search 
points within effective distance among neighbourhood has been 
established. Aiming at target segmentation, points in certain 
distance are classified into one class. We adopt the nearest 
neighbor query method since finding proximal points to create 
local surface patch rapidly is the key step (Bin, 2008). When 
given point p and query distance d, the nearest neighbour query 
method is to lookup points in the sphere with p as center and d 
as radius. Obviously, the core algorithm is to find all units 
intersecting with the sphere. The unit of KD-tree is called 
hyperrectangle (as rectangle in two-dimensional, rectangular 
parallelepiped in three-dimensional), and can be defined with 
two arrays: the minimum and maximum of coordinate value of 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012 
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia 
each point. On purpose of estimating whether there is an 
intersection between the hyperrectangle Ar and the sphere, the 
point £ in Ar nearest to p must be found, its expression is: 
h^ P; < hr 
x min max (1) 
pep de" eph 
jm D, > hr 
where pre and hr is the minimum and maximum value of hr 
in the ith dimension. Hyperrectangle satisfies condition that 
distance between p and £ no more than d would be looked up, 
and the range query terminates when all points are checked. 
In the clustering method, the choice of a reasonable distance 
threshold has an important influence on the results of target 
segmentation. Therefore, in this paper, the distance threshold is 
set to 1-1.5 times point spacing. 
3. MOMENT INVARIANTS 
Considering that the feature of airplane is distinct when 
overlooked, so the target recognition method in image is used 
for airplane recognition in LIDAR data. Moment is usually used 
to characterize the distribution of random quantity in statistics. 
If we take binary image or gray image as two-dimensional 
density distribution function, the moment method can be 
applied to image analysis. 
3.1 Basic Concept of Moment 
For digital image f(j, j) of two-dimensional (NxM), moment 
with p+q order can be defined as (Zhongliang et al., 1992): 
M-1N-1 
my = 21, J) @) 
j-0 i-0 
where i, j is the coordinate in the image, and the central moment 
of f(i, j) With p+q order is: 
M-1N-1 
ty = 2 2 (=F (y=) f(x) G 
j-0 i-0 
It’s easy to prove central moment ; is translation invariance, 
Pq 
if making it with scale invariance, normalized central moment 
in, should be used and defined as: 
= Un or — _ Up (4) 
u, 6 = u, = 
pq (ua, uy Y pq Gl UD? 
where rz(p--q*2)/4,p*q-2,3,.... 
3.2 Hu's Moment Invariants 
Lower order moment could express a certain distribution or 
target's basic geometric properties. Main regular moments are 
zeroth order moment, first-order moment, second-order moment, 
third-order moment. Hu's moment invariants theory (Hu, 1962) 
is a nonlinear combination of 7 parameters by normalized 
central moments, defined as: 
Moment invariant 1: 
$ utu (5) 
Moment invariant 2: 
d, = (uy = Uy) + du}, (6) 
Moment invariant 3: 
% = (t5, = 3u,,) + Qu, = 403 ¥ (7) 
    
  
   
  
  
   
   
   
    
   
    
  
    
   
  
  
  
  
    
     
   
  
  
  
  
  
    
    
  
    
   
  
    
   
    
    
    
   
    
   
   
    
   
    
  
    
   
  
rn 
rf 
^^ M4 ———- rf) "y me