In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009 
GEOREFERENCED 
' ■ 
USER RAW DATA 
PREPROCESSING 
3D CLOUD POINTS 
INTO 2D ACCUMULATOR 
EXTRACTION OF FEATURES 
MODELING 
BUILDING FOOTPRINT 
Figure 4: Data flow diagram of the building footprint extraction 
approach. 
the dataset by thresholding these distances. Moreover, this tem 
poral effect distinctly appear on the image of intensity of the laser 
beam and looks like a succession of rows having the same inten 
sity (see figure 3). Therefore detecting redundant frames can also 
be based on differences between the intensity of return of two 
consecutive rows. This step solves only the problem of data re 
dundancy related to the sensor immobility. 
3.1.2 Volume of interest The sensor characteristics are used 
to select the 3D points belonging to the facade plane. The 3D 
available points are principally positioned above the vehicle to 
reduce the problem of occlusions. A horizontal band is defined 
between two horizontal planes. The lower plane passes through 
the sensor center. The upper plane is shifted by a certain dis 
tance that is related to the height of the buildings under study. We 
precise that the ground altitude could be simply deduced by mea 
suring manually the laser sensor height. Finally, the volume of 
interest is defined by the georeferenced trajectory of the vehicle 
and the above horizontal band. The 3D points not included in this 
volume will be removed from the dataset. 
having a high score are kept. The process uses a global threshold 
which is compared to the maximum score. By this technique, the 
erratic points of the cloud are removed from the data. The cells 
with high scores are principally facade points with high density. 
Several techniques for the detection of outliers in laser point clouds 
can be found in (Sotoodeh, 2006) and (Sotoodeh, 2007). 
3.2 
Building footprints extraction 
3D cloud points 
Projection 3D to 2D 
T 
Hough counting space 
/r-nieans clustenng 
e 
Lines extraction 
0 
Figure 5: The main steps of our proposed approach for building 
footprint extraction. 
3.1.3 Exploiting the linearity of 3D data After the preced 
ing filtering steps, the frames have undergone a horizontal crop 
ping. The data structure represented by frames is now repre 
sented by a sequence of 3D points. We exploit the fact that in 
this representation facade points are locally aligned. We seek fa 
cade points which are principally organized vertically. Thus, the 
dataset in this sequence is parsed by triplets. The central point 
of each triplet is kept in the dataset if the triplet is aligned, other 
wise it will be removed from the dataset. Therefore, the coplanar 
points of the building facade are kept. Besides, we observe that 
the 3D points belonging to other linear structures are also kept. 
3.1.4 Mapping the 3D point cloud onto a 2D accumulator 
The goal of this step is twofold. Firstly, it aims at removing noisy 
and outlier points. Secondly, it gives a very compact representa 
tion of the filtered 3D points. Since we are interested in the verti 
cal structures that generally represent the facades, we project the 
3D cloud on a horizontal plane. More precisely, the 3D points are 
projected into a 2D grid to create an accumulation space. Each 
point of the cloud votes in one cell, giving a score. Only cells 
The goal is to automatically extract the building footprint using 
the 3D filtered points cloud contained in the compact 2D accumu 
lator. The building footprint is a set of 2D segments that can be 
detected in this 2D space. Recall that the vertical structure of the 
facades is captured by the scores of the cells. Each cell contains, 
if any, a set of 3D points P(x,y,z). Furthermore, an efficient 
extraction can be obtained by working with the barycenters (2D 
coordinates) of the cells together with their scores. Our approach 
combines the use of the counting space of Hough Transform, the 
fc-means clustering technique and the RANSAC method. We 
briefly describe these three techniques and their properties ap 
plied in our context. Figure 5 illustrates the main extraction steps. 
The Standard Hough Transform (SHT) allows the extraction of 
the 2D lines among 2D dataset points (Hough, 1962). In the 
field of our application, this method is currently used to detect 
the building boundaries in aerial images using the edge points. 
This method is also used to extract buildings in LIDAR data (e.g., 
(Tarsha Kurdi et al., 2007) and (Karsli and Kahya, 2008)).