一种新型稀疏标志点的特征描述算法

石诚，程筱胜，崔海华，方舟，张逸，胡广露

(南京航空航天大学 机电学院，江苏 南京 210016)

0 引言

近年来，随着航空航天、汽车船舶、机电重工等大型装备制造业蓬勃发展，摄影测量技术因其便携、快速和高精度的优点，正得到越来越多的应用[1]。为将摄影测量应用于大型装备制造装配变形分析，提出一种稀疏标志点数据的特征描述算法，用以匹配变形前后的标志点数据。

目前关于点云数据匹配的研究[2-3]大多针对点云密度较高的数据，一般分为粗配准和精配准[4]，通常采用“先粗后精”的思路。粗配准主要分为基于RANSAC[5]和基于特征的配准方法，其中基于特征匹配的方式，更具有效率和鲁棒性[6]。RUSU R B等提出了视点特征直方图[7](viewpoint feature histogram，VFH)特征量和快速点云直方图[8](fast point feature histograms，FPFH)特征量作为描述子；刘剑等[9]将三角剖分与FPFH特征描述相结合，黄源等[10]利用局部几何特征作为描述子，进行数据的匹配。这些描述特征点的思路被借鉴，用以解决稀疏标志点数据的匹配问题，翁金平等[11]使用能量法描述稀疏标志点，实现了标志点的特征匹配，但能量法局限于标志点数据不发生形变的情况，适用性不够广泛。

本文受点特征直方图[12](point feature histograms，PFH)描述算法启发，利用稀疏标志点数据邻域的拓扑信息，进行稀疏标志点数据的匹配。

1 特征描述算法

假设摄影测量在初始状态获取的标志点数据集合为点集P，产生局部形变后获取的数据集合为点集Q。P和Q在不同测量坐标系下且包含未发生形变的点对，稀疏标志点的描述算法根据点邻域的拓扑信息，对P和Q中每个点做唯一描述，描述结果称为描述子。通过描述子确定P和Q的对应点对，并筛选出其中几乎未发生形变的点对，以完成稀疏标志点数据的匹配。

1.1 描述子的建立

任选稀疏数据中一点Po，简述描述子的建立过程：

1)利用KD树检索，查找距离Po最近的k个点，依据这些点与Po的欧氏距离di(i=1,2,…,k)：

(1)

将这k个点由近及远，构成k邻域点集Pk(图1)。取k=3，展示了k邻域点集Pk的建立思路。

图1 建立k邻域点集Pk

2)对于点集Pk内一点Pi，在Po处建立图2所示的局部坐标系(u,v,w) (U,V,W)，其中no为点Po的法矢，建立过程如下：

U=no

(2)

(3)

W=U×V

(4)

图2 定义局部坐标系

其中:坐标轴u、v、w的方向分别对应矢量U、V、W的方向。

3)基于局部坐标系(u,v,w)，根据PFH特征值的计算方法，计算图2中一组角度，来表示点Po法矢no和点Pi法矢ni的偏差：

α=V·ni

(5)

(6)

θ=arctan(W·ni,U·ni)

(7)

4)按照步骤2)、步骤3)，分别计算Po与点集合Pk中各点的特征值α、φ、θ，则每对点Po和Pi可得到如下四维描述向量，记为Di：

Di=(di,αi,φi,θi)

(8)

5)按照k邻域点集Pk中的顺序，建立点Po的k×4描述矩阵D，D即为点Po的描述子：

D=(D1,D2,…,Dk)T

(9)

6)将描述矩阵D进一步变形为如下形式，则β为k维的向量，由各邻域点到点Po的欧氏距离构成，B为k×3的矩阵，由各邻域点到点Po的角度特征构成：

D=(βT,B)

(10)

将描述子D拆分，是因为β能够更准确地判断前后点之间的对应关系，而矩阵B更好地折射出形变大小。下文称β为距离向量，称B为角度矩阵。

1.2 描述子相似度的衡量

