Next Article in Journal
Optimized Contrast Enhancement for Infrared Images Based on Global and Local Histogram Specification
Previous Article in Journal
Classification of 3D Digital Heritage
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Building Detection Method Based on Semi-Suppressed Fuzzy C-Means and Restricted Region Growing Using Airborne LiDAR

1
School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China
2
Department of Oceanography, Dalhousie University, Halifax, NS B3H 4R2, Canada
3
Faculty of Resources and Environmental Science, Hubei University, Wuhan 430068, China
*
Authors to whom correspondence should be addressed.
Submission received: 12 February 2019 / Revised: 5 April 2019 / Accepted: 6 April 2019 / Published: 8 April 2019

Abstract

:
Building detection using airborne Light Detection And Ranging (LiDAR) data is the essential prerequisite of many applications, including three-dimensional city modeling. In the paper, we propose a coarse-to-fine building detection method that is based on semi-suppressed fuzzy C-means and restricted region growing. Based on a filtering step, the remaining points can be separated into two groups by semi-suppressed fuzzy C-means. The group contains points that are located on building roofs that form a building candidate set. Subsequently, a restricted region growing algorithm is implemented to search for more building points. The proposed region growing method perfectly ensures the rapid growth of building regions and slow growth of non-building regions, which enlarges the area differences between building and non-building regions. A two-stage strategy is then adopted to remove tiny point clusters with small areas. Finally, a minimum bounding rectangle (MBR) is used to supplement the building points and refine the results of building detection. Experimental results on five datasets, including three datasets that were provided by the International Society for Photogrammetry and Remote Sensing (ISPRS) and two Chinese datasets, verify that most buildings and non-buildings can be well separated during our coarse building detection process. In addition, after refined processing, our proposed method can offer a high success rate for building detection, with over 89.5% completeness and a minimum 91% correctness. Hence, various applications can exploit our proposed method.

Graphical Abstract

1. Introduction

Airborne Light Detection And Ranging (LiDAR) is an active Earth observing system that is composed of an Inertial Measurement Unit (IMU), Global Positioning System (GPS), and a laser scanner [1]. The primary purpose of LiDAR is to acquire high-accuracy three-dimensional (3D) geospatial data of the Earth’s surface. Despite the fast development and integration of hardware components over the past three decades, limitations still exist regarding data post-processing algorithms; the current software systems are far from automatic in processing, even if a single task, such as ground points extraction, is performed [2]. Object extraction from point cloud, in general, and particularly building detection, pose challenges to multiple research communities [3,4].
Buildings are considered to be one of the most important components in urban areas. As airborne LiDAR can now obtain high-density and high-accuracy roof data, building detection has become one of the key steps in LiDAR data processing. Building detection is a prerequisite of city planning, disaster assessment, digital mapping, transportation planning, and more [5,6,7]. In the LiDAR field, building detection means separating the points that belong to buildings from other points, which can also be termed as building extraction [8,9]. The International Society for Photogrammetry and Remote Sensing (ISPRS) has been committed to promoting the development of research that is related to automatic building detection and construction in complex scenes using airborne LiDAR and image data. During the last two decades, many researchers have uploaded their algorithms and experimental results that are based on test data provided by ISPRS, and the related comparative analysis on their precisions has been published [10]. However, the current research on building detection still faces two problems [11,12]:
(1) There are various roof types, and most existing algorithms only focus on plane roofs, which may be associated with a point cloud’s configuration. For example, the shape of curved roofs is similar to that of vegetation. In addition, roof material can affect data density and might lead to missing data, which presents difficulties in building detection.
(2) It is hard to achieve automatic building detection in complex scenes. Many existing algorithms are intricate and they have particular requirements for source data. In general, the automation of building detection is a long and arduous task.
Thus, it is of great importance to continue building detection research using airborne LiDAR data. The main contribution of this paper is to introduce a novel building detection method that is based on semi-suppressed fuzzy C-means clustering and restricted region growing. Unlike most previous building detection methods, our method can effectively extract the elliptical roofs and several attachment structures, like long-corridors and railings, which is beneficial to the subsequent three-dimensional building’s modeling. The remaining contents of this paper are organized, as follows: Section 2 briefly reviews the related work; Section 3 describes the principles and implementation steps of our proposed method in detail; Section 4 presents and analyzes the experimental results, as well as making comparisons with other algorithms; and, the main conclusions are provided in Section 5.

2. Related Work

