基于法矢修正的点云数据去噪平滑算法

薛萍　姚娟　邹学洲　王宏民

摘要：逆向工程数据采集点云数据的离群点和噪声点的存在，直接影响数据的多视图拼合，特征提取，数据精简以及曲面重构的质量。在对双边滤波和三边滤波算法的研究的基础上，提出了一种基于法矢修正的点云数据去噪平滑的算法。对于噪声点通过加权协方差矩阵估算点云邻域内几何特征，将具有相似几何特征的点限制在法向量相似的区域，在相似邻域内的采样点法矢和位置分别进行保特征的三边滤波。改进后的算法能够有效地滤出点云数据中的离群点和噪声点，同时保证了点云数据的尖锐及边缘特征，取得良好的去噪效果。

关键词：

点云数据；去噪平滑；加权协方差矩阵；三边滤波；法矢修正

DOI：10.15938/j.jhust.2018.05.015

中图分类号： TP3919

文献标志码： A

文章编号： 1007-2683（2018）05-0086-06

Abstract：The presence of outliers and noise points in the cloud data of the reverse engineering data collection directly affects the multviews combination of the data， feature extraction， data reduction and the quality of surface reconstruction Based on the research of bilateral filtering and trilateration filtering algorithm， this paper presents an algorithm of denoising and smoothing of point cloud data based on normal vector correction Firstly， the local neighborhood of the point cloud data is constructed， and the noise points of the scattered data collected by the data acquisition system are classified and processed For outliers in the point cloud data， mathematical statistics analysis is used to filter out the points whose KNN is lower than the threshold The points with similar geometric characteristics are restricted to the regions where the normal vectors are similar， and the normal vectors and positions of the samples in the similar neighborhoods are triangulated The improved algorithm can effectively filter the outliers and noise points in the point cloud data， and ensure the sharp and edge features of the point cloud data and obtain good denoising effect

Keywords：point cloud data； denoising smoothing； weighted covariance matrix； trilateration filtering； normal vector correction

0引言

逆向工程中對实体表面的数据获取[1]方式分为接触式测量和非接触式测量。随着三维测量技术的不断发展和完善，各种各样的三维测量设备很容易对物体表面的数据进行采集，同时得到的测量数据不可避免的存在着噪声信号，这些测量的噪声信号受到测量物体的形状，物体的材料，光线或者其他环境因素的影响。这些测量误差统称为噪声点，与此同时点云数据[2]中也存在离主体点云较远的离群点。由于点云数据的离群点和噪声点的存在，直接影响数据的多视图拼合，特征提取，数据精简以及曲面重构的质量，因此需要对噪声进行滤波处理。在滤除噪声点的同时要注意滤波过度的问题，保持点云的特征点不被大量滤除，以免影响曲面重构[3]后模型的质量，所以点云数据的去噪和平滑显得尤为重要。首先对噪声的来源和产生噪声的原因进行分析，有利于对噪声的研究，发现噪声点的特征，然后根据噪声和有效点云的区别进行有效的点云去噪。

目前点云数据去噪的方法主要有：一是将散乱点云数据网格化，对网格数据进行去噪处理；二是对散乱点云数据直接去噪处理。拉普拉斯（Laplace）去噪[4]是一种常用而且算法实现又简单的散乱点云数据去噪方法，该算法首先对点云数据中的每个数据点进行拉普拉斯算子，并将其进行多次迭代，将噪声点调整到附近邻域位置，从而达到去噪光顺的目的。但是这种方法存在很大的问题，就是经过多次迭代后对于网格分布不均匀的点云区域会产生原来网格的大面积变形，严重影响曲面重构的质量。双边滤波去噪算法是由图像处理算法双边滤波算法发展而来的点云数据去噪算法，该算法能较好地保留数据的局部特征，但是也存在一定的问题，针对较大的噪声的处理上就会出现过

光顺的现象，使重构后的模型显得模糊失真。本文所述算法的思想是，采用数理统计的方法，滤出点云数据中的离群点，去除K近邻点低于设定阈值的点，通过加权协方差矩阵，分析估算点云邻域内的几何特征[5]，将具有相似几何特征的点限制在法向量相似的区域，在相似邻域内的采样点法矢和位置分别进行保特征的三边滤波。

