1 引言

随着激光雷达(LiDAR)技术在遥感测绘领域的广泛应用^[1],LiDAR三维点云数据地物分类成为测绘遥感领域热门的研究方向,但点云分类处理还存在许多问题需要解决。点云数据是三维空间内无序排列的点集,点之间没有必然的联系,缺乏分类必要的语义信息。而且城市环境复杂,建筑物、植被、人造物体等交错分布,激光雷达扫描时存在建筑物遮挡、建筑物与周围物体间距过小等问题,易造成点云信息的缺失。综合上述问题,设计分类算法,对大规模城区点云数据进行有效分类是目前研究的热点和难点^[2]。

传统的点云滤波分类方法有形态学滤波、不规则三角网(TIN)滤波等方法^[3],这些滤波方法利用地形、高程等信息进行点云分类。Kilian等^[4]运用窗口滤波作形态学开运算,得到城区的数字高程模型;Axelsson^[5]提出基于不规则三角网的加密滤波算法,能够对城市和林区点云进行有效分类;黄作维等^[6]在经典滤波算法的基础上提出一种基于多尺度虚拟格网的改进算法,可获取精细地面点。这些滤波分类方法虽然能取得较好的分类效果,但是需要根据应用场景人工设置大量参数和条件。算法对不同场景的自适应程度不高,参数或条件选择不当会造成分类错误。随着机器学习的发展,近年来研究者开始将机器学习方法应用于点云数据分类。陈向宇等^[7]结合多种树木特征,利用支持向量机(SVM)实现对不同树种的分类;Anguelov等^[8]采用马尔可夫随机场模型对点云数据进行多元分类;肖杨等^[9]利用分层聚类方法完成树木点云的提取;Lodha等^[10]采用扩展支持向量机分类点云数据。

机器学习方法有效降低了点云分类算法的复杂度,提高了分类算法的自学习性,但是有效选取目标特征和提高LiDAR点云分类精度等问题仍需进一步研究。针对以上问题,本文基于改进后的渐进加密三角网(IPTD)和最邻近支持向量机(NN-SVM),提出一种城区点云数据分类算法。该算法用IPTD滤波选出地面点,依据地面点进行点云归一化并剔除地面点,提取地物点特征进行有效性评估,筛选出合适特征用于地物点分类。构建SVM分类器对地物点进行粗分类和细分类,得到分类结果,并与其他分类算法进行对比分析。

2 渐进加密三角网滤波及点云归一化

城区地理环境复杂,地形变化会使地面点之间的高程值存在差异,造成点云误分类,因此优先提取点云的地面点,根据地面点对点云数据进行归一化处理,消除地形起伏对点云数据高程值的影响。图1为德国Vaihingen城区原始点云数据样本。原始点云数据滤波提取地面点的主要依据是:1)地面点的高程值相比于周围地物点低;2)自然地形坡度变化范围不大,小于某一阈值,而建筑物等人工建筑的坡度会大于这一阈值^[11]。以点云的高程和坡度为依据,利用改进的IPTD滤波算法提取地面点^[12]。IPTD算法简单,准确度高。

图 1. 原始点云数据样本

Fig. 1. Original point cloud data sample

下载图片 查看所有图片

2.1 IPTD滤波算法

传统加密三角网滤波算法存在将低矮物体误分类为地面的问题,影响地面点滤波精度。采用IPTD滤波算法可以解决这一问题。在传统算法基础上用小尺寸格网划分点云数据,加强了对点云中细节的处理;传统算法中每次迭代需重新计算数据派生阈值,本研究只在TIN加密到很小时重新派生阈值,提高了整体地形获取的效率。算法流程图如图2所示。

图 2. IPTD滤波算法流程图

Fig. 2. Flow chart of IPTD filtering algorithm

下载图片 查看所有图片

IPTD滤波算法具体步骤如下:1) 选取格网尺寸。在城区点云数据中,量取最大建筑物的尺寸L作为格网大小,对点云数据进行格网化。2) 选择初始种子点。点云数据格网化之后,取每个格网内的最低点作为起始种子点V_j(j=1,2,3,…),找出所有网格的种子点作为初始地面点。3) 构建三角网。利用起始种子点生成稀疏TIN,构建初始的TIN。4) 迭代加密过程。遍历所有待分类的地物点P_n(n=1,2,3,…),计算各点到其投影所在三角形的距离d及点到三角形3个顶点与三角形平面所成角度值,如图3所示。将计算值分别与迭代距离D与迭代角度α进行比较,如果小于对应阈值,则将此点判定为地面点,并加入三角网中。重复此过程,直至所有地面点分类完毕。

