中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2020 , Vol. 42 >Issue 2: 18 - 22

DOI: https://doi.org/10.3969/j.issn.1673-3819.2020.02.004

Information Fusion

Passive Multi-Sensor Multi-Target Tracking Method Based on Multi-Dimensional Assignment

  • BU Shi-zhe 1, 2 ,
  • ZHOU Gong-jian 1, 2
Expand
  • 1. Harbin Institute of Technology, Harbin 150001
  • 2. Key Laboratory of Marine Environment Monitoring and Information Processing, Ministry of Industy and Information Technology, Harbin 150001, China

Received date: 2019-10-22

  Online published: 2022-04-28

Copyright

Copyright reserved © 2020
Fold

Abstract

Data association is the key to solve multi-sensor multi-target tracking problem, the source of the multi-sensor measurements can be determined after the process of data association. In passive multi-sensor systems, only angular measurements are available, and data association processing is more challenging. To address this issue, a new data association method based on multi-dimensional assignment is proposed in this paper to solve the multi-sensor multi-target tracking problem. Firstly, multi-dimensional assignment process is used to solve the multi-sensor measurement-to-measurement association problem, and the multi-sensor measurements from the same target are collected. The position information of targets is calculated using these associated measurements under the maximum likelihood estimation criterion. Secondly, the association problem between the position maximum likelihood estimates of targets and the multi-target tracks is solved according to the two-dimensional assignment process, the multi-target tracks are updated using the associated position estimates. Monte Carlo simulation results demonstrate the performance of the proposed method and show this method can solve the passive multi-sensor multi-target tracking problem with low calculation load added and high precision.

Key words： multi-target tracking; passive multi-sensor; multi-dimensional assignment; data association

Cite this article

BU Shi-zhe , ZHOU Gong-jian . Passive Multi-Sensor Multi-Target Tracking Method Based on Multi-Dimensional Assignment[J]. Command Control and Simulation, 2020 , 42(2) : 18 -22 . DOI: 10.3969/j.issn.1673-3819.2020.02.004

在多传感器多目标跟踪领域中,为了有效利用多传感器观测数据提高目标状态估计精度,需要确定各传感器观测数据的目标来源,即进行将数据关联处理。从20世纪60年代开始,已有文献对数据关联问题进行研究,发展出一系列算法[1,2,3,4],这些算法在复杂度和跟踪性能上各不相同。
解决多传感器多目标数据关联问题的方法有最近邻法(NN)[5],联合概率数据关联(JPDA)[6]以及多假设跟踪(MHT)[7]等。其中,最近邻法是最简单的数据关联解决方案,该方法将统计意义上与目标预测位置最近的观测数据作为关联上的观测数据,仅适用于信噪比高且目标密度低的场景,在实际应用中效率低。JPDA方法通过最后一帧扫描中观测数据的一对多和多对一关联关系计算概率来解决数据关联问题,适合杂波少的环境。MHT方法试图考虑所有的关联假设以提供最优的解决方案,但直接实施MHT方法会导致关联假设数量随时间呈指数增长。为了满足MHT方法的计算量要求,需利用截断技术减少不太可能的假设数量。除此之外,多维分配(MDA)技术[8,9,10]是解决数据关联问题的另一类方案。利用该技术可将多目标跟踪中的数据关联问题描述为一定条件下的离散优化问题,可通过有限长度的滑窗处理逼近MHT跟踪性能,避免了MHT算法中的暴力穷举,它被证明是一种实用可行的MHT的替代选择。
本文基于多维分配方法开展被动多传感器多目标跟踪方法的研究。在被动多传感器多目标跟踪中,传感器只能获得目标的角度观测数据,只利用角度观测数据进行数据关联处理更具有挑战性[11]。为了实现多目标的有效跟踪,首先要进行多传感器观测数据之间的关联,也称为点迹-点迹关联,利用多维分配处理找出来源于同一目标的观测数据集合,并利用集合中多传感器观测数据在最大似然准则下估计目标位置。在传感器数目大于3时,多维分配问题被判为NP-hard问题,解决此问题的核心是合理利用拉格朗日松弛算法[12,13]对多维分配问题进行降维并寻找满足实时性要求的次优解。随后,利用二维分配方法解决目标位置估计和目标航迹之间的关联问题,也称为点迹-航迹关联,利用关联上的位置估计更新目标航迹,实现多传感器多目标跟踪。

1 问题描述

