中国指挥与控制学会会刊 
数据关联是密集回波环境下多目标跟踪中至关重要的一个环节,数据关联算法的好坏直接影响跟踪的效果。联合概率数据关联(JPDA)[1-2]算法是杂波环境下多目标跟踪的一种非常有效的算法,该算法将落入波门的量测都用于目标状态更新过程,并且考虑了各目标对共有量测的竞争,因此该算法能取得较好的关联效果。但也正因如此周密的考虑,随着目标数目以及候选回波数的增多,该算法的计算量急剧增加(指数级增速),导致算法实时性变差,不能满足某些应用场景的时间要求。因此,若能在不降低或略微降低关联性能和滤波精度的同时减少JPDA算法的计算量以提高其实时性将很有意义。
在JPDA算法中,随着目标个数及杂波密度的增大,落入目标波门公共区域的回波数也随之增多,这就导致在对确认矩阵进行拆分时可行关联事件数爆炸式增长,实际上很多可行关联事件的概率是极小的,而这些概率极小的可行关联事件占据了大量的计算时间。
文献[3]首先用PDA[1-2]的方法计算各量测属于各目标的概率并构建聚概率矩阵,将各关联概率与设定概率阈值比较,进而对确认矩阵进行简化,新的确认矩阵减少了很多概率较小的可行关联事件,从而减少了JPDA算法的计算量,但概率阈值的选取不宜过大或过小,因此,不同跟踪环境下的概率阈值应当是不同的,从而限制了该方法的使用。
文献[4]首先利用Cheap JPDA[7] 算法粗略计算关联概率之后,通过设定阈值对聚概率矩阵进行适当的处理并构建新的简化确认矩阵,然后利用标准JPDA算法计算关联概率,但为了提高邻近目标关联正确率,该文献采用了自适应消除方法,去掉概率矩阵中容易引起错误关联的量测,最终在实时性上的提升不太明显。
文献[5]在获得确认矩阵之前对目标空间进行网格的划分与连通,对每个连通域中的目标进行数据关联,得到多个维数较低的确认矩阵,利用每个网格对应的确认矩阵计算关联概率,再分别对每个连通域中的目标采用标准联合概率数据关联算法,最终在关联成功率略微下降的同时大大缩短了运行时间,但网格大小的选取没有一般规则,因此通用性不强。
文献[6]通过合理选取波门门限阈值,去除概率较小的可行关联事件,然后再对落入各目标跟踪门内的公共点迹的互联概率进行衰减,重新计算关联概率,最终在跟踪成功率与标准JPDA相当的同时,计算时间大大缩短。
文献[7]提出了一种经验JPDA(Cheap JPDA)算法,该算法在计算关联概率时对只出现在一个目标波门内的量测作“重”加权,而对同时出现在多个目标波门内的量测作“轻”加权,该方法避免了矩阵拆分的过程,从而在实时性上有较大提升,但由于该算法所得每一条航迹关联概率之和不为1使得不正确回波权系数过高,从而导致关联误差较大。
文献[8]首先计算各量测属于各个目标的后验概率,然后将所有公共量测单独列出,计算公共量测的修正因子以降低其分属各个目标的概率,再利用修正系数及后验概率计算量测与目标之间的关联度并归一化从而得到最终的关联概率,最终在实时性上较标准JPDA算法有较大提升。
文献[9]根据波门内量测的分布和点迹-航迹关联规则构造统计距离,将各目标的预测位置作为聚类中心,采用模糊聚类的方法,计算各候选量测与不同目标关联的概率,最终该算法平均位置估计均方根误差及正确关联率与标准JPDA相当但计算时间大幅缩短。
文献[10]使用了部分联合事件的概念。航迹t1与t2的波门重叠, 并有一个共同回波, 这个事件被视为一个部分联合事件。由于考虑了部分联合事件, 因此相对于一些快速算法而言,该算法精度较高但实时性较差。
本文通过定义滤波参与度,分别考虑了波门中心和量测在滤波更新中所起的作用,在计算某一量测与某一目标的关联概率时利用了类似于PDA的方法,但同时考虑了该目标同其他相关目标对该量测的竞争关系以及该量测同其他相关量测对该目标的归属关系,将归一化后的关联概率乘以滤波参与度即为最终的关联概率。这样处理的好处是避免了复杂的矩阵拆分过程但又考虑了目标及量测之间复杂的归属关系,从而将多目标跟踪问题转化为多个单目标的跟踪问题,因此本文所提算法取得了较为理想的结果。
1 JPDA
1.1 基本原理
PDA对于单目标跟踪可以取得较好的跟踪效果,但是在杂波环境下,当目标个数较多时,这种方法的关联效果不很理想,甚至可能出现误跟。其原因是当目标距离较近,或进行交叉运动时,PDA没有考虑各航迹对落入公共关联区域的量测的竞争。为此,Bar-shalom等人对PDA进行了推广,提出了联合概率数据关联(JPDA)算法,这种方法很好地解决了杂波环境下的多目标跟踪问题。此算法的原理与PDA完全相同,唯一的不同之处在于关联概率的计算。JPDA算法不仅要考虑关联区域内各量测源自目标的概率,还要考虑多条已建目标航迹对公共关联区域内的量测的竞争概率。
1.2 计算关联概率
为了解决候选量测的源的问题,Bar-shalom首先定义了确认矩阵以表示候选量测与各目标关联门的复杂关系。其定义为
Ω=(ωjt), j=1,2,···,mk,t=0,1,···,T
式中,mk为量测数量,T为目标数量。t=0对应没有目标的情形,因此ωjt的第一列全为1,这是因为所有候选量测均可能源自杂波。ωjt=1表示量测j与目标t相关联,ωjt=0表示量测j不与目标t关联。在关联门重叠的区域,量测可能与多个目标关联,此时ωjt中的某一行或某几行除第一列以外有多个元素的值为1。
前述提及JPDA与PDA的本质区别在于关联概率的计算,在JPDA算法中,可以将关联概率表示为
βjt= P{θi/Zk} (θi)
式中,βjt为第j个量测源自第t个目标的概率;P{θi/Zk}为第i个可行关联事件θi的后验概率。Zk为到k时刻的累积量测集合; (θi)为第i个可行关联事件θi所对应的互联矩阵 (θi)中量测j与目标t的关联状态,若在此事件中量测j来自目标其值为1,否则为0。
可行关联事件θi表示的是所有候选量测与所有目标相互关联的一种可能。可行关联事件需满足两个假设:
1)同一量测只能来自一个目标(包括虚警);
2)同一目标只能对应一个量测。
由可行关联事件的定义可知,在θi所对应的互联矩阵 (θi)中, (θi)中每行元素之和为1,除第一列以外,每一列的元素之和小于等于1。
对于参数模型[1]而言,第i个可行关联事件θi的后验概率:
P{θi/Zk}= [Ntj(Zj(k)) ((1-
式中,λ为杂波密度;c为归一化常数,其值为k时刻所有可行关联事件对应的联合概率密度之和;Φ为可行关联事件θi中的虚假量测数;v为k时刻所有目标关联门体积之和;Ntj(Zj(k))为量测j源自目标t时所对应的概率密度。
Ntj(Zj(k))=N[Zj(k);Zj(k)- (k|k-1);St(k)], (k|k-1)为k时刻目标t的预测量测,Zj(k)- (k|k-1)为量测新息,St(k)为新息协方差。即Ntj(Zj(k))服从以量测新息Zj(k)- (k|k-1)为均值,St(k)为方差的高斯分布。τj为量测指示器,当量测j分配给一个真实目标时其值为1,否则为0; 为目标t的检测概率;δt为目标指示器,当有量测分配给目标t时,其值为1,否则为0。
1.3 滤波更新
得到关联概率βjt后即可对各个目标运动状态及相应的协方差的进行更新,具体过程如下:
状态预测:
(k|k-1)=Ft(k-1) (k-1|k-1)
量测预测:
(k|k-1)=Ht(k) (k|k-1)
协方差预测:
Pt(k|k-1)=Ft(k-1)Pt(k-1|k-1)Ft(k-1)T+Qt(k-1)
新息协方差:
St(k)=Ht(k)Pt(k|k-1)Ht(k)T+Rt(k)
滤波增益:
Kt(k)=Pt(k|k-1)Ht(k)TSt(k)-1
新息:
(k)=Zj(k)- (k|k-1)
组合新息:
(k)= βjt (k)
状态更新:
(k|k)= (k|k-1)+Kt(k) (k)
估计协方差更新:
Pt(k|k)=β0t(k)P(k|k-1)+(1-β0t(k)) (k|k)+dPt(k)
其中,
(k|k)=Pt(k|k-1)-Kt(k)St(k)Kt(k)T
$d P^{t}(k)=K^{t}(k)\left[\sum_{j=1}^{m(k)} \beta_{j t}(k) \tilde{z}_{j}^{t}(k) \tilde{z}_{j}^{t}(k)^{\mathrm{T}}-\tilde{z}^{t}(k) \tilde{z}^{-t}(k)^{\mathrm{T}}\right] K^{t}(k)^{\mathrm{T}}$
2 改进算法
JPDA算法中对确认矩阵进行拆分的本质是为了求解每一个量测源自每一批目标的概率。本文的基本思想是跳过矩阵拆分过程而直接计算各候选量测源自每一批目标的概率,这样一来,多目标数据关联问题就能够化作多个单目标的数据关联问题。
在滤波更新过程中,波门中心和候选量测对最终的滤波结果都会产生影响。为此,首先定义:
滤波参与度:滤波参与度分为波门中心参与度和量测参与度,分别用a1,a2表示,代表的是在每次更新中波门中心和量测所起的作用。
对单个目标而言,当波门内的所有量测全为杂波(包括其他目标的回波)时,波门中心参与滤波,否则量测参与滤波。假设在某一周期中,某一目标波门中共有n个回波,该n个回波要么全为杂波,要么有一个源自该目标,其余为杂波。
在假定落入目标波门的杂波个数服从泊松分布的情况下(即杂波数服从参数为λV的泊松分布,其中,λ为杂波密度,V为波门“体积”),波门中出现n个杂波和n-1个杂波的概率分别为:
P{N=n}=
P{N=n-1}=
其中,N代表杂波的个数。
考虑到检测概率PD和门概率PG的影响,滤波参与度可用下式表示:
a1=P{N=n}(1-PDPG)
a2=P{N=n-1}PDPG
归一化后,有
a1=
a2=
当量测参与滤波时,各量测对目标状态更新的贡献是不同的,离波门中心近的量测贡献较大,离波门中心远的量测其贡献较小,而对于量测落入公共波门的情况还需要考虑各目标对量测的竞争。
首先,计算各目标的候选量测与波门中心的统计距离:
dij= vij
其中,i(i=1,···,mk)对应候选量测中的第i个量测,j(j=1,···,T)对应第j批目标,vij为量测i与目标j预测量测的新息,Sj为目标j对应的新息协方差。
构建量测与目标的互联矩阵D={Dij}:
Dij=
由上式可知D每行之和不为0而每列之和可能为0,因此某一量测属于各目标的概率为
=Dij/ Dij
某一目标拥有各量测的概率为
=
再将Pt与Pm中的对应元素相乘得到Pc,此时得到的Pc既考虑了目标对量测的竞争,又考虑了量测对目标的竞争,再对Pc的列进行归一化,有
=
最终,各候选量测与各目标的关联概率为
βij=a2(j)
同时,没有量测与目标j关联的概率为
β0j=a1(j)
其中a1(j)、a2(j)分别表示第j个目标对应的波门参与度和量测参与度。
计算完关联概率后,即可按照标准JPDA算法的滤波过程完成对目标的状态估计。
3 数值仿真
3.1 性能指标
为了便于比较分析,首先给出几个性能指标的定义及计算方法。
单步耗时:单步耗时是指一次完整仿真实验中每个采样周期平均花费的时间,计算公式为
Taver=
其中,Taver为每周期平均花费的时间也即单步耗时,Tall为一次完整仿真实验中总共花费的时间,N为采样周期数。
误跟率:误跟率是指在多次Monte Carlo仿真实验中目标滤波轨迹严重偏离真实轨迹的航次占总航次的比率,假设目标滤波轨迹最终与真实轨迹的偏差大于三倍量测误差即认为发生误跟。误跟率计算公式为
False-rate=
其中,False-rate代表误跟率,False-num代表误跟航次,MC-num代表Monte Carlo仿真次数,Tn代表目标数。
均方根误差:均方根误差指的是估计值与真值偏差的平方之和与Monte Carlo仿真次数n比值的平方根。均方根误差能够很好地反映估计精度。均方根误差计算公式为
RMSE=
其中,RMSE为均方根误差,Xi为第i次仿真的估计值,X为真值,n为仿真次数。
3.2 态势设置
为了比较改进算法(MJPDA)与标准算法(JPDA)及经验算法(Cheap JPDA)的性能,本文在相同环境下对三种算法进行Monte Carlo仿真实验。目标批数分别为2、4、6,采样周期为10s,检测概率PD=0.9,杂波服从均匀分布且密度λ=0.3,量测误差协方差R=diag([80 80])。目标初始状态如表1 所示。
表1 目标初始状态 |
| 目标 | x/m | /(m·s-1) | y/m | /(m·s-1) |
|---|---|---|---|---|
| 1 | 15330 | -6 | 25693 | -8 |
| 2 | 16374 | -8 | 24363 | -6 |
| 3 | 16869 | -10 | 22821 | -3 |
| 4 | 16801 | -10 | 21274 | 1 |
| 5 | 16227 | -9 | 19913 | 4 |
| 6 | 15262 | -7 | 18888 | 7 |
目标真实运动轨迹分别如图1 、图2 、图3 所示。
3.3 均方根误差对比
以四批目标的情形为例,三种算法在100次Monte Carlo试验中的位置均方根误差(仅考虑三种算法均未出现误跟的情况)如图4 至图7 所示。
3.4 误跟率对比
三种算法的三组100次以及一组10000次的Monte Carlo实验误跟率统计结果如表2 、表3 所示(λ=0.3),不同杂波密度下100次Monte Carlo实验的误跟率如表4 所示。
表2 三组100次实验误跟率(%) |
| 目标 批数 | 2 | 4 | ||||
|---|---|---|---|---|---|---|
| 组次算法 | 1 | 2 | 3 | 1 | 2 | 3 |
| JPDA | 1.50 | 2.00 | 0.50 | 2.50 | 1.50 | 3.75 |
| MJPDA | 2.00 | 2.50 | 2.00 | 3.75 | 1.75 | 5.50 |
| CheapJPDA | 4.00 | 5.00 | 3.50 | 6.50 | 4.00 | 10.00 |
表3 10000次实验误跟率(%) |
| 目标批数算法 | 2 | 4 |
|---|---|---|
| JPDA | 2.74 | 2.78 |
| MJPDA | 3.30 | 3.93 |
| CheapJPDA | 5.14 | 7.18 |
表4 误跟率与目标数及杂波密度的关系(%) |
| 目标 批数 | λ=0.2 | λ=0.3 | ||||
|---|---|---|---|---|---|---|
| JPDA | M JPDA | Cheap JPDA | JPDA | M JPDA | Cheap JPDA | |
| 2 | 0.50 | 1.00 | 2.50 | 1.50 | 2.00 | 4.00 |
| 4 | 2.50 | 3.50 | 6.00 | 3.75 | 5.50 | 10.00 |
| 6 | 3.67 | 6.83 | 12.33 | 6.17 | 9.50 | 15.17 |
3.5 实时性对比
不同目标数、不同杂波密度下三种算法的单步耗时如表5 所示。(各目标航迹相交于同一点,相邻航迹之间的夹角为20°)
表5 单步耗时与目标数及杂波密度的关系(单位:s) |
| 目标 批数 | λ=0.2 | λ=0.3 | ||||
|---|---|---|---|---|---|---|
| JPDA | MJPDA | CheapJPDA | JPDA | MJPDA | CheapJPDA | |
| 4 | 0.0093 | 0.0031 | 0.0029 | 0.0100 | 0.0044 | 0.0041 |
| 5 | 0.0139 | 0.0039 | 0.0036 | 0.0155 | 0.0056 | 0.0053 |
| 6 | 0.0216 | 0.0051 | 0.0048 | 0.0233 | 0.0067 | 0.0063 |
| 7 | 0.0347 | 0.0053 | 0.0050 | 0.0373 | 0.0077 | 0.0074 |
| 8 | 0.0583 | 0.0060 | 0.0057 | 0.1298 | 0.0091 | 0.0086 |
| 9 | 0.1132 | 0.0073 | 0.0068 | 0.1369 | 0.0100 | 0.0096 |
| 10 | 0.2890 | 0.0092 | 0.0086 | 0.2742 | 0.0112 | 0.0107 |
| 11 | 0.6478 | 0.0101 | 0.0095 | 0.8783 | 0.0126 | 0.0120 |
| 12 | 1.4523 | 0.0114 | 0.0111 | 1.8851 | 0.0138 | 0.0132 |
| 13 | 4.5382 | 0.0126 | 0.0122 | 16.4531 | 0.0147 | 0.0142 |
为了更进一步考察改进算法的实时性,在杂波密度λ=0.3的条件下,分别对50、100、200、500批目标的单步耗时做了统计(标准算法耗时太久因此未作统计),结果如表6 所示,同表5 中的情况类似,CheapJPDA算法的单步耗时比本文所提算法略短。
表6 改进算法单步耗时与目标数的关系 |
| 目标数 | 单步耗时/s |
|---|---|
| 50 | 0.0834 |
| 100 | 0.1621 |
| 200 | 0.8438 |
| 500 | 5.4298 |
4 结束语
本文提出了一种JPDA改进算法,该算法避免了复杂的矩阵拆分过程,简化了关联概率的计算过程。仿真实验表明,改进算法在关联精度、误跟率方面虽比标准算法稍差,但基本相当,而在实时性上的改善非常明显。同时本文还将改进算法与比较经典的CheapJPDA算法进行了比较,结果表明本文所提算法在实时性方面与CheapJPDA几乎完全一致,在正确关联的条件下两种算法的位置均方根误差相当,但在误跟率方面本文所提算法表现较好。在目标数目较多、回波密集的情况下,改进算法在实时性方面较标准算法的优势更为明显,当目标数多至数百批时改进算法的实时性依然表现良好,满足实时性要求。针对回波密集的应用背景,本文所提算法具有一定的应用价值。