基于移动最小二乘法的点云平滑及重采样

吴晓庆，黄玉清

(西南科技大学 信息工程学院，四川 绵阳 621010)



基于移动最小二乘法的点云平滑及重采样

吴晓庆，黄玉清

(西南科技大学 信息工程学院，四川 绵阳 621010)

将点云进行三维重建符合人们的视觉习惯，可以逼真地反映场景的立体效果，并且可以方便地进行多角度显示。针对贪婪投影三角化重建结果中存在的曲面不光滑且存在孔洞等问题，提出了使用移动最小二乘法来进行点云的平滑、重采样处理。实验表明，通过移动最小二乘法进行先平滑后采样的方法比直接使用贪婪投影三角化算法或仅平滑处理、采样处理再重建的效果都要好。

三维重建；移动最小二乘法；点云平滑；重采样；贪婪投影三角化算法

0 引言

曲面重建技术在逆向工程、数字可视化、机器视觉、虚拟现实、医疗技术等领域中得到了广泛的应用。除了上述传统行业，随着新兴的廉价RGBD获取设备在数字娱乐行业的病毒式扩展，使得更多人开始使用点云来处理对象并进行工程应用。PCL中目前实现了基于点云的曲面重建模块框架，在此基础上实现了比较基础的泊松重建[1]、MC重建、EarClipping、贪婪投影三角化重建[2]等算法。但是由于测量技术的原因，造成一些误差，通过基本的重建算法无法达到目标效果。本文通过对输入点云进行移动最小二乘法(Moving Least Squares,MLS)的先平滑后采样的处理，并将点云作为贪婪投影三角化重建算法(Greedy Projection Algorithm)的输入，最终实现较好的重建结果。

1 贪婪投影三角化算法

贪婪算法是一种把复杂问题进行精简的算法[2]，在对问题求解时，不从整体最优上加以考虑，它所得的是在某种意义上的局部最优解。也就是说，它把所有的步骤进行细化，形成一个接一个的小问题，之后按照问题的复杂度来对它们进行排序，这在当时被认为是最好的解决办法，然后逐渐地接近最后的问题，最后求解得到解答[3]。

将三维点通过发现投影到某一平面，然后对投影得到的点云做平面内的三角化，从而得到各点的连接关系。在平面区域三角化的过程中用到了基于Delaunay的空间区域增长算法，该方法通过选取一个样本三角片作为初始曲面，不断扩张曲面边界，形成一张完整的三角网格曲面。最后根据投影点云的连接关系确定各原始三维点间的拓扑连接，所得三角网格即为重建得到的曲面模型[4]。

该算法基于增量表面生长规律[5]，遵循贪婪类型方法。算法通过创建一个起始的三角形启动，并不断添加新的三角形直到所有点云中的点被包含或没有更有效的三角形。算法如下[6]：

(1)最近邻域搜索：对于点云中的每一个点p，选择一个k邻域。这个邻域是由搜索参考点k-近邻的范围内创建的，半径为r。半径定义为μ×d，其中d是p点以及最接近邻域的距离，μ是用户指定的常数，以计算点云密度。Kdtree邻域算法经常被用来计算给定点云的临近点。

点云中的点被分配各种状态：没有限制的、边缘、边界和完成，这取决于算法。

①最初，点云中的所有点都是没有限制的，即这些点没有入射的三角形。

②当一个点的所有可能三角形被确定，那么点被定义为完成状态。

③当点被选做一个参考点，但是由于最大允许角度参数的限制而缺失一些三角形，点被定义为边界点。

④边缘点是那些未被选做参考点的点。

(2)使用切平面的邻域投影：邻域投影在一个表面上，该表面相切于p点周围且有序形成的曲面。

(3)修剪：根据可见度和距离标准修剪点，并连接p和靠近边缘的连续点，形成具有最大角度标准和可选最小角度标准的三角形。点云中的点被修剪取决于很多标准。例如：

①通过距离标准修剪。

②位于以参考点为中心的影响范围之外的其他点是被删除。所选择的点被称为候选点。

③投影平面的选择：在应用距离标准后的候选点集合投影到近似切面上。

④角度指定：以参考点作为初始点定义新的局部坐标，并且上一步的平面投影作为xy平面。所有在候选集中的点被映射到这个面上。基于局部坐标系统的x轴和从原点到映射的坐标之间的角度θ，选择周围的参考点。

⑤可视化：潜在形成的自相关网格的点被丢弃。

使用参考点、候选点集合边界边缘方法，投影平面。在这种情况下，从参考点到候选顶点的视线被边缘阻塞，则该点被遮挡。

