地面激光雷达（Terrestrial Laser Scanning，TLS）获取点云数据方便快捷，能够较好地反映林下垂直结构，基于这一特性有研究者将其应用于林分参数提取^[1]、树干点检测^[2−3]、单木分割和建模^[4−6]等研究。根据TLS林分点云分离出地面、树干和枝叶等类别可为数字高程模型构建、单木定位^[6]、胸径和树高反演^[1]等研究提供重要依据，所以将点云按类别快速分离在林业研究中具有重要意义。

点云分类任务主要包括特征构造和特征识别。构造特征是点云分类的基础，多年来，研究者们一直在致力于构造适当的点特征用以描述点与点之间的差异。根据构造策略的不同，构造点特征的方法大致分为两类，一类通过计算直方图的方法来描述点特征^[7−9]；另一类通过点与其近邻的相关关系构造几何特征。前者解译性较差，研究者不能从这些特征中直观地解读其所表征的三维特性，且特征维度较高，至少有33维^[8]，因而很少用于点云分类研究。通过近邻关系构造的特征几何含义明显，研究者可以从中解读其表征的几何含义^[12]，特征维度相对较低，应用较为广泛。如将近邻点投影到水平的二维平面中构造特征D_2D和R_λ,2D^[10−11]；通过近邻点协方差矩阵特征值的不同组合来挖掘其所表征的几何含义^[12−14]；通过计算近邻点的法向量和曲率构造特征^[15−16]。构造好特征之后需要寻找适当的方法进行特征识别，成熟的机器学习算法能够快速分离不同特征对应的类别，所以有较多的研究者选择用机器算法学习点特征以达到点云高精度分类的目的。Hackel等^[15]和Becker等^[17]的研究中分别构造了16和15个几何特征训练随机森林，分类准确率分别为0.90和0.84。上述方法均构造了较高维度的特征，而特征维度较高容易使得特征之间的相关关系复杂化，降低分类器对特征的敏感度，增加特征构造时间和内存消耗^[11]。

为了解决地面激光雷达点云分类特征维度较高的问题，本研究以TLS扫描的蒙古栎（Quercus mongolica）人工林数据为基础，通过对原始点云滤波处理后采用快速KDtree搜索近邻点，用近邻点分别计算协方差矩阵特征值、法向量、曲率、方差和最大高程差构造5个几何特征训练分类器。为了表明上述特征在TLS林分点云分类中具有较高的稳定性，本研究分别用Hackel等^[15]和Becker等^[17]使用的随机森林和本研究引入的xgboost这两个成熟的分类器进行训练，然后选用表现优异的分类器模型分离测试集点云。上述方法旨在构造一组稳健且维度较低的几何特征用于点云分类，以期达到快速分离林分点云的目的。

1.   研究方法

1.1   数据收集与样本选取

本研究数据用地面激光雷达（表1）扫描蒙古栎人工林获取，点间距最小为2 mm，扫描树型完整，扫描时间为2016年6月1日，共架设5个扫描站（图1a），站间平均间距20 m，其中S1扫描站设为360°全景扫描，其余4站（S2、S3、S4、S5）为定向扫描。该蒙古栎人工林（图1b）地势平坦、树种单一且垂直结构较好、林分单木间隔为3 m左右，枝叶间存在遮挡，灌木较少，林分平均密度为2 500株/hm²，平均树高和胸径分别为9.98 m和13.55 cm。

表  1  三维激光扫描仪技术参数

Table  1.  Technical parameters of TLS

参数 Parameter	数值 Value
点位精度 Position precision	6 mm
距离精度 Resolution of distance	4 mm
角度分辨率 Resolution of angle	12″
颜色及波长 Color and wavelength	Green/532 nm
扫描距离 Scanning range	300 m
扫描速率 Scanning velocity	50 000 点/s
	50 000 points/s
扫描光斑直径 Scanning spot diameter	4.5 mm (0 ~ 50 m)

下载: 导出CSV 

| 显示表格

图  1  扫描站和蒙古栎人工林

Figure  1.  Scanning stations and plantation of Mongolian oak

下载: 全尺寸图片 幻灯片

用以训练分类器的样本通常分为训练样本、验证样本和测试样本3类。训练样本用于训练分类器；验证样本和训练样本均采集自同一样本集，验证样本常用做比较不同分类器的性能。本研究将验证集准确率较高的分类器用于测试样本的分类。本研究的5个站点TLS林分点云数据几何特征相近，全景扫描相较于定向扫描数据量丰富，所以本研究的训练样本和验证样本分别是从标记好的全景扫描数据中随机采集1 000 000和10 000个点获得，测试样本为剩余4个站点中任选1站的点云数据。

