基于多描述子投票的飞机蒙皮局部扫描点云定位

张一鸣 李红卫 赵安安 谢 乾 汪 俊

1.南京航空航天大学计算机科学与技术学院，南京，210016 2.航空工业西安飞机工业(集团)有限责任公司，西安，710089 3.南京航空航天大学机电学院，南京，210016

0 引言

飞机蒙皮对飞机的气动性和安全性起着重要作用，一方面，作为飞机气动力外形构件，蒙皮类钣金零件需要具备光滑的自由曲面，具有尺寸大、刚性弱、外形复杂等特点，为了避免加工过程产生较大误差，加工出的蒙皮零件往往需要和理论模型进行对比检测；另一方面，飞机蒙皮直接暴露于外界环境，日久老化、交变载荷、酸液腐蚀、外界撞击等不确定性因素常常使蒙皮出现划痕、裂纹、凹陷、膨胀等一系列损伤[1]，这些损伤的积累对飞机的安全性造成了极大影响，因此，飞机蒙皮质量的检测也是飞机日常维护工作中的一项重要任务。

目前国内的蒙皮零件检测大多仍旧采用手动测量的方法，依靠模胎、样板等专业检验工装进行检测。这种方法依赖于操作人员的实践经验，主观性强，误差大，效率低[2]。飞机蒙皮的日常维护技术也经历了从传统的目视检测，到涡流、磁粉、渗透检测等无损检测技术[3]，再到近年来基于机器视觉的蒙皮检测技术的发展历程[4-6]。然而，基于机器视觉的蒙皮检测技术处理飞机蒙皮的二维图像，颜色、光照等图像纹理信息往往会对其检测质量产生较大的干扰。数字化测量设备的广泛应用，如三坐标测量机、激光跟踪仪、激光雷达等，使得人们能够很容易地获取物体的三维点云数据。利用点云数据对飞机蒙皮进行自动化检测，能在不受外界环境影响的同时保证较高的测量精度，是制造工业向数字化检测方向发展的一个技术趋势。JOVANCEVIC等[7]通过分析扫描到的三维点云数据，自动化识别并提取飞机表面上存在的凹痕、突起或划痕等损伤。高瑞[8]研究蒙皮外形检测特征的识别提取，规划蒙皮外形的扫描测量路径，实现了蒙皮自动化测量。XIE等[9]提出了一种从三维扫描点云中自动提取蒙皮表面铆钉的方法。许龙[10]研究了基于激光雷达的自动化测量基准建立的原则与方法，并设计了针对飞机蒙皮外形的自动化检测方法和流程。

飞机蒙皮的数字化检测技术通过设备对飞机蒙皮件进行扫描，得到高精度的点云数据，再将其和零件理论CAD模型或其生成的点云进行配准分析，能够快速获得零件的制造误差或蒙皮的凹陷、突起、膨胀等损伤信息。其中，局部蒙皮扫描点云和其理论模型的对齐是一个重要环节。由于飞机局部蒙皮和整机蒙皮有着很大的尺寸差异，现有的自动配准算法如基于主成分分析[11-12]的方法、基于几何特征分析的方法[13-17]等方法很难一次性将局部点云对齐到准确的位置上[18]，所以基于数字化测量技术的飞机蒙皮形变检测可以分为局部蒙皮定位、配准和误差分析三个步骤。其中，局部蒙皮定位是在整机蒙皮上确定出局部蒙皮的所在位置，它能够保证后续配准的速度和精度，从而提高误差分析的准确度。因此，实现局部蒙皮点云的自动化定位对于提高飞机蒙皮形变检测效率具有重要意义。

针对上述问题，本文提出基于多描述子投票的飞机蒙皮局部扫描点云定位算法，以实现局部蒙皮点云的自动化定位。算法的整体思路是：先根据局部扫描点云的大小，在整体飞机点云上取得一系列大小与之相近的蒙皮局部点云面片，组成蒙皮面片集合；然后分别用不同的全局描述子选出蒙皮面片集合中与局部扫描点云相似度最高的几个，其所在位置为该描述子确定的投票点；在所有投票点组成的投票空间上进行欧氏聚类，划出投票点最为密集的区域；最后利用投票点加权定位算法由聚类区域内的投票点确定出最终的定位点。

