一种新的三维点云模型去噪光滑算法研究

廖昌粟 何东建 王美丽*

1(西北农林科技大学信息工程学院 陕西 杨凌 712100)2(西北农林科技大学机械与电子工程学院 陕西 杨凌 712100)

一种新的三维点云模型去噪光滑算法研究

廖昌粟1何东建2王美丽1*

1(西北农林科技大学信息工程学院 陕西 杨凌 712100)2(西北农林科技大学机械与电子工程学院 陕西 杨凌 712100)

提出一种三维点云模型的去噪光滑算法。该算法根据密度滤波和点法矢量信息对离群噪声点进行去除；再利用张量投票算法和数据点的近邻点在其最小二乘平面上投影的分布均匀性检测出模型的边界特征，并对特征实现加强操作；最后，采用双边滤波对模型表面进行光滑。实验表明，该算法能有效地对模型进行去噪光滑处理，且由于对模型边界特征进行了保留与加强，从而避免了模型光滑操作对模型特征造成损害的问题。

三维点云 边界检测 密度滤波

0 引 言

由三维扫描仪所得到的三维点云模型往往带有不同程度的噪声点，这对于点云模型的逆向重建有着不小的影响，所以对模型进行去噪光滑处理显得十分重要。

通常三维点云模型的噪声点可分为离群噪声点(大尺度噪声点)和模型表面噪声点(小尺度噪声点)。对这两种噪声的去除方法已经有了很多研究。其中较为典型的是利用聚类对噪声点进行检测。Wang等[1]引入模糊C均值聚类算法，利用模糊C均值聚类算法对噪声点进行光滑。Schall等[2]提出了一种基于聚类的mean-shift去噪方法，将每个数据点都移动到最大相似位置，从而得到光滑的模型表面。刘大峰等[3]提出了一种鲁棒滤波算法，采用核密度估计聚类方法，通过mean-shift迭代将每一个数据点“漂移”到核密度估计函数的局部最大值点，利用该最大值点，可以确定点云的聚类中心和原始曲面，并充分利用了数据点的法向量方向。该算法能够实现快速高效的光顺去噪。

除了聚类算法之外，统计学方法也经常应用到点云模型的去噪算法中，Wetzler等[4]将拉普拉斯算子运用到滤波过程中，该方法能够在去除噪声点的同时，有效地对模型特征进行保留。Jenke等[5]利用贝叶斯统计法消除点云模型的噪声点，也得到了较好的效果。刘辉等[6]在点云数据的垂直方向和水平方向上分别采用比较相邻点夹角大小和相邻点加权平均的方法去除噪声点，再利用最小二乘拟合的方法得到去除噪声点处的三维坐标。Daniels等[7]利用移动最小二乘法(MLS)对三维点云模型进行拟合，能够取不同的权函数以改变拟合曲面的光滑度。

对于点云模型的光滑处理，更为普遍的算法要数高斯滤波算法，而由其衍生出的双边滤波算法在图形图像处理方面更是应用广泛。目前，对于传统的双边滤波和高斯滤波也出现了很多改进算法。范涵奇等[8]提出了一种统一的局部高阶双边滤波算法，该算法引入鲁棒统计理论以获得模型表面的几何特征，优化数据点的法向量，对模型进行高阶双边滤波处理。曹爽等[9]对双边滤波算法进行了改进，先利用邻域点判断数据点是否属于噪声点，然后根据不同尺度的点云集合来确定噪声点与非噪声点的双边滤波因子，实现了基于特征选择的双边滤波去噪方法。唐杰等[10]提出一种基于CUDA的点云光滑方法，利用高斯加权的方法计算数据点的法矢量，并在光滑过程中加入邻近点面积影响因子。Wang等[11]扩展了图像去噪中的non-local技术，提出一种对于采样表面的非局部去噪方法。该方法具有较强的鲁棒性，与双边滤波、均值转移滤波相比，受噪声点的影响较小，有更好的效果。

以上提到的所有方法，对于点云模型的去噪光滑过程都有一定的帮助，但是在模型进行光滑处理的同时，都会对模型的特征造成一定的损害。因此，本文提出一种能够对点云模型特征进行保留和加强的去噪光滑算法。实验结果表明，本文算法能够在去除点云模型两类噪声点的同时，保留和加强模型的边界特征。

1 算法总体描述

针对点云模型不同的两类噪声点，本文采用不同的方法将其去除，且为了避免光滑算法对模型特征的损害，在对点云模型表面进行光滑处理之前，先保留点云模型的特征并将其适当加强，从而可以避免出现“过光滑”的现象。本文算法可分为三个部分：a) 离群噪声点的去除；b) 点云模型特征边界的检测与加强；c) 点云模型的表面光滑。

2 离群噪声点的去除

离群噪声点相对于模型的特征数据点来说，有一个很显著的特点，即离群噪声部分的点云密度通常要小于模型特征部分的点云密度。(如图1所示，右边线圈出的为离群噪声部分；左边线圈出的为模型特征部分)利用这一特点即可分离出离群噪声点。

图1 离群噪声部分与模型特征部分的对比示意图

本文算法利用上述特性，并在此基础上根据点云模型整体的密度信息，实现密度滤波阈值的自动生成，使得算法具有自适应性。再根据数据点的法矢量信息，进一步区分离群噪声点和模型特征点，减少密度滤波对模型特征的损害。

2.1 密度滤波

要计算点云模型某部分的数据点密度，则需要定义一个基本的空间单元，再根据单元中数据点的数量进行密度的计算。在本文中，设点云模型集合为N，点云模型的数据点的总数量为Num，pi={pi|pi∈N,i=1,2,…,Num}，以数据点pi为中心，建立以d为半径的空间包围球SV(如图2所示)，搜索得到该包围球SV内的数据点数量Pnum。设一密度阈值为dv，若：

dv>Pnum/d

(1)

则将点pi作为离群噪声点的备选点。

图2 空间包围球SV示意图

上述计算方法虽然简单，但是，不同的点云模型，其数据点坐标值之间往往相差较大，所以使得空间包围球SV的半径d值变得不好选择。针对此问题，本文根据模型总体的密度信息计算得到d的值。

利用模型的点云坐标信息，可以得到模型的空间最小包围立方体V，设该立方体V的边长为l，令：

d=0.1×l

(2)

本文提出一个“满密度”的概念，如图2所示，搜索点pi的n个最邻近点，若n个邻近点均在以d为半径的包围球内，则称点pi为“满密度”点。计算点云模型中的“满密度”点的个数，设为CNum，若：

CNum>rate×Num

(3)

则令：

d=dp×d

(4)

其中，rate与dp均为比例系数，取0～1。重复上述式(3)、式(4)的计算，直到“满密度”点的个数CNum不满足式(3)，此时d的值即为该模型包围球SV的适宜半径值。在上述计算过程中，比例系数rate表示直接被认定为模型特征点的数量与模型数据点总数量的比值，直接被认定为特征点的数据点不再进行式(1)的判断，所以式(3)的意义在于控制密度滤波的滤波程度。比例系数dp表示每次半径d缩小的程度，当半径d缩小，即数据点的包围球SV缩小时，在其包围球中能够搜索到的数据点则减少，从而“满密度点”的数量也会减少。重复上述计算，即可得到要求的滤波程度，以及合适的球半径d值。

上述的密度滤波的算法过程可以总结为：a) 利用式(2)得出球半径d的初始值；b) 设定数据点pi的邻近点搜索个数n，搜索其n个邻近点，检测是否均在其以d为半径的包围球内，由此得出模型“满密度”点的个数CNum；c) 判断CNum是否满足式(3)，若不满足，则可得到半径d的值；若满足，则利用式(4)得出半径d的值，并重复b)、c)的过程。d) 设定密度阈值dv，利用式(1)，判断数据点pi是否为离群噪声点的备选点。

在此算法的步骤d)中，由于不同点云模型所对应的球半径d值之间差异很大，密度阈值dv的值并不方便直接设定。为了缩小dv的取值范围，本文利用点云个数的比较来代替密度之间的直接比较，令：

dv=dnum/d

(5)

则式(1)可替换为：

dnum

(6)

其中dnum为一个自然数，由于Pnum不大于邻近点搜索个数n，所以dnum的取值范围为0～n，由此可以将dnum代替密度阈值dv，使得阈值的取值限定在一个较小范围内。

2.2 密度滤波的改进

2.1节中的算法只考虑了点云模型的密度信息，这样可能会在去噪过程中出现如图3所示的情况。由于图3中的杯子点云模型某些特征部分的点云密度过小，使得在去除了离群噪声点的同时，该部分的特征点也被去除了，损害了模型的特征。

图3 密度滤波对密度过小模型的处理结果

为了避免这种情况的发生，本文算法根据模型数据点的法矢量的方向信息对噪声点和模型特征点进行进一步的判断。由于离群噪声点相对于模型特征点的分布更没有规律性，所以只需要判断数据点法矢量的一致性即可分辨出噪声点和模型特征点。

设定一个方差阈值Sv，为使该阈值的取值缩小到一个较小范围内，先对集合NN中所有的法矢量进行单位化，再利用：

(7)

(8)

即可得到方差值s，其中n为集合NN的元素个数。若：

s

(9)

则表示数据点pi为模型特征点而非离群噪声点。其中Sv的取值范围为0～0.5。

如图4所示，利用上述方法，可以一定程度上避免由于点云模型本身局部特征点密度过小而造成的特征被损害的问题。

图4 增加法矢量方差判断的密度滤波处理结果

3 模型特征边界的检测与加强

三维点云模型的特征提取是三维重建工程中非常重要的一环，目前已经有了很多这方面的研究。Pang等[12]提出了一种基于模型局部表面适应方法，能够有效地检测模型的尖锐特征和平滑特征，并且适用于不同密度特征的检测。Altantsetseg等[13]利用截断的傅里叶级数对特征点进行检测，利用拉普拉斯滤波算法对模型进行光滑操作。该方法能有效地避免噪声点干扰。Mérigot等[14]提出了一种基于泰森多边形的算法，该算法能对模型的分段光滑表面进行主曲率，尖锐特征，法矢量进行有效计算的方法，该方法对于噪声点也有一定的容错性。Fleishman等[15]基于鲁棒的统计模型，对噪声点进行去除。利用移动最小二乘法重建分段光滑平面。该方法能够有效地检测模型的尖锐特征。Park等[16]对张量投票算法进行了改进，提出多尺度张量投票算法，该方法对噪声有一定的抵御作用。

本文采用文献[16]中提到的张量投票算法，并且结合数据点邻近点在其最小二乘平面上的分布均匀性，对模型的边界特征进行检测。

3.1 张量投票算法

每一个三维空间中的点坐标都能表示成一个3×3的对称半正定矩阵，利用文献[16]中对张量投票算法的描述，设模型中的某数据点pi和其邻近点集合N，则pi所对应的张量投票矩阵为Ti，且：

(10)

(11)

(12)

设一阈值ω+，若ωi>ω+，则数据点pi为模型的特征边界点。

利用文献[16]中的方法，如图5所示，可以得到模型的边界特征。但该方法存在一个问题，便是只能够保留模型密闭部分的边界特征，模型非密闭部分的边界特征无法取得。

图5 张量投票算法对模型边界特征的提取效果图

3.2 点云模型非密闭部分边界特征的检测

针对张量投票算法只能保留模型非密闭部分边界特征的缺陷，本文根据数据点的邻近点在其最小二乘平面上的投影分布均匀性，判断数据点是否为模型非密闭部分的边界特征点。

点云模型非密闭部分的边界点与非边界点在其最小二乘平面上的投影分布有着较为明显的区别，如图6所示。边界点的近邻点通常分布不均匀，而非边界点的近邻点分布较为均匀。利用这一分布上的区别，可以区分模型非密闭部分的边界点和非边界点。

图6 点云模型非密闭部分边界点与非边界点在其最小二乘平面上的投影分布图

|bNum-aNum|/n>thre

(13)

则表示数据点pi为边界点，否则其为非边界点。其中thre为一大于0的比例系数，可以控制边界保留的程度。

如图7所示，利用该方法，可以得到点云模型非密闭部分的边界特征。

图7 模型非密闭部分边界特征的提取效果图

如图8所示，将该方法与3.1节中的张量投票算法相结合，即可得到点云模型的所有边界特征，包括其密闭部分边界特征和非密闭部分边界特征。

图8 模型综合边界特征的提取效果图

3.3 特征边界的加强

获取点云模型的边界特征之后，为了提高后期模型重建工作的精确性，常常需要对点云模型的特征边界进行加强操作。本文采用简单的插点法对模型的特征简介进行加强，即在某特征点与其最近特征点中间插入新的数据点。如图9所示，此方法虽然简单，但可能会引起误差点的增多。

图9 特征边界加强效果图

因此本算法规定，只有当两特征点之间的距离小于空间包围球SV的半径值d时，才进行插点操作。结果如图10所示。可以一定程度上解决误差点增多的问题。

图10 带判断的特征边界加强效果图

4 模型表面的光滑处理

对于点云模型表面的光滑处理，在上文中已经提到了很多，虽然其对模型均有损害，可能产生“过光滑”现象，但是由于本文算法保留了模型的边界特征，所以像均值滤波、中值滤波、高斯滤波、双边滤波等方法，均可以运用到本方法中，对模型表面进行光滑处理，且不会对模型的特征边界造成损害。

本文采用双边滤波对点云模型表面进行光滑处理。双边滤波算法具有非迭代、局部、实现简单等特点，利用文献[17]：

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

其中，N(pi)表示数据点pi的邻近点集合，pj为数据点pi的邻近点，k为邻近搜索数据点个数，n为模型数据点总数，l为用户自定义阈值，取值范围一般为{1/16 1/8 1/4 1/2 1 2 4 8 16}[18]。利用上述方法可以快速确定双边滤波算法中σc和σs两参数的值。

5 实验结果

本文所有算法均在IntelCOREi5-3210M、2.50GHz处理器，4.00GB内存的环境下实现和运行。

如图11和图12分别为规则模型和非规则模型的离群噪声点去除效果图，表1中的零件模型与玉米叶模型所对应的数据分别为该模型去噪处理时所涉及到阈值的值，dnum为2.1节中提到的自然数，所有实验中邻近搜索点数n均为10，比例系数rate为0.5。由处理结果可知，本文提出的离群去噪算法对于这两类模型的离群噪声的去除都有很好的效果。

图11 规则模型的离群去噪处理结果示意图

图12 不规则模型的离群去噪处理结果

模型号dnum零件模型3玉米叶模型5花瓣模型13

如图13中的花瓣模型为带有大片连续噪声的不规则模型。其中(b)为dnum等于1时的离群去噪结果，可以看出，此时的处理结果中还带有部分的噪声点；(c)为dnum等于3时的结果，此时的花瓣模型中离群噪声点已经全部去除。由此可见，对于带有大片连续噪声模型噪声点的去除可以通过调整dnum的值，以达到满意的处理效果。

图13 不规则模型的连续离群噪声点去噪处理结果

因此，阈值dnum对于带有大片连续噪声的不规则模型的处理结果影响较大，可以利用它调整不同模型的离群去噪程度。

图14为本文算法对于带有两种噪声点(离群噪声点和模型表面噪声点)的模型的总体处理结果，以及文献[17]的处理结果。由图14(a)和(b)对比可知，算法对模型的离群噪声点有很好的去除效果；该人头模型的主要特征为人头的五官部分，由(c)和(d)的结果可知，算法对其特征部分进行了较好的保留；由(e)和(b)的处理结果可知，算法对模型模型的表面进行了良好的光滑处理。由(e)和(f)对比可知，两种方法都能够较好地对模型的离群噪声点进行去除和模型表面进行光滑。综上所述，本文算法对于这两种噪声点都有很好的去除作用。

图14 本文算法总体处理结果

图15中(a)为本文算法对人头模型去噪光滑处理后，表面生成的结果，(b)为文献[17]的处理结果。本文算法由于进行了模型特征边界的保留，因此，所得到的结果保留了更多模型原本的特征；而文献[17]仅对离群噪声点进行去除和模型表面进行光滑操作，因此，模型容易出现过度光滑的现象。

图15 本算法与文献[17]处理结果对比

6 结 语

本文提出了一种新的针对三维点云模型的去噪光滑算法。该算法分为三个部分，其中具有自适应性的离群去噪算法对于模型的离群噪声点有很好的去除效果；模型边界特征的保留算法能够同时保留模型密闭部分和非密闭部分的特征；对双边滤波算法的阈值选取进行了一定的改进，能够更加容易获取合适的阈值。算法在去除点云模型两种噪声点的同时，能较好地保留模型的边界特征，一定程度上解决双边滤波、高斯滤波、均值滤波等光滑算法对模型产生“过光滑”的问题。本算法适用于各类三维点云模型，且均能达到较好的效果。

由于文中边界保留方法的抗噪性还不够强，当模型表面的噪声点过多时，会影响本文算法对模型边界特征的提取结果，这个部分将作为后续工作中研究的重点。

[1]WangL,YuanB,MiaoZ.EllipsoidCriterionandFuzzyCMeansAlgorithmfor3DPointCloudDataDenoising[C]//Proceedingsofthe2008CongressonImageandSignalProcessing,2008,2:361-365.

[2]SchallO,BelyaevA,SeidelHP.RobustFilteringofNoisyScatteredPointData[C]//ProceedingsoftheSecondEurographics/IEEEVGTCConferenceonPoint-BasedGraphics,2005:71-77.

[3] 刘大峰,廖文和,戴宁,等.散乱点云去噪算法的研究与实现[J].东南大学学报(自然科学版),2007,37(6):1108-1112.

[4]WetzlerA,RosmanG,KimmelR.Patch-spaceBeltramidenoisingof3Dpointclouds[C]//2012IEEE27thConventionofElectricalandElectronicsEngineersinIsrael,2012:1-5.

[5]JenkeP,WandM,BokelohM,etal.Bayesianpointcloudreconstruction[J].ComputerGraphicsForum,2006,25(3):379-388.

[6] 刘辉,王伯雄,任怀艺,等.基于三维重建数据的双向点云去噪方法研究[J].电子测量与仪器学报,2013,27(1):1-7.

[7]DanielsJI,HaLK,OchottaT,etal.RobustSmoothFeatureExtractionfromPointClouds[C]//ProceedingsoftheIEEEInternationalConferenceonShapeModelingandApplications,2007:123-136.

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

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

[10] 唐杰,徐波,宫中樑,等.一种基于CUDA的三维点云快速光顺算法[J].系统仿真学报,2012,24(8):1633-1637,1642.

[11]WangR,ChenW,ZhangS,etal.Similarity-baseddenoisingofpoint-sampledsurfaces[J].JournalofZhejiangUniversity-SCIENCEA,2008,9(6):807-815.

[12]PangXF,PangMY,SongZ.ExtractingFeatureCurvesonPointSets[J].InternationalJournalofInformationEngineeringandElectronicBusiness,2011,3(3):1-7.

[13]AltantsetsegE,MurakiY,MatsuyamaK,etal.FeaturelineextractionfromunorganizednoisypointcloudsusingtruncatedFourierseries[J].TheVisualComputer,2013,29(6):617-626.

[14]MérigotQ,OvsjanikovM,GuibasL.RobustVoronoi-basedCurvatureandFeatureEstimation[C]//2009SIAM/ACMJointConferenceonGeometricandPhysicalModeling,2009:1-12.

[15]FleishmanS,Cohen-OrD,SilvaCT.RobustMovingLeast-squaresFittingwithSharpFeatures[J].ACMTransactionsonGraphics(TOG),2005,24(3):544-552.

[16]ParkMK,LeeSJ,LeeKH.Multi-scaletensorvotingforfeatureextractionfromunstructuredpointclouds[J].GraphicalModels,2012,74(4):197-208.

[17] 王丽辉,袁保宗.鲁棒的模糊C均值和点云双边滤波去噪[J].北京交通大学学报,2008,32(2):18-21.

[18] 张毅,刘旭敏,隋颖,等.基于k-近邻点云去噪算法的改进与研究[J].计算机应用,2009,29(4):1011-1014.

RESEARCH ON A NEW DENOISING ALGORITHM FOR 3D POINT CLOUD MODEL

Liao Changsu1He Dongjian2Wang Meili1*

1(CollegeofInformationEngineering,NorthwestA&FUniversity,Yangling712100,Shaanxi,China)2(MechanicalandElectronicEngineering,NorthwestA&FUniversity,Yangling712100,Shaanxi,China)

This paper proposes a denoising algorithm for 3D cloud model. The algorithm removes outlier noise point based on density filtering and vector information of points. Then, the boundary feature of the model is detected by the tensor voting algorithm and the uniformity of the projection of the nearest neighbors of the data points on the least squares plane, and the features can be enhanced. Finally, the model surface is smoothed by bilateral filtering. The experimental results show that the algorithm can effectively smooth the model and preserve and strengthen the boundary feature of the model to avoid the problem that the smooth operation of the model damages the model features.

3D point cloud Boundary detection Density filtering

2016-01-27。国家高技术研究发展计划项目(2013AA102304)子课题；第56批中国博士后基金项目。廖昌粟，本科生，主研领域：图形图像处理。何东健，教授。王美丽，副教授。

TP317.4

A

10.3969/j.issn.1000-386x.2017.04.048