树木点云数据的自动分割方法

摘要

本发明是一种树木点云数据的自动分割方法，该方法的步骤包括：点云的获取及预处理，点云法方向估计，局部坐标系的构造，近邻点拟合二次曲面，利用二次曲面计算主曲率，定义并计算轴向分布密度，利用轴向分布密度区分树枝点云与树叶点云，对树枝点云进行区域生长，对树枝点云进行区域合并。本发明利用激光扫描仪的树木扫描数据和估计的主曲率，实现树木扫描点云符合实际器官分布情况的分割。该方法通过局部主曲率方向实现树木点云扫描数据不同器官间的自动分割，算法简单，计算结果准确。其计算结果在树木点云3D重建、林业测量以及树木点云的配准等领域具有重要的应用价值。

权利要求

1.一种树木点云数据的自动分割方法，其特征在于，该点云分割步骤包括：

步骤S1：利用激光扫描仪扫描直接采集树木的扫描点云数据并对点云数据预处理，按照点云数据中每个点的坐标进行空间划分，实现三维空间的数据存储结构称为kd树(k-dimensional tree)；

步骤S2：对于点云数据的每一个点，利用点云数据的kd树查找多个近邻点，根据最小二乘方法把这些点拟合出一个平面，以这个平面的法向量作为点云法向量的初始估计值；

步骤S3：对于点云数据的每一个点，利用其法向量、切平面构造局部三维直角坐标系；

利用点云数据的kd树查找多个近邻点；

步骤S4：对于查找到的近邻点，利用这些近邻点拟合二次曲面；

步骤S5：对于点云数据的每一个点，利用该点拟合出的二次曲面计算主曲率；

步骤S6：对于点云数据的每一个点，利用主曲率方向计算轴向分布密度；所述计算轴向分布密度是对点云模型P中的点p，以点p为中心，以h为高，以r为半径构建圆柱S，圆柱S的轴向与点p的主方向 一致；其中高h被设置为10倍于扫描间距，半径r被手工设置为2倍于扫描间距；位于圆柱S内的每一个点p，将点p投影到圆柱S的中心轴上，投影点被记为PS(p)，然后再以中心轴为中心，设置的固定长度α为长度选定线段u(p，S)，称选定线段u(p，S)为点p在圆柱S内的投影覆盖区域；当将圆柱S内的每一个点p投影到中心轴后，则得到了中心轴上的若干表现为一个个线段的投影覆盖区域，这些区域可能相互重叠，求取这些区域的并集，记为：记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S内的所有点在圆柱S内的分布密度和分布均匀情况，表示了点p附近近邻点云是否沿点p的主曲率方向均匀分布；轴向分布密度C(p)，定义为：C(p)＝L[U(p，S)]/h，

轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内覆盖的比例；

步骤S7：利用轴向分布密度将属于树枝上的点云与属于树叶上的点云区分；所述将属于树枝上的点云与属于树叶上的点云区分是设定一个阈值β，将点云模型P中轴向分布密度值大于β的点选定为种子点，首先孤立的种子点被去除，随后保留的种子点和种子点对应的圆柱S内所有点标记起来作为树枝上的点云，其余点云被认为是位于树叶上的点云；

步骤S8：对于属于树枝上的点云，利用主曲率方向进行区域生长，产生过分割的分割结果；

步骤S9：对于过分割的树枝上的点云，依照相邻组内的点云数量以及依照分组中所有点云的主曲率方向的平均值所确定的组角度进行区域合并，得到符合树木树枝器官分布的分割结果。

2.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述拟合二次曲

2 2

面为h(u，v)＝c0u+2c1uv+c2v，其中(u，v，h(u，v))为空间中的点，该二次曲面h(u，v)＝

2 2

