非完全模拟树木水分养分传输的枝干点云骨架提取方法

1.本发明属于树木建模技术领域，具体涉及一种非完全模拟树木水分养分传输的枝干点云骨架提取方法。

背景技术：

2.树木建模广泛应用于林业、虚拟现实、计算机游戏、电影场景等领域。在林业上，高精度的树木模型可以帮助林业工作者精准地掌握出树木的真实情况；而在虚拟现实、计算机游戏、电影场景上，能够增加真实感，进而增加用户的沉浸感。目前，由于激光雷达技术的快速发展，这一获取物体表面信息并将其以点云形式存储的方式成为了与图像、规则或过程、草图共同构成的树木建模的四大主要方法的基础。虽然点云数据能够直接有效地表现模型的几何信息，本身就可以作为一种树木的三维模型，但是其占用存储空间、散乱且无拓扑、存在噪声的弊端局限了其表达更多信息的能力，因而通常作为数据源，经过一定的处理后转换成其它模型后进行树木建模，通常转换成(广义)圆柱模型。(广义)圆柱模型采用多个圆柱(或圆台)表达枝干，生成这些圆柱(圆台)的轴线即为树木枝干的骨架，因而骨架提取算法的性能直接影响到枝干模型的整体几何形态。
3.枝干点云骨架提取算法主要有三大类——基于体素空间、基于点云收缩和基于几何特征。现有的基于几何特征的枝干点云骨架提取算法仅在运算速度上略不占优势，在三者中排在第二，比点云收缩慢约50％，而在模型质量的指标上均为最优或同等优秀。正因为模型质量更好，树木定量模型(qsm)采用了这一类算法，用于计算树木的材积。现有的算法是以点云分层与最小生成树结合的方法 (xu，h.；gossett，n.；chen，b.knowledge and heuristic-based modeling oflaser-scanned trees.acm transactions on graphics，2007)，核心思想是按照一定的规则对点云分层，对每一层分别聚类，每个聚类计算得到骨架线，然后利用最小生成树算法确定骨架线，虽然实现起来简单，运行速度较快，但骨架线的确定并未考虑枝干点云本身，因而存在较多的拓扑上的错误。
4.聚类算法是影响树木骨架精度的最重要因素之一，现有聚类算法普遍存在的问题包括对初值敏感，难以到最优聚类，聚类效率和对噪声的敏感度，每一种聚类算法都或多或少存在四类问题中的一类或几类。能够适用于树木枝干点云骨架提取方面的更加优良的聚类算法有待提出。
5.任何枝干骨架提取算法对数据源的要求均为枝干点云是完整的，且不能有枝条与枝条十分接近乃至相交的情况。

技术实现要素：

