基于APOCS的点云去噪算法

李刚森　程远志

摘 要：使用3D扫描工具获取点云数据时常常会伴随着加性噪声。本文提出了一个基于凸集平均映射（APOCS）的原创点云去噪算法。首先，使用基于相关性筛选改良过的均值滤波算法对噪声点云的法向量进行滤波。每个滤波后的法向量都能决定其相对应的局部平面，将这些平面视为凸集，可通过APOCS算法更新点云中各点的位置。在本文的最后将给出该算法在不同强度噪声点云上与双边滤波对比的实验结果。

关键词：点云； 去噪； APOCS； Graph-cut

Abstract： Point cloud data is often accompanied by additive noise when it is collected by 3D scanning tools. This paper proposes an original method of point cloud denoising based on APOCS （Average Projections Onto Convex Sets）. First，the normal vectors of the noised point cloud is filtered using a mean filter improved by correlation based selection. And some planes are determined by the filtered normal vectors， which can be used to optimize the points ' locations through APOCS. Compared with bilateral filtering， the experiment demonstrates the results on point clouds with different intensity noises.

Key words： point cloud； denoise； APOCS； Graph-cut

引言

點云是计算机视觉领域一个新兴方向。随着近年来扫描技术的快速发展，大规模点云数据的获取成为可能。然而，扫描工具不能像相机那样精细，扫描获得的点云往往会包含加性噪声，严重影响了三维表面重构的效果。因此，点云数据的去噪算法将发挥十分重要的作用。现存的点云去噪算法主要是通过滤波实现的，包括邻域滤波和非局部滤波。这些方法在大多数情况下均能取得满意的效果，但对离异点的效果不佳。

本文提出一种原创的点云数据去噪方法，该方法基于凸集平均映射（APOCS），不仅能够与以往的点云去噪方法得到相同甚至更好的去噪效果，更关键的是对奇异点有极大的抗性。利用点P的邻域内各点的法向量包含的信息进行去噪，这比利用P邻域内各点的位置信息稳健的多。

1 相关技术

很多点云去噪算法都是从2D图像拓展到3D图像的，例如应用十分广泛的双边滤波。（Tomasi and Manduchi， 1998）利用双边滤波对噪声图像去噪[1]，而（Fleishman et al， 2003）将双边滤波应用到3D mesh模型去噪上[2]。此外，针对双边滤波不能同时兼顾平滑区域和纹理丰富区域的缺点，（Fu， 2015）将双边滤波和平面映射算法相结合应用到点云去噪当中[3]。除了双边滤波之外，（Taubin， 1995）将Laplace算法从图像处理领域延伸到点云上面[4]，（Deschaud， 2010）将非局部去噪算法发展到点云去噪上[5]。（Buades et al， 2005）提出了一种计算像素之间相似度的方法[6]，但此方法并不适用于点云数据，因此Mines提出了一种基于MLS （moving least-squares）的相似度计算方法，可用于点云数据上。无独有偶，（Mederos et al， 2003）将MLS用于点云去噪[7]，而（Fleishman et al， 2005）和（Oztireli et al， 2009）分别对该方法作出了改进而产生了RMLS（Robust Moving Leas Square） [8]和RIMLS（Robust Implicit Moving Least Square） [9]。有趣的是，这种基于MLS的点云去噪算法并不是通过滤波实现的，而是利用映射，这一点跟本文的方法如出一辙。

另外，还有一些专门针对3D点云数据提出的算法。（Zhu， 2005）提出了一种采用三维小块算法实现的数据点压缩方法[10]。（Liu， 2013）提出了一种相对复杂的基于三维重构数据的双向点云去噪算法[11]。（Zhu， 2015）推出利用密度分析检测分层奇异点的算法[12]。本文的方法也是直接针对3D点云数据提出的。

2 算法详述

2.1 算法概况

假设有一含有加性噪声的点云数据 C0=〖JB（{〗pi〖JB（|〗i∈I〖JB）〗〖JB）}〗，采用的算法是多次迭代的过程。每个迭代过程包含求点云法向量、更新点云顶点坐标两个步骤。首次得到点云法向量时，由于点云有噪声，法向量受到噪声的影响而不准确，此时采用一种经过相关性筛选改良的均值滤波对法向量进行滤波。众所周知，均值滤波有很强的平滑效果，为了避免点云过度平滑，仅在第1个循环当中采用这种法向量滤波操作，之后的迭代循环当中，只通过点云坐标估算法向量，不再对法向量做滤波操作。通常情况下，在迭代3到4次之后就可得到最优的去噪结果。算法流程如图1所示。

2.2 法向量的滤波算法

算法开始对法向量先做一次均值滤波操作。均值滤波器核的大小是决定滤波结果的一个重要参数。核太大，滤波结果会损失纹理信息，过于平滑。核太小，则滤波效果不明显。这里选取一个相对较小的滤波器核，然后基于核内各点与待滤波点的相关性做一次筛选，剔除噪声大的部分对滤波的影响。

本文的相关性筛选步骤受启发于基于图分割（graph cut）的聚类算法。将每个点云顶点视为图的顶点，点云顶点之间的相关性作为图的边，这样就可以构成一个图。不过与聚类不同的是，人们并不需要知道一共有多少个类别，也不必知道每个点的所属类别。只想找到与将要滤波的法向量所在点属于同一类的点，也就是找出哪些点是跟将要滤波的法向量相关性比较大的点。因此，并不需要建立一个完整的图（graph），或者说计算所有点两两之间的相关性，只需要计算待滤波点与其周围最近的Nf个点之间的相关性。至于Nf个点两两之间的相关性，并不需要计算，因而大大减少了算法的复杂度。

