一种基于结构分析的点云场景树木提取方法与流程

1.本发明属于树木提取方法技术领域，涉及一种基于结构分析的点云场景树木提取方法。


背景技术：

2.树木是城市道路建设和发展的重要组成部分，其在维护环境质量、减少污染和城市景观方面发挥着至关重要的作用。由于场景对象的多样性和邻近性，很难从城市点云场景数据中准确地提取单棵树木。目前，已有的树木提取方法可以分为两类：基于分割的树木提取方法以及基于机器学习的树木提取方法。
3.①
基于分割的树木提取方法
4.rutzinger通过确定每株树木的树冠中心位置，根据就近原则，将其它点云数据划分到距离最近的树冠中心实现树木的分割。yang等通过对点云数据三维结构的分析提取出树干，并将树干与地面相交的位置作为树木的位置。得到树木的位置后，用分层最小分割法来分割出树木。廖通过trimblerealworks对采集的点云数据分类为地面、建筑、树木、标牌、电力线和杂点等，采用dbscan密度聚类算法实现单根树木的提取。然后提出了基于密度特征的格网竞争算法对重叠的树冠点云进行精细分割。基于分割的方法往往从点云场景数据中提取单个树林。在真实场景中，相邻树木的树冠往往重叠，增加了单个树木分割的难度。
5.②
基于机器学习的树木提取方法
6.li在计算了16个局部几何特征(如宽度，高度，空间分布模式等)后，采用了离散adaboost算法将点云分为树干和树冠。利用相邻树之间的不连通性和单棵树内的邻接性，对单株树进行定位和分割；heinzel等提出了一种最小化马尔可夫随机场能量的约束谱聚类方法提取场景中的树木。但是有监督机器学习方法需要人工选择训练数据。xiang在场景分割的基础上，提取每个分割点云簇的几何特征，然后利用四个分类器(支持向量机、随机森林，朴素贝叶斯、极限学习机)将点云场景分为六类：建筑物，电线杆，汽车，树木，地面等。虽然利用机器学习的方法能较好的对点云场景进行分类与识别，但往往依赖领域专家手动设定特征。


技术实现要素：

