基于Murty方法的多目标跟踪快速算法

基于Murty方法的多目标跟踪快速算法

第!"卷第!期!(()年*月

宇航学报

+$,-./%$0123-$./,3452

#$%&!"’$&!6/-57!(()

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

基于!"#$%方法的多目标跟踪快速算法

刘志刚，卢焕章，陈辉煌

（国防科学技术大学1<=实验室，长沙)>((;*）

摘要：+?@1是一种有效的多目标跟踪算法，但算法的复杂度随着目标和观测值的增加而显著增长。为了减

少+?@1算法所需要的存贮空间和计算时间，通过6,-3A方法，得到B个最优的目标与观测值对应关系，再利用这B个最优对应关系实现+?@1算法。仿真结果表明，新算法跟踪成功率与+?@1相近，所需的时间远低于+?@1算法。

关键词：+?@1；6,-3A算法；多目标跟踪中图分类号：<?;"

文献标识码：1

文章编号：>(((8>*!:（!(()）(!8(>9C8()

&引言

多目标环境中，在多个目标距离较近，并且有杂

而跟踪性能与+?@1相比下降不大。’

算法思想

波的情况下，要实现正确的多目标跟踪非常困难，主要问题是难以找出正确的目标与观测值（包括目标观测值与杂波观测值）之间的对应关系。解决这个问题的方法有多假设跟踪（6,%34D%EFAD$37E242<-/5G8简称6F<）、概率数据关联（?-$I/I4%43A@/3/122$84.H，

简称?@1）以及联合概率数据关联（+$4.354/34$.，

简称+?@1）。6F<是一种?-$I/I4%43A@/3/122$5/434$.，

理论上最优的算法，由于其过于巨大的存贮和计算要求，实际系统中不用这种方法。?@1主要用于单目标跟踪，当多个目标距离较远时，性能不错，而当多个目标距离较近时，由于没有考虑目标之间的相互影响，性能效差。+?@1在实际工程中用得最多。+?@1的原理是先找出所有的目标与观测值的对应

关系，再根据所有对应关系综合得到每个观测值与某个目标的隶属概率，最后得到一个综合观测值用于某一目标的跟踪。当目标与观测值增多时，它们的对应关系呈指数级增长。为了解决这一问题，学

［"，9］者们提出了很多不同的方法，大体上是对多个

+?@1算法的关键是计算出跟踪区域内每个观

测值!与目标"的隶属概率!!"。!!"为所有含有观测值!的对应关系的概率和，当目标与观测值数目较多时，它们之间的对应关系的数目呈指数级增长，对于存贮空间和计算能力都有限的一个系统而言，这是无法忍受的。由于!!"是含有观测值!的对应关系的概率和，而影响!!"值大小的主要是那些大概率的对应关系，即!!"近似等于含有观测值!的大概率对应关系的概率和。令!#!"等于含有观测值!的$个最大概率对应关系的概率和，$的大小由系统资源决定，系统的存贮空间和计算能力大时，可以

#取大的$值。$越大，当$为目标!!"的值越接近；

#

与量测的所有对应关系的数目时，!!"等于!!"。

要从目标与观测值的所有对应关系中找出B个最大概率的对应关系，直观方法是先计算出所有对应关系的概率，然后通过比较找出B个最大值，但这没有任何意义，因为求B个最大概率对应关系就是为了避免计算所有的对应关系的概率。6,-3A方法是一种不必计算全部任务分配，就可求出B个最优任务分配的算法。J$K在［!］中用6,-3A方法来求6F<中的B个最优假设。本文使用6,-3A方法来求+?@1中的B个概率最大的对应关系。

下面是G时刻新算法的处理过程：

找出G时刻各个目标的预测点跟踪窗口内的>）

观测值，建立权值矩阵!（"4L）

目标的公共观测值进行加权处理，这些方法虽然减少了存贮量和计算量，但目标密集时，性能下降较快。

［>］

方法，在不必计算所有目标与本文利用6,-3A

观测值对应关系的情况下，得到B个概率最大的目

标与量测的对应关系，再利用这B个对应关系进行+?@1跟踪。这一方法降低了存贮要求与计算时间，

收稿日期：修回日期：　!((*8(98(9，!((*8(:8!;

基于Murty方法的多目标跟踪快速算法

+ID

宇航学报第!*卷

通过"#$%&方法，找出’个最优的目标与观!）

测值对应关系

计算’个最优目标与观测值对应关系的后(）

验概率

计算出各个量测点与观测值的隶属概率!!)）"#

表+

01234+

对目标航迹进行状态更新*）

算法的关键部分是+）和!），即权值矩阵的建立和"#$%&方法的使用。假设有,个目标和"个观测值，建立如下对应权值矩阵!（"-.）。

目标/观测值权值矩阵

54-67%81%$-924%:44;%1$64%<1;=841<#$484;%<

权值矩阵的前$列是目标与实际观测值的权值，（&，’）("

由于目标可能漏检，特增加%个量测，$>&代

表目标&的漏检观测值。从表+可以看出，从$>+列到$>%列是一个对角矩阵。

（&，’）("

{

&

［（］观测值’落在目标&%*,-），3;)

的有效范围之内#

观测值’落在目标&的有效范围之外?，

（+）

A

{

&），（+)*+’($/&)3;

其它?，

（!）

&

是目标&的检测概率，其中#表示杂波密度，*+&&

［（］［,（；（，］服从高%@%,-B-C+）.（-）&,’-）’-）

在建立权值矩阵之后，用"#$%&方法找出’个

最优目标与观测值对应关系，由于权值矩阵中的元素是取自然对数后的值，求’个最大概率的对应关系等效于从矩阵中找出’个最小任务分配。方法如下：

斯分布，表示量测-时刻量测’相对目标&的统计距

A&&

离。,（-B-C+）是目标&在-时刻的预测点，（.-）为目标&在-时刻的新息协方差。

+

利用匈牙利算法（详细过程参考［E］）求得最优分配.D，，〈!，，〈(，，…，〈%，，），其中〈&，从权值矩阵$D，（〈+，.D@’!〉’(〉’%〉’&〉’+〉

%

表示目标&对应的观测值是’&。’+，…，表示权值和!"（&，最小。’!，’%互不相同。.D是最优分配，’&）

&(+

!()

把〈$D，加入到权值矩阵0分配集合中.D〉清空最优分配集合

FG$-@+%G’，

〈$，.〉)1+从权值矩阵0分配集合中找出权值和最小的)1!)1()1)

从权值矩阵0分配集合中去掉〈$，.〉把.加到最优分配集合中

对于.中的每一个目标关联〈&，，’〉)1)1+)1)1!)1)1()1)1))1)1*

在$!@$

（&，在$!中，令"’）@?

利用匈牙利算法求$!的最优分配.!

如果.!存在

加到权值矩阵0分配集合〈$!，.!〉)1)1)1+把

除了"（&，本身外，令"（#，…%，令"（&，…，从$中，’）’）@?，#@+，!，#"&；2）@?，2@+，!，$>%，2"’

在找出权值矩$的3个最优分配之后，令.是3个，〈!，，〈(，，…，最优分配中的一个，（〈+，’!〉’(〉.@’+〉〈%，），’%〉.的后验概率为：

（)（.4,）(49H*

5

-

$

%

（&，）’&）"!&(+

（(）

式中5是规一化常数。观测值"对应于目标#的

隶属概率是：< …… 此处隐藏：4101字，全部文档内容请下载后查看。喜欢就下载吧 ……