邻域自适应的三维点云滤波算法

吴俊威，焦吾振，郑河荣

(浙江工业大学 计算机科学与技术学院，杭州 310023)

1 引 言

近年来，利用三维激光扫描仪获取物体表面三维坐标并进行处理成为智能制造的趋势所字.对于这些得到离散三维点云集合，需要通过去噪、网格化才能成为工程上有意义的三维数据[1].因此，如何有效地对三维点云数据进行处理，得到高质量数据以及网格化后处理是一个非常重要的问题.这也是图形学的一个长期研究热点.

对于三维扫描数据，由于用户、设备和扫描环境等各种因素的影响，三维点云数据不仅包含大量的噪点和离群点(外点)[2].因此，需要对原始扫描数据进行滤波操作，去除这些噪点和外点.在三维重建过程中，点云滤波算法扮演着一个十分基础但关键的角色.否则由于点云噪声的存在，三维扫描点云网格化处理以及逆向工程应用会出现许多问题.例如重建网格会导致拓扑连接错误.对于点云滤波，目前最为典型的做法把网格滤波算法扩展到点云滤波.因此研究人员针对点云建立拓扑结构，通常做法是给点云建立八叉树或者kd-tree，使点云拥有和网格相似的邻域关系结构.在现有研究中，网格滤波算法中拓展推出了很多点云滤波算法，如常见的拉普拉斯滤波，双边滤波等.但是网格滤波算法应用于点云滤波，需要考虑的问题是如何更好地保持精度、维持细小特征.特别是在工业领域应用中，因为去噪过程要求更高的精度保持，滤波算法难度也大大增加.已有研究人员在精度维持方面也提出了一些改进.在一个集成点云处理的方法中，Ohtake等人[3]，在防止点云滤波收缩中提出一个用二次误差计算滤波偏差的方法来进行去噪.Schall等人[4]在此基础上提出基于核聚类的方法，首先为每一个点定义一个局部似然函数，然后定义模型整体的似然函数，应用类似梯度下降法，把每一个采样点迭代到似然函数最大的位置.Kalogerakis等人[5]提出了一个鲁棒的统计学点云滤波框架，他们用一个迭代的最小二乘方法来估计每个采样点的曲率并分配不同的权重，利用这曲率和权重进行修正法线，进而进行保特征滤波.另外，基于点邻域的双边滤波算法[6]，其利用采样点周围点的距离以及采样点和周围点的相似性把图像双边滤波推广到三维点云和网格滤波中.Lipman等人[7]提出局部最优投影(LOP)算法，该算法用点云中的一个子集去投影到原始点云中，得到一个去噪后的原始点云的子集，里面有两个惩罚函数一个控制平滑力度，另一个控制点的分布是否均匀，该算法可以很好的去除高噪声.Huang等人[8]在局部最优投影的基础上根据不同位置的点云密度提出加权局部最优投影(WLOP)算法，后面Huang等人[9]又在此基础上提出增采样，提高在特征边缘的恢复能力，也取得了不错的效果.基于拟合曲面的移动最小二乘方法(Moving least squares，MLS)[10，11]滤波算法中，利用采样点邻域构建移动最小二乘曲面来拟合真实表面，也取得了不错的滤波结果.之后针对稀疏采样和尖锐特征丢失的问题又提出了鲁棒性隐式移动最小二乘法(Robust Implicit Moving least squares，RIMLS)[12].字典学习[13]算法被用到点云滤波和表面重建中也取得了很好的滤波效果.陈永辉等人[14]提出了一种利用高斯映射划分特征点，引入法向量权重，实现特征保持的均匀采样算法.陈佳舟等人[15]提出了重投影剔除和基于空间剖分的扩散聚类算法的滤波思路.王勇等人[16]提出了一种多分辨率配准点的ICP算法，在精度和速度上有较大提高，随后王勇等人[17]在此算法基础上进行了改进，在粗配准阶段采用欧式距离约束和RANSAC 算法进行外地点剔除，保证良好的滤波效果.

但是已有研究点云滤波算法会出现收缩，从而影响重建精度.因此论文提出了鲁棒性的邻域自适应的混合点云采样滤波算法，旨在提高点云滤波精度.算法首先对特征处邻域均值滤波点云数据中插入对应原始点，提高采样密度同时保留原始点云特征信息；然后算法通过法向夹角和曲率约束定义自适应邻域保持局部特征；最后为采样点定义一个似然函数求解得到滤波位置.实验部分表明，本文算法在保证滤波效果的同时提高了点云滤波精度.