c0u+2c1uv+c2v 的系数c0、c1、c2通过最小化 获得，其中A、B、μ为矩阵：ui、vi、hi为n个近邻点的坐标值，i＝1，…，n，c0、c1、c2为二次曲面的系数，通过μT T -1 T T＝[c0 c1 c2] ＝(AA) AB得到二次曲面的系数，其中T表示转置，[c0 c1 c2] 表示矩阵[c0 c1 c2]的转置矩阵；利用拟合二次曲面计算出点云模型P中p点处的局部几何量，包括两个主曲率k1(p)和k2(p)，k1(p)＜＝k2(p)以及对应的主曲率方向 和

3.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述点云区分是通过计算各个点的轴向分布密度实现属于树枝上的点云与属于树叶上的点云区分。

4.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述相邻组是对于两个通过分割获得的点云分组W1和W2，使用Hausdorff距离h(W1，W2)＝min{||p-q||；

点p∈W1，点q∈W2}来衡量两组之间的距离，当该距离小于一定的阈值时，称W1和W2为相邻组。

5.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述组角度的定义为 其中W为通过分割获得点云分组， 为组内的点pi的主方向，j为组内点的数量。

6.按权利要求5所述的树木点云数据的自动分割方法，其特征在于，计算组角度时随机从组内选择一个点的主曲率方向D，对组内每一个点的主曲率方向 进行180°的调整以满足

7.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述依照相邻组内的点云数量进行区域合并，是将点云数量小于设定阈值N的组合并到其所有相邻组中与之距离最近的组。

8.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，依照分组中所有点云的主曲率方向的平均值的夹角进行区域合并，是计算任意两个相邻组中所有点云的主曲率方向的平均值之间的夹角并且将夹角存储在一张角度表中，从角度表中寻找夹角最小并且满足角度限制的两个组进行合并，形成的新组的组方向被重新计算，角度表格被更新；

重复上面的过程直到组之间的夹角大于设定的阈值。

说明书

树木点云数据的自动分割方法

技术领域

[0001] 本发明属于微分几何、计算数学、计算机图形学和计算机视觉技术领域，涉及一种利用三维激光扫描仪进行树木测量得到树木点云数据，并根据点云数据来进行属于不同器官间点云的自动分割的方法。在虚拟现实、电脑游戏、数据压缩、特征提取、林业测量、植物三维3D重建等领域具有重要的应用价值。

背景技术

[0002] 点云模型是一种无组织的点云集合(Unorganized Points)。在几何压缩和传输、交互编辑、纹理映射、参数化等应用方面，需要将点云数据划分为特征单一，互不重叠的区域，这需要使用点云分割技术。

[0003] 针对树木的生物学特点，树木扫描点云可以被分为树枝点云和树叶点云，其中位于树枝上的点云又可以按照所处的不同的枝干进行进一步划分。树木点云模型的准确分割对模型的应用具有重要意义。在进行模型重建的过程中，由于树枝与树叶的重建方法有较大的区别，所以已有的大部分重建方法在重建之前需要对点云进行树枝树叶的分离。同样道理，直接在点云模型上进行的林业测量工作也需要明确的知道哪些点云位于树枝哪些点云位于树干上。树木点云模型的配准工作中，如果能对不同的树枝上的点云进行准确的区分会对配准工作带来很大的帮助。

[0004] 尽管近年来树木点云的分割算法没有被单独的研究过，但在近年的许多基于点云的树木重建方法中，提出了一些针对树木点云的形状分解或者三维分割方法。

[0005] Xu利用将到根节点的最短路径相似的点归类的方法进行点云的分组，每个根节点的选取对最后的分割结果具有重大影响，然而根节点的选取并不是自动的，这导致点云的分组工作需要较多的手工交互。同时在树枝的分叉处，不同树枝上的点可能具有相同的到根节点的最短路径，这样的结果就是属于不同树枝的点可能被划归到同一组中。Cheng使用手工的方法进行树叶与树枝的分离，大量属于细枝的点云被当作位于树叶上的点云被处理。同时，Cheng使用不同枝干在深度图像中会发生深度跳变的性质进行树干点云的分离，不同枝干间如果深度相似的话将无法成功区分。