As the main component in urban areas, buildings are some of the most important pieces of fundamental geographic information. The main data sources for acquiring 3D building information include image data and airborne LiDAR data [13]. Building detection has become a hot research issue in airborne LiDAR data processing. It should be noted that building detection research in the airborne LiDAR field mainly focuses on the extraction of points that are located on roofs and their attachments. Many airborne LiDAR-related building detection algorithms have been proposed, and they all can be categorized into two groups according to data source:
(1) Combining airborne LiDAR data and other data
In this group, image data is the most commonly used. The abundant spectral and texture information in image data can be considered as a helpful complement to precise height information in airborne LiDAR data [14]. However, in terms of improving classification, image data and the first echo information of LiDAR data are not significantly different when compared to separating buildings and vegetation only with the last echo information of LiDAR data [15]. Many researchers have adopted the normalized Digital Surface Model (nDSM) and normalized difference vegetation index (NDVI) to roughly remove vegetation areas, before refining the classification results by shape area thresholds [16], spectral values [17], or texture features [18,19]. Additionally, some researchers have attempted to combine Geographic Information System (GIS) data [20,21]. However, these methods unavoidably involve multi-source registration issues, which can lead to decreased precision.
(2) Only airborne LiDAR data
The common methods in this group include Random Sample Consensus (RANSAC) and three-dimensional Hough transform [11]. The RANSAC algorithm [22] is robust and widely adopted in building plane detection [23]. However, RANSAC is prone to finding pseudo planes and its computational efficiency significantly decreases with an increasing amount of point cloud data [24]. To solve this problem, [25] adopted weighted RANSAC to eliminate pseudo planes, and the weight function considered the relationship between points and planes. In their paper, they also defined an error suppression ratio coefficient to measure error distribution between the true plane and the pseudo plane. Their experimental results showed that the proposed method could improve the ability of RANSAC in plane identification efficiently. RANSAC has been combined with a least squares algorithm to extract both plane and curved roofs and enhance the robustness in building detection [26]. The classical Hough transform has been mainly used in two-dimensional images for describing lines, circles, or other shapes [27]. The Hough transform was introduced into point cloud data processing for detecting planes and spheres, which combined several constraint conditions, such as local planarity and normal vector consistency [28]. Hough transform was extended further to detect arbitrary shapes, independent of objects’ direction and scales [29]. However, their experimental results were easily affected by sampling intervals, when sampling in parameter space.
A region growing algorithm is also often used in building detection, and it is simple and easy to operate; however, it only works well when the initial seed points are of high quality, and it is prone to excessive growth [30]. A novel building detection method was proposed while using robust voxel-based region growing, and combining some geometric constrains, such as smoothness, continuity, and convexity [31]. Their experimental results showed it could work efficiently in a complex situation, with an overall quality measure better than 0.6. Clustering algorithms can also be adopted to measure the similarity between points and segmented LiDAR data [32,33]. A clustering algorithm was used for curved roofs to efficiently extract building area, by depicting the contour lines of the test area, clustering those contour lines with similar height values, and combining several geometric constraints, such as connectivity and smoothness [33]. In addition, the profile analysis method was introduced into point cloud data processing to identify plane features, but it was invalid for the roofs with complex shapes [34].
Supervised learning algorithms are also very popular in point cloud classification [9,35,36], which are generally composed of three steps, including sample training, feature extraction, and classification. However, the classification precision of these methods is greatly dependent on the quality of sample points, and the results are sometimes hard to explain [37].

3. Methodology

In general, building detection algorithms focus on the local features of a certain point to determine whether it belongs to buildings or not [9,25]. From a local perspective, the ground points show similar characteristics to building points, such as planarity and height continuity, which will affect the building detection results. Hence, in this paper, we provide a building detection workflow on the basis of ground point extraction (termed as filtering in the LiDAR field [3,38]). The whole process includes three main steps: filtering, coarse, and refined building detection. The details will be introduced in the following parts.

3.1. Filtering

Originally proposed by [39], an improved progressive TIN (Triangulated Irregular Network) densification (PTD) method for urban areas is proposed and adopted in the paper. In general, PTD is an iterative process, which includes three steps [39]: (1) searching for initial seed points in the preset grids, (2) constructing TIN by points in seed-point set, and (3) densification for the seed-point set. If no new point has been added into a seed-point set, iteration immediately terminates, otherwise, back to step (2). Here, one point Pi considered as a seed point should satisfy two essential requirements [39], as shown in Figure 1: (1) the distance d between Pi and its corresponding TIN (P1P2P3) is shorter than a threshold, (2) the angles α , β , γ between the corresponding TIN and lines connecting Pi to each vertex of the TIN are smaller than a threshold.
It should be noted that low noise points that are caused by the multipath effect could mainly affect the accuracy of PTD. In other words, seed points in step (1) should exclude those low noise points. Hence, in our improved PTD algorithm, an essential strategy is added in step (1), to judge whether the selected “seed” point Pi belongs to low noise points or not. To work efficiently, the strategy should be implemented based on sorting of regional height values. The strategy includes two necessary requirements: (1) variance of distances from its k (20) nearest points to the plane estimated by these points is smaller than a threshold (1 meter), (2) the height difference between the certain point to the highest point in its cylinder-based neighborhood (as shown in Figure 2a [37]) is smaller than a threshold (2.5 meters). If both of the requirements are satisfied, Pi can be considered as a seed point; otherwise, the search for the new seed point again in the seed-point set without Pi. To avoid impacts on subsequent building detection, those abandoned points are also labelled as ground points when PTD is finished.

3.2. Building Detection

After filtering, the remaining unclassified LiDAR points mainly belong to two types of ground objects, which are referred to as building and vegetation. An automatic coarse-to-fine building detection method is proposed in the paper to improve the flexibility and automation of the existed methods for complex roofs. To protect classification precision from sample selection, a clustering algorithm, semi-suppressed fuzzy c-means, is herein considered to separate building points from other points. Before that, feature extraction is an important and unavoidable step. Based on analyzing point neighborhood information, a region growing algorithm is adopted to refine the building detection results.

3.2.1. Feature Extraction