利用上述算法计算出稀疏数据中每个点的描述子，点集P中所有点的描述子构成集合FP={Dpi|1≤i≤nP，i∈N}, 点集Q中所有点的描述子构成集合FQ={Dqj|1≤j≤nQ，j∈N}。其中nP和nQ分别为点集P和Q中点的总个数，Dpi和Dqj分别为点集P中第i个点和点集Q中第j个点的描述子。

(11)

利用最近邻匹配法(nearest neighbor)[13]和阈值法分析距离向量，初步获取点集P和Q的对应点对。最近邻匹配法即对P中一点Ps，取其对应的距离向量βps，然后搜索出点集Q中距离最近的向量βqt，将点Ps和点Qt视作一对对应点。为了防止误匹配，再使用阈值法，设置阈值h1，若ρ(βpi,βqj)≤h1，则将这对点作为初步匹配结果。

初步获取对应点对后，需筛选出其中几乎没有发生形变的点对，这就要利用角度矩阵。角度矩阵主要描述了查询点与其周围k个邻域点之间的相对位置关系，因此假如该查询点与其k个邻域点的位置较为恒定，角度矩阵并没有太大的变化；反之，角度矩阵则会有明显变化。据此，利用F-范数来衡量角度矩阵的变化大小。以对应点对Ps和Qt为例：

BE=Bps-Bqt

(12)

2 实验结果及分析

2.1 实验过程及评价标准

实验利用加拿大某公司的摄影测量设备获取标志点，图3(a)为初始状态的标志点排布情况，图3(b)模拟了局部形变和位移后，标志点的排布，图中黑色圆内的靶标是基准点，用于变形前后数据匹配，以验证算法精度。实验过程具体步骤如下：

1) 布设标志点，获取标志点点集P；

2) 模拟局部位移和形变，变换测量坐标系，获取标志点点集Q；

3) 通过基准靶标，利用奇异值分解[14](SVD)算法，匹配点集P和Q；

4) 输出对应点的编号，并计算各点变形大小；

5) 利用本文提出的算法，筛选出几乎不形变的对应点对，据此匹配点集P和Q；

6) 输出对应点的编号，计算各点变形大小。

图3 标志点排布情况

步骤4)所得结果作为本次实验的标准值，将步骤6)结果与标准值对比，验证本文算法的准确性和匹配精度。

2.2 实验数据分析

两次测量所获取的点集分别为P和Q，它们的标志点编号分别如图4(a)、图4(b)所示。

图4 标志点编号

使用本文的算法，得到对应点对的初步匹配关系如图5所示，在获取了初步对应点对匹配结果之后，继续使用本文的算法，筛选出几乎不发生形变的对应点对，这些点对记录在表1。

图5 对应点匹配结果

表1 用于匹配的对应点对

利用表1中的对应点对，计算转换矩阵，匹配点集P和Q，并计算各点变形前后的误差。利用基准点匹配所得的误差如图6所示，将作为误差评判的标准。利用本文算法匹配所计算出的误差如图7。将本文算法和标准结果对比，偏差结果如图8所示，最大偏差为-0.098mm，最小偏差为-0.017mm，绝对偏差的平均值为0.029mm。

图6 各点标准误差

图7 本文算法所得各点误差

图8 本文算法与标准结果对比

在进行了大量实验统计后，对应点对匹配的成功率接近100%，绝对平均误差为平均值为0.029mm，最低仅为0.008mm。

3 结语

为解决稀疏标志点的匹配问题，本文借助PFH的描述思想，提出了稀疏标志点的特征描述算法，并以此对各标志点进行唯一性描述。实验证明，该算法具有极高的准确性，能够精准地分析出基本不发生形变的对应点对。利

用这些点对求解转换矩阵并完成匹配，平均偏差为0.029mm，足以满足装配周期较长的大尺寸装配摄影测量变形检测的需求。同时，本文的算法也能应用于其他需要标志点匹配的情形，例如基于标志点匹配的点云拼接。为保证匹配结果的准确性，本文对未发生形变的点对筛选过于严格，被筛选出的点在邻域内几乎不发生形变，今后将进一步改进，以适应更多稀疏标志点匹配的应用场景。