保持细节特征的点云去噪算法

郑一帆 ，郑茜颖 ，程树英

（1.福州大学 物理与信息工程学院，福建 福州 350108；2.微纳器件与太阳能电池研究所，福建 福州 350108）

0 引 言

近年来，得益于激光雷达、RGB-D双目相机和TOF（Time of Flight）相机的不断发展，点云在自动驾驶[1]、虚拟现实[2]、3D打印[3]等领域广泛运用。但是受到仪器精度、人为操作扰动和复杂环境等因素影响，采集得到的点云数据往往会出现噪声点和离群点，并且存在数据冗余和不均匀等缺点。这些缺点会造成之后的重建过程耗费大量时间，重建模型出现轮廓不清晰和细节特征丢失，造成模型鲁棒性不足。因此，需要在三维重建前对点云数据进行去噪处理。

国内外研究人员一直对各种点云去噪技术加以改进和完善，传统的点云去噪方法主要有基于统计学的方法、基于投影的方法以及基于过滤器的方法。早期点云去噪方法以基于统计学方法为主，如SCHALL等[4]使用局部定义的核函数为含有噪声的点云定义全局的概率分布函数，然后求其函数最大值从而实现去噪。而后点云去噪方向逐步以基于投影和基于过滤器方法为主，如有基于双边过滤器[5-6]和基于邻域滤波器[7]的去噪算法。近年来，深度学习逐渐兴起，不少研究人员开发了基于深度学习的算法。YU等[8]制定一个基于边缘感知的框架，在上采样的同时恢复点云坐标，得到坐标与边缘的距离，利用边缘感知损失函数实现点云去噪。CHEN等[9]提出一种能够推理点云拓扑关系的自动编码器网络结构，利用无监督学习得到原始点云。PISTILLI等[10]的卷积神经网络通过点的高维特征表示之间的相似性动态构建邻域图来提升点云表面法线的质量，从而实现去噪。CATTAI等[11]利用局部谐波角滤波器的研究成果，提出了视觉驱动点云去噪算法（Visually Driven Point Cloud Denoising Algorithm，VIPDA），通过对点云进行谐波角度分析，使点云顶点相关联从而剔除噪声点。CHEN等[12]受到几何统计的启发，定义一个旋转不变的高度图补丁，将非局部相似的补丁的高度图打包成一个（Height-Map Patch，HMP）矩阵，然后利用一个低秩恢复模型过滤噪声。以上算法虽然能够在一定程度上去除点云噪声，但是尖锐特征区域容易出现模糊，造成之后重建模型失真。为了解决上述问题，本文提出一种旨在去除噪声点云的同时保持特征的点云去噪算法。该算法利用八叉树进行递归划分，得到点云之间的拓扑关系，同时加速点云的邻域搜索速度；然后在点云邻域的基础上利用主成分分析法（Principal Component Analysis，PCA）估算点云法向量，使用最小生成树解决点云法向不一致问题；最后依据双边滤波器能够保持特征的特点，将其与加权局部最优算法结合，从而实现点云去噪同时保持细节特征。

1 本文方法

1.1 基于八叉树的邻域搜索

一般情况下，三维扫描设备采集得到的原始点云数据只包含xyz空间坐标，并且点云之间散乱无序，不存在拓扑关系。本文使用八叉树来建立点云的拓扑结构，加速点云的邻域搜索。八叉树是一种描述三维空间的树状数据结构，其递归划分的过程是在开始邻域搜索时先假设一个搜索半径或者阈值，最开始的父节点代表一个标准正方体，一般以点云的最小包围盒大小作为标准正方体的体积，然后对父节点进行递归划分，又划分为8个相同大小的小正方体代表子节点。如果子节点的点云数量大于设定的一个阈值，则每个子节点继续向下划分为8个小正方体，直到点云数量小于阈值则递归划分结束，其过程如图1所示。图2为斯坦福Dragon模型建立八叉树的具体过程。该过程体现了八叉树进行邻域搜索时不需要遍历整个点云集的优点，只需要在部分空间中进行搜索，因此大大加快了点云邻域搜索速度，提高了算法运算效率。

