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

刘许　宋阳

摘 要： 使用测量仪器获取点云数据的过程中，由于测量仪器自身缺陷、物体局部遮挡等因素，导致原始点云数据存在孔洞，严重影响曲面重建，需要实施孔洞修补，以便获取完整的模型。采用非封闭孔洞相连的散乱点云的边界确定孔洞修补范围，有效提取非封闭的孔洞边界点及附近模型的边界点，根据孔洞及其周围点的信息，基于移动最小二乘法重构一个隐式曲面，并且通过一定步长实施隐式曲面采样，完成孔洞修补。实验结果显示该算法可以修补不同类型的孔洞，并且修补数据与原始点云数据较好的融合在一起，恢复原始模型。

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

中图分类号： TN98?34 文献标识码： A 文章编号： 1004?373X（2017）05?0101?04

Abstract： In the process of acquiring the point cloud data with the measuring instrument， the holes exist in the original point cloud data due to the defect of the measuring instrument itself， object partial occlusion and other factors， which seriously affect on the surface reconstruction， and it is necessary to repair the hole to get a complete model. The scattered point cloud boundary connected with the non?closed hole is used to determine the hole repairing range， and extract the boundary points of the non?closed hole and nearby model. According to the hole and information around it， an implicit surface was reconstructed based on the moving least square method， and sampled with a certain step to repair the hole. The experimental results show this algorithm can repair the holes of different types， and fuse the repaired data with the original point cloud data together to restore the original model.

Keywords： moving least square method； point cloud data； hole surface； repairing data

0 引 言

中國的古代建筑是中国历史的重要见证，代表中国建筑的继承与发展，保护这类风格的建筑，也就是保护中国的历史，是现代人义不容辞的任务[1]。随着激光测绘、计算机虚拟、图像处理、三维建模等技术的快速发展，三维激光扫描技术与虚拟现实技术在此基础上亦得到较大改进，已经在古建筑重建、模具制造、3D打印等领域得到了广泛的普及和应用，取得了较好的效果[2?5]。三维点云数据采集过程中，由于模型自身损坏、激光扫描视线遮挡等原因，造成点云数据缺失，直接影响建模质量，因此，为了促使建模呈现光滑，需要进行孔洞修复[5?6]。

点云数据孔洞修补算法得到了改进和发展，但是由于测量物体及仪器自身缺陷、测量环境复杂等因素，导致测量的点云数据存在许多的非封闭孔洞。为了能够更好地实现非封闭孔洞修补，本文提出采用非封闭孔洞相连的散乱点云的边界确定孔洞修补范围，采用三次曲线边界可以拟合模型边界点，根据孔洞及其周围点的信息，基于移动最小二乘法重构一个隐式曲面，并且通过一定步长实施隐式曲面采样，完成孔洞修补，实验结果表明该算法能够很好地恢复古建筑容貌[7?9]。

1 非封闭孔洞的提取和检测

大量的古籍文物在保护和恢复过程中，需要重建其往日容貌，但是拍摄工具及古籍文物自身的缺陷容易导致产生非封闭孔洞，需要寻找一种有效的算法，对其进行优化、修补。因此，准确的提取和检测非封闭孔洞已经成为孔洞修补的基础工作，具有重要的作用。如果点[P]的K?邻近反映有实际曲面的边界存在，并且点[P]就存在于边界上，因此点[P]就被称为边界特征点。基于K?邻近点的毗邻关系可以提取边界特征点，通过K?邻近点向其切平面投影可以建立毗邻关系。连接K?邻近点的投影点与形心的投影点形成一条线段，以该线段为起始边，逆时针旋转，可以计算该线段与其他线段的投影角，并且可以对投影角进行排序，排序完成之后，将投影角按照前后顺序相减，可以计算出K?邻近点的每一个毗邻角。

为了能够更好地、全面地修补点云数据孔洞，本文将非封闭孔洞转化为封闭孔洞，对封闭孔洞进行修补。具体的封闭孔洞转化步骤为：在非封闭孔洞两边各自选取4～6个非噪音点作为三次曲线边界拟合的控制顶点；针对选取的点实施三次非均匀曲线边界曲线拟合；重新采样新得到的曲线边界曲线，并且提取孔洞边界的新增采样点；结合非封闭孔洞的边界点与新增采样点，将其连接成封闭的孔洞边界。

在上述执行步骤中，关键点是拟合曲线采样。拟合曲线采样首先需要计算型值点的参数间距，并且对其进行排序，选取最小值[Δmin]。引入一个[λ]系数，根据相关经验，可以设置[λ=2]，如果任意两个相邻点[Pi，][Pj]之间的参数间距[Δ>λ×Δmin，]则表示相邻点[Pi，][Pj]之间需要新增采样点，其中[Δ=ui-uj，][ui]表示点[Pi]关联的参数值，[uj]表示点[Pj]关联的参数值，则：

