基于分段序列离散度的异步航迹关联算法

衣晓，杜金鹏

海军航空大学，烟台 264001

在分布式多传感器多目标跟踪系统[1-2]中，航迹关联(即判断航迹“同源”)是进行信息融合的基础。然而传感器开机时机或采样周期的不同往往导致航迹是异步不等速率[3-4]的，这增大了航迹关联的难度。

为解决此问题，文献[5]提出一种基于最小二乘法的关联算法；文献[6]利用顺序成对关联思想，将关联问题转化为广义似然比检验；文献[7]借助变异蚁群算法解决了最小二乘多维分配问题。文献[8]组合距离分布直方图特征，引入机器学习进行特征提取，对航迹插值处理进行时间对齐；文献[9]利用滤波插值补偿全局估计，构造反馈序列，进行自适应航迹关联。文献[10]利用插值重构，将测量值与滤波值统一，用伪测量校准时间后再使用经典分配法进行关联。通过衡量航迹集合之间的最优次模式分配(OSPA)距离[11]，文献[12]提出一种基于滑窗OSPA距离的航迹关联算法，但对于不等速率采样情况下的异步航迹关联仍需作同步处理。

无论是最小二乘拟合还是拉格朗日插值，异步不等速率航迹关联问题的传统解决思路是先通过时域配准[13]将航迹时刻统一，再利用内插外推的方法得到等长航迹序列进行关联。但时域配准会增加算法运算量，且在同步化过程中，估计值的误差会发生传播，这种传播与滤波误差有一定相关性，难以进行描述和衡量，从而影响关联性能。

文献[14]引入灰理论[15]，用区间灰数表征异步特性，提出了航迹灰关联算法；文献[16]通过区实混合序列变换，将航迹序列灰化，利用灰色系统分析进行关联；文献[17]使用动态时间规划，从整体上考虑航迹形状的相似性进行关联。文献[18]则将不同航迹公共测量时间区间划分为时间窗，计算时间窗权重，应用D-S证据理论或Bayes理论进行关联。

文献[16-18]无需时域配准对异步航迹进行关联，但算法均是以航迹间距离为依据，根据航迹整体形状相似性或相对位置进行关联。在实际的航迹交叉、分叉和合并[12,19]现象中，航迹交叉点或航迹分叉合并前后的平行阶段，依靠局部航迹间的距离进行航迹关联往往会导致错误关联。

为避免以局部航迹距离为判据带来的错误关联，本文将航迹序列作为数据集进行处理，利用分段混合航迹序列的离散度来判断2条航迹的接近程度。该方法无需时域配准，未引入新误差，可直接对异步不等速率航迹进行关联，并且航迹序列的分段处理可有效解决航迹交叉、分叉和合并问题。

1 数据集的离散度度量

定义1混合数据集的离散度

对任意2个数值型数据集X={x1,x2,…,xM}和Y={y1,y2,…,yN}，记(X,Y)=X∪Y为混合数据集，称

(1)

为混合数据集的离散度。

式中：n=INTL[M/N]；INTL[x]表示不大于x的最大整数；m=MmodN，ymodx表示y除以x的余数；∪为集合“并”运算。

对数据集X={x1,x2,…,xp}，有

nX={nx1,nx2,…,nxp}

2 基于分段序列离散度的航迹关联算法

2.1 问题描述

假设由2部雷达对公共观测区域内的多个目标进行跟踪，雷达标号为s、w，所得航迹标号集合为

Us={1,2,…,ms},Uw={1,2,…,mw}

(2)

记

(3)

为

(4)

的估计。

由于离散度表征数据离散程度，航迹交叉现象会对判别产生干扰。如图1(a)所示，当航迹l2、l3存在交叉现象时，航迹l1与航迹l2、l3的几何中心w12、w13几乎重合，由于几何对称性，航迹点的离散度基本相同，此时无法判断航迹l2、l3与l1的关联情况。但若如图1(b)所示，将航迹序列分段，则产生的两段子序列几何中心不再重合，航迹l1与航迹l2关于几何中心w12的平均离散度小于航迹l1与航迹l3关于几何中心w13的平均离散度，可以正确判断航迹l1与航迹l2关联。