考虑使用S个传感器的情况,各传感器采样率相同且观测时刻同步,每帧扫描中可得到S个观测数据列表,此时的多维分配问题也称为S维分配问题。假设k时刻传感器s获得ns个观测数据,观测数据 z s i s, is=1,…,ns,来源于目标或杂波。
z s i s= h s ( X p ) + w s i s 来源于目标 z ~ s i s 来源于杂波
其中,Xp是目标p未知的状态, w s i s是服从高斯分布的观测噪声,其均值为零,方差为 σ s 2,各传感器的观测噪声相互独立。虚假观测 z ~ s i s在观测区域内服从均匀分布,传感器的探测概率为 P D s。为了表示传感器对目标的漏检,需要将虚假观测zs0添加到传感器的观测序列中。此时,传感器s在k时刻的观测数据集合为
Zs(k)={ z s i s∈ v ps k, is=0,…,ns}
所有传感器观测数据构成集合Z(k)
Z(k)={Zs(k), s=1,…,S}
从每个传感器观测数据集合中选择一个观测数据构建观测数据的S元组 Z i 1 i 2 … i S,表示可能来源于同一目标p的数据组合。观测数据集合Z(k)可以划分为多个S元组,多传感器数据关联就是找出最有可能来源于同一目标的S元组的集合。

2 观测数据关联的多维分配模型

2.1 S元组代价函数构建

当S元组中的观测数据来源于同一目标p时,对应的似然概率为
p( Z i 1 i 2 … i S|Xp)= ∏ s = 1 S(1- P D s ) 1 - u ( i s )·[ P D sp( z s i s|Xp) ] u ( i s )
其中,u(is)为二值函数,当is=0时u(is)=0,否则u(is)=1。同时,S元组中的观测数据可能来源于杂波,此时的似然概率表示为
p( Z i 1 i 2 … i S|ø)= ∏ s = 1 S 1 ψ s u ( i s )
其中,ψs表示传感器s观测区域的体积。
为每个S元组分配代价函数 c i 1 i 2 … i S,用于表示该元组中观测数据来源于同一个目标代价,可表示为
c i 1 i 2 … i S=-ln p ( Z i 1 i 2 … i S | X p ) p ( Z i 1 i 2 … i S | ø )
将式(4)和式(5)代入式(6),可得代价函数为
c i 1 i 2 … i S= ∑ s = 1 S[u(is)-1]ln(1- P D s)+u(is) 1 2 σ s 2 [ z s i s - h s ( X p ) ] 2 - ln P D s ψ s 2 π σ s
由于多传感器观测数据和目标之间存在相互对应关系,存在下面的约束条件:
ρ i 1 i 2 … i S= 1 { i 1 , i 2 , … , i S } 来源于同一目标 0 其他
利用上述过程完成了多传感器观测数据S元组代价函数的构建。

2.2 多维分配模型的引出

进行数据关联时多维分配模型可看作一定条件约束下的全局离散优化问题,其目标是最小化全局关联代价,即在式(8)的约束条件下找出使得全局关联代价函数最小的S元组的分配结果,完成多传感器观测数据关联处理。由此引出下面的S维分配问题和S个约束集
JS= min ρ i 1 i 2 … i S ∑ i 1 = 0 n 1 ∑ i 2 = 0 n 2… ∑ i S = 0 n S c i 1 i 2 … i S ρ i 1 i 2 … i S
满足以下的约束条件:
∑ i 2 = 0 n 2 ∑ i 3 = 0 n 3 ∑ i 4 = 0 n 4 … ∑ i S = 0 n S ρ i 1 i 2 … i S = 1 , i 1 = 1,2 , … , n 1 ∑ i 1 = 0 n 1 ∑ i 3 = 0 n 3 ∑ i 3 = 0 n 3 … ∑ i S = 0 n S ρ i 1 i 2 … i S = 1 , i 2 = 1,2 , … , n 2 　　　　 ︙ 　　　 ︙ 　　　 ︙ ∑ i 1 = 0 n 1 ∑ i 2 = 0 n 2 ∑ i 3 = 0 n 3 … ∑ i S - 1 = 0 n S - 1 ρ i 1 i 2 … i S = 1 , i S = 1,2 , … , n S
在S≥3时,该问题为NP-hard问题,需用拉格朗日松弛算法对多维分配问题的约束条件进行松弛,通过连续的降维处理将其转化成二维分配问题进行处理。

2.3 约束松弛