1 飞机蒙皮局部点云面片

飞机蒙皮局部点云面片(以下简称蒙皮面片)是完整飞机点云的一部分，其选取方法直接影响到算法的精度和效率，选取应遵循以下原则：一是蒙皮面片的选取过程要符合真实的扫描过程；二是所有选取的蒙皮面片能够全部覆盖飞机蒙皮表面，且相邻面片之间存在重叠；三是蒙皮面片的数量要在保证精度的同时衡量算法效率。本节结合以上原则对算法中蒙皮面片的选取方法和蒙皮面片集合的建立过程进行说明。

1.1 欧氏距离与测地距离

从一个三维扫描点云中选取局部点云，一种常见的方法是基于欧氏距离(Euclidean distance)进行选取，选取关键点周围半径re以内的近邻点作为一个局部点云。对于一般物体或场景点云，该方法简单快速，适用于对选取的局部点云无特殊要求的任务。然而，为了确保蒙皮面片集合中存在与局部扫描点云相似的形状，就要使选取的蒙皮面片尽量贴近真实扫描出的点云，其形状应沿着飞机蒙皮表面连续延伸。基于欧氏距离的选取方法在一些地方往往无法取得符合上述要求的蒙皮面片，包含着大量的无用点，如图1a所示，在类似飞机机翼的结构处，若以上表面一点vi为中心、re为半径选取局部点云时(红色区域)，基于欧氏距离的选取方法很容易选取到下表面的点，其形状不符合真实扫描出的局部点云。这些形状给局部扫描点云和蒙皮面片集合之间的相似度比较带来了极大的干扰，使得之后的局部蒙皮定位过程无法定位到正确的位置。

本文算法基于测地距离选取蒙皮面片，如图1b所示。测地距离(geodesic distance)描述了曲面上两点沿其表面的最短距离，或者图上两个节点之间的最短距离。对于三维空间中的一张无向图G={V,E}，节点vi在rg半径内的邻近点，是所有与节点vi之间测地距离小于rg的节点的集合，描述为

(a)欧氏距离

Nvi={vj|vj∈V,g(vj,vi)≤rg}

(1)

其中，Nvi为点vi的邻近点集合，g(vj,vi)为vi、vj两节点之间测地距离。该算法可以确保其形状沿着飞机蒙皮表面延伸，符合真实扫描点云数据的特点。

1.2 飞机蒙皮面片集合的建立

飞机蒙皮面片集合包含若干从完整飞机点云上选取的蒙皮面片，基于测地距离的选取方法可以保证它们的形状贴近真实扫描的局部点云。同时，集合规模和其中蒙皮面片形状的完备也影响着算法的精确性和运行速度。集合中蒙皮面片对整个飞机蒙皮表面覆盖得越完整，形状越丰富，数量越多，越能保证其中存在与局部扫描点云高相似度的蒙皮面片，从而提高算法的精度。但集合增大意味着需要花费更长的时间，后续计算描述子的时间开销也会随之增加。通过下文的实验可以看出，过多数量的蒙皮面片只能对算法精度带来有限的提升。本节先介绍蒙皮面片的详细选取过程，然后说明蒙皮面片集合的建立方法，最后考虑到算法的时间复杂度和空间复杂度，提出一种优化的集合建立策略。

在空间中离散分布的三维点云无法直接反映点与点之间的测地距离关系，只能先将点云构造成离散带权无向图G。从输入点云构造图G=(V，E)的流程如下[19]：

(1)将完整飞机点云中的所有点作为节点V={v1,v2,…,vn}并入图G。

(2)构造点云的k邻近图。若点vj是vi邻近点,则将以这两点为节点的边eij并入图G的边集E,以两点之间的欧氏距离作为该边的权值。

(3)对于图G中任意两个节点，用Dijkstra算法计算它们此时在图G上的最短距离，并作为该边的权值并入图G的边集E。