As Figure 3 shows, planar information of point cloud data, like two-dimensional coordinates, does not work in building detection. However, height value and its derivative statistics, such as height variance and average, present an obvious difference between buildings and vegetation from the visual point of view, as shown in Figure 3c. Thus, Table 1 lists the extracted features that were adopted in the paper and Figure 2 shows the neighborhood definitions. Details of these features can be found in [37,40,41].
(1) Height variance
This feature is the variance of point height in the neighborhood.
(2) Height range
This feature is the maximum height difference between the highest height and the lowest height.
(3) Planarity
λ P = λ 2 λ 3 λ 1
where λ 1 > λ 2 > λ 3 represent the eigenvalues of the covariance matrix. This value is large if the points in the neighborhood are coplanar.
(4) Sphericity
λ S = λ 3 λ 1
This value is large if the points in the neighborhood are discrete.
(5) Omnivariance
λ O = λ 1 λ 2 λ 3 3
This feature is the structure tensor of the surface.
(6) Change of curvature
λ C = λ 3 λ 1 + λ 2 + λ 3
This feature describes the surface variation.
(7) Surface roughness
This feature is the standard variance of the distance between the points and the fitted plane.
(8) Distance to plane
This feature is the distance between the current point and the fitted plane.
(9) Point density
This feature is the density of points within a given neighborhood.
(10) Point density ratio
This feature is the ratio of point density in cylinder-based neighborhood to point density in sphere-based neighborhood.
(11) Point count ratio
Similar to point density ratio, this feature means the ratio of point counts.

3.2.2. Coarse Building Detection Based on Semi-Suppressed FUZZY C-Means

Clustering algorithms belong to one of the most important unsupervised classification methods, which divide the sample space into several groups by a certain similarity measurement [32]. Among these algorithms, the fuzzy C-means (FCM) method is widely used [42]. FCM belongs to iteration algorithms and it is evolved from hard C-means (HCM) [43]. For binary classification, HCM divides the samples into two groups, 0 or 1, according to distance. Although HCM is simple and fast, the classification precision is not always promising. FCM is proposed based on HCM, which changes the values of class membership function from 0 , 1 to [ 0 , 1 ] [43]. Each sample point has a membership degree for each class, and for one certain point, the sum of membership degree for different classes is 1.
Fuzzy clustering issues can be presented as the following equation [43]:
min J m U , V = j = 1 n i = 1 c u i j m d i j 2
where X = x 1 , x 2 , , x n R s , s is the dimension of sample space, n is the number of samples, c is the number of clustering classes, m > 1 is fuzzy factor, d i j = x j v i is the distance between sample point xj and ith cluster center vi, V = v i j c × s ; similarly, v i R s , fuzzy membership matrix U = u i j c × n satisfies Equation (5), and uij is the membership degree of xj belonging to the ith class, which satisfies:
i = 1 c u i j > 1 , 1 j n
u i j 0 , 1 i c , 1 j n
j = 1 n u i j > 0 , 1 i c
Thus, FCM can be considered as a constrained optimization issue. The steps of FCM include [43]:
(1) Initialize the cluster center V(0), the iterative index k = 0, the maximum iteration number K, and the threshold ε > 0 .
(2) Calculate the membership degree matrix U(k) while using Equations (6) and (7). Given j , r , d i j k > 0 , then
u i j = 1 r = 1 c d i j k / d r j k 2 m 1
where i r , if there exists j and r values that make d i j k = 0 , then
u r j k = 1 , u i j k = 0 i r
(3) Compute the cluster center V i k + 1 using the following equation:
V i k + 1 = j = 1 n u i j m k x j j = 1 n u i j m k
(4) If V i k + 1 V i k < ε or k > K, iteration terminates immediately; otherwise, k = k + 1 and back to step (2).
FCM enhances the optimizing capability of HCM, but it decreases the convergence rate [42]. As such, a suppressed FCM (S-FCM) algorithm [42] has been proposed by introducing a competitive mechanism. S-FCM adds a modification process for membership degree U(k) in step (2) of FCM. The details can be described, as follows:
Given a certain sample xj, if the membership degree of xj belongs to the rth class, which is the maximum in all classes, the degree value is labeled as u r j , u r j = max i = 1 c u i j , and the membership degrees of other classes for xj are labeled as u i j , where 1 i c and i r . Modify u r j and u i j by Equation (9).
u r j = α u r j + 1 α u i j = α u i j i r
where α ( 0 α 1 ) is called the suppressed factor and 1 α is called the suppressed rate. 0.5 is the recommended α [42].
It should be noted that the membership degree values for all points are modified in each iteration [44]. S-FCM aims at improving the convergence rate of cluster centers. However, S-FCM only considers the absolute values of the maximum membership degrees, which leads to the premature convergence of cluster centers and unpromising clustering results. In addition, if the maximum of membership degrees for a certain sample xj is close to 0.5, xj may be located in the boundary of several clusters. In this situation, once all membership degrees are changed in this iteration, xj is likely to be categorized into the wrong cluster. Therefore, we added the suppressed threshold T α ( 0.5 T α 1 ), and Equation (9) can be rewritten as:
u r j = α u r j + 1 α , u r j > T α u r j , u r j T α u i j = α u i j , u r j > T α u i j , u r j T α
For a certain sample xj, only when its maximum of membership degrees is bigger than T α , the semi-suppressed FCM algorithm should suppress its non-maximal membership degree. In such a way, the convergence rate is improved, and samples with large membership degree values still determine the cluster centers. Subsequently, the unclassified points (except ground points) can be categorized into three groups: suspected building points, suspected vegetation points and unclassified points. To efficiently separate building points from vegetation points, we proposed a post-processing method that is based on height constraints. Firstly, a big grid index is constructed to contain building points, low vegetation points, and ground points as much as possible, and its radius can be set to five meters. If the height difference between one certain suspected building (or vegetation) point and its nearest ground point in the same grid is lower than two meters (the threshold is set with reference to [9,32]), this suspected point is not considered as a building (or vegetation) point. Secondly, a small grid index is constructed and its radius is set as twice the average point space. If the eight neighborhood grids of the current grid are all empty, and the point number in the current grid is fewer than three, all of the points in the current grid are considered as unclassified points. After post-processing, most low vegetation that is close to the ground can be removed, further reducing the impact of vegetation on subsequent building detection.