1点云数据去噪平滑方法

11八叉树法空间划分及K邻域数据搜索

建立点云数据的最小包围立方体，该最小立方体称为八叉树[6]的根节点，然后把根节点划分为8个边长相同的子立方体，被划分的8个子立方体称为根节点的子节点，包含点云数据的子节点称为“黑体”，不包含点云数据的子节点称为“白体”。当“黑体”的边长大于预先设定的最小划分边长Lmin时，以此类推对子节点进行划分，直至被划分的子立方体的边长小于或等于预先设定的最小划分边长Lmin，划分结束。

对点云数据进行八叉树划分后，利用0-7的八进制对子立方体进行数据编码[7]，每个子立方体都可以用一个唯一的八进制码唯一表示：

Q=qn-18n-1+qn-28n-2+…+qk8k+…+q181+q080（1）

式（1）中qi为八进制数编码，qi∈[0，7]，i∈[0，n-1]。

其中qi/22表示qi/2取整，qi/42表示qi/4取整，n表示分层数。

由八叉树法空间划分规则和子节点编码方式可以知道，当给定子节点在空间中的坐标位置，可以求出其节点编码，同样知道子节点的编码，可以求出其在根节点中的位置坐标。

12离群点滤除

对点云数据离群点的滤除在点云数据处理中是十分重要的，将直接影响到点云分割、特征提取、精简等一系列的后续处理过程。

设点云的集合P={pi|i∈1，2…，pi∈R3}，通过建立点云的拓扑关系对点云集合中的任意一个点pi，其K邻域集合pij={pi1，pi2，pi3，…}，令其为Nb（pi），对点云数据中的离群点采用数理统计方法滤出，即基于数据点K邻域的距离特征滤出离群点。对点云数据中的任意采样点pi计算K邻域[8]的平均距离并记为di，然后对整个点云数据集合P中的点云计算全局距离平均值uN和标准方差σN，K邻域的平均距离在全局距离之外的点视为离群点，并把该点从点云数据中滤除。滤出离群点后的点云数据可用集合表示为：

P*={p*i∈P|（uN-ασN）≤di*≤（uN+ασN）}

滤除离群点的过程如下：

1）八叉树空间拓扑关系的建立及对数据点云中的任意数据点pi的K邻域搜索，K邻域点集合Nb（pi）；

2）对于点云数据中的任意采样点pi计算K邻域的平均距离并记为di

di=1k∑kj=1‖pi-pij‖（5）

3）对于整个点云集合

P={pi|i∈1，2…，pi∈R3}计算全局距离平均值uN和标准方差σN；

uN=1N∑Ni=1di，σN2=1N∑Ni=1（di-uN）2（6）

4）通过K邻域平均距离与uN±ασN的比较，其中α为标准差的倍数，满足diuN+ασN的数据点pi是离群点，将该点从点云数据中滤除[9]。其中α取值为1。

13法向量估计

滤除后的点云数据[10]就是不包含离群点的点云数据，然后就可以进行去噪平滑的算法，采用加权协方差矩阵的方法进行几何特征的计算。点云集合中的任意一个点pi，通过K近邻搜索得到其K邻域点数据集合，通过最小二乘法拟合平面L，平面L满足pi的邻近点到该平面的距离之和值最小。这样的平面L可用数学公式表示为：

L（n，d）=arg min（n，d）∑ki=1（n·pi-d）2（7）

式（7）中，n表示pi的K近邻点拟合平面的法向量，d表示坐标原点到L（n，d）的距离。通过分析式（7）得出L经过数据点K近邻点的质心pi，构造协方差矩阵C：由L的公式可以通过分析得出L经过数据点的K近邻点的质心pi，构造协方差矩阵C：

C=1k∑kj=1（pij-pi）·（pij-pi）T，

C·el=λl·el l∈{0，1，12}（8）

