采用密度k-means和改进双边滤波的点云自适应去噪算法*

郭 进, 陈小宁, 吕峻闽, 徐鸿雁

(西南财经大学 天府学院 信息技术中心,四川 绵阳 621000)

采用密度k-means和改进双边滤波的点云自适应去噪算法*

郭 进, 陈小宁, 吕峻闽, 徐鸿雁

(西南财经大学 天府学院 信息技术中心,四川 绵阳 621000)

采用相移结构光测量系统得到的三维点云，不可避免存在噪声。通过密度k均值(k-means)聚类算法将点云分为大尺度噪声点和小尺度噪声点，设定邻域大小以及点的数量来去除孤立噪声点；使用类内距离和类间距离的比值作为评价函数,得到最佳聚类数去除小片噪声点云；对于混杂在真实点云中的小尺度噪声点，采用鲁棒性更强的改进型双边滤波器进行点云光顺。实验验证表明:采用基于密度k-means和改进双边滤波结合的点云去噪算法可以有效去除各类噪声点，保持点云特征，相比平均曲率算法和基于特征选择的双边滤波算法，去噪效率分别提高了24 %和16 %。

多频相移;k均值聚类; 双边滤波; 点云; 曲率

0 引 言

计算机视觉在逆向工程、工业检测等领域中得到广泛应用，获取高精度点云模型成为研究热点[1]。获得三维点云数据的方式主要有激光和结构光测量，激光测量采用线扫描，得到噪声较大的散乱点云；结构光测量采用面扫描，从格雷码加相移，到基于时间相位的多频相移[2]，得到有序点云，但也会引入噪声。

基于相移结构光的测量系统在获取点云过程中，会出现各种噪声点，大尺度噪声点表现为离散颗粒噪声点，或者小片解相位误差点云[3]；小尺度噪声夹杂在真实点云当中，因为投影仪Gamma畸变[4]，以及测量系统的非线性误差[5]而产生。学者们研究了例如卡尔曼滤波，Mean-Shift[6]等，苏志勋[7]采用基于法向修正的中值滤波，但法向修正会出现误差而影响迭代计算；肖春霞等人[8]实现基于平均曲率流的去噪，但属于同性算法，不能很好地区分是高频特征还是噪声。去噪的同时要防止因算法导致细节过度丢失，学者们研究了基于各向异性的算法。范涵奇[9]通过鲁棒统计理论计算点云表面几何特征，在曲率空间对点云进行滤波，但对颗粒噪声点识别不理想；宋阳等人[10]将C均值聚类和双边滤波相结合，达到了不错的效果；葛宝臻[11]将平面投影与双边滤波结合实现点云自适应去噪，但在顶点曲率估计上有误差；曹爽[12]采用基于特征选择的双边滤波去噪，采用不同滤波因子去噪，但特征选择过程时间较长。

各向异性算法得到了很大的改进，但很多无法有效识别噪声类型。为了更好地识别噪声类型，对尖锐的噪声进行去除，保留点云特征，本文提出基于密度k-means和改进双边滤波的点云自适应去噪，针对大尺度噪声点和小片噪声点云，采用基于密度的k-means算法，通过设定邻域以及计算该邻域内点云数量来排除孤立点；采用类内和类间距离的比值作评价函数，确定最佳聚类数，设定阈值来排除小片噪声点。针对小尺度噪声点，采用改进型的双边滤波器进行各向异性平滑去噪，提高了去燥效率。

1 三维点云去噪算法

1.1 传统k-means聚类原理

根据k-means聚类原理来排除大尺度噪声点中的颗粒点和小片点云，从n个点的数据集{p1,p2,p3,…，pn}中，找出k个聚类中心{a1,a2,a3,…，ak}簇，使聚类后的每片对象具有很高相似度。开始从n个待聚类的对象中随机选择k个作为初始值，再根据所有对象离每个聚类中心的距离分配到最近的中心，计算新聚类中心簇的质心，取平均距离，进行迭代，直到目标函数收敛后实现聚类

(1)