构造后的带权无向图G中任意两节点之间的边的权值，即可作为点云上对应两点间的测地距离。基于图G和飞机点云上的关键点，可按照式(1)选取关键点周围半径rg以内的邻近点作为该处的蒙皮面片。

关键点的位置和数量直接关系到蒙皮面片的分布情况，要尽量使其在飞机表面上均匀分布，以使所有蒙皮面片能完全覆盖整个飞机表面，本文采用最远点采样法(farthest point sampling)确定关键点，采样数量应根据飞机尺寸进行调整，以满足前文所述的精度和效率之间的平衡。在下文的实验中，对某型飞机模型下最优设定的关键点密度情况进行了分析和可视化。

如果直接将整个飞机点云建立成一张离散带权图，算法的时间复杂度和空间复杂度都将是O(n2)，这对于大规模的点云来说无疑会耗费较大的内存空间和较长的运行时间，因此，本文提出一种优化的算法策略建立蒙皮面片集合T={t1,t2,…,tl},其中，l为集合的大小，具体建立过程如下。

首先在完整飞机点云上选取l个关键点；对于第i个关键点，先以半径re选取其周围基于欧氏距离的邻近点集合Si；建立集合Si的离散带权图Gi；然后在图Gi上以半径rg选取关键点i周围基于测地距离的邻近点，构成蒙皮面片ti,其中rg=0.7re；重复上述过程直至建立完整的集合T。算法流程如图2所示。优化后算法的时间和空间复杂度降为O(nlogn)。

图2 飞机蒙皮面片集合的建立Fig.2 Establishment of aircraft skin patch set

2 基于多描述子投票的蒙皮定位

建立飞机蒙皮面片集合后，为了定位局部扫描点云，需要将其与集合中的蒙皮面片一一比较，确定出相似度最高的一块蒙皮面片，该蒙皮面片的所在位置即为定位点。基于全局特征的三维描述子是常用的点云之间相似度比较工具。目前不同的基于全局特征的描述子对形状、密度各异的点云的描述能力往往各有优劣，单一的描述子容易选出错误的蒙皮面片。因此，本文提出了基于多描述子投票的蒙皮定位方法，首先利用多个描述子各自确定的相似度最高的蒙皮面片的位置建立投票空间，然后在投票空间上进行聚类，找出投票点最密集的区域，最后在该区域中确定最终的定位位置。

2.1 建立投票空间

传统的点云特征描述子根据提取特征尺度的不同，可以划分为局部特征描述子和全局特征描述子。由于局部扫描点云每次扫描大小尺度不一，点数各异，采用局部特征描述子编码蒙皮面片和局部扫描点云得到的描述向量长度也会难以统一，这将增大后续算法的复杂度。而全局特征描述子则会将任意点云编码成统一长度的向量，更便于相似度比对。在所有传统全局特征描述子中，一些描述子专门为特定任务设计，如Point-related Shape[20]、GFPFH[21]等，均难以适用于蒙皮定位任务，也有一些描述子由于考虑视点信息而缺乏旋转和平移不变性，或是需要额外的物体类别信息输入，这些都不适合用于投票空间的建立和后续的蒙皮定位。

综上，本文筛选了现有的全局点云描述子，最终选出以下4种描述子建立投票空间：快速点特征直方图[13](fast point feature histogram，FPFH)、形状函数集合[14](ensemble of shape function，ESF)、全局半径表面描述子[15](global radius-based surface descriptor，GRSD)以及全局正交物体描述子[22](global orthographic object descriptor，GOOD)，其中，FPFH作为全局描述子使用。值得注意的是，本文方法并不局限于上述4种描述子建立投票空间，参与投票空间建立的描述子种类和数量均可根据不同任务进行调整。假设每种描述子确定q个投票点，对投票空间的建立过程进行说明，对于每一种描述子，以ESF为例，具体建立过程如下：

(1)计算蒙皮面片集合中所有蒙皮面片的ESF特征，组成集合的ESF描述空间。

(2)计算局部扫描点云的ESF特征，并寻找该特征在集合的ESF描述空间里的前q个最邻近点。