式（8）中k为通过K近邻搜索得到其K邻域点数据个数，pi是L经过数据点的K近邻点的质心，λl为协方差矩阵的特征值，el为特征值相对应的特征向量。设特征值λ0<λ1<λ2，pi处的法向量可以用特征向量的值来表示，即ni=el。因此可以用协方差矩阵的特征值来估计采样点的曲面尖锐程度。由Pauly定义的曲面可由点pi处的曲率表示为：

ρi=λ0λ0+λ1+λ2（9）

式（9）中，由于λ0<λ1<λ2，因此0<ρi<1/3，通过这样的方法，很容易估算出点云中任意一点pi处的曲率，但是对于尖锐特征区域的点云数据，这样的估算方法显得不那么准确，可通过加权来改善。

14采样点去噪平滑

设平滑采样点后的坐标的位置为pi′，可表示为：

pi′=pi+ni′f2（pi）∑pij∈Nb（pi）G1G3（1+hi）（10）

G3=e-2/2σ23ni′·nij′>Ti′

0ni′·nij′

式（11）中σ3是一個邻域点法相与采样点法相之差对采样点的影响因子，Ti′为法相角度阈值。G3是一个与采样点、采样点邻域内点的法向量、σ3相关的特征保持权重函数。由式（11）可知，G3反映了向量pi-pij在ni上的投影长度，进一步地反映了采样点在其邻域的切平面的收敛性。G3越小，说明近邻点集中与切平面存在，这样的设定是为了保持这些点对采样点特征的影响较大。对G3这样调整能够使采样点的噪声[11]偏移限制在法向投影的可控范围内，即邻域点法相投影的最大投影距离和最小投影距离之间，不引入新的噪声点。

2对初始法向量的改进和修正

21法向量估计的改进

通过在协方差矩阵中添加加权值，改进后的协方差矩阵可表示为：

C=1k∑kj=1（pij-pi）·（pij-pi）Tφ（‖pij-pi‖/r）（12）

式（12）中φ表示协方差函数的权重函数，r表示pi的K邻域数据的最小包围球的半径。上述协方差矩阵考虑了近邻点的距离对采样点特征的影响[12]，但是在对法向量的计算上并不能够保尖锐特征，需要对协方差矩阵做进一步的改进，调整紧邻点对采样点的影响。改进后的加权协方差矩阵：

C=1k∑kj=1εi（pij-pi）·（pij-pi）T（13）

假设采样点pi到最小二乘法拟合平面L的最大距离为dmax，K邻域搜索的近邻点pij到L的距离为dij，若dijdmax，则把相应的εi=exp（-d2ij/u2）。

这种加权函数的设定，更加能够反映邻域内的点对采样点的影响，距离小于dmax的采样点对采样点的影响较大，设置较大的权重函数，当采样点距离大于dmax时，应用较小的权值函数，这样就能够减小远距离邻域点对采样点的影响，抑制噪声，保留几何特征。

22法矢修正

通过对加权协方差矩阵的权重因子设定不同的权值函数可以抑制一定的噪声，但是当点云数据中的噪声较大時，初始法向量的估计[13]就难以满足要求，因此需要对法矢进一步的修正。考虑双边滤波算法能够在一定的程度上保持特征，但这种特征的保持只考虑了空间域和频域特性，也会存在过光顺的问题。综合考虑散乱点云数据的空间特性、法向量和曲率的三种特性，对初始法向量进行修正，得到保特征的点云数据。

对于数据点云pi，其中包含采样点的空间位置坐标（xi，yi，zi），数据点的采样曲率hi，法向量ni。设修正后的法向量为ni′，法向量的修正公式：

ni′=ni+1f1（pi）∑pij∈Nb（pi）‖ni-nij‖G1G2（1+hi）（14）

G1=e-‖ni-nij‖2/2σ21（15）

G2=e-‖ni-nij‖2/2σ22，ni·nij>Ti′

0，ni·nij

hi=（ρi-ρmax）/（ρmax-ρmin）（17）

