The Extraction of Vegetation Points from LiDAR Using 3D Fractal Dimension Analyses

Abstract

Light Detection and Ranging (LiDAR), a high-precision technique used for acquiring three-dimensional (3D) surface information, is widely used to study surface vegetation information. Moreover, the extraction of a vegetation point set from the LiDAR point cloud is a basic starting-point for vegetation information analysis, and an important part of its further processing. To extract the vegetation point set completely and to describe the different spatial morphological characteristics of various features in a LiDAR point cloud, we have used 3D fractal dimensions. We discovered that every feature has its own distinctive 3D fractal dimension interval. Based on the 3D fractal dimensions of tall trees, we propose a new method for the extraction of vegetation using airborne LiDAR. According to this method, target features can be distinguished based on their morphological characteristics. The non-ground points acquired by filtering are processed by region growing segmentation and the morphological characteristics are evaluated by 3D fractal dimensions to determine the features required for the determination of the point set for tall trees. Avon, New York, USA was selected as the study area to test the method and the result proves the method’s efficiency. Thus, this approach is feasible. Additionally, the method uses the 3D coordinate properties of the LiDAR point cloud and does not require additional information, such as return intensity, giving it a larger scope of application.

1. Introduction

The extraction and analysis of vegetation information is important in many fields of research. It is widely used in biomass and carbon estimations, hydrological model calculations, urban ecological assessments, etc. Accurately and entirely obtaining vegetation information is a difficult task [1,2,3,4]. Currently, there are various types of techniques for extracting and surveying vegetation information. These techniques involve, for example, detailed field surveys of all the vegetation in a district, which can provide the most accurate and detailed distribution of vegetation and a basis for classification [5]. Other techniques include using optical remote sensing images to extract the vegetation information based on distinctive spectral and textural features [6,7], and using Light Detection And Ranging (LiDAR) to obtain 3D point cloud data, designing a point cloud processing workflow to extract vegetation information [8,9,10]. LiDAR offers a fast and high-precision method for obtaining 3D information [11]. Unlike traditional observation techniques, LiDAR acquisitions can identify a large number of ground features and provide accurate spatial locations of surfaces and features. It is now widely used in digital mapping, forest monitoring, resource surveying, etc. [12]. LiDAR has been used for information acquisition and feature descriptions in an increasing number of studies, because of its advantages, including high precision, independence from environmental conditions, and its ability to obtain the vertical structure of surface features [13].

Currently, LiDAR studies focus on feature classification and building information extraction. For example, Yu et al. [14] divided their study area into water, vegetation, and other areas based on hyperspectral images, and extracted buildings according to height and roughness from LiDAR-derived DSM (Digital Surface Model). José Sánchez-Lopera and José Luis Lerma [15] used angular classification to differentiate buildings from vegetation and other small objects. For multi-class problems, researches have used many different approaches. Lafarge and Mallet [16] used an energy function and the Potts model to combine local features and local context. Rutzinger et al. [17,18] presented an object-based method for point cloud classification, which combined points clustering and full-waveform ALS data classification, and this method performed well for vegetation and building detection in urban areas. Additionally, multiple-entity features have been applied to improve both the accuracy and speed of computation by using several different entities in classifications from point clouds [19,20].

Moreover, researchers have undertaken exploratory work on the extraction of vegetation information from LiDAR data. Generally, studies focus on the following aspects: (1) Combining remote sensing, aerial imagery, and other spatial data, and using the LiDAR point cloud to extract vegetation information [21,22,23,24]; (2) Interpolating or processing the LiDAR point cloud into a raster image in the form of DTM (Digital Terrain Model), DSM, etc., and processing the data by remote sensing image classification methods to achieve indirect vegetation extraction from LiDAR point cloud data [25,26]; (3) Based on the traits of LiDAR data, using machine-learning methods for classification or using traits such as full-waveform and multi-echo LiDAR data as the basis of vegetation information extraction [27,28,29,30]. The core idea behind the above methods involves learning the remote sensing image classification technique and then applying it to the discrete point set from the LiDAR data. Many studies do not take full advantage of the vectorial 3D spatial distribution characteristics provided by the LiDAR point cloud. Meanwhile, some LiDAR data do not have full-waveform and multi-echo characteristics, thus not providing the required traits for vegetation information extraction. Thus, a method for extracting vegetation information using only the basic characteristics shared by most types of LiDAR point cloud data would be significant.

