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