[0006] 在Quan的重建算法中，从图像中恢复三维点云，然后对三维点云进行手工交互的分割，但三维分割的准确性受到相机参数估计准确性的影响。所以该方法虽然可以获得较好的视觉效果，但是实际准确性并不理想。另外手工交互可以处理叶片较大，树叶与树枝区分明显的植物，但如果树叶分布密集，与树枝大量混杂在一起就难于靠手工分割获得较好的效果。

[0007] Bucksch提出了一套基于八叉树和图论的方法从树木点云模型中实现树枝分割和骨架提取的算法，这套算法只能用于没有树叶的模型，并且在分割过程中无法克服过分割的问题。

发明内容

[0008] 本发明欲解决在分割过程中无法克服过分割的技术问题，本发明的目的是针对现实世界中由激光扫描得到的树木点云数据，提供一个激光扫描点云模型符合树木实际器官分布的准确的分割方法。

[0009] 为实现上述目的，本发明的技术解决方案是提供一种基于主曲率分析的树木点云分割方法，该点云分割步骤包括：

[0010] 步骤S1：利用激光扫描仪扫描直接采集树木的扫描点云数据并对点云数据预处理，按照点云数据中每个点的坐标进行空间划分，实现三维空间的数据存储结构称为kd树(k-dimensional tree)；

[0011] 步骤S2：对于点云数据的每一个点，利用点云数据的kd树查找多个近邻点，根据最小二乘方法把这些点拟合出一个平面，以这个平面的法向量作为点云法向量的初始估计值；

[0012] 步骤S3：对于点云数据的每一个点，利用其法向量、切平面构造局部三维直角坐标系；利用点云数据的kd树查找多个近邻点；

[0013] 步骤S4：对于查找到的近邻点，利用这些近邻点拟合二次曲面；

[0014] 步骤S5：对于点云数据的每一个点，利用该点拟合出的二次曲面计算主曲率；

[0015] 步骤S6：对于点云数据的每一个点，利用主曲率方向计算轴向分布密度；

[0016] 步骤S7：利用轴向分布密度将属于树枝上的点云与属于树叶上的点云区分；

[0017] 步骤S8：对于属于树枝上的点云，利用主曲率方向进行区域生长，产生过分割的分割结果；

[0018] 步骤S9：对于过分割的树枝上的点云，依照相邻组内的点云数量以及依照分组中所有点云的主曲率方向的平均值所确定的组角度进行区域合并，得到符合树木树枝器官分布的分割结果。

[0019] 其中，所述拟合二次曲面为h(u，v)＝c0u2+2c1uv+c2v2，其中(u，v，h(u，v))为空间中的点，该二次曲面h(u，v)＝c0u2+2c1uv+c2v2的系数c0 c1 c2通过最小化获得， 其中A、B、μ为矩阵：

[0020]

[0021] ui、vi、hi为n个近邻点的坐标值，i＝1，...，n，c0 c1 c2为二次曲面的系数，通过T T -1 T Tμ＝[c0 c1 c2] ＝(AA) AB得到二次曲面的系数，其中T表示转置，[c0 c1 c2] 表示矩阵[c0 c1 c2]的转置矩阵；利用拟合二次曲面计算出点云模型P中p点处的局部几何量，包括两个主曲率k1(p)和k2(p)，k1(p)＜＝k2(p)以及对应的主曲率方向 和

[0022] 其中，所述点云区分是通过计算各个点的轴向分布密度实现属于树枝上的点云与属于树叶上的点云区分。

[0023] 其中，所述轴向分布密度，由下列方法确定：对点云模型P中的点p，以点p为中心，以h为高，以r为半径构建圆柱S，圆柱S的轴向与点p的主方向 一致；其中高h被设置为10倍于扫描间距，半径r被手工设置为2倍于扫描间距；位于圆柱S内的每一个点p，将点p投影到圆柱S的中心轴上，投影点被记为Ps(p)，然后再以中心轴为中心，设置的固定长度α为长度选定线段u(p，S)，称选定线段u(p，S)为点p在圆柱S内的投影覆盖区域；当将圆柱S内的每一个点p投影到中心轴后，则得到了中心轴上的若干表现为一个个线段的投影覆盖区域，这些区域可能相互重叠，求取这些区域的并集，记为：