式中σ1表示K近邻点对采样点法向量的影响因子，σ2表示K邻域点法向量平均值与当前的采样点的法向量的差值对采样点的影响因子，σ2可以表示为σ2=α（max-min）。G1为空间光顺高斯核函数，它的值由采样点、采样点邻域内的法向量和采样点处的影响因子所决定。G2为特征保持权重函数，当ni·nij>Ti′时其为一个指数函数，值由采样点及其邻域内的法向量之差和空间域和法相域的滤波尺度所决定，其中Ti′为设定的法相角度阈值。当ni·nij

对于法矢修正采样点的去噪能够保持采样点的几何特征[14]，但也可能存在降噪点漂移，需要对降噪点进行稳定。通过位置坐标因子G1、法相投影因子G3和曲率hi对邻域内数据点进行滤波，这样就能够将采样点位置限定在法向量和曲率近似的空间位置内，可以有效地避免降噪点的漂移，沿着新的法相调整降噪点的位置。

3算法流程及实验结果分析

31算法流程

本文同时考虑了采样点与K个紧邻点间的局部平均距离与整个点云采样点间全局平均距离做比较，对离群点有效的滤除，同时又能够保留数据特征。滤除离群点后的点云数据通过加权协方差矩阵的方法进行几何特征的计算，估算出法向量和曲率，通过自适应邻域将邻域点限制在法向量最相似的区域，然后在邻域内对数据点进行法向量，曲率和坐标为特征的三边滤波因子的滤波。基于法矢修正的点云数据去噪平滑算法的流程图如图2所示：

算法的过程如下：

1）点云读入，拓扑划分。点云数据读入，采用八叉树法对点云数据空间划分，直至划分的子节点不包含数据点或者子节点立方体的边长小于最小划分边长Lmin。

2）K邻域搜索。对八叉树划分的子节点进行数据编码，计算数据点在子节点内到临近点的欧式距离，计算点的K邻域，扩大搜索范围到相邻的子节点至完成搜索。

3）离群点去除。点云数据中的离群点滤出，采用数理统计分析技术滤除K近邻点低于设定阈值的点。

4）初始法向量和曲率的估计。通过加权协方差矩阵的方法进行几何特征的计算，估算出法向量和曲率。

5）法矢修正和平滑。以空间位置坐标，曲率以及法向量为三边滤波因子，对采样点数据进行法向量修正，调整采样点的位置。法矢修正平滑后的点云数据能够保持点云数据的尖锐特征，模型的平滑。

32实验结果分析

321离群点滤除结果分析

通过对点云数据建立的拓扑关系和K邻域搜索的方法，K邻域的搜索直接影响到邻域点的最小二乘法拟合的切平面L（n，d），K值的选取太小，会使搜索时间大大减小，但是不能够保证光顺。当K的选择过大时，K邻域搜索的时间过长，同时也不能保证光顺。通过实验验证，K值的大小在15～20之间时能够有很好的效果，本文选取k=18。在初始法向量的估计过程中点，采样点pi到最小二乘法拟合平面L的最大距离dmax的选取经过多次试验，把其设定为K邻域点到邻域点拟合平面的距离的平均值。σ1的值取K邻域的包围点球体的半径，σ2的值通过试验比较控制在01～02之间较好，在这里取015。在角度阈值的选取上，在07～08为最好，本文取075。σ3取采样点邻域的标准差。

322去噪平滑实验分析

对改进后的算法进行实验分析，图3（a）为原始的点云数据，图3（b）为滤除离群点后的点云数据，图3（c）为去除离群点后的点云数据曲面[15]重构的结果，图3（d）为采用本文去噪平滑后的点云曲面重构的模型。通过试验比较可以知道，建立拓扑关系后的点云数据采用数理统计的离群点的滤除方法能够有效地滤除噪声点云数据中的离群点。没有经过去噪光顺后[16]的点云数据曲面重构后的模型出现大量的空洞，对于特征变化明显的区域显得更加的突出。离群点滤除后的曲面重构模型有效的滤除了离群点，能够从一定程度上提高点云数据的质量[17]。

