基于最小二乘密度聚类的城市点云去噪算法

杨 鹏,刘德儿,刘靖钰,邹纪伟,张荷苑,陈增辉

(1.江西理工大学建筑与测绘工程学院,江西 赣州 341000; 2.成都大学中国东盟艺术学院,四川 成都 610106)

1 引 言

3D点云表达,作为对象表面的表达方式之一,在对象识别和三维重构等领域越发重要。目前3D点云数据获取主要通过三维激光扫描的方式。受益于三维激光扫描技术的发展,3D点云密度越来越密,精度也越来越高。但是实际操作环境的复杂性,造成获取到的点云数据中不可避免的存在噪音点和错误点。而点云数据的质量对于最终三维重构成果的质量的影响十分巨大。因此,去除点云数据中的噪音点具有很高的实用和研究价值[1-15]。

目前,在点云去噪方面,已经成为近年来的一个研究热点。同时,国内外专家都做出了许多重要的研究成果,出现了一大批优秀的理论和算法,苏本跃等[16]基于K-means聚类对RGBD点云进行外部噪声去噪和精简,首先计算各点在局部曲面的曲率值,通过K-means对其进行聚类,在根据邻近点的曲率变化和该点到聚类中心的距离判断是否为噪声点,该算法可保留点云的原始特征；张巧英、田青华等[17-18]均运用了聚类算法,但是其算法中的邻域搜索普遍耗时较长,未凸显统计特性。冯东恒等[19]提出用共面法向量特征去除离群面的RANSAC算法,与传统PCL算法相比,该算法去噪效果好且执行效率高,但若地表复杂且包含较多树木,则影响较大；林万誉等[20]提出基于最小截取二乘法的分段拟合的滤波算法,在去除点云的同时能较好的保留局部细节特征,但仅局限于多曲面三维点云；赵凯等[21]提出的基于体素栅格的快速密度聚类算法,将点云进行体素栅格划分,缩小各个对象在空间上的搜索范围,再结合DBSCAN进行去噪,大幅度提高了运行效率。李明磊等[22]通过对平均点间距附加权重再作阈值判断,降低了对远距离离散点的误判,且通过八叉树格网结构提高了生长探测法的运行效率；李仁忠等[23]提出的基于方法库的点云模型去噪与精简算法,通过结合PCL中的直通滤波、统计滤波、半径滤波、双边滤波等,可有效对大尺度噪声点进行去除,但在该算法中统计滤波和半径滤波阈值设置决定运行效率。林洪彬等[6]提出基于参数自适应各向异性高斯核的散乱点云保特征去噪算法,利用切平面的投影和采样点构建相似度函数,从而确定有效领域,通过研究采用点的特征值和特征向量分布确定参数自适应的高斯核函数,从而完成点云去噪,该算法虽然较好地实现了点云去噪,但仍无法达到完全自适应。许龙等[7]提出了基于模糊C均值和均值滤波的点云去噪算法,首先用C均值去除大尺度噪声,再结合均值滤波对小尺度噪声进行光顺,该算法在去噪的同时较好地保留了边界特征。

上述去噪算法能够在一定程度上解决了目前的工程所需,但是现有的点云去噪算法的复杂度、自适应性、稳定性、快速性以及通用性等仍然有待提升,尤其是在一些极其苛刻、复杂的场景之下,错分率非常高。例如:林业园区、城市街区以及不规则、不平整地区等,对于这些地区的点云数据运用去噪算法,一定需要在某些阈值选取时加以限制。

2 原理与方法

本文基于三维激光扫描仪RIEGL VZ-1000收集的城市点云数据,该数据的角度分辨率为0.0005°,100米的扫描精度为5mm,图1为2019年4月的部分城市点云数据,共820025个点,横纵方向扫描角设置为0.02°,受扫描角度的限制、阴影遮挡与随机误差的影响,其中存在大量的噪声和空洞,且噪声点表现较为杂乱、规律不明显,因而对该场景下的噪声剔除需要更多的考虑内在随机噪声特性。通常城市点云的噪声主要来自于孤立噪声点、非地面的随机噪声点以及扫描稀疏边界等。因此,首先,建立近邻点特征空间；其次,确定噪声点与实体点的分界线；最后,基于特征空间的特征表达原则,再结合特征密度的分布进行聚类求交,最终可消除随机误差的影响。