图1 八叉树递归划分过程

图2 Dragon模型划分过程

1.2 PCA估算点云法向量

法向量是点云不可缺少的重要信息。点云法向量一般采用主成分分析法[13]（Principal Component Analysis，PCA）来估算。PCA用于法向量估计时，只能得到大致的点云法向量，对于点云法向量方向是否一致无法进行确定。因此，首先进行法向量方向的判断。设两个相邻点的法矢向量为ni和nj，若ni与nj是平行的，则ni·nj=±1；如果ni·nj＞0，则表示ni与nj之间法向量方向相同；如果ni·nj＜0，则表示ni和nj之间法向量方向相反，需要使用奇偶图或者最小生成树法（Minimal Spanning Tree，MST）实现法向一致性。本文使用最小生成树法实现法矢方向一致。首先构造点云的黎曼图，任意确定一个点的法向量，沿此点的法向量方向进行传播，然后根据点云法向量之间点积的值进行判断，如果点积值为负则将其法向翻转，重复遍历，直到所有点的法向量方向被调整为一致。

1.3 改进的局部最优投影算法

1.3.1 LOP算法和WLOP算法

为了解决点云噪声和分布不均的问题，LIPMAN[14]等基于L1中值问题提出了一种不受点云参数影响的去噪算法，即局部最优投影算法（Local Optimal Projection，LOP）。该算法的核心思想是将目标点云Q={qi}i∈I⊂R3投影到原始点云P={pj}j∈J⊂R3上，从而得到不含噪声的点云Q。具体算法如下。

对原始点云P={pj}j∈J⊂R3，LOP以任意点集开始，将X(0)投影到P上，进行能量方程的优化：

式中：E1(X,P,C)项中的θ(r)是快速递减的空间加权函数，作用是促使投影点尽可能逼近采样表面；E2(X,C)项中的η(r)是递减的惩罚函数，目的是使投影点保持均匀分布；E2(X,C)项中的λi′的作用是平衡E1(X,P,C)和E2(X,C)两项函数。当λi′参数设置得较小时，目标点云Q可以很好地逼近原始点云P，但是点云均匀性较差，当λi′参数设置得较大，则E1(X,P,C)项作用被削弱，可以得到均匀分布的目标点云Q，但是无法逼近原始点云P，达不到去噪效果。由此可见，LOP算法对初始点云P的采样点分布有很强的依赖性。因此，HUANG等[15]提出加权局部最佳投影（Weighted LOP，WLOP）。在LOP基础上，WLOP进行了两处修改：首先在E1(X,P,C)项加入了全局密度vj，在E2(X,C)项中加入全局密度wik，解决了LOP算法依赖于采样点导致的分布不均；其次，WLOP算法将惩罚项函数改为η(r)=-r，使函数可以收敛。WLOP算法具体方程如下：

1.3.2 双边加权的WLOP算法

尽管WLOP算法生成的点云分布更加均匀，但是由于没有考虑到尖锐特征，会导致结果中的尖锐特征丢失。而双边滤波器对尖锐特征有很好的保持效果。因此，本文从中得到启发，将双边滤波器与WLOP相结合。按照双边滤波器的公式：

式中：ni是PCA求得的法向量，β是双边滤波因子。在E1(X,P,C)项里加入双边滤波器，同时保持E2(X,C)项不变，得到一个去除噪声同时保留尖锐特征的点云算法。算法具体如下：

式中：θ1(x)是特征保留权重函数，目的是保持点云的尖锐特征。将公式迭代后得到：

式（14）的结果即为去噪后的点云。

2 实验结果

