463 
AUTOMATIC GENERATION OF DIGITAL BUILDING MODELS FOR COMPLEX 
STRUCTURES FROM LIDAR DATA 
Changjae Kim a , Ayman Habib a ’ *, Yu-Chuan Chang 3 
a Geomatics Engineering, University of Calgary, Canada - habib@geomatics.ucalgary.ca, (cjkim, ycchang)@ucalgary.ca 
Commission IV, WG IV/3 
KEY WORDS: LiDAR, Ground/non-ground Separation, Building Hypotheses, Segmentation, Digital Building Model 
ABSTRACT: 
Automated and reliable 3D reconstruction of man-made structures is important for various applications in virtual reality, city 
modeling, military training, etc. This paper is concerned with the automated generation of Digital Building Models (DBM) 
associated with complex structures comprised of small parts with different slopes, sizes, and shapes, from a LiDAR point cloud. The 
proposed methodology consists of a sequence of four steps: ground/non-ground point separation; building hypothesis generation; 
segmentation of planar patches and intermediate boundary generation; and boundary refinement and 3D wire frame generation. First, 
a novel ground/non-ground point classification technique is proposed based on the visibility analysis among ground and non-ground 
points in a synthesized perspective view. Once the LiDAR point cloud has been classified into ground and non-ground points, the 
non-ground points are analyzed and used to generate hypotheses of building instances based on the point attributes and the spatial 
relationships among the points. The third step of the proposed methodology segments each building hypothesis into a group of planar 
patches while simultaneously considering the attribute similarity and the spatial proximity among the points. The intermediate 
boundaries for segmented clusters are produced by using a modified convex hull algorithm. These boundaries are used as initial 
approximations of the planar surfaces comprising the building model of a given hypothesis. The last step of the proposed 
methodology utilizes these initial boundaries to come up with a refined set of boundaries, which are connected to produce a wire 
frame representing the DBM. The performance of the proposed methodology has been evaluated using experimental results from real 
data. 
1. INTRODUCTION 
Recent developments in positioning and navigation technology 
is having a positive impact on the widespread adoption of 
LiDAR (Light Detection And Ranging) systems, leading to an 
abundant availability of accurate surfaces with high point 
density. Abstracting the huge number of points in a typical 
LiDAR survey and relating them to physical objects, especially 
man-made structures, are among the key problems being 
addressed by current research. Therefore, there has been 
significant interest in developing DBM generation 
methodologies for representing artificial structures in a simple 
way, instead of using the enormous amount of points present in 
the LiDAR point cloud. Various methods have been suggested 
for building extraction from LiDAR points. Haala et al. (1998), 
Brenner and Haala (1998), Vosselman and Dijkman (2001) 
made use of ground plan data. Several attempts based on using 
Digital Surface Models (DSM) and Digital Terrain Models 
(DTM) have been made by Brunn and Weidner (1997), Ameri 
(2000), and Rottensteiner and Briese (2002). This paper 
discusses the topic of automated generation of DBM associated 
with complex mad-made structures from a raw LiDAR point 
cloud. More specifically, we will present a new framework for 
DBM generation from LiDAR data, which overcomes 
shortcomings of existing techniques. The proposed 
methodology consists of four basic steps: 1) Ground/non 
ground point separation; 2) Building hypothesis generation; 3) 
Segmentation of planar patches and intermediate boundary 
generation; and 4) Boundary refinement and 3D wire frame 
generation. First, a novel ground/non-ground point 
classification technique is proposed based on the visibility 
analysis among ground and non-ground points in a synthesized 
perspective view. After the original LiDAR points have been 
classified into ground and non-ground points, further 
investigation into the non-ground points is performed, to 
generate hypotheses of building instances. The generated 
hypotheses are based on the planarity and the proximity of the 
non-ground points. The points representing a single hypothesis 
might be comprised of several connected planes with different 
slopes and aspects. Therefore, the third step of the proposed 
methodology segments each building hypothesis into a group of 
planar patches. The proposed segmentation technique in this 
paper uses a voting scheme that keeps track of the point 
attributes. The clustering of the points is implemented based on 
simultaneous consideration of the attribute similarity and spatial 
neighborhood among the points, to provide a robust and 
accurate solution. Moreover, this procedure is more efficient 
compared to the existing methods in terms of computation load. 
Once the clusters are provided from the segmentation procedure, 
the boundary for each of the segmented clusters is derived using 
a modified convex hull algorithm. These boundaries will be 
used as initial approximations of the planar surfaces comprising 
the building model of a given hypothesis. The last step of the 
proposed methodology utilizes these initial boundaries to come 
up with a delineated set of boundaries which are connected to 
produce a wire frame representation of the DBM. Various 
geometric characteristics such as intersection, proximity, 2D 
collinearity, and height frequency are utilized to regularize 
initial boundaries. The detailed explanation of the proposed 
methodology is presented in section 2. The performance of the 
Corresponding author.