匹配算法及其改进算法

时间：2022-11-06 百科知识版权反馈

【摘要】：COR、MAD和MSD算法机理表明，COR算法的稳定性和精度较差，可认为不适合作为匹配结果的决定性指标。为增加TERCOM匹配算法的稳定性和可靠性，下面将Hausdorff距离引入TERCOM算法中。分别采用上述改进的TERCOM算法和传统的TERCOM算法，进行了匹配导航定位实验。改进型TERCOM算法匹配结果较好，平面位置精度在100m以内，且误差分布均匀。

7.4.1　TERCOM匹配算法及其改进算法

TERCOM(terrain contour matching)利用平行于INS航迹的一组地磁序列作为最终匹配序列。该算法首先在格网内改变第一个INS推算点位置，在背景场中寻找与INS推算航迹平行的一组新的序列。遍历第一个INS推算位置有效范围内的格网，得到多组与INS推算航迹平行的序列。将每一组序列各点格网对应的地磁值与磁力实测值进行匹配，寻找匹配最优的一组作为最终的匹配结果。

最优匹配组的判断采用相关分析算法，目前主要采用的相关算法有互相关COR(cross correlation)算法、平均绝对差MAD(mean absolute difference)以及均方差MSD(mean square difference)算法。

上式中:τ_x和τ_y分别代表两个坐标轴方向的偏移量; T_ACQ代表实测磁力值; T_ST为对应位置的背景地磁值; L为匹配序列的长度，即积累长度。

COR、MAD和MSD算法机理表明，COR算法的稳定性和精度较差，可认为不适合作为匹配结果的决定性指标。MAD和MSD两指标接近，均优于COR指标。但MSD是MAD积分项平方的积分值，相对MAD在量值上要显著得多，更能够反映匹配的精度。因此，在实际应用中，采用MSD指标。

TERCOM是目前采用最广泛的匹配导航算法，但是由于INS提供的航迹随着时间的推移而存在误差积累，该航迹与实际航迹存在一定的角度偏差，而TERCOM算法中采用INS提供航迹进行平移匹配，这必然会导致在背景图中寻找真实航迹时匹配的精度与稳定性均可能较差。此外，目前采用的三种最优配准原则(COR、MAD和MSD)存在相同的机理，不能实现相互校准。因此，下面介绍一种基于Hausdorff距离的匹配准则以及自适应旋转角度探测技术，以期克服传统的TERCOM匹配中出现的上述问题。

1.基于Hausdorff距离的匹配准则

Hausdorff距离是一种极大、极小距离表示法，其主要作用是反映两个集合之间的匹配程度，已被广泛应用于模式识别和模板匹配等图像匹配领域。为增加TERCOM匹配算法的稳定性和可靠性，下面将Hausdorff距离引入TERCOM算法中。

Hausdorff距离主要是针对两个有限闭合点集间距离度量的数学定义。若两个有限点集分别为X(x₁，x₂，….，x_n)和Y(y₁，y₂，…，y_n)，则这两个点集间的Hausdorff距离可表示为:

式中H(X，Y)也可以称为X集合和Y集合间的双向Hausdorff距离。其中h(X，Y)表示集合X到集合Y的单向Hausdorff距离。同样，h(Y，X)表示集合Y到集合X的单向Hausdorff距离。

式中，‖·‖表示距离范数，可以用多种距离范数表示，常用的为欧氏范数、和范数以及极大范数。Hausdorff距离代表两个集合的不匹配程度，距离越大，其匹配程度越差。距离越小，匹配程度越好。

下面对原始航迹所测地磁值加不同随机噪声，借助匹配结果来进一步分析MSD准则和Hausdorff距离准则的性能。两种准则下的匹配结果如表7-1所示。从表7-1可以看出，二者均能达到较高的匹配导航精度，其中MSD用时1.1s，Hausdorff用时略高于MSD，为1.8s，但Hausdorff距离提供了一种新的目标函数用于TERCOM匹配导航，增加了误匹配的诊断指标，有利于误匹配的发现。

表7-1 M SD和Hausdorff准则匹配结果及时间比较

2.基于自适应旋转变换的TERCOM算法

传统TERCOM算法需要借助INS提供航迹，从而利用该航迹平移得到最终匹配序列。该方法对INS提供的航迹在角度上有较高的要求。目前受制于惯导技术的限制，INS提供的航迹随时间的推移存在坐标误差积累，同时，INS提供的航向也存在一定的偏差，加之被匹配对象存在相似性，这些因素严重影响了匹配精度。针对传统TERCOM算法不能精确得到匹配结果的局限，下面介绍一种基于自适应旋转角探测机制的TERCOM适配序列精匹配算法。该算法的流程为:

首先，根据INS提供的航迹，确定整个匹配航迹的重心坐标(x_g，y_g)。

式中，(x_i，y_i)为INS提供的航迹平面位置坐标; w为其权值。

其次，以该匹配序列重心位置为原点，对INS提供航迹增加旋转角a。

式中，［x_p，y_p］为添加旋转偏角a之后的航迹坐标，R为由a组成的旋转矩阵。

将旋转后航迹［x_p，y_p］作为初始匹配序列，进行TERCOM匹配，最终实现定位。

为了实现旋转角度的自适应探测以及匹配导航定位的自动化，下面给出完整的、基于自适应旋转角探测机制的TERCOM适配序列精匹配导航定位过程:

(1)遍历搜索中，对于每个格网，初始匹配时，旋转角从0°开始，以s为步长(s设置为0.5°)对原始INS航迹进行旋转，每旋转一次利用旋转后航迹进行一次传统的TERCOM匹配，直到旋转角大于2倍INS角度偏差(设置为3°)为止。

(2)根据MSD最优匹配准则或者基于Hausdorff距离的匹配准则，从每次匹配结果中得到最小MSD及其对应的旋转角a_i。

(3)以a_i为中心在［a_i－s］到［a_i+ s］范围内以为步长重复步骤(2)，进行循环迭代。

(4)当相邻两次匹配结果的差值满足限差时，停止迭代，计算实测磁力值与背景磁力值偏差的均方根。

(5)遍历搜索区内的每一个网格，执行步骤(1)～(4)得到一组实测磁力值与背景磁力值偏差的均方根序列，从该序列中寻找出精度最高的一组对应的格网，该格网的位置即为潜航器当前位置。

上述匹配过程如图7-2所示。

从以上过程可以看出，在遍历每一个格网时，旋转变换经历了一个由粗旋转到精旋转的过程，实现了INS提供航迹到真实航迹的精确校正，从而也实现了实测地磁序列与背景地磁序列的精确匹配，以及载体位置信息的精确获取。

3.试验验证及分析

为检验上述算法相对传统TERCOM算法的优越性，利用某海域地磁实测数据进行了地磁匹配导航仿真试验，试验区域为30km×20km，地磁测量比例尺为1∶5000。对实验区的地磁观测数据进行处理，构建局域地磁场模型，并以50m×50m格网化整个背景场。人为设定INS角偏差为3°，在x和y方向的积累误差为2000m。分别采用上述改进的TERCOM算法和传统的TERCOM算法，进行了匹配导航定位实验。图7-3显示了匹配结果与真实航迹的偏差分布，图7-4显示了两种方法匹配定位后与真实航迹的吻合程度，表7-2给出了匹配后纠正航向与真实航向的偏差。