图 3. 点到三角网示意图

Fig. 3. Diagram of points to TIN

下载图片 查看所有图片

迭代角度α为待分类点与已知地面点间允许的角度范围,迭代距离D为待分类点与三角网对应的三角形之间的距离阈值。对于起伏较大的地形可以适当调大两个阈值。IPTD滤波根据地形的高程和坡度信息提取地面点,由初始地面点向周围生长,根据设定的迭代距离D剔除高程值高于D的点,由设定的迭代角度α剔除坡度高于α的点,通过不断迭代从地物点选取符合条件的点作为新的地面点。设置停止生长阈值为l,当待分类点对应的三角形边长小于l时,则停止加密三角网,该值可防止局部生成地面点过密。

2.2 依据地面点归一化

为了消除城区地形起伏引起的误分类问题,依据滤波得到的地面点对点云数据进行归一化处理^[13],去除地形起伏对地物点高程值产生的影响,归一化点云数据单纯表示地表物体高程特征。归一化的具体方法为:1) 遍历点云数据,找出地物点。2) 将每个地物点的高程值Z减去其最近地面点高程值。3) 将地面点的高程值统一设置为0。归一化点云计算公式为

ZNorm=Z-Z0,(1)

式中:Z为地物点的高程值;Z₀为距离地物点最近的地面点的高程值;Z_Norm为归一化后的地物点高程值。

3 地物点分类

3.1 NN-SVM介绍及算法流程

支持向量机是一种有监督学习的二元分类方法,分类关键在于将非线性的学习样本映射到高维空间,通过统计学习训练一个最优超平面B来对样本数据进行二分类,其模型已经能够有效解决分类、回归、聚类等问题。理想情况下,最优超平面B要使两类样本点集合到超平面的最小距离h相等,而且两类样本点间距最大,即点间距是h的2倍^[14]。样本数据集为 {(x₁,y₁), (x₂,y₂),…,(x_m,y_m)},其中m为样本中点的总数。由于噪点的存在,样本混叠严重无法严格线性可分,按理想情况训练分类器会造成过拟合。本文使用NN-SVM^[15]作为分类器,通过以下两方面解决样本混叠问题:1) 通过去除最邻近奇异点对训练样本进行精简,放弃对边界处少数奇异点的精确分类,得到新的训练样本;2) 对所有样本点,包括到超平面距离小于最小距离h的数据点,引入一个松弛变量ζ_i并设置新的约束条件,约束条件在放弃对离群噪点精确分类的同时,获得了更大的Margin,使用最小化目标函数寻找最优超平面^[16]。约束条件和目标函数为

yiwxi+b)≥1-ζi,ζi≥0minw,bw‖22+C∑i=1nζi,(2)

式中:w为超平面法向量;i为当前样本点序号;b为超平面位移项;C为控制边缘分类错误的惩罚因子,C越大则误分类的样本点数越少。

选用NN-SVM作为分类器,采用粗细双层的分类策略进行地物点分类的算法流程如图4所示。图中左边框内为粗分类过程,提取地物点云特征并对特征进行有效性评估,选取有效性高的特征组成特征向量训练分类器,采用“一对一”策略进行地物点云粗分类;右边框内为细分类过程,对粗分类的边界处点云数据提取不同尺度样本进行主成分分析,得到多尺度维度特征训练分类器,对边界点云数据进行细分类。

图 4. 地物点分类算法流程

Fig. 4. Flow chart of ground point classification algorithm

下载图片 查看所有图片

3.2 点云粗分类

3.2.1 点云特征选择