式中：[n]表示相邻点[Pi，][Pj]之间需要新增的采样点个数；[u*i]表示新增采样点的参数值。使用式（1）和式（2）可以计算拟合曲线上[u*i]参数值上的坐标点，进而可以得到相邻点[Pi，][Pj]之间的新增采样点。

2 构建孔洞曲面数学模型

2.1 确定孔洞邻近域的特征面

为了使点云数据孔洞修补的效果更加光滑，本文使用孔洞及关联的几何信息确定孔洞区域隐式曲面。孔洞及其附近的几何信息通常被称为孔洞邻近域，邻近域的厚度可以确定孔洞附近的点属于孔洞邻近域。为了能够更好地实现点云数据孔洞修补效果，本文将孔洞边界点的一次K?邻近点统归于孔洞邻近域。假设孔洞所在面上到孔洞邻近域中的各个点[P1P2…Pn]的平方和最小，则该面表示孔洞邻域的特征面。特征面可以使用空间点[O]和单位法向量[n]来定义，其中[O]表示孔洞邻近域[P1P2…Pn]的形心：

假设矩阵[MMT]的最小特征值对应的单位特征向量为[t，]根据主成分分析理论可知[t]垂直于特征面。

2.2 计算局部坐标系

3 孔洞填充点计算

3.1 计算重新采样点的[u]轴、[v]轴的坐标值

将孔洞多边形变换到孔洞坐标系下并且可以把孔洞多边形投影到特征面上，投影面上的多边形称为投影孔洞多边形。求出投影孔洞多边形在局部坐标系下的包围框，可以得到该投影孔洞在[u]轴、[v]轴上的[umax，][vmax，][umin，][vmin。]使用一组平行于[u]轴、[v]轴的直线与孔洞多边形求交，平行线间的间距也就是采样间隔，采样间隔的[stepsize]可以表示为：

3.2 计算填充点

在隐含曲面函数方程中代入重新采样点在[u]轴、[v]轴的值，重新采样点在[s]轴上的值就可以求解得到，按照上述计算方法迭代执行，求解所有的[s]轴坐标值。确定全部重新采样点在孔洞坐标系中的位置。

4 实验及结果分析

为了有效验证本文算法的有效性，与基于径向基函数[8]的点云数据孔洞修补算法进行比较。实验过程中，本文使用RIEGLVZ?4000三维激光扫描仪采集的古建筑生成的点云数据，由于光照、古建筑自身缺损，在圖1中的灰色区域产生了一个非封闭孔洞，在其他区域也产生了一些散乱分布的孔洞，如图1所示。

为了能够更好地实现古建筑模型重建，本文采用基于移动最小二乘法的点云数据孔洞修补算法，修补的孔洞使用黄色进行覆盖，算法运行结果如图2所示。

为了能够验证本文算法执行的有效性，与基于径向基函数的点云数据孔洞修补算法执行的结果进行对比分析。古建筑模型的原始孔洞点数为452个，径向基函数修补后孔洞点数剩余76个，孔洞修补率为83.2%；本文算法修补后孔洞点数剩余21个，孔洞修补率为95.4%，孔洞修补成功率明显高于径向基函数修补算法。另外，本文算法修补耗费时间为6 143.5 ms，远小于径向基函数算法，因此，综合孔洞修补成功率和耗费的修补时间，本文算法具有较好的效果，详细数据如表1所示。

5 结 语

随着古籍文物保护技术的发展，三维重建具有不可替代的作用，为了能够更加精确地恢复古籍文物的容貌，本文提出了一种针对散乱点云数据非封闭孔洞修补的算法，采用三次曲线边界可以拟合模型边界点，并且按照一定的步长进行采样，形成封闭的孔洞边界，充分利用孔洞边界特征面及其领域信息，基于移动最小二乘法构建隐式曲面函数，计算孔洞填充点的坐标值，实现孔洞修补点与原始点的平滑过渡，具有较好的修补效果。

参考文献

[1] 杨永.古建筑数字化保护关键技术研究[D].开封：河南大学，2010：1?10.

[2] 李宝瑞.地面三维激光扫描技术在古建筑测绘中的应用研究[D].西安：长安大学，2012：2?7.

[3] 熊友谊，冯志新，陈颖彪，等.利用点云数据进行三维可视化建模技术研究[J].测绘通报，2012，32（5）：20?23.

[4] 陈飞舟，陈志杨，丁展，等.基于径向基函数的残缺点云数据修复[J].计算机辅助设计与图形学学报，2012，18（9）：1414?1419.

[5] 孙殿柱，朱昌志，李延瑞.散乱点云边界特征快速提取算法[J].山东大学学报（工学版），2012，34（1）：42?48.

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

[7] 田建磊，刘旭敏，关永，等.大规模孔洞点云的快速重建算法研究[J].计算机应用研究，2010，27（4）：1544?1546.

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

[9] 晏海平，吴禄慎，陈华伟.基于径向基函数的散乱点云孔洞修复算法[J].计算机工程与设计，2014，35（4）：1253?1257.