一种避免矩阵拆分的改进JPDA算法

石汪权, 袁富宇, 蒲 勇

(江苏自动化研究所, 江苏 连云港 222061)

一种避免矩阵拆分的改进JPDA算法

石汪权, 袁富宇, 蒲 勇

(江苏自动化研究所, 江苏 连云港 222061)

联合概率数据关联(JPDA)算法是杂波环境下多目标跟踪的一种非常有效的算法,但该算法在目标密集或回波数较多时实时性较差,不能满足某些复杂的多目标跟踪应用场景。针对此问题,提出了一种避免矩阵拆分的改进JPDA算法,简化了关联概率的计算,从而提高了JPDA算法的实时性,仿真实验证明了改进算法的有效性。

数据关联； 多目标跟踪； 矩阵拆分

数据关联是密集回波环境下多目标跟踪中至关重要的一个环节,数据关联算法的好坏直接影响跟踪的效果。联合概率数据关联(JPDA)[1-2]算法是杂波环境下多目标跟踪的一种非常有效的算法,该算法将落入波门的量测都用于目标状态更新过程,并且考虑了各目标对共有量测的竞争,因此该算法能取得较好的关联效果。但也正因如此周密的考虑,随着目标数目以及候选回波数的增多,该算法的计算量急剧增加(指数级增速),导致算法实时性变差,不能满足某些应用场景的时间要求。因此,若能在不降低或略微降低关联性能和滤波精度的同时减少JPDA算法的计算量以提高其实时性将很有意义。

在JPDA算法中,随着目标个数及杂波密度的增大,落入目标波门公共区域的回波数也随之增多,这就导致在对确认矩阵进行拆分时可行关联事件数爆炸式增长,实际上很多可行关联事件的概率是极小的,而这些概率极小的可行关联事件占据了大量的计算时间。

已有诸多文献对JPDA算法进行改进以增强其实时性,改进思路主要分为两种：一种是减少可行关联事件数[3-6]；一种是避免矩阵拆分,简化关联概率的计算[7-10]。

文献[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

(1)

式中，mk为量测数量,T为目标数量。t=0对应没有目标的情形,因此ωjt的第一列全为1,这是因为所有候选量测均可能源自杂波。ωjt=1表示量测j与目标t相关联,ωjt=0表示量测j不与目标t关联。在关联门重叠的区域,量测可能与多个目标关联,此时ωjt中的某一行或某几行除第一列以外有多个元素的值为1。

前述提及JPDA与PDA的本质区别在于关联概率的计算,在JPDA算法中,可以将关联概率表示为

(2)

可行关联事件θi表示的是所有候选量测与所有目标相互关联的一种可能。可行关联事件需满足两个假设:

1)同一量测只能来自一个目标(包括虚警);

2)同一目标只能对应一个量测。

对于参数模型[1]而言,第i个可行关联事件θi的后验概率:

(3)

式中，λ为杂波密度;c为归一化常数,其值为k时刻所有可行关联事件对应的联合概率密度之和;Φ为可行关联事件θi中的虚假量测数;v为k时刻所有目标关联门体积之和;Ntj(Zj(k))为量测j源自目标t时所对应的概率密度。

1.3 滤波更新

得到关联概率βjt后即可对各个目标运动状态及相应的协方差的进行更新,具体过程如下:

状态预测:

(4)

量测预测:

(5)

协方差预测:

Pt(k|k-1)=Ft(k-1)Pt(k-1|k-1)Ft(k-1)T+Qt(k-1)

(6)

新息协方差:

St(k)=Ht(k)Pt(k|k-1)Ht(k)T+Rt(k)

(7)

滤波增益:

Kt(k)=Pt(k|k-1)Ht(k)TSt(k)-1

(8)

新息:

(9)

组合新息:

(10)

状态更新:

(11)

估计协方差更新:

Pt(k|k)=β0t(k)P(k|k-1)+

(1-β0t(k))Pt*(k|k)+dPt(k)

(12)

其中，

Pt*(k|k)=Pt(k|k-1)-Kt(k)St(k)Kt(k)T

(13)

(14)

2 改进算法