定义无约束的拉格朗日乘子集并对其进行初始化。
ur,r=S,S-1,…,3; u r i r=0,∀ir=1,…,nr
初始化二维分配子问题的对偶解为fdual=-∞,S维分配问题的可行解为fprimal=∞。将式(8)中S个约束集的后S-r个约束条件进行松弛,使其服从前r个约束条件,得到r维分配子问题
min ρ i 1 i 2 … i S ∑ i 1 = 0 n 1… ∑ i S = 0 n S( c i 1 i 2 … i S- u ( r + 1 ) i ( r + 1 )…- u S i S) ρ i 1 i 2 … i S+ ∑ i r + 1 = 0 n r + 1 u ( r + 1 ) i ( r + 1 )+…+ ∑ i S = 0 n S u S i S
定义r维分配子问题的代价函数 d i 1 i 2 … i r r和二值变量 w i 1 i 2 … i r r
d i 1 i 2 … i r r= min i r + 1… min i S( c i 1 i 2 … i S- u ( r + 1 ) i ( r + 1 )…- u S i S)= min i r + 1( d i 1 i 2 … i r + 1 r + 1- u ( r + 1 ) i ( r + 1 ))
w i 1 i 2 … i r r= ∑ i r + 1 = 0 n r + 1… ∑ i S = 0 n S ρ i 1 i 2 … i S= ∑ i r + 1 = 0 n r + 1 w i 1 i 2 … i r + 1 r + 1
对约束条件依次进行松弛,直到r=2,则对应的二维分配子问题可描述为
{Jr, w γ k i r *}= min w γ k i r ∑ γ k = 0 N ^ ∑ i r = 0 n r d γ k i r r w γ k i r+ ∑ i r + 1 = 0 n r + 1 u ( r + 1 ) i ( r + 1 )…+ ∑ i S = 0 n S u S i S
满足以下的约束条件:
∑ i r = 0 n r w γ k i r=1; γk=1,2,…, N ^ ∑ i r = 0 N ^ w γ k i r=1; ir=1,2,…,nr
其中,R=2; N ^=n1;γk←{k}k=0,1,…, N ^, r=R,利用广义拍卖算法[14,15]可求得二维分配子问题的对偶解。令 J 2 *=J2,当 w γ k i r *=1时表示γk和ir成功关联, w γ k i r *=0时则表示二者之间无关。初始化 N ^=0,对于分配结果 w γ k i r *=1的集合,进行操作 N ^= N ^+1; γ N ^←{γk,ir},同时计算最优对偶解fdual=max(fdual, J 2 *)。在拍卖算法过程中可求得价值向量 μ r i r,ir=1,2,…,nr,r=3,4,…,S,用于后续拉格朗日乘子的更新。
对偶解为最优解的下界,一般不可行。需要依次附加各维的约束条件,同时对拉格朗日乘子进行更新,获得各维子问题的可行解。通过对偶解和可行解的差值判断是否需要进行迭代。

2.4 约束实施及拉格朗日乘子更新

定义次梯度向量 g ( r + 1 ) i r + 1=1; r=2,…,S-1,用二维分配的结果对次梯度向量进行更新,即对于 w γ k i r *=1:
j=arg min i r + 1 c γ k i r … i S- u ( r + 1 ) i ( r + 1 )-… u S i S
g(r+1)j=g(r+1)j-1
次梯度向量提供了一种衡量约束冲突的机制,用于对拉格朗日乘子进行更新。当取值为0时,表明r+1维子问题中的ir+1只进行一次分配,取值为1表明没有被分配,小于0表明进行了多次分配。完成次梯度向量的求解后,接下来进行r+1维分配子问题可行解的求解及拉格朗日乘子的更新。
在二维问题对偶解基础上,采用式(15)和式(16)获得r+1维子问题可行解 w γ k i r + 1 *及代价值Jr+1,初始化 N ^=0,对于分配结果 w γ k i r + 1 *=1的集合,进行操作
N ^= N ^+1; γ N ^←{γk,ir+1}
并更新拉格朗日乘子
u ( r + 1 ) i r + 1= u ( r + 1 ) i r + 1+ ( J r + 1 a - f dual ) ‖ g r + 1 ‖ 2 2 n r + 1 μ r + 1 i r + 1 ∑ k = 1 n r + 1 μ r + 1 k g r + 1 i r + 1
其中, J r + 1 a为各次迭代中代价值Jr+1的最小值,令R=R+1, r=R,若R<S则进行式(15)~(20)的处理过程。R=S时得S维分配可行解 w γ k i S *和代价值JS及最优可行解fprimal=min(fprimal, JS)。进行处理
N ^=0, N ^= N ^+1; γ N ^←{γk,iS}
从而完成约束松弛和拉格朗日乘子更新过程。

2.5 迭代停止原则

