基于GA-BP神经网络的散乱点云孔洞自动修补

王春香，郝林文，王 耀，周国勇，纪康辉，刘 流

（内蒙古科技大学机械工程学院，内蒙古包头014010）

随着三维点云数据采集技术日趋成熟，点云模型被广泛应用于逆向工程、文物修复、医疗诊断和地形测绘等领域。完善的点云数据是后续应用的基础。但在实际的点云数据采集过程中，由于操作技术、实物自身特性和测量环境等多种因素的影响，使得采集到的点云数据不完整，从而导致点云模型存在形状各异的孔洞［1］。孔洞缺陷的存在不仅会影响点云模型的显示效果，还会对后续点云数据的处理以及分析操作等产生较大影响［2］。因此有必要对点云模型的孔洞进行修补，进而保证点云数据完整，为下游模型的重构、快速成型和仿真分析等奠定基础。

散乱点云是指通过测量得到的最原始的数据集合，也是与物体表面误差最小的数据集合，直接对散乱点云进行孔洞修补不需要重建拓扑关系，具有较高的存储和执行效率［3］，此类修补方法一直是国内外学者关注的热点。散乱点云孔洞修补往往都是先在检测并提取孔洞边界和孔洞周围影响区域点云信息的基础上构建隐式曲面、神经网络和样条曲线等，然后通过孔洞区域插值实现孔洞修补。例如：杨永强等［4］在采用最小二乘支持向量机根据孔洞周围点云信息构建曲面的基础上，完成了点云孔洞的修补；Kumar等［5］根据孔洞周围点云数据，先拟合得到非均匀B样条曲面，再通过插值实现孔洞修补。上述2种方法对散乱点云平滑区域孔洞的修补效果较好，但在修补曲率变化剧烈区域的孔洞时会造成特征信息缺失，从而导致修补效果欠佳。梁亮［6］分别采用粒子群算法、遗传算法（genetic algorithm，GA）和思维进化算法优化BP（back propagation，反向传播）神经网络，然后直接在三维空间内修补散乱点云的平面、曲面和跨面孔洞，并通过优化BP神经网络的参数提高了点云孔洞修补精度；何东健等［7］提出了一种基于三次B样条曲线的点云孔洞修补方法，并采用该方法对奶牛点云大面积孔洞进行修补，取得了良好的修补效果，但某些局部区域的修补效果受噪点的影响较大。

针对目前基于GA‐BP神经网络（利用GA优化的BP神经网络）的散乱点云孔洞传统修补方法存在人机交互复杂、自动化程度低等缺点，笔者提出了一种基于GA‐BP神经网络的散乱点云孔洞自动修补方法。首先，对散乱点云的孔洞识别、孔洞区域插值和孔洞修补的方法和步骤进行分析；然后，基于提出的修补方法，开展散乱点云人为孔洞和自然孔洞修补实验，以验证所提出修补方法的有效性和准确性。

1 基于GA-BP神经网络的传统修补方法

BP神经网络具有良好的非线性映射能力和容错能力，但存在收敛速度慢、易陷入局部最优等缺陷，对此很多学者通过采用具有良好全局搜索能力的GA寻优得到BP神经网络的最佳权值和阈值，从而克服BP神经网络的缺陷［8］。GA‐BP神经网络算法的流程如图1所示。

图1 GA-BP神经网络算法流程Fig.1 Flow of GA‐BP neural network algorithm

基于GA‐BP神经网络的散乱点云孔洞传统修补方法的基本思路为：先利用散乱点云孔洞周围影响区域的点云作为样本数据训练GA‐BP神经网络，得到孔洞区域内数据点的某2个坐标与另一个坐标之间的近似映射关系，再利用该映射关系对初步选取的孔洞区域插值点进行调整优化，从而实现孔洞的修补，其流程如图2所示。

图2 基于GA-BP神经网络的散乱点云孔洞传统修补流程Fig.2 Traditional repair process of scattered point cloud hole based on GA‐BP neural network

在基于GA‐BP神经网络的散乱点云孔洞传统修补方法中，孔洞识别、孔洞区域插值和孔洞修补均需借助逆向软件（如Imageware、Geomagic Design X等）通过人机交互的方式来完成［9］，其修补过程比较繁琐，严重影响了修补效率。此外，在修补过程中，由于需要数据转换，可能会造成数据失真，从而影响修补后点云模型的质量。

2 基于GA-BP神经网络的自动修补方法