2 点云滤波收缩问题分析

对于点云滤波，由于原始点云存在较大噪声，从而导致滤波结果不够光滑[3].因此，研究人员为了提高滤波结果的平滑性，对原始点云(特别是尖锐特征处)进行重新采样[4].虽然这种处理方法对滤波的平滑性有较好提高，并且使用重采样恢复，较好的保留了平滑后的尖锐特征.但是，因为这种算法将原始点云使用均值点来进行取代，导致了滤波结果出现收缩问题.收缩是指算法在滤波过程中对原始点云进行重采样等操作所导致的测量精度下降问题.因此，如何在保持尖锐特征和平滑性的同时，更好地避免收缩现象是滤波算法需要考虑的问题.

图1 原始点和均值点Fig.1 Original point and mean point

为了更好地理解收缩问题，图1中给出了三维原始点和滤波均值点的示意图.从滤波知识可以知道，均值点相对于原始点云数据，可以获得更好的平滑效果.但是从图1(c)中可以看到均值点本身已经在特征处偏移了实际点云位置，利用均值点滤波丢失了原始点云信息，尤其在特征处收缩严重，无法很好的还原扫描物体的真实曲面.

图2 均值点云滤波收缩问题Fig.2 Mean point cloud filtering shrinkage problem

为了进一步分析滤波过程中的收缩问题，图2给出了三维扫描数据的滤波前后的二维截面误差对比图.二维截面图中，线1表示原始点云，线2表示滤波结果.可以发现，实际三维扫描数据实验结果在均值点滤波后，曲线位置发生了明显的偏移误差.其中在顶部出现明显的凸起，而在根部又逆向凹陷，出现了逆向收缩的现象.无法满足逆向工程要求.

3 自适应滤波邻域选择

对于点云滤波，需要建立拓扑关系用于邻域点选择.目前，点云拓扑通常采用kd-tree结构.但是kd-tree一个主要问题是只考虑点云的距离.这个问题会导致在曲率特征变化的地方，不同曲率和法向差别较大的点会相互影响，造成精度误差.图3中点1为滤波点，圈内区域点为kd-tree搜索到的邻域点，可以看到不同曲率和法线的点被同时选中，造成滤波后精度损失.

为了进一步分析滤波误差，论文进行实际三维扫描数据实验对比.实验结果可以知道仅仅采用距离定义邻域进行点云滤波，会出现在曲率变化明显的部分相互影响严重，根部由于低曲率平面和高曲率加强筋部分相互影响，造成了中部凸起和平面凹陷的问题，凸起部分达到0.14mm，平面凹陷部分达到0.05mm.

图 3 kd-tree邻域选择Fig.3 kd-tree neighborhood selection

针对这一问题，算法在进行邻域计算的时候，首先进行合理邻域的选择.论文算法受到文献[18]的启发，自适应选择邻域，用式(1)来确定：

(1)

这里0≤T≤1是一个用户自己设定的法向阈值，试验中一般选取0.5.这里可以看到计算过程中，如果两个点的法线相差很大，超过了阈值，则可以认为在计算中舍弃了该点，不加入计算.在应用PCA分析中可以很容易获得该点的曲率信息，因此为了防止在计算高曲率点被低曲率点影响，低曲率点被高曲率点影响，对精度造成损失，我们用类似的方法去除曲率差别很大的点.

4 似然估计

在上述混合点云和自适应邻域条件下，算法采用似然函数计算滤波采样点的真实位置.算法首先为每一个采样点向量pi定义一个局部似然函数Li.Li由点pi所在邻域{PSi}中任意点向量psj到该邻域的最小二乘拟合平面距离的平方所确定.

首先根据式(2)通过计算带有权重的协方差矩阵来获得最小二乘拟合平面Ci.

(2)

然后采用公式(3) 计算点pi到最小二乘拟合平面距离的平方确定局部似然函数Li.

Li=Φi(pi-ci)[h2-[(pi-ci)·ni]2]

(3)

其中，h为邻域搜索半径，Φ为高斯函数，ni为法向.

似然函数L反映了点是采样表面的似然性，根据所有采样点pi的局部似然函数Li来确定.