[0024]

[0025] 记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S内的所有点在圆柱S内的分布密度和分布均匀情况，表示了点p附近近邻点云是否沿点p的主曲率方向均匀分布；轴向分布密度C(p)，定义为：

[0026] C(p)＝L[U(p，S)]/h，

[0027] 轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内覆盖的比例。

[0028] 其中，所述将属于树枝上的点云与属于树叶上的点云区分，由下列方法确定：设定一个阈值β，将点云模型P中轴向分布密度值大于β的点选定为种子点，首先孤立的种子点被去除，随后保留的种子点和种子点对应的圆柱S内所有点标记起来作为树枝上的点云，其余点云被认为是位于树叶上的点云。

[0029] 其中，所述相邻组是对于两个通过分割获得的点云分组W1和W2，使用Hausdorff距离h(W1，W2)＝min{‖p-q‖；点p∈W1，点q∈W2}来衡量两组之间的距离，当该距离小于一定的阈值时，称W1和W2为相邻组。

[0030] 其中，所述组角度的定义为 其中W为通过分割获得点云分组， 为组内的点pi的主方向，j为组内点的数量。

[0031] 其中，计算组角度时随机从组内选择一个点的主曲率方向D，对组内每一个点的主曲率方向 进行180°的调整以满足

[0032] 其中，所述依照相邻组内的点云数量进行区域合并，是将点云数量小于设定阈值N的组合并到其所有相邻组中与之距离最近的组。

[0033] 其中，依照分组中所有点云的主曲率方向的平均值的夹角进行区域合并，是计算任意两个近邻组中所有点云的主曲率方向的平均值之间的夹角并且将夹角存储在一张角度表中，从角度表中寻找夹角最小并且满足角度限制的两个组进行合并，形成的新组的组方向被重新计算，角度表格被更新；重复上面的过程直到组之间的夹角大于设定的阈值。

[0034] 本发明的有益效果是对树木点云数据直接进行分割。利用点云的坐标信息和点云的主方向信息。本发明与前人方法的区别主要体现在，定义轴向分布密度，对于点云数据的每一个点，利用其轴向分布密度判断是否位于树枝，此外本发明还利用主曲率方向指导树枝上的点云进行区域生长和区域合并。实验表明，本发明的方法获取的树木点云的分割结果准确，符合实际器官分布。我们利用三维激光扫描仪获取实物的表面信息，并根据扫描数据利用常规方法计算出各个点的法向量，再计算求出主曲率和主方向，定义了表示点云近邻点云分布情况的“轴向分布密度”，利用轴向分布密度分离树枝与树叶点云，利用主曲率方向为引导进行区域生长和区域合并分离各个枝干之间的连接关系。本发明所获得的计算结果能用于计算机图形学各应用领域，包括虚拟现实、电脑游戏、数据压缩、特征提取、林业测量、植物三维3D重建等领域具有重要的应用价值。利用本发明，可以自动、准确地对树木扫描点云模型进行符合实际树木器官分布的分割。

附图说明

[0035] 图1本发明方法的流程图；

[0036] 图2本发明采用的单面扫描数据；

[0037] 图3a、图3b树木点云主方向分布规律示意图；

[0038] 图4圆柱构造示意图；

[0039] 图5a、图5b轴向分布密度的可视化表示和被判断属于树枝上的点云；

[0040] 图6区域生长的结果示意图；

[0041] 图7小分组被合并后的分割情况示意图；

[0042] 图8a、图8b区域合并的角度限制示意图；

[0043] 图9区域合并后的分割结果示意图；

[0044] 图10a、图10b、图10c三个树木点云数据的分割结果示意图。

具体实施方式

[0045] 下面结合附图详细说明本发明技术方案中所涉及的各个细节问题。应指出的是，所描述的实施例仅旨在便于对本发明的理解，而对其不起任何限定作用。

[0046] 1、方法概述(overview of approach)

