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.