JPDA算法中对确认矩阵进行拆分的本质是为了求解每一个量测源自每一批目标的概率。本文的基本思想是跳过矩阵拆分过程而直接计算各候选量测源自每一批目标的概率,这样一来,多目标数据关联问题就能够化作多个单目标的数据关联问题。

在滤波更新过程中,波门中心和候选量测对最终的滤波结果都会产生影响。为此,首先定义:

滤波参与度:滤波参与度分为波门中心参与度和量测参与度,分别用a1,a2表示,代表的是在每次更新中波门中心和量测所起的作用。

对单个目标而言,当波门内的所有量测全为杂波(包括其他目标的回波)时,波门中心参与滤波,否则量测参与滤波。假设在某一周期中,某一目标波门中共有n个回波,该n个回波要么全为杂波,要么有一个源自该目标,其余为杂波。

在假定落入目标波门的杂波个数服从泊松分布的情况下(即杂波数服从参数为λV的泊松分布,其中,λ为杂波密度,V为波门“体积”),波门中出现n个杂波和n-1个杂波的概率分别为:

(15)

(16)

其中,N代表杂波的个数。

考虑到检测概率PD和门概率PG的影响,滤波参与度可用下式表示:

a1=P{N=n}(1-PDPG)

(17)

a2=P{N=n-1}PDPG

(18)

归一化后,有

(19)

(20)

当量测参与滤波时,各量测对目标状态更新的贡献是不同的,离波门中心近的量测贡献较大,离波门中心远的量测其贡献较小,而对于量测落入公共波门的情况还需要考虑各目标对量测的竞争。

首先,计算各目标的候选量测与波门中心的统计距离：

(21)

其中,i(i=1,…,mk)对应候选量测中的第i个量测,j(j=1,…,T)对应第j批目标,vij为量测i与目标j预测量测的新息,Sj为目标j对应的新息协方差。

构建量测与目标的互联矩阵D={Dij}：

(22)

由上式可知D每行之和不为0而每列之和可能为0,因此某一量测属于各目标的概率为

(23)

某一目标拥有各量测的概率为

(24)

再将Pt与Pm中的对应元素相乘得到Pc,此时得到的Pc既考虑了目标对量测的竞争,又考虑了量测对目标的竞争,再对Pc的列进行归一化,有

(25)

最终,各候选量测与各目标的关联概率为

(26)

同时,没有量测与目标j关联的概率为

β0j=a1(j)

(27)

其中a1(j)、a2(j)分别表示第j个目标对应的波门参与度和量测参与度。

计算完关联概率后,即可按照标准JPDA算法的滤波过程完成对目标的状态估计。

3 数值仿真

3.1 性能指标

为了便于比较分析,首先给出几个性能指标的定义及计算方法。

单步耗时:单步耗时是指一次完整仿真实验中每个采样周期平均花费的时间,计算公式为

(28)

其中,Taver为每周期平均花费的时间也即单步耗时,Tall为一次完整仿真实验中总共花费的时间,N为采样周期数。

误跟率:误跟率是指在多次Monte Carlo仿真实验中目标滤波轨迹严重偏离真实轨迹的航次占总航次的比率,假设目标滤波轨迹最终与真实轨迹的偏差大于三倍量测误差即认为发生误跟。误跟率计算公式为

(29)

其中,False-rate代表误跟率,False-num代表误跟航次,MC-num代表Monte Carlo仿真次数,Tn代表目标数。

均方根误差:均方根误差指的是估计值与真值偏差的平方之和与Monte Carlo仿真次数n比值的平方根。均方根误差能够很好地反映估计精度。均方根误差计算公式为

(30)

其中,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 目标初始状态

目标真实运动轨迹分别如图1、图2、图3所示。

图1 两目标真实运动轨迹

图2 四目标真实运动轨迹

图3 六目标真实运动轨迹

3.3 均方根误差对比

以四批目标的情形为例,三种算法在100次Monte Carlo试验中的位置均方根误差(仅考虑三种算法均未出现误跟的情况)如图4至图7所示。

图4 目标1位置均方根误差

图5 目标2位置均方根误差

图6 目标3位置均方根误差

图7 目标4位置均方根误差

3.4 误跟率对比

三种算法的三组100次以及一组10000次的Monte Carlo实验误跟率统计结果如表2、表3所示(λ=0.3),不同杂波密度下100次Monte Carlo实验的误跟率如表4所示。

