Objective

2

Street trees have played a key role in the urban forest resource inventory. Traditional methods of street tree detection and survey are based on 2D satellite images

which have low resolution and lack 3D information. At present

mobile laser scanner systems have been used to successfully collect the 3D side information of urban street trees at a low cost and high efficiency. Hence

this study uses a hierarchical clustering approach to extract street tree stems from mobile laser radar (LiDAR) point clouds. This study proposes a bottom-up hierarchical clustering method to extract urban street trees from mobile laser scanner point clouds. The proposed algorithm calculates the cost of different cluster combination and optimizes the cluster merging.

Method

2

There are three main steps in the proposed tree stem extraction. The first preprocessing step is to filter noise and ground points to reduce the calculation complexity. The noise point filtering is based on the mean

μ

and standard deviation

σ

of

K

-nearest neighbor points. A point is considered to be an outlier if the average distance to its

K

-nearest neighbors is above the specified threshold. Points that fall out of the range between

μ

-

σ

and

μ

+

σ

are regarded as noise points. To remove ground points

we analyze the elevation histogram of points. The second step is to group points from the same tree into one unit based on the clustering approach. Each cluster contains one unique point. The proximity matrix is calculated iteratively. If the cluster set is converged (i.e.

the number of clusters is stable)

the algorithm will output the clustering results; otherwise

the algorithm goes to the proximity matrix calculation and repeats the above-mentioned steps. The third step is the refinement of results. Given that pole-like objects tend to be regarded as tree stems

we analyze the point distribution. The method is based on the kurtosis of point in the vertical direction. If the kurtosis of a candidate tree cluster falls in

μ

k

-1.5

σ

k

and

μ

k

+ 1.5

σ

k

this cluster will be regarded as a tree; otherwise

this cluster will be regarded as a false tree.

μ

k

and

σ

k

are the mean and standard deviation kurtosis of a candidate tree cluster

respectively. The proximity matrix required for the hierarchical clustering to measure the difference between clusters is based on the Euclidean distances and the principal direction of local points. The main contribution is to minimize the cluster combination cost by solving the matching problem in graphs.

Result

2

To evaluate the tree stem clustering

the proposed algorithm is used on two urban scenes. The first scene is from an open benchmark located in Paris

the collection system is mobile laser scanning(MLS)

and the date is in January 2013. The second scene is collected by a wearable laser scanning (WLS) system. The WLS device used to perform the study was the ZEB-REVO lightweight mobile laser scanner by GeoSLAM. The proposed algorithm succeeds in extracting 85 out of 96 tree stems from the first dataset and 118 out of 118 tree stems from the second dataset. In the urban scene

if the tree is close to the LiDAR sensor (< 10 m)

tree stems and branches will be extracted effectively. However

if trees are far from sensors (> 30 m)

the extraction results will contain the main stems and branches only due to the sparse tree points. In the two experimental scenes

the proposed algorithm effectively extracts trees within 50 m

which means that the algorithm works well in an urban street scene. The main contribution is to minimize the cluster combination cost by solving the matching problem in graphs. The proposed bottom-up clustering strategy succeeds in extracting points from the stem regions and achieves the completeness of 94.8%

correctness of 98.5%

and F-score of 0.97 on urban road environments. Given that the proposed results are based on the optimal cluster combination

the robustness of the segmentation of scatter points will be higher than others. The segment of stems is based on the principal direction; therefore

the results will not be affected by the holes or incomplete regions. Moreover

the proposed stem cluster does not rely on a fitting approach. Therefore

the proposed method works for different tree models or structures.

Conclusion

2

The proposed tree stem clustering does not require any prior knowledge of trees (e.g.

the number of trees

the location

and geometric shape information). The proposed method is based on the Euclidean distance and principal direction to formulate the proximity matrix and uses the perfect matching in a bipartite graph to optimize the cluster combination. Experiments show that the proposed method succeeds in clustering stems from two complex urban street scenes and is proved to be suitable for various tree structures. The calculation of the optimal cluster combination is effective to reduce the "over-segmentation" and "under-segmentation" in the tree stem detection

improving the clustering accuracy and robustness from 3D point clouds.