机器学习分类器的分类效果依赖于训练特征的优劣,好的特征组合能够提高分类精度,而无效特征则会造成分类精度下降。因此通过对各种特征进行有效性评估,从中选取一个特征子集训练分类模型,以达到较好的分类效果。实验中选取6种常用点云特征,用F-score方法进行有效性评估,选取有效性高的特征组成特征向量训练分类模型。待选取的点云特征如下:1) 归一化高程值h。点云依据地面点归一化得到归一化数字地表模型,依据nDSM的高程值h可有效区分高差距明显的物体,例如低矮的人造物体和高大的建筑物。2) 高程方差(HV)。某一激光点的高程方差指以该点为中心,R₁为半径的球形邻域范围内所有点的高程值方差,高程方差体现了物体表面的平整度。3) 点云法向量偏角β。某点的法向量偏角指该点邻域内点拟合平面的法向量与垂直方向夹角。建筑物表面法向量偏角基本不变,而植被表面的法向量偏角变化较大。4) 回波率f。某点的回波率是以该点为中心,半径为R₂的球形范围内点云数量和以相同中心为轴心,半径为R₂的垂直于水平面的圆柱体内点云数量的比值^[17],实验中R₂设置为平均点距的2倍,防止过大导致相邻不同地物的误分类。回波率f计算公式为

f=nballncolumn,(3)

式中:n_ball为球体内点云的个数;n_column为柱体内点云的个数。5) 回波强度方差(PV)。某一点多次回波的回波强度值的方差为该点的回波强度方差。激光雷达能接收到树木产生的多次回波,回波强度方差大;建筑物表面平整,只反射一次回波,回波方差小。6) 点云平面残差R。平面残差指某点邻域内点到拟合平面的垂直距离差。植被的平面残差值较大,而建筑物和人造物体的残差值较小。

特征向量选择完成后,由于不同点云特征的数值大小和测量范围差别较大,因此要对选取的特征进行去差异处理,消除不同特征之间的相对差别,避免小数值特征的作用被忽略,使各类特征在SVM分类中的作用最大化。特征去差异的表达式为

x'=x-xminxmax-xmin,x'∈[0,1],(4)

式中:x为某点处的原始特征值;x'为该点处去差异后的特征值;x_max和x_min分别为待分类点云数据中该特征的最大值和最小值。

3.2.2 基于“一对一”策略的SVM多元分类

使用“一对一”分类方法^[18],对样本数据中各种类别两两构建一个二分类器,用这一组二分类器处理待分类点云数据,所有分类结果进行逐点投票,票数最多的结果作为最终分类结果。“一对一”方法一共需要构建N(N-1)/2个分类器,其中N为种类数。地物点云数据分类为建筑物、人造物体和植被3类,需要构建3个二分类器。

考虑到径向基核函数(RBF)在某些参数设定条件下与Sigmoid核、线性核等核函数性能相近,适用于多种分类问题,而且RBF 核与其他核相比具有参数少、复杂度低的优点。因此,选择RBF 核作为SVM分类器内核进行分类模型的训练。RBF 核函数表达式为

K(x,y)=ϕxTϕ(y)=exp(-γ‖x-y‖2),γ>0,(5)

式中:x和y为低维特征向量;ϕ(x)和ϕ(y)为映射后的高维向量;γ为RBF核参数^[19]。选取适当的γ和惩罚因子C,用已知类别的训练样本训练SVM分类模型,对分类数据进行粗分类,将点云数据分为建筑物、人造物体和植被3类。

3.3 点云细分类

由于建筑物与植被分布过密、相互遮挡等因素,建筑物和植被相邻处的点云数据会产生误分类情况,比如,表面相对平整的植被点通常会被误分类为建筑物点。提取点云特征时,相邻物体间过渡区域的部分特征会产生偏差,比如房屋边缘处回波率会小于房顶处,而与植被回波率相似,这也会导致点云数据的误分类。

考虑到地物边界的误分类问题,采用多尺度特征融合的方法提升分类精度,通过多尺度的维度特征组合体现同类样本在不同尺度下维度特征的变化^[20],各类地物之间多尺度维度特征的明显差别能够增强地物的可分性,用多尺度维度特征训练分类器并对相邻建筑物与植被边界进行进一步的细分类,提高分类精度。

点云细分类流程如下:

1) 选取若干建筑物和植被的点云样本,删除样本中的异类点。

2) 选取样本中任意一点为圆心,尺度L为半径的球形邻域中的所有点的三维坐标作主成分分析,得到维度特征值并按降序排列,即λ₁≥λ₂≥λ₃。非零维度特征值个数表明点云样本的维度特征,例如一维分布的点云样本只有一个非零特征值^[21]。对特征值进行归一化,表达式为

