基于多维分配的被动多传感器多目标跟踪方法

卜石哲,周共健

(1.哈尔滨工业大学,黑龙江 哈尔滨 150001；2.对海监测与信息处理工业和信息化部重点实验室，黑龙江 哈尔滨 150001)

在多传感器多目标跟踪领域中,为了有效利用多传感器观测数据提高目标状态估计精度,需要确定各传感器观测数据的目标来源,即进行将数据关联处理。从20世纪60年代开始，已有文献对数据关联问题进行研究,发展出一系列算法[1-4],这些算法在复杂度和跟踪性能上各不相同。

解决多传感器多目标数据关联问题的方法有最近邻法(NN)[5],联合概率数据关联(JPDA)[6]以及多假设跟踪(MHT)[7]等。其中，最近邻法是最简单的数据关联解决方案,该方法将统计意义上与目标预测位置最近的观测数据作为关联上的观测数据,仅适用于信噪比高且目标密度低的场景,在实际应用中效率低。JPDA方法通过最后一帧扫描中观测数据的一对多和多对一关联关系计算概率来解决数据关联问题,适合杂波少的环境。MHT方法试图考虑所有的关联假设以提供最优的解决方案,但直接实施MHT方法会导致关联假设数量随时间呈指数增长。为了满足MHT方法的计算量要求,需利用截断技术减少不太可能的假设数量。除此之外,多维分配(MDA)技术[8-10]是解决数据关联问题的另一类方案。利用该技术可将多目标跟踪中的数据关联问题描述为一定条件下的离散优化问题,可通过有限长度的滑窗处理逼近MHT跟踪性能,避免了MHT算法中的暴力穷举,它被证明是一种实用可行的MHT的替代选择。

本文基于多维分配方法开展被动多传感器多目标跟踪方法的研究。在被动多传感器多目标跟踪中,传感器只能获得目标的角度观测数据,只利用角度观测数据进行数据关联处理更具有挑战性[11]。为了实现多目标的有效跟踪,首先要进行多传感器观测数据之间的关联,也称为点迹-点迹关联,利用多维分配处理找出来源于同一目标的观测数据集合,并利用集合中多传感器观测数据在最大似然准则下估计目标位置。在传感器数目大于3时,多维分配问题被判为NP-hard问题,解决此问题的核心是合理利用拉格朗日松弛算法[12-13]对多维分配问题进行降维并寻找满足实时性要求的次优解。随后,利用二维分配方法解决目标位置估计和目标航迹之间的关联问题,也称为点迹-航迹关联,利用关联上的位置估计更新目标航迹,实现多传感器多目标跟踪。

1 问题描述

考虑使用S个传感器的情况,各传感器采样率相同且观测时刻同步,每帧扫描中可得到S个观测数据列表,此时的多维分配问题也称为S维分配问题。假设k时刻传感器s获得ns个观测数据,观测数据zsis,is=1,…,ns，来源于目标或杂波。

(1)

(2)

所有传感器观测数据构成集合Z(k)

Z(k)={Zs(k),s=1,…,S}

(3)

从每个传感器观测数据集合中选择一个观测数据构建观测数据的S元组Zi1i2…iS,表示可能来源于同一目标p的数据组合。观测数据集合Z(k)可以划分为多个S元组,多传感器数据关联就是找出最有可能来源于同一目标的S元组的集合。

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

2.1 S元组代价函数构建

当S元组中的观测数据来源于同一目标p时,对应的似然概率为

(4)

其中，u(is)为二值函数,当is=0时u(is)=0,否则u(is)=1。同时,S元组中的观测数据可能来源于杂波,此时的似然概率表示为

(5)

其中，ψs表示传感器s观测区域的体积。

为每个S元组分配代价函数ci1i2…iS,用于表示该元组中观测数据来源于同一个目标代价,可表示为

(6)

将式(4)和式(5)代入式(6),可得代价函数为

(7)

由于多传感器观测数据和目标之间存在相互对应关系,存在下面的约束条件:

(8)

利用上述过程完成了多传感器观测数据S元组代价函数的构建。

2.2 多维分配模型的引出

进行数据关联时多维分配模型可看作一定条件约束下的全局离散优化问题,其目标是最小化全局关联代价,即在式(8)的约束条件下找出使得全局关联代价函数最小的S元组的分配结果,完成多传感器观测数据关联处理。由此引出下面的S维分配问题和S个约束集

(9)

满足以下的约束条件:

(10)

在S≥3时，该问题为NP-hard问题,需用拉格朗日松弛算法对多维分配问题的约束条件进行松弛,通过连续的降维处理将其转化成二维分配问题进行处理。

2.3 约束松弛

定义无约束的拉格朗日乘子集并对其进行初始化。

ur,r=S,S-1,…,3;urir=0,∀ir=1,…,nr

(11)

初始化二维分配子问题的对偶解为fdual=-∞,S维分配问题的可行解为fprimal=∞。将式(8)中S个约束集的后S-r个约束条件进行松弛,使其服从前r个约束条件,得到r维分配子问题

(12)

(13)

(14)

对约束条件依次进行松弛,直到r=2,则对应的二维分配子问题可描述为

(15)

满足以下的约束条件:

(16)

对偶解为最优解的下界,一般不可行。需要依次附加各维的约束条件,同时对拉格朗日乘子进行更新,获得各维子问题的可行解。通过对偶解和可行解的差值判断是否需要进行迭代。

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

(17)

g(r+1)j=g(r+1)j-1

(18)

次梯度向量提供了一种衡量约束冲突的机制,用于对拉格朗日乘子进行更新。当取值为0时,表明r+1维子问题中的ir+1只进行一次分配,取值为1表明没有被分配,小于0表明进行了多次分配。完成次梯度向量的求解后,接下来进行r+1维分配子问题可行解的求解及拉格朗日乘子的更新。

(19)

并更新拉格朗日乘子

(20)

(21)

从而完成约束松弛和拉格朗日乘子更新过程。

2.5 迭代停止原则

设定S维分配的停止原则,预先给定最小的差值mingap和最大迭代次数maxiter。最优可行解与对偶解的相对差值为

gap=(fprimal-fdual)/|fprimal|

(22)

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

3.1 位置极大似然估计

完成S维分配后,利用得到的S元组中的观测数据计算目标在k时刻位置的极大似然估计

(23)

3.2 点迹-航迹关联

(24)

目标航迹可用与之关联的点迹进行更新,航迹在更新过程中需设立相应的准则。本算法采用6/10逻辑进行判断,即每隔10个周期对当前所有航迹进行查询,若满足10个周期中至少有6个周期航迹被更新,且最后一个周期航迹被更新,则继续对航迹进行维持。否则，当不满足准则时，停止航迹更新,并对航迹进行撤销,从而实现航迹整个过程的管理。

4 仿真结果及分析

本文以4个被动传感器对区域内4个目标进行跟踪的场景为例进行实验。多传感器进行100次采样,各传感器观测同步且采样周期均为T=1 s,探测概率均为PDs=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 虚假航迹数

5 结束语

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