[0047] 如图1示出本发明整个方法的流程，其中本发明算法的主要步骤包括：

[0048] 1)、局部几何量计算，包括6个子步骤：(a)点云的获取及预处理、(b)点云法方向估计、(c)局部坐标系的构造、(d)利用近邻点拟合二次曲面、(e)利用二次曲面计算主曲率、(f)计算轴向分布密度。

[0049] 2)、对树木点云模型进行分割，包括3个子步骤：(g)利用轴向分布密度区分属于树枝上的点云与属于树叶上的点云、(h)利用主曲率方向进行区域生长、(i)依照相邻组内的点云数量以及组内点云主曲率平均值的夹角进行区域合并。

[0050] 3)、输出计算结果，存储分割结果，将点云按照分割以不同的颜色表示。

[0051] 2、数据预处理

[0052] 首先，计算真实树木的扫描数据(如图2示出采用的扫描数据)的局部几何量，点云的局部几何量，包括法方向、主曲率大小和主曲率方向，可以表示点云的局部形状特征，是点云分割的重要依据。计算一个点(记为p)的局部几何量包括以下七个步骤：

[0053] 2.1创建kd树

[0054] 在计算三维点云数据法向量和主曲率、主方向的过程中都需要用到近邻点，我们使用建立点云数据的3维空间的二分查找树，简称为kd树(k-dimensional tree)来查找近邻点。

[0055] 首先，建立kd树。kd树基于点的空间位置信息，通过二分法迭代划分三维空间，实现最优存储。在kd树上，进行k近邻查找的时间复杂度为O(log2n)，这里n为点云数据的点的个数。

[0056] 2.2搜索近邻点

[0057] 由于预处理阶段建立了kd树，以点云模型P中点p为查询点，基于欧式距离查找k近邻，比如k＝20近邻或k＝30近邻，根据数据扫描精度确定近邻点的个数，扫描精度较低则取15个近邻点，扫描精度较高则取30个近邻点，这里记qi(i＝1，2，...，m)为查询得到的m个近邻点。

[0058] 2.3计算各个点的法向量

[0059] 对于点云数据的每一个点，利用点云数据的kd树查找15个或30个近邻点，对整个点云模型P中的每个点p选择其近邻点组成的点集N(p；k)＝{qi；i＝1，...，k}表示点p附近的局部形状、qi(i＝1，...，k)为点p的k个近邻点进行曲面拟合。点p处的法方向可以用下述方法计算：首先构造矩阵，

[0060]

[0061] 其中 表示向量之间的叉乘，M(p，k)的较小的特征值对应的特征向量即为p点处的法方向。我们记该法方向为 我们统一的把朝向摄像机的一侧作为法方向 的正方向。

[0062] 2.4建立局部坐标系

[0063] 在点云各个点处建立局部坐标系，设点p的法向量为 其中nx，p，ny，p，nz，p法向量的三个分量，则这个p点就是局部坐标系的原点，X，Y，Z三个坐标轴分别为 Z＝N＝(nx，p，ny，p，nz，p)，
其中ψ和 通过下式计算：ψ＝arccos(nz，p)，

[0064] 2.5拟合二次曲面2 2

[0065] 点云模型P处待拟合的二次曲面为h(u，v)＝c0u+2c1uv+c2v，其中(u，v，h(u，2 2
v))为空间中的点，该二次曲面h(u，v)＝c0u+2c1uv+c2v 的系数c0 c1 c2通过最小化获得，其中A、B、μ为矩阵：

[0066]

[0067] ui、vi、hi为n个近邻点的坐标值，i＝1，...，n，c0 c1 c2为二次曲面的系数，通过μ＝[c0 c1 c2]T＝(ATA)-1ATB得到二次曲面的系数，其中T表示转置，[c0 c1 c2]T表示矩阵[c0 c1 c2]的转置矩阵；

[0068] 2.6计算局部几何量