表2 三组100次实验误跟率(%)

表3 10000次实验误跟率(%)

表4 误跟率与目标数及杂波密度的关系(%)

3.5 实时性对比

不同目标数、不同杂波密度下三种算法的单步耗时如表5所示。(各目标航迹相交于同一点,相邻航迹之间的夹角为20°)

表5 单步耗时与目标数及杂波密度的关系(单位:s)

为了更进一步考察改进算法的实时性,在杂波密度λ=0.3的条件下,分别对50、100、200、500批目标的单步耗时做了统计(标准算法耗时太久因此未作统计),结果如表6所示,同表5中的情况类似,CheapJPDA算法的单步耗时比本文所提算法略短。

表6 改进算法单步耗时与目标数的关系

4 结束语

本文提出了一种JPDA改进算法,该算法避免了复杂的矩阵拆分过程,简化了关联概率的计算过程。仿真实验表明,改进算法在关联精度、误跟率方面虽比标准算法稍差,但基本相当,而在实时性上的改善非常明显。同时本文还将改进算法与比较经典的CheapJPDA算法进行了比较,结果表明本文所提算法在实时性方面与CheapJPDA几乎完全一致,在正确关联的条件下两种算法的位置均方根误差相当,但在误跟率方面本文所提算法表现较好。在目标数目较多、回波密集的情况下,改进算法在实时性方面较标准算法的优势更为明显,当目标数多至数百批时改进算法的实时性依然表现良好,满足实时性要求。针对回波密集的应用背景,本文所提算法具有一定的应用价值。

[1] Bar-shalom Y,Fortman T E.Tracking and data association[M].New York:Academic Press,1988.

[2] 何友,修建娟,关欣.雷达数据处理及应用[M].第3版.北京:电子工业出版社,2013.

[3] 秦卫华,胡飞,秦超英.一种简化的联合概率数据关联算法[J].西北工业大学学报,2005,23(2):276-279.

[4] 李首庆,徐扬.基于自适应聚概率矩阵的JPDA 算法研究[J].西南交通大学学报,2017,52(2):340-347.

[5] 张成宝,曹伟,匡华星.基于网格连通的联合概率数据关联算法[J].电光与控制,2013,20(9):34-36.

[6] 余周, 左现刚, 侯志松.一种改进的联合概率数据关联算法[J]. 火力与指挥控制,2010,35(4):106-110.

[7] Yaakov Bar-Shalom. Multitarget-Multisensor Tracking: Advanced Applications Vol 1. [M]. Norwood, MA: Artech House, 1990.

[8] 贾正望,张华阳.一种基于多目标跟踪的改进概率数据关联算法[J].指挥信息系统与技术,2010,1(3):36-40.

[9] 刘俊,刘瑜,何友,孙顺.杂波环境下基于全邻模糊聚类的联合概率数据互联算法[J].电子与信息学报,2016,38(6):1438-1445.

[10] Roecker J A. A class of near optimal JPDA algorithms [J]. IEEE Trans on AES, 1994,5(2):504-510.

A Modified Algorithm of Joint Probabilistic Data AssociationAvoiding Matrix Splitting

SHI Wang-quan, YUAN Fu-yu, PU Yong

(Jiangsu Automation Research Institute, Lianyungang 222061, China)

The Joint Probabilistic Data Association Algorithm is highly effective for multiple targets tracking in clutter, but its real-time is poor in dense targets or echo environment, so that it can not satisfy some complex scenario of multiple targets tracking. A modified JPDA algorithm is proposed to solve the problem. In the proposed algorithm, the process of splitting the validation matrix is avoided, so the calculation of association probability is simplified and the real-time is improved, simulation results proved the effectiveness of the proposed algorithm.

data association; multiple targets tracking; matrix splitting

1673-3819(2017)06-0047-06

E911；E917

A

10.3969/j.issn.1673-3819.2017.06.011

2017-09-21

2017-10-18

石汪权(1993-),男,湖北黄冈人,硕士研究生,研究方向为多目标数据关联技术。袁富宇(1964-),男,研究员,博士生导师。蒲 勇(1981-),男,硕士,高级工程师。