vk=λkλ1+λ2+λ3,k=1,2,3,(6)

式中:v_k为归一化维度特征;k为维度特征的序号。提取点云样本不同尺度的归一化维度特征组成多尺度维度特征组合。

3)依据多尺度维度特征训练二分类器,找到最佳尺度组合,并对边界处局部点云数据进行细分类,将点云数据分为建筑物和植被。

4 实验与分析

4.1 实验数据和地面点滤波

本文使用国际摄影测量与遥感学会提供的Vaihingen城区数据集测试分类算法有效性,为了让实验具有普适性,数据集包含各种地物场景,点云的平均点距为0.66 m,分类算法将点云数据分为地面、建筑物、植被和人造物体4类。选取面积为19125 m²的点云数据(包含47656个离散点)作为测试集,测试集中点云类别已经过人工标记,作为测试点云分类精度的依据。

根据测试数据集具体地形分布设置IPTD滤波参数,进行多次实验并选择分类精度最高的参数组合。测试集地形相对平坦,非地面物体绝大部分垂直于地面分布,最大地形坡度设置为85°;人工测量测试集的建筑物尺寸,最大建筑物尺寸设置为66 m;迭代距离D设置为1.6 m,迭代角度α设置为30°。利用IPTD滤波算法对原始点云数据滤波进行分类,结果如图5所示。完成地面点滤波之后,对点云进行归一化处理,原始的点云数据和依据地面点归一化后的点云数据如图6所示,图中的点云高程值用颜色表示,从蓝色到红色点云的高程逐渐增加。从图中可以看出,原始点云因为地形起伏导致高程值变化,归一化后地面点高程值均为0。

图 5. 地面点分类结果。(a)平房区域;(b)楼房区域

Fig. 5. Classification results of ground points. (a) Bungalow area; (b) building area

下载图片 查看所有图片

图 6. 点云高程分布。(a)原始点云;(b)归一化点云

Fig. 6. Elevation distributions of point clouds. (a) Original point clouds; (b) normalized point clouds

下载图片 查看所有图片

4.2 特征选择

在进行分类器训练之前,从训练样本中提取点云特征,并对所选特征的有效性进行评估。实验中利用LIBSVM软件包中的F-score模块对选取的特征进行有效性评估^[22]。F-score模块通过评估给每个特征赋予相应的权值,权值越高表示该特征在点云分类中的作用越大。实验提取了3.2.1节中的6种点云特征并对有效性进行了评估,F-score评估结果如图7所示。其中,归一化高程权值最高,高程方差、回波强度方差和回波率的权值依次排在2到4位,以上4种特征权值远高于法向量偏角和残差,因此选取归一化高程值、高程方差、回波率和回波强度方差4种特征组成特征向量,进行去差异处理后用于NN-SVM分类器训练。

图 7. 不同特征的评估结果

Fig. 7. Assessment results of different features

下载图片 查看所有图片

4.3 地物点分类和精度评价

完成地面点滤波和特征选择后,对地物点进行分类。粗分类过程选取6个样本集训练NN-SVM分类器,样本集的平均离散点个数为7131,每个样本集都包含建筑物、人造地形和植被3类。本文使用LIBSVM工具训练分类器,利用LIBSVM自带的交叉验证模块选择最优核参数γ和惩罚因子C,得到最优超平面和较大的Margin,使训练的模型具有较高的预测精度^[23]。要训练3个分类器,每个分类器能够区分2类点云数据,用“一对一”方法处理测试集数据,通过投票机制确定每个点的类别。细分类过程首先选择最优尺度的维度特征组合。选择不同尺度组合计算维度特征,尺度范围不超过植被样本最大尺寸,在尺度范围内均匀划分尺度等级,训练分类器并对测试集局部点云数据进行分类,多次实验找到最优的尺度组合。通过对比,选定尺度范围为0.3~6.3 m的尺度组合,均匀划分12个尺度,尺度间隔为0.6 m。用训练好的分类器对边界点云数据进行细分类,得到精细分类结果。将边界点云数据粗分类和细分类结果进行对比,结果如图8所示。

