ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002
SURFACE CLUSTERING FROM AIRBORNE LASER SCANNING DATA
Sagi Filin
Department of Geodesy, Faculty of Civil Engineering and Geosciences, Delft University of Technology, The Netherlands
s.filin@citg.tudelft.nl
Working Group III/3
KEY WORDS: Clustering, Laser altimetry, Surface classification, Surface reconstruction, Data segmentation
ABSTRACT
This paper presents an algorithm for the extraction of surface clusters from airborne laser data. Surface structure analysis
is fundamental to almost any application involving LIDAR data, yet most algorithms focus only on identifying planar
segments. The proposed algorithm is more general insofar as it aims at extracting surface segments that exhibit an
homogeneous behavior, without restriction to one specific pattern. The algorithm adopts a data clustering methodology
for this purpose, which offers a very general and flexible way to identify homogeneous patterns in the data.
1 INTRODUCTION
Laser altimetry has emerged in recent years as a leading
technology for the extraction of information of physical
surfaces. The dense description of physical objects and the
terrain that is achieved by current airborne systems have
led to an increased interest in utilizing the data for geo-
spatial analysis as well as to surface reconstruction and ter-
rain models generation. Growing experience shows, how-
ever, that the ability to use the raw data directly for deriv-
ing products and for analysis is rather limited, mainly as
the data consists of a mixture of terrain, surface, and non-
surface points without any semantic information that may
distinguish one set of points from the others. As a result,
applications that require separating one type of points from
the others, e.g., masking vegetation, terrain points from
non-terrain points, object points from non-object points, or
applications that depend on evaluating local surface prop-
erty require introducing some level of surface analysis to
the data. It has been suggested to apply point based tech-
niques as a potential solution to some applications, but ex-
perience shows that they have their own limitations and
that a more rigorous approach is preferable. The role of
surface structure analysis goes beyond filtering or masking
the data. As digital surface models (DSM) generation, 3D
object recognition, or applications such as 3D city model-
ing require laser surfaces as an input, laser surface analy-
sis becomes prerequisite for any application that involves
interpretation of the data. As laser surfaces are defined
by laser points, identifying surface structure consists of
grouping the points into segments with common attributes.
Segmentation of range data is still an active field. The ma-
jority of the reported algorithms concern close-range ap-
plications, as the works by, Besl (88); Kóster and Spann
(2000) or the review in Hoover et al. (1996), indicate. Yet,
close range applications are usually applied to modeling
objects with well-defined, smooth shapes; the surfaces sur-
veyed by airborne LIDAR systems offer, in contrast, far
more complex shapes representing a variety of natural phe-
nomena. Notwithstanding, the majority of the reported
algorithms focus on extracting planar surfaces (see, e.g.
Lee and Schenk, 2001; Vosselman, 2001), mostly in asso-
ciation with the extraction of roof facets for building ex-
traction. By narrowing their scope to this specific type of
surfaces these algorithms are likely to fail with complex
building shapes or with mixture of vegetation and build-
ings; they also lack the generality required in associating
the laser points in the dataset with a segment (the essence
of data segmentation). Based on similar arguments Maas
(1999) and Oude Elberink and Maas (2000) tackle the seg-
mentation of airborne laser data. The authors propose seg-
mentation algorithms for a rasterized and quantized ver-
sion of the range data. They identify classes in the data
based on height texture measures. Their algorithms clas-
sify the data by attaching a label to each pixel but prac-
tically do not provide surface segments. So, while an as-
sociation of the data with classes is achieved, identifying
structure in the data is not guaranteed at all.
This paper presents a point clustering algorithm for ex-
tracting homogeneous segments in the laser data. Homo-
geneity refers to clusters of data sharing consistent attributes,
and in the current case surface attributes. Clustering is a la-
bel for a variety of procedures aiming at grouping the data
into homogeneous patterns, usually without an explicit a
priori definition for the patterns. The clustering method-
ology offers generality and flexibility in accommodating
spatial relation and attributes and also the ability to incor-
porate different cues into the process in a very natural way.
Clustering can be seen as a combination of two processes
— identifying patterns in the data based on attributes and
grouping the data into clusters. Attributes should identify
the properties that capture the sought-after information and
produce the best separation among classes. Grouping con-
cerns identifying areas with homogeneous attributes; the
goal is to find clusters that are spatially meaningful and at
the same time to avoid an algorithmic tendency for over-
segmentation of the data. With laser data, further details
regarding the data acquisition systems should be consid-
ered. The data itself consists by nature of a set of irreg-
ularly distributed points that carry only a limited amount
of information, namely their x, y, and z coordinates. The
spatial point distribution and the point density cannot be
assumed fixed as they depend on the scanning system. The
algorithm that is presented here copes with the varying
point density and operates on the laser points directly with-
out rasterization or other preliminary processing that may
A- 119