1.2   数据坐标系定义

本研究的5站数据坐标系均由相对独立的笛卡尔坐标系定义（图2），坐标原点O为扫描仪中心所在的空间位置，X、Y轴互相垂直，其所确定的平面为水平平面，Z轴指向由右手法则确定。使用激光雷达进行数据采集时，若空间中存在一点P，其在上述坐标系中的空间距离为OP，那么P点的空间坐标即为OP向量在X、Y、Z轴3个方向上的分量。

图  2  数据坐标系

Figure  2.  Data coordinate system

下载: 全尺寸图片 幻灯片

1.3   点近邻特征构造

在林分点云分类任务中，同一类别的点云具有相似的特征，所以特征的构造对点云分类准确率有决定性作用。本研究构造的5个几何特征定义如下：

式中：λ₁ > λ₂ > λ₃ ≥ 0表示点和近邻点协方差矩阵的特征值，λ_{1, 2D} > λ_{2, 2D}≥ 0表示近邻点在X，Y坐标的特征值，R_{λ, 2D}指近邻点在水平投影中第二特征值与第一特征值的比值；V是垂直度；n_Z是邻近点法线向量Z轴方向分量；C_λ是点与近邻点构成曲面的曲率；${\sigma _{Z_{\rm{KNN}}}}$是近邻点在Z方向的方差；$\Delta {Z_{\rm{KNN}}}$是近邻点在Z方向的最大距离，KNN表示快速KDtree搜索的近邻值，Z_i和$\bar Z$分别表示近邻点的Z坐标值和Z坐标均值，Z_max和Z_min分别表示近邻点最大和最小Z坐标值。

图3a、b、c分别为全景扫描站中截取的3个类别林分激光雷达点云。由图3可知，本研究的地面点平面特性较好，树干点的垂直特性显著，枝叶点形状不规则且离散特性较差。为不失一般性，表2给出了用全景扫描点云计算3个类别几何特征的均值。特征R_λ,2D与近邻点在X、Y轴投影的离散程度相关，近邻点云分布集中则其值较小，反之则较大；地面点X、Y方向分布较为分散，故特征R_λ,2D较大，趋近1；树干点在水平投影面呈月牙形，故其值较小，趋近0；枝干离散特性不稳定，故其值趋近0.5。特征V与近邻点逼近曲面的法向量相关，地面的曲面法向量近似平行于Z轴，树干的曲面法向量近似垂直于Z轴，故地面与树干的特征V分别趋近0和1；枝叶的近邻点法向量分布不规律，故其特征V介于地面与树干之间。特征C_λ用于衡量近邻点逼近曲面的弯曲程度，在3个类别中，地面弯曲程度较小，故C_λ最小；枝叶近邻点比树干近邻点分布集中，故其曲率相对较大；树干曲率介于两者之间。特征${\sigma _{Z_{\rm{KNN}}}}$和ΔZ_KNN仅与近邻点的Z方向分布相关，分布越集中其值越小，反之越大；地面点Z方向差异最小分布集中，故其特征${\sigma _{Z_{\rm{KNN}}}}$和ΔZ_KNN最小；树干Z方向差异比地面大但比枝叶均匀，故枝叶特征${\sigma _{Z_{\rm{KNN}}}}$和ΔZ_KNN值最大，树干特征${\sigma _{Z_{\rm{KNN}}}}$与ΔZ_KNN值介于地面与枝叶之间。

图  3  全景扫描站中截取的3个类别点云

Figure  3.  3 categories of point clouds intercepted in the panoramic scanning station

下载: 全尺寸图片 幻灯片

表  2  全景扫描不同类别点云的特征均值

Table  2.  Mean features of different kinds of points from full scanning

类别 Category	Rλ,2D	V	Cλ	$\scriptstyle{{\sigma _{Z_{\rm{KNN}}}}}$	ΔZKNN
地面 Ground	0.732 4	0.012 9	0.012 7	0.000 1	0.047 3
树干 Stem	0.183 5	0.873 2	0.047 2	0.002 4	0.142 8
枝叶 Branch and leaf	0.471 5	0.281 5	0.085 2	0.005 9	0.212 8
注：Rλ,2D是近邻点在水平投影中第二特征值与第一特征值的比值，V是垂直度，Cλ是点与近邻点构成曲面的曲率，$\scriptstyle{{\sigma _{Z_{\rm{KNN}}}}}$是近邻点在Z方向的方差，ΔZKNN是近邻点在Z方向的最大距离。Notes: Rλ,2D is the ratio of the second eigenvalue to the first eigenvalue in the horizontal projection of the neighboring points, V is the verticality, Cλ is the curvature of the surface formed by the neighboring points, $\scriptstyle{{\sigma _{Z_{\rm{KNN}}}}}$ is the variance of the neighboring points in the Z direction, ΔZKNN is the maximum distance of the neighboring points in the Z direction.

