1.2. Related work
Numerous algorithms have been developed over the years for
the segmentation of lidar point clouds; employing both range
images and unstructured point clouds. Vosselman and Dijkman
(2001) use Hough transform to extract planar points and then
perform merging and expanding operation to obtain planar roof
faces. Alharthy and Bethel (2004) perform least squares
moving surface analysis along with with region growing
segmentation to extract building faces. Kim and Shan (2011)
employ a multiphase level set approach to building roof
segmentation and modeling. Dorninger and Nothegger (2007)
cluster the features which define the local regression planes of
the points and implement a region growing segmentation.
Sampath and Shan (2010) analyze the eigenvalues in the
voronoi neighborhood of the roof points and cluster the surface
normals for segmentation. Filin and Pfeifer, (2006) also use
feature clustering on 3D lidar point clouds with slope adaptive
neighborhood. Biosca and Lerma, (2008) present an
unsupervised fuzzy clustering based segmentation approach for
TLS point clouds. Douillard et. al., (2011) investigate several
methods considering data density, ground filtering, and
clustering techniques for the segmentation of 3-D point clouds
employing graph clustering. Golovinskiy and Funhouser,
(2009) perform a min-cut based method for a foreground-
background segmentation of objects in the point clouds.
Regarding the determination of the support regions of the
points Lalonde et. al. (2005) and Pauly et. al. (2003) investigate
the scale factor. Regarding the connection between point
segmentation and classification, Belton and Lichti (2006)
outline a method for point classification by using the variance
of the curvature in the local neighborhood of the points
followed by a region growing segmentation on terrestrial laser
scanning (TLS) point clouds. Lim and Suter, (2007) propose a
method employing conditional random fields (CRF) for the
classification of 3-D point clouds that are adaptively reduced by
omitting geometrically similar features. Niemeyer et. al. (2008)
also employ CRF for the supervised classification of lidar point
clouds. Carlberg et. al. (2009) present a multi-category
classification of point clouds using 3-D shape analysis and
region growing.
Our study follows the algorithms which utilize a feature vector
to represent the properties of the point neighborhood for
labeling the point cloud. We first label the points that are from
a surface (e.g. roof tops, ground, etc.) or 3-D manifold scatter
(e.g. trees) by optimizing the graph which represents the energy
function constructed for the classification problem. Then we
label the points that are from surfaces with different properties
using a second graph which represents an energy function for
the segmentation problem.
2. LOCAL NEIGHBORHOOD
2.1. Local neighborhood of a point
Although there are various definitions for the neighborhood of
an image pixel, it is intuitive to define its neighborhood due to
the inherent structure. On the other hand, defining the
neighborhood of a point in an unstructured point cloud is not
straightforward. Quality of the features that represent certain
properties of the point is dependent on the local neighborhood
of the point. For example, a very commonly used feature, the
normal vector of the point can be reliably estimated if its valid
neighbors may be identified. Too many or too few points may
affect the normal vector estimation either by degrading the
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
local characteristic or by not representing the local geometry
(OuYang and Feng, 2005). Hence, determining an accurate
local neighborhood of the point representative of their geometry
is of significance. Filin and Pfeifer (2005) provide a thorough
explanation of the properties of neighborhood systems in
airborne lidar data. Neighborhood of a lidar point may be
defined with a Delaunay triangulation which is the dual of the
Voronoi tessellation of the points. This representation is widely
used in computer vision for mesh generation. Neighborhood of
a point is also commonly defined by its k nearest neighbors, or
points within a volume defined by a sphere or a cylinder
centered at the point. One should note that the selection of the
parameters for defining the neighborhood of a point (e.g. radius
of the sphere, number of closest points) is closely related to the
scale. These parameters are most of the times not optimally
chosen.
2.2. Local neighborhood determination
Different approaches exist to determine the local neighborhood
of each point. Some of them are combinatorial algorithms like
the Delaunay ball algorithm of Dey and Goswami (2004).
There are also numerical approaches to estimate the optimal
neighborhood like the iterative method of Mitra and Nguyen
(2003). For airborne lidar point clouds, Filin and Pfeifer (2005)
propose slope adaptive neighborhood definition. Lalonde et. al.
(2005) investigate Mitra and Nguyen’s (2003) scale selection
algorithm applied to data from different sensors. Lim and Suter
(2007) also implement the same approach to determine the
support region of the points from a TLS for CRF classification.
Pauly et. al. (2003) determine the size of the local
neighborhood by looking for jumps in the surface variation as
the neighborhood size increases. In their recent study,
Demantke et. al. (2011) propose a method to find the optimal
neighborhood of each point.
The eigenvalues of the covariance matrix of a point’s
neighborhood have been employed in various studies as means
to determine the geometric properties and structure of the local
neighborhood (Gumhold et. al., 2001; Pauly et. al., 2003; West
et. al, 2004; Lalonde et. al.,2005; Lim and Suter, 2007;
Carlberg et. al., 2009; Niemeyer et. al., 2008, Demantke et. al.,
2011). We follow the method in Pauly et. al. (2003) while
determining the neighborhood of each point for feature
calculation. We start with a minimum number of nearest
neighbors for each point and calculate the covariance matrix C
of the neighborhood. Let JV, be the neighborhood of point p
which consists of a set of k points p; (i — 1,..., k) with the
centroid p. The covariance matrix C is calculated as
C2 iXE.: - B(pi - p" (1)
Pauly et. al. (2003) introduce surface variation as
On(p)=A3/(4 + A2 + A3) (2)
where A; < A; € A, are the eigenvalues of the covariance
matrix C.
We observe the change in the surface variation and detect the
jumps as the number of neighbors increase. Figure 1 shows the
change of surface variation with the increase in the number of
neare:
to the
surfac
Surface Variation
Figur
3.1. 5
Segm
labeli
L of |
find :
label
functi
The c
by n
segmt
identi
optim
form
repre:
functi
struct
probl
E(f)
where
Edata
The f
the d.
are c
how ı
is al
(Boyl
speci
assigi
3.2.
Most
many
globa
exhai
minir
(Felz