6.本发明解决的技术问题：提供一种进一步对算法加速，可为树木建模提供更好的参考的非完全模拟树木水分养分传输的枝干点云骨架提取方法。
7.技术方案：为了解决上述技术问题，本发明采用的技术方案如下：
8.s1：采用递归实现算法计算骨架点，生成骨架线的集合；
9.s2：利用分段递归加速算法，将步骤s1的递归深度拆分成若干区间，加速递归；
10.s3：采用断点连接算法，减少分段递归加速算法分段中过少的点造成的断点。
11.进一步的，步骤s1中，将所有未经探索的点分割成合适的类别作为不同的枝干，并且对每一个枝干执行以下操作：(1)在一定步长范围内的点计算骨架点； (2)在一定步长范围外的点作为继续“传输水分养分”的部分；(3)将一定步长范围内的点从当前枝干中未经探索的点去除，并用此时剩余的未经探索的点作为输入，重复(1)。
12.进一步的，递归实现算法的实现包括以下步骤：
13.s11：首先初始化已经“传输”的距离d，初始化骨架点q(最初点不存在)，初始化骨架线的集合e；然后输入枝干点云序列p；
14.s12：采用聚类算法将未经探索的点分类；
15.s13：计算并存储每一个点与根节点间最短路径距离的序列；
16.s14：步长内的部分用于计算骨架点，步长外的部分用于递归；
17.s15：质心作为骨架点。
18.进一步的，步骤s2中，步骤s1的递归深度，将递归深度拆分成若干区间，每一个区间由整棵树的一部分组成，最初，聚类并判断该部分分枝类别数量，然后在每一个分枝类别上进一步递归。
19.进一步的，为了保证区间长度能够被步长整除，引入每区间步长数h，h∈n
*
，调节h，l，通常设置h＝5；
20.且有关系
[0021][0022]
成立，该式当且仅当l|l并且h|l时等号成立，而在其它情况下，区间数与区间长度之积必须超过最长距离。
[0023]
进一步的，利用多线程加速算法将分段递归加速算法的任务分配给不同的线程，设cpu的最大线程数t，最长距离可被步长分得的份数m，每区间包含的步长数量h，并令
[0024][0025]
其中，x代表每个线程平均任务所囊括的分段数。
[0026]
非完全模拟树木水分养分传输的枝干点云骨架提取方法，其特征在于：断点连接算法的实现步骤包括：
[0027]
s31：计算每个骨架点的入度、出度，除了根骨架点外的入度为0的骨架点为断点；
[0028]
s32：计算当前最长骨架线长度；
[0029]
s33：对每一个断点bi，利用kd_tree到半径在最长骨架线长度范围内的全部近邻骨架点，由近及远排序后组成序列k。
[0030]
进一步的，对每一个近邻骨架点qj∈k，如果qj在bi所在的子树上，则跳过；否则，对第一个满足不在bi所在的子树的骨架点qj，若该点出度为0，则到与qj相连的骨架点r，用
取代否则在骨架线中添加否则在骨架线中添加均为骨架线。
[0031]
有益效果：与现有技术相比，本发明具有以下优点：
[0032]
(1)本发明以真实树木的枝干点云作为输入对象，在获取到最短路径后，用户可根据需要的骨架的精细程度，采用非完全模拟树木水分养分传输的枝干点云骨架提取算法获取树木枝干骨架，重建流程简单；
[0033]
(2)本发明提出的方法能构建出反映树木真实拓扑情况骨架。本发明结合生态学原理中“树木的水分养分传输趋向于使用最短路径以达到资源配置的最优化”的结论，并在算法执行过程中充分结合枝干点云的特征和关系信息，避免了机械分层造成的拓扑错误；提取的骨架能够反映树木真实拓扑情况，降低了后续应用由于拓扑错误而造成的潜在问题。
[0034]
(3)本发明将分段递归算法由聚类对象差异引起的断点给出连接算法，结合断点仅在区间交替间的特点，采用邻近连接方式恢复了拓扑的连续性；
[0035]
(4)本发明经过多次加速改进，实例表明，对于点数为196203的枝干点云，所需时间约为同类别的基于几何特征算法的50％；在速度上，与现有算法相比，本算法同等优秀；在模型质量上，与现有算法相比，本算法更加优秀。
附图说明
[0036]
图1是本发明递归实现算法的执行过程示意图；
[0037]
图2是分段递归加速算法分段范围示意图；
[0038]
图3是样木1枝干点云形态示意图；
[0039]
图4是样木1在步长0.05时的骨架示意图；
[0040]
图5是样木1在步长0.10时的骨架示意图；
[0041]
图6是样木1在步长0.50时的骨架示意图；
[0042]
图7是样木2枝干点云形态示意图；
[0043]
图8是样木2在步长0.05时的骨架示意图；
[0044]
图9是样木2在步长0.10时的骨架示意图；
[0045]
图10是样木2在步长0.50时的骨架示意图；
[0046]
图11是样木3枝干点云形态示意图；
[0047]
图12是样木3在步长0.05时的骨架示意图；
[0048]
图13是样木3在步长0.10时的骨架示意图；
[0049]
图14是样木3在步长0.50时的骨架示意图。
具体实施方式
[0050]
下面结合具体实施例，进一步阐明本发明，实施例在以本发明技术方案为前提下进行实施，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围。
[0051]
本发明的非完全模拟树木水分养分传输的枝干点云骨架提取方法，英文简称为isttwn(incomplete simulationof tree transmitting waterand nutrients)算法，主要包括以下步骤：
[0052]
s1：采用递归实现算法计算骨架点，并同时生成骨架线，用有向线段表示，将其加
入骨架线集合，从而生成骨架线的集合e，
[0053]
本实施例中，e是存放骨架线的集合，骨架线“以有向线段的形式表达”。
[0054]
生态学研究表明，树木趋向于使用最短路径传输水分和养分以达到资源配置的最优化，基于此结论，将所有未经探索的点分割成合适的类作为不同的枝干，并且对每一个枝干执行以下操作：
[0055]
(1)在一定步长范围内的点计算骨架点；
[0056]
(2)在一定步长范围外的点作为继续“传输水分养分”的部分；
[0057]
(3)将一定步长范围内的点从当前枝干中未经探索的点去除，并用此时剩余的未经探索的点作为输入重复(1)。
[0058]
递归实现算法执行过程如图1所示，包括以下步骤，
[0059]
s11：首先初始化已经“传输”的距离d，初始化骨架点q(最初没有点)，初始化骨架线的集合e；然后输入枝干点云序列p；
[0060]
其中，第i个点pi∈p，p1必须是根节点，且pi≠pj，|p|是 p中的元素个数；pj是点云中第j个点；
[0061]
s12：将未经探索的点分类。
[0062]
因为分类数量在枝干的不同位置并不总是一样的，为解决这一问题，本发明采用聚类算法(cluster_algorith)，本实施例中优选采用欧式距离聚类算法。
[0063]
将原点云p、用于聚类算法的扫描半径(eps)t、用于聚类算法的最小包含点数(minpts)n作为输入参数执行欧氏距离聚类，聚类结果以分类后的类别的集合s的形式表示，其中t≥r，r是先前使用的kd-tree的搜索半径，一般取t＝r， n＝1，每个s的元素互不相交，且它们并集为p。
[0064]
s13：计算并存储每一个点与根节点间最短路径距离的序列d；
[0065]
类别初始化p
′
，p
″
，d
″
，序列d出与sk一一对应的距离，组成
[0066]
其中，且表示s
k，j
与根节点p1间最短路径距离，距离距离 d
″
是当前路径序列d完全分割后的两个子集、p
′
、p
″
是当前递归中的枝干点云 p完全分割后的两个子集，但后面说明了目的是不一样的，p
′
和d
″
用于后续递归，而p’用于计算骨架点，是用于判断哪些点、距离用于递归、哪些计算骨架点。
[0067]
第i个元素di表示pi与根节点p1间的最短路径距离，是d的子集，然后点s
k，j
属于类别sk，而sk属于s，而s属于p，因此s
k，j
是点云序列p中的某一个被划分到类别sk的点，因此，d中每个元素都是点云中每个点与根节点的距离，而中是类别sk中的点与根节点的距离，且只有最长距离l满足l＝max{d}。
[0068]
s14：步长内的部分用于计算骨架点，步长外的部分用于递归；
[0069]
如果将点s
k，j
加入点集p
′
，否则将点s
k，j
加入点集p
″
，将距离加入距离序列d
″
；
[0070]
步长l满足l≥r。
[0071]
s15：质心作为骨架点
[0072]
[0073]
如果q存在，则在骨架线集合e中添加骨架线
[0074]
探索完某一枝后(即满足d＞l或|p|＝0)，返回。
[0075]
s2：利用分段递归加速算法，基于步骤s1的递归深度将递归深度拆分成若干区间，每一个区间由整棵树的一部分组成。最初，聚类并判断该部分分枝类别数量，然后在每一个分枝类别上进一步递归。
[0076]
最初，聚类并判断小树的数量，然后在每一棵小树上进一步递归，这样就能够大幅度节省时间。但值得注意的是，若假设区间长度不能被步长整除，则最坏情况是几乎所有的骨架点都会偏离步骤s11-s15所得到的，并且很有可能发生，因而，为了保证区间长度能够被步长整除，引入每区间步长数h，h∈n
*
，n
*
是正整数集合，调节h，l，通常设置h＝5；
[0077]
且有关系
[0078][0079]
成立，该式当且仅当l|l并且h|l时等号成立，而在其它情况下，区间数与区间长度之积必须超过最长距离。此外，为保证分段递归加速算法得到的骨架是连通的，每一分段需要额外包括下一分段的第一个步长的长度，以h＝3为例，如图2所示。
[0080]
分段递归加速算法具体实现步骤如下：
[0081]
s21：m定义为m表示最长距离可以被步长分成的段数；
[0082]
s22：在每一个区间[u，u+h+1]用距离序列中符合最小距离(u-1)l替代原算法中的d、最大距离(u+h)l替代原算法中的l，并将距离向量中符合距离在此时的[d，l)范围内对应的原枝干点云中的点的取出，以执行s11-s15代表的递归算法；
[0083]
其中，u表示第u个分段，u的值从1依次至m，每一区间包括步长加1段，即h+1，这能保证前后区间能够相连；
[0084]
最小距离是指作为s22当前该分段执行s11-s15代表的递归算法的初始距离；
[0085]
最大距离是指作为s22当前该分段执行s11-s15代表的递归算法的最长距离。
[0086]
另外，本发明除了分段递归加速算法外，还可以采用多线程加速算法，实际编程时可以用[(i+1)x+1]l替代ml以忽略判断，因为[(i+1)x+1]l＞ml总是成立，并且在没有未探索的点时算法会自动终止。每一个线程，以表中给出的起始距离和终止距离将符合的点云和距离序列子集作为参数p，d执行分段递归加速算法。该方法的目的仅仅是将任务分配给不同的线程，并没有改变分段递归加速算法的本质，因而得到的骨架与分段递归加速算法是一致的。多线程加速算法实现方式为：
[0087]
设cpu的最大线程数t，最长距离可被步长分得的段数m，每区间包含的步长数量h，并令
[0088]
[0089]
其中，x代表每个线程平均任务所囊括的分段数(但是需要+1才能保证每个线程的结果相连)，用于表1。
[0090]
表1是各线程分配的任务涵盖的距离范围汇总表
[0091]
线程起始距离终止距离10(x+1)l2xl(2x+1)l
………
i-1(i≤t)(i-1)xl(ix+1)lιixlml(实际编程时按[(i+1)x+1]l即可)
[0092]
s3：采用断点连接算法，减少分段中过少的点造成的断点
[0093]
由于每次执行递归实现算法每次聚类所用的点云是剩余全部未探索的枝干上的点构成的，而分段递归加速算法或多线程加速后的分段递归加速算法(即多线程加速算法)每次聚类所用的点云只是所在的区间长度范围内的点，因而两者的结果包括骨架线、骨架点都会存在一定的差异，特别是在受到遮挡导致点稀疏的冠层处的点云。n＝1可以解决某些区间的分段中过少的点造成的断点，但仍然会存在少量区间过渡时的断点。
[0094]
断点连接算法的实现步骤包括：
[0095]
s31：计算每个骨架点的入度、出度，除了根骨架点外的入度为0的骨架点为断点；
[0096]
s32：计算当前最长骨架线长度；
[0097]
s33：对每一个断点bi，利用kd_tree到半径在最长骨架线长度范围内的全部近邻骨架点，由近及远排序后组成序列k。对每一个近邻骨架点qj∈k，如果qj在bi所在的子树上，则跳过；否则，对第一个满足不在bi所在的子树的骨架点qj，若该点出度为0，则到与qj相连的骨架点r，用取代否则在骨架线中添加均为骨架线，是有向线段。
[0098]
采用本发明的方案进行应用，应用结果和分析如下：
[0099]
本发明在cpu时钟频率为2.8ghz，内存16g，显存4.0g的笔记本上运行测试。一般地，取t＝r，n＝1，调节h，l，通常设置h＝5，预处理阶段时，均取r ＝0.05，多个样木点云的结果如表2所示。
[0100]
表2多个样木点云的结果
[0101][0102]
由表2可知，对于树木枝干点云，建立骨架的时间通常在5秒内。经过测试，本发明经过多次加速改进，对于点数为196203的枝干点云，所需时间约为现有算法的50％。
[0103]
以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