下载: 导出CSV 

| 显示表格

1.4   近邻搜索方法

点近邻计算要考虑两个重要因素：（1）依据近邻点计算的点特征质量；（2）搜索近邻的算法效率。

在本研究中点云密度与扫描距离呈负相关变化，即距离扫描仪较近的点云密度较大，距离扫描仪较远点云密度较小。一般而言，近邻点云可以基于定半径和定近邻个数进行搜索，前者受点云密度影响较大，点云密度小定半径搜索的点数量较少计算的特征不具代表性；点云密度大定半径搜索点数量急剧增加则降低算法运算效率。通常学者考虑基于K近邻搜索点云^[11,14−16]，这样不仅保证搜索点云个数，而且受点云密度影响较小。当遍历点云数据搜索近邻点时，若近邻点数量相近则其对应的几何特征差异较小；近邻点数量较大则容易搜索到较多其他类别点云促使计算的几何特征失真，所以本研究的K值拟在20 ~ 200范围内,以30为步长分别取值，并进行最优K值探究。

随着计算机科学的进步，相近样本的搜索效率也取得长足的发展。早期研究者通过计算单样本与所有样本之间的最近距离搜索近邻样本，即KNN搜索^[18]。KNN算法的效率与样本的数量呈线性关系，随着样本数量和特征维度的增加其对计算机内存的要求逐渐增高，该算法容易陷入维度灾难。而后研究者又提出了维度递归二叉树的方法搜索最近样本，即KDtree。KDtree算法依据二分类思想按维度迭代分割样本所在空间，直到每个最后一棵树仅由一个元素构成，然后采用回溯方法查找临近点，当近邻点数量达到阈值或近邻点最大距离达到阈值则查找结束。本研究数据量较大，故采用改进的快速KDtree^[19]搜索点云K近邻，其算法效率相较于传统KDtree取得了巨大进步。当然也有基于Octree搜索近邻的方法^[20]。

1.5   分类器

分类器的分类精度往往取决于构造的特征，即特征对类别的表征能力决定了分类器的上限。如果两个成熟分类器均能够有效分离地面、树干和枝叶则表明本研究构造的几何特征具有较高的稳定性。本研究分别取Hackel等^[15]和Becker等^[17]研究中选用的随机森林^[21]与近年来在分类比赛中表现优异的xgboost^[22]这两个分类器进行比较研究。

1.5.1   随机森林

Breiman^[21]在文章中对随机森林做如下定义：随机森林是一种包含多个决策树的分类器，每棵树针对输入X给出其所属类别的判断。$\left\{ {h\left( {X,{{\varTheta} _m}} \right)} \right.,$$m = 1,2, \cdots ,$$M\}$，$h\left( {X,{{\varTheta} _m}} \right)$是分类器对输入X所属类别做出判断；Θ是一组随机向量，其取决于树的结构；M是决策树的数量。随机森林有3个特性：（1）对输入的N个样本采用bagging方式进行重新采集。（2）节点特征采样，这个策略可以防止过拟合，提高分类器的泛化能力。（3）每棵树都使用贪心算法尽量增长到最大深度。

随机森林的边缘函数（Mg）定义如下：

式中：I（）是判断函数，h_m（X）为决策树对样本的判断，m为决策树索引，X表示输入，Y表示类别标签，av_m表示所有决策树正确判断的均值，$\mathop {\max }\limits_{j \ne Y} a{v_m}$表示最多错判的均值。

该公式的含义是所有决策树正确判断的均值与最多错判均值的差，差值越大表明分类器的置信度越高。

1.5.2   xgboost

xgboost是梯度提升决策树^[23]（Gradient Boosted Decision Trees，GBDT）的改进，也是基于决策树的训练，xgboost相较于GBDT在训练方法上做了较大的改进。其优点如下：（1）引入正则化项，该策略能够防止分类器过拟合；（2）采用剪枝技术，保证算法精度；（3）目标函数采用泰勒展开式的二项逼近；（4）支持并行计算，提高运算效率。

