基于OPTICS聚类和改进双边滤波的点云去噪方法

钟志鹏，张建州，梁彪

（1.四川大学计算机学院，成都 610065；2.东方电机有限公司焊接分厂，德阳 618000）

0 引言

获取真实世界物体的三维几何是计算机视觉和图形研究中的一个长期课题[1]。随着低成本、高分辨率三维扫描仪的商业化，三维点云数据的获取变得比较容易[2]。然而，由于传感器的限制，采集装置的固有噪声，场景中的表面或人工制品的反射特性等仪器自身因素、环境因素、人为因素，采集的点云数据不可避免地含有噪声。因此，有必要对原始点云进行去噪处理，以获得适合于进一步处理的精确点云[3]。好的去噪算法有以下几个特征（1）在有效去噪的同时能保持点云模型的特征；（2）抑制模型的体积和外形变化；（3）算法复杂度低；（4）具有较强的鲁棒性。

目前，国内外有许多学者对点云去噪提出了各种方法，Taubin[4]将图像Laplace滤波引入到网格模型去噪中，提出了基于信号处理的三角网格去噪方法，对于数据点密度不均匀的点云，容易造成数据点向密集处漂移；Fleishman等人[5，6]将图像双边滤波引入三维点云去噪，提出基于双边滤波的各向异性保特征去噪算法，算法简单且去噪速度较快，但对于大噪声容易造成过光顺、细节特征丢失；Desbrun等人[7]将基于偏微分方程技术运用到曲面处理上，提出了基于平均曲率流的三角网格光顺去噪算法，但会使点集的采样率变坏；王丽辉等人[8]结合模糊C均值和双边滤波进行点云去噪，该方法对不同尺度的噪声进行分步处理，得到了较好的效果，但对噪声敏感，会影响聚类结果；曹爽等人[9]利用邻域点将点分为特征点和非特征点，分别计算双边滤波因子进行去噪，有效保持了被扫描物体的特征，但特征选择时间较长；袁华等人[10]、李鹏飞等人[11]、李仁忠等人[12]和赵扬[13]都将噪声细分为大尺度和小尺度噪声，用统计滤波和半径滤波相结合去除大噪声，袁华、李仁忠和赵扬用改进双边滤波去除小噪声，李鹏飞用快速双边滤波去除小噪声，但噪声点去除效率不是很高；许龙等人[14]提出了基于模糊C均值和均值滤波的点云去噪算法，用模糊C均值聚类算法去除大噪声，用均值滤波去除小噪声，较好地保持了边界特征，但聚类结果也对噪声敏感。

尽管噪声点是随机产生的，但根据其分布可以将其分为大尺度噪声和小尺度噪声，大尺度噪声即离群噪声，这部分噪声离点云主体较远，小尺度噪声即点云模型表面噪声，这部分噪声离点云主体较近。针对不同尺度的噪声，为了在有效去除噪声的同时保留点云特征，本文提出一种基于OPTICS聚类和改进双边滤波的点云去噪算法，首先用OPTICS聚类算法去除大尺度噪声，然后用改进的双边滤波算法去除小尺度噪声。

1 基于OPTICS聚类的去噪

聚类算法使得类内的数据对象相似性尽可能大，类间的数据对象的差异性也尽可能大，所以可用其将点云主体和噪声有效地区分开。基于密度聚类的方法利用密度而不是距离进行聚类，能发现形状不规则的聚类，这对具有噪声的数据十分重要。这类算法用点邻域内的邻居点数来衡量该点所在空间的密度，如果它的密度大于给定阈值，则将其加入到相近的聚类中。其中 OPTICS（Ordering Points to Identify the Clus⁃tering Structure）是一种典型的基于密度聚类的方法[15]，它是对 DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法[16]的改进，该算法对输入参数邻域半径ε不再敏感，只要确定了邻域最少点数MinPts，邻域半径ε的改变不会影响得到的有序对象列表，并且能够通过得到的有序对象列表来获得不同密度的聚类。由于OPTICS算法不需要初始定义聚类数目、对噪声不敏感、对输入参数不敏感、能够识别噪声点，使得其非常适合处理点云模型中的噪声。

1.1 OP TICS算法的有关概念

假设数据集合为X={x1,x2,…,x3}，邻域半径为ε，邻域最少点数为MinPts：

定义1：ε邻域：设x∈X，x的ε邻域为：

定义2：密度：设x∈X，x的密度为：

定义 3：核心点：设x∈X，如果ρ(x)≥MinPts，则x为X的核心点。

定义 4：直接密度可达：设x,y∈X，如果x∈Nε(y)且ρ(y)≥MinPts（即x为y的ε邻域且y为核心点），则x是从y直接密度可达的。

定义5：核心距离：设x∈X，称使得x成为核心点的最小邻域半径为x的核心距离，数学定义为：

定义5：可达距离：设x,y∈X，y关于x的可达距离定义为：

1.2 OPTICS 算法去噪步骤

图1 OPTICS算法去噪流程图

图1为将OPTICS算法应用到点云去噪的基本步骤，具体如下：

（1）初始化：输入点云得到点集Points，给定邻域半径ε和邻域最少点数MinPts，创建两个队列：有序队列（核心点及其直接密度可达点）和结果队列（样本点输出次序）。

（2）如果点集Points中所有点都已处理，则跳转到（4）。否则从中点集Points取一个未处理（即不在结果队列）的核心点，将其放入结果队列，将其未在结果队列的直接密度可达点放入有序队列并按可达距离升序排列。

（3）如果有序队列为空，则跳转到步骤（2）。否则从有序队列中取出第一个点放入结果队列，并执行以下操作：

（3.1）如果该点非核心点，则跳转到步骤（3）。否则找到其所有直接密度可达点。