3.2.3. Refined Building Detection Based on Restricted Region Growing

After coarse building detection, the non-ground points are clustered into two groups: (1) mainly includes points located on roofs; and, (2) mainly includes points located in the building boundary and vegetation. It is noteworthy that building boundary points can be completed by region growing to ensure the completeness of building detection. Thus, the proposed refined algorithm is designed for the first group Lroof, and its steps include:
(1) For each xi in Lroof, if xj i j in its neighborhood satisfies the region growing requirements, and then add xj into Lroof and label xj as building points.
(2) If no new point has been added into Lroof, iteration immediately terminates; otherwise, back to step (1).
Here, the region growing parameters should follow two requirements to achieve restricted requirements: (1) improve the growth of plane regions and (2) slow down the growth of surfaces with large curvature. Three parameters have been used in the refined algorithm for each point to be classified, including (1) distance variance between points and the plane that is estimated by points in the neighborhood (0.4 meters), (2) curvature variance of neighborhood points (0.05 meters), and (3) the absolute height difference between the current point and the lowest (or highest) point (0.2 meters). Figure 4 shows the local area difference of building and non-building point clusters after restricted region growing, where green points belong to buildings and red points belong to non-building objects.
Area threshold (20 square meters) is also commonly used in building detection to remove small point clusters that may belong to vegetation or cars [5,7,30]. We adopt a two-stage strategy to remove too small non-building point clusters:
(1) Set the buffer distance and merge nearby point clusters. Here, buffer distance should be set as neither too small nor too large. If too small, several adjacent point clusters that belong to the same object cannot be merged, which may lead to decreased completeness of building detection. If too large, the non-building point clusters are likely impossible to remove. Thus, buffer distance is set as twice the average point spacing according to point density. When the buffer zones of two point clusters overlap, it should be considered that these two clusters are adjacent and can be merged together into one cluster. As shown in Figure 5, different point clusters have been presented in different colors, where blue, red, and yellow clusters are large point clusters, and green and white clusters are scattered non-building point clusters.
(2) Remove the non-building point clusters using an area threshold. After merging, the area of the building point clusters is large, in general, but the scattered non-building point clusters remain almost the same as before merging.
Due to the restricted region growing parameters that were adopted before, building points cannot be completely extracted. The missing building points are mainly located in two places: around roof feature lines and roof attachments. For the former situation, a minimum bounding rectangle is used to depict each point cluster, and these unclassified points that are located in the corresponding rectangle and close to the adjacent building are also considered as building points. However, unfortunately, if the points located in roof attachments are not detected during coarse building detection, and their heights are much higher or lower than the adjacent buildings, those points are unable to be extracted in region growing and remain missing, as shown in Figure 6, where the red points belong to buildings and white points belong to the unclassified group.

4. Results

4.1. Data and Environment Desciption

Two test datasets were used to verify the efficiency of our proposed method, including:
(1) Airborne LiDAR data provided by the ISPRS [45], composed of three reference data sets, as shown in Figure 7a–c, which are located in Vaihingen and obtained by Leica ALS50. The average point density is approximately 4–7 points/m2.
(2) Two Chinese datasets. The average point density is approximately 5 points/m2, as shown in Figure 7d,e.
Area 1: includes 37 buildings, mainly composed of dense and complex buildings and vegetation.
Area 2: includes 14 buildings, mainly composed of a few tall residence buildings that are surrounded by vegetation.
Area 3: includes 56 buildings, mainly composed of several connected buildings and vegetation.
Area 4: includes two complex buildings with elliptical roof structures and long-corridor attachments.
Area 5: includes 20 buildings, mainly composed of buildings and sparse vegetation.
All of the experiments were implemented in Matlab 2014b and the results were displayed in LiDAR_suite (software developed by the authors).

4.2. Accuracy Evaluation and Disscussion