xgboost优化的目标函数（OBJ）定义如下:

式中：g_i、h_i为目标函数的梯度，γ、λ是目标函数的优化参数，T是决策树的叶子节点数，I_j是训练样本所在的叶子索引，$w_j^*$是第j个叶子节点的权重。

1.6   精度评价

训练好分类器之后，需要对其表现做出定性的评价，在机器学习中衡量分类器性能的定义如下：

式中：A、P、R、F_1score、$M_{F_{1{\rm{score}}}}$分别表示分类器的准确率、查准率、召回率、F₁分数和F₁分数均值。C_N表示正确估计的样本数，T_N表示样本总量，${C_{N_i}}$表示类别i中正确估计的样本数量，${P_{N_i}}$表示估计为类别i的总量，${T_{N_i}}$表示实际为类别i的总量，n表示样本类别个数。

A用于分类器表现直观估计，P和R用于评价分类器在某类上的表现。由于难以用两个量衡量分类器在某一类别上的表现，研究者引入F_1score。通常还采用$M_{F_{1{\rm{score}}}}$衡量分类器的总体表现，其值越大表示分类器分类效果越好。

2.   结果与分析

2.1   快速KDtree的K值的选择

用分类器处理点云分类任务时，研究者常常考虑在不影响分类器精度前提下，兼顾特征计算速度和分类器训练速度。图4a、b分别展示了随着K值的变化随机森林算法在数据集上的表现。由图4a可知，快速KDtree近邻搜索的时间与K值近似线性关系；在用特征训练分类器时发现随着K值的增大，训练时间逐渐减小，当K大于140时训练用时趋于稳定。

图  4  快速KDtree搜索用时和随机森林的训练统计量

Figure  4.  Statistics of random forest training and fast KDtree search

下载: 全尺寸图片 幻灯片

在图4b中分别绘制了随着K值增大分类器在训练样本、验证样本和测试样本上的表现。随着K值的增大，分类器训练准确率逐渐增长，在达到0.96时趋于稳定。测试准确率随着K值的增长也不断提高，当K大于80时，准确率趋于平稳，且在K为140时，准确率达到最大值。随机森林的训练精度总是比测试精度大了近0.03，且在K为140时差值最小，说明随机森林存在轻微的过拟合现象。综上所述，本研究采用K为140的快速KDtree搜索近邻点云。

2.2   分类器比较

在用机器学习处理点云分类时，一组好的特征能够适应多种分类器，即分类器的分类精度很大程度上取决于构造的特征。本研究中随机森林和xgboost均由50个决策树组成，决策树分裂最大深度为6层。由表3可知，xgboost和随机森林在林分点云分类中均有较好的表现，测试集的准确率分别达到0.936 3和0.932 1。仔细分析不难发现，xgboost在每个类别的查准率、召回率、F_1score和$M_{F_{1{\rm{score}}}}$均比随机森林有千分级的优势。由2.1节分析可知，随机森林存在轻微的过拟合现象，xgboost在目标函数中引入了正则化项，其在训练中能够较好地控制分类器过拟合，所以xgboost有较好的泛化能力。综合准确率和$M_{F_{1{\rm{score}}}}$可知，xgboost的表现略优于随机森林，但两个分类器在本研究构造的特征中均能够较好地完成分类任务。

表  3  多分类器分类统计量

Table  3.  Labeling statistics of different classifiers

分类器 Classifier	准确率 Precision	类别 Category	正确估计 Right estimation	估计数量 Number of estimation	真实数量 Real number	查准率 Precision ratio	召回率 Recall ratio	F1分数 F1 score	F1分数均值 Mean F1 score
xgboost	0.936 3	地面 Ground	362 553	371 882	374 843	0.974 9	0.967 2	0.971 0	0.942 5
		树干 Stem	704 596	746 743	774 039	0.943 6	0.910 3	0.926 6
		枝叶 Branch and leaf	828 648	906 250	875 963	0.914 4	0.946 0	0.929 9
随机森林 Random forest	0.932 1	地面 Ground	362 718	373 029	374 843	0.972 4	0.967 7	0.970 0	0.938 9
		树干 Stem	699 419	744 994	774 039	0.938 8	0.903 6	0.920 9
		枝叶 Branch and leaf	825 283	906 852	875 963	0.910 1	0.942 1	0.925 8

下载: 导出CSV 

| 显示表格

2.3   点云分类结果

