(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210642833.2 (22)申请日 2022.06.08 (71)申请人 电子科技大 学 地址 611731 四川省成 都市高新区 （西区） 西源大道 2006号 (72)发明人 李世华　田志林　 (74)专利代理 机构 电子科技大 学专利中心 51203 专利代理师 闫树平 (51)Int.Cl. G06V 20/64(2022.01) G06V 10/764(2022.01) G06V 10/762(2022.01) G06V 10/40(2022.01) (54)发明名称 一种基于图论的单木点云枝叶分离方法 (57)摘要 本发明属于地面激光雷达点云数据处理技 术领域， 具体涉及一种基于图论的单木点云枝叶 分离方法。 本发 明基于地面激光雷达获取的多站 扫描单木点 云数据， 依次经历构建图、 分层聚类、 初始枝干提取和最终枝干提取， 建立用于区分单 木点云枝叶组分的单木点云枝叶分离方法。 本发 明充分利用了图的最短路径信息， 不依赖先验知 识和机器学习， 在保证分类精度的同时具有精简 高效的特点， 为单木点云进行枝叶分离提供了一 种新的思路， 并可进一步应用于森林参数提取、 智慧林业、 植被辐射传输建模等领域。 权利要求书2页 说明书7页 附图2页 CN 115187979 A 2022.10.14 CN 115187979 A 1.一种基于图论的单木点云枝叶分离方法， 其特 征在于， 包括以下步骤： 步骤1、 构建图： 将离 散单木点云连成一张无向带权连通图G； 步骤2、 分层聚类： 以分层切图的方式对原 始单木点云t ree_cloud进行聚类； 2‑1、 最短路径提取： 采用单源最短路径算法从步骤1得到的图G中提取每个点到根节点 的最短路径信息路， 路径序列path_l ist和路径长度path_dis； 2‑2、 路径长度分层： 基于路径长度p ath_dis对原始单木点云tree_cloud进行分层， 分 层间距interval_D＝treeHight/30， 通过在图G中删除位于分层边界上的边实现， 经过分层 切边操作， 图G的连通分量对应的点云 即为聚类结果； 步骤3、 初始枝干提取： 提取步骤2聚类结果中特 征显著的枝干类簇； 步骤4、 最终枝干提取： 以步骤3得到的初始枝干点为种子点， 通过区域增长的方式提取 特征不显著处的枝干点云， 具体为： 4‑1、 种子点补充： 将初始枝干点及其路径序列path_l ist上的所有点均 作为种子点； 4‑2、 区域增长： 4‑2‑1.创建种子点 集合L和枝干点 集合F， 然后将上述 步骤4‑1的种子点 放入L和F； 4‑2‑2.如果Dpp′<0.25*interval_D且Drp′<Drp， 则将p′加入临时集合temp_L； 其中p为L中 一点， p′为p在未删除边的原始图G上相邻且不在F中的点， Dpp′表示p到p ′的距离， Drp和Drp′分 别表示p和p ′到根节点的最短路径 距离path_dis； 若temp_L中有点， 更新 L＝temp_L， 并将temp_L中的点 放入F， 重新执 行4‑2‑2； 若temp_L中没有点， 则增长结束； 4‑3、 集合F中的点即为枝干点云， F的补集t ree_cloud‑F即为叶片点云。 2.如权利要求1所述基于 图论的单木点云枝叶分离方法， 其特征在于， 所述步骤1具体 为： 步骤1‑1、 插入根节点： 在原始单木点云tree_cloud中插入一个根节点， 选取树干底部 高度为5‑20cm的一段点云， 将其投影到树干最低点所在水平面， 对投影后的点云进行最小 二乘圆拟合， 圆心即为 根节点的插 入位置； 1‑2、 大尺度近邻点搜索： 搜索原始单木点云tree_cloud中每个点的大范围近邻点 neighbors_K， 50≤K≤300， 以充分获取每个点的邻近关系， 数据缺失越严重K的值取越大， 但会增大内存消耗； 1‑3、 小尺度邻域图构建： 1‑3‑1.创建当前集合Q和已访问集 合V， 并将根节点 放入Q和V； 1‑3‑2.对于在当前集合Q中的每个点， 将其与其相应的大范围近邻点neighbors_K中最 近的5个不在V中的点相连， 并将这些点添加到临时集合temp_Q， 更新Q＝temp_Q， 然后将临 时集合temp_Q中的点添加到V； 重复执 行该步骤直至临时集 合temp_Q中没有点； 1‑3‑3.初始化thr_neighb or_Dis＝treeHight/30， treeHight为树高,thr_neighb or_ Dis为邻近点距离阈值； 1‑3‑4.定义未访问集 合un_V＝t ree_cloud–V， 并判断un_V是否为空： 若un_V不为空， 遍历un_V中的每个点， 如果其相应的大范围近邻点neighbors_K中存在 距离小于thr_neighbor_Dis且在V中的点， 将其与这些点中最近的5个点相连， 并将其自身 加入temp_Q； 若temp_Q中有点， 更新Q＝temp_Q， 并将temp_Q中的点添加到V， 跳转到1 ‑3‑2；权　利　要　求　书 1/2 页 2 CN 115187979 A 2若temp_Q中没有点， 更新thr_neighbor_Dis+＝t reeHight/60， 重新进入1 ‑3‑4； 若un_V为空， 则构建完成， 得到图G＝(V,E)， G由顶点集V和边集E构成， 边的权重为两点 间的欧氏距离 。 3.如权利要求1所述基于图论的单木点云枝叶分离方法， 其特征在于： 所述步骤2 ‑1中 的单源最短路径算法为Dijkst ra算法。 4.如权利要求1所述基于 图论的单木点云枝叶分离方法， 其特征在于， 所述步骤3具体 为： 3‑1、 坐标变换： 定义类簇轴向为类簇中每个点与其路径序列path_list上第一个前驱 点所构成方向向量的和向量， 然后旋转三维直角坐标系坐标轴， 使坐标z轴与类簇轴向平 行； 3‑2、 尺寸滤波： 若|dimen_z ‑interval_D|>0.25*interval_D， 则认为该类簇过小或过 大， 将其过 滤掉； dimen_z为该类簇在坐标变换后沿z轴方向的最大z值 ‑最小z值； 3‑3、 树干和主枝类簇提取： 提取圆柱特征显著的树干和主枝类簇， 通过圆柱拟合进行 识别， 具体过程如下： 3‑3‑1、 圆柱拟合： 经过3 ‑1坐标变换， 类簇的轴向已与坐标z轴 平行， 因此可以将类簇沿 z轴投影到二维平面进行最小二乘圆拟合， 从而达 到圆柱拟合的效果； 3‑3‑2、 基于相对拟合 误差识别： 圆柱相对拟合 误差公式定义如下： 式中， n为类簇包含的点数， di为类簇中任一点到所拟合圆柱轴线的距离， r为所拟合圆 柱的半径； 当rEr ror<0.2时， 表明类簇圆柱特 征显著， 进行提取； 3‑4、 细枝类簇提取： 提取线性特征显著的细枝类簇， 通过主成分分析进行识别， 具体过 程如下： 3‑4‑1、 主成分 分析： 设P为类簇点 集， P的协方差矩阵定义如下： 式中， n为P包含的点数， pi为P中任一 点， pc为P的质心； CovP的特征值 λ1≥λ2≥λ3表征了P在三个主成分方向上的离散程度， P的空间分布特征由 特征值计算得到； 3‑4‑2、 基于线性特征识别： 定义线性度Linearity＝ λ1/( λ1+λ2+λ3)来表示类簇的线性特 征； 当Linearity>0.9时， 表明类簇的线性特 征显著， 进行提取； 3‑5、 分类纠正： 基于树干到树枝逐渐变细这一树木生长规则， 纠正被误分为树干和主 枝的呈现圆柱特 征的树叶类簇， 具体过程如下： 3‑5‑1、 遍历每个以步骤3 ‑3圆柱拟合方式分为树干和主枝的类簇c， 从c中任意一点沿 路径序列path_list向根节点搜索， 如果遇到从步骤3 ‑4得到的细枝类簇或遇到从步骤3 ‑3 得到的树干和主枝的类簇c ′但c的圆柱拟合半径大于c ′的圆柱拟合半径， 则表明类簇c系误 分， 将其剔除。权　利　要　求　书 2/2 页 3 CN 115187979 A 3