CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
70 
Figure 11: The application of the k-means clustering. 
As can be seen, the classical Hough Transform provided many 
2D lines (facade support) corresponding to the many local max 
ima in the Hough counting space. We can observe that both the 
curved facade and the partially occluded facade are modelled by 
several lines. However, by using our proposed approach based 
on k-means clustering, the correct and accurate 2D lines were 
obtained. As explained above, the 2D lines can be given either 
by the centroid of the cluster, its maximum or by the RANSAC 
technique. As can be seen in figure 10, the building footprint ex 
traction will be more precise using the RANSAC method. The 
maximum score method detects the line comprising the maxi 
mum of points, but it is not necessarily the correct 2D line. The 
information provided by the clustering method allows us to re 
fine the estimation of the facade lines by exploiting the number 
of points and the dispersion if the detected cluster (facade) within 
the RANSAC framework. 
Figure 11 shows the application of the k-means clustering algo 
rithm on the 3D data associated with the two facades. Figure 
11 .(a) depicts the validity score as a function of the number of 
clusters k. As can be seen the optimal value for k is 2. Figure 
11 .(b) shows the convergence associated with this optimum. The 
footprint lines extracted from this clustering are illustrated in fig 
ure 9. 
5 CONCLUSIONS AND FUTURE WORK 
We presented an approach for the automatic extraction of the 
building footprint in urban environments. This approach does not 
require previous knowledge of the number of facades in the input 
dataset. Moreover, the approach is robust to the heterogeneous 
densities of facade points. The proposed approach is based on 
fast filtering and feature extraction techniques. This stage consti 
tutes an essential task for 3D building modeling. Experimental 
results show the feasibility and robustness of the proposed ap 
proach on small islets of buildings. 
Future work may investigate the extension of the approach to 
buildings with a high complexity of shapes and the possibility 
of application to large areas because each islet of the buildings 
is delimited by its georeferenced trajectory. Furthermore, since 
outdoor squares inside the buildings are inaccessible areas for the 
vehicle, we plan to extend our approach to model full buildings by 
exploiting the terrestrial data and the corresponding aerial data. 
ACKNOWLEDGEMENT 
The authors would like to thank Bertrand Cannelle from IGN for 
his assistance with software and helpful discussions related to the 
data used in this work. 
REFERENCES 
Baz, I., Buyuksalih, G., Kersten, T. and Jacobsen, K., 2008. Doc 
umentation of istanbul historic peninsula by static and mobile ter 
restrial laser scanning. In: ISPRS08, p. B5: 993 ff. 
Boulaassal, H„ Landes, T., Grussenmeyer, R and Tarsha Kurdi, 
F., 2007. Automatic segmentation of building facades using ter 
restrial laser data. In: Laser07, p. 65. 
Bretar, F. and Roux, M., 2005. Extraction of 3D planar primitives 
from raw airborne laser data: a normal driven ransac approach. 
In: MVA, pp. 452—455. 
Cheng, L., Gong, J., Chen, X. and Han, P., 2008. Building bound 
ary extraction from high resolution imagery and lidar data. In: 
ISPRS08, p. B3b: 693 ff. 
Fischler, M. A. and Bolles, R. C., 1981. Random sample consen 
sus: a paradigm for model fitting with applications to image anal 
ysis and automated cartography. Commun. ACM 24(6), pp. 381 — 
395. 
Forgy, E. W., 1965. Cluster analysis of multivariate data: ef 
ficiency vs interpretability of classifications. Biometrics 21, 
pp. 768-769. 
Haala, N., Peter, M., Kremer, J. and Hunter, G., 2008. Mobile 
lidar mapping for 3D point cloud collection in urban areas: A 
performance test. In: ISPRS08, p. B5: 1119 ff. 
Hough, R, 1962. Method and means for recognizing complex 
patterns. In: US Patent. 
Karsli, F. and Kahya, O., 2008. Building extraction from laser 
scanning data. In: ISPRS08, p. B3b: 289 ff. 
Macqueen, J., 1967. Some methods for classification and analysis 
of multivariate observations. In: 5th Berkeley Symposium on 
Mathematical Statistics and Probability, Berkeley, CA. 
Pu, S., 2008. Generating building outlines from terrestrial laser 
scanning. In: ISPRS08, p. B5: 451 ff. 
Ray, S. and Turi, R., 1999. Determination of number of clusters in 
k-means clustering and application in colour image segmentation. 
In: Proceedings of the 4th International Conference on Advances 
in Pattern Recognition and Digital Techniques, pp. 137-143. 
Sester, M. and Neidhart, H., 2008. Reconstruction of building 
ground plans from laser scanner data. In: AGILE08. 
Sotoodeh, S., 2006. Outlier detection in laser scanner point 
clouds. In: International Archives of Photogrammetry, Remote 
Sensing and Spatial Information Sciences XXXVI-5, pp. 297- 
302. 
Sotoodeh, S., 2007. Hierarchical clustered outlier detection in 
laser scanner point clouds. In: Laser07, p. 383. 
Tarsha Kurdi, F., Landes, T. and Grussenmeyer, R, 2007. Hough- 
transform and extended ransac algorithms for automatic detection 
of 3D building roof planes from lidar data. In: Laser07, p. 407. 
Tarsha Kurdi, F., Landes, T., Grussenmeyer, P. and Smigiel, E., 
2006. New approach for automatic detection of buildings in air 
borne laser scanner data using first echo only. In: PCV06. 
Xu, R. and Wunsch, D., 2005. Survey of clustering algorithms. 
Neural Networks, IEEE Transactions on 16(3), pp. 645-678.