式中 Wn为数据集{p1,p2,p3,…，pn}中所有对象与它所在的聚类中心的平方误差之和，ai为聚类中心的均值，pj为每个聚类中的对象。

1.2 密度k-means点云聚类中心数确定

1.2.1 孤立噪声点剔除

定义P={p1,p2,p3,…，pn},P∈R3为三维空间的点云集，n为点云总个数，密度为pi的邻域内点的数量。定义邻域为以pi为中心，半径为E的三维球体

Z(pi)={pi∈P|0≤dis(pi,pj)≤E,

i=1,2,…,n,j=1,2,…，n}

(2)

式中dis(pi,pj)为邻域内两个点的欧氏距离

dis(pi,pj)=

(3)

通过经验值确定半径E，以及邻域最少三维点个数minp，求点云集中每个三维点的密度，根据minp值判断哪些是颗粒噪声点ns，哪些是集合点np，将颗粒点从样本中删除，实现大尺度噪声点剔除，数据集减少为n-ns。再遍历三维点数据，根据标记判断三维点pi是否有相同的集合点，如果有则只保留一个作为集合点，并标记重复个数为nc，再将np-nc作为初始聚类的样本个数值m。

1.2.2 类内和类间距离比值的判断准则

采用类内和类间距离比值作为评价准则。定义类内距离Din(k)为每个三维点到同一个簇中其它三维点的平均距离的最小值。而整个点云的类内距离为所有簇中类内距离最大值

(4)

定义类间距离Dout(k)为不同聚类中心簇的最近两个三维点的距离

(5)

评价函数定义如下，比值越小说明聚类效果越好

Q=Din(k)/Dout(k)

(6)

1.3 基于密度k-means大尺度噪声点去除算法

1)按照1.2节的方法首先确定点云初始聚类个数m=np-nc，聚类中心ai(i=1,2,…,m)，排除颗粒噪声点。

2)计算三维点与各个聚类中心簇的距离，按照距离最近原则进行聚类，更新新簇质心

(7)

3)由式(4)、式(5)、式(6)计算评价函数Qm。

4)合并类间距离最近的两个点云簇，标记新簇和新簇质心

(8)

5)重复步骤(2)～(4)，直至m=1。

6)查找步骤(1)～(5)过程中计算的Qm，确定最佳聚类数，选择最小的Qm，从m个点云簇中，判断每个点云个数是否都不小于minp，若是则m为最佳聚类数k，若不是则舍弃该Qm，再重复步骤(6)。

7)得到了最佳聚类数，再根据设定的噪声点阈值数去除小片噪声点。

1.4 改进型双边滤波的小尺度噪声点去噪

1.4.1 传统双边滤波点云去噪模型

传统双边滤波器首先估计点云法向和曲率，再根据滤波因子计算三维点的偏移量，移动各点到新的位置。双边滤波定义为

(9)

a=

(10)

式中 N为pi的邻域，Wc为pi到邻域的光顺滤波因子，Ws为pi到邻域在法向上的特征保持因子，ni和nj为pi和pj的法相量

(11)

(12)

式中 σc和σs为高斯参数，σc为控制光顺程度，σs为控制特征保持程度。使用双边滤波算法实现对点云中小尺度噪声点的各向异性去噪，有效去噪的同时达到很好地保留特征效果。

1.4.2 改进型双边滤波点云去噪

本文对传统双边滤波因子进行改进，采用法向夹角的余弦值作为特征保持因子，在邻域内采样点的法向变化能够反映特征变化，点云特征变化大的地方，曲率变化大，对应法向变化也大；特征变化小的地方，比较平坦，曲率变化小，对应法向变化也小，因此，采用法向夹角作为特征保持因子能够在特征变化大的地方凸显出来。

1)当邻域点与当前计算的点的法向夹角在0°～90°的时候，其余弦值随夹角变大而变小，双边滤波器的特征保持权值也随夹角变大而减小。

2)当邻域点与当前计算的点的法向夹角大于90°时，认为该点对当前点不再有影响，令特征保持权值为0。

2 本文算法优点

本文算法主要实现了点云分类去噪，优点表现为:

