专利名称：树木点云数据的自动分割方法
技术领域：
本发明属于微分几何、计算数学、计算机图形学和计算机视觉技术领域，涉及一种 利用三维激光扫描仪进行树木测量得到树木点云数据，并根据点云数据来进行属于不同器 官间点云的自动分割的方法。在虚拟现实、电脑游戏、数据压缩、特征提取、林业测量、植物 三维3D重建等领域具有重要的应用价值。
背景技术：
点云模型是一种无组织的点云集合(Unorganized Points)。在几何压缩和传输、 交互编辑、纹理映射、参数化等应用方面，需要将点云数据划分为特征单一，互不重叠的区 域，这需要使用点云分割技术。针对树木的生物学特点，树木扫描点云可以被分为树枝点云和树叶点云，其中位 于树枝上的点云又可以按照所处的不同的枝干进行进一步划分。树木点云模型的准确分割对模型的应用具有重要意义。在进行模型重建的过程中，由于树枝与树叶的重建方法有较 大的区别，所以已有的大部分重建方法在重建之前需要对点云进行树枝树叶的分离。同样 道理，直接在点云模型上进行的林业测量工作也需要明确的知道哪些点云位于树枝哪些点 云位于树干上。树木点云模型的配准工作中，如果能对不同的树枝上的点云进行准确的区 分会对配准工作带来很大的帮助。尽管近年来树木点云的分割算法没有被单独的研究过，但在近年的许多基于点云 的树木重建方法中，提出了一些针对树木点云的形状分解或者三维分割方法。Xu利用将到根节点的最短路径相似的点归类的方法进行点云的分组，每个根节点 的选取对最后的分割结果具有重大影响，然而根节点的选取并不是自动的，这导致点云的 分组工作需要较多的手工交互。同时在树枝的分叉处，不同树枝上的点可能具有相同的到 根节点的最短路径，这样的结果就是属于不同树枝的点可能被划归到同一组中。Cheng使 用手工的方法进行树叶与树枝的分离，大量属于细枝的点云被当作位于树叶上的点云被处 理。同时，Cheng使用不同枝干在深度图像中会发生深度跳变的性质进行树干点云的分离， 不同枝干间如果深度相似的话将无法成功区分。在Quan的重建算法中，从图像中恢复三维点云，然后对三维点云进行手工交互的 分割，但三维分割的准确性受到相机参数估计准确性的影响。所以该方法虽然可以获得较 好的视觉效果，但是实际准确性并不理想。另外手工交互可以处理叶片较大，树叶与树枝区 分明显的植物，但如果树叶分布密集，与树枝大量混杂在一起就难于靠手工分割获得较好 的效果。Bucksch提出了一套基于八叉树和图论的方法从树木点云模型中实现树枝分割和 骨架提取的算法，这套算法只能用于没有树叶的模型，并且在分割过程中无法克服过分割 的问题。

