Segments-based progressive TIN densification filter for DTM generation from airborne LIDAR data①

Xu Ying (許 穎), Yue Dongjie, Qiu Zhiwei

(*Ministry of Water Resources Key Laboratory for the Process and Control of Soil and Water Loss in Loess Plateau, Zhengzhou 450003, P.R.China) (**School of Earth Sciences and Engineering, Hohai University, Nanjing 211100, P.R.China)

Segments-based progressive TIN densification filter for DTM generation from airborne LIDAR data①

Xu Ying (許 穎)***, Yue Dongjie②**, Qiu Zhiwei**

(*Ministry of Water Resources Key Laboratory for the Process and Control of Soil and Water Loss in Loess Plateau, Zhengzhou 450003, P.R.China) (**School of Earth Sciences and Engineering, Hohai University, Nanjing 211100, P.R.China)

Airborne light detection and ranging (LIDAR) has revolutionized conventional methods for digital terrain models (DTMs) acquisition. Ground filtering for airborne LIDAR is one of the core steps taken to obtain a high quality DTM. This paper presents a segments-based progressive TIN (triangulated irregular network) densification (SPTD) filter that can automatically separate ground points from non-ground points. The SPTD method is composed of two key steps: point cloud segmentation and clustering by iterative judgement. The clustering method uses the dual distance to obtain a set of seed points as a coarse spatial clustering process. Then the rest of the valid point clouds are classified iteratively. Finally, the datasets provided by ISPRS are utilized to test the filtering performance. In comparison with the commercial software TerraSolid, the experimental results show that the SPTD method in this paper can avoid single threshold restrictions. The expected accuracy of ground point determination is capable of producing reliable DTMs in the discontinuous areas.

airborne light detection and ranging (LIDAR), point cloud, ground filtering, triangulated irregular network (TIN), digital terrain models (DTMs)

0 Introduction

Airborne light detection and ranging (LIDAR) technology makes it possible to acquire the Earth’s 3D surface information more directly and conveniently. Compared with photogrammetric systems and field surveys, a LIDAR system provides an accurate and fast alternation for obtaining information over large areas at high resolution and is more and more popular in generating digital terrain models (DTMs)[1]. So far, the applications of airborne LIDAR mainly include 3D reconstruction of a digital city[2], building reconstruction[3], coastline monitoring[4], power line reconstruction[5], forest inventorying[6], and so on. Among them, the extraction of accurate ground points, that is, ground filtering, is a key step of this process for the generation of the DTM. Airborne LIDAR technology is now used to produce regional and national DEM products in USA and European countries[7].

So far, many ground filtering approaches to airborne LIDAR data have been proposed in the existing literature[8]. Generally speaking, the ground filtering methods can be divided into four categories. For a slope-based filter, it is assumed that slopes between terrain and objects in a landscape are distinctively different. If the difference in elevation exceeds the preset threshold, the point with the lower elevation will be recognized as the terrain in generating the DTM[9]. In the interpolation-based approach, the best-fitting surface of the ground is generated by linear regression. Iterative computation can restrain high frequency data, nevertheless it may give rise to excessive erosion of terrain[10,11]. The morphology-based approach is based on a series of morphological operations to obtain the approximate terrain surface, such as openings and closings. Different window sizes provide a method of choosing these parameters when considering height differences. In general, a suitable structuring element plays an important role when considering filtering accuracy[12,13]. In the clustering-based approach, the structural differences between two points will not be the only criterion of terrain structure. This approach involves the relations among the set of points in the same class[14]. Thus it can be seen that the clustering segmentation-based approach is more suitable for distinguishing ground and non-ground points.

A segmentation method with local characteristics of point clouds is put forward by Sithole George, and later another method based on scan line segmentation is presented, respectively[15,16]. Under the assumption that the non-ground segments are higher than the ground segments, the clustering is implemented on the basis of the heights between different neighboring segments. In general, if only the topological relationship of the segments and the height information are considered in the process of clustering, unreasonable clustering results may be obtained or the loss of effective information may occur, so it is more reasonable to involve the characteristic information for clustering.

To generate high quality DTMs in complex terrain, this article develops a segments-based progressive TIN densification (SPTD) filtering algorithm by combining it with a clustering method. The SPTD method first analyses raw LIDAR data by removing outliers and multiple echo analysis. Ground seed segments are acquired through a clustering method considering the spatial attribute and the non-spatial attribute. The remaining segments are selected as the basic processing unit for the progressive TIN densification. The reliability and effectiveness of the algorithm proposed in this paper are verified by the corresponding experiments.

1 Segments-based progressive TIN densification filter