2 MLS平滑、重采样

因为贪婪投影三角化算法的输入是具有估计的表面法线和曲率数据的点云。现有程序是通过PCA(主成分分析)的方法来求取表面法线的。有时，测量较小的对象时会产生一些误差，这些误差所造成的不规则数据如果直接用来曲面重建会使重建的曲面不光滑或者有漏洞。这些不规则数据很难用统计分析消除，所以为了建立完整的模型必须对表面进行平滑处理和漏洞修复。

在此部分，在现有数据的基础上，利用移动最小二乘方法(Moving Least Squares,MLS)解决数据重采样这一问题，重采样算法通过对周围数据点进行高阶多项式插值来重建表面缺失的部分。

2.1 拟合函数的建立

在拟合区域的一个局域子域U上，拟合函数表示为：

(1)

式中，a(x)=[a1(x),a2(x)…am(x)]T为待求系数，它是坐标x的函数，p(x)=[p1(x),p2(x)…pm(x)]T称为基函数，它是一个阶完备的多项式，是基函数的项式[7]，常用的二次基为[1,u,v,u2,v2,uv]T，所以式(1)中的拟合函数通常表示为[8]：

f(x)=a0(x)+a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv

考虑下面的加权离散L2范式[9]：

a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv)-yi]2

(2)

式中：n是影响区域节点的数目，f(x)是拟合函数，yi是x=xi处的节点值。yi=y(xi);w(x-xi)是节点xi的权函数。为了确定系数a(x)，式(2)中[(a0(x)+a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv)-yi]2应取极小值，从而得：

a=(BWBT)-1BWy

但是以上的权函数只能用于描述低等级的表面，因此在某些情况下会产生不足的近似值，为了反映现实情况，重新估计点较近的采样点应该比估算较远的采样点有更大的影响，所以应该重新考虑权函数。

2.2 权函数的确定

权函数是移动最小二乘法的核心。在移动最小二乘法中，权函数w(x-xi)应该具有紧支性，即权函数在x的一个子域内不等于0，在这个子域外全是0，这个子域称为权函数的支持域(即x的影响域)，其半径记为smax。由于权函数的紧支性，所以只有属于影响区域内的点才会对点x的取值有影响[7]。

(1)点云平滑处理

1.1 研究对象 2014年1月-2014年12月南京市胸科医院的门诊及住院呼吸系统疾病患者6 984例，男性4 681例，女性2 303例，年龄11～99岁，平均年龄（55.24±18.62）岁；按年龄分为五组，≤20岁组258例，20～40岁组1 322例，40～60岁组2 337例，60～80岁组2 626例，≥80岁组441例；按不同季节分组，春季（3-5月）1 931例，夏季（6-8月）1 742例，秋季（9-11月）1 650例，冬季（12-2月）1 661例；所有病例均存在呼吸道感染的临床表现：持续性咳嗽、发热、呼吸急促或呼吸困难；肺部听诊可闻及细湿啰音等。所有患者均知情同意。

由于拟合函数会继承权函数的连续性，所以权函数还应具有一定的光滑性：如果权函数w(x-xi)是C1阶连续的，则拟合函数也是C1连续的。常用的权函数为立方样条权函数：

(2)点云重采样进行孔洞修补

为了体现离重新估算点较近的采样点对拟合函数的影响大于较远的采样点，权因子w(x-xi)应随着估算点的不同而进行“移动”[11-12]。针对这种情况，本文使用如下权函数[8]：

(3)

其中di(x)为新的采样位置p与第i个初始采样位置pi之间的距离。当对一个输入点云进行正确评估时，这个权函数变得无穷大。为了避免这一问题，此种情况被单独处理。参数α控制区域邻近特征对重采样的影响。因为权函数与重采样的位置有关，对于每一个采样点，单独计算新的系数为：

a(x)=(BW(x)BT)-1BW(x)y

其中，W(x)为由式(3)计算的对角矩阵。

①对于一个点云，创建一个三角网格。

②重复以下过程：

a.KD树查找边缘和它的邻域；

b.对于一个孔邻域计算投影平面；

c.判定平面上的重采样位置；

d.拟合曲面且重新采样。

③直到没有孔洞存在。

3 实验结果

实验中，方案平台硬件环境为：深度摄像头微软kinect；软件开发工具为Windows 7操作系统、vs2012、pcl 1.7.2。在同一个平台下，对比了几种算法：普遍使用的贪婪三角形算法进行重建；使用MLS算法进行曲面平滑、重采样及两者结合后，采用贪婪三角形算法进行重建。实验结果及分析如下。

(1)结果显示如图1～图4所示。