Figure 8 shows the filtering results of five test datasets using hill shading. According to the visual results, the ground points have been extracted as much as possible, including low noise points. In addition, the terrain relief has also been completely preserved.
After filtering, the remaining points mainly include buildings, vegetation, and several tiny object points, such as cars and pedestrians. Firstly, coarse building detection was implemented for those remaining points. It should be noted that the membership degree threshold was set as 0.7, which is helpful for not only extraction of building seed points, but also for the merging of adjacent point clusters. In other words, when the maximum membership degree of one certain point is larger than the threshold, it will be labelled as building (or vegetation); otherwise, it remains unclassified. Figure 9 shows the results of coarse building detection for five test datasets, where the yellow points are mainly roof points, whilst the blue points are building boundary points and vegetation points. Note that the subsequent refined building detection algorithm was only implemented for yellow points.
Figure 10 illustrates the results of restricted region growing for five test datasets. To depict the comparison of building and non-building point clusters before and after the restricted region clearly grows, two colors are shown in the figure according to their true labels, where yellow means buildings and blue means non-buildings. As seen from the figure, the proposed restricted region growing strategy simultaneously ensures the rapid growth of building point clusters and slow growth of non-building point clusters. In addition, due to a few buildings and a big area difference between buildings and non-buildings, building points have been almost correctly detected in Area 2.
Besides, if the roof structure is relatively simple and consists of planes with low slope, the building points can be almost detected after the restricted region growing. However, if the roof structure is complex, for example, a dormer window on the roof, the points located in these attachments may be omitted.
A two-stage strategy was subsequently adopted, as shown in Figure 11. The buffer distance was set as twice the average point spacing. If the two-dimensional Euclidean distance between two points is shorter than the threshold, the two points were considered as belonging to the same cluster. Meanwhile, small grids were constructed to calculate the area of each point cluster. The remaining points after the two-stage strategy were considered as the building seed points.
Non-building point clusters can be removed after the two-stage strategy. However, some tiny buildings, such as the white circle in Figure 10b, were wrongly removed. Unfortunately, these points were unable to be added during the subsequent process. Finally, MBR was used to refine the results of building detection. Figure 12 shows the final results of the proposed building detection for five test datasets, where red rectangles in (a) to (c) are reference building vectors that are provided by ISPRS.
As seen from Figure 12, most buildings can be correctly detected by our proposed method. It should be noted that our method succeeded in the extraction of an elliptical roof and several attachment structures, like long-corridors and railings, as shown in (d) Area 4 and (e) Area 5. However, white circles in (d) and (e) present several wrongfully classified points. The reasons may include: (1) points within the white circle in (d) are located in a large square, which have not been efficiently eliminated during the proposed process; (2) points within the white circle in (e) are located on dense vegetation with a similar height as the adjacent buildings.
For quantitative evaluation, three indicators: completeness (Comp), correctness (Corr), and quality (Q), are adopted to evaluate the precision of the building detection results. The equations are described, as follows:
C o m p = T P T P + F N C o r r = T P T P + F P Q = T P T P + F N + F P
where T P is the number of correctly classified building points, F N is the number of omitted building points, and F P is the number of wrongly classified building points.
Table 2 lists the precision of our building detection method. For the ISPRS datasets, we compare our method with RANSAC [22], reference [46], reference [6], and reference [7].
Table 2 shows that our method had similar average values to other algorithms, except [46], as well as a better quality. For Area 1, Area 3, and average values, our method achieved the best completeness and the second-best quality. It should be noted that our method performed worse in the completeness and quality of Area 2, due to the missing building in Figure 10b. However, based on the complete extraction of other building points, the correctness of Area 2 remained satisfactory. For the two Chinese datasets, our method was able to achieve both reliable and promising accuracy with correctness and completeness for both better than 91%. Additionally, the quality of Area 4 was relatively low, due to the many building attachments.

5. Conclusions

Building detection has been a hot topic in the airborne LiDAR field for at least two decades. Due to varied types of buildings in the real world, although there are a lot of building-related methods, fully automatic and high-accuracy building-related algorithms are still urgently required. It should be noted that, from the view of a point cloud’s configuration, the building points are distinguishable from vegetation and ground points. In this research, we proposed a coarse-to-fine building detection method that is based on semi-suppressed fuzzy C-means and region growing. As the whole workflow was implemented on the basis of filtering, we also improved the classical PTD algorithm to extract the ground points as much as possible, also including low noise points. Based on filtering, the proposed semi-suppressed FCM was adopted to coarsely detect building points. Eleven features were generated from raw airborne LiDAR data to distinguish the building and non-building points in coarse building detection. The proposed region growing method perfectly ensures the rapid growth of building regions and slow growth of non-building regions, which enlarges the area differences between building and non-building regions. Refined building detection was performed based on restricted region growing. Furthermore, no sample points are herein required, which avoids probable different classification precisions that are caused by sample selection. The experimental results verified that our method could efficiently separate buildings from non-buildings in various scenes. In addition, our method also succeeded in the extraction of an elliptical roof and several attachment structures, such as long-corridors and railings, which would be beneficial to the subsequent three-dimensional building’s modeling. In terms of precision, our method achieved promising results for the ISPRS datasets and the two Chinese datasets, with completeness better than 89.5%, correctness better than 91.0%, and quality better than 85.2%.
However, in the current research, we mainly focused on urban datasets for the filtering and building detection process. Hence, how to detect buildings in mountainous regions with steep slopes efficiently is our future work. In addition, there are several parameters that are adopted in our method, which limited the full automation of building detection. We will also attempt to construct a self-adaptive building detection algorithm in the next step.

Author Contributions

Z.C. designed and performed the experimental analysis and wrote the article. H.M. supervised the analyses experiments and revised this article. L.Z. helped with the validation, writing and data tests.

Funding

This research was jointly funded by National Key R&D Program of China (2018YFB0504500) and Natural Science Foundation of China (Grant numbers 41601504 and 61378078).

Acknowledgments

