B. Babu Madhavan
Prof. Kazuhiko Yamamoto
HOIP Project, Dept. of Information Science
Faculty of Engineering, Gifu University, Japan
This research explains vision based semi-automatic construction of 3D-City models from airborne laser scanner (ALS) data. ALS data pre-processing involves noise removal by smoothening, edge-detection and vectorization for urban building boundary edges. Segmentation of ALS data performed to extract roof regions. Both the boundary and roof edges have been vectorised and polygons representing buildings obtained to compose 3D city models. Descriptions on the possible applications of the 3D urban models with special references to Virtual City models and Geographic Information Systems (GIS) have been provided.
About three years ago, airborne laser scanner systems (ALS) started to become available to the mapping and Geographic Information Systems (GIS) industries, and some researchers have started to include the DSM’s data in the research and development of automatic building extraction systems     . There are only a few studies solely based on Laser scanner surface data   . Helicopter based systems with higher resolutions of 5 or more measurements per square meter have been reported for 3D building modelling  . Within the automatic systems, aerial images, laser DSM, and 2D plans have been utilized alone or in combination to generate 3D building models. Automatic Systems working solely on the basis of Laser DSM’s have been reported . Laser DSM’s have the great advantage of representing 3D geometry directly. Also, it is possible to estimate the parameters of planar structures quite accurately with DSM of high resolution.
In the field of GIS not many computer vision oriented techniques have been employed in 3D urban modelling from Laser scanner research. Computer vision techniques such as boundary detection, roof edge detection based on segmentation and plan fitting, thinning, polygonisation and 3D model fitting are new to the GIS Laser Scanner data processing. Therefore these methods can be considered as new efforts for 3D building modelling. The present research methods extract edges, segment data into regions related to man-made buildings from laser radar images (Fig. 1). The segmentation results and edges are to be processed by fitting models to the data. Fitted models are to be used to build a photo-realistic model of the scene to be displayed for the purpose of scene characterization.
Fig. 1: Flow chart of vision based complex roof detection from ALS and 3D building modelling
Buildings in Japan
Many Japanese buildings and houses are planned based on a unit of approximately 2m x 2m in the horizontal directions and the building height is 2m/floor . Therefore the present airborne Laser scanner data (Airborne Helicopter; 200-400m aMSL; 2000/sec pulse length; 20/sec scan Time; 50cm x 50cm resolution) is expected to offer enough capability of detecting and modelling buildings in Japan. Thus the ALS data has sufficient spatial accuracy and resolution (Fig.2). The ALS system is capable of giving orthoimage by combining the position and altitude of ALS and a CCD array sensor mounted on the same platform (Fig.3).
Building data are detected by thresholding the DSM data. The threshold is chosen according to prior knowledge about the buildings. Since the interpretation based solely on range/height data is difficult, a colour air-photo (visible or infrared band) co-registered with the laser measurements has been utilised interpretation (Fig.3). A histogram-based data scaling has been carried out after the interpretation of colour air-photo of corresponding ALS image (Fig. 2).
Smoothing by Modified SUSAN filter
In the Smoothing over Univalue Segment Assimilating (SUSAN) noise filtering algorithm a Gaussian in the brightness domain has been employed for smoothing . This means that the SUSAN filter is like the sigma filter in the brightness and the spatial domains and the Gaussian filter in the spatial domain. Since laser data is elevation data with more speckle noise, it is decide to use median filter in the brightness domain . The SUSAN filter works by taking an average over all of the pixels in the locality that lie in the USAN. It is obvious that this will give the maximal number of suitable neighbours with which to take an average, whilst not involving any neighbours from unrelated regions. Thus all image structure should be preserved.
The pixel values in the laser data represent elevation and thus, the zero-crossings in the convolution output denote significant elevation changes . For example, the positive values (or positive valued regions) in the convolution output represent the objects above the datum. Lapalacian of Gaussian (LoG) edge detector has been used for edge detection in the laser data in the present research.
Fig. 5: Results of SUSAN filter
The LoG operator calculates the second spatial derivative of an image. This means that in areas where the image has a constant intensity (i.e. where the intensity gradient is zero), the LoG response will be zero. In the vicinity of a change in intensity, however, the LoG response will be positive on the darker side, and negative on the lighter side. LoG has the following advantages for extraction of buildings from laser data: Building edges are step edge and LoG is good for step edges. It generates closed edges, which avoids linking problems faced by some other edge detectors (Since all building edge is closed edge, closure property can also be used to get ride some non-building edges). It is insensitive to noise. The strength value of each LoG edge can be used to remove some noise edges, assuming building edges are strong edges.
Fig. 6: Results of edge detectors
Figure 6 illustrates the effects of LoG on ALS images. It was observed that the LoG output shows closed and thin boundaries of buildings.
Edge Thinning and Vectorisation
The thinning method, utilising mathematical algorithm of Zhang Suen Thinning has produced appreciable results . The Zhang Suen method tends to be better at extracting straight lines from a raster and resulted in more desirable vectors from an edge image, which comprises mainly straight lines. The fast algorithm presented here is able to separate different cells on the basis of intensity information and to measure their geometrical properties.
Fig. 7: Thinning effect
Once a raster has been thinned down to lines of single width pixels, and then vectorisation can be used to extract real vectors. The designed method converted images that contain inconsistent line weights and filled areas. This method converted images by tracing an outline of each element in the image. Figure 7 shows polygons of building boundaries after thinning process. Segmentation
Imprecisely, segmenting a range/laser radar image is the process of labelling the pixels so that pixels whose measurements are of the same surface are given the same label. The segmentation algorithm adopted here can be characterised as an example of the common approach to region segmentation by iteratively growing from seed regions suggested by Hoover et al . The segmenter works by computing a planar fit for each pixel and then growing regions whose pixels have similar plane equations. A two-stage process is used to compute a pixel’s normal. First, a growing operation is performed from the pixel, bounded by an N ´ N window. To join a bordering four-connected pixel must be within Tperp range units. This has the effect of separating “outliers” from “inliers” (with respect to the central pixel), where the outliers could be across a jump edge, or simple noise.
If less than 50% of the pixels within the window are inliers, then a single plane equation is fit to the pixels. If 50% or more of the pixels within the window are inliers, then a set of nine plane equations are computed using edge preserving sub-masks of the inliers in the N ´ N window. Improvement of this procedure is underway. Roof polygons obtained are shown in figure 8 (b).
ALS image DSM products and Applications
Some of the results of generated DSM of urban areas are shown in figure 9 (a-f). 3D Urban model form ideal completion of a GIS database. They are the appropriate data source for: – 1. primary acquisition of the building structure; 2. town planning applications including 3-D-visualisation of new buildings in the existing environment; 3.simulation: of transmitter placement for telecommunication, line of sight analyses; of air flow, pollution and noise distribution; of surface water flows to improve air quality by avoiding and eliminating “hot”-spots, areas of high concentrations of exhaust gases and reduced fresh-air supply (microclimate modelling).
Other applications include Emergency and Defence (Counter terrorism operations, Surveillance, Road traffic accident mapping, Crime scene forensic imaging, Disaster planning and scene pickup, Nuclear accident assessment), Engineering & Architecture (City council fixed asset management, Road surveys, Rail surveys, Water course analysis, Infrastructure survey – bridges, buildings, Urban environment impact studies, As-built compared with design survey, Site mapping) and Entertainment (Virtual set design for movie, Actor, equipment planning for movie production 3D gaming development, Virtual museum, Virtual tour guide Production).
This research explicated the automatic construction of building surface models of 3D-scene from laser scanner data. ALS data smoothening has been performed by noise removal filter called median_SUSAN. The detection, thinning and vectorization of Building boundary edges followed this. Segmentation of ALS data was performed to extract roof regions. Both the boundary and roof edges were vectorised and polygons representing buildings have been obtained.
The authors appreciate the research and funding facilities provided by the Japan Science and Technology (JST) and Softopia Japan, Japan. Mr. Kawano, Gifu University was very helpful in the computational part of this research.
- Gruen, A., Kuebler, O., and Agouris, P., 1995. Editors, Automatic Extraction of Man Made Objects from Aerial and Space Images. Birkhauser Verlag, Basel, 1995. (1)
- Wang, Z., 1998. Extracting building information from Lidar data. Symposium on Object Recognition and Scene Classification from Multispectral and Multisensor Pixels, ISPRS Commission III, Columbus, Ohio, USA. (2)
- Haala, N., Brenner, C., and Andres, K-H. 1998. 3D urban GIS from Laser altimeter and 2D map data, ISPRS J. Photogrammetry &Remote Sensing, 32, Part 3/1, pp.339-346. (3)
- Lemmens, M., H. Deijkers, and P. Looman, 1997. Building detection by fusing airborne laser-altimeter DEMs and 2D digital maps, ISPRS J. Photogrammetry and Remote Sensing, 32, Part 3-4W2, 29-42. (4)
- Mass, H-G, and Vosselman, G., 1999. Two algorithm for extracting building models from raw laser altimetry data, ISPRS J. Photogrammetry & Remote Sensing, 54, 153-163. (5)
- Brenner, C., 1999. Interactive Modeling tools for 3D Building Reconstruction, in: D. Fritsch & R. Spiller, eds, ‘Photogrammetric Week ’99’, Herbert Wichmann Verlag, Heidelberg, pp. 23-34. (6)
- Murakami, H., Nakagawa, K., Hasegawa, H., Shibata, T., and Iwanami, E., 1999. Change detection of buildings using an airborne laser scanner, ISPRS J. of Photogrammetry & Remote Sensing, 54, 148-152. (7)
- Maas, H. G., 1999a. Closed solutions for the determination of parametric building models from invariant moments of airborne laser scanner data. ISPRS Conference ‘Automatic Extraction of GIS Objects from Digital Imagery, München/Germany, 8-10. 9. 1999.Brunn, A., and Weidner, U., 1997. Extracting buildings from digital surface models, In: ISPRS J. Photogrammetry and Remote Sensing, 32, Part 3-4W2, 27-34. (8)
- Smith, S. M., and Brady, J. M., 1997. SUSAN – a new approach to low-level image processing. Int. J. of Computer Vision, 23(1): 45-78. (9)
- Babu Madhavan, B., 2001. Vision based 3D City Modelling by using ALS and SOS images. 2nd Workshop on HOIP, Softopia Japan, Japan. (10)
- Zhang, T. Y., and Suen, C. Y., 1993. Digital Image Processing, Gonzales and Woods R. E., (editors), Addison Wesley.(11)
- Hoover, A., Jean-Baptiste, G., Jiang, X., Flynn, P. J., Bunke, H., Goldgof, D. B., Bowyer, K., Eggert, D. W., Fitzgibbon, A., and Fisher, R. B., 1996. An experimental comparison of range image segmentation algorithms. IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 18, 7, 673-689. (12)