设定S维分配的停止原则,预先给定最小的差值mingap和最大迭代次数maxiter。最优可行解与对偶解的相对差值为
gap=(fprimal-fdual)/|fprimal|
若满足gap<mingap或iter>maxiter,则迭代结束,否则继续进行式(12)~(20)的处理过程。其中{γk;k=1,2,…, N ^}表示对应于同一个目标的S元组观测数据的集合。

3 点迹-航迹关联的二维分配模型

3.1 位置极大似然估计

完成S维分配后,利用得到的S元组中的观测数据计算目标在k时刻位置的极大似然估计
Xp=arg max X ∏ s = 1 S(1- P D s ) 1 - u ( i s )[ P D sp( z s i s|X) ] u ( i s )
式(23)中p( z s i s|X)=N( z s i s;hs(X), σ s 2)满足高斯分布。使得上式获得最大值的变量X即为目标位置的极大似然估计。

3.2 点迹-航迹关联

用得到的目标位置估计建立暂时航迹,待航迹起始后进行点迹航迹的关联,用二维分配方法进行解决。对k+1时刻目标的状态进行预测,即 X ^ k + 1 | k=F· X ^ k | k,其中,F为状态转移矩阵。k+1时刻位置的极大似然估计用 Z ^ k + 1表示,表示目标位置极大似然估计和目标航迹之间关联代价的函数cij表示为
cij=-ln ψ s 2 π σ x σ y+ ( Z ^ k + 1 x - X ^ k + 1 | k x ) 2 2 · σ x 2+ ( Z ^ k + 1 y - X ^ k + 1 | k y ) 2 2 · σ y 2
其中,i=1,…,M表示位置极大似然估计的索引,j=1,…,N表示各个目标航迹的索引,ψs表示传感器观测区域的体积,σx, σy分别表示x和y方向上过程噪声的标准差, Z ^ k + 1 x和 Z ^ k + 1 y分别表示观测数据集在x和y方向上位置的极大似然估计, X ^ k + 1 | k x和 X ^ k + 1 | k y分别表示目标在x和y方向上的预测位置。同时位置极大似然估计和目标航迹之间也存在约束关系ρij,即ρij=1时表示第i个位置极大似然估计与第j个目标的航迹相关联,ρij=0表示未关联。因而,该问题可转换为二维分配问题,可用拍卖算法进行求解,所得分配结果对即为点迹和航迹的关联组合。
目标航迹可用与之关联的点迹进行更新,航迹在更新过程中需设立相应的准则。本算法采用6/10逻辑进行判断,即每隔10个周期对当前所有航迹进行查询,若满足10个周期中至少有6个周期航迹被更新,且最后一个周期航迹被更新,则继续对航迹进行维持。否则,当不满足准则时,停止航迹更新,并对航迹进行撤销,从而实现航迹整个过程的管理。

4 仿真结果及分析

本文以4个被动传感器对区域内4个目标进行跟踪的场景为例进行实验。多传感器进行100次采样,各传感器观测同步且采样周期均为T=1 s,探测概率均为 P D s=0.95,观测噪声标准差为σt=0.5°。4个目标初始状态为(-1 000 m, 0 m/s,-100 m,-10 m/s),(-1 500 m, 15 m/s, 100 m,-8 m/s),(-1 000 m, 15 m/s,1 000 m, 8 m/s)和(400 m, 5 m/s,-400 m,-10 m/s)。拍卖算法的最大迭代次数设为50次。
每一时刻区域内均存在50个呈均匀分布的杂波,用来模拟复杂电磁环境。单次仿真中多目标的跟踪航迹如图1所示。在杂波环境下,利用本文算法可实现多传感器观测数据的正确关联,区域内产生的虚假少,可实现多目标的有效跟踪。为了验证算法的收敛性,本算法还进行50次Monte Carlo仿真,给出多目标位置估计和多目标速度估计的均方根误差(RMSE),如图2和图3所示。
图1 多目标跟踪航迹
图2 多目标位置估计RMSE
图3 多目标速度估计RMSE
由图中结果可看出,多目标位置和速度估计的RMSE均呈现收敛的趋势,且收敛值较小。说明利用多维分配方法能实现多传感器观测数据的正确关联,利用二维分配方法能实现位置极大似然估计和多目标航迹的正确关联,有效利用多传感器观测数据提高目标的跟踪性能。此外,给出各个时刻成功跟踪的目标数以及虚假航迹数,进一步表明本文算法的跟踪效果。如图4,5所示。
图4 成功跟踪目标数
由图4可知,每时刻成功跟踪的目标数逐渐维持在4个,说明本算法在目标跟踪发现方面,能实现对全部目标的有效跟踪。
由图5可知,每时刻的虚假航迹数维持在0.4附近,这说明本算法有较好的虚假航迹剔除能力,能将虚假航迹保持在较低水平。因此,本文算法在未损失目标跟踪发现能力的条件下,维持了较低的虚假航迹数,具有较强分辨目标与虚警的能力,能实现被动多传感器系统中多目标的有效跟踪。