基于GA‐BP神经网络的散乱点云孔洞自动修补方法通过计算机编程将传统修补方法中的孔洞识别、孔洞区域插值和孔洞修补相结合，实现从残缺点云模型直接到完整点云模型的自动修补，整个过程无须进行复杂的人机交互。

2.1 孔洞识别

孔洞识别是散乱点云孔洞修补的首要环节。对于散乱点云，孔洞识别的本质是孔洞边界点的检测及提取。由于散乱点云中相邻点之间不存在拓扑关系，其孔洞识别难度比网格模型大［10］。对于散乱点云的孔洞识别，往往是根据检测点的邻域点在其局部微切平面内的分布情况来判断该检测点是否为孔洞边界点：内部点的邻域点在其局部微切平面内的投影均匀分布在检测点周围，而孔洞边界点的邻域点在其局部微切平面内的投影集中偏向一侧［11］。目前，最常见的孔洞识别方法是将检测点及其邻域点投影到对应的局部微切拟合平面上，并求解拟合平面内相邻向量间的最大夹角，将夹角大于设定阈值的点判定为孔洞边界点［12‐15］，但该方法的过程较为繁琐。

鉴于散乱点云的噪点会影响孔洞识别的效果，在孔洞识别之前须对其进行降噪处理。散乱点云孔洞边界点的检测流程如图3所示，其中局部微切平面通过最小二乘法拟合得到［16］。识别散乱点云孔洞时需要不断循环孔洞边界点检测流程，直到完成所有点的检测，最后输出孔洞边界点及其邻域点，作为GA‐BP神经网络模型的训练数据。

图3 散乱点云孔洞边界点检测流程Fig.3 Detection flow of boundary point of scattered point cloud hole

在散乱点云孔洞边界点检测过程中，当对由检测点及其邻域点对应的投影点组成的向量进行归一化处理后，这些向量的终点均在图4所示的以检测点的投影点P'为圆心的单位圆上。若邻域点的投影点在P'周围均匀分布，如图4（a）所示，其对应向量矢量和的模较小；若邻域点的投影点在P'周围集中偏向一侧，如图4（b）所示，则其对应向量矢量和的模较大。故可利用来分析检测点P的邻域点的分布情况，从而判断检测点P是否为孔洞边界点：若表示假设所有向量方向相同时的矢量和的模）的比值大于检测阈值δ，则检测点P是孔洞边界点；否则检测点P是点云内部点。

图4 局部微切平面内检测点邻域点的分布情况Fig.4 Distribution ofneighborhood pointsofdetection point in local micro‐tangent plane

综上可知，当检测点的k个邻域点足以体现其邻近范围内的点集分布情况时，可通过计算各向量的矢量和来判断孔洞边界点。通常情况下，邻域点数量k一般取15～30，其大小主要由孔洞周围点云密度决定，点云密度越大，k越小；检测阈值δ一般取0～1，其大小主要与点云的弯曲程度有关，点云的弯曲程度越大，δ越小。该孔洞识别方法简单、高效，无须进行复杂的角度计算，只需通过简单的向量运算就可以有效检测并提取散乱点云的孔洞边界点，可为后续的孔洞区域插值和孔洞修补奠定基础。

2.2 孔洞区域插值

在识别和提取散乱点云孔洞边界点后，须初步选取孔洞区域插值点（即初步填充点）。散乱点云孔洞传统修补方法一般是通过将点云模型转化为网格模型，利用逆向软件通过三角剖分的方式获得插值点，但该方法得到的插值点的均匀性较差，不同位置的点集密度差异较大［17］。此外，在数据转换过程中可能造成数据失真，从而影响修补后点云的质量。

为了获得更符合实际测量点云密度的修补点云，在孔洞区域采用等步长生长的方法选取插值点。首先，将孔洞边界点投影到由这些点拟合得到的局部微切平面上；然后，在局部微切拟合平面的孔洞区域内，以孔洞边界点平均密度作为步长分别沿x方向和y方向进行生长，直到获得孔洞区域内的全部插值点；最后，输出这些插值点在局部微切拟合平面上的二维坐标，作为GA‐BP神经网络模型的输入数据。

在局部微切拟合平面上，孔洞区域内插值点的横坐标为：

式中：xmin为孔洞边界点对应投影点横坐标的最小值；xmax为孔洞边界点对应投影点横坐标的最大值；R为孔洞边界点平均密度。

在局部微切拟合平面上的x=xi处，孔洞区域内插值点的纵坐标为：