图1 原始的点云

2.1 特征空间

城市点云本身所具有的复杂性,增加了噪声点去除的难度,而去噪精度严重影响后期的实物提取与建模。城市点云噪声空间的分布规律具有不稳定的变化,运用简单的密度聚类将无法达到满意精度。由于各单独点没有空间特征及实体属性,因此不能以点为对象进行密度聚类,而需要对空间描述算子的密度聚类。然而,描述一群空间散乱点所需要的特征算子可以有很多个,因此,用于聚类的特征空间将会被提升到更高维度的空间中。

图2 空间投影

如图2所示,不同的三维空间实体,在二维空间中的投影具有很大的差异性,有的是三维空间物体相同或相似的,在二维空间中完全不同,也有的是在二维空间投影相似的,其三维空间中的特性却完全不同。同理,更高维度空间向二维平面投影时,也会出现这种现象,因此不能单独在一个维度上对特征算子空间进行描述,这样会使得结果陷入局部最优解,使去噪精度变得不满足工程所需。

本文首要研究的着重点就是:在点云特征算子中,如何快速有效的解决高维空间密度聚类。经验表明:单一的一个特征值只能算是特征空间在某一特定方向的投影,其在一定程度上表现了原始数据的特性,但是这个过程并非一一映射,也会有其他方向的投影与该特征值相同或相似,这也就是点云特征空间聚类出现错分类的主要决定性原因。在复杂的点云空间中,每一个点都是独立的、附有特殊空间意义的存在,从本质上讲,每一个点都有属于它自己的特别属性,而我们要做的就是尽可能的将不同属性区分出来。

一个高维空间在低维空间上的投影可以有无数个,这些投影可以由一个集合表示,每一个投影都是这个集合中的一个元素,理论上投影元素越多精度越高。虽然用投影集合去分辨点云的属性在数学理论上是准确且可行的,但是在效率上确实无法估计。由于高维度的计算量很大,使得其效率低；低维度的计算量随少,使得其准确率低；因此,需要在效率和准确性之间进行平衡。

综上所述,本文提出一种最小二乘密度聚类去噪算法,旨在从高维特征空间中切分出具有实物属性的点云。首先,基于KD-Tree搜索各点的k个近邻点,再计算近邻点的统计特征；其次,由多个统计特征生成高维度的密度空间,并基于最小二乘解[24]求得密度空间在各维度上的回归线,并结合密度分析求得实物与噪声的分界线；最后,遍历密度空间,找出噪声点并剔除。

2.2 最小二乘密度聚类算法

为了从空间特性上描述点云,本文对近邻点的邻域特征空间进行聚类,由于特征空间维度高于3个维度,可以构建高维度信息的聚类,并以任意两个维度的最小二乘解限制聚类边界是否超限,因此,本文提出一种基于最小二乘法实现城市点云的最小二乘密度空间聚类方法,并以此为基础进行去噪。

本文算法实现的具体步骤如下:

第1步：确定近邻点数N,求得近邻特征空间,记为PN(x1、x2、x3、x4、x5);

第2步：将均值、方差、斜率、极值、能量进行排序,分别记为x1、x2、x3、x4、x5;

第5步：由密度空间的离散情况,截断阈值选择保留2倍中误差的有效数据作为所需的研究对象,其中2δ=95.44 %;

第6步：由第5步的标准计算出密度空间各投影方向的截断阈值ωij,截断条件为p(Tij≥ωij)=95.44 %,各投影方向的有效数据为Dij=Ti(Ti≤ωi),最终将各投影方向的有效数据取交集,即为在高维空间中的有效点集Qij=D12∩D13…∩D45。

3 实验结果与分析

对特征密度空间进行分析,需要充分考虑高维度密度空间的特性,以此分析各投影方向上密度的紧密性,即去噪能力的强弱,分析结果如下图3、图4所示。图1中的(a)、(b)、(c)、…、(j)依次为各投影面。

图3 邻域10个点的特征密度分布