(4)

在本文中我们定义wi的值为上节的曲率法线约束值.

在定义了似然函数后，我们对于公式(4)该点云模型的似然函数，采用梯度下降的方法，把所有采样点迭代到其最大似然值的位置.其滤波迭代序列为：

(5)

(6)

5 实验结果分析

为了进一步验证论文算法的有效性，本节和相关算法进行比较.这些相关算法包括在点云滤波里面使用最为广泛的双边滤波采样[6]；以及Huang等[9]人提出的用于边缘特征维持的增采样策略；Schall等[4]人所采用的不考虑领域自适应处理的似然函数估计算法.

本文通过在主频2.7GHz、内存32G的Intel i7 DELL图形工作站进行数据处理来验证论文算法的有效性.首先，采用HScan330手持三维激光扫描仪获取模型点云数据完成数据采集，然后应用本文算法、文献[4]算法、文献[6]算法和文献[9]算法进行点云滤波去噪，最后把滤波后的点云数据与原始未滤波点云数据进行精度对比，精度对比采用Geomagic Qualify 2013软件平台进行比对检测，精度比较采用软件定义的四元素法(D、Dx、Dy、Dz)：测量总误差(D)、测量X方向误差(Dx)、测量Y方向误差(Dy)、测量Z方向误差(Dz)，表中给出了图4中标注误差数值.

图4 钣金件扫描比对结果Fig.4 Sheet metal scan comparison results

首先我们对工业常见钣金件(见图4)进行扫描滤波处理，各算法在去除噪声点，平滑方面都取得了满意的结果.然而通过分析滤波后与原始点云进行精度对比的色谱图数据(见表1)可以明显看出，文献[6]算法和文献[9]算法已经明显可以看出收缩，无法适用于逆向工程，而本文算法和文献[4]精度都保持在0.04mm以内，效果较好接下来我们又扫描了汽车轮毂(见图5)进行滤波测试和精度对比.从表2的滤波结果看出双边滤波中去除噪声点和精度保持方面都没能达到令人满意的结果.而本文算法在滤除噪声点和文献[4]保持一致的情况下，保持了较好的进度，都基本保持在0.04mm以内.滤波结果甚至可以应用于工业逆向工程和检测等高精度领域.

表1 图中标注3点的钣金件不同误差(D、Dx、Dy、Dz)Table 1 Different errors of sheet metal parts marked with 3 points in the figure(D、Dx、Dy、Dz)

最后，对工业零件中常见的加强筋(见图6)进行测试.通常情况下，圆弧角越小，滤波后点云精度丢失越多.我们选择距离2mm的加强筋进行更加严苛的精度测试.从表3可以看出双边滤波已经达到0.20mm，无法被工业逆向检测所接受.而在此种更小的圆弧角情况下，文献[4]算法的精度丢失也达到了0.08mm，本文算法的在混合点云增采样基础上，加入曲率约束和法线约束后精度丢失依旧可以保持在0.05mm以内的误差范围，在不牺牲滤波效果的前提下，对精度有了更好的保持.

表2 图中标注3点的轮毂不同误差(D、Dx、Dy、Dz)Table 2 Different wheel hub errors marked with 3 points(D，Dx，Dy，Dz)

表4的精度对比中可以看出，本文算法在实验结果中精度保持表现最好，都能保持在0.05mm以内，可以应用于工业逆向造型和检测.

图6 加强筋扫描比对结果Fig.6 Stiffener scan comparison results

表3 图中标注3点的发动机盖不同误差(D、Dx、Dy、Dz)Table 3 Different errors of the hood marked with 3 points in the figure(D，Dx，Dy，Dz)

表4 精度比较Table 4 Precision comparison

6 结 论

论文提出了一种保精度的混合点云滤波算法，在滤波效果得到保证的情况下，对点云滤波的精度保持进行了提高.该算法不仅在工业检测和逆向工程中可广泛应用，而且对三维扫描后处理的发展和应用有积极的意义.

对于点云滤波，影响精度的另外一个主要原因是法向估计.已有研究搜索采样点周围的邻域点，进行平面拟合，计算该平面的法向量作为该点的法向量.这种方法会导致高噪声点云数据出现明显误差，进而降低滤波精度.在后续工作，论文将考虑研究更为稳定可靠的法向计算方法，提高算法准确率.