(3)将这q个邻近点所代表的蒙皮面片在三维空间中的位置，即其关键点的位置，作为该描述子的q个投票点。

(4)对于其余描述子重复以上过程，总共可得到4q个投票点。

(a)FPFH投票空间 (b)GRSD投票空间

包含这4q个投票点的三维空间即最终建立的投票空间如图3所示。由于每种描述子从各自的描述空间中依次寻找前q个邻近点作为投票点，所以理论上第一个投票点会比第二个投票点具有更大的投票力度，即与局部扫描点云具有更高的相似度。但实验过程中发现由于描述子自身不稳定的表现，这一推论并不总是成立，因此，从宏观角度上讲，本文在投票空间建立时赋予了所有投票点相同的权值，而下文将在更微观的尺度上设计算法来验证这一趋势。

2.2 蒙皮局部点云面片定位

投票空间代表不同描述子各自选出的若干个最优定位位置。为了综合利用各个描述子的优势，在最终定位阶段，算法从描述空间中找出投票点最为密集的区域，如图3中黑色圆圈所示。具体地，本文采用点云库(point cloud liabrary)中的欧氏聚类算法，以聚类半径rc=rg确定该区域。

聚类区域包含着m个投票点，最终的定位位置为这m个投票点的线性加权组合：

(2)

式中，s为定位点坐标；wi为第i个投票点的权值；vi为第i个投票点坐标。

由于聚类区域中的投票点具有不同的投票力度，最终的定位位置不应简单地取所有投票点的平均值，而是应该靠近力度大的投票点。如图4所示，投票点上的数字显示了该点在其描述子上的投票排名，1表示该描述子投出的第一个点，其投票力度最大，以此类推，同排名的投票点投票力度相等。因此，本文采用如下方法确定投票点的权值：

(3)

式中，wi为第i个投票点的权值；m为聚类区域中投票点的个数；pi为第i个投票点在其描述子中的排名；δ为大于q的任意整数。

(a)定位点和各投票点等距 (b)定位点靠近力度高的投票点图4 不同策略下的定位点位置Fig.4 Localization position under different strategies

当δ→∞时，wi→1/m，此时定位点坐标为聚类区域内所有投票点的平均值。δ值越小，排名更高的投票点会取得更大的权值。上述方法称为投票点的加权定位法。

假设局部扫描点云的中心点为c,定位点为s,通过对局部扫描点云施加平移矩阵T=(I,s-c)，其中，I为单位矩阵，可以将点云平移对齐到定位点。

3 实例分析

基于多描述子投票的蒙皮定位方法综合了不同描述子的优势。本节首先将该方法与基于单一描述子的蒙皮定位方法进行对比实验，验证该方法在实际飞机扫描点云中能取得良好的定位效果。然后针对1.2节的论述，验证不同规模的蒙皮面片集合对定位精确度的影响。

3.1 对比实验验证

分别基于FPFH、ESF、GRSD、GOOD描述子的蒙皮定位法和基于以上4种全局描述子投票的蒙皮定位法进行对比实验。采用从歼-6型战斗机三维模型上采样得到的点云数据进行实验，点云规模为22 000个点。从150个不同的位置选择锚点和半径，参照1.2节所述方法选取其基于测地距离的蒙皮面片作为该位置的局部扫描点云，然后采用不同的定位方法对其进行定位。各锚点坐标作为对应局部扫描点云的真实位置。所有单一描述子定位方法将局部扫描点云的特征向量与蒙皮面片集合中蒙皮面片的特征向量一一计算欧氏距离，然后取距离最近的特征所对应的蒙皮面片，其所在位置即为该描述子方法的定位点。实验规定，若某种方法确定的定位点与真实位置之间的误差距离e小于阈值ε，则认为该方法定位准确。在本实验中，将ε设定为0.7 m，每种描述子的投票数q设定为3，蒙皮面片集合的大小设置为800。

