基于移动最小二乘法的点云数据孔洞修补算法

张予民

摘 要： 由于受到多种因素的综合作用，点云数据不完整，曲面上出现了一些孔洞，为了提高点云数据的孔洞修补精度，解决目前一些方法的局限性，提出基于移动最小二乘法的点云数据孔洞修补算法。首先对当前点云数据孔洞修补研究现状进行分析，并得到点云数据曲面上的孔洞数据，采用移动最小二乘法对点云数据孔洞进行修补，最后通过具体应用实例对其可行性进行测试。结果表明该方法可以对点云数据孔洞进行有效修补，能够获得比较理想的点云数据曲面重建效果。

关键词： 点云数据； 孔洞修补； 移动最小二乘法； 数据处理

中图分类号： TN911.1?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）21?0031?04

Point cloud data hole?filling algorithm based on moving least square method

ZHANG Yumin

（Jiangxi Institute of Economic Administrators， Nanchang 330088， China）

Abstract： In order to improve the hole?filling precision of point cloud data and solve some limitations of the current methods， a point cloud data hole?filling algorithm based on moving least square method is proposed. The research status of hole filling of point cloud data is analyzed to get the hole data on the curved surface of the point cloud data. The moving least square method is used to repair the holes of the point cloud data. Its feasibility was tested with a specific application example. The results show that the method can repair the hole of the point cloud data effectively， and get the ideal curved surface reconstruction effect of point cloud data.

Keywords： point cloud data； hole filling； moving least square method； data processing

0 引 言

在点云数据采集过程中，由于设备自身原因、外界环境的影响，原始点云数据存在一些误差和噪声，出现大量的孔洞，直接影响后续的点云数据曲面建模，为了获得更优的点云数据重建效果，需要对点云数据的孔洞进行修补处理[1?2]。

为了提高点云数据孔洞修补精度，提出基于移动最小二乘法的点云数据孔洞修补算法。首先采集点云数据曲面上的孔洞数据，然后采用移动最小二乘法对点云数据曲面进行拟合和孔洞修补，最后通过具体应用实例对本文方法进行验证，结果表明，本文方法能够获得理想的点云数据孔洞修补效果。

1 点云数据处理与孔洞修补的研究现状

为了解决点云数据处理中存在的问题，学者们一直致力于该问题的研究，当前出现了一些点云数据处理和孔洞修补算法[3?4]。点云数据处理包括数据配准、数据分割、数据去噪、数据简化等方法，这些方法均存在各自的优缺点[5?6]。采集点云数据时，有时不能一次提取目标的完整信息，需要进行多个节点的描述，这样需要将多个节点数据转换到同场景中，实现点云数据配准，提高数据的完整性[7]。点云数据的配准分为两类：基于有特征的点云数据配准和基于无特征的点云数据配准，有特征的点云数据配准过度依赖特征点的提取精度，而无特征的点云数据配准工作时间长，配准效率低[8?9]。点云数据分割将点云数据划分为多个小区域，对每一个区域建立自然曲面；点云数據去噪采用不同的去噪算法消除点云数据中的噪声，如有傅里叶变换的点云数据去噪算法，但这种算法去噪效率低[10]。点云数据简化主要是去除点云数据中的冗余信息，但有时会去除一些有用的特征信息[11]。当前点云数据孔洞修补方法分为体积元素和三角网格两种。体积元素采用体积元素描述点云数据目标孔洞修补模型，该类方法简单、执行速度快，但当点云数据量大时，孔洞修补效率低[12]；三角网格采用三角网格对点云数据目标进行孔洞修补，当点云数据分布均匀，数据规模小时，点云数据曲面孔洞修补效果好，但当数据规模大时，孔洞修补时间长。

2 点云数据技术

点云数据技术是一种高精度的测量技术，根据脉冲测距得到距离值[S，]根据精密时钟测量每个点的横向和纵向扫描角度观测值[α]和[θ，]收集反射强度为[I，]扫描点[P（x，y，z）]的三维坐标为：

[x=Scosαcosθy=Ssinαcosθz=Ssinθ] （1）

扫描点的反射强度和颜色信息主要用于后续数据处理，点云数据系统内部坐标系如图1所示。

相对于传统测量技术，点云数据技术的精度更高，具有良好的非接触性和高效率，可应用于许多人无法触及的环境。采用点云数据技术对目标进行处理，可以得到大量数据，即点云数据（Point Cloud），从而可以用孔洞修补一些实体表面模型，被广泛应用于医学、文物保护、市政建设等领域。点云数据技术的工作流程如图2所示。endprint

3 点云数据的去噪处理

由于受到采集设备和其他因素的作用，原始点云数据存在一些噪声，它们降低了曲面重建质量，因此本文采用小波变换去除原始点云数据中的噪声，以提高点云数据孔洞修补效果。设[ψt∈L2（R），][ψt]的傅里叶变换为[ψ（t）]，如果[ψ（t）]满足式（2）的条件，那么就可以进行小波变换操作：