图1 交叉和分段处理示意图Fig.1 Schematic diagram of cross and segmentation

2.2 不等长航迹序列的分段划分

定义2航迹序列的分段划分

对航迹序列X={x1,x2,…,xM}进行n段划分，可得

如果满足：

则称为航迹序列的分段划分。

由定义2可知，经过划分可将航迹序列分为n段子序列。

假设由2部雷达和1个融合中心构成信息融合系统，对公共观测区域内的多个目标进行跟踪。设T为融合中心的一个处理周期，在第k个处理周期[(k-1)T,kT]内，雷达s,w上报的航迹数目分别为ms、mw。在第k个处理周期内上报的航迹集合ζs(k)记为

设2部雷达异步，采样速率不一致但恒定，则在融合中心的同一处理周期内，2部雷达上报航迹的航迹点数目不同，即航迹序列的长度不同，假设来自雷达s的第i条航迹包含ni个航迹点。由于采样周期不一致，雷达上报航迹的次数亦不同，假设在同一处理周期内雷达s上报a次航迹，来自雷达s第b次上报的航迹集合中第i条航迹记为

在同一处理周期内对多次上报的同批号航迹集合作并集处理，即

处理后雷达s的第i条航迹记为

2) 序列分段时，尽可能保证每个分段航迹子序列所含航迹点数目相等。

3) 尽量避免某分段航迹子序列只包含单一航迹点。

4) 原则优先级为：1) ≻2) ≻3)。

根据以上原则，可保证分段后每组对比子序列航迹点数目之比与原始序列航迹点数目之比基本不变；并确保航迹序列至少分为2段，避免中心交叉问题。

2.3 分段航迹序列离散度的计算

取雷达w的mw条航迹作为比较航迹，雷达s的第i条航迹作为参考航迹。由于每条航迹的航迹点数目不同，根据分段原则，共有mw种分段方式，每种分段方式对应一条比较航迹和参考航迹。

例如在第1个位移分量x上定义分段航迹序列矩阵为Ψx：

(5)

分段航迹序列矩阵Ψx为2mw×nk维，每一行表示每一条航迹在分量x上的分段子序列集合；奇数行元素来源于比较航迹，偶数行元素来源于参考航迹。由于分段数目不同，矩阵各行元素数目不同，故各行缺失元素用0做补齐处理。

根据定义1中对数据集离散度的定义，可计算得到参考航迹和比较航迹的离散度矩阵为

Θx=[δe,f]mw×nk=

(6)

式中：

e=1,2,…,mw;f=1,2,…,nk

(7)

进而可以计算在位移分量x上，来源于雷达s的第i条航迹与来源于雷达w的第j条航迹的离散度，记为

(8)

考虑到位移分量与速度分量具有相关性(导数关系)，并且物理意义的不同导致不同属性分量间的滤波精度不易比拟，故仅采用位移分量进行关联。

同理，可以列出在位移分量y上的分段航迹序列矩阵Ψy，相应求解航迹在位移分量y上的离散度，记为λy。对位移分量的航迹离散度进行加权融合，得到在第k个处理周期内参考航迹i(i∈Us)和比较航迹j(j∈Uw)之间的总离散度为

λij=α1λx+α2λy

(9)

式中：加权系数α1、α2为非负实数，且满足α1+α2=1的约束条件。其数值大小取决于滤波精度，精度越高，权重越大。记状态滤波协方差矩阵中位移分量x、y的滤波误差分别为σx、σy，则加权系数为

(10)

2.4 航迹关联判定

根据所用的指标量离散度λij，可推广为广义经典分配法。对于雷达s、w上报的ms、mw条航迹分别计算离散度，构成ms×mw维矩阵，由此将问题转化为全体航迹的分类问题。