图3的特征空间所示,去噪前后特征的集聚性对比明显,去噪之前,受到众多噪声的影响,使得密度集聚度散乱,且整体的最小二乘解受噪声点的影响较大。结合最小二乘解的密度空间聚类为去噪之后的结果,尽管有一定的散乱特性,但其缩小了约100倍的密度聚集体中包含了原有的大部分特征信息,即实现了数据的特征聚类,并消除了大部分随机误差影响,尤其是在包含能量的投影面上,其拟合度精度最高。然而,这些特征空间密度聚类后的交集包含的就是符合所有特征空间判定的有效点云,对于某些特有属性的点来说,该结果的判断具有一定的不确定性,可以通过调节层次权重的方式或者增加特征维度来进行判断。10个近邻点的密度特征空间能够反映出绝大部分噪声点,再结合密度阈值,即可获得到有效点云。

如图4所示,近邻点为40时,相较于图3的密度分布,图4的特征空间压缩了近80倍,其噪声点离散性增强,方差增强,从噪声的剔除上看,效果优于10个近邻点时的效果。虽然40个近邻点在特征空间中突出了噪声点,增加了离散度,但其特征空间范围也被快速增大了,这有可能将有效地面点也剔除了。

图4 邻域40个点的特征密度分布

图5 提取效果

本文算法实验结果如图5所示,选择A/B/C/D四处被认定为噪声点云的区域,如图可知,A区域为阴影遮挡的稀疏点云区域,由于阴影的影响,其实物属性无法体现,被作为噪声剔除也属正常；B区域为空中离群点,该算法能准确的找出并剔除；C区域为避雷针,由于其细而长的特性,在密度空间中很难被表现出来,这就属于错误区分的点云,但其点云个数极少,对总体精度影响不大；D区域透过玻璃随机产生的随机噪声点,相对于较为稀疏的主体墙体而言,也能将随机噪声与墙体分离开,但同时也有少许边缘点被错误区分,可通过调节截断阈值,提高精度。

同时为了能定性、定量分析本文算法,选用不同邻域点进行实验,得到结果如表1所示。带有均值及斜率的投影特征密度其密度空间的一阶偏导Cij均有所提升,带有能量、极差和方差的投影特征密度空间,其一阶偏导Cij随着近邻点个数的增加均有所下降。

如表2所示,在不同的邻域点时,其中(1)、(3)、(4)、(6)、(7)的特征空间,其提取效果较差,只能去掉1000～3000个随机噪声点；(2)、(5)、(8)、(9)的特征空间,随着邻域点的增加,其去噪能力也在增强；(11)为特征空间的最终去噪结果,其随着近邻点的增加,噪声点剔除个数也在增加,且总体趋势与实际理论相符。

表1 不同近邻点的投影特征最小二乘约束条件

表2 不同近邻点在各投影面上去噪后的点个数

采用第一类错分误差、第二类错分误差以及总错分误差验证算法的有效性,其中总错分误差是将有效点错误分为噪声点的数量和将噪声点错误分为有效点的数量之和占总和点云的比例,公式为:

式中,a为有效点数量；b为噪声点数量；c为将有效地面点错误分为噪声点的数量；d为将噪声点错误分为有效地面点的数量。

由表3可知,选择的近邻点数不同时,其噪声的剔除能力不同,均方差和分类误差均有所变动,同时,在选择近邻点个数为30时,虽然其均方差较大,但其分类误差最小,总的错分率t为0.000574,满足工程所需精度。

表3 不同邻域点个数下的提取结果及精度

4 结 论

本文提出了一种基于最小二乘密度聚类的城市点云去噪算法,计算近邻点统计特征空间,运用最小二乘约束特征空间在各维度方向的投影密度,以此进行密度聚类、剔除噪声点云。以VZ-1000地面三维激光扫描仪获取的城市点云数据,分析复杂环境下的城市点云空间结构与邻域特性,结果表明当近邻点个数为30时,该算法总分类误差最小。同时,实验也体现出本算法的优势:理论便于实现,且能快速、精确地去除噪声点云,具有一定的实用价值；但仍有不足之处,主要为稀疏点云的边缘、障碍物的阴影处以及低密度的线性地物等点云,这些是极容易造成错误分类的点,因此未来需要更深入地进行研究。