式中：yimin为孔洞边界点对应投影点在x=xi处纵坐标的最小值；yimax为孔洞边界点对应的投影区域在x=xi处纵坐标的最大值。

该孔洞区域插值点选取方法无须将点云模型转换为网格模型，避免了因数据转换而造成的数据失真。此外，利用该方法得到的孔洞区域插值点与孔洞周围的点云密度相近，更符合实际测量得到的点云密度，且分布较为均匀，这在一定程度上有助于提高修补点云的质量。

2.3 孔洞修补

将利用上述孔洞识别方法提取到的孔洞边界点及其邻域点作为样本数据来训练和测试GA‐BP神经网络，其中80%的点作为训练数据，20%的点作为测试数据，以得到孔洞修补精度满足要求的GA‐BP神经网络模型。将利用上述插值点选取方法得到的孔洞区域插值点的二维坐标作为GA‐BP神经网络模型的输入数据，并计算其对应的仿真预测值。整合孔洞区域插值点的二维坐标与对应的仿真预测值，得到孔洞修补点的三维坐标，将孔洞修补点云和原始点云融合后得到完整点云，即完成了散乱点云的孔洞修补。

3 散乱点云孔洞修补实验及结果分析

为了验证所提出的基于GA‐BP神经网络的散乱点云孔洞自动修补方法的修补效果，在内存为4.00GB、操作系统为Windows10的Intel（R）Core（TM）i5‐4210M CPU@2.60GHz计算机上利用MATLAB R2015a平台进行编程，分别对残缺点云模型的人为孔洞和自然孔洞进行修补，并分析孔洞修补效果。

3.1 人为孔洞修补

在鼠标点云模型中挖取一个如图5所示的人为孔洞，该区域内缺失点的数量为397个。根据该点云模型的特性，取k=15，δ=0.45，基于图3流程检测并提取孔洞边界点及其邻域点，结果如图6所示。

图5 鼠标点云模型人为孔洞Fig.5 Artificial hole of mouse point cloud model

图6 鼠标点云模型孔洞边界点及其邻域点Fig.6 Boundary points and neighborhood points of hole in mouse point cloud model

采用基于GA‐BP神经网络的散乱点云孔洞自动修补方法对该鼠标点云模型的人为孔洞进行修补，结果如图7所示。

图7 修补后的鼠标点云模型Fig.7 Mouse point cloud model after repair

为了进一步研究该方法的修补精度，在逆向软件Imageware中计算图8所示的鼠标点云模型人为孔洞修补点云（十字线）与原始点云（空心圆）之间的偏差，结果如图9所示。

图8 鼠标点云模型人为孔洞修补点云与原始点云对比Fig.8 Comparison between repaired point cloud and origi‐nal point cloud of artificial hole in mouse point cloud model

图9 鼠标点云模型人为孔洞修补点云与原始点云的偏差Fig.9 Deviation between repaired point cloud and original point cloud of artificial hole in mouse point cloud model

根据上述修补结果可知，基于GA‐BP神经网络的散乱点云孔洞自动修补方法的修补效果较好，修补点云能够与孔洞周围点云自然过渡，无明显修补痕迹。为了进一步验证本文方法的修补效果，对基于本文方法与传统方法的鼠标点云模型人为孔洞修补结果进行比较，如表1所示。

表1 基于不同方法的鼠标点云模型人为孔洞修补结果对比Table 1 Comparison of repair results of artificial hole in mouse point cloud model based on different methods

分析表1数据可知，传统方法利用逆向软件获取的插值点数量较少，与孔洞区域缺失点的数量相差较大，而本文方法获得的插值点数量更接近原始孔洞区域缺失点的数量，误差率较小。此外，若以最大偏差作为修补精度，传统方法和本文方法的修补精度均可满足鼠标点云模型的精度要求，但本文方法的修补精度更高。实验结果验证了基于GA‐BP神经网络的散乱点云孔洞自动修补方法的准确性和有效性。

3.2 自然孔洞修补

采用基于GA‐BP神经网络的散乱点云孔洞自动修补方法来修补因外物遮挡而造成的链轨节点云模型的自然孔洞（如图10所示）。

图10 链轨节点云模型自然孔洞Fig.10 Natural hole of track link point cloud model

为了使链轨节点云模型自然孔洞的修补效果较好，需准确提取该点云模型孔洞的边界点及其邻域点。根据链轨节点云模型的特点，取检测阈值δ=0.1，0.2，0.3，对应的孔洞边界点提取结果分别如图11、图12和图13所示。