[0069] 利用二次曲面h(u，v)＝c0u2+2c1uv+c2v2，计算p点处的局部几何量，包括两个主曲率k1(p)和k2(p)，k1(p)＜＝k2(p)以及对应的主曲率方向 和 图3a是各点主方向 的结果，图3b是图3a主方向 的局部放大图。

[0070] 3、树木点云模型的分割，包括以下三个步骤：

[0071] 3.1计算轴向分布密度

[0072] 大多数的树干及树枝都近似圆柱形，分布在上面的点云也呈圆柱面分布。圆柱面上对应主曲率值较小的主曲率方向与圆柱的轴向一致，所以树干及树枝上点云处的局部几何量也有相同的性质，即 与树干的轴向方向近似一致，所以我们在这里更加关心统一朝向地面的方向为 的正方向，在后面，我们称 为主方向。

[0073] 但是仅仅依靠近邻点云的主方向相似度无法实现树枝与树叶的分离，原因有如下的两点：

[0074] a、在树枝的某些位置由于形状不规则或遮挡而导致相邻的点也没有相似的主方向。

[0075] b、尽管大多数树叶的点云的主方向都杂乱无章，但是在当进行二次拟合时，当k近邻点的选取不能保证在同一平面时，拟合结果将体现出一定的随机性，某些位于树叶上的局部点云也可能具有相似的主方向。

[0076] 因此，仅仅考虑近邻点云方向的相似度没有充分利用点云的空间位置信息。在综合考虑点云主方向和空间位置关系后，我们注意树枝上点云的另外一个特点：树枝上点云在树枝轴向方向近似均匀分布。我们在树枝点云p1处，以p1为中心，以其主方向为轴向构建细长圆柱，在细长圆柱内近似均匀分布很多点云。而在树叶点云处，尽管某些局部近邻点云具有相似的主方向，但不满足在主方向上分布的特点。具体构建细长圆柱如图4所示。利用这个特点，我们可以实现枝叶分离。

[0077] 对点云模型中的点p，以点p为中心，以h为高，以r为半径构建圆柱S，圆柱S的轴向与点p的主方向 一致；其中高h被设置为10倍于扫描间距，半径r被手工设置为2倍于扫描间距；位于圆柱S内的每一个点p，将点p投影到圆柱S的中心轴上，投影点被记为Ps(p)，然后再以中心轴为中心，手工设置的固定长度α为长度选定线段u(p，S)，称线段u(p，S)为点p在圆柱S内的投影覆盖区域；当将圆柱S内的每一个点p投影到中心轴后，则得到了中心轴上的若干表现为一个个线段的投影覆盖区域，这些区域可能相互重叠，求取这些区域的并集，记为

[0078]

[0079] 记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S内的所有点在圆柱S内的分布密度和分布均匀情况，换而言之，表示了点p附近近邻点云是否沿点p的主曲率方向均匀分布；

[0080] 轴向分布密度C(p)，定义为

[0081] C(p)＝L[U(p，S)]/h，

[0082] 轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内覆盖的比例。被称为点p的轴向分布密度。

[0083] 如果点p是位于树枝上的点云，即使树枝比较细或者由于形状不规则而导致附近点主曲率方向不规则，只要点p的主方向与树枝轴向大致一致，也可以保证在点p构建的圆柱S内包含一定数量沿轴向分布的点云，从而获得较大的轴向分布密度C(p)。另一方面，如果点p是位于树叶上的点云，虽然点p附近点云可能与具有与点p相似的主方向，但很难实现在的主方向上分布，所以轴向分布密度C(p)有效的表示了点p位于树枝上的可能性。

[0084] 3.2通过轴向分布密度进行树枝点云与树叶点云的分离

[0085] 在计算出每个点对应的轴向分布密度C(p)之后，我们手工选定一个阈值β，分布密度值大于β被选定为种子点，首先计算没个种子点与最近邻种子点之间的距离，如果这个距离大于一个手工选定的阈值ε，我们认为该种子点为孤立种子点，孤立种子点被去除，随后我们将保留的种子点和种子点对应的圆柱S内所有点标记起来作为树枝上的点云，其余点云被认为是位于树叶上的点云。图5a显示了整个点云按照不同点对应的轴向分布密度C(p)用不同的颜色表示的模型。蓝色表示轴向分布密度C(p)最小，黄色表示轴向分布密度C(p)最大。图5b显示了通过我们的方法确定的属于树枝上的点云，从图中可以看到即使某些枝干比较细小或者被遮挡的比较严重，位于上面的点云仍然能被我们的方法准确的区分出来。