令

(11)

式中:ϑij=1表示航迹i与航迹j关联；ϑij=0表示二者不关联。目标函数记为

(12)

则形成二维分配问题

(13)

此类二维分配问题，存在匈牙利算法、拍卖算法等经典解决方法，此处不再赘述。分配问题的本质为约束条件下求解目标函数最值的问题，求解算法的不同，求解中多义性的具体表现也不尽相同。

(14)

然后按照2.3节重复计算步骤，直至分配方案呈现唯一性。

分段数目的增加会细化数据处理程度，放大局部航迹的离散度差异，提高度量精度，能有效解决多义性问题。算法的流程如图2所示。

图2 算法流程图Fig.2 Flowchart of algorithm

3 仿真验证与分析

3.1 仿真环境

假设由2部异地配置的2D雷达构成的跟踪系统对公共区域进行观测，目标批数为20批，持续观测时间为30 s。雷达1、2位置坐标分别为(0,0) km, (100,0) km，雷达1的采样时间间隔为T1=0.2 s，雷达2的采样时间间隔为T2=0.5 s，并且雷达2比雷达1晚开机0.2 s。

目标运动模型采用二维平面匀速直线运动模型，目标初始方向在0～2π rad内随机分布，目标初始速度在200～400 m/s内随机分布。雷达1的测距和测角误差分别为σr1=150 m、σθ1=0.03 rad；雷达2的测距和测角误差分别为σr2=180 m、σθ2=0.02 rad。

进行M次Monte Carlo仿真实验，采用正确关联率对航迹关联结果进行评价：

(15)

式中：Ci(k)为第k个处理周期内正确关联的航迹数目；M为Monte Carlo仿真实验的次数；N为每次仿真实验的目标航迹数目。

3.2 算法性能比较与分析

在仿真环境中，进行100次Monte Carlo仿真实验。在不同条件下对本文算法与文献[5]中算法和文献[16]中算法进行比较。

图3给出了在仿真环境中3种算法关联结果的比较。可以看出，本文算法的正确关联率最高，但在采样初期，本文算法关联效果较差。这是由于本文算法的离散度属于统计学度量，采样初期数据点较少，对关联的正确性造成了很大影响。

图3 不同算法的正确关联率对比Fig.3 Comparison of correct associating rates of different algorithms

但影响持续时间较短，算法可以很快收敛至最佳关联效果。

在仿真环境的基础上，改变2部雷达的采样频率之比，图4给出了不同采样频率之比对3种算法的影响。本文算法利用同源航迹数据集波动性小的特点进行关联判定，只关乎航迹点的同源性，航迹点数目(满足一定统计学数据量)并不会对关联结果产生影响，故雷达采样频率不一致对本文算法无显著影响。从图4中可以看出，随着采样频率相差越来越大，文献[5]中算法的正确关联率下降较为明显，而本文算法和文献[16]中算法的正确关联率并无明显变化，与理论结果吻合。

图4 关联结果随采样率之比的变化Fig.4 Variation of correlation results with changing ratio of sampling rate

在仿真环境的基础上，根据不同信噪比，改变参数中噪声的幅值，模拟强杂波干扰。从图5中可以看出，随着信噪比的减小，文献[5]中算法的正确关联率迅速下降；本文算法和文献[16]中算法的正确关联率起初并无明显变化，在信噪比低于28 dB后有明显下滑，且文献[16]中算法的下滑趋势较快。

图5 关联结果随信噪比的变化Fig.5 Variation of correlation results with changing SNR

表1给出了不同采样周期和开机时延下本文算法的平均正确关联率。可以看出，采样周期增大，算法正确关联率有小幅度下降；开机时延并未产生明显影响。这是由于采样周期越长，数据量越少，对离散度的刻画越不准确；而一定范围内的开机时延只造成数据点在时间上的错位，并不影响数据分布的离散度。

