基于三角形拓扑相似性的航迹关联算法

毛艺帆，　张多林，　王　路

(空军工程大学 防空反导学院， 陕西 西安 710051)



基于三角形拓扑相似性的航迹关联算法

毛艺帆，张多林，王路

(空军工程大学 防空反导学院， 陕西 西安 710051)

针对多个传感器量测航迹在系统误差下关联融合困难的问题，提出基于拓扑4交差模型和三角形拓扑相似度的航迹关联方法，将传感器探测目标分成若干个拓扑三角形结构，使用4交差模型排除不同传感器探测中相关可能性小的三角形；然后定义三角形相似度，对归属于不同探测源的拓扑三角形相似程度进行度量，从而得出目标之间的相关程度，获取航迹关联结果。仿真结果表明，在目标密集编队时，该算法具有有效性。

航迹融合；航迹关联；拓扑4交差模型；三角形相似度

航迹关联是航迹融合中的关键问题，解决了不同航迹是否属于同一目标的问题，是后续信息能够进行可靠融合的基础，是跟踪成功的关键。在分布式信息处理系统中，信息处理子节点提供目标的状态估计航迹；在信息处理中心，对不同节点的航迹信息关联对准，对关联成功的航迹对再进行航迹融合，得到最终的融合结果。现阶段，已有大量的关于航迹融合及航迹关联的研究成果，主要分为基于统计的方法[1-2]、基于模糊理论的方法[3-6]和基于灰色理论的方法[7-8]。这些方法大多只考虑探测的随机误差，未考虑系统误差，且在目标密集编队时，无法在短时间内获取良好的关联效果。因此，需要在现有研究的基础上，发掘新的方法，解决上述问题。

本文首先推导存在系统误差的目标粗相关波门，再将航迹目标进行分割，划分成最简单的拓扑目标——三角形目标进行研究，并通过基于空间拓扑模型进行筛选，通过筛选的目标进行基于三角形相似度比较的精相关，最后结合双门限准则和多义性处理，得到最终的航迹关联结果。

1　目标粗相关波门计算

目标粗相关的思想是根据关联波门，对待关联的目标进行筛选，以便在进一步的关联操作中，摒弃关联波门以外的目标。粗关联可有效减小计算量，提高计算效率[9]。在粗关联中，关联波门的选择是尤为重要的，因此，本文对存在系统误差时的关联波门计算方法进行阐述。

假设有传感器S1、S2对规定区域进行目标探测和跟踪，探测到的目标分别为m和n个；探测到的航迹信息传递到信息融合中心，以融合中心为坐标原点，建立笛卡尔坐标系，取其中两维进行研究，设S1和S2在该坐标系下的坐标为(xs1,ys1)和(xs2,ys2)；将传感器S1所在位置设为融合中心，则其与传感器及任一目标位置关系如图1所示。图中，S1和S2分别表示2个传感器，Target表示目标真实位置，TS1和TS2分别表示传感器的测量值。考虑传感器的系统误差，其测距以及测角系统误差为(Δrs1,Δθs1)和(Δrs2,Δθs2)。

图1　融合中心、传感器及任一目标位置关系示意图

(1)

(2)

(3)

(4)

(5)

(6)

2　基于三角形相似性的航迹相关

2.1目标三角形分割

由于三角形是形状比较简单的拓扑结构，可以很好地反映局部的拓扑结构，而且对大规模的运算而言，运算负担不会很重，其在模式识别方面已经得到广泛应用[10]，因此，本文选择将三角形结构作为拓扑结构元，研究基于目标之间拓扑信息的航迹关联方法。

a) 传感器1中选中的三角形示意图

b) 传感器2中目标点迹三角形组合

a) 传感器2中目标点迹三角形组合

b) 传感器2中目标点迹三角形组合

2.2目标三角形筛选

(7)

式中，Aο表示集合A的内部；Bο表示集合B的内部；∂A表示集合A的边界；∂B表示集合B的边界。该模型可描述多种点/点、点/线、点/面、线/线、线/面、面/面关系。

相对于其他模型(如9交模型等)，4交模型只需计算4个元素，且可表征比较完备的空间目标拓扑关系，其应用比较广；然而要进行4个交运算，运算复杂性比较高。因此，邓敏等[11]46-49提出了一种混合模型——4交差模型，如式(8)所示。较之4交模型，其只需进行2个交运算和2个差运算，显然，差运算比交运算的计算复杂性低；而且，该模型同样可以很好地表征空间目标的拓扑关系。

(8)

若2个拓扑目标相关，则其在空间中的距离不应相距太远，而彼此之间的距离衡量需要定义另外的函数。假设有一个映射函数σ(Δ),其定义如式(9)。进而，定义距离函数，如式(10)所示。

(9)

(10)