当使用某种方法对所有150个局部扫描点云进行定位时，准确定位的局部扫描点云数量在其中的占比称为该方法下的定位准确率。不同方法的定位准确数量和定位准确率见表1，多描述子投票相较于单一描述子定位准确率平均提高约37.5%。同时，图5所示为多描述子投票法构建的投票空间的可视化结果，其中红色圆圈中表示的是算法经过聚类后得到的投票点集，其中包含了FPFH、ESF、GOOD等描述子的投票点。值得注意的是，即使GOOD全局描述子的定位准确率相较于其他描述子有着较大的差距，但是以图5所示情况为例，GOOD仍然有一票发挥了正确的投票作用，而正确率相对较高的GRSD描述子3个投票点却均未能正确定位。这说明多描述子投票法能有效抵抗单个描述子定位效果波动的干扰，综合利用不同效果差异的描述子的优势，从而提高定位准确率。

表1 各个方法的定位准确率对比Tab.1 Comparison of methods in location accuracy

图5 投票空间可视化Fig.5 Visualization of voting space

3.2 聚类区域内投票点的加权实验

在聚类区域内确定最终的定位点时，为了使定位位置更加准确，需要考虑其中投票点不同的投票力度。参照2.2节提出的投票点加权定位法，本节实验对比了式(3)中δ=∞和δ=q+1时的定位效果。实验配置参考3.1节，q取值为3。在150个局部扫描点云中，选择其中定位准确的实例，计算它们与真实定位位置之间误差距离的平均值，称为该方法的平均定位偏差。

图6所示为两种加权方法在不同蒙皮面片集合大小下平均定位偏差。相比简单地计算聚类区域内投票点的平均值，改进的加权方法能够有效降低定位点的偏离程度。

图6 不同权值下的实验对比Fig.6 Experimental comparision in different weights

3.3 蒙皮面片集合大小的影响

1.2节论述了不同大小的蒙皮面片集合影响着算法的精度和效率。参照3.1节的实验配置，本节实验调整了其中蒙皮面片集合的大小,以验证蒙皮面片集合大小对定位准确率的影响。在歼-6型飞机点云上的实验结果如图7中实线所示。可以看出，随着集合中蒙皮面片数量的增加，定位准确率逐步上升，但当蒙皮面片的数量大于600时，定位准确率的增长趋势放缓。进一步，实验选择ModelNet40[23]集上的两模型飞机A和飞机B进行多次实验验证，可以得出相同的结论。

图7 不同蒙皮面片集合大小下的定位准确率Fig.7 Localization accuracy in various scale of skin patch set

图8所示为不同蒙皮面片集合大小下程序的运行时间。与定位准率不同，程序的运行时间随着蒙皮面片数量的增多持续线性增长，这意味着定位算法的效率也将随之降低。以歼-6型战斗机为例，在蒙皮面片集合大小为600时，算法效率将达到最高，此时的定位准确率约为74%。图9所示为此时完整飞机点云上关键点的分布情况。

图8 不同蒙皮面片集合大小下的程序运行时间Fig.8 Running time in various scale of skin patch set

图9 最优设定下的关键点可视化Fig.9 Key points visualization under optimal settings

3.4 工程实例

使用Metro-Scan750 Elite扫描仪对歼-6型战斗机进行实测扫描，如图10所示，飞机长度14.64 m，翼展9.0 m，高度3.89 m。实验获取飞机某处的局部扫描点云，对应的飞机蒙皮面积约为1.5 m2。扫描仪得到的格式为ply的点云文件在CloudCo-mpare中进行去噪和降采样处理。图11所示为本文算法在该实测数据上的定位位置的可视化结果，证明了本文算法在实际工程中的可行性。

图10 歼-6型飞机真实点云数据获取Fig.10 Scanning real point cloud data of J-6

图11 实测数据算法定位结果Fig.11 Localization result on a real scanning point cloud

4 结论

(1)针对飞机蒙皮数字化检测技术中局部蒙皮定位问题，本文提出了基于多描述子投票的局部蒙皮定位方法；提出了投票点的加权定位算法减小定位误差；定量地分析了本文方法相较于单一描述子定位的效果优势；定性地分析了选取关键点的最佳采样密度。

(2)在歼-6型飞机实测点云数据上进行实例验证，并对实验结果进行了可视化分析，证明该算法可以在实际工程中应用。