In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009
133
OBJECT EXTRACTION FROM LIDAR DATA USING AN ARTIFICIAL SWARM BEE
COLONY CLUSTERING ALGORITHM
S. Saeedi a , F. Samadzadegan b , N. El-Sheimy a
a Department of Geomatics Engineering, University of Calgary, T2N 1N4, AB, Canada - (ssaeedi, elsheimy)@ucalgary.ca
b Department of Geomatics Engineering, Faculty of Engineering, University of Tehran, Iran - samadz@ut.ac.ir
Commission III, WG III/4
KEY WORDS: Clustering, LIDAR, Artificial Bee Colony, Urban Area, Object Extraction
ABSTRACT:
Light Detection and Ranging (LIDAR) systems have become a standard data collection technology for capturing object surface
information and 3D modeling of urban areas. Although, LIDAR systems provide detailed valuable geometric information, they still
require extensive interpretation of their data for object extraction and recognition to make it practical for mapping purposes. A
fundamental step in the transformation of the LIDAR data into objects is the segmentation of LIDAR data through a clustering
process. Nevertheless, due to scene complexity and the variety of objects in urban areas, e.g. buildings, roads, and trees, clustering
using only one single cue will not reach meaningful results. The multi dimensionality nature of LIDAR data, e.g. laser range and
intensity information in both first and last echo, allow the use of more information in the data clustering process and ultimately into
the reconstruction scheme. Multi dimensionality nature of LIDAR data with a dense sampling interval in urban applications, provide
a huge amount of valuable information. However, this amount of information produces a lot of problems for traditional clustering
techniques. This paper describes the potential of an artificial swarm bee colony optimization algorithm to find global solutions to the
clustering problem of multi dimensional LIDAR data in urban areas. The artificial bee colony algorithm performs neighborhood
search combined with random search in a way that is reminiscent of the food foraging behavior of swarms of honey bees. Hence, by
integrating the simplicity of the A'-means algorithm with the capability of the artificial bee colony algorithm, a robust and efficient
clustering method for object extraction from LIDAR data is presented in this paper. This algorithm successfully applied to different
LIDAR data sets in different urban areas with different size and complexities.
1. INTRODUCTION
The need for rapidly generating high-density digital elevation
data for areas of considerable spatial extent has been one of the
main motives for the development of commercial airborne laser
scanning systems. During the last decade, several clustering and
filtering techniques have been developed for the extraction of
3D objects for city modelling applications or removing the
“artefacts” of bare terrain (i.e. Buildings and trees) in order to
obtain the true Digital Elevation Model (Filin and Pfeifer; 2006;
Kraus and Pfeifer, 1998; Lodha et al., 2007; Rottensteiner and
Briese, 2002; Tovari and Vogtle, 2004).
However due to low information content and resolution of
available commercial LIDAR scanners, it is difficult to
correctly recognize and remove 3D objects exclusively from
LIDAR range data in urban areas (Maas, 2001; Samadzadegan,
2004; Tao and Hu, 2001; Vosselman et al., 2004).
In order to improve the performance of 3D object extraction
process, additional data should be considered. Most LIDAR
systems register, at least, two echoes of the laser beam, the first
and the last echo, which generally correspond to the highest and
the lowest object point hit by the laser beam. First and last echo
data will especially differ in the presence of vegetation (Kraus,
2002). Moreover, LIDAR systems record the intensity of the
returned laser beam which is mainly in the infrared part of the
electromagnetic spectrum. In addition, an extra powerful source
of information is visible image. Digital images can provide
additional information through their intensity and spectral
content as well as their high spatial resolution which is better
than the resolution of laser scanner data.
Therefore, in the context of 3D object extraction in urban
areas, various type of information can be fused to overcome
the difficulties of classification and identification of
complicated objects (Lim and Suter, 2007; Vosselman et al.,
2004). Collecting this information, extremely enlarge the size
of data sets and proportionally the dimension of feature spaces
in clustering process. As a result, most of traditional clustering
techniques that have been applied with standard data and low
feature space dimension are not efficient enough for object
extraction process from LIDAR data (Melzer, 2007; Lodha et
al., 2007).
&-means is one of the most popular clustering algorithms for
handling massive datasets. The algorithm is efficient at
clustering large data sets because its computational
complexity only grows linearly with the number of data points
(Kotsiantis and Pintelas, 2004). However, the algorithm may
converge to solutions that are not optimal. This paper presents
an artificial bee colony (ABC) clustering algorithm for
overcoming the existing problems of traditional A:-means.
2. BASIC CONCEPTS IN DATA CLUSTERING
Historically, the notion of finding useful patterns in data has
been given a variety of names including data clustering, data
mining, knowledge discovery, pattern recognition, information
extraction, etc (Ajith et al., 2006). Data clustering is an
analytic process designed to explore data by discovering of
consistent patterns and/or systematic relationships between
variables, and then to validate the findings by applying the
detected patterns to new subsets of data.