技术特征：

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所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法，其特征在于：断点连接算法的实现步骤包括：
s31：计算每个骨架点的入度、出度，除了根骨架点外的入度为0的骨架点为断点；s32：计算当前最长骨架线长度；s33：对每一个断点b
i
，利用kd_tree到半径在最长骨架线长度范围内的全部近邻骨架点，由近及远排序后组成序列k。8.根据权利要求7所述的非完全模拟树木水分养分传输的枝干点云骨架提取方法，其特征在于：对每一个近邻骨架点q
j
∈k，如果q
j
在b
i
所在的子树上，则跳过；否则，对第一个满足不在b
i
所在的子树的骨架点q
j
，若该点出度为0，则到与q
j
相连的骨架点r，用取代否则在骨架线中添加否则在骨架线中添加否则在骨架线中添加均为骨架线。

技术总结

本发明公开一种非完全模拟树木水分养分传输的枝干点云骨架提取方法，采用递归实现算法计算骨架点，生成骨架线的集合；利用分段递归加速算法，将递归实现算法的递归深度拆分成若干区间，加速递归；采用断点连接算法，减少分段递归加速算法分段中过少的点造成的断点。本发明以真实树木的枝干点云作为输入对象，在获取到最短路径后，根据需要的骨架的精细程度，获取树木枝干骨架。重建的拓扑能够反映树木真实情况，降低了后续应用由于拓扑问题而造成的潜在问题，并且所需时间约为现有算法的50％，在速度上，与现有算法相比，本算法同等优秀；在模型质量上，与现有算法相比，本算法更加优秀，可为树木三维建模提供一种新方法。可为树木三维建模提供一种新方法。可为树木三维建模提供一种新方法。