In this section, SPTD filter for distinguishing ground points and non-ground points for the generation of DTM from airborne LIDAR data is proposed. Firstly, point cloud data are described as an octree index structure and then segmented based on plane fitting. Secondly, a coarse spatial clustering process is implemented to obtain a set of seed points. Thirdly, instead of a single point, the segment region is selected as the basic processing unit for the densification of the terrain segments.

1.1 Obtaining the seed segments

1.1.1 Point cloud segmentation

The purpose of point cloud segmentation is to divide the input data into several clusters with the characteristics of connection and coherence. The segmentation method in this paper is based on the octree, and the concrete steps are described as follows:

a) A point cloud index vector is set up to store the point clouds index information; that is, every detected point cloud cluster will be preserved here.

b) In the process of segmentation, discrete points will be divided continuously until all subsets contain a plane only. That is to say, the segment points extracted from the whole point cloud data belong to the plane corresponding to the estimated parameters or the planar distance does not exceed a preset threshold. The estimation of the plane characteristic is finished by plane fitting, and PCA (principal component analysis) is used for plane fitting.

c) At last, it is necessary to generate connected graphs which are used to describe the adjacency relations between segment regions.

1.1.2 Integrative clustering

Point cloud clustering is to combine different groups on the basis of segmentation. The similarity of point data should be kept as weak as possible for different groups and as high as possible for the same group. As inherent dual attributes of spatial data, the spatial attribute requires a spatial adjacency for the similar elements, and the non-spatial attribute requires that the greatest similarity is maintained between the elements. When both of these attributes are considered, the approach is called integrative clustering. The normal vector, Gaussian curvature, and mean curvature, which indirectly reflect the non-spatial attribute characteristics of the points, are the geometric representation of the surface shape, so they can be accepted as the feature vector in the clustering process.

In this paper, let P be the set of 3D spatial elements denoted as pi(xi, yi, zi) and let P={p1, p2,…, pn}(n≥2); the dimension of non-space is m. According to the characteristics of the airborne LIDAR point cloud, the eigenvector ri=(xi, yi, zi, ai, bi, ci, Ki, Hi) obtained by PCA estimation is adopted, where (ai, bi, ci), Ki, Hiare normal vectors, and as the Gaussian curvature and mean curvature parameter of the point. Then, for 1≤i, j≤n, the distance between piand pjis expressed in

d(i, j)=

(1)

where ‖·‖ represents the two-norm, ppis the coordinate value of all points, pnis the normal vector of the corresponding points, and pcis the curvature of the corresponding points.

The detection of seed segments based on the integrative clustering is specified as follows:

(1) According to the results of octree segmentation, the initial k categories are obtained, and then the clustering centres are calculated and denoted as m1(0), m2(0),…, mk(0).

(2) The distance between each category and the adjacent categories is calculated on the basis of Eq.(1). If the distance is less than a certain threshold, the category and its adjacent category are merged; else, the process proceeds to the next step.

(3) In the light of step 1, the centres of each category are updated, and then the updated clustering centres denoted as m1(t), m2(t),…,mk(t) are obtained.

(4) Step 2 is repeated until the values of the category remain unchanged.

1.2 Densification of the terrain based on segments

For the rough classification, this paper proposes an iterative refinement judgment methodology with ground triangulation densification based on segment blocks. The progressive TIN densification proposed by Axelsson gradually generates triangulations with the original LIDAR point clouds data, preserving the corrective points as ground points in accordance with certain conditions and removing the other non-ground points[10]. This method has been successfully applied to the commercial software TerraSolid. However, the deficiency of the classic filtering algorithm inevitably leads to the misclassification of ground points and non-ground points. In order to overcome this shortcoming, this article generates a TIN with segment regions instead of single points. The ground clusters are selected on the basis of larger clusters.

1.3 Process of DTM generation

A flow chart of the main steps of the SPTD method is shown in Fig.1.

Firstly, the outliers of the LIDAR point clouds are removed by statistical analysis techniques. Secondly, the single and the last echo signals are selected as the experimental data based on multiple-echo information analysis[17]. Then the selected points are processed by the SPTD method. The advantage of this method is that the TIN generation uses segment regions instead of single points.

2 Experiments and analysis of results

2.1 Test data