[0086] 3.3利用主曲率方向进行区域生长

[0087] 在属于不同枝干的点云分割分组过程中，我们将综合考虑点云的主方向与空间位置关系。我们在区域生长中要保证属于不同枝干的点云不会被划分到同一分组中，尽管经常以过分割为代价，我们会在后一节的区域合并过程中解决过分割的问题。

[0088] 首先，我们给出本节中近邻点的定义，本节中我们定义点p的近邻点为点云模型P中与点p的欧氏距离小于一定阈值λ的点。λ在本文中被设置为0.2m。

[0089] 开始，点云模型P中的每个点都被给予单独的标记。首先P中一个随机选取的点被作为种子点，对种子点的所有近邻点进行判断，如果近邻点的主方向与种子点的主方向夹角小于一定的角度阈值θ，此处θ被手工设置为15°，该近邻点会被划入种子点分组Wseed。之后这些近邻点被选为新的种子点进行相同规则的区域生长，试图将更多周围的点云划归到Wseed中，直到没有新点云会被Wseed吸收。之后在点云模型P中寻找未被划分的点作为新的种子点，重复上面的区域生长直到所有的点实现划分。

[0090] 上述区域生长算法具体表示过程如下所示。

[0091] 步骤(1)随机在点云模型P中寻找为未划分点p作为种子点；

[0092] 步骤(2)寻找点p的近邻点点集B＝{b0，...，bn}，计算其中每个点bi与点p的主方向的夹角，如果夹角值小于给定的角度阈值θ，则点bi被划分到与点p相同的分组Wseed，所有在该步骤中被划分到中的新点被记为点集Bin。如果点集Bin为空，则回到步骤(1)。如果Bin为不为空，选取Bin中的点作为新的种子点重复步骤(2)。

[0093] 步骤(3)选择新的种子点，重新执行步骤(2)。

[0094] 步骤(4)当P中所有点完成划分后，算法结束。

[0095] 步骤(2)中角度阈值θ的选取非常重要，如果选取的过小，则点云之间难以被划分到同一分组，形成大量只有一个点的分组，使整个区域生长过程无意义；如果选取的过大又可能导致不同枝干的点云被划分到同一分组中，形成错误的结果。

[0096] 区域生长结果如图6所示，从图中我们可以看出，这是一个过分割的结果，相同的枝干经常被分解为不同的部分，而且一些分组内只有较少的点，产生这种情况的原因与上一节中提到的树枝形状不规则导致主方向杂乱相同。该结果能够保证不同枝干上的点云不被划分到同一分组中。

[0097] 3.4区域合并

[0098] 区域合并的过程中受到下面两个约束的影响：

[0099] 相邻组对于两个点云分组W1和W2.我们使用Hausdorff距离h(W1，W2)＝min{‖p-q‖；点p∈W1，点q∈W2}来衡量两组之间的距离，当该距离小于一定的阈值时，我们称W1和W2为相邻组。

[0100] 组方向我们定义组W的组角度为 其中 为组内的点的主曲率方向，j为组内点的数量，由于主方向具有180°的随机性，所以我们首先随机从组内选择一个点的主方向D，保证组内每一个点的主曲率方向满足

[0101] 在上节中我们知道，过分割导致很多分组点云数量少，而只有点云数量足够大的组的组方向能够表示其所在树枝的轴向，可以指导区域合并，较少数量点云的组，其组方向无法表示其所在树枝的轴向，对于区域合并没有帮助，所以首先我们无条件的将点云数量小于一定阈值N的组合并到其所有相邻组中与之距离最近的组。经过这个过程，所有分组都具有较多数量的点云。图7是将点云数量小的分组合并后的分割情况示意图。