图 8. 边界区域分类结果比较。(a)平房粗分类结果;(b)楼房粗分类结果;(c)平房细分类结果;(d)楼房细分类结果

Fig. 8. Comparison of boundary classification results. (a) Rough classification result of bungalow area; (b) rough classification result of building area;(c) fine classification result of bungalow area; (d) fine classification result of building area

下载图片 查看所有图片

为了检测点云数据的分类效果,采用单类精度和总体精度两个指标进行评估,测试整体和单类物体的分类精度,计算公式为

Acategory=NtNt+Nf1+Nf2Aoverall=NtureNall,(7)

式中:A_category为单类精度;A_overall为总体精度;N_t为某类样本中正确分类为该类别的点数;N_f1为该类别样本被错分类为其他类别的点数;N_f2为其他类别的样本被错分类为该类别的点数;N_ture为所有类别正确分类点数总和;N_all为点云总点数。

为了对特征选取的有效性和双层分类结果进行评估,实验利用选择后的4种特征和所有特征分别进行地物点粗分类,同时对未依据地面点归一化地物点云数据也提取了所有特征并进行粗分类,测量3种情况下的分类精度,如表1所示。对比可知,未归一化地物点分类效果远低于归一化后的地物点分类精度,说明地形起伏引起地物点云数据高程等信息的改变,会造成地物点的误分类,因此在进行地物点分类前通过归一化去除地形因素的影响,可以有效提高地物点的分类精度;利用选择后的特征分类的精度与利用所有特征分类的精度基本相同,甚至对于建筑物的分类精度由90.5%提升至91.6%,说明剔除权值低的特征对于点云的分类效果基本不会产生影响,而且通过特征选取完成了特征降维,有效消除了冗余特征。对粗分类和细分类的分类精度进行对比分析,如表2所示。由图8和表1、2可知,由于遮挡等原因导致的粗分类结果中的误分类问题,经过细分类后大部分误分类点被纠正,局部边界处的植被点和建筑物点的分类精度提高。

为验证算法的整体分类效果,将本文算法整体分类结果与和传统SVM分类器和NN-SVM分类器的分类结果进行比较,结果如图9所示。用单类精度和整体精度评价分类结果,如表3所示。从图9和表3可知,传统SVM和NN-SVM提取地面点时,容易将平整的建筑物房顶等区域误分类为地面点,而本文算法通过IPTD滤波对地面点分类效果更好,分类精度为92.7%,高于传统SVM的79.2%和NN-SVM的86.5%。在地物点分类方面,从表3中可知,NN-SVM的分类精度全面优于传统SVM,并且耗时更短。本文算法基于双层NN-SVM分类地物点,分类准确性与NN-SVM相比,植被点分类精度从87.4%提升至91.6%,建筑物点分类精度由88.2%提升至93.3%,本文算法总体分类精度为92.6%,高于其他两种算法,分类效果更优。在耗时方面,本文算法采用多层分类策略,总耗时比NN-SVM多,但是基于分类速度快的NN-SVM分类器,所以比传统SVM耗时更少。

图 9. 不同算法分类结果。(a)人工分类结果;(b)传统SVM分类结果;(c) NN-SVM分类结果;(d)本文算法分类结果

Fig. 9. Classification results of different algorithms. (a) Artificial classification results; (b) classification results of traditional SVM; (c) classification results of NN-SVM; (d) classification results of proposed algorithm

下载图片 查看所有图片

5 结论

提出了一种基于渐进三角网和NN-SVM的点云分类算法,应用于城区点云数据的分类,并对算法流程和相应技术理论进行了详细描述,通过实验验证算法的有效性。研究表明,IPTD滤波有效提高了地面点的分类精度,并且点云数据归一化处理消除了地形对于地物点分类的影响,提高了下一步的地物点分类精度。通过特征有效性评估筛选点云特征,在保证分类精度的前提下剔除无效特征,降低特征向量维度。通过双层分类提高地物点的分类精度,特别是通过植被和建筑物边界处的密集分布区域得到有效分类。本文算法仅利用点云特征,没有加入光谱、纹理等特征,而且仍然需要人工提取特征,在后续工作中可以深入研究特征的自动提取,考虑与深度学习等新技术结合,进一步提高特征提取和分类算法的自动化程度和分类精度。