图1 贪婪投影三角化算法重建前后点云

图2 MLS平滑后做重建效果

图3 MLS重采样后重建效果

图4 MLS先平滑后采样后重建效果

从图2可以看出，平滑后的点云重建效果明显好于图1，曲面更加光滑且细纹被平滑了。通过图(3)可以看出，经过重采样后，将图2中区域内的孔洞进行了修补。最终使用先平滑后采样的方法，使得孔洞更加细微。经过比较可以看出，图4的这种方法是最好的。

(2)效率分析

表1记录了几种算法程序运行的时间。可以看出优化后的算法时间上均有所减少，在重建效果上，图3与图4的孔洞进行了修补，且两者相比，图4的效果更好，运行时间上也比图3的要少。

表1 几种算法对比

4 结论

针对目前点云重建算法——贪婪投影三角形存在的测量误差所造成的不规则数据使得重建的曲面不光滑且存在孔洞的情况，使用MLS算法进行曲面平滑，并通过重采样实现孔洞的修补，最终实现较好的重建效果。并在此重建基础上，使用八叉树来代替KD搜索算法，在不影响重建结果的情况下，使运行效率在每一种算法原来的基础上得到优化。实验总体表明，对原始点云进行平滑、重采样，运行效率相对于原始算法而言衰减了，但是重建结果得到了优化。

[1] CHAND A K B, NAVASCUES M A. Natural bicubic spline fractal interpolation[J].Nonlinear Analysis:Theory,Methods & Applications,2008,69(11):3679-3697.

[2] DEY T K, GOOSWAMI S. Tight coeone: a water-tight surface reconstructor[A]. In Proceedings of 8th ACM Symposium on Solid Modeling and Applications[C]. Washington: ACM Press, 2003: 127-134.

[3] 刘为宏.点云数据曲面重建算法及研究[D].秦皇岛:燕山大学，2015.

[4] MARTON Z C, RUSU R B, BEETZ M. On fast surface reconstruction methods for large and noisy datasets[C].Proceedings of the IEEE International Conference on Robotics and Automation(ICRA), Kobe, Japan,2009.

[5] MENCL R, MULLER H. Interpolation and approximation of surfaces from three-dimensional scattered data points[C]. In: State of the Art Reports, Eurographics’98, 1998: 51-67.

[6] Navpreet Kaur Pawar.Surface reconstruction from point clouds[D].Bournemouth University, 2013.

[7] 张崇军,郑德华,孟庆年.基于移动最小二乘法的点云数据拟合方法[J].勘察科学技术,2016(4):26-28.

[8] LANCASTER P,SALKAUSKAS K.Curve and surface fitting[M]. The NVRBS, Book. Springer Berlin Heidelberg,1986: 361-453.

[9] 刘小虎,张雄,陆明万.基于MLS的最小二乘配点法[J].强度与环境, 2000, 15(5):65- 69.

[10] 刘欣.无网格方法[M].北京:科学出版社,2011.

[11] 谷利国,候振杰.基于三维重建技术的三角剖分[J].微型机与应用,2010,29(18):44-47.

[12] Wang Jianning, OLIVEIRA M M. A hole-filling strategy for reconstruction of smooth surface in range images[C].SIBGRAPI’03:1530-1834.

Smoothing and resampling of point cloud based on moving least squares

Wu Xiaoqing, Huang Yuqing

(School of Information Engineering, Southwest University of Science and Technology, Mianyang 621010, China)

The three-dimensional reconstruction of the point cloud is in line with people’s visual habits, it can be realistic to reflect the three-dimensional effect of the scene, and can be easily displayed in multi-angle. Aiming at the problem that the surface is not smooth and the holes exist in the reconstructed result of the greedy projection triangulation, the moving least squares(MLS) method is proposed to smooth and resample the point cloud. Experimental results show that the method of smoothing and sampling by moving least squares method is better than that of using greedy projection triangulation algorithm or only smoothing, sampling processing, and then reconstruction.

three-dimensional reconstruction; Moving Least Squares (MLS); point cloud smoothing; resample; greedy projection triangulation

TP391.41

A

10.19358/j.issn.1674- 7720.2017.11.014

吴晓庆，黄玉清.基于移动最小二乘法的点云平滑及重采样[J].微型机与应用，2017,36(11)：47-49，53.

2017-01-13)

吴晓庆(1991-)，女，硕士研究生，主要研究方向：图象处理与机器视觉。

黄玉清(1962-)，通信作者，女，硕士，教授，主要研究方向：无线控制及无线通信技术、图象处理与机器视觉、智能技术应用。E-mail:hyq3053061@163.com。