Wavelet-Based Clustering Method to Detect Building in Urban Area from Airborne Laser Scanner Data
Vu Tuong Thuy
Space Technology Applications and Research Program – Asian Institute of Technology
P.O. Box 4 Klong Luang, Pathumthani, 12120, Thailand
Environmental System Engineering – Kanazawa Institute of Technology
7-1,Ogigaoka, Nonoichi, Ishikawa 921-8501 Japan
Airborne laser scanner is an integrated system of GPS, INS and laser scanner to send the laser pulse and receive the laser hit on Earth surface. Consequently, the cloud points with X, Y and Z coordinates were acquired. After flying survey, simply speaking, the remained work to be done is to distinguish between ground surface points and object points on the surface. Nevertheless, it is not a simple processing as simply described due to the reflectance of laser hit on unpredictable distribution of objects on Earth surface. Several developed algorithms can be listed as (Haala et al. 1998) derived parameters for 3-D CAD models of basic building primitives by least-squares adjustment minimizing the distance between a laser scanning digital surface model and corresponding points on a building primitive; (Axelsson, 1999) introduced the classification algorithm based on the Minimum Description Length criterion for detection of structure; (Haala et al. 1999) integrated multi-spectral imagery and laser scanner data to extract buildings and trees in urban environment. Furthermore, one category of segmentation algorithm is the direct application on cloud points to eliminate the error introduced by interpolation such as (Maas and Vosselman, 1999) and (Sithole and Roggero, 2001). However, this type of algorithm has to pay a cost of computation time.
It is noted that most of developed algorithms is applied in European region either urban or rural sites. The distribution and the type of objects in the Asian region are completely different from the ones in European region. The obvious observation on the big Asian city is the high density of building with the interference between high buildings and very small houses. Some of developed algorithms may be successful applied in this complex scene. Originated from the mentioned point, this paper proposed the multi-resolution approach in segmentation laser points. The multi-resolution method allows the processing to analyze object at different resolutions. Therefore, it is possible to distinguish the objects of different sizes. A redundant wavelet analysis with B3 spline wavelet function (Starck and Murtagh, 1994) was utilized to form the multi-resolution method. Briefly, the wavelet-based algorithm in this paper, named wavelet-based clustering, is to smooth the cloud points, which were grid-based format, to find out the point clusters at different resolutions, and therefore, the object existences at different resolutions. Tracking the signatures over several resolutions, the required objects are easily to be detected from the rest ones.
The following parts of this paper are started with the description of proposed algorithm and the testing result applied in Shinjuku area, Tokyo, Japan. Shinkjuku area is a commercial and office area, which is covered by several towels, several smaller and lower buildings, with crowded activity of people. It is a typical and interesting site to test the proposed algorithm. Conclusion and several further improved points will end up this paper.
The complete processing to detect building is summarized in the flowchart in Figure 1.
Airborne laser scanner data used to process in this research was provided by Kokusai Kogyo Co., Ltd. Geomatics Department. This company accomplished the flying survey over most of Japan country. The parameter of the fly over our testing area is given in Table 1 below.
Table 1 – Airborne laser scanner data parameters
Scan Swath Width
Cross Track Spacing
Along Track Spacing
X, Y Positional Accuracy
0.3 m RMSE absolute
Z Positional Accuracy
0.15 m RMSE absolute
– Interpolation: according to (Behan, 2000), the planar interpolation method on triangulated irregular network (TIN) gives the most accurate interpolated image. This interpolation method is applied here with the basic resolution of 1 meter (see Figure 2).
Wavelet-Based Clustering Method to Detect Building in Urban Area from Airborne Laser Scanner Data
– Wavelet analysis: the purpose of this analysis is to find out the cluster pattern of laser points, i.e. smooth versions of elevation images, at different resolutions. This analysis applied a trous algorithm as described briefly below.
Let F(x) and Y(x) be scaling function and wavelet function, respectively. The scaling function is chosen to satisfy the dilation equation as follow.
where h is a discrete low pass filter associated with scaling function F. This equation shows the link between two consecutive resolutions, which are different by a factor of 2, by low pass filtering. Then, the smoothed data cj(k) at a given resolution j and at position k is the scalar product
In implementation, this smoothed data can be obtained by convolution
The difference between two consecutive resolutions is calculated as
Which is the definition of wavelet transform at resolution j. The wavelet function Y(x) is defined by
Assume the smooth operation is stopped at resolution p, the reconstruction formula of a signal is
The above wavelet transform, which is described for a single index can be extended to higher dimensional space. For example, in two-dimensional space, x in all equations above implies (x,y).
The smooth images by wavelet analysis at four consecutive resolutions are depicted in Figure 3. It is obvious to recognize the distribution of laser points, which is the buildings, in fact, in urban area. The small and low buildings gradually disappear when moving to coarser resolution. This is a clue for the multi-resolution segmentation in the following step.
– Multi-resolution segmentation: based on the signatures in multi-resolution space, the buildings were easily detected from the elevation images. This simple idea is illustrated in Figure 4 below.
The segmentation result presented most of main buildings in the study area. There were a few low buildings missing or being distorted due to their very low signatures. The detected buildings are showed in Figure 5 both in raster and vector format. Figure 5 also depicted the missing buildings at the top-right corner of images.
The detected buildings then were masked on laser cloud points to obtain the laser points that belong to buildings. The acquired laser data was quite low density with 0.2point/m2 approximately. Therefore, after being interpolated at resolution of 1m, there existed the confusion along the edge of buildings. Furthermore, the wavelet analysis, in fact, is one kind of linear multi-resolution approach. As a result, wavelet analysis introduces the distortion of object edge. A non-linear approach should be taken into account to improve this point. Being aware, when masking with laser points, there was a careful refinement the laser points along the edge of buildings. The fusion with aerial photo or existing 2D data can be a useful aid to correct the edges of detected buildings. Figure 6 below depicted the original digital surface model on the left and the perspective 3D detected building on the right. The digital surface model illustrated the very complicated scene of the study area, especially very small and low building locates beside the tower. In addition, this area also presented the complicated roads with different levels. This kind of object will be detected and presented in future paper.
The results of segmentation by applying multi-resolution approach showed quite good result in testing area. It is necessary to emphasize the purpose of this research is to detect the buildings in urban area. The other man-made object such as roads or high ways, which are also necessary for reconstruction of 3D city, will be detected in the further development of this algorithm. In addition, this algorithm analyzed laser points in grid format to reduce the computation time.
Conclusions and Recommendations
After several introductions to apply wavelet in segmentation of airborne laser scanner data (Vu, T.T. and Tokunaga, M. 2001, Vu, T.T. and Tokunaga, M. 2002), this research is a step forward to the real detection of specific man-made objects in urban area. In conclusion, the proposed algorithm successfully detected most of buildings in a testing area. The key point is how to detect over multi-resolution that is simple tracking the signature over multi-resolution space. However, this algorithm introduced the problem at the edge of objects. It is continued in development with the integration of non-linear multi-resolution approach and the fusion of some other existing data such as aerial photo or 2D vector data. Not only buildings, all of man-made objects in urban area will be detected in the further step of this algorithm to accomplish the all requirements of 3D city model.
- Axelsson, P., 1999. Processing of laser scanner data – algorithms and applications. ISPRS Journal of Photogrammetry & Remote Sensing, 54: 138-147.
- Behan, A., 2000. On the matching accuracy rasterised scanning laser altimeter data. In Proceedings of the XIXth congress of ISPRS, Amsterdam 2000,”International Archives of Photogrammetry and Remote Sensing”, XXXIII, part B 2, ISSN 0256-1840, pp 75-82.
- Haala, N. and Brenner, C., 1999. Extraction of buildings and trees in urban environment. ISPRS Journal of Photogrammetry & Remote Sensing, 54: 130-137.
- Maas, H. G. and Vosselman, G., 1999. Two algorithms for extracting building models from raw laser altimetry data. ISPRS Journal of Photogrammetry & Remote Sensing, 54: 153-163.
- Roggero, M., 2001. Airborne Laser Scanning: Clustering in Raw Data. International Archives of Photogrammetry and Remote Sensing, Volume XXXIV-3/W4 Annapolis, MD, 22-24 Oct. 2001: 227-232.
- Sithole, G., 2001. Filtering of Laser Altimetry Data using a Slope Adaptive Filter. International Archives of Photogrammetry and Remote Sensing, Volume XXXIV-3/W4 Annapolis, MD, 22-24 Oct. 2001: 203-210.
- Starck, J.L., and Murtagh, F., 1994. Image restoration with noise suppression using wavelet transform. Astronomy and Astrophysics, 288: 342-348.
- Vu, T.T. and Tokunaga, M. 2001. Wavelet and Scale-space theory in segmentation of airborne laser scanner data. Proc. of The 22nd Asian Conference on Remote Sensing,176-180, November 2001.
- Vu, T.T. and Tokunaga, M. 2002. Designing
of Wavelet-based Processing System for Airborne Laser Scanner
Segmentation. Proc. of International Archives of Photogrammetry,
Remote Sensing and Spatial Information Science, Volume: XXX IV
Part No.: 5/W3, ISSN: 1682-1777, February 2002.