例如目标相等和目标相离之间拓扑距离计算过程为

已知

可以看出，目标相等和目标相交、包含、包含于、覆盖、覆盖于这几种关系的距离较近，由于传感器探测到的目标都不是百分百准确的目标信息，所以具有不同程度的模糊性。因此本文认定，当空间目标处于相等、相交、包含、包含于、覆盖、覆盖于这几种拓扑关系时，目标是有相关的可能性的，只是可能性大小不同；反之，当处于相接和相离关系时，认定其是不相关的。根据此方法，排除相关可能性较低的拓扑三角形目标，使用Arcview软件即可实现，并可与Matlab进行数据互通。

2.3三角形相似度度量

已经经过相关筛选的三角形目标，需要进行进一步的处理，才能获取目标关联结果。本文根据目标之间的拓扑相似性来判断目标相关程度。具体来说，当拓扑目标之间的结构相似度越大，则可知构成三角形拓扑结构的目标点之间的关联程度就越高，继而问题转化为如何判断三角形目标相似度。参考文献[14]中对三角形相似度的阐述，定义三角形拓扑相似度为

(11)

2.4双门限准则和多义性处理

某一时刻的目标关联结果并不能作为整体的航迹关联结果，需要经过多次的关联检验，才有可能形成固定的航迹关联对，因此，需要引入双门限准则和多义性处理帮助进行航迹关联判定。

双门限准则[9,15]：选择整数I和R(一般根据经验选值)，∀k=1,…,R时刻，若关联成功，则计数器mij(k)=mij(k-1)+1，mij(0)置0；若经过R次关联检测，计数器值大于门限值I,即mij(R)≥I,则判定目标i和目标j为同一目标，否则，需进入下一检验周期进行关联检测。已经判定为关联的目标对则不需要进行进一步的关联检测。

3　算法流程

5) 对目标进行基于I/R规则的航迹相关检验，并在必要的时候进行多义性处理，得到最终航迹关联对。对已关联航迹对，使用基本加权融合法，得到航迹融合结果。

4　仿真分析

为说明本文方法的有效性，设置如下的基本仿真环境：假设在以融合中心为原点的坐标系中有2个传感器，坐标分别为(0,0)和(0,50)。在2个传感器的重叠观测区域内，有30批目标。传感器的重叠观测区域一般是不规则图形，为了方便对关联方法进行讨论，设置该区域为矩形，目标初始位置随机分布在30km×30km的矩形区域内，目标的初速和初始方位角分别位于20～200 m/s和0～2π rad范围内，目标进行匀速直线运动。随机测量距离误差为50 m，随机测量角度误差为0.5°。假设共同观测概率为1，进行50次蒙特卡罗仿真，每次20步，使用本文的方法和传统的最近邻(Nearest Neighbor,NN)算法进行仿真。为对航迹关联的效果进行度量，定义航迹正确关联概率Pr，Pr=Cr/(Cr+Cw),其中Cr表示正确关联航迹对数目，Cw表示错误关联航迹对数目。I/R逻辑选择3/5规则。设置不同的仿真条件，进行仿真实验。

1) 系统误差范围固定。假设传感器1的系统测量距离和角度偏差最大值分别为100 m和1°，传感器2的系统测量距离和角度偏差最大值分别为100 m和1°。使用本文方法和基本NN关联法以及文献[5]1694-1697中所提的模糊关联法进行仿真实验。在起始时刻，目标真实位置及2个传感器的测量值如图4所示，使用本文的方法，其最终航迹关联结果的局部如图5所示。

图4　初始时刻目标示意图

图5　航迹关联结果局部图

根据本文算法和NN算法，得到正确关联概率如图6。在经过20步的关联检验之后，3种方法的关联正确率均可达到0.9以上，说明在检验步数一定的情况下，3种方法均有效。

2) 系统测角误差不固定。假设传感器1的系统测量距离和角度偏差最大值分别为100m和1°，传感器2的系统测量距离最大值为100 m，其系统测量角度偏差最大值为1°～5°，分别为1°、1.5°、2°、2.5°、3°、3.5°、4°、4.5°和5°。使用本文方法和基本NN关联法以及文献[5]1694-1697中的模糊关联法进行仿真实验，得到正确关联概率如图7。由图可得，随着测角误差增大，NN算法性能下降严重，文献[5]1694-1697的方法也有所下降，且在误差达到5°时关联正确率已经降至0.7，本文方法性能比较稳定，关联正确率仍旧在0.8以上。

3) 系统测距误差不固定。假设传感器1的系统测量距离和角度偏差最大值分别为100 m和1°，传感器2的系统测量角度偏差最大值1°，其系统测量距离偏差最大值为100～500 m，分别为100 m、150 m、200 m、250 m、300 m、350 m、400 m、450 m和500 m。使用本文方法和基本NN关联法以及文献[5]1694-1697中的模糊关联法进行仿真实验，得到正确关联概率如图8。随着测距误差增大，NN算法和文献[5]1694-1697的方法性能均下降严重，说明以上算法对距离误差是比较敏感的，本文算法性能也有所下降，但正确关联概率稳定在0.8以上。

