(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221091940 5.X (22)申请日 2022.08.01 (71)申请人 南京林业大 学 地址 210037 江苏省南京市玄武区龙蟠路 159号 (72)发明人 温小荣　杨杰　刘磊　 (74)专利代理 机构 南京智转慧移知识产权代理 有限公司 32649 专利代理师 田沛沛 (51)Int.Cl. G06V 10/40(2022.01) G06V 10/762(2022.01) G06V 10/764(2022.01) (54)发明名称 非完全模拟树木水分养分传输的枝干点云 骨架提取方法 (57)摘要 本发明公开一种非完全模拟树木水分养分 传输的枝干点云骨架提取方法， 采用递归实现算 法计算骨架点， 生成骨架线的集合； 利用分段递 归加速算法， 将递归实现算法的递归深度拆分成 若干区间， 加速递归； 采用断点连接算法， 减少分 段递归加速算法分段中过少的点造成的断点。 本 发明以真实树木的枝干点云作为输入对象， 在获 取到最短路径后， 根据需要的骨架的精细程度， 获取树木枝干骨架。 重建的拓扑能够反映树木真 实情况， 降低了后续应用由于拓扑问题而造成的 潜在问题， 并且所需时间约为现有算法的50％， 在速度上， 与现有算法相比， 本算法同等优秀； 在 模型质量上， 与现有算法相比， 本算法更加优秀， 可为树木三维建模提供一种新方法。 权利要求书2页 说明书7页 附图11页 CN 115512121 A 2022.12.23 CN 115512121 A 1.一种非完全 模拟树木水分养分传输的枝干点云骨架提取 方法， 其特 征在于， 包括： S1： 采用递归实现算法计算骨架点， 并同时生成骨架线， 用有向线段表示， 将其加入骨 架线集合； S2： 利用分段递归加速算法， 将步骤S1的递归深度拆分成若干区间， 加速递归； S3： 采用断点连接算法， 减少分段递归加速算法分段中过少的点造成的断点。 2.根据权利要求1所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 步骤S1 中， 将所有 未经探索的点分割成合适的类作为不同的枝干， 并且对每一个 枝干执行以下操作： (1)在一定步长范围内的点计算骨架点； (2)在一定步长范围外的点作 为继续“传输水分养分 ”的部分； (3)将一定步长范围内的点从当前枝干中未经探索的点去 除， 并用此时剩余的未 经探索的点作为输入， 重复(1)。 3.根据权利要求1所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 递归实现算法的实现包括以下步骤： S11： 首先初始化已经 “传输”的距离， 初始化骨架点， 初始化骨架线的集合； 然后 输入枝 干点云序列； S12： 采用聚类算法将未 经探索的点分类； S13： 计算并存 储每一个点与根节点间最短路径 距离的序列； S14： 步长内的部分用于计算骨架点， 步长 外的部分用于递归； S15： 质心作为骨架点。 4.根据权利要求1所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 步骤S2 中， 步骤S1的递归深度， 将递归深度拆分成若干区间， 每一个区间由整棵 树的一部 分组成， 最初， 聚类并判断该部 分分枝类别数量， 然后在每一个分枝类别上进一步 递归。 5.根据权利要求4所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 为了保证区间长度能够被步长整除， 引入每区间步长数h， h∈N*； 且有关系 成立， 该式当且仅当l|L并且h|L时等号成立， 而在其它情况下， 区间数与区间长度之积 必须超过最长距离 。 6.根据权利要求1所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 利用多线程加速算法将分段递归加速算法的任务分配给不同的线程， 设CPU的最 大线程数T， 最长距离被步长分得的份数m， 每区间包 含的步长数量h， 并令 其中， x代 表每个线程平均任务所囊括的分段 数。 7.根据权利要求1所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 断点连接算法的实现步骤 包括：权　利　要　求　书 1/2 页 2 CN 115512121 A 2S31： 计算每 个骨架点的入度、 出度， 除了根骨架点外的入度为0的骨架点 为断点； S32： 计算当前最长骨架线长度； S33： 对每一个断点Bi， 利用kd_tree找 到半径在最长骨 架线长度范围内的全部近邻骨架 点， 由近及远排序后组成序列K。 8.根据权利要求7所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法， 其 特征在于： 对每一个近邻 骨架点Qj∈K， 如果Qj在Bi所在的子树上， 则跳过； 否则， 对第一个满 足不在Bi所在的子树的骨架点Qj， 若该点出度为0， 则找到与Qj相连的骨架点R， 用 取代 否则在骨架线中添加 均为骨架线。权　利　要　求　书 2/2 页 3 CN 115512121 A 3