表2给出了不同噪声分布形式下本文算法的正确关联率。可以看出，噪声的分布形式对本文算法没有影响。综合表1和表2可知，本文算法在多种情景下均保持较高的正确关联率，稳定性较佳。

表1 不同采样周期和开机时延的正确关联率

表2 不同噪声分布的正确关联率

3.3 航迹分叉合并情况的可辨性分析

在仿真环境的基础上，调整目标数目、初始位置和初始速度，模拟目标在二维平面上航迹交叉、分叉和合并的情况。当观测区域中的目标航迹存在大量交叉、分叉和合并现象时，以航迹间距离作为关联依据的传统算法，在交叉点或平行阶段容易发生错误关联。从图6可以看出，文献[5]和文献[16]中算法的正确关联率相较于匀速直线模型有所下降；而本文算法由于不依赖距离进行判定，故仍保持较佳的关联效果。

图6 航迹存在分叉合并时的正确关联率对比Fig.6 Comparison of correct associating rates of track bifurcation merging

图7(a)仿真了航迹分叉过程。在开始时刻雷达s、w所观测2目标进行平行飞行，距离较近，后分别转向，改为独立飞行。图7(b)则仿真了2目标航迹合并过程。开始2目标相距较远，后组成编队平行飞行，距离拉近。

图7 航迹分叉与合并示意图Fig.7 Schematic diagram of track bifurcation and merging

图8仿真了航迹分叉和合并过程中同源航迹{s1,w1}、{s2,w2}和非同源航迹{s1,w2}、{s2,w1}对应的各分段航迹相对离散度的变化趋势。为直观反映本文算法对处理目标运动状态发生突变现象的灵敏程度，细化航迹序列分段为25段予以说明。

图8 分段航迹序列离散度的变化Fig.8 Variation of segmented track sequence dispersion

从图8(a)中可以看出，在目标进行平行飞行时，同源航迹和非同源航迹的相对离散度均较小，无法进行有效的航迹关联。但目标航迹分叉后，同源航迹{s1,w1}、{s2,w2}的相对离散度并未产生变化，而非同源航迹{s1,w2}、{s2,w1}的相对离散度却迅速增大。

同样，从图8(b)中可以看出独立飞行时非同源航迹{s1,w2}、{s2,w1}的相对离散度较大，同源航迹{s1,w1}、{s2,w2}的离散度较小；但随着航迹的合并，非同源航迹的相对离散度迅速下降，接近同源航迹的相对离散度。

从航迹交叉合并现象的仿真实验中可以看出，测度分段航迹离散度的方法可以迅速对航迹状态突变做出反应，即算法在解决航迹状态突变问题中具有灵敏度高的特点。即使航迹存在平行飞行阶段，只要对各分段航迹的离散度取平均，依旧可以进行准确的航迹关联。

3.4 算法复杂度分析

图9给出了3种算法耗时的比较。可以看出，随着目标航迹数目的增加，3种算法的CPU耗时均呈增加趋势，但本文算法耗时高于文献[16]中算法，远高于文献[5]中算法。

图9 不同算法的耗时对比Fig.9 Comparison of time consumption of different algorithms

以等长航迹序列关联为例，假设有m条比较航迹与1条参考航迹进行关联，各航迹均包含n个航迹点，数据类型为实数类型，计算各算法运算量，如表3所示。显然，本文算法运算量要高于文献[16]中算法。

表3 不同算法的运算量Table 3 Calculation amount of different algorithms

4 结 论

1) 本文提出一种基于分段序列离散度的异步航迹关联算法，给出离散度的具体度量指标和不等长航迹序列的分段划分规则，并针对多义性问题给出二次检验方法。

2) 本文算法无需时域配准，可在多种环境下直接对异步不等速率航迹进行准确关联，具有稳定性。算法不受噪声分布的影响，且噪声强度对算法的影响相对较小，具有良好的抗杂波干扰性。

3) 本文算法可有效分辨航迹交叉、分叉和合并等复杂情况。