为了验证本文去噪算法的有效性，选用斯坦福大学的Dragon和Blade模型进行对比实验，在Windows 10平台上基于Visual Studio 2015软件和CGAL库实现本文算法。实验第一部分是在相同高斯噪声下对Dragon模型使用不同算法进行实验，第二部分是在不同强度高斯噪声下对Blade模型使用本文算法进行实验。

2.1 相同高斯噪声下不同算法的比较

使用PCL（Point Cloud Library）软件对Dragon点云模型增添15 dB噪声，然后分别用WLOP算法、RMLS算法、双边滤波算法和本文算法进行处理，结果如图3（b）、图3（c）、图3（d）、图3（e）所示。图3（a）为原始Dragon模型的重建结果。图3（b）为WLOP算法处理后的重建模型，对比图3（a）可以看出Dragon模型的头部、足部和尾部细节丢失较多。WLOP算法无法保持Dragon模型的尖锐特征，无法很好地还原原始模型。图3（c）为RMLS算法处理后的重建模型，对比图3（a）可以看出RMLS算法重建效果较差，Dragon模型的躯干、足部等出现了较大的缺失。图3（d）是双边滤波算法处理后的重建模型，虽然保留了Dragon模型的大部分细节和轮廓，但是重建模型中出现了部分空洞，并且模型光顺度不佳。图3（e）为本文算法处理后的重建模型，对比图3（a）可以看出本文算法基本还原了原始模型，同时比较图3（b）、图3（c）、图3（d）模型，也很好地保留了模型的头部、背部和足部细节信息，同时解决了模型缺失问题。

图3 相同噪声下不同算法的结果

图4（a）、图4（b）、图4（c）分别为WLOP算法、双边滤波算法、本文算法模型与原始Dragon模型的偏差比较结果。从图4各子图右边的色谱直方图可以看出，WLOP算法与原始模型偏差最大，最大偏差为0.010 2 mm；本文算法偏差最小，最大偏差仅0.009 0 mm。

图4 不同算法的偏差图

表1为3种不同算法处理后的误差比较，对比可以看出本文算法误差最小，最大程度地还原了原始模型。

表1 不同算法的误差比较

2.2 不同强度噪声下去噪算法的对比

为了验证不同强度高斯噪声下本文算法的效果，选用斯坦福的Blade模型进行实验。对原始的Blade模型添加信噪比SNR=10 dB、SNR=20 dB、SNR=30 dB的高斯噪声，结果如图5（c）、图6（c）、图7（c）所示。

图5 10 dB噪声下本文算法的结果

图6 20 dB噪声下本文算法的结果

图7 30 dB噪声下本文算法的结果

通过对比原始Blade模型可以看出，本文算法在不同噪声下均具有较好的去噪和细节特征保持。利用Geomagic Studio 2013软件进行模型偏差分析，结果如图8（a）、图8（b）、图8（c）所示。从偏差分析图可以看出，本文算法处理后的模型与原始模型整体偏差较小，误差保持在合理范围内，说明本文算法具有较好的鲁棒性。

图8 不同噪声下本文算法的偏差分析

表2为添加3种不同噪声后经过本文算法处理的Blade模型的偏差数据。对比可以看出，10 dB噪声时最大偏差、平均偏差和标准偏差都是最大的，但是仍然保持在合理范围内。30 dB噪声时最大偏差、平均偏差和标准偏差最小，说明算法去噪效果好，同时也保留了模型原始的细节特征。

表2 不同强度噪声下Blade模型的偏差分析

3 结 语

本文提出了一种保持细节特征的点云去噪算法。该算法利用八叉树加速了算法处理速度，同时通过改进的局部最优投影算法实现对点云的去噪和均匀化，以提高点云模型的精度。实验结果比对和偏差分析表明，该算法能够很好地去除点云数据中的噪点，保留模型原始的细节特征，在噪声强度较大的情况下也能够保持较小的误差，使模型具有很好的鲁棒性。