The test data and reference data were acquired with an Optech ALTM scanner over the Vaihingen/Enz test field and Stuttgart city centre as part of the second phase of the OEEPE project[16]. These data from ISPRS Commission III, Working Group III, are employed to test the filtering effect of the SPTD method and to compare the DTMs with the classic filtering method in the meantime. In this paper, CSite2, sample 23, and sample 24, which include discontinuous terrain, are selected as the test data. The reference data generated by manually filtering the datasets contain some discontinuous terrain for testing the filtering accuracy, such as steep slopes and ridges, high frequency of relief, discontinuous ditches, and so on. In the datasets, all points are labelled as “ground points” or “non-ground points”. Detailed descriptions of the landscape features included are given in Ref.[18].

Fig.1 Flow chart of DTM generation by the SPTD method

2.2 Filtering

CSite2 is located in an urban area.Fig.2(a)-(d) shows the filtering procedure of the proposed filtering method. The LIDAR data are preprocessed before SPTD. In this process, the outliers are removed by the statistical analysis technique, as they are one of the circumstances that restrict the SPTD accuracy, and as the last and the first echoes are collected in the experimental data, the paper selects the last echoes for the next step by analysing the multiple echo information[17].

Fig.2(a) shows the pre-processing results. A rough classification identified as ground points is obtained as shown in Fig.2(b) in the filtering process of the SPTD method. The construction of TIN by the points in Fig.2(b) is shown in Fig.2(c). Finally, through the densification of the terrain based on segments, the airborne LIDAR point clouds classification is finished, as shown in Fig.2(d). The result of the filter on CSite2 suggests that the SPTD method is capable of removing a large proportion of object measurements. Obviously, the ground area consists of many major clusters, while the distribution of other points is scattered.

Fig.2 Filtering process for CSite2

2.3 DTM production

The terrain point clouds are obtained according to the point clouds classification. Three DTMs are computed: one with reference data, the second using the proposed method, and the last using the commercial software Terrasolid.Fig.3 and Fig.4 show the digital surface model (DSM) and the DTMs obtained by several filters of sample 23 and sample 24 respectively. From the difference between Fig.3(c) and Fig.3(d), it is obvious that the advantage of the SPTD method is that it can preserve the ground characteristics in areas with discontinuous terrain compared with Fig.3(b), as shown in the ellipse regions.

DTM of sample 23 generated by SPTD is closer to reference DTM than that obtained by the software. At the same time,Fig.4 reveals that there is less difference between the DTMs produced by the reference data and the Terrasolid method. The DTM generated by Terrasolid expresses a small difference in the discontinued areas, as shown in the black ellipse regions.

2.4 Performance analysis

The above qualitative assessments are carried out by visually comparing the SPTD results and the DTMs. The quantitative assessment of the filtering results is of the greatest importance for the generation of a high quality DTM. As described in the literature, the error is divided into three types, respectively: type I error (classify ground points as object points), type II error (classify non-ground points as ground points), and the total error is the percentage of any misclassified points[15]. The three types of errors of the SPTD method for all the samples from ISPRS benchmark dataset are listed in Table 1. Three kinds of errors can be obtained using Eq.(2):

Fig.3 Difference between reference DTM and generated DTM for sample

Fig.4 Difference between reference DTM and generated DTM for sample 24

(2)

Fig.3 and Fig.4 show the qualitative assessments for sample 23 and sample 24. In order to obtain the filtering results of quantitative assessment, Table 2 and Table 3 show the comparison of three errors of SPTD and the eight classical filtering for sample 23 and sample 24. The total errors of SPTD and the well-known filters (including MHC method) for the 15 reference samples are listed in Fig.5.

Table 1 Quantitative evaluation of filtering effect

Table 2 Comparison of three errors of SPTD and the eight classical filtering for sample 23

Table 3 Comparison of three errors of SPTD and the eight classical filtering for sample 24

Fig.5 Total error (%) of the filtering results compared with the data of 15 ISPRS samples

SPTD errors are shown in Table 1. Table 2 and Table 3 show the comparison of three errors of SPTD and the eight classical filtering. The results show that SPTD has the best classification results for sample 23 in terms of type II error, the type I error and total error are slightly higher than that of Axelsson, but much lower than those of the other seven methods (Table 2). In terms of total error, SPTD has the best classification results in most test sites (Fig.5). The suggested method can achieve high accuracies and the total errors are less than that obtained by the classical algorithm and the MHC (multiresolution hierarchical classification) algorithm proposed by Ref.[18] in most cases. SPTD has a heavy bias towards type II errors for sample 24 (Table 3), it still needs to be improved in areas of sparse vegetation. Therefore, the SPTD method is more suitable for high quality DTM generation.

3 Conclusions

