图匹配算法激光扫描点云树干分割

Tree stem segmentation of laser scanning point clouds based on graph matching algorithm

目的移动激光扫描系统能够成功采集丰富的城市行道树侧边信息,然而由于点云数据规模大、密度欠均匀和噪声多等原因,导致行道树的提取精度和效率偏低。为此,本文提出一种基于层次聚类的算法从移动激光扫描点云中提取树干。方法采用自下而上的聚类策略合并目标区域,基于点云间欧氏距离和点云的局部主方向计算聚类所需的邻近矩阵,通过构造能量函数评估不同的簇合并方案,将能量函数最小化问题转换为计算二分图匹配问题,求解二分图的最小代价完美匹配获得全局最优的层次聚类。结果实验在公开的巴黎场景数据集与自采集的南京黄埔路场景数据集上进行测试,本文提出的自下向上的聚类算法成功地从点云中提取出树干和主要树枝点,其中提取树干的平均正确率、完整率和F-score分别为98.5%、94.8%和0.97,与其他算法中最好的实验结果对比,分别提高了1.0%、0.6%和0.02。结论实验结果表明,本文算法通过优化层次聚类中的簇合并,可以有效减少聚类中的"过分割"和"欠分割",提高点云中树干的分割精度与效率。

Objective 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.MethodThere 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σofK-nearest neighbor points.A point is considered to be an outlier if the average distance to itsK-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σkandμk+1.5σk,this cluster will be regarded as a tree;otherwise,this cluster will be regarded as a false tree.μkandσkare 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.ResultTo 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 Li DAR 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 of98.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.ConclusionThe 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.