图11 δ=0.1时提取的链轨节点云模型自然孔洞边界点Fig.11 Extracted boundary points of natural hole in track link point cloud model withδ=0.1

图12 δ=0.2时提取的链轨节点云模型自然孔洞边界点Fig.12 Extracted boundary points of natural hole in track link point cloud model withδ=0.2

图13 δ=0.3时提取的链轨节点云模型自然孔洞边界点Fig.13 Extracted boundary points of natural hole in track link point cloud model withδ=0.3

由图11至图13可知：当检测阈值δ=0.1时，链轨节点云模型自然孔洞识别结果的准确度较差，识别得到的孔洞边界点包含许多噪点；当检测阈值δ=0.3时，识别得到的孔洞边界点数量较少，无法构成该孔洞的完整边界；当检测阈值δ=0.2时，识别得到的孔洞边界点较为完整且不存在噪点。因此，取0.2作为链轨节点云模型自然孔洞边界点检测的阈值，提取孔洞边界点及其邻域点，结果如图14所示。此外，由于链轨节点云模型自然孔洞属于跨面孔洞且面积较大，在逆向软件Imageware中直接圈选孔洞边界点及其邻域点的难度较大，需进行多次调整，而本文方法可以自动、准确地提取该孔洞的边界点及其邻域点。

根据提取到的链轨节点云模型自然孔洞的边界点，利用本文方法选取其孔洞区域的二维插值点，如图15所示。

图15 链轨节点云模型自然孔洞区域的二维插值点Fig.15 Two‐dimensionalinterpolation points ofnatural hole area in track link point cloud model

利用检测阈值δ=0.2时提取到的链轨节点云模型自然孔洞的边界点及其邻域点训练GA‐BP神经网络模型，得到其预测误差，如图16所示。

图16 用于链轨节点云自然孔洞修补的GA-BP神经网络模型的预测误差Fig.16 Prediction error of GA‐BP neural network model for repair of natural hole in track link point cloud

分别利用本文方法和传统方法对链轨节点云模型自然孔洞进行修补，得到的修补点云如图17所示，其中四周十字线表示识别或圈选的孔洞边界点及其邻域点，中间X形线表示修补点。

图17 基于不同方法的链轨节点云模型自然孔洞修补点云Fig.17 Repaired point cloud of natural hole in track link point cloud model based on different methods

由图17可以看出，传统方法得到的修补点数量较少且分布散乱，而本文方法得到的修补点较为均匀，与孔洞周围点云密度相近，且更接近实际测量点云的密度。为了直观显示孔洞的修补效果，将采用本文方法修补后的链轨节点云模型着色，如图18所示。

图18 采用本文方法修补后的链轨节点云模型Fig.18 Track link point cloud model repaired by method of this paper

由图18可知，基于GA‐BP神经网络的散乱点云孔洞自动修补方法的整体修补效果较好。为了进一步验证本文该方法的有效性，在逆向软件Geomagic Design X中，采用正逆向混合建模方法对修补后的链轨节点云模型进行实体模型重构［18］，如图19所示。重构的实体模型验证了基于GA‐BP神经网络的散乱点云孔洞自动修补方法的有效性和实用性。

图19 采用本文方法修补后的链轨节实体模型Fig.19 Track link solid model repaired by method of this paper

4 结束语

针对基于GA‐BP神经网络的散乱点云孔洞传统修补方法因需通过人机交互完成孔洞识别、孔洞区域插值和孔洞修补而耗时较多的问题，提出了一种基于GA‐BP神经网络的散乱点云孔洞自动修补方法，充分利用计算机自动处理程序，减少了人机交互工作量，提高了散乱点云孔洞修补的自动化程度，使得散乱点云孔洞的修补更为方便和高效。此外，采用基于等步长生长的孔洞区域插值方法所得到的插值点比较均匀，且与孔洞周围点云密度的较一致，在一定程度上提高了修补后点云模型的质量。

虽然本文方法可以有效修补密度较为均匀的残缺点云模型孔洞，但对于不同部位密度相差较大的残缺点云模型孔洞的修补效果不够理想，这将是后续的研究重点。此外，该方法仅适用于存在单个孔洞的残缺点云模型，当残缺点云模型存在多个孔洞时，还需对检测到的孔洞边界点作进一步的聚类处理。同时，该方法需要通过不断调整多个参数来达到理想的孔洞修补效果，如何根据残缺点云模型的特性自动选取各参数的最优值有待进一步研究。