1)根据相移光栅匹配的原理快速建立点云拓扑结构。由极几何约束和相位约束实现纵向和横向的匹配，实现三维点与图像点的映射。由此建立三维点云数据拓扑结构的效率将大大提高，是k-d树，八叉树等算法无法相比的。

2)实现噪声点的分类处理，将噪声点区分为大尺度和小尺度，大尺度噪声点分为了孤立噪声和小片噪声。从噪声来源上进行区分，针对不同原因产生的噪声进行不同的处理，很好实现点云去噪的自适应处理。

3)采用改进双边滤波使得特征保持权重因子被限定在一个更加合理的范围，能够增强特征保持性，再计算其多个邻域点法向夹角的时候，隐式的引入了多个滤波平面，也能够增强数据点的抗噪性能，改善滤波效果。

3 实验结果与对比分析

为了验证实验结果，选用加噪的平面点云进行实验，验证算法有效性，再选择牙模和挂坠的点云数据进行对比实验，验证算法的效率。

图1 去除大尺度噪声点效果图Fig 1 Effect diagram of removing large scale noise point

采用本文算法对加了噪声的平面点云进行去噪处理，图1(a)为含大量颗粒噪声点的大尺度噪声点云，图1(b)为采用密度k-means处理后的点云，大尺度的噪声点已经全部清除。

为了进一步验证算法的有效性，选取了噪声点较多的挂坠玉佩点云(噪声点数为2 000)以及特征较多的义齿牙模点云，将本文算法和平均曲率流，基于特征选择的双边滤波算法进行对比实验。

图2(a)～图2(d)为经过不同去噪算法处理后的效果图，图2(a)为原始点云，噪声分布在点云的周围，图2(b)为采用平均曲率流去噪后得到的点云，仅能去除一些颗粒噪声点，对小片噪声点处理效果不佳，图2(c)为基于特征选择的双边滤波去噪算法得到的点云，距离较近的小片噪声点云无法剔除，图2(d)为本文算法，噪声点去除效果较好。从表1可以看出，针对该点云数据，平均曲率流算法的去噪效率为70 %，基于特征选择的双边滤波为78%，而本文的去噪效率为94 %，大大降低了噪声点。

图2 不同去噪算法玉佩点云对比图Fig 2 Comparison diagram of points cloud by different denoising algorithms

点云模型玉佩点云(噪声点2000)玉佩三角面个数去噪点点云去噪效率/%原始点云14834229265700平均曲率146936290824140670特征选择双边滤波146770289914157278本文算法146457289831188594

通过对特征比较丰富的义齿模型进行对比实验，观察点云曲率变化较大的地方经过不同去噪算法处理后特征保持效果。图3(a)为原始点云，直接三角化后牙齿特征放大图示，图中可以看出该牙齿部分噪声较多，图3(b)为经过平均曲率流算法处理后的点云牙齿三角化放大图示，相比图3(a)去噪效果明显，但在牙齿的曲率变化比较大的地方，丢失了细节。图3(c)为双边滤波算法处理后牙齿三角化放大图示，相对于图3(a)去噪效果也较明显，相对于图3(b)特征保持较好。图3(d)为本文算法采用的改进型双边滤波，相对于图3(a)达到了更好的去噪效果，相对于图3(b)和图3(d)又更好保持了点云特征，尤其是曲率变化较大的细节。

4 结 论

本文分析了结构光测量系统的误差和噪声的来源，将噪声点分为大尺度的孤立噪声点和小片噪声点，以及掺杂

图3 不同去噪算法义齿点云三角面对比图Fig 3 Comparison diagram of denture points cloud by different denoising algorithms

在点云当中的小尺度噪声。提出了基于密度k-means和改进双边滤波相结合的点云去噪算法，针对大尺度点云，采用基于密度k-means聚类算法剔除，使用改进型双边滤波器对小尺度噪声点进行去噪，在去噪平滑的同时较好保留了点云特征。相比平均曲率算法和基于特征选择的双边滤波算法实验证明去噪效率大大提高，可以有效提高去噪准确度。

[1] 张晓娟，李忠科，王先泽，等.基于特征点和改进ICP的三维点云数据配准算法[J].传感器与微系统，2012，31(9)：116-122.