发明内容
本发明欲解决在分割过程中无法克服过分割的技术问题，本发明的目的是针对现 实世界中由激光扫描得到的树木点云数据，提供一个激光扫描点云模型符合树木实际器官 分布的准确的分割方法。为实现上述目的，本发明的技术解决方案是提供一种基于主曲率分析的树木点云 分割方法，该点云分割步骤包括步骤Sl 利用激光扫描仪扫描直接采集树木的扫描点云数据并对点云数据预处 理，按照点云数据中每个点的坐标进行空间划分，实现三维空间的数据存储结构称为kd树 (k-dimensional tree)； 步骤S2 对于点云数据的每一个点，利用点云数据的kd树查找多个近邻点，根据最 小二乘方法把这些点拟合出一个平面，以这个平面的法向量作为点云法向量的初始估计值；步骤S3 对于点云数据的每一个点，利用其法向量、切平面构造局部三维直角坐 标系；利用点云数据的kd树查找多个近邻点；步骤S4 对于查找到的近邻点，利用这些近邻点拟合二次曲面；步骤S5 对于点云数据的每一个点，利用该点拟合出的二次曲面计算主曲率；步骤S6 对于点云数据的每一个点，利用主曲率方向计算轴向分布密度；步骤S7 利用轴向分布密度将属于树枝上的点云与属于树叶上的点云区分；步骤S8 对于属于树枝上的点云，利用主曲率方向进行区域生长，产生过分割的 分割结果；步骤S9 对于过分割的树枝上的点云，依照相邻组内的点云数量以及依照分组中 所有点云的主曲率方向的平均值所确定的组角度进行区域合并，得到符合树木树枝器官分 布的分割结果。其中，所述拟合二次曲面为h (u，ν) = cqu2+2CiuV+C2V2，其中(u，v，h(u，v))为空间
中的点，该二次曲面h (u，ν) =cqu2+2ciuV+C2V2的系数c。c1 C2通过最小化 in | | a μ-b | |2
获得，其中Α、B、μ为矩阵 、 、比为！！个近邻点的坐标值，土 = !，...，!!，。C1 C2为二次曲面的系数，通过 μ = [c0 C1 c2]T= (AtA)-1AtB得到二次曲面的系数，其中T表示转置，[C(l C1 0工表示矩阵 [C0 C1 C2]的转置矩阵；利用拟合二次曲面计算出点云模型P中P点处的局部几何量，包括 两个主曲率h (ρ)和1^2 (ρ)，Μρ) <= k2(p)以及对应的主曲率方向AO)和式O)。其中，所述点云区分是通过计算各个点的轴向分布密度实现属于树枝上的点云与 属于树叶上的点云区分。其中，所述轴向分布密度，由下列方法确定对点云模型P中的点P，以点P为中 心，以h为高，以r为半径构建圆柱S，圆柱S的轴向与点ρ的主方向式(内一致；其中高h被设置为10倍于扫描间距，半径r被手工设置为2倍于扫描间距；位于圆柱S内的每一个点 P，将点P投影到圆柱S的中心轴上，投影点被记为Ps (p)，然后再以中心轴为中心，设置的固 定长度α为长度选定线段u (ρ，S)，称选定线段u (ρ，S)为点ρ在圆柱S内的投影覆盖区域； 当将圆柱S内的每一个点ρ投影到中心轴后，则得到了中心轴上的若干表现为一个个线段 的投影覆盖区域，这些区域可能相互重叠，求取这些区域的并集，记为 记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S 内的所有点在圆柱S内的分布密度和分布均勻情况，表示了点ρ附近近邻点云是否沿点ρ 的主曲率方向均勻分布；轴向分布密度C(p)，定义为C(p) = L[U(ρ, S)]/h，轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内 覆盖的比例。其中，所述将属于树枝上的点云与属于树叶上的点云区分，由下列方法确定设定 一个阈值β，将点云模型P中轴向分布密度值大于β的点选定为种子点，首先孤立的种 子点被去除，随后保留的种子点和种子点对应的圆柱S内所有点标记起来作为树枝上的点 云，其余点云被认为是位于树叶上的点云。其中，所述相邻组是对于两个通过分割获得的点云分组W1和W2,使用Hausdorff距 ^hd1, W2) = min{ Il p-q Il ；点P e W1,点q e ff2}来衡量两组之间的距离，当该距离小于 一定的阈值时，称W1和W2为相邻组。其中，所述组角度的定义为旳= Σ J1(P1) ]/j ,其中W为通过分割获得点云
分组，J1Cp,)为组内的点Pi的主方向，j为组内点的数量。其中，计算组角度时随机从组内选择一个点的主曲率方向D，对组内每一个点的主 曲率方向孓(A)进行180°的调整以满足J1O^rD〉0。其中，所述依照相邻组内的点云数量进行区域合并，是将点云数量小于设定阈值N 的组合并到其所有相邻组中与之距离最近的组。其中，依照分组中所有点云的主曲率方向的平均值的夹角进行区域合并，是计算 任意两个近邻组中所有点云的主曲率方向的平均值之间的夹角并且将夹角存储在一张角 度表中，从角度表中寻找夹角最小并且满足角度限制的两个组进行合并，形成的新组的组 方向被重新计算，角度表格被更新；重复上面的过程直到组之间的夹角大于设定的阈值。本发明的有益效果是对树木点云数据直接进行分割。利用点云的坐标信息和点云 的主方向信息。本发明与前人方法的区别主要体现在，定义轴向分布密度，对于点云数据的 每一个点，利用其轴向分布密度判断是否位于树枝，此外本发明还利用主曲率方向指导树 枝上的点云进行区域生长和区域合并。实验表明，本发明的方法获取的树木点云的分割结 果准确，符合实际器官分布。我们利用三维激光扫描仪获取实物的表面信息，并根据扫描数 据利用常规方法计算出各个点的法向量，再计算求出主曲率和主方向，定义了表示点云近 邻点云分布情况的“轴向分布密度”，利用轴向分布密度分离树枝与树叶点云，利用主曲率 方向为引导进行区域生长和区域合并分离各个枝干之间的连接关系。本发明所获得的计算 结果能用于计算机图形学各应用领域，包括虚拟现实、电脑游戏、数据压缩、特征提取、林业测量、植物三维3D重建等领域具有重要的应用价值。利用本发明，可以自动、准确地对树木 扫描点云模型进行符合实际树木器官分布的分割。