In automatic DTM generation, many ground filtering methods have been developed to tackle the difficulty of separating terrain from non-terrain points, which is one of the important issues in LIDAR applications. The paper introduces a segments-based filtering algorithm dedicated to DTM generation in disconnected terrain. The filtering procedure is carried out using ISPRS CSite2. The resulting DTM is evaluated using the reference DTM and compared with the software DTM. A further performance evaluation is carried out using three types of errors. According to the study of the SPTD method, the improvement of integrative clustering and segments-based iteration can reduce the type I error, such result appears promising for computing high-quality DTMs in complex environments. Further researches will focus on the efficiency and robustness of SPTD based on the combination of GPU and image to complex landscapes.

[1] Guan H, Li J, Yu Y, et al. Dem generation from lidar data in wooded mountain areas by cross-section-plane analysis. International Journal of Remote Sensing, 2014, 35(3): 927-948

[2] Chen Z, Devereux B, Gao B, et al. Upward-fusion urban DTM generating method using airborne LIDAR data. Isprs Journal of Photogrammetry & Remote Sensing, 2012, 72(3):121-130

[3] Stal C, Tack F, Maeyer P D, et al. Airborne photogrammetry and LIDAR for DSM extraction and 3D change detection over an urban area: a comparative study. International Journal of Remote Sensing, 2013, 34: 1087-1110

[4] Chen X Y, Lai Z L, Li W H, et al. Research on some key technologies of features extraction from LIDAR data in coastal zone. In: Proceedings of the IEEE International Conference on Information Engineering & Computer Science, Wuhan, China, 2009. 1-3

[5] Jwa Y, Sohn G B, Kim H. Automatic 3d powerline reconstruction using airborne lidar data. International Archives of the Photogrammetry & Remote Sensing and Spatial Information Sciences, 2009, 38(P3/W8):105-110

[6] Liu Q W, Li Z Y, Chen E X, et al. Estimating biomass of individual trees using point cloud data of airborne LIDAR. Chinese High Technology Letters, 2010, 20(7): 765-770 (In Chinese)

[7] Lee I. A feature based approach to automatic extraction of ground points for DTM generation from LIDAR data. In: Proceedings of the ASPRS Annual Conference, Denver, USA, 2004. 23-28

[8] Li F. A Research on Filtering and Classification of Airborne LiDAR Point Clouds: [Ph.D dissertation]. Beijing: College of Geoscience and Surveying Engineering, China University of Mining and Technology, 2013. 65-75 (In Chinese)

[9] Susaki J. Adaptive slope filtering of airborne LiDAR data in urban areas for digital terrain model generation. Remote Sensing, 2012, 4:1804-1819

[10] Axelsson P. DEM generation from laser scanner data using adaptive TIN models. International Archives of Photogrammetry and Remote Sensing, 2000, 33:111-118

[11] Zhang X H. Theory and Method of Airborne LiDAR Measurement. Wuhan: Wuhan University Press, 2007. 96-99 (In Chinese)

[12] Chen C, Li Y, Li W, et al. A multiresolution hierarchical classification algorithm for filtering airborne LiDAR data. Isprs Journal of Photogrammetry & Remote Sensing, 2013, 82(82): 1-9

[14] Tóvári D, Pfeifer N. Segmentation based robust interpolation-a new approach to laser data filtering. International Archives of the Photogrammetry & Remote Sensing and Spatial Information Sciences, 2005, 36(W19): 12-16

[15] Sithole G, Vosselman G. Experimental comparison of filter algorithms for bare earth extraction from airborne laser scanning point clouds. ISPRS Journal of Photogrammetry and Remote Sensing, 2004, 59(1-2): 85-101

[16] Sithole G, Vosselman G. Filtering of airborne laser scanner data based on segmented point clouds. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2005, 36(3/W19): 66-71

[17] Darmawati A T. Utilization of Multiple Echo Information for Classification of Airborne Laser Scanning Data: [M. S. Dissertation]. Enschede: International Institute for Geo-information Science and Observation, 2008.35-40

[18] Sithole G, Vosselman G. The full report: ISPRS Comparison of Filters. International Society for Photogrammetry and Remote Sensing commission III, 2003, 6:1-29

Xu Ying, born in 1986. She received her B.S. and M.S. degrees from Henan polytechnic University in 2007 and 2010 respectively. Her research focuses on the point cloud data post-processing and feature detection from airborne LIDAR data.

10.3772/j.issn.1006-6748.2017.01.003

①Supported by the National Natural Science Foundation of China (No. 41174002), the Opening Fund of Key Laboratory of the Ministry of Water Resources(No. 2015003), and the Fundamental Research Funds for the Central Universities(No. 2014B38614)

②To whom correspondence should be addressed. E-mail: yuedongjie@163.com Received on Mar. 4， 2016