There are considerable differences among the morphological structures of different landscape features; for example, trees have a rough crown, smooth planes constitute buildings, while transmission lines present a linear form. These structures are reflected in the LiDAR point cloud. The type of feature determines the 3D distribution structure in the LiDAR data. Accordingly, the spatial morphology features in LiDAR data can be an important factor in distinguishing vegetation. Thus, in our study, we aim to explore a new method that takes advantage of the 3D spatial morphology features of tall trees as a distinguishing factor, and uses a 3D fractal dimension to conduct a spatial morphological description for vegetation extraction. The 3D fractal dimension, based on fractal theory, is a statistical index describing ground features’ irregularity and roughness. By using 3D fractal dimensions, vegetation can be extracted solely on the basis of its spatial morphology. Based on the considerations above, we first studied ground features’ overall morphological structure, and then used 3D fractal dimensions as indices to analyze ground features’ morphology and to distinguish between different types of features. A new method is presented for extracting tall trees. First, we pretreat LiDAR point cloud data by filtering to obtain non-ground points. Second, we separate the point set by regional growth division. Finally, we evaluate the morphological characteristics of the segmented objects using 3D fractal dimensions to determine the type of vegetation and to obtain the point set for tall trees.

2. Study Area and Data Source

The study area (Figure 1) is located in the town of Avon in New York, USA, covering nearly 0.309 km². Tall trees, shrubs, buildings, power lines, and other features can be found within the study area. With the abundant types and diverse set of surface features, this area is appropriate for extracting the vegetation features and analyzing the information.

Figure 1. Map and image of the study area.

Figure 1. Map and image of the study area.

