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

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

作　　者：徐姗姗[1] Xu Shanshan(College of Science and Technology,Nanjing Forest University,Nanjing 210037,China)

机构地区：[1]南京林业大学信息科学技术学院,南京210037

出　　处：《中国图象图形学报》2021年第5期1095-1104,共10页Journal of Image and Graphics

基　　金：江苏省高等学校自然科学研究项目(19KJB520010);中国博士后科学基金项目(2019M661852);江苏省自然科学基金项目(BK20200784)。

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

关 键 词：3维数据处理 计算机视觉 图匹配 层次聚类 点云数据 城市行道树 

分 类 号：S771[农业科学—森林工程]