通过试验的方法来验证基于法矢修正的点云数据去噪平滑算法的滤波效果，与中值滤波算法，双边滤波算法和三边滤波算法进行比较。图3为经过不同的滤波算法后的点云数据曲面重构[18]的结果。图4（a）为原始的点云数据，图4（b）为加入噪声点后重构模型，图4（c）为中值滤波后曲面重构模型，图4（d）双边滤波后曲面重构模型，图4（e）为三边滤波后曲面重构模型，图4（f）为本文算法后曲面重构模型。中值滤波使顶点产生漂移，双边滤波会产生过光顺，三边滤波能够取得很好的光顺效果，本文的算法是在三边滤波的基础上进行的改进算法，能够对噪声点的位置进行有效的调整，保留了数据点的几何特征，达到很好的滤波效果。在去噪平滑的时间上，由于算法是建立在点云数据的拓扑关系之上，加快了去噪的运算速度。

4结论

經过法矢修正和位置平滑后重构的曲面能够明显地改善重构曲面中大光顺问题，几何特征变化明显的区域重构的结果也能够突出几何特征。从以上的比较可以得出基于法矢修正的点云数据平滑滤波算法不但能够对大的噪声信号（离群点）有效的滤除，也能够有效的平滑较小的噪声点，能够达到降噪平滑的作用。本文提出的点云数据去噪算法中阀值的选取大多采用经验值或实验值，如何实现各种阀值的自动选取，提高算法的鲁棒性是下一步研究的重点和难点。

参 考 文 献：

[1]FLEISHMAN S， COHENOr D， SILVA CT Robust Moving Leastsquares Fitting with Sharp Features [C]// ACM Transactions on Graphics， 2005， 24（3）：544-552

[2]SUN W， BRADLEY C， ZHANG Y F， etal Cloud data modeling employing a unified nonredundant triangular mesh [J]. Computer Aided Design， 2001， 33（2）： 183-193

[3]尹婷三维激光扫描数据处理技术的研究[D].武汉：武汉理工大学，2010

[4]李天兰三维点云数据的处理与应用[D].昆明：昆明理工大学，2011

[5]张金花，吴思，胡本刚，等基于地面三维激光扫描仪点云数据的去噪算法研究[J].测绘与空间地理信息，2016（3）：76-78

[6]MEDELLIN H， CORNEY J， DAVIES J B Algorithms for the Physical and Assembly of Octree Models [J]. ComputerAided Design， 2006， 38（1）：69-85

[7]SUN Xiaoxia， SUN Dianzhu， LI Yanrui， et al Algorithm of Point Data Direct Reduction in Reverse Engineering[J]. Machinery Design & Manufacture， 2006（8）：37-38

[8]HUANG G Z， LU Z P Methods of Point Cloud Data Reduction for Reverse Engineering[J]. Machine Design and Research， 2005， 21（3）： 59-61

[9]王丽辉三维点云数据处理的技术研究[D].北京：北京交通大学，2011

[10]何东健，邵小宁，王丹，等Kinect获取植物三维点云数据的去噪方法[J].农业机械学报，2016（1）：331-336

[11]张育锋三维数据点云的去噪及其检测[D].南京：南京信息工程大学，2014

[12]PIEGL LA， TILLER W Algorithm for Finding All K Nearest Neighbors [J].Computer Aided Design， 2002， 34（2）： 167-172

[13]XU Dong， ZHANG Quanfang， LIU Xianguo， et al Geometry Compression for Genreal Polygon Meshes[J].Journal of Computer Aided Design & Computer Graphics， 2002， 14（9）： 815-819

[14]张帆点云数据几何处理方法研究[D].西安：西北大学，2013

[15]罗格三维模型去噪算法的研究及其在三维曲面重建上的应用[D].哈尔滨：哈尔滨工业大学，2015

[16]梁士超三维点云预处理技术研究[D].绵阳：西南科技大学，2015

[17]吴琼三维点云模型数据的滤波算法与配准算法研究[D].秦皇岛：燕山大学，2014

[18]姜晓通离散点云数据重建关键技术的研究[D].南京：南京航空航天大学，2013

（编辑：关毅）