The LiDAR point cloud data (Figure 2) were obtained from the free data provided by the Rochester Institute of Technology’s SHARE 2012 program (http://www.rit.edu/cos/share2012/). The average point cloud density of the LiDAR dataset covering the study area is 35.480 pts/m² with the WGS_1984_UTM_Zone_18N spatial reference system. Detailed information for the data is listed in Table 1. In this study, we have only used the spatial location information of the LiDAR point cloud covering the study area, without additional information such as the return intensity. Therefore, the approach presented in this paper will be applicable to most types of LiDAR data used in vegetation information extraction processes.

Figure 2. Scanning LiDAR data for the study area.

Figure 2. Scanning LiDAR data for the study area.

Table 1. Detailed LiDAR parameters for the study area.

Sensor	ALS60
Data capture date	9/12/2012
Total number of points	5,875,674
Minimum height (m)	162.140
Maximum height (m)	208.990
Median height (m)	179.264
Average point density (pts/m2)	35.480

Table 1. Detailed LiDAR parameters for the study area.

Sensor	ALS60
Data capture date	9/12/2012
Total number of points	5,875,674
Minimum height (m)	162.140
Maximum height (m)	208.990
Median height (m)	179.264
Average point density (pts/m2)	35.480

3. Methods

Our new method is divided into two inter-connected steps: first, the dataset is filtered to acquire non-ground points in pre-processing; second, 3D fractal dimension analysis is applied to the acquired non-ground points to obtain the vegetation point set. The first step provides input data (i.e., non-ground points) for the second step.

To extract ground features, we need to distinguish between ground points and non-ground points, which is achieved by LiDAR filtering [31]. Filtering helps to exclude the ground points to obtain the non-ground points. Based on the non-ground points, the accuracy and completeness of the extraction are significantly improved. Thus, filtering the LiDAR point cloud is very important for LiDAR vegetation extraction.

Ground points can be used to generate terrain models such as a DTM. However, non-ground points correspond to a variety of unknown types of feature. Vegetation information extraction involves identifying real ground feature points that belong to different classes of vegetation and separating them from the non-ground points. To extract vegetation entirely and exactly in our study, we combine 3D region segmentation and 3D fractal dimension analysis to evaluate the 3D spatial characteristics of the LiDAR point cloud. First, we use region segmentation to distinguish every feature and obtain some feature aggregation; then, we calculate the 3D fractal dimensions, analyze the 3D spatial morphology of features, and define the classification to identify the point cloud representing vegetation. Figure 3 shows the procedure of vegetation information extraction from the LiDAR point cloud.

Figure 3. Workflow of vegetation information extraction from LiDAR imagery.

Figure 3. Workflow of vegetation information extraction from LiDAR imagery.

3.1. LiDAR Data Preparation

Researchers have extensively studied LiDAR filtering. After ten years of development, numerous successful and efficient filter algorithms have been obtained [31,32,33,34,35], which can be generally divided into mathematical morphological filtering, progressive densification filtering, surface-based methods, and segmentation-based methods [36]. These algorithms are based on the spatial structure of the LiDAR point cloud, applying different mathematical principles to distinguish ground and non-ground points. In our study, we applied morphological gradient filtering [36] to filter the LiDAR point cloud. The algorithm was tested using sample data provided by the International Society of Photogrammetry and Remote Sensing (ISPRS) [37] and the result shows that it can distinguish between the majority of features and noise points. According to this test, the filtering rate is more than 90%, and complicated and low features can be filtered well. Therefore, morphological gradient filtering was applied during preprocessing of the LiDAR point cloud to distinguish the ground points and the non-ground points, a prerequisite for region segmentation and 3D fractal dimension analysis.

The core idea of morphological gradient filtering is to identify the variance of height and provide a basis for computational filtering. Then, a mathematical morphological computation is used to revise the gradient-mutational points. If the height variance was more than the height variance threshold, that point was recognized as a non-ground point to optimize the filtering process. Therefore, determining the proper threshold is key to the filtering process, and filtering parameters vary according to different terrains and feature-covers. The study area contains a variety of features, including forests and buildings. Thus, single parameters cannot distinguish between the ground and non-ground points. To solve this problem, we manually divided the study area into four sub-areas with similar terrain and feature characteristics to conduct the morphological analysis separately, and then combined these filtering outcomes to obtain the results of preprocessing the LiDAR data (Figure 4).

Figure 4. Sub-area division chart.

Figure 4. Sub-area division chart.

3.2. Three-Dimensional Fractal Dimension

Fractal geometry is a mathematical concept that is used to study irregular objects and chaotic motion [38]. It can be used to assess the complexity of objects. The theory has been widely used in geography, image processing, signal analysis, etc. Traditional Euclidean geometry takes the object as a regular geometric figure and the spatial dimension is an integer (e.g., one, two, or three dimensions). However, real-world objects are always irregular and complicated. Thus, the dimension is not an integer at all and fractal theory can be applied to describe the complexity and irregularity of objects.

A fractal dimension is a characteristic index measuring the fractal morphology of features [39]. The fractal dimension is an objective characteristic quantity characterized by scale invariance. It is an important index for describing irregularity and roughness. The spatial morphological structure of ground features constituted of LiDAR discrete points has its unique and class-related irregularity and roughness, such as the smooth planes of buildings, the irregular branches of trees, etc. The spatial morphological structure of these unique ground features can be described by a fractal dimension. In studies of fractal dimensions, some common definitions of fractal dimensions are the Hausdorff dimension, the box-counting dimension, the divider dimension, etc. Because the box-counting dimension is determined by the cover of an identical shape set, its calculation is easier than for other dimensions, and it is often used in geographical research. Therefore, we use the box-counting dimension (Figure 5) to calculate the 3D fractal dimensions of LiDAR feature points [40]. To calculate the box-counting dimension, first, we use a cube to completely cover the entire feature point cloud without cracks and count the non-empty cube number N; the dimension is defined as

D = lim (n→0) (log N / log(1/r))

(1)

where D is the box-counting dimension. D can be calculated when the side length r of the cube approaches 0.

Figure 5. Box-counting dimension calculating sketch map.

Figure 5. Box-counting dimension calculating sketch map.

In the theoretical formula, the box-counting dimension is given by the limit when the radius approaches 0. However, this situation is impossible in reality. From the box-counting dimension, the relationship between r and N is

log (N) = − D log(r) + C

(2)

where C is a constant. Thus, for a series of different side lengths, r, applying the least square method to simulate the linear functions of log (N) and log(r) gives the slope of the linear function as equal to the box-counting dimension D. It should be noted that, unlike continuous objects, the point cloud consists of discrete points. Moreover, when the side length of the cube is smaller than the length of the interval, the number of non-empty cubes is determined and will not change when the side length reduces. Additionally, the spatial characteristics allow the smallest side length of the cube to be equal to the average point distance of the LiDAR point cloud.

3.3. Region Segmentation and 3D Fractal Dimension Analysis

The filtering result of the non-ground points is the mixing point set of all kinds of features. It is impossible to judge the classification by discrete points and so it is necessary to divide the dataset into single feature sets to analyze the attribute. Applying the trait that points belonging to the same type would be aggregated, and the characteristic distribution of the discrete point cloud in 3D, we can use the region-growing method to divide the point set [41]. The detailed procedure is as follows: (1) Based on a certain side length, build a quick 3D mesh for the whole non-ground points region and form a hierarchical bounding box for the non-ground points. To avoid a large bounding box’s influence on the accuracy of the division, the side length of the bounding box is twice the average pitch of the LiDAR point cloud; (2) Select a non-empty bounding box as a seed and expand it in 3D spaces. If the neighboring bounding box is not empty, feature points in the bounding box are points for a single feature and this bounding box is a part of the non-ground points; (3) Set the new bounding box as the seed, and repeat procedure (2) until no new point is added. In order to avoid the bounds of some features from becoming tangled and connected with each other in the expansion procedure, an expansion threshold must be set for the bounding box. If the number of points in the box is smaller than the threshold, this bounding box must be considered to be located on the edge of the feature and is not expandable (Figure 6).

Figure 6. Box-counting dimension calculation sketch map.

Figure 6. Box-counting dimension calculation sketch map.

After obtaining a single type of feature by region segmentation, it is possible to calculate 3D fractal dimensions to describe the spatial shape of this kind of feature to define their class. In order to explore the different 3D fractal dimensions of features, region segmentation and 3D fractal dimension evaluations for trees, shrubs, buildings, power lines, and a variety of other features for different point densities were conducted. According to the variation of ground features’ 3D fractal dimensions at different point densities, we divided 3D fractal dimensions into distributions for high, medium, and low point densities (Table 2).

Table 2. Density range in three different conditions.

	High Density	Medium Density	Low Density
Point density (pts/m2)	≥20	5–20	≤5

Table 2. Density range in three different conditions.

	High Density	Medium Density	Low Density
Point density (pts/m2)	≥20	5–20	≤5

Figure 7 shows that 3D fractal dimensions of different features have their own distribution range, which match their specific spatial distribution morphology. The intervals do not overlap among features with obvious characteristics, making identification possible. Under the three point cloud densities, the 3D fractal dimensions of trees are the largest, those of buildings are intermediate, and those of power lines are the smallest. This is consistent with the actual situation of practical features. In reality, wires consist of poles, wires, and other one-dimensional lines. These shapes are simple to identify compared with other features. Houses consist of walls, roofs, and other two-dimensional surfaces. However, the shapes of trees are complicated and ground surfaces are irregular. Laser points falling on them are not only distributed on the surface but also within trees. These complex shapes determine the high 3D fractal dimension of trees. Shrubs are shorter than tall trees, and their surfaces are irregular. However, because of the limitations of the point density or blocking by other ground features, the number of discrete points falling on or within shrubs is often smaller than for trees. The 3D fractal dimension of shrubs ranges between that of trees and buildings, and may even coincide with trees that have a low-dimensional fractal dimension. That is because some low trees have shapes similar to shrubs and therefore similar 3D fractal dimensions. Nevertheless, there is a significant difference between shrubs and trees. Under different point cloud conditions, the 3D fractal dimensions of trees are unique and therefore easily identified. Hence, we use 3D fractal dimensions to extract information related to tall trees.

Figure 7. Statistil graphs of diverse features’ 3D fractal dimension distributions: (a) high-density; (b) medium-density; (c) low-density.

Figure 7. Statistil graphs of diverse features’ 3D fractal dimension distributions: (a) high-density; (b) medium-density; (c) low-density.

Meanwhile, the lower the point density, the smaller the distribution area of the 3D fractal dimension (Figure 8). For high, medium, and low densities, the 3D fractal dimensions are distributed correspondingly between 1.47–1.92, 1.35–1.83, and 1.29–1.74, respectively. The range of 3D fractal dimensions has a left-shift phenomenon. Additionally, the smaller the point cloud density, the larger the difference in 3D fractal dimensions between tall trees and other types of ground features and vice versa. Especially under low-density point cloud conditions, the distribution extent of a ground feature’s 3D fractal dimension may expand, leading to a decrease in the difference in the 3D fractal dimensions among different types of ground features. Under specific point cloud conditions, it is necessary to apply the corresponding 3D fractal dimension to extract information related to tall trees to ensure the result is complete and accurate.

Figure 8. Changes in the distribution range of the different features’ 3D fractal dimensions for the three point cloud density conditions: (a) tree; (b) brush; (c): house; (d) electric line.

Figure 8. Changes in the distribution range of the different features’ 3D fractal dimensions for the three point cloud density conditions: (a) tree; (b) brush; (c): house; (d) electric line.

According to the analysis above, we obtained the distribution and variation pattern of ground features’ fractal dimensions. By applying these dimensions to analyze the ground features’ type, tall tree points can be distinguished from other point types, and the extraction of tall trees from the LiDAR point cloud is achieved. The extraction process presented in this paper is summarized as follows:

(1) Preprocessing of the LiDAR point cloud. Use a filter on the original LiDAR point cloud to obtain a complete set of non-ground points, which provides the basic data for the classification of the point cloud.

(2) Region growing segmentation on LiDAR non-ground points. Use region growing segmentation to segment the original discrete points into “ground feature sets” consisting of several point set features, which provides the object for the spatial morphological analysis of ground features.

(3) Spatial morphological analysis and tall tree extraction on LiDAR non-ground points. Use 3D fractal dimensions to perform a spatial morphological evaluation on ground features consisting of LiDAR points, and then distinguish between the different types of ground features according to their 3D fractal dimension distribution characteristics, allowing tall trees to be extracted.

4. Results and Discussion

4.1. Vegetation Extraction Results

By using a morphological gradient filter test to preprocess the test data, we obtained all non-ground points (Figure 9), which provides the starting point for a spatial morphological analysis of ground features.

Figure 9. Non-ground points (a) and ground points (b) after filtering.

Figure 9. Non-ground points (a) and ground points (b) after filtering.

Then, the non-ground points were segmented using region growing, and a 3D fractal evaluation was performed to achieve the 3D fractal dimension distribution (Figure 10).

Owing to the high average point density of LiDAR data in the study area, our study uses the 3D high-density point cloud fractal dimension (1.68–1.92) to study tall trees. The result is shown in Figure 11.

Figure 10. 3D fractal dimension distribution in the study area.

Figure 10. 3D fractal dimension distribution in the study area.

Figure 11. Tall trees point set.

Figure 11. Tall trees point set.

4.2. Accuracy Assessment

The result shows that the tall trees were extracted well. The extraction results are fairly complete and few other ground features are mixed in the result point set. Further quantitative assessment of the extraction results is carried out by calculating the accuracy and completeness. The reference data are classified point sets obtained from human visual interpretation, on the basis of LiDAR point cloud and a high-resolution remote sensing image. The results were analyzed using the Error Matrix Method (EMM) [42], and the form of the EMM employed in this study is listed in Table 3.

Table 3. The form of the Error Matrix Method (EMM).

		Classification Results
		Tall Trees	Non-Tall Trees
Reference data	Tall trees	A	B
	Non-tall trees	C	D

Table 3. The form of the Error Matrix Method (EMM).

		Classification Results
		Tall Trees	Non-Tall Trees
Reference data	Tall trees	A	B
	Non-tall trees	C	D

A is the number of correctly classified tall tree points, B is the number of tall tree points that were wrongly classified as other types, C is the number of non-tall tree points that were wrongly classified as tall trees, and D is the number of correctly classified non-tall tree points. According to the EMM, the completeness I, accuracy E, and comprehensive assessment index Kappa for the extraction of ground features can be calculated using

I = A ÷ (A + B)

E = A ÷ (A + C)

(3)

Kappa = (S× (A + D) – ∆) ÷ (S ² – ∆)

where S = A + B + C + D, and ∆ = (A + B) × (A + C) + (B + D) × (C + D).

According the form of the EMM employed in this research, the counted results for extracted tall trees are listed in Table 4.

Table 4. The evaluation of the extraction of tall trees.

		Classification Results
		Tall Trees	Non-Tall Trees
Reference data	Tall trees	3093606	137046
	Non-tall trees	252747	994201
Completeness	95.57%	Results	91.83%
Index Kappa		0.8006

Table 4. The evaluation of the extraction of tall trees.

		Classification Results
		Tall Trees	Non-Tall Trees
Reference data	Tall trees	3093606	137046
	Non-tall trees	252747	994201
Completeness	95.57%	Results	91.83%
Index Kappa		0.8006

4.3. Error Analysis and Discussion

Table 4 shows that the accuracy and completeness of the extraction are high, achieving over 90%, and demonstrating the feasibility and effectiveness of our extraction method. However, the fact that the morphology of a few short trees is similar to shrubs means that some of the shrub points were mistakenly classified as tall trees (Figure 12a). Meanwhile, tall trees located on boundaries were misclassified as non-vegetation points because of the incompleteness of their morphology (Figure 12b). Generally, tall trees with a complete morphology in the study area were successfully separated from other ground features using 3D fractal dimensions. In addition, the higher the density of the point cloud, the better the results will be, because the irregularity and roughness of the tall trees’ morphology will become more obvious.

Our new method has the following characteristics: (1) In contrast to some other methods, the conditions for input data are simple with no support required from remote sensing and aerial imagery. Moreover, the LiDAR cloud data does not need to be full-waveform, meaning this method can be applied to most LiDAR data to extract the required features. (2) The evaluation standard is the 3D morphological trait of the LiDAR point cloud itself. Instead of considering each discrete point or its derived image, we start from ground features’ overall morphological structure. This method focuses on the description of the 3D morphology of tall trees in the point cloud. The effect is comprehensive and accurate. (3) In the computational process, there is no requirement to build a TIN or other raster grids to organize the point cloud. Thus, the procedure has the advantages of being easy and quick to implement.

Figure 12. Error types for tall tree extraction: (a) Shrubs misrecognized as tall trees; (b) Missed tall trees.

Figure 12. Error types for tall tree extraction: (a) Shrubs misrecognized as tall trees; (b) Missed tall trees.

This paper focuses on discussing the feasibility of extracting tall tree points from LiDAR data using 3D fractal dimensions. There are various ground features and morphologically intact terrain in the study area. The feasibility of extracting tall tree points using 3D fractal dimensions has been demonstrated in the study area and this approach achieved good results. However, because of the limited area and number of ground features in the study area, using 3D fractal dimensions to extract tall trees in more complex scenarios has not yet been tested. Considerable additional work is needed in other study areas with different features in order to examine the wider applicability of this approach. In addition, further characteristics of ground features’ morphological structures may be discovered in different aspects, and could be combined with those in 3D fractal dimensions, potentially resulting in a better classification result. Further research on the segmentation of non-ground points to improve the accuracy of 3D fractal dimension evaluation would also be informative. These considerations provide potential directions for future research.

5. Conclusions

This study generated a new approach to extract vegetation features from the LiDAR point cloud. The data were first preprocessed to obtain the non-ground points through filtering. The non-ground points were then divided using region growing segmentation and evaluated to obtain 3D fractal dimensions. All features were finally differentiated to extract vegetation. According to the analysis of 3D fractal dimensions for different features, each type of feature has a unique distribution and variation trend in its 3D fractal dimensions. Tall trees, because of their complex shape and rough surfaces, have larger 3D fractal dimensions than some other features with simpler shapes or smoother surfaces. Under different point densities, the medium 3D fractal dimension of tall trees is approximately 1.74. Additionally, the smaller the point cloud density, the larger the difference in 3D fractal dimensions between tall trees and other types of features. Based on the characteristics of tall trees’ 3D fractal dimensions discussed here, our method was tested and the results showed an accuracy and a completeness of over 90%. This method takes advantage of the 3D spatial morphology features of tall trees to extract them from the LiDAR point cloud data, and its efficiency is proved.