由2.2节分析可知相较于随机森林，xgboost分类性能较好，所以本节结合xgboost的分类结果进行讨论。图5a和图5b分别为用于分类的训练样本和基于xgboost分类结果标记的测试样本，其中颜色绿、红、灰分别代表枝叶、树干、地面。表4为测试样本点云分类的混淆矩阵和错估统计，在混淆矩阵中每行表示分类器在该类别的预测分布，每列的和表示类别总量。表5的列表示每个类别的分类占比。

图  5  训练样本和xgboost的分类结果

Figure  5.  Training sets and classification results of xgboost

下载: 全尺寸图片 幻灯片

表  4  测试样本的混淆矩阵和错估统计

Table  4.  Confusion matrix and the statistics of wrong estimation in test sets

类别 Category	地面 Ground	树干 Stem	枝叶 Leaf	错估量 Wrong estimation	错估占比 Ratio of wrong estimation/%
地面 Ground	362 553	1 990	7 339	9 329	0.46
树干 Stem	2 171	704 596	39 976	42 147	2.08
枝叶 Branch and leaf	10 149	67 453	828 648	77 602	3.83
总和 Total	374 873	774 039	875 963	129 078	6.37

下载: 导出CSV 

| 显示表格

表  5  测试样本的类别间的估计准确率统计

Table  5.  Statistics in estimation accuracy of different classes in test sets

类别 Category	地面 Ground	树干 Stem	枝叶 Branch and leaf
地面 Ground	96.71	0.26	0.84
树干 Stem	0.58	91.03	4.56
枝叶 Branch and leaf	2.71	8.71	94.60

下载: 导出CSV 

| 显示表格

通过对图5b所示结果进行分析发现，分类器正确标记了测试集中大多类别点云，而且能够有效分离冠层中的树干点，但在地面处分类器容易将部分地面点云错分为枝叶，而在枝叶处分类器容易将部分点云错分为树干。

结合表4和表5可知，分类器正确标记地面、树干和枝叶的准确率分别为96.71%、91.03%和94.60%，错估数据量分别占测试样本总量的0.46%、2.08%和3.83%。2.2节中指出xgboost的准确率为93.63%，由此分析可知其中近6%的错估率来自树干和枝叶的影响。由于树干和枝叶的关系紧密，在树干产生枝干处点近邻构造的空间特征相似度较高，所以分类器容易产生错误估计；分类器能够较好地分离地面，但由于地面起伏和部分落叶的影响分类器在地面与枝叶间也容易产生部分错误估计。由表5可知，类别树干中8.71%的点被错估为枝叶，类别枝叶中4.56%的点被错估为树干，类别地面中2.71%的点被错估为枝叶。

3.   结论与讨论

为了解决地面激光雷达点云分类特征维度较高的问题，本研究依据近邻点的相关关系构造了5个几何特征，借助随机森林和xgboost分类器实现了TLS点云高精度分类，所得结论如下：

（1）适当的K近邻构造特征有利于提高分类器性能。本研究样地林间间距适中，点云密度与距扫描仪距离呈负相关变化，在使用本研究点云构造K近邻的几何特征训练分类器时发现：随着K值的增大分类器训练准确率不断提高且训练时间逐渐减小，并都慢慢趋于平稳。

（2）本研究构造的几何特征在林分点云分类任务中有较高的稳定性。使用本研究TLS数据构造特征训练的随机森林和xgboost均能正确标记大多数点云。

（3）在空间上相近的类别间分类器容易产生错误估计。错分的点云大多在地面与树干或树干与枝叶空间上相交处，这两处点搜索的K近邻多包含两种类别点云。

本研究构造了5个几何特征，xgboost的训练和测试准确率分别为0.96和0.93，类别错估占比介于0.46% ~ 3.83%之间。Hackel等^[15]和Becker等^[17]在其研究中分别构造了16和15个几何特征用于随机森林训练。在Hackel等的研究中分类器的测试准确率为0.90，本研究的值比其提高了0.03；本研究的训练准确率与Becker等的研究结果相近（0.95），其测试准确率为0.84，比本研究少0.09，类别间的错估占比介于1.1% ~ 18.9%之间，说明本研究在保证点云分类准确率的基础上，达到了降低特征维度的目的。

在保证分类器估计准确率的前提下，本研究在处理点云分类任务时极大地降低了用于训练的特征维度，但对在空间上相近的点云识别能力较低。因此，在接下来的研究中，我们将继续探索构造特征的方法，以期能够更好地完成林分点云分类任务。