[Cψ=Rψ（t）2tdt<∞] （2）

式中[ψ（t）]为母小波。

对[ψ（t）]进行伸缩和平移操作可得：

[ψa，bt=1aψt-ba， a，b∈R，a≠0] （3）

式中：[ψa，bt]为小波序列；[a]和[b]分别为伸缩和平移因子。

设含有噪声的原始点云数据为：

[s（t）=x（t）+n（t）] （4）

式中[s（t）]和[n（t）]分别为真实信号和噪声。

对[s（t）]实现离散变换产生[s（n），][n=0，1，2，…，N-1，]小波变换可以描述为：

[W2jsk=12jn=0N-1snψ*（2-jn-k）， j，k∈Z] （5）

[xf（j，k）]和[Wf（j，k）]分别表示尺度系数和小波系数，通过式（6）的递归操作，进行多次小波细分：

[xf（j+1，k）=xf（j，k）*h（j，k）Wf（j+1，k）=Wf（j，k）*g（j，k）] （6）

式中：[xf（0，k）]为真实信号；[h]和[g]为低通和高通滤波器。

通过设置一定的阈值去除原始点云数据中的噪声，最后通过小波重构得到高质量的原始点云数据，重构公式具体为：

[xf（j-1，k）=xf（j，k）*h0（j，k）+Wf（j，k）*g0（j，k）] （7）

式中[h0]和[g0]为重构低通和高通滤波器。

采用小波变换对含有噪声的原始点云数据进行去噪，结果如图3所示。

4 点云数据曲面孔洞修补

4.1 孔洞的检测和修复

点云数据重建过程中，会产生一些孔洞，需要对这些孔洞进行修补，而孔洞的检测是孔洞修补的基础。设点[P]存在于边界上，根据K?邻近点得到曲面边界的所有特征点。根据边界特征点的定义，可以得到两类孔洞：封闭孔洞和非封闭孔洞。为了全面地修补点云数据的孔洞，首先将非封闭孔洞转化为封闭孔洞，然后进行修补，非封闭孔洞转化为封闭孔洞的步骤为：

Step1：在非封闭孔洞边上选择多个非噪音点作为控制顶点。

Step2：对控制顶点进行曲线边界拟合操作。

Step3：对边界曲线进行重新采样，得到新的采样点。

Step4：根据原始边界点与新样点建立新的孔洞边界。

若两个相邻点[Pi，][Pj]的间距[Δ>λ×Δmin，]那么[Pi，][Pj]间需要增加采样点，[Δ=ui-uj，][ui]和[uj]分别为[Pi]和[Pj]的关联参数值，有：

[n=IntΔ（λ×Δmin）] （8）

[u*i=ui+Δn×i， i=1，2，…，n-1] （9）

式中：[n]表示[Pi，][Pj]间新增的采样点数；[u*i]为新增采样点的参数值。

4.2 提取孔洞邻近域的特征面

为了更加准确地修补孔洞，提取孔洞区域的特征面。孔洞和周围信息为孔洞邻近域，厚度可以描述孔洞附近点的多少。设孔洞和邻近域间的点为[P1，P2，…，Pn，]如果这些点的平方和最小，那么表示它们构成了特征面，设[P1，P2，…，Pn]的形心为[O，]特征面可采用空间点[O]和单位法向量[n]描述，有：

[O=1ni=0nPi] （10）

那么相应的构造矩阵为：

[M=P1-OP2-O?Pn-O] （11）

4.3 计算孔洞的坐标系

设[d（Pi，O）≥d（Pj，O），][?j≠i，]那么[Pd]表示[P1，P2，…，Pn]的最远点，[d（x，y）]表示[x]和[y]间的距离，[（Pd-O）×n，][n×（Pd-O）×n，][n]为孔洞坐标系的[u，][v，][s]轴。

4.4 移动最小二乘法的点云数据曲面重建

设[U]为拟合区域的子域，那么移动最小二乘法的拟合函数为：

[s（p）=i=0mai（p）Mi（p）=MT（p）a（p）] （12）

式中：[p∈U；][a（p）=a1（p），a2（p），…，am（p）T]为待求系数；[M（p）]为基函数，拟合函数变为：

[s（p）=a0（p）+a1（p）u+a2（p）v+a3（p）u2+a4（p）uv+a5（p）v2] （13）

加权离散[L2]范式定义如下：

[J=i=1Nw（p-pi）s（p）-fi=i=1Nw（p-pi）a0（p）+a1（p）u+a2（p）v+a3（p）u2+a4（p）uv+a5（p）v2-fi] （14）

式中：[fi]为[P=Pi]处的节点值；[w（p-pi）]为[pi]的权函数。

为了对系数[a（p）]进行求解，对[a]进行求导，且[?J?a=0]，那么有：