[0102] 经过上一步处理，每个分组内都有足够的点来表示该组所在枝干的轴向，各个分组的组方向被计算出来，任意两个相邻点云分组W1和W2.夹角用下式计算出来。-1

[0103] θ(W1，W2)＝cos ([(2-D(W1)·D(W2))/2])

[0104] 其中θ(W1，W2)是两个相邻点云分组W1和W2.的组方向的夹角，夹角θ(W1，W2.)是指导区域合并的重要约束，但是并不是唯一的约束，如果我们简单的把具有较小夹角θ的相邻组合并的话，合并结果将难以保证准确度，图8a是两个属于不同树枝的点云分组，点云组P和点云组Q是相邻组并且具有较小的夹角，但是两组显然不属于同一枝干。

[0105] 为了避免上述的错误合并，我们引入了一个新的限制条件，点p1和点p2(p1∈P和p2∈Q，)是点云分组P和点云分组Q中距离最近的两个点，店Pa是点云分组P中使‖pa-p1‖(pa∈P)最大化的点，点pb是点云分组Q中使‖pb-p2‖(pb∈Q)最大化的点。由点p1和点p2以及点pa和点pb确定两个方向f1＝pa-p1，f2＝pb-p2，新的限制条件为仅当方向f1和方向f2的夹角α大于一定的阈值，此处阈值设为140°，我们称这个限制为角度限制。图8b显示了由点p1和点p2以及点pa和点pb确定的两个方向形成的角度限制。

[0106] 在获得了区域合并过程中的参考量和限制条件后，我们对分组进行区域合并，这里我们首先计算任意两个近邻组之间的夹角并且将夹角存储在一张角度表中，从角度表中寻找夹角最小并且满足角度限制的两个组进行合并。形成的新组的组方向被重新计算，角度表格被更新。重复上面的过程指导组之间的夹角大于设定的阈值，此处阈值设定为22°。

[0107] 4、结果输出

[0108] 我们用不同的颜色表示不同的分组，结合点云数据显示出来。图9展示了经过区域合并后的分割结果。

[0109] 5、实验结果与结论

[0110] 我们在OpenGL的基础上，用C语言实现了本章介绍的树木点云分割的算法，我们的实验都是在一台Dual Core 3.0G，4GB内存，GeForce9600gso，操作系统为Windows XP的pc机上实现完成。

[0111] 我们在三个树木点云模型上验证了算法，第一个模型为一棵8米高的油松，为单侧扫描数据，该模型共有119796个点。第二个模型是一棵具有102201个点的9米高的白皮松。第三个模型为一棵11米高的油松，共有265426个点。所有的分割结果在图10a，图10b，图10c中展示出来。其中绿色的点云代表分布在树叶上的点云，不同树枝上的点用不同的颜色区分。

[0112] 从实验结果可以看到，我们的分离算法能够将以往算法无法分割的树木点云数据合理分组，在图10c油松中，尽管大量的细枝被树叶遮挡，露出部分即使依靠肉眼进行人工区分也有很大的难度，我们的算法仍然能将细枝提取出来。

[0113] 本发明的方法的特色和创新在于根据树木的特点，在点云中依靠二次曲面拟合计算每个点对应的主曲率方向，按照树枝的形态特征定义判断点位于树枝可能性的轴向分布密度，通过该轴向分布密度树枝点云与树叶点云被区分开。之后，不同树枝上的点云按照其所对应的主曲率方向进行区域生长和区域合并，实现不同树枝上点云的分离。

[0114] 在很多树木的建模中，这个树木点云的分割结果可以有效的提供信息，表达树木的结构和几何特征，辅助建模的准确性，并且树木点云的准确自动分割可以应用于林业测量，多树木点云配准等领域。

[0115] 以上所述，仅为本发明中的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉该技术的人在本发明所揭露的技术范围内，可理解想到的变换或替换，都应涵盖在本发明的包含范围之内，因此，本发明的保护范围应该以权利要求书的保护范围为准。