（3.2）如果该点所有直接密度可达点都已处理（即在结果队列），则跳转到步骤（3），否则取其中一点，执行下一步。

（3.3）如果该直接密度可达点已在有序队列，且此新的可达距离比旧的小，则用新的可达距离取代旧的，并重新排列有序队列，跳转到步骤（3.2）。

（3.4）如果该直接密度可达点不在有序队列，则插入该点，并重新排列有序队列，跳转到步骤（3.2）。

（4）得到有序对象列表（即结果队列），给定邻域半径ε͂（ε͂≤ε）。

（5）遍历所有点，去除可达距离和核心距离都大于ε͂的噪声点。

1.3 参数选择

在上述去噪步骤中，需要给定的参数有邻域半径ε、ε͂，邻域最少点数MinPts。由于确定了邻域最少点数MinPts，邻域半径ε的改变不会影响得到的有序对象列表，本实验中ε取MAX。MinPts的选取有一个指导性原则，即MinPts≥dim+1，其中dim表示数据的维度。根据实验，MinPts取4或5即可得到良好的效果。对于ε͂，计算每个点对应的第k个最近邻域的距离并降序排序，将这个排序图中第一个谷值点对应的k距离值设为ε͂，并可适当修改此值以获得实验数据的最佳效果。在ε取MAX的情况下，点的核心距离也是点对应的第k（=MinPts）个最近邻域距离，所以在实验中可直接通过核心距离求得，节省了开销。

2 基于改进的双边滤波算法去噪

经过基于OPTICS聚类的去噪后，大尺度噪声被去除，但点云模型表面仍有一些小尺度噪声。双边滤波算法[17]简单高效，对边缘特征有良好的保持效果，对小尺度噪声有较好的去除效果，所以本文采用双边滤波算法对小尺度噪声进行平滑去噪。双边滤波算法以当前点的邻域点的加权平均值来修正当前点的位置，从而达到滤波的效果。

2.1 传统双边滤波算法

传统双边滤波的表达式为：

其中，为滤波后的点，pi为原数据点，α为双边

滤波因子，n为点pi的法矢。α的表达式为：

Ws的表达式为：

其中，σc和σs为高斯滤波参数。σc为点pi到其邻域点的距离对点的影响因子，用来控制平滑程度。σc为点pi到其邻域点的距离在其法向上的投影对点pi的影响因子，用来控制特征保持程度。通常可以用数据点pi的邻域半径来表示σc，用数据点pi的邻域点标准差来表示σc。确定σc后，σc的不同取值会影响点云数据模型的平滑效果。

2.2 改进的双边滤波算法去噪

双边滤波因子受点局部邻域特征信息的影响较大，为了提高其保特征性与稳健性，对传统双边滤波因子进行改进。改进后的双边滤波因子为：

其中各项参数含义均与2.1小节中相同。

改进的双边滤波算法去噪的基本步骤如下：

（1）对每个点pi，计算它的k个最近邻域点N(pi)。

（2）对每个点pi，在k邻域的基础上通过主成分分析法（PCA）来获得点pi的法矢，并进行法向一致性调整。

（3）对每个近邻点pi，计算平滑滤波权函数的参数和特征保持权函数的参数

（4）按照式（7）和式（8）计算出平滑滤波权函数Wc(x)和特征保持权函数WS(y)。

（5）将Wc(x)和WS(y)代入式（9）求出改进双边滤波因子α′的值。

（6）通过式（5）计算使用改进双边滤波后的点的位置，将点pi移动到新的位置处。

（7）遍历完所有点后，得到平滑去噪后的新点云模型，算法终止。

3 实验结果

本文实验均通过VS2013、PCL点云库和MATLAB实现。为了验证本文算法的有效性，选取了经典的Stanford bunny点云模型以及Laurana点云模型来进行实验，在原始点云中随机选取了一定数量的点，在它们的法线方向上增加了噪声点，噪声模型如下：

其中，为滤波后的点，pi为原数据点，β为随机数，ni为点pi的法矢。此外，还将本文算法与常用的三维点云去噪算法统计滤波、半径滤波和统计滤波结合半径滤波进行了比较。

图2 不同去噪方法Stanford bunny点云模型的去噪效果图

图3不同去噪方法Laurana点云模型的去噪效果图

图2 、图3分别是不同去噪方法对Stanford bunny点云模型和Laurana点云模型的去噪效果图。从图2（f）、图3（f）可以看到点云周围的大尺度噪声被去除了，并且较好地保留了点云特征，说明本文算法能有效去除大尺度噪声。通过比较图 2（f）与图 2（c）（d）（e）、图 3（f）与图 3（c）（d）（e）可知本文算法去除的大尺度噪声数多于统计滤波、半径滤波和二者结合滤波。通过对比图 2（f）与图 2（g）、图 3（f）与图 3（g）可以看到点云周围的小尺度噪声被去除了，从对比局部放大的图2（h）与图 2（i）、图 3（h）与图 3（i）更能清晰地看到去除和平滑的效果，同时也很好地保留了点云特征，说明改进双边滤波能够有效去除和平滑小尺度噪声。

表1为不同去噪方法的去噪效果数据对比，通过具体数值更能得知本文算法能有效去除噪声，且效率较高。

表1 不同去噪方法去噪效果对比

4 结语

本文将利用OPTICS聚类去除大尺度噪声的优势和改进双边滤波去除小尺度噪声的优势，将二者相结合用于点云去噪，并将该方法与常用的点云去噪方法统计滤波、半径滤波、统计滤波结合半径滤波进行了对比分析。通过使用Stanford bunny点云模型以及Lau⁃rana点云模型进行实验，证明了本文方法对点云去噪是有效的，且能较好地保留点云的特征。通过对比实验证明了本文方法提高了准确性。