在军事和民用领域监视中,如何实时有效地跟踪机动目标,防止误跟或失跟目标,是目标跟踪系统设计的主要目的。多目标跟踪[1]涉及随机统计决策、自适应滤波、神经网络、模糊推理等现代信息处理技术,它的核心问题是如何解决目标和量测之间的关联,即数据关联问题,因为数据关联算法性能的优劣直接影响跟踪系统的整体性能。现代战争环境下的跟踪监视系统,由于各种自然和人为干扰或不确定性的存在,以及目标机动性能的提高,造成数据的强烈模糊性及不确定性,对数据关联技术提出了更高的要求。
在传统的各种数据关联算法中,联合概率数据关联(join probabilistic data association filter,JPDAF)[2, 3]和多假设跟踪(multiple hypothesis tracking,MHT)[4]需要穷举所有可能的关联事件,“量测与目标一一对应”造成了算法计算量与目标和量测数呈指数型增长,甚至造成计算量爆炸。另外,在近距离空间目标、低信噪比和传感器分辨率较低时,这些算法不能满足跟踪要求。R. L. Streit提出的基于期望极大化(expectation maximization,EM)的概率多假设跟踪(probabilistic multiple hypothesis tracking,PMHT)[5, 6]算法,通过批处理、迭代获得目标航迹的最大似然估计。PMHT算法以其对各目标与量测关联的独立性假设,获得目标的最优估计,并且计算量随目标个数增长呈线性增长。同时,由于是一种Bayes框架下的跟踪算法,在概率统计意义下所表现的易扩展特性受到学者们越来越多的关注[7]。C. Rago等在文献[8]提出了Homothetic PMHT (HPMHT)算法,假设一个目标有多个量测模型,将同均值不同量测噪声的多量测模型引入PMHT算法,极大的提高了航迹稳定性。
PMHT算法的缺点是对初始值很敏感,一旦初始值与真实值相差较大,目标误跟踪率增大,跟踪性能下降。本文将HPMHT算法与DA技术[9]相结合,提出了DA-HPMHT算法,该方法利用热力学系统的最大熵原理计算跟踪中的条件概率质量函数,借鉴退火过程,有效减小了对初始值的敏感。仿真结果表明,所提算法的目标与航迹关联成功率比HPMHT算法有明显提高,同时在跟踪精度上也有所提高,证明该算法的有效性。
1 PMHT算法PMHT算法基于EM算法[10, 11, 12],EM算法是在不完备数据条件下,求解待估参数的极大似然值或最大后验概率。假设一个目标可以产生多个量侧,一个量测只能源于一个目标,且量测/目标关联过程相互独立。
假设存在M个目标,xm(t)为第m个目标t时刻的状态,定义X(t)=(x1(t),x2(t),…,xM(t))。设t时刻的量测为Z(t)=(z1(t),z2(t),…,znt(t)),其中znt(t)是t时刻第nt个量测,nt是确认区域内t时刻的量测数。第m个目标的运动模型为
式中:Fm(t)为系统矩阵,Hm(t)为观测矩阵;wm(t)和vm(t)分别为过程噪声和观测噪声,并假定其分别是方差为Qm(t)和Rm(t)、均值为零的高斯白噪声。
考虑到量测的不确定性,定义关联变量K(t)=(k1(t),k2(t),…,knt(t)),量测来源于目标m的先验概率p(kj(t)=m)=πm(t),j=1,2,…,nt,且假设该先验概率是相互独立的。
完备数据对数似然函数的期望为:
式中,n是迭代次数。在n+1次迭代中,X的后验期望可表示为:
PMHT算法由E-Step和M-Step完成。E-Step计算先前参数估计值和量测条件下的完备数据对数似然函数的期望,M-Step求此期望的最大值。
2 DA-HPMHT算法确定性退火DA-EM算法最早由Ueda和Nakano提出[13]。本文将DA-EM应用于HPMHT,可以改善后验关联概率的精确度,使MAP收敛于全局最大,提高对多个目标跟踪的有效性。
2.1 DA-HPMHT算法实现E-Step:
定义后验关联概率:
由PMHT算法的假设条件,所有的wkj(t),j(t)在时刻t是独立的,又由于目标当前状态和量测是给定的,所以wkj(t),j(t)在每拍之间也是独立的。由此得到不可观测数据的条件概率质量函数:
其中全概率公式为
部分概率为
式中,是对量测数据的估计,即
DA-EM算法[14]是将条件概率质量函数写为如下形式:
将(9)式代入(2)式,并引入β得到:
式中:0 < β < 1。当β < 1时,p(K|Z,X(n))的概率密度函数比较平滑,即对X(n)的依赖性较小;当β慢慢增加时,p(K|Z,X(n))的影响增大,同时对X(n)的估计精确性提高;当β=1时,(10)式与(2)式相同。由于先前估计X(n)的精确性增加,DA-EM算法更容易收敛于全局MAP。
由此得到后验关联概率:
完备数据对数似然函数期望:
HPMHT[8]算法是将t次扫描得到的量测来源改为多个具有相同均值Hm(t)xm(t),不同协方差阵κmpRm(t)的混合高斯分布。即把同一个目标用P个目标表示,但这P个目标均属于这同一个航迹。典型值是P=3,κ={1,4,16}。由此得DA-HPMHT的后验关联概率
M-Step:
此步骤求解极大后验意义下QDA(X(n+1);X(n))的最大值。定义
则 。求得合成量测和相对应的量测误差协方差阵分别为
对每一个目标,利用扩展卡尔曼平滑算法得到目标状态xm(n+1) (t)估计值,循环迭代直到收敛。
2.2 实现要点1) 先验概率:
先验概率用来表示量测与目标关联的初始概率。假设该先验概率是相互独立的,即
一般,将先验概率πm(t)设为一恒定值:
式中,Pd为系统的检测概率,V是空间监视区域,λ为杂波密度。
2) β因子的选择
实际应用时,需要寻找一种增加β的方法,这里在每次迭代中设β=n/nmax,其中n是迭代次数,nmax是最大迭代次数。
3) 收敛性
一般情况下,算法经过3~5次的迭代就能收敛,经过10~20次的迭代后xm(n+1)(t)的值基本不会变化,因此可以把迭代次数设为一固定值。
另外,也可通过计算前后2次迭代中状态X的变化值达到收敛,当算法满足(19)式时,则XMAP=X(n+1)。
式中,n表示迭代次数,ε是给定参数,这里取1%,此方法比固定迭代次数的方法效率有所提高,本文采用此方法。
3 仿真分析仿真在直角坐标系二维平面内进行,过程噪声和量测噪声均服从均值为零的高斯分布,过程噪声方差δq2=0.01 m2,量测噪声方差δr2=10 m2。两目标的探测概率都为PD=0.8,杂波密度λ=10-5.5,杂波或虚警的个数服从泊松分布,均匀分布于量测空间,并假定噪声序列和初始状态无关。扫描周期Δt=3 s,仿真步数为30步,Monte Carlo仿真次数为50次,κ={1,4,16}。
跟踪轨迹1:两目标作匀速直线交叉运动,目标1初始位置为x=y=0 m,初始速度为vx=6 m/s,vy=7 m/s,目标2初始位置为x=0 m,y=500 m,初始速度为vx=6 m/s,vy=-6 m/s。跟踪轨迹2:两目标做机动转弯交叉运动,机动角速度取 rad/s,目标1初始位置为x=y=0 m,初始速度为vx=vy=10 m/s,目标2初始位置为x=-400 m,y=200 m,初始速度为vx=10 m/s,vy=-10 m/s。跟踪轨迹3:两目标作匀速直线邻近运动,目标1初始位置为x=0 m,y=300 m,初始速度为vx=6 m/s,vy=-7 m/s,目标2初始位置为x=5 m,y=400 m,初始速度为vx=6 m/s,vy=-7 m/s。仿真中目标的初始值都取均值为真实值,方差为diag([2,0.7,2,0.7])的高斯序列,仿真结果如图 1~图 6。
从图 1和图 2可知,在跟踪匀速直线交叉运动目标和机动转弯交叉目标时,在航迹交叉处和密集杂波处,DA-HPMHT算法没有出现误关联,能很好地跟踪目标。从图 3可知,跟踪匀速直线邻近目标时,在整个扫描周期内DA-HPMHT算法均能正确跟踪两目标,没有出现航迹交叉或航迹偏离。
从图 4~图 6可看出,DA-HPMHT的距离均方根误差很小,表明DA-HPMHT算法对机动和非机动目标、邻近和交叉多目标具有较好的跟踪精度,算法误跟踪率较低。而HPMHT算法距离均方根误差很大,跟踪性能下降。为了进一步验证DA-HPMHT算法的可行性,表 1和表 2分别给出了2种算法在杂波密度依次为10-5、10-5.5和10-6时的运行时间和目标误跟踪率,表中无DA代表HPMHT算法,有DA代表DA-HPMHT算法。
λ/(个·m-2) | 运行时间/s | 误跟踪率/% | |||
无DA | 有DA | 无DA | 有DA | ||
10-5 | 1.170 3 | 1.370 3 | 45 | 6 | |
10-5.5 | 1.101 2 | 1.281 2 | 41 | 4 | |
10-6 | 1.086 7 | 1.199 4 | 33 | 3 |
λ/(个·m-2) | 运行时间/s | 误跟踪率/% | |||
无DA | 有DA | 无DA | 有DA | ||
10-5 | 1.366 5 | 1.466 5 | 61 | 10 | |
10-5.5 | 1.232 3 | 1.432 3 | 57 | 7 | |
10-6 | 1.113 2 | 1.344 2 | 49 | 5 |
从表 1~表 3可以看出,随着杂波密度增大,2种算法运行时间和误跟踪率都相差不大。在实时性方面,DA-HPMHT算法运行时间总体比HPMHT算法略长,这是因为每次迭代加入了 因子的缘故,但并不影响其实时性。在误跟踪率方面,DA-HPMHT算法误跟踪率明显低于HPMHT算法,跟踪效果较好,进入跟踪门内的杂波较少,证明DA-HPMHT算法的有效性,而HPMHT算法误跟踪率很大,难以满足跟踪要求。
λ/(个·m-2) | 运行时间/s | 误跟踪率/% | |||
无DA | 有DA | 无DA | 有DA | ||
10-5 | 1.072 3 | 1.232 5 | 56 | 8 | |
10-5.5 | 1.106 2 | 1.109 3 | 54 | 7 | |
10-6 | 1.114 7 | 1.113 5 | 49 | 4 |
结合确定性退火技术,提出了密集杂波环境下多机动目标跟踪DA-HPMHT算法,对DA-HPMHT算法进行了理论分析和仿真实验,并与HPMHT算法进行了对比。仿真结果表明,在初始值与真实值相差较大的情况下,DA-HPMHT算法对多个机动和非机动交叉、邻近目标都具有较好的跟踪精度和较低的误跟踪率。该算法对初值依赖性低,计算量适中,易于实现,实时性强,具有较好的工程应用价值。
[1] | 耿峰, 祝小平. 一种改进的多传感器多目标跟踪联合概率数据关联算法研究[J]. 系统仿真学报, 2007, 19(10): 4671-4675 Geng Feng, Zhu Xiaoping. Research of Improved Joint Probabilistic Data Association Algorithm for Multisensor-Multitarget Tracking[J]. Journal of System Simulation, 2007, 19(10): 4671-4675 (in Chinese) |
Cited By in Cnki (19) | Click to display the text | |
[2] | Svensson L, Svensson D, Guerriero M, Willett P. Set JPDA Filter for Multi-Target Tracking[J]. IEEE Trans on Signal Processing, 2011, 59(10): 4677-4691 |
Click to display the text | |
[3] | 叶西宁, 潘泉, 陈鸣,等. 密集回波环境下多目标跟踪的一种新算法[J]. 西北工业大学学报, 2004, 22(3):388-391 Ye Xining, Pan Quan, Chen Ming, et al. A New and Better Algorithm for Multitarget Tracking in Dense Clutter[J]. Journal of Northwestern Polytechnical University, 2004, 22(3): 388-391 (in Chinese) |
Cited By in Cnki (7) | Click to display the text | |
[4] | 李爱军, 吴小俊. 一种模糊算法及其在多假设多目标跟踪中的应用[J].计算机工程与应用, 2008, 44(10):224-226 Li Aijun, Wu Xiaojun. Fuzzy Algorithm and Its Application to MHT Multitarget Tracking[J]. Computer Engineering and Applications,2008, 44(10):224-226 (in Chinese) |
Cited By in Cnki (3) | Click to display the text | |
[5] | Streit R L and Luginbuhl T E. A Probabilistic Multi-Hypothesis Tracking Algorithm without Enumeration and Pruning[C]//Proceedings of the Sixth Joint Service Data Fusion Symposium, 1993:1015-1024 |
[6] | Streit R L, Luginbuhl T E. Maximum Likelihood Method for Probabilistic Multi-Hypothesis Tracking[C]//Proceedings of SPIE International Symposium, Signal and Data Processing of Small Targets, 1994, 2235: 5-7 |
Click to display the text | |
[7] | Willett P, Ruan Y, Streit R L. The PMHT: Problems and Some Solutions[J]. IEEE Trans on Aerospace and Electronic Systems, 2002, 38(3):738-754 |
Click to display the text | |
[8] | Rago C, Willett P, Streit R L. A Comparison of the JPDAF and PMHT Tracking Algorithms[C]//Proceedings of the International Conference on Acoustics, Speech and Signal Processing, 1995:357l-3574 |
Click to display the text | |
[9] | Wan F, Mak P U, Mak P I, Vai M I. Robust Deterministic Annealing Based EM Algorithm[J]. Electronics Letters, 2012,48(5): 289-290 |
Click to display the text | |
[10] | Avitzour D. A Maximum Likelihood Approach to Data Association[J]. IEEE Transa on Aerospace and Electronic Systems, 1992, 28(2): 560-565 |
Click to display the text | |
[11] | Wieneke M, Koch W. The PMHT: Solutions for Some of Its Problems[C]//Proceedings of SPIE Conference on Signal and Data Processing of Small Targets, San Diego, CA, 2007, 6699: 1-12 |
Click to display the text | |
[12] | Rago C, Willett P, Streit R L Direct Data Fusion Using the PMHT[C]//Proceedings of the 1995 American Control Conference, 1995:1688-1702 |
Click to display the text | |
[13] | Ueda N, Nakano R. Deterministic Annealing EM Algorithm[J]. Neural Networks, 1998, 11(2): 271-282 |
Click to display the text | |
[14] | David F Crouse, Marco Guerriero, Peter Willett. A Critical Look at the PMHT[J]. Journal of Advances in Information Fusion,2009, 4(2):93-116 |
Click to display the text |