7.本发明的目的是提供一种基于结构分析的点云场景树木提取方法，解决了现有技术中存在的相邻树木间重叠冠层的导致分割不准确问题。
8.本发明所采用的技术方案是，一种基于结构分析的点云场景树木提取方法，包括以下步骤：
9.步骤1、沿x、y轴对三维点云数据进行栅格化，寻找每个栅格内z值的最小值，根据每个栅格内的z值最小值、每个点z值，将点云划分为地面点、低位置点、高位置点；
10.步骤2、对全部低位置点进行分割，得到多个点云簇，并根据点云簇的几何特征提取候选树干；
11.步骤3、对全部高位置点进行分割，得到多个点云簇，并根据点云簇的空间分布模式、最小外接矩形的投影面积提取候选树冠；
12.步骤4、候选树冠点云簇的最小外接矩形是否仅覆盖一个候选树干点云簇，若是，则完成候选树木提取；否则删除候选树干或进行下一步；
13.步骤5、判断候选树冠点云簇匹配的多个提取候选树干为与树木交缠的杆状物或多棵树的树冠互相交叠，若为与树木交缠的杆状物，则移除与树木交缠的杆状物；若为多棵树的树冠互相交叠，对相邻树木的重叠冠层进行分割，将交叠的点云划分到各自所属的树木中，完成单棵树木点云的分割。
14.本发明的特点还在于：
15.步骤1包括以下步骤：
16.步骤1.1、沿x、y轴对三维点云数据进行栅格化，寻找每个栅格内z值的最小值z
localmin
；
17.步骤1.2、根据下式将点云划分为地面点g
ground
、低位置点g
lowlayer
、高位置点g
highlayer
；
[0018][0019]
上式中，为栅格内的任意一点p
i
的z值。
[0020]
步骤2包括以下步骤：
[0021]
步骤2.1、利用dbscan聚类算法对全部低位置点进行分割，得到多个点云簇；
[0022]
步骤2.2、将多个点云簇投影到xoy平面，计算每个点云簇的投影面积；
[0023]
步骤2.3、计算每个点云簇中z值最大值z
imax
与z值最小值z
imin
的差值δz，即点云簇高度；
[0024]
步骤2.4、若点云簇的投影面积、点云簇高度同时满足下述条件，则判定该点云簇为候选树干点云：
[0025]
条件一、投影面积小于0.4；
[0026]
条件二、点云簇高度大于1；
[0027]
条件三、点云簇最低点z
min
与地面接近。
[0028]
每个点云簇的投影面积计算方式如下：
[0029]
假设点云簇中最大x、y坐标值为x
imax
、y
imax
，最小x、y坐标值为x
imin
、y
imin
，最大x坐标值与最小x坐标值的差值为δx
i
＝|x
imax
‑
x
imin
|，最大y坐标值与最小y坐标值的差值为δy
i
＝|y
imax
‑
y
imin
|，则点云簇的投影面积为area
i
＝δx
i
×
δy
i
。
[0030]
步骤3包括以下步骤：
[0031]
步骤3.1、利用dbscan聚类算法对全部高位置点进行分割，得到多个点云簇；
[0032]
步骤3.2、对于每个点云簇中的任意一点p
i
，找到点p
i
的k个近邻点点p
i
的三阶协方差矩阵m为：
[0033][0034]
上式中，为点p
i
的k个邻近点的平均位置；
[0035][0036]
通过奇异值分解对点p
i
的三阶协方差矩阵m进行特征值分解，得到协方差矩阵m的特征值λ1、λ2和λ3，且λ1≥λ2≥λ3≥0；基于特征值计算得到点p
i
的维度特征：
[0037][0038]
a
1d
,a
2d
,a
3d
分别表示线状特征、面状特征、散乱状特征，根据得到每个点p
i
的空间分布模式；
[0039]
步骤3.3、计算每个点云簇投影数据的最小外接矩形的投影面积；
[0040]
步骤3.4、若点云簇的最小外接矩形的投影面积、空间分布模式同时满足下述条件，则判定该点云簇为候选树冠点云：
[0041]
条件一、投影数据的最小外接矩形面积大于0.5；
[0042]
条件二、空间分布模式为散乱状点个数大于线状、面状点个数。
[0043]
步骤4包括以下步骤：
[0044]
步骤4.1、若候选树干点云簇在xoy平面投影的最大x坐标值x
imax
、最大y坐标值y
imax
、最小x坐标值x
imin
、最小y坐标值y
imin
均在候选树冠点投影的最小外接矩形的坐标范围内，则认为候选树冠的最小外接矩形能够覆盖候选树干；根据候选树冠最小外接矩形覆盖的候选树干数量，通过下述方式进行候选树木的提取：
[0045]
若候选树冠点云簇的最小外接矩形能够覆盖一个候选树干点云簇，则认为该候选树冠和候选树干组成一棵树木；
[0046]
若候选树冠的最小外接矩形并未覆盖候选树干，则将该候选树冠视为不完整的树，并删除该候选树干；
[0047]
若候选树冠的最小外接矩形覆盖多个候选树干，判断存在多棵树的树冠互相重叠或者树木和杆状物互相交缠的情况，进行下一步。
[0048]
步骤5包括以下步骤：
[0049]
步骤5.1、假设候选树冠的最小外接矩形覆盖多个候选树干，利用下式计算候选树冠覆盖的候选树干点云簇t
i
的中心点c
i
坐标
[0050][0051]
上式中，n为每个树杆点云点的个数，(x
j
,y
j
,z
j
)为候选树干点云簇t
i
中任意一点的坐标值；
[0052]
假设候选树冠覆盖的候选树干1的中心点为候选树干2的中心点为
两个中心点之间的向量为x轴的方向向量为为和两个向量之间的夹角为：将候选树冠和覆盖的候选树干点朝x轴方向旋转θ度，对于任意一点p，其新坐标为：
[0053]
转换后的x值：p.x
new
＝p.x*cos(θ) p.y*sin(θ)
[0054]
转换后的y值：p.y
new
＝p.y*cos(θ)
‑
p.y*sin(θ)
[0055]
转换后的z值：p.z
new
＝p.z
[0056]
坐标转换后，向量与x轴平行；
[0057]
步骤5.2、将候选树干点与候选树冠点的新坐标投影到xoz平面，计算候选树冠点在x方向的最大值x
tmax
和最小值x
tmin
，候选树杆中心点与候选树冠最大值x
tmax
、最小值x
tmin
的距离分别为：
[0058]
若d1＜0.5或d2＜0.5，即树杆中心点靠近候选树冠的边缘，则认为该候选树干点云簇为与树木交缠的杆状物，删除d1＜0.5的点，移除与树木交缠的杆状物；若d1＞0.5或d2＞0.5，则认为多棵树的树冠互相交叠，进行下一步：
[0059]
步骤5.3、沿z轴方向对重叠候选树冠进行横向切分，将候选树冠点云分为5～10层，得到树木的各层点云数据；利用基于欧几里得聚类算法，将每层点云数据根据点间的距离信息分成不同的点云簇，根据就近原则，将每个点云簇分配给距离其质心最近的树杆；
[0060]
若经过横向切分后的点云数据仅包括一个点云簇，则认为该点云簇是相邻候选树冠的重叠部分；候选树干1与候选树干2中心点之间的距离为：候选树冠最小值x
min
与候选树干1中心点之间的距离为候选树干2与候选树冠最大值之间的距离为比例因子α为：对于该层候选树冠中的任意一点p，如果它的x坐标的值满足：则该点属于候选树干1所在的候选树冠，否则，属于候选树干2所在的候选树冠；
[0061]
若各层点云数据中，候选树干1的最大x坐标值x
max
小于候选树干中心点x坐标，则将该层的候选树冠点归为候选树干1。
[0062]
本发明的有益效果是：
[0063]
本发明的一种基于结构分析的点云场景树木提取方法，先从三维点云数据中提取候选树冠和候选树干，再将候选树冠和候选树干进行匹配，移除未匹配的候选树干、与树木互相交缠的杆状物，并对相邻树木的重叠树冠进行分割，将交叠的树冠点云划分到各自所属的树木中，实现单棵树木的完整分割，解决了现有分割方法存在的相邻树木间重叠树冠的分割不准确的问题；无需进行人工选择训练数据，避免手动设定带来的分割误差，实现了单棵树木的精确提取。
附图说明
[0064]
图1a是本发明一种基于结构分析的点云场景树木提取方法的低位置点的点云场景数据图；
[0065]
图1b是本发明一种基于结构分析的点云场景树木提取方法的高位置点的点云场景数据图；
[0066]
图2是本发明一种基于结构分析的点云场景树木提取方法的局部坐标系建立示意图；
[0067]
图3是本发明一种基于结构分析的点云场景树木提取方法中移除与树木交缠的杆状物后的效果图；
[0068]
图4是本发明一种基于结构分析的点云场景树木提取方法的重叠树冠细分割示意图；
[0069]
图5是本发明一种基于结构分析的点云场景树木提取方法的点云树木提取效果图。
具体实施方式
[0070]
下面结合附图和具体实施方式对本发明进行详细说明。
[0071]
一种基于结构分析的点云场景树木提取方法，包括以下步骤：
[0072]
步骤1、沿x、y轴对三维点云数据进行栅格化，栅格大小设置为2m
×
2m，寻找每个栅格内z值的最小值z
localmin
，根据每个栅格内的z值最小值z
localmin
、每个点的z值，将点云划分为地面点、低位置点(如图1a所示)、高位置点(如图1b所示)；
[0073]
具体的，步骤1.1、沿x、y轴对三维点云数据进行栅格化，寻找每个栅格内z值的最小值z
localmin
；
[0074]
步骤1.2、根据下式将点云划分为地面点g
ground
、低位置点g
lowlayer
、高位置点g
highlayer
；
[0075][0076]
上式中，为栅格内的任意一点p
i
的z值；若满足则认为p
i
为地面点g
ground
；若满足则认为p
i
为包含地表低矮地物以及树干点的低位置点g
lowlayer
；若满足则认为p
i
为包含树冠点的高位置点g
highlayer
。
[0077]
步骤2、对全部低位置点进行分割，得到多个点云簇，并根据点云簇的几何特征提取候选树干；
[0078]
步骤2.1、利用dbscan聚类算法对全部低位置点进行分割，得到多个点云簇；
[0079]
dbscan算法的具体实施步骤为：
[0080]
步骤a、选择任意一个未被标记的低位置点p
i
，统计其邻域半径eps中的点的个数
minpts
i
，将p
i
邻域范围内的点记为n
eps
(p
i
)，若n
eps
(p
i
)中点的个数minpts
i
不小于最小密度阈值minpts，即minpts
i
≥minpts，建立簇c并将点p
i
邻域内的点加入c。若n
eps
(p
i
)中点的个数minpts
i
小于minpts，则p
i
被标记为噪声点；
[0081]
步骤b、对n
eps
(p
i
)中未被标记的点q，统计其邻域半径eps中的点的个数minpts
q
，如果minpts
p
≥minpts，则将其邻域中未归入任何一个簇的点加入簇c；
[0082]
步骤c、重复步骤b，继续检查簇n
eps
(p
i
)中未被标记的点，直到没有点加入簇c；
[0083]
步骤d、重复步骤a、b、c直到所有点都归入某个簇或标记为噪声，得到多个点云簇。
[0084]
dbscan算法依赖于两个参数：邻域半径eps和密度阈值minpts。其范围分别设置为0.1
‑
0.3和30
‑
50。经过dbscan聚类之后，可以初步将低位置点分割为多个点云簇。
[0085]
步骤2.2、将多个点云簇投影到xoy平面，根据下式计算每个点云簇的投影面积：
[0086]
假设点云簇中最大x、y坐标值为x
imax
、y
imax
，最小x、y坐标值为x
imin
、y
imin
，最大x坐标值与最小x坐标值的差值为δx
i
＝|x
imax
‑
x
imin
|，最大y坐标值与最小y坐标值的差值为δy
i
＝|y
imax
‑
y
imin
|，则点云簇的投影面积为area
i
＝δx
i
×
δy
i
；
[0087]
步骤2.3、计算每个点云簇中z值最大值z
imax
与z值最小值z
imin
的差值δz：δz＝|z
imax
‑
z
imin
|，即点云簇高度；
[0088]
步骤2.4、若点云簇的投影面积、点云簇高度同时满足下述条件，则判定该点云簇为候选树干点云：
[0089]
条件一、投影面积小于0.4，即area
i
＜0.4；
[0090]
条件二、点云簇高度大于1，即δz＞1；
[0091]
条件三、点云簇最低点z
min
与地面接近，即
[0092]
步骤3、对全部高位置点进行分割，得到多个点云簇，并根据点云簇的空间分布模式、最小外接矩形的投影面积提取候选树冠；
[0093]
步骤3.1、利用dbscan聚类算法对全部高位置点进行分割，得到多个点云簇；
[0094]
步骤3.2、对于每个点云簇中的任意一点p
i
，找到点p
i
的k个近邻点点p
i
的三阶协方差矩阵m为：
[0095][0096]
上式中，为点p
i
的k个邻近点的平均位置；
[0097][0098]
通过奇异值分解对点p
i
的三阶协方差矩阵m进行特征值分解，得到协方差矩阵m的特征值λ1、λ2和λ3，且λ1≥λ2≥λ3≥0；基于特征值计算得到点p
i
的维度特征：
[0099][0100]
a
1d
,a
2d
,a
3d
分别表示线状特征、面状特征、散乱状特征，根据得
到每个点p
i
的空间分布模式；
[0101]
步骤3.3、计算每个点云簇投影数据的最小外接矩形的投影面积；
[0102]
假设最小外接矩形的最大x坐标值为x
jmax
，最大y坐标值为y
jmax
，最小x坐标值为x
jmin
，最小y坐标值为y
jmin
，则投影面积为：area
j
＝δx
j
×
δy
j
；
[0103]
步骤3.4、若点云簇的最小外接矩形的投影面积、空间分布模式同时满足下述条件，则判定该点云簇为候选树冠点云：
[0104]
条件一、投影数据的最小外接矩形面积大于0.5，即area
j
＞0.5；
[0105]
条件二、该点云簇中空间分布模式为散乱状点的个数大于线状、面状点个数。
[0106]
步骤4、判断候选树冠点云簇的最小外接矩形是否仅覆盖一个候选树干点云簇，若是，则完成候选树木提取；否则删除候选树干或进行下一步；
[0107]
步骤4.1、若候选树干候选点云簇在xoy平面投影的最大x坐标值x
imax
、最大y坐标值y
imax
、最小x坐标值x
imin
、最小y坐标值y
imin
均在候选树冠点投影的最小外接矩形的坐标范围内，即满足下式：
[0108][0109]
则认为候选树冠的最小外接矩形能够覆盖候选树干；
[0110]
根据候选树冠的最小外接矩形下候选树干的数量，通过下述方式进行候选树木的提取：
[0111]
若候选树冠点云簇的最小外接矩形能够覆盖一个候选树干点云簇，则认为该候选树冠和候选树干组成一棵树木，即完成候选树木的提取；
[0112]
若候选树冠的最小外接矩形并未覆盖候选树干，则将树冠视为不完整的树，将未被覆盖的候选树干删除；
[0113]
若候选树冠的最小外接矩形覆盖多个候选树干，判断存在多棵树的树冠互相重叠或者树木和杆状物互相交缠的情况，进行下一步；
[0114]
步骤5、判断候选树冠点云簇匹配的多个提取候选树干为与树木交缠的杆状物或多棵树的树冠互相交叠，若为与树木交缠的杆状物，则移除与树木交缠的杆状物；若为多棵树的树冠互相交叠，对相邻树木的重叠冠层进行分割，将交叠的点云划分到各自所属的树木中，完成单棵树木点云的分割。
[0115]
步骤5.1、假设候选树冠的最小外接矩形覆盖多个候选树干，如图2所示，利用下式计算候选树冠覆盖的候选树干点云簇t
i
的中心点c
i
坐标
[0116][0117]
上式中，n为每个树杆点云点的个数，(x
j
,y
j
,z
j
)为候选树干点云簇t
i
中任意一点的坐标值；
[0118]
假设候选树冠覆盖的候选树干1的中心点为候选树干2的中心点为两个中心点之间的向量为x轴的方向向量为
和两个向量之间的夹角为：将候选树冠和覆盖的候选树干点朝x轴方向旋转θ度，对于任意一点p，其新坐标为：
[0119]
转换后的x值：p.x
new
＝p.x*cos(θ) p.y*sin(θ)
[0120]
转换后的y值：p.y
new
＝p.y*cos(θ)
‑
p.y*sin(θ)
[0121]
转换后的z值：p.z
new
＝p.z
[0122]
坐标转换后，向量与x轴平行；
[0123]
步骤5.2、将候选树干点与候选树冠点的新坐标投影到xoz平面，计算候选树冠点在x方向的最大值x
tmax
和最小值x
tmin
，候选树杆中心点与候选树冠最大值x
tmax
、最小值x
tmin
的距离分别为：
[0124]
若d1＜0.5或d2＜0.5，即树杆中心点靠近候选树冠的边缘，则认为该候选树干点云簇为与树木交缠的杆状物，如图3a所示，删除d1＜0.5的点，移除与树木交缠的杆状物，如图3b所示；
[0125]
若d1＞0.5或d2＞0.5，则认为多棵树的树冠互相交叠，进行下一步：
[0126]
步骤5.3、沿z轴方向对重叠候选树冠进行横向切分，将候选树冠点云分为5～10层，得到树木的各层点云数据；利用基于欧几里得聚类算法，将每层点云数据根据点间的距离信息分成不同的点云簇，根据就近原则，将每个点云簇分配给距离其质心最近的树杆；
[0127]
若经过横向切分后的点云数据仅包括一个点云簇，则认为该点云簇是相邻候选树冠的重叠部分，如图4所示；候选树干1与候选树干2中心点之间的距离为：候选树冠最小值x
min
与候选树干1中心点之间的距离为候选树干2与候选树冠最大值之间的距离为比例因子α为：对于该层候选树冠中的任意一点p，如果它的x坐标的值满足：则该点属于候选树干1所在的候选树冠，否则，属于候选树干2所在的候选树冠；
[0128]
若各层点云数据中，候选树干1的最大x坐标值x
max
小于候选树干中心点x坐标，则将该层的候选树冠点归为候选树干1。
[0129]
经过步骤1
‑
5后，可以从点云场景中完整提取出树木。图5为从点云场景中提取单棵树木的效果图。
[0130]
通过以上方式，本发明的一种基于结构分析的点云场景树木提取方法，先从三维点云数据中提取候选树冠和候选树干，再将候选树冠和候选树干进行匹配，移除未匹配的候选树干、与数目互相交缠的杆状物，并对相邻树木的重叠冠层进行分割，将交叠的点云划分到各自所属的树木中，实现单棵树木的完整分割，解决了现有分割方法存在的相邻树木间重叠冠层的分割不准确的问题；无需进行人工选择训练数据，避免手动设定带来的分割误差，实现了单棵树木的精确提取。