这里N是参考点的数量。阈值的选取依据计算得到的相关性自适应选择，一般会选择相关性分布的一个断层作为阈值，也就是阈值分开的两个集合中的点相关性差距较大。

相关性计算公式中第3项的作用可以从图3中清楚的看到。如图3所示，点云中存在一个奇异点（图中箭头所指），该点与邻域内其它点不在同一平面内，这种奇异点将影响做滤波的效果。若仅考虑两点的位置远近及法向量方向来计算两点之间的相似性是不够的，由于该奇异点与待滤波点pi（位于坐标原点的点）距离很近，法向量方向也差异不大，所以这个想要排除在外不予考虑的点很大程度上会被选作参与均值滤波的参考点。如在图3（b）中，该奇异点被选为pi的均值滤波参考点，而将两点在n〖DD（-*2〗→〖DD）〗i方向上的距离加入到相关性计算之后，奇异点就被排除在参考点集之外了。从图中可直观看到，奇异点在法向量方向上与其它非奇异点距离相差甚远，将这个特征作为筛选均值滤波参考点集的参考因素，得到的结果更为理想，如图3（c）所示。

与双边滤波对比的点云去噪的实验结果见表2，从表2可以看出本文方法处理后的误差要比双边滤波的误差小很多，尤其是dV。事实上，dV刻画的就是奇异点的处理结果，可以直观的理解为最大的误差，往往这些最大的误差都是在奇异点上产生的。为了使结果更加生动直观，将误差比例的折线在图6中给出。可以清晰明了地看到双边滤波对于dV的效果微乎其微，甚至在有些情況会扩大该误差。在这方面，本文提出的方法有显著性的提升。图7中给出一个典型代表的实验结果。图中右边一列出现的点都是与原始无噪声图像误差超过0.05的点，点越多说明结果越不好。图7（b）中的点明显多于图7（c），尤其是耳朵、脚等纹理丰富的部位。这也是算法的优势所在。

4 结束语

本文提出了一个基于APOCS的原创点云去噪算法，该算法通过重复计算法向量、更新点坐标的操作实现。首先，用相关性筛选改良过的均值滤波对法向量进行滤波，然后用基于APOCS的方法更新点云顶点的坐标位置。将本文的算法与双边滤波在不同噪声强度点云上的结果进行比较，印证了方法比双边滤波算法好很多，尤其是在处理奇异点的问题上。

参考文献

[1] TOMASI C， MANDUCHI R. Bilateral filtering for gray and color[LL]

[JP5] images[C]//IEEE Conference on Computer Vision. Bombay， India：IEEE， 1998： 839-846.

[2] FLEISHMAN S， DRORI I， COHEN-OR D. Bilateral mesh denoising[J]//ACM transactions on graphics （TOG）， 2003， 22（3）： 950-953.

[3] YAN Fu， ZHAI Jinlei. Research on scattered points cloud denoising algorithm[C]// 2015 IEEE International Conference on Signal Processing， Communications and Computing （ICSPCC）. NINGBO， CHINA：IEEE， 2015： 1-5.

[4] TAUBIN G. A signal processing approach to fair surface design[C]//Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. NEW YORK， NY， USA ：ACM， 1995： 351-358.

[5] DESCHAUD J E， GOULETTE F. Point cloud non local denoising using local surface descriptor similarity[J]. IAPRS， 2010， 38（3A）： 109-114.

[6] BUADES A， COLL B， MOREL J M. A non-local algorithm for image denoising[C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR '2005） . SAN DIEGO， CA， USA：IEEE， 2005： 60-65.

[7] MEDEROS B， VELHO L， de FIGURIREDO L H. Robust smoothing of noisy point clouds[C]//Proc. SIAM Conference on Geometric Design and Computing. Brentwood， TN：Nashboro Press， 2003： 1-13.

[8] ZTIRELI A C， GUENNEBAUD G， GROSS M. Feature preserving point set surfaces based on non-linear kernel regression[J].Computer Graphics Forum， 2009， 28（2）： 493-501.

[9] ZHU Maomao， FENG Zujun， GUO Jianhua， et al. Data point reduction using a 3-dimensional cube algorithm[J]. Journal of Shanghai University（Natural Science Edition）， 2005，11（3）：242-246.

[10]LIU Hui， WANG Boxiong， REN Huaiyi， et al. Two-way point cloud denoising method based on three-dimensional reconstruction data[J]. Journal of Electronic Measurement & Instrument， 2013， 27（1）：1-7.

[11]ZHU Junfeng， HU Xiangyun， ZHANG Zuxun， et al. Hierarchical outlier detection for point cloud data using a density analysis method[J]. Acta Geodaetica Et Cartographica Sinica， 2015， 44（3）：282-291.

[12]WANG Xianze， LI Zhongke， MAI Yaqi， et al. Robust denoising of unorganized point clouds[C]//IEEE Conference Anthology， China： IEEE， 2013： 1-3.

[13]ZHANG Wangyu， DENG Bailin， ZHANG Juyong， et al. Guided mesh normal filtering[C]//Computer Graphics Forum. 2015， 34（7）： 23-34.