5 结束语

本文提出了一种基于多维分配数据关联方法实现被动多传感器系统中多目标跟踪的有效跟踪。利用多维分配方法通过约束松弛的处理解决多传感器观测数据之间的关联问题,确定来源于同一目标的观测数据的集合,并用集合中的观测数据对目标完整的位置信息进行最大似然估计。二维分配方法用于进行各个位置最大似然估计和多目标航迹之间的关联,用关联上的位置估计更新目标航迹。Monte Carlo仿真表明,本文算法在含有杂波和噪声的环境下,每时刻能保持较高的航迹关联正确率以及较低的虚假航迹数,算法的关联精度高,能实现被动多传感器系统中多目标的有效跟踪。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Cox I J. A Review of Statistical Data Association Techniques for Motion Correspondence[J]. International Journal of Computer Vision, 1993, 10(1): 53-66.

DOI

[2]
Musicki D, Evans R, Stankovic S. Integrated Probabilistic Data Association-finite Resolution[J]. IEEE Transactions on Automatic Control, 1994, 39(6): 1237-1241.

DOI

[3]
Musicki D, Evans R. Joint Integrated Probabilistic Data Association: JIPDA[J]. IEEE Transactions on Aerospace and Electronic Systems, 2004, 40(3): 1093-1099.

DOI

[4]
Pattipati K R, Deb S, Bar-Shalom Y, et al. A New Relaxation Algorithm and Passive Sensor Data Association[J]. IEEE Transactions on Automatic Control, 1992, 37(2): 198-213.

DOI

[5]
Aziz A M. A New Nearest-neighbor Association Approach Based on Fuzzy Clustering[J]. Aerospace Science & Technology, 2013, 26(1): 87-97.

[6]
Chang K C, Chong C Y, Bar-Shalom Y. Joint Probabilistic Data Association in Distributed Sensor Networks[J]. IEEE Transactions on Automatic Control, 1986, 31(10): 889-897.

DOI

[7]
Blackman S S. Multiple Hypojournal Tracking for Multiple Target Tracking[J]. IEEE Aerospace and Electronic Systems Magazine, 2004, 19(1): 5-18.

DOI

[8]
Sathyan T, Sinha A, Kirubarajan T, Mcdonald M. MDA-Based Data Association with Prior Track Information for Passive Multitarget Tracking[J]. IEEE Transactions on Aerospace and Electronic Systems, 2011, 47(1): 539-556.

DOI

[9]
Kreucher C, Shapo B. Multitarget Detection and Tracking Using Multisensor Passive Acoustic Data[J]. IEEE Journal of Oceanic Engineering, 2011, 36(2): 205-218.

DOI

[10]
Sathyan T, Sinha A. A Two-stage Assignment-Based Algorithm for Asynchronous Multisensor Bearings-Only Tracking[J]. IEEE Transactions on Aerospace and Electronic Systems, 2011, 47(3): 2153-2168.

DOI

[11]
Zhou L, He Y, Zhang W H. Study on Data Association Algorithm of Multi-passive-sensor Location System[J]. Journal of Systems Engineering and Electronics, 2005, 16(3): 489-493.

[12]
Deb S, Yeddanapudi M, Pattipati K R, Bar-Shalom Y. A Generalized 2-D Assignment Algorithm for Multisensor Multitarget State Estimation[J]. IEEE Transactions on Aerospace and Electronic Systems, 1997, 33(2): 523-538.

DOI

[13]
Poore A B, Rijavec N. A Lagrangian Relaxation Algorithm for Multidimensional Assignment Problems Arising from Multitarget Tracking[J]. SIAM Journal of Optimization, 1993, 3:544-563.

DOI

[14]
Ouyang C, Ji H B, Tian Y. Improved Relaxation Algorithm for Passive Sensor Data Association[J]. IET Radar Sonar Navigation, 2012, 6(4): 214-250.

[15]
Bertsekas D P. The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem[J]. Annals of Operations Research, 1988, 14(1): 105-123.

DOI

Options
Outlines

/

〈 〉