The test datasets were provided by the International Society for Photogrammetry and Remote Sensing (ISPRS) Working Group. The article was edited by Ashley Veniott. Authors also would like to thank anonymous reviewers for their constructive comments for the manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Baltsavias, E.P. Airborne laser scanning: Existing systems and firms and other resources. ISPRS J. Photogramm. Remote Sens. 1999, 54, 164–198. [Google Scholar] [CrossRef]
  2. Shi, X.; Ma, H.; Chen, Y.; Zhang, L.; Zhou, W. A parameter-free progressive TIN densification filtering algorithm for lidar point clouds. Int. J. Remote Sens. 2018, 4, 1–14. [Google Scholar] [CrossRef]
  3. Zhang, J.; Lin, X. Filtering airborne LiDAR data by embedding smoothness-constrained segmentation in progressive TIN densification. ISPRS J. Photogramm. Remote Sens. 2013, 81, 44–59. [Google Scholar] [CrossRef]
  4. Khoshelham, K.; Nardinocchi, C.; Frontoni, E.; Mancini, A.; Zingaretti, P. Performance evaluation of automated approaches to building detection in multi-source aerial data. ISPRS J. Photogramm. Remote Sens. 2010, 65, 123–133. [Google Scholar]
  5. Zhang, Y.; Liu, X.; Zhao, Z. Roof plane extraction from airborne lidar point clouds AU-Cao, Rujun. Int. J. Remote Sens. 2017, 38, 3684–3703. [Google Scholar]
  6. Du, S.; Zhang, Y.; Zou, Z.; Xu, S.; He, X.; Chen, S. Automatic building extraction from LiDAR data fusion of point and grid-based features. ISPRS J. Photogramm. Remote Sens. 2017, 130, 294–307. [Google Scholar] [CrossRef]
  7. Huang, R.; Yang, B.; Liang, F.; Dai, W.; Li, J.; Tian, M.; Xu, W. A top-down strategy for buildings extraction from complex urban scenes using airborne LiDAR point clouds. Infrared Phys. Technol. 2018, 92, 203–218. [Google Scholar] [CrossRef]
  8. Tomljenovic, I.; Tiede, D.; Blaschke, T. A building extraction approach for Airborne Laser Scanner data utilizing the Object Based Image Analysis paradigm. Int. J. Appl. Earth Obs. Geoinf. 2016, 52, 137–148. [Google Scholar] [CrossRef]
  9. Zhou, Z.; Gong, J. Automated residential building detection from airborne LiDAR data with deep neural networks. Adv. Eng. Inform. 2018, 36, 229–241. [Google Scholar] [CrossRef]
  10. Rottensteiner, F.; Sohn, G.; Gerke, M.; Wegner, J.D.; Breitkopf, U.; Jung, J. Results of the ISPRS benchmark on urban object detection and 3D building reconstruction. ISPRS J. Photogramm. Remote Sens. 2014, 93, 256–271. [Google Scholar] [CrossRef]
  11. Tomljenovic, I.; Höfle, B.; Tiede, D.; Blaschke, T. Building extraction from Airborne Laser Scanning data: An analysis of the State of the Art. Remote Sens. 2015, 7, 3826. [Google Scholar] [CrossRef]
  12. Wang, R.; Peethambaran, J.; Chen, D. LiDAR point clouds to 3-D urban models: A review. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2018, 11, 606–627. [Google Scholar] [CrossRef]
  13. Sohn, G.; Dowman, I. Data fusion of high-resolution satellite imagery and LiDAR data for automatic building extraction. ISPRS J. Photogramm. Remote Sens. 2007, 62, 43–63. [Google Scholar] [CrossRef]
  14. Chen, L.C.; Teo, T.-A.; Shao, Y.-C.; Lai, Y.-C.; Rau, J.-Y. Fusion of LIDAR data and optical imagery for building modeling. Int. Arch. Photogramm. Remote Sens. 2004, 35, 732–737. [Google Scholar]
  15. Matikainen, L.; Kaartinen, H.; Hyyppä, J. Classification tree based building detection from laser scanner and aerial image data. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2007, 36, W52. [Google Scholar]
  16. Gilani, S.; Awrangjeb, M.; Lu, G. Fusion of lidar data and multispectral imagery for effective building detection based on graph and connected component analysis. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2015, 40, 65–72. [Google Scholar] [CrossRef]
  17. Vu, T.T.; Matsuoka, M.; Yamazaki, F. LiDAR signatures to update Japanese building inventory database. In Proceedings of the 25th Asian Conference on Remote Sensing, Istanbul, Turkey, 12–23 July 2004; Volume XXXV, pp. 607–610. [Google Scholar]
  18. Rottensteiner, F.; Trinder, J.; Clode, S.; Kubik, K.; Lovell, B. Building detection by Dempster-Shafer fusion of LIDAR data and multispectral aerial imagery. In Proceedings of the 17th International Conference on Pattern Recognition, Cambridge, UK, 26 August 2004; Volume 2, pp. 339–342. [Google Scholar]
  19. Peng, D.; Zhang, Y. Building change detection by combining lidar data and ortho image. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2016, 41, 669. [Google Scholar] [CrossRef]
  20. Schwalbe, E.; Maas, H.-G.; Seidel, F. 3D building model generation from airborne laser scanner data using 2D GIS data and orthogonal point cloud projections. In Proceedings of the ISPRS WG III/3, III/4, V/3 Workshop on Laser Scanning, Enschede, The Netherlands, 12–14 September 2005. [Google Scholar]
  21. Salimzadeh, N.; Hammad, A. High-level framework for GIS-based optimization of building photovoltaic potential at urban scale using BIM and LiDAR. In Proceedings of the International Conference on Sustainable Infrastructure, New York, NY, USA, 26–28 October 2017; pp. 123–134. [Google Scholar]
  22. Fischler, M.A.; Bolles, R.C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 1981, 24, 381–395. [Google Scholar] [CrossRef]
  23. Li, L.; Yang, F.; Zhu, H.; Li, D.; Li, Y.; Tang, L. An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells. Remote Sens. 2017, 9, 433. [Google Scholar] [CrossRef]
  24. Schnabel, R.; Wahl, R.; Klein, R. Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum 2007, 26, 214–226. [Google Scholar] [CrossRef]
  25. Xu, B.; Jiang, W.; Shan, J.; Zhang, J.; Li, L. Investigation on the weighted RANSAC approaches for building roof plane segmentation from LiDAR point clouds. Remote Sens. 2016, 8, 5. [Google Scholar] [CrossRef]
  26. Hofman, P.; Potůčková, M. Comprehensive approach for building outline extraction from LiDAR data with accent to a sparse laser scanning point cloud. Geoinformatics FCE CTU 2017, 16, 91–102. [Google Scholar] [CrossRef]
  27. Leavers, V.F. Which Hough transform? CVGIP Image Underst. 1993, 58, 250–264. [Google Scholar] [CrossRef]
  28. Vosselman, G.; Gorte, B.G.; Sithole, G.; Rabbani, T. Recognising structure in laser scanner point clouds. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2004, 46, 33–38. [Google Scholar]
  29. Khoshelham, K. Extending generalized hough transform to detect 3d objects in laser range data. In Proceedings of the ISPRS Workshop on Laser Scanning and SilviLaser 2007, Espoo, Finland, 12–14 September 2007. [Google Scholar]
  30. Vo, A.-V.; Truong-Hong, L.; Laefer, D.F.; Bertolotto, M. Octree-based region growing for point cloud segmentation. ISPRS J. Photogramm. Remote Sens. 2015, 104, 88–100. [Google Scholar] [CrossRef]
  31. Xu, Y.; Yao, W.; Hoegner, L.; Stilla, U. Segmentation of building roofs from airborne LiDAR point clouds using robust voxel-based region growing AU-Xu, Yusheng. Remote Sens. Lett. 2017, 8, 1062–1071. [Google Scholar] [CrossRef]
  32. Miliaresis, G.; Kokkas, N. Segmentation and object-based classification for the extraction of the building class from LIDAR DEMs. Comput. Geosci. 2007, 33, 1076–1087. [Google Scholar] [CrossRef]
  33. Song, J.; Wu, J.; Jiang, Y. Extraction and reconstruction of curved surface buildings by contour clustering using airborne LiDAR data. Optik 2015, 126, 513–521. [Google Scholar] [CrossRef]
  34. Wu, T.; Hu, X.; Ye, L. Fast and accurate plane segmentation of airborne LiDAR point cloud using cross-line elements. Remote Sens. 2016, 8, 383. [Google Scholar] [CrossRef]
  35. Guo, L.; Chehata, N.; Mallet, C.; Boukir, S. Relevance of airborne lidar and multispectral image data for urban scene classification using Random Forests. ISPRS J. Photogramm. Remote Sens. 2011, 66, 56–66. [Google Scholar] [CrossRef]
  36. Guo, B.; Huang, X.; Zhang, F.; Sohn, G. Classification of airborne laser scanning data using JointBoost. ISPRS J. Photogramm. Remote Sens. 2015, 100, 71–83. [Google Scholar] [CrossRef]
  37. Ma, H.; Cai, Z.; Zhang, L. Comparison of the filtering models for airborne LiDAR data by three classifiers with exploration on model transfer. J. Appl. Remote Sens. 2018, 12, 18. [Google Scholar] [CrossRef]
  38. Cai, Z.; Ma, H.; Zhang, L. Model transfer-based filtering for airborne LiDAR data with emphasis on active learning optimization. Remote Sens. Lett. 2018, 9, 111–120. [Google Scholar] [CrossRef]
  39. Axelsson, P. DEM generation from laser scanner data using adaptive TIN models. Int. Arch. Photogramm. Remote Sens. 2000, 33, 111–118. [Google Scholar]
  40. Kim, H.; Sohn, G. 3D classification of power-line scene from airborne laser scanning data using random forests. Int. Arch. Photogramm. Remote Sens 2010, 38, 126–132. [Google Scholar]
  41. Rutzinger, M.; Höfle, B.; Hollaus, M.; Pfeifer, N. Object-based point cloud analysis of full-waveform airborne laser scanning data for urban vegetation classification. Sensors 2008, 8, 4505–4528. [Google Scholar] [CrossRef]
  42. Fan, J.-L.; Zhen, W.-Z.; Xie, W.-X. Suppressed fuzzy c-means clustering algorithm. Pattern Recognit. Lett. 2003, 24, 1607–1612. [Google Scholar] [CrossRef]
  43. Bezdek, J.C. Pattern recognition with fuzzy objective function algorithms. Adv. Appl. Pattern Recognit. 1981, 22, 203–239. [Google Scholar]
  44. Zhao, F.; Fan, J.; Liu, H. Optimal-selection-based suppressed fuzzy c-means clustering algorithm with self-tuning non local spatial information for image segmentation. Expert Syst. Appl. 2014, 41, 4083–4093. [Google Scholar] [CrossRef]
  45. Cramer, M. The DGPF-test on digital airborne camera evaluation—Overview and test design. Photogramm. Fernerkund. Geoinf. 2010, 2010, 73–82. [Google Scholar] [CrossRef]
  46. Awrangjeb, M.; Fraser, C.S. Automatic segmentation of raw LIDAR data for extraction of building roofs. Remote Sens. 2014, 6, 3716. [Google Scholar] [CrossRef]