[2] 黄亚楠，娄小平.基于多频外差原理的相位校正及匹配方法研究[J].应用光学，2014，2(2):237-241.

[3] 吴蜀予，杨宜民，钟震宇，等.光栅投影测量系统中的相位误差校正算法[J].光学学报，2014，7(7):123-128.

[4] Li Zhongwei,Fu You.Gamma-distorted fringe image modeling and accurate gamma correction for fast phase measuring profilo-metry[J].Optics Letters,2011,36(2):154-156.

[5] Xu Ying,Ekstrand Laura,Dai Junfei.Phase error compensation for three-dimensional shape measurement with projector defocu-sing[J].Appl Opt,2011,50(17):2578-2581.

[6] Song J.Two-stage point-sampled model denoising by robust ellipsoid criterion and mean shift[C]∥2013 Int’l Conf on Intelligent System Design and Engineering Applications,Hong Kong:IEEE,2013:1581-1584.

[7] 苏志勋，栗志扬，王小超.基于法向修正及中值滤波的点云平滑[J].计算机辅助设计与图形学学报，2010，22(11):1892-1898.

[8] Xiao Chunxia,Miao Yongwei,Liu Shu,et al.A dynamic balanced flow for filtering point-sampled geometry[J].The Visual Compu-ter,2006,22(3):210-219.

[9] 范涵奇，苗兰芳，张 鑫，等.鲁棒的高阶双边滤波去噪算法[J].计算机辅助设计与图形学学报，2009，21(6):812-818.

[10] 宋 阳，李昌华，马宗方，等.应用于三维点云数据去噪的改进C均值算法[J].计算机工程与应用，2015，51(12):1-4.

[11] 葛宝臻，项 晨，田庆国.基于曲率特征混合分类的高密度点云去噪方法[J].纳米技术与精密工程，2012，10(1):64-67.

[12] 曹 爽，岳建平，马 文.基于特征选择的双边滤波点云去噪算法[J].东南大学学报，2013，43(2):351-354.

[13] 张 琳，陈 燕，汲 业，等.一种基于密度的K-means算法研究[J].计算机应用研究，2011，28(11):4071-4073.

[14] Fu Desheng,Zhou C.Improvedk-means algorithm and its implementation based on density[J].Journal of Computer Applications,2011,31(2):432-434.

[15] 周世兵，徐振源，唐旭清.K-means算法最佳聚类数确定方法[J].计算机应用，2010，30(8):1995-1998.

[16] 王 勇，唐 靖，饶勤菲，等.一种新的散乱点云快速去噪算法[J].计算机应用与软件，2015,23(7):74-78.

Points cloud self-adaptive denoising algorithm based on densityk-means and improved bilateral fitering*

GUO Jin, CHEN Xiao-ning, LÜ Jun-min, XU Hong-yan

(Tian Fu College of Southwestern University of Finance and Economic,Mianyang 621000,China)

3D points cloud gained by using phase-shift measurement system unavoidably has noise.Cloud-point is divided into large scale noise points and small scale noise points by densityk-means clustering algorithm,isolated noise points is removed by setting neighbourhood size and quantity of points;take ratio of intraclass distance and between-class distance as evaluation function obtain the optimal number of clusters to remove little noise points cloud.Using stronger robustness improved bilateral filterer for points cloud.Experiment shows that point clouds de-noising algorithm combines densityk-means and improved bilateral filtering can effectively remove noises point,maintain point cloud features.Compared to mean curvature algorithm and the bilateral filtering algorithm based on feature selection,the de-noising efficiency are improved around 24 % and 16 %.

multiple frequency phase-shift;k-means clustering; bilateral filtering; points cloud; curvity

10.13873/J.1000—9787(2016)07—0147—03

2016—05—06

四川省教育厅一般项目(15ZB0475,13ZB0377)

TP 391.4

A

1000—9787(2016)07—0147—03

郭 进(1982-)，男，四川郫县人，硕士，讲师，从事机器视觉、数字图像处理、三维光学测量方面工作。