图1本发明方法的流程图； 图2本发明采用的单面扫描数据；图3a、图3b树木点云主方向分布规律示意图；图4圆柱构造示意图；图5a、图5b轴向分布密度的可视化表示和被判断属于树枝上的点云；图6区域生长的结果示意图；图7小分组被合并后的分割情况示意图；图8a、图8b区域合并的角度限制示意图；图9区域合并后的分割结果示意图；图10a、图10b、图IOc三个树木点云数据的分割结果示意图。
具体实施例方式下面结合附图详细说明本发明技术方案中所涉及的各个细节问题。应指出的是， 所描述的实施例仅旨在便于对本发明的理解，而对其不起任何限定作用。1、方法概述(overview of approach)如图1示出本发明整个方法的流程，其中本发明算法的主要步骤包括1)、局部几何量计算，包括6个子步骤(a)点云的获取及预处理、(b)点云法方向 估计、(c)局部坐标系的构造、(d)利用近邻点拟合二次曲面、(e)利用二次曲面计算主曲 率、(f)计算轴向分布密度。2)、对树木点云模型进行分割，包括3个子步骤(g)利用轴向分布密度区分属于 树枝上的点云与属于树叶上的点云、(h)利用主曲率方向进行区域生长、⑴依照相邻组内 的点云数量以及组内点云主曲率平均值的夹角进行区域合并。3)、输出计算结果，存储分割结果，将点云按照分割以不同的颜色表示。2、数据预处理首先，计算真实树木的扫描数据(如图2示出采用的扫描数据)的局部几何量，点 云的局部几何量，包括法方向、主曲率大小和主曲率方向，可以表示点云的局部形状特征， 是点云分割的重要依据。计算一个点(记为P)的局部几何量包括以下七个步骤2. 1 创建 kd 树在计算三维点云数据法向量和主曲率、主方向的过程中都需要用到近邻点，我们 使用建立点云数据的3维空间的二分查找树，简称为kd树(k-dimensional tree)来查找 近邻点。首先，建立kd树。kd树基于点的空间位置信息，通过二分法迭代划分三维空间，实 现最优存储。在kd树上，进行k近邻查找的时间复杂度为O(Iog2Ii)，这里η为点云数据的 点的个数。2. 2搜索近邻点
由于预处理阶段建立了 kd树，以点云模型P中点ρ为查询点，基于欧式距离查找k 近邻，比如k = 20近邻或k = 30近邻，根据数据扫描精度确定近邻点的个数，扫描精度较 低则取15个近邻点，扫描精度较高则取30个近邻点，这里记qi(i = 1，2，·.·，m)为查询得 到的m个近邻点。2. 3计算各个点的法向量对于点云数据的每一个点，利用点云数据的kd树查找15个或30个近邻点，对整 个点云模型P中的每个点P选择其近邻点组成的点集N(P ；k) = {qi ;i = 1，...，k}表示 点P附近的局部形状、Qi(I = L--^k)为点ρ的k个近邻点进行曲面拟合。点ρ处的法 方向可以用下述方法计算首先构造矩阵， 其中 表示向量之间的叉乘，M(p，k)的较小的特征值对应的特征向量即为ρ点处 的法方向。我们记该法方向为H(妁，我们统一的把朝向摄像机的一侧作为法方向HO)的正 方向。2. 4建立局部坐标系在点云各个点处建立局部坐标系，设点ρ的法向量为巩妁=i.^p,ny p, nzp)，其中 nx,p, ny,p，nz,p法向量的三个分量，则这个ρ点就是局部坐标系的原点，X，Y，Z三个坐标轴分 别为X = (-sin φ, cos 屮，0) ,Y = (cos ^ cos φ, cosy sin <ρ, -^ ηψ), I = N= (nx,p, ny,p, nz,p),
其中 Ψ 和φ通过下式计算 2.5拟合二次曲面点云模型P处待拟合的二次曲面为h (u，v) = Cqu2+2CiuV+C2V2，其中(u，ν, h(u， ν))为空间中的点，该二次曲面h(u，ν) =CqU2+2CiUV+C2V2的系数cQ C1 C2通过最小化
min I |Αμ-B| 12获得，其中A、B、μ为矩阵 、 、比为！！个近邻点的坐标值，土 = !，...，!!，。C1 C2为二次曲面的系数，通过 μ = [c0 C1 c2]T= (AtA)-1AtB得到二次曲面的系数，其中T表示转置，[C(l C1 0工表示矩阵 [c0 C1 C2]的转置矩阵；2. 6计算局部几何量利用二次曲面h(u，ν) = c0u2+2ciuv+c2v2,计算ρ点处的局部几何量，包括两个主 曲率Ic1 (ρ)和1^2 (P)A1(P) <= k2(p)以及对应的主曲率方向J1 (ρ)和式(ρ)。图3a是各点主 方向A(P)的结果，图3b是图3a主方向的局部放大图。3、树木点云模型的分割，包括以下三个步骤3.1计算轴向分布密度大多数的树干及树枝都近似圆柱形，分布在上面的点云也呈圆柱面分布。圆柱 面上对应主曲率值较小的主曲率方向与圆柱的轴向一致，所以树干及树枝上点云处的局部几何量也有相同的性质，即io)与树干的轴向方向近似一致，所以我们在这里更加关心 dx(P)，统一朝向地面的方向为式O)的正方向，在后面，我们称J10)为主方向。但是仅仅依靠近邻点云的主方向相似度无法实现树枝与树叶的分离，原因有如下 的两点a、在树枝的某些位置由于形状不规则或遮挡而导致相邻的点也没有相似的主方 向。b、尽管大多数树叶的点云的主方向都杂乱无章，但是在当进行二次拟合时，当k 近邻点的选取不能保证在同一平面时，拟合结果将体现出一定的随机性，某些位于树叶上 的局部点云也可能具有相似的主方向。因此，仅仅考虑近邻点云方向的相似度没有充分利用点云的空间位置信息。在综 合考虑点云主方向和空间位置关系后，我们注意树枝上点云的另外一个特点树枝上点云 在树枝轴向方向近似均勻分布。我们在树枝点云P1处，以P1为中心，以其主方向为轴向构 建细长圆柱，在细长圆柱内近似均勻分布很多点云。而在树叶点云处，尽管某些局部近邻点 云具有相似的主方向，但不满足在主方向上分布的特点。具体构建细长圆柱如图4所示。利 用这个特点，我们可以实现枝叶分离。对点云模型中的点p，以点ρ为中心，以h为高，以r为半径构建圆柱S,圆柱S的 轴向与点P的主方向J1(P)—致；其中高h被设置为10倍于扫描间距，半径r被手工设置为 2倍于扫描间距；位于圆柱S内的每一个点p，将点ρ投影到圆柱S的中心轴上，投影点被 记为Ps(P),然后再以中心轴为中心，手工设置的固定长度α为长度选定线段u (ρ，S)，称线 段u(p，S)为点ρ在圆柱S内的投影覆盖区域；当将圆柱S内的每一个点ρ投影到中心轴 后，则得到了中心轴上的若干表现为一个个线段的投影覆盖区域，这些区域可能相互重叠， 求取这些区域的并集，记为 记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S 内的所有点在圆柱S内的分布密度和分布均勻情况，换而言之，表示了点ρ附近近邻点云是 否沿点P的主曲率方向均勻分布；轴向分布密度C (p)，定义为C(p) = L[U(p，S)]/h，轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内 覆盖的比例。被称为点P的轴向分布密度。如果点ρ是位于树枝上的点云，即使树枝比较细或者由于形状不规则而导致附近 点主曲率方向不规则，只要点P的主方向与树枝轴向大致一致，也可以保证在点P构建的圆 柱S内包含一定数量沿轴向分布的点云，从而获得较大的轴向分布密度C (P)。另一方面，如 果点P是位于树叶上的点云，虽然点P附近点云可能与具有与点P相似的主方向，但很难实 现在的主方向上分布，所以轴向分布密度C(P)有效的表示了点P位于树枝上的可能性。3. 2通过轴向分布密度进行树枝点云与树叶点云的分离在计算出每个点对应的轴向分布密度C(p)之后，我们手工选定一个阈值β，分布 密度值大于β被选定为种子点，首先计算没个种子点与最近邻种子点之间的距离，如果这个距离大于一个手工选定的阈值ε，我们认为该种子点为孤立种子点，孤立种子点被去除， 随后我们将保留的种子点和种子点对应的圆柱S内所有点标记起来作为树枝上的点云，其 余点云被认为是位于树叶上的点云。图5a显示了整个点云按照不同点对应的轴向分布密 度C(p)用不同的颜色表示的模型。蓝色表示轴向分布密度C(p)最小，黄色表示轴向分布 密度C(p)最大。图5b显示了通过我们的方法确定的属于树枝上的点云，从图中可以看到 即使某些枝干比较细小或者被遮挡的比较严重，位于上面的点云仍然能被我们的方法准确 的区分出来。3. 3利用主曲率方向进行区域生长在属于不同枝干的点云分割分组过程中，我们将综合考虑点云的主方向与空间位 置关系。我们在区域生长中要保证属于不同枝干的点云不会被划分到同一分组中，尽管经 常以过分割为代价，我们会在后一节的区域合并过程中解决过分割的问题。首先，我们给出本节中近邻点的定义，本节中我们定义点ρ的近邻点为点云模型P 中与点P的欧氏距离小于一定阈值λ的点。λ在本文中被设置为0. 2m。开始，点云模型P中的每个点都被给予单独的标记。首先P中一个随机选取的点 被作为种子点，对种子点的所有近邻点进行判断，如果近邻点的主方向与种子点的主方向 夹角小于一定的角度阈值Θ，此处θ被手工设置为15°，该近邻点会被划入种子点分组 Wseed。之后这些近邻点被选为新的种子点进行相同规则的区域生长，试图将更多周围的点云 划归到Wseed中，直到没有新点云会被Wseed吸收。之后在点云模型P中寻找未被划分的点作 为新的种子点，重复上面的区域生长直到所有的点实现划分。上述区域生长算法具体表示过程如下所示。步骤(1)随机在点云模型P中寻找为未划分点ρ作为种子点；步骤(2)寻找点ρ的近邻点点集B = {b0,. . .，bn}，计算其中每个点h与点ρ的主 方向的夹角，如果夹角值小于给定的角度阈值θ，则点h被划分到与点ρ相同的分组Wsrad， 所有在该步骤中被划分到中的新点被记为点集Bin。如果点集Bin为空，则回到步骤(1)。如 果Bin为不为空，选取Bin中的点作为新的种子点重复步骤⑵。步骤(3)选择新的种子点，重新执行步骤(2)。步骤(4)当P中所有点完成划分后，算法结束。步骤⑵中角度阈值θ的选取非常重要，如果选取的过小，则点云之间难以被划 分到同一分组，形成大量只有一个点的分组，使整个区域生长过程无意义；如果选取的过大 又可能导致不同枝干的点云被划分到同一分组中，形成错误的结果。区域生长结果如图6所示，从图中我们可以看出，这是一个过分割的结果，相同的 枝干经常被分解为不同的部分，而且一些分组内只有较少的点，产生这种情况的原因与上 一节中提到的树枝形状不规则导致主方向杂乱相同。该结果能够保证不同枝干上的点云不 被划分到同一分组中。3.4区域合并区域合并的过程中受到下面两个约束的影响相邻组对于两个点云分组W1和W2.我们使用Hausdorff距离h (W1，W2)= min{ Il P-Q Il ；点P e W1,点q e ff2}来衡量两组之间的距离，当该距离小于一定的阈值时， 我们称W1和W2为相邻组。
组方向我们定义组W的组角度为/K旳=[Σ^(Α)]Λ/，其中为组内的点 的主曲率方向，j为组内点的数量，由于主方向具有180°的随机性，所以我们首先随机从 组内选择一个点的主方向D，保证组内每一个点的主曲率方向满足J1O,) ·Ζ) > O。在上节中我们知道，过分割导致很多分组点云数量少，而只有点云数量足够大的 组的组方向能够表示其所在树枝的轴向，可以指导区域合并，较少数量点云的组，其组方向 无法表示其所在树枝的轴向，对于区域合并没有帮助，所以首先我们无条件的将点云数量 小于一定阈值N的组合并到其所有相邻组中与之距离最近的组。经过这个过程，所有分组 都具有较多数量的点云。图7是将点云数量小的分组合并后的分割情况示意图。经过上一步处理，每个分组内都有足够的点来表示该组所在枝干的轴向，各个分 组的组方向被计算出来，任意两个相邻点云分组Wl和W2.夹角用下式计算出来。θ (W1, W2) = cos-1 ([(2-D (W1) ‘ D (W2)) /2])其中θ (WijW2)是两个相邻点云分组WjPW2.的组方向的夹角，夹角θ (W1,W2.)是 指导区域合并的重要约束，但是并不是唯一的约束，如果我们简单的把具有较小夹角θ的 相邻组合并的话，合并结果将难以保证准确度，图8a是两个属于不同树枝的点云分组，点 云组P和点云组Q是相邻组并且具有较小的夹角，但是两组显然不属于同一枝干。为了避免上述的错误合并，我们引入了一个新的限制条件，点P1和点P2(P1 e ρ 和P2 e Q，)是点云分组P和点云分组Q中距离最近的两个点，店Pa是点云分组P中 使Il Pa-P1 Il (pa e P)最大化的点，点pb是点云分组Q中使Il pb-p2 Il (pb e Q)最大化的点。 由点P1和点P2以及点Pa和点Pb确定两个方向fi = Pa-P1, f2 = Pb-P2，新的限制条件为仅 当方向fi和方向f2的夹角α大于一定的阈值，此处阈值设为140°，我们称这个限制为角 度限制。图8b显示了由点P1和点P2以及点Pa和点Pb确定的两个方向形成的角度限制。在获得了区域合并过程中的参考量和限制条件后，我们对分组进行区域合并，这 里我们首先计算任意两个近邻组之间的夹角并且将夹角存储在一张角度表中，从角度表中 寻找夹角最小并且满足角度限制的两个组进行合并。形成的新组的组方向被重新计算，角 度表格被更新。重复上面的过程指导组之间的夹角大于设定的阈值，此处阈值设定为22°。4、结果输出我们用不同的颜色表示不同的分组，结合点云数据显示出来。图9展示了经过区 域合并后的分割结果。5、实验结果与结论我们在OpenGL的基础上，用C语言实现了本章介绍的树木点云分割的算法，我们 的实验都是在一台Dual Core 3. 0G，4GB内存，GeForce9600gso，操作系统为Windows XP的 pc机上实现完成。我们在三个树木点云模型上验证了算法，第一个模型为一棵8米高的油松，为单 侧扫描数据，该模型共有119796个点。第二个模型是一棵具有102201个点的9米高的白 皮松。第三个模型为一棵11米高的油松，共有265426个点。所有的分割结果在图10a，图 10b，图IOc中展示出来。其中绿色的点云代表分布在树叶上的点云，不同树枝上的点用不 同的颜色区分。从实验结果可以看到，我们的分离算法能够将以往算法无法分割的树木点云数据 合理分组，在图IOc油松中，尽管大量的细枝被树叶遮挡，露出部分即使依靠肉眼进行人工区分也有很大的难度，我们的算法仍然能将细枝提取出来。
本发明的方法的特色和创新在于根据树木的特点，在点云中依靠二次曲面拟合计 算每个点对应的主曲率方向，按照树枝的形态特征定义判断点位于树枝可能性的轴向分布 密度，通过该轴向分布密度树枝点云与树叶点云被区分开。之后，不同树枝上的点云按照其 所对应的主曲率方向进行区域生长和区域合并，实现不同树枝上点云的分离。在很多树木的建模中，这个树木点云的分割结果可以有效的提供信息，表达树木 的结构和几何特征，辅助建模的准确性，并且树木点云的准确自动分割可以应用于林业测 量，多树木点云配准等领域。以上所述，仅为本发明中的具体实施方式
，但本发明的保护范围并不局限于此，任 何熟悉该技术的人在本发明所揭露的技术范围内，可理解想到的变换或替换，都应涵盖在 本发明的包含范围之内，因此，本发明的保护范围应该以权利要求书的保护范围为准。
权利要求
一种树木点云数据的自动分割方法，其特征在于，该点云分割步骤包括步骤S1利用激光扫描仪扫描直接采集树木的扫描点云数据并对点云数据预处理，按照点云数据中每个点的坐标进行空间划分，实现三维空间的数据存储结构称为kd树(k-dimensional tree)；步骤S2对于点云数据的每一个点，利用点云数据的kd树查找多个近邻点，根据最小二乘方法把这些点拟合出一个平面，以这个平面的法向量作为点云法向量的初始估计值；步骤S3对于点云数据的每一个点，利用其法向量、切平面构造局部三维直角坐标系；利用点云数据的kd树查找多个近邻点；步骤S4对于查找到的近邻点，利用这些近邻点拟合二次曲面；步骤S5对于点云数据的每一个点，利用该点拟合出的二次曲面计算主曲率；步骤S6对于点云数据的每一个点，利用主曲率方向计算轴向分布密度；步骤S7利用轴向分布密度将属于树枝上的点云与属于树叶上的点云区分；步骤S8对于属于树枝上的点云，利用主曲率方向进行区域生长，产生过分割的分割结果；步骤S9对于过分割的树枝上的点云，依照相邻组内的点云数量以及依照分组中所有点云的主曲率方向的平均值所确定的组角度进行区域合并，得到符合树木树枝器官分布的分割结果。
2.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述拟合二次曲 面为 h(u，v) = cqu2+2Ciuv+c2v2，其中(u，v，h(u，v))为空间中的点，该二次曲面 h(u，ν)=C。U2+2ClUV+C2v2的系数CtlC1C2通过最小化mjn | B| |2获得，其中A、B、μ为矩阵 、\、比为η个近邻点的坐标值，i = 1，-,n,c0 C1 C2为二次曲面的系数，通过μ = [C0 C1 C2Jt= (AtA)-1AtB得到二次曲面的系数，其中T表示转置，[Ctl C1 (3工表示矩阵[Ctl C1 C2]的转置矩阵；利用拟合二次曲面计算出点云模型P中P点处的局部几何量，包括两个主 曲率k“p)和Ii2(P)J1 (P) <= k2(p)以及对应的主曲率方向义(P)和式O)。
3.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述点云区分是 通过计算各个点的轴向分布密度实现属于树枝上的点云与属于树叶上的点云区分。
4.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述轴向分布密 度，由下列方法确定对点云模型P中的点P，以点P为中心，以h为高，以r为半径构建圆 柱S，圆柱S的轴向与点ρ的主方向J1(P)—致；其中高h被设置为10倍于扫描间距，半径r 被手工设置为2倍于扫描间距；位于圆柱S内的每一个点p，将点ρ投影到圆柱S的中心轴 上，投影点被记为Ps(P),然后再以中心轴为中心，设置的固定长度α为长度选定线段u(p， S)，称选定线段u (p，S)为点ρ在圆柱S内的投影覆盖区域；当将圆柱S内的每一个点ρ投 影到中心轴后，则得到了中心轴上的若干表现为一个个线段的投影覆盖区域，这些区域可能相互重叠，求取这些区域的并集，记为U (P, S)= ∪u{p,S)p∈P,p∈S记L[U(p，S)]为投影覆盖区域并集的长度，长度L[U(p，S)]能够同时表示圆柱S内的 所有点在圆柱S内的分布密度和分布均勻情况，表示了点ρ附近近邻点云是否沿点ρ的主 曲率方向均勻分布；轴向分布密度C(p)，定义为C(p) = L [U (p，S)]/h，轴向分布密度C(p)表示了所有投影覆盖区域并集的总长度在圆柱S的轴高度内覆盖 的比例。
5.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述将属于树枝 上的点云与属于树叶上的点云区分，由下列方法确定设定一个阈值β，将点云模型P中轴 向分布密度值大于β的点选定为种子点，首先孤立的种子点被去除，随后保留的种子点和 种子点对应的圆柱S内所有点标记起来作为树枝上的点云，其余点云被认为是位于树叶上 的点云。
6.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述相邻组是对 于两个通过分割获得的点云分组W1和W2,使用Hausdorff距离WW1，W2) = min{ || p-q || ； 点ρ e W1,点q e WJ来衡量两组之间的距离，当该距离小于一定的阈值时，称W1和W2为相 邻组。
7.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述组角度的定 义为D(W) = [ Σ ^1(Pl)Vj ,其中W为通过分割获得点云分组，&(凡)为组内的点Pi的主方 向，j为组内点的数量。
8.按权利要求7所述的树木点云数据的自动分割方法，其特征在于，计算组角度时随 机从组内选择一个点的主曲率方向D，对组内每一个点的主曲率方向式(ρ,.)进行180°的调 整以满足忑(几)·!)> O0
9.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，所述依照相邻组 内的点云数量进行区域合并，是将点云数量小于设定阈值N的组合并到其所有相邻组中与 之距离最近的组。
10.按权利要求1所述的树木点云数据的自动分割方法，其特征在于，依照分组中所有 点云的主曲率方向的平均值的夹角进行区域合并，是计算任意两个近邻组中所有点云的主 曲率方向的平均值之间的夹角并且将夹角存储在一张角度表中，从角度表中寻找夹角最小 并且满足角度限制的两个组进行合并，形成的新组的组方向被重新计算，角度表格被更新； 重复上面的过程直到组之间的夹角大于设定的阈值。
全文摘要
本发明是一种树木点云数据的自动分割方法，该方法的步骤包括点云的获取及预处理，点云法方向估计，局部坐标系的构造，近邻点拟合二次曲面，利用二次曲面计算主曲率，定义并计算轴向分布密度，利用轴向分布密度区分树枝点云与树叶点云，对树枝点云进行区域生长，对树枝点云进行区域合并。本发明利用激光扫描仪的树木扫描数据和估计的主曲率，实现树木扫描点云符合实际器官分布情况的分割。该方法通过局部主曲率方向实现树木点云扫描数据不同器官间的自动分割，算法简单，计算结果准确。其计算结果在树木点云3D重建、林业测量以及树木点云的配准等领域具有重要的应用价值。
文档编号G01B11/24GK101839701SQ201010184490
公开日2010年9月22日 申请日期2010年5月27日 优先权日2010年5月27日
发明者代明睿, 张晓鹏, 李红军 申请人:中国科学院自动化研究所