Figure 1. The diagram of progressive TIN (Triangulated Irregular Network) densification (PTD) algorithm.
Figure 1. The diagram of progressive TIN (Triangulated Irregular Network) densification (PTD) algorithm.
Remotesensing 11 00848 g001
Figure 2. Neighborhood definitions: (a) Cylinder-based neighborhood; and, (b) Sphere-based neighborhood. The red point means the current point and the blue points means its neighbor points. “r” represents the radius of the neighborhood.
Figure 2. Neighborhood definitions: (a) Cylinder-based neighborhood; and, (b) Sphere-based neighborhood. The red point means the current point and the blue points means its neighbor points. “r” represents the radius of the neighborhood.
Remotesensing 11 00848 g002
Figure 3. The different views of airborne Light Detection And Ranging (LiDAR) point cloud data: (a) Two-dimensional view; (b) Three-dimensional view; and, (c) Profile view. The color in the figure is displayed by height values, which ascend from blue to red.
Figure 3. The different views of airborne Light Detection And Ranging (LiDAR) point cloud data: (a) Two-dimensional view; (b) Three-dimensional view; and, (c) Profile view. The color in the figure is displayed by height values, which ascend from blue to red.
Remotesensing 11 00848 g003
Figure 4. Area comparison of building and non-building point clusters before (a) and after (b) the restricted region growing.
Figure 4. Area comparison of building and non-building point clusters before (a) and after (b) the restricted region growing.
Remotesensing 11 00848 g004
Figure 5. Results of merging the adjacent point clusters.
Figure 5. Results of merging the adjacent point clusters.
Remotesensing 11 00848 g005
Figure 6. The missing building points. The left figure (a) is the two-dimensional top view of several buildings and the right figure (b) is the profile view of points within white rectangle in the left figure.
Figure 6. The missing building points. The left figure (a) is the two-dimensional top view of several buildings and the right figure (b) is the profile view of points within white rectangle in the left figure.
Remotesensing 11 00848 g006
Figure 7. Test datasets adopted in our proposed method (colored by height values).
Figure 7. Test datasets adopted in our proposed method (colored by height values).
Remotesensing 11 00848 g007
Figure 8. Filtering results of five test datasets (units: meter).
Figure 8. Filtering results of five test datasets (units: meter).
Remotesensing 11 00848 g008
Figure 9. Results of coarse building detection for five test datasets.
Figure 9. Results of coarse building detection for five test datasets.
Remotesensing 11 00848 g009
Figure 10. Results of the restricted region growing strategy for five test datasets.
Figure 10. Results of the restricted region growing strategy for five test datasets.
Remotesensing 11 00848 g010aRemotesensing 11 00848 g010b
Figure 11. Results of the two-stage strategy for five test datasets.
Figure 11. Results of the two-stage strategy for five test datasets.
Remotesensing 11 00848 g011
Figure 12. Final results of the proposed building detection method for five test datasets.
Figure 12. Final results of the proposed building detection method for five test datasets.
Remotesensing 11 00848 g012
Table 1. The extracted features in building detection.
Table 1. The extracted features in building detection.
NeighborhoodCylinder-BasedSphere-Based
Features
Height-relatedHeight variance
Height range
Eigenvalue-relatedPlanaritySphericity
OmnivarianceChange of curvature
Plane-relatedSurface roughness
Distance to plane
Density-relatedPoint density
Point density ratio
OthersPoint count ratio
Table 2. The precision of our building detection method (%).
Table 2. The precision of our building detection method (%).
DataPrecisionRANSACAwrangjebDuHuangOurs
Area 1Comp870.083.893.691.895.6
Corr95.296.994.598.694.2
Q83.381.688.890.690.2
Area 2Comp91.085.794.687.389.5
Corr99.284.695.499.097.3
Q90.474.290.586.587.3
Area 3Comp94.778.693.990.295.1
Corr98.497.894.798.195.8
Q93.377.289.288.791.3
AverageComp90.982.794.089.893.4
Corr97.693.194.998.695.8
Q89.077.789.588.689.6
Area 4Comp////93.2
Corr////91.0
Q////85.2
Area 5Comp////96.9
Corr////91.2
Q////88.6

Share and Cite

MDPI and ACS Style

Cai, Z.; Ma, H.; Zhang, L. A Building Detection Method Based on Semi-Suppressed Fuzzy C-Means and Restricted Region Growing Using Airborne LiDAR. Remote Sens. 2019, 11, 848. https://0-doi-org.brum.beds.ac.uk/10.3390/rs11070848

AMA Style

Cai Z, Ma H, Zhang L. A Building Detection Method Based on Semi-Suppressed Fuzzy C-Means and Restricted Region Growing Using Airborne LiDAR. Remote Sensing. 2019; 11(7):848. https://0-doi-org.brum.beds.ac.uk/10.3390/rs11070848

Chicago/Turabian Style

Cai, Zhan, Hongchao Ma, and Liang Zhang. 2019. "A Building Detection Method Based on Semi-Suppressed Fuzzy C-Means and Restricted Region Growing Using Airborne LiDAR" Remote Sensing 11, no. 7: 848. https://0-doi-org.brum.beds.ac.uk/10.3390/rs11070848

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop