一种聚类与滤波融合的点云去噪平滑方法

牛晓静　王美丽　何东健

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



一种聚类与滤波融合的点云去噪平滑方法

牛晓静1王美丽1何东健2*

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

针对采集的原始三维点云数据存在噪声、表面不光滑不利于后期三维重建的问题，提出一种自适应密度聚类与双边滤波融合的三维点云去噪平滑方法。该方法首先对点云模型进行自适应密度聚类分析，根据聚类结果删除模型中的噪声点；然后再计算采样点的k邻域，并求得利用k邻域构造采样点所在平面的法矢，进而得到双边滤波因子，以对点云模型进行平滑。实验结果表明，该算法能有效识别并去除噪声，并对点云模型进行平滑，同时还能保持原始模型的特征信息。

点云去噪自适应密度聚类k邻域双边滤波特征保持

0　引　言

虚拟现实技术是当前及将来影响人们生活的重要技术之一。随着计算机图形图像技术的发展，虚拟模型在生活的各个方面有着广阔的应用前景。通过三维扫描仪等设备获得真实世界作物的表面三维点云是一种普遍的三维重建方式。现有的三维扫描仪由于仪器本身的适应性、人为因素、环境因素和测量方法等的影响，采集的三维点云中总包含噪声，不能精确地表现被测作物的表面信息。三维点云中噪声点的存在将影响后续特征点的提取精度和重建三维模型的质量，导致重构曲线、曲面不光滑，故研究保留尖锐特征的三维点云去噪方法对提高建模质量具有重要的意义。

1　相关工作

近年来，国内外学者们提出了多种点云模型的光顺去噪算法，这些算法大多是来自图像去噪和网格光顺算法[1]，且主要与点云的排列形式密切相关[2]。罗才华等[3]讨论了基于八叉树模型的点云数据预处理方法，该方法对点云数据处理有较好的灵活性和适应性。黄文明等[4]采用均匀栅格法划分点云空间，进而进行散乱点云的简化。该方法不仅能够充分保留点云中的几何特征，而且速度快；但随着数据的增大，不能保持细小特征的完整性。Xiao等[5]利用kd-tree表示空间点云的拓扑关系进行点云简化，该方法有较高的运行效率，且可避免漏洞。上述方法证明这三种拓扑关系对点云处理是有效的。本文采用八叉树构建点云之间的拓扑关系，以提高点云去噪平滑的效率。

在基于三角网格模型的降噪算法研究方面，Yu等[6]提出一种两阶段特征保持网格去噪框架。该方法可以在很好保持曲面网格特征的前提下取出噪声，但不能精确处理容易被噪声影响的细小特征。尹旺中等人[7]对模型中每个三角片的每个顶点分别求出其一邻域内所有三角片与当前三角片法矢夹角的变化率，根据该变化率用拉普拉斯算子对三角片法矢进行调整，进而调整模型中各顶点位置。由于该方法是各向同性的，故存在重要特征模糊现象。张三元等[8]和Zheng等[9]将各向异性思想推广到三角网格上，提出了各向异性网格光顺算法。这些算法虽然能够保持几何特征，但通常采用高阶几何流，算法复杂度较高，有些情况下还会造成网格模型的变形和扭曲。Dutta等[10]提出一种改进的三维几何双边滤波方法，该算法可以在去除噪声的同时保持对象的细节特征，并且克服了前人方法降低点云密度的缺点。但是该方法不能简单地推广到点云模型上。在直接针对点云数据的平滑处理方面，刘大峰等[11]提出一种快速去除散乱点云数据表面噪声和离群点的鲁棒滤波算法，但当每一个点都独立收敛于一个似然函数最大值时，并行问题没有解决。杜小燕等[1]提出一种特征保持点云模型光顺去噪算法，该算法通过调整采样点在法向的位置实现局部的光顺去噪，但是没有涉及到振幅较大的奇异点的自动去除。葛宝臻等[12]提出的基于曲率信息混合分类的特征保持点云平滑算法将平面投影与双边滤波算法相结合，采用主成分分析法对点云的局部曲率特性进行评价，可用于高密度点云数据的去噪；但该方法计算效率低。王丽辉等[13]将噪声分为大尺度和小尺度分步处理，分别用模糊C均值聚类算法和双边滤波器对大、小尺度噪声进行光顺。该方法计算效率较高，且避免了过光顺问题，但对噪声敏感会降低聚类结果的质量。Park等人[14]通过近似拟合二次曲面实现点云的去噪，该方法依赖于鲁棒的法向估计和基于投影的局部曲率，可很好地保持特征，效率也比较高；但是法向估计由于偏差的干扰可能会不准确。

针对上述问题，本文提出一种自适应密度聚类和双边滤波融合的三维点云数据去噪光滑算法。该算法对噪声不敏感，可以去除任意形状、大小的噪声，同时也可在保持原始模型特征信息的前提下对模型进行平滑。

2　算法描述

2.1自适应密度聚类算法

2.1.1密度聚类算法

在获取的点云数据中，除了目标点云外，还有一些分布比较稀疏或孤立的噪声点。而聚类算法可以实现类内个体之间具有较大的相似性，类间个体间具有较大的相异性。在聚类算法中，选择合适的阈值就可以将目标点云分离，因此可以利用聚类方法进行噪声的去除。基于密度的聚类算法将类定义为密度相连的点的最大集合，它本身对噪声不敏感，能发现任意形状、大小的类簇。该算法不依据距离进行分类，克服了基于距离判别准则只能发现“类圆形”聚类的限制[15]。故本文利用密度聚类方法对三维点云进行聚类，从而在聚类结果中选择出目标点云主体，进而实现噪声的去除。

密度聚类的步骤如下(如图1所示)：

1) 给定初始半径e和最小邻域数MinPts，并赋类号ClusterID为1；

2) 从待分类集合D中读出一个未标记的对象P，并查找D中关于e和MinPts的从P密度可达的所有对象；

3) 若P是核心对象(P的e邻域内至少包含MinPts个点)，则对象P的类号赋值为ClusterID；如果P是一个边界点(P不是核心点，但落在某个核心点的e邻域内)，则对象P的类号赋值为0，并转步骤2)；

4) 搜索所有与对象P密度可达的对象，将其类号赋值为ClusterID；从对象P密度可达的对象开始继续搜索，直至无对象为止，将所有密度可达的对象赋值为ClusterID，ClusterID加1，并转步骤2)；

5) 若待分类集合D中有未标记的对象，转步骤2)；

6) 判断能否分离目标点云，若能分离，则停止聚类；否则根据需要重新选择新的初始半径e和最小邻域数MinPts进行聚类。

图1　自适应密度聚类算法流程图

2.1.2自适应参数调整

在上述密度聚类步骤中，初始半径e和最小邻域数MinPts均为自定义参数。参数初始值设置好后，需要根据聚类效果不断调整这两个参数以获得最好的聚类效果，比较耗时。为了解决这一问题，本文提出一种自适应参数计算方法。

首先，根据式(1)计算任意两点之间的欧式距离。

(1)

然后根据式(2)-式(3)求得dist(i,j)的最大值maxdist和最小值mindist，进而根据式(4)求得距离间隔distrange。

maxdist=Max{dist(i,j)|0≤i

(2)

mindist=Min{dist(i,j)|0≤i

(3)

distrange=maxdist-mindist

(4)

其中，n表示点的数目。

将距离间隔等距分为十段，统计dist(i,j)在每段范围内的频数 ，初始半径e的值即为erang所在分段的中值。erang的计算公式如式(5)所示。

erang=Max{pk|0≤k<10}

(5)

初始半径e确定后，根据e逐步增大最小邻域数目MinPts，计算邻域超过最小邻域数目的点的数目pNum(计算公式如式(7)所示)。随着最小邻域数目的增加，pNum会逐渐减少并趋于稳定，选择拐点所在的最小邻域数目作为MinPts。其中，对于任意给定点p的邻域点数目pNumi的计算如式(6)所示。

pNumi=count{dist(i,j)

(6)

那么：

pNum=count{pNumi≥MinPts|0≤i

(7)

通过该方法可以实现初始半径和最小邻域数的自动选择，进而避免这两个参数的反复设置。

2.2双边滤波方法

利用自适应密度聚类方法去除噪声后，模型的表面仍然不是很光滑。为了保证后期三维重建效果，本文用双边滤波方法对点云模型进行平滑。该方法的关键是法矢的估计和双边滤波因子的计算。

2.2.1法矢估计

设点云模型中所有点的集合为cloud，则与点p距离最近的k个点为p的k邻域，记为N(p)，那么点云k近邻的搜索就转换为八叉树近邻的搜索。根据点云中每个点的空间位置，通过深度优先遍历找到每个点所在的叶子节点，通过搜索相邻节点获得每个点的k近邻。然后通过最小二乘法[16-18]在N(p)内构造点p在N(p)上的切平面，记作T(p)。对于点云中的任意一点，其方向矢量等价于该点与其邻域的最小二乘拟合平面的法向量[19]，所以T(p)的单位法矢即为点p处的单位法矢。

2.2.2双边滤波因子

双边滤波方法是一种保边去噪的方法，首先用于消除图像噪声。在本文算法中，将双边滤波方法[20]用于三维点云数据的平滑中，在保持模型边界的前提下，对模型表面进行平滑。

定义：

(8)

(9)

式中：N(qi)—数据点qi的邻域。用标准高斯滤波进行平滑滤波，定义为：

(10)

特征保持权重函数类似于平滑滤波，定义为：

(11)

2.3自适应密度聚类与双边滤波融合方法

将双边滤波用于经自适应密度聚类算法去噪后新数据点的平滑，算法步骤如下：

1) 对于每一个数据点qi，求出它的m个近邻点kij，j=1,2,…,m;

2) 对于每个邻近点，求出平滑滤波函数的参数x=‖qi-kij‖和特征保持权重函数的参数y=，其中x为点qi到邻近点kij的距离，y为点qi与邻近点的距离向量qi-kij与该点法向的内积；

3) 按照式(10)和式(11)计算出平滑滤波函数Wc(x)和特征保持权重函数Ws(y)；

4) 将Wc(x)和Ws(y)代入式(9)，计算出双边滤波因子；

5) 根据式(8)计算得到滤波后的新数据点；

6) 所有数据点均更新后，程序结束。

双边滤波方法在平滑模型时考虑了邻域点的影响，避免了过平滑现象的发生。

3　实验结果及分析

为验证本文算法的有效性，在Win 7平台(CPU主频3.20 GHz，内存8 GB)上，基于Visual Studio 2010和OpenGL实现本文算法。使用西红柿、玉米植株、树和小麦点云模型对本文算法进行验证。本文使用的模型均由scanstation 2激光扫描仪获得。下述实验中，k邻域的数目均为7。

在实验过程中，我们还对Laplace平滑算法和本文算法进行了比较测试，主要在平滑效果上进行比较。在用scanstation 2扫描的点云模型中存在很多噪声点，如图2中(a)所示的西红柿原始点云模型。(b)是经过本文算法去噪平滑后的点云效果(与原图相比经过旋转)，(c)是使用本文算法去噪后，再使用Laplace平滑方法获得的效果，(d)-(f)分别是西红柿点云去噪前、本文算法去噪平滑后和Laplace平滑后的重建效果。

图2　西红柿点云模型处理效果

使用本文提出的方法对玉米植株点云(如图3所示)进行去噪光滑的效果如图4所示。

图3　原始玉米点云　　图4　玉米点云本文算法去噪光滑效果

图5-图7分别表示玉米原始点云、本文算法去噪平滑后和Laplace平滑后点云的重建效果和局部放大效果。

图5　原始玉米植株点云重建效果和局部放大效果

图6　玉米点云本文算法去噪光滑后的重建效果和局部放大效果

图7　Laplace平滑后重建效果和局部放大效果

在图2的(e)和(f)中，重建效果的差距并不明显。但是从图5-图7的局部放大效果图中可以发现，未经去噪处理的点云模型中由于噪声点的存在，使重建的表面不光滑，部分有凸起。点云去噪后，经Laplace平滑方法处理过的点云模型中仍然存在部分小的凸起，表面也不是很光滑；而经过本文算法去噪光滑的模型，重建效果要比Laplace平滑后的重建效果好。

利用本文提出的方法对树和小麦的点云模型进行处理的效果分别如图8和图9所示。

图8　树点云模型处理效果

图9　小麦点云模型处理效果

表1为各模型去噪前后的点数和去噪平滑所用时间。在双边滤波平滑过程中，虽然避免了迭代计算，但是随着数据量的增大，消耗时间仍较长。

表1　各点云模型去噪和平滑时间

4　结　语

本文提出了一种自适应密度聚类与双边滤波融合的三维点云数据去噪平滑算法。通过密度聚类算法，可以有效去除模型中的噪声点，而通过双边滤波方法可以实现点云平滑效果。本文提出的方法不需要迭代计算。实验结果表明，本文算法可以在保持模型特征的前提下有效去除三维点云数据中的噪声，为后期三维点云分割及重建效果与质量提供基础。目前本文算法在近邻搜索中耗时比较长，下一步的工作需要结合GPU编程进一步提高算法的效率。

[1] 杜小燕,姜晓峰,郝传刚,等.点云模型的双边滤波去噪算法[J].计算机应用与软件,2010,27(7):245-246,264.

[2] 樊宇,王宇楠.三维激光扫描点云数据预处理技术研究[J].科技创新导报,2011(32):27-28.

[3] 罗才华,周燕.基于八叉树模型的三维点云数据预处理研究[J].福建电脑,2008,24(12):81-82.

[4] 黄文明,彭希为,温佩芝,等.保留几何特征的散乱点云简化方法[J].计算机工程与应用,2009,45(28):168-170,186.

[5] Xiao Z X,Huang W M.Kd-tree based non-uniform simplification of 3D point cloud[C]//Genetic and Evolutionary Computing,WGEC’09,3rd International Conference on.IEEE,2009:339-342.

[6] Yu J Z,Wei M Q,Qin J,et al.Feature-preserving mesh denoising via normal guided quadric error metrics[J].Optics and Lasers in Engineering,2014,62:57-68.

[7] 尹旺中,周来水,神会存,等.基于三角片法矢调整的三角网格模型光顺[J].机械科学与技术,2006,25(4):410-414.

[8] 张三元,李强,张引.一种保持特征的三角网格去噪方法[J].中国科技论文在线,2010,5(2):129-132.

[9] Zheng Y Y,Fu H B,Au O K,et al.Bilateral normal filtering for mesh denoising[J].Visualization and Computer Graphics,IEEE Transactions on,2011,17(10):1521-1530.

[10] Dutta S,Banerjee S,Biswas P K,et al.Mesh denoising by improved 3D geometric bilateral filter[C]//Computer Vision,Pattern Recognition,Image Processing and Graphics (NCVPRIPG),2013 Fourth National Conference on.IEEE,2013:1-4.

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

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

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

[14] Park M K,Lee S J,Jang I Y,et al.Feature-aware filtering for point-set surface denoising[J].Computers and Graphics,2013,37(6):589-595.

[15] 张巧英,陈浩,朱爽.密度聚类算法在连续分布点云去噪中的应用[J].地理空间信息,2011,9(6):101-104.

[16] 刘彬,李梦瑞,林洪彬,等.基于正交投影约束的点模型去噪[J].计算机工程,2012,38(20):264-267,271.

[17] Zhang L,Gu T Q,Zhao J,et al.An adaptive moving total least squares method for curve fitting[J].Measurement,2014,49:107-112.

[18] 许斌,李忠科,吕培军,等.基于特征的点云精确配准算法[J].计算机应用与软件,2013,30(11):112-114,122.

[19] 杨现辉,王惠南.ICP算法在3D点云配准中的应用研究[J].计算机仿真,2010,27(8):235-238.

[20] 孙正林.三维激光扫描点云数据滤波方法研究[D].长沙:中南大学,2011.

A POINT CLOUD DENOISING AND SMOOTHING METHOD BASED ON FUSION OF CLUSTERING AND FILTERING

Niu Xiaojing1Wang Meili1He Dongjian2*

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

The original three-dimensional point cloud data collected has the problems of noise and unsmooth surface which is not conductive to three-dimensional post-reconstruction. In view of this, this paper presents a three-dimensional point cloud denoising and smoothing method, it is based on the fusion of adaptive density clustering algorithm and bilateral filtering. First, the method applies adaptive density clustering analysis on the point cloud model, and erases the noise points in the model according to clustering result. Then, it calculates the k neighbourhood of sampling point, and calculates the normal vector of the plane where the k neighbourhood is used to construct sampling points, and further obtains the bilateral filtering factor so as to smooth the point cloud model. Experimental results show that the proposed algorithm can identify and remove noise effectively and smoothes the point cloud model. At the same time, it can well keep characteristic information of the original model.

Point cloud denoisingAdaptive density clusteringK neighbourhoodBilateral filteringFeature preserving

2015-06-18。国家高技术研究发展计划项目(2013AA 102304)；第56批中国博士后科学基金项目(2014M562457)。牛晓静，硕士生，主研领域：计算机图形学，图像处理。王美丽，讲师。何东健，教授。

TP3

A

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