[a=（BWBT）-1BWf] （15）

式中[B]值表示矩阵。

在移动最小二乘法中，权函數[wi（p）]与[p-pi]之间是一种单调递减的关系，因此[wi（p）]随着估算点变化而变化，权函数的计算公式为：

[wi（p）=e-μd2i（p）d2i（p）] （16）

权函数与重新采样点密切相关，对系数[a（p）]要进行重新计算，即：endprint

[a（p）=BW（p）BT-1BW（p）f] （17）

式中[W（p）]为一个对角线的取值。

隐含曲面的函数方程计算步骤如下：

Step1：把[P1，P2，…，Pn]投影到特征面上，得到孔洞坐标系下的[s1，s2，…，sn，]计算[f]向量值。

Step2：把[P1，P2，…，Pn]投影到[u，v]轴上，计算坐标值[u1，u2，…，un，][v1，v2，…，vn，]得到[B]的值。

Step3：根据重新采样点和[P1，P2，…，Pn]在特征面上的投影点得到每一个点的权值。

Step4：根据[B，W]和[f]计算求解拟合曲面的系数[a0，a1，a2，a3，a4，a5，]然后计算重新采样点的曲面函数方程，实现点云数据描述的曲面孔洞修补。

5 实验及结果分析

为了测试本文方法的有效性，采用VC++ 6.0进行点云数据孔洞修补实验，以兔子作为实验对象，点云数据孔洞修补和曲面重建实验结果如图4所示。

从图4可以看出，本文方法获得了较理想的点云数据孔洞修补效果，实验结果验证了本文方法的有效性。

为了分析本文方法的优越性，选择文献[13?14]的点云数据孔洞修补方法进行对比实验，各方法的孔洞修补精度和孔洞修补速度如表1所示，从表1可以看出，与其他点云数据曲面孔洞修补方法相比，本文方法的曲面孔洞修补精度有所提高，孔洞修補速度有所加快，具有比较明显的优越性。

6 结 语

点云数据技术可以快速获得目标对象的三维数据和信息，是当前研究中的热点。在点云数据采集过程中，受到外界环境的影响，数据中存在一定的错误和噪声，对后续曲面重建产生了负面影响，为了提高点云数据孔洞修补的精度，提出基于移动最小二乘法的点云数据孔洞修补算法。通过具体应用实例对方法的性能进行测试，结果表明，本文方法可以有效去除点云数据中的噪声，减少误差，采用最小二乘法得到了点云数据曲面孔洞修补最优平面，在提高点云数据孔洞修补速度的同时，提高了孔洞修补精度，具有一定的实际应用价值。

参考文献

[1] 宋宏.三维激光扫描测量技术及其应用分析[J].测绘技术装备，2008，10（2）：40?43.

[2] 刘大峰，廖文和.散乱点云去噪算法的研究与实现[J].东南大学学报（自然科学版），2007，37（6）：1109?1111.

[3] 张舜德，朱东波，卢秉恒.反求工程中三维几何形状测量及数据预处理[J].机电工程技术，2001（1）：7?10.

[4] XU Yuanchun， JIA Jianhua. Adaptive spectral clustering ensemble selection via re?sampling and population?based incremental learning algorithm [J]. Wuhan University journal of natural sciences， 2011， 16（3）： 228?238.

[5] 钟毅，林德静.基于移动最小二乘法的点云空洞曲面重建算法[J].北京服装学院学报，2007，28（3）：9?13.

[6] 马淑梅，张海波，李爱平.基于覆盖二元Lagrange插值的三维激光扫描数据切片技术[J].机械设计与研究，2010，26（6）：91?94.

[7] 马腾，龙翔，冯路，等.点云模型的谱聚类分割[J].计算机辅助设计与图形学学报，2012，24（12）：1549?1558.

[8] 李元旺，黄文明，温佩芝，等.空间超限邻域点云去噪算法的研究与实现[J].计算机系统应用，2010，19（3）：35?38.

[9] 郑海峰.基于多尺度Retinex的超声图像去噪及增强技术[J].激光杂志，2016，37（2）：71?73.

[10] 田青，梁荣华，毛剑飞.面向非匀点云拟合的RSR移动最小二乘法[J].计算机工程与应用，2009，43（35）：153?156.

[11] 罗先波，钟约先，李仁举.三维扫描系统中的数据配准技术[J].清华大学学报（自然科学版），2004，44（8）：1104?1106.

[12] 韩江，江本赤，夏链，等.基于轮廓关键点的B样条曲线拟合算法[J].应用数学和力学，2015，36（4）：423?431.

[13] 袁红星，吴少群，朱仁祥，等.散乱三维激光扫描数据的高阶平滑隐式曲面重建[J].计算机应用研究，2013，30（5）：1593?1595.

[14] 蒋刚.基于SVM和空间投影的点云空洞修补方法[J].计算机工程，2012，35（12）：269?271.endprint