图6　系统误差固定时的关联正确率

图7　系统测角误差变化时的关联正确率

图8　系统测距误差变化时的关联正确率

由以上不同条件的仿真结果可知，首先，在系统误差相差比较大的情况下，能够获取较好的关联效果；进而，在系统误差产生变化时，算法性能稳定，在系统测量误差逐渐增大时，算法的正确关联概率虽然也会逐渐减小，但比较平稳，变化不大，在可接收的范围内。

5　结 束 语

针对现有航迹关联算法对编队飞行及密集目标关联效果较差的问题，提出基于三角形拓扑相似性的航迹关联方法，该方法有别于传统的方法，是解决航迹关联问题的一个有益的尝试，仿真结果也表明本文方法的有效性。然而，本文算法虽然可以解决目标密集的问题，但运算量是一个不得不考虑的问题。在今后的研究中，应着重提升算法的效率，以便在实时性要求比较高的场合能够得到应用。

References)

[1]卢大威, 高彦钊, 晏行伟, 等.基于角度观测关联对的NN-EKF红外/毫米波融合跟踪算法[J]. 弹箭与制导学报, 2011,31(5):4-8.

[2]耿利祥,陈钱,钱惟贤.改进的联合概率数据关联算法(JPDA)对红外目标与诱饵的辨别[J].红外与激光工程,2013,42(2):305-310.

[3]刘德浩,王国宏,陈中华.系统误差下的模糊航迹关联方法[J].现代防御技术, 2012,40(3):128-131；143.

[4]郭徽东,章新华.基于模糊综合函数的航迹关联算法及其应用[J].系统工程与电子技术,2003,25(11):1401-1403.

[5]丁锋,薛磊.基于模糊理论的证据航迹关联算法分析[J].计算机应用研究,2015,32(6):1694-1697.

[6]毛艺帆,王睿,张金成.基于空天信息的异类传感器模糊航迹关联算法[J].空军工程大学学报(自然科学版),2012,13(5):35-39.

[7]闫子豪.基于灰关联分析-模糊推理的目标关联技术[J].华东理工大学学报(自然科学版),2007,33(5):712-715.

[8]李鹏,刘思峰.基于灰色关联分析和D-S证据理论的区间直觉模糊决策方法[J].自动化学报,2011,37(8):993-998.

[9]宋强,熊伟,何友.基于复数域拓扑描述的航迹对准关联算法[J]. 宇航学报, 2011, 32(3):560-566.

[10]赵凤,刘汉强.不同形状邻域空间信息的模糊聚类图像分割[J].计算机工程与应用, 2015,51(10):12-15；35.

[11]邓敏,李志林,吴静.空间关系理论与方法[M].北京:科学出版社,2013.

[12]邓敏.矢量GIS中拓扑关系的扩展模型、理论和方法[D].武汉:武汉大学,2003：85-90.

[13]邓敏,刘文宝,冯学智.GIS面目标间拓扑关系描述的形式化模型[J].测绘学报, 2005,34(1):85-91.

[14]杨哲,韩崇昭,李晨,等.基于目标之间拓扑信息的数据关联方法[J].系统仿真学报,2008,20(9):2357-2360.

[15]宋强,熊伟,马强.基于目标不变信息量的模糊航迹对准关联算法[J]. 系统工程与电子技术,2011, 33(1):190-195.

(编辑：李江涛)

A Track Association Approach Based on Topological Triangle Similarity Degree

MAO Yifan，ZHANG Duolin，WANG Lu

(Air and Missile Defense College, Air Force Engineering University, Xi’an Shaanxi 710051, China)

To solve out the challenges over the track association and fusion with system error when measuring track with multiple sensors, the paper proposes a track association method based on topological 4-intersection-and-difference model and triangle similarity degree. By dividing the detected target of multiple sensors into several topological triangle similarity structures, using 4-intersection-and-difference model, the paper excludes those triangles with small possibility of association , then the paper defines the triangle similarity degree and measures the topological triangle similarity degree so as to draw the relevance among targets and the result of track association. The simulation result shows, the algorithm is effective in case of intensive formation targets.

track fusion; track association; topological 4-intersection-and-difference model; triangle similarity degree

2016-01-25

毛艺帆(1988—)，女，博士研究生，主要研究方向为作战建模与仿真。myf1210@126.com

TP212

2095-3828(2016)04-0069-06

A

10.3783/j.issn.2095-3828.2016.04.015

张多林，男，教授，博士生导师。