石汪權, 袁富宇, 蒲 勇

(江蘇自動化研究所, 江蘇 連云港 222061)

一種避免矩陣拆分的改進JPDA算法

石汪權, 袁富宇, 蒲 勇

(江蘇自動化研究所, 江蘇 連云港 222061)

聯(lián)合概率數(shù)據(jù)關聯(lián)(JPDA)算法是雜波環(huán)境下多目標跟蹤的一種非常有效的算法,但該算法在目標密集或回波數(shù)較多時實時性較差,不能滿足某些復雜的多目標跟蹤應用場景。針對此問題,提出了一種避免矩陣拆分的改進JPDA算法,簡化了關聯(lián)概率的計算,從而提高了JPDA算法的實時性,仿真實驗證明了改進算法的有效性。

數(shù)據(jù)關聯(lián)； 多目標跟蹤； 矩陣拆分

數(shù)據(jù)關聯(lián)是密集回波環(huán)境下多目標跟蹤中至關重要的一個環(huán)節(jié),數(shù)據(jù)關聯(lián)算法的好壞直接影響跟蹤的效果。聯(lián)合概率數(shù)據(jù)關聯(lián)(JPDA)[1-2]算法是雜波環(huán)境下多目標跟蹤的一種非常有效的算法,該算法將落入波門的量測都用于目標狀態(tài)更新過程,并且考慮了各目標對共有量測的競爭,因此該算法能取得較好的關聯(lián)效果。但也正因如此周密的考慮,隨著目標數(shù)目以及候選回波數(shù)的增多,該算法的計算量急劇增加(指數(shù)級增速),導致算法實時性變差,不能滿足某些應用場景的時間要求。因此,若能在不降低或略微降低關聯(lián)性能和濾波精度的同時減少JPDA算法的計算量以提高其實時性將很有意義。

在JPDA算法中,隨著目標個數(shù)及雜波密度的增大,落入目標波門公共區(qū)域的回波數(shù)也隨之增多,這就導致在對確認矩陣進行拆分時可行關聯(lián)事件數(shù)爆炸式增長,實際上很多可行關聯(lián)事件的概率是極小的,而這些概率極小的可行關聯(lián)事件占據(jù)了大量的計算時間。

已有諸多文獻對JPDA算法進行改進以增強其實時性,改進思路主要分為兩種：一種是減少可行關聯(lián)事件數(shù)[3-6]；一種是避免矩陣拆分,簡化關聯(lián)概率的計算[7-10]。

文獻[3]首先用PDA[1-2]的方法計算各量測屬于各目標的概率并構建聚概率矩陣,將各關聯(lián)概率與設定概率閾值比較，進而對確認矩陣進行簡化,新的確認矩陣減少了很多概率較小的可行關聯(lián)事件,從而減少了JPDA算法的計算量,但概率閾值的選取不宜過大或過小,因此,不同跟蹤環(huán)境下的概率閾值應當是不同的,從而限制了該方法的使用。

文獻[4]首先利用Cheap JPDA[7]算法粗略計算關聯(lián)概率之后,通過設定閾值對聚概率矩陣進行適當?shù)奶幚聿嫿ㄐ碌暮喕_認矩陣,然后利用標準JPDA算法計算關聯(lián)概率,但為了提高鄰近目標關聯(lián)正確率,該文獻采用了自適應消除方法,去掉概率矩陣中容易引起錯誤關聯(lián)的量測,最終在實時性上的提升不太明顯。

文獻[5]在獲得確認矩陣之前對目標空間進行網(wǎng)格的劃分與連通,對每個連通域中的目標進行數(shù)據(jù)關聯(lián),得到多個維數(shù)較低的確認矩陣,利用每個網(wǎng)格對應的確認矩陣計算關聯(lián)概率,再分別對每個連通域中的目標采用標準聯(lián)合概率數(shù)據(jù)關聯(lián)算法,最終在關聯(lián)成功率略微下降的同時大大縮短了運行時間,但網(wǎng)格大小的選取沒有一般規(guī)則,因此通用性不強。

文獻[6]通過合理選取波門門限閾值,去除概率較小的可行關聯(lián)事件,然后再對落入各目標跟蹤門內(nèi)的公共點跡的互聯(lián)概率進行衰減,重新計算關聯(lián)概率,最終在跟蹤成功率與標準JPDA相當?shù)耐瑫r,計算時間大大縮短。

文獻[7]提出了一種經(jīng)驗JPDA(Cheap JPDA)算法,該算法在計算關聯(lián)概率時對只出現(xiàn)在一個目標波門內(nèi)的量測作“重”加權,而對同時出現(xiàn)在多個目標波門內(nèi)的量測作“輕”加權,該方法避免了矩陣拆分的過程,從而在實時性上有較大提升,但由于該算法所得每一條航跡關聯(lián)概率之和不為1使得不正確回波權系數(shù)過高，從而導致關聯(lián)誤差較大。

文獻[8]首先計算各量測屬于各個目標的后驗概率,然后將所有公共量測單獨列出,計算公共量測的修正因子以降低其分屬各個目標的概率,再利用修正系數(shù)及后驗概率計算量測與目標之間的關聯(lián)度并歸一化從而得到最終的關聯(lián)概率,最終在實時性上較標準JPDA算法有較大提升。

文獻[9]根據(jù)波門內(nèi)量測的分布和點跡-航跡關聯(lián)規(guī)則構造統(tǒng)計距離,將各目標的預測位置作為聚類中心,采用模糊聚類的方法,計算各候選量測與不同目標關聯(lián)的概率,最終該算法平均位置估計均方根誤差及正確關聯(lián)率與標準JPDA相當?shù)嬎銜r間大幅縮短。

文獻[10]使用了部分聯(lián)合事件的概念。航跡t1與t2的波門重疊, 并有一個共同回波, 這個事件被視為一個部分聯(lián)合事件。由于考慮了部分聯(lián)合事件, 因此相對于一些快速算法而言,該算法精度較高但實時性較差。

本文通過定義濾波參與度,分別考慮了波門中心和量測在濾波更新中所起的作用,在計算某一量測與某一目標的關聯(lián)概率時利用了類似于PDA的方法,但同時考慮了該目標同其他相關目標對該量測的競爭關系以及該量測同其他相關量測對該目標的歸屬關系,將歸一化后的關聯(lián)概率乘以濾波參與度即為最終的關聯(lián)概率。這樣處理的好處是避免了復雜的矩陣拆分過程但又考慮了目標及量測之間復雜的歸屬關系,從而將多目標跟蹤問題轉化為多個單目標的跟蹤問題,因此本文所提算法取得了較為理想的結果。

1 JPDA

1.1 基本原理

PDA對于單目標跟蹤可以取得較好的跟蹤效果,但是在雜波環(huán)境下,當目標個數(shù)較多時,這種方法的關聯(lián)效果不很理想,甚至可能出現(xiàn)誤跟。其原因是當目標距離較近,或進行交叉運動時,PDA沒有考慮各航跡對落入公共關聯(lián)區(qū)域的量測的競爭。為此,Bar-shalom等人對PDA進行了推廣,提出了聯(lián)合概率數(shù)據(jù)關聯(lián)(JPDA)算法,這種方法很好地解決了雜波環(huán)境下的多目標跟蹤問題。此算法的原理與PDA完全相同,唯一的不同之處在于關聯(lián)概率的計算。JPDA算法不僅要考慮關聯(lián)區(qū)域內(nèi)各量測源自目標的概率,還要考慮多條已建目標航跡對公共關聯(lián)區(qū)域內(nèi)的量測的競爭概率。

1.2 計算關聯(lián)概率

為了解決候選量測的源的問題,Bar-shalom首先定義了確認矩陣以表示候選量測與各目標關聯(lián)門的復雜關系。其定義為

Ω=(ωjt),j=1,2,…,mk,t=0,1,…,T

(1)

式中，mk為量測數(shù)量,T為目標數(shù)量。t=0對應沒有目標的情形,因此ωjt的第一列全為1,這是因為所有候選量測均可能源自雜波。ωjt=1表示量測j與目標t相關聯(lián),ωjt=0表示量測j不與目標t關聯(lián)。在關聯(lián)門重疊的區(qū)域,量測可能與多個目標關聯(lián),此時ωjt中的某一行或某幾行除第一列以外有多個元素的值為1。

前述提及JPDA與PDA的本質(zhì)區(qū)別在于關聯(lián)概率的計算,在JPDA算法中,可以將關聯(lián)概率表示為

(2)

可行關聯(lián)事件θi表示的是所有候選量測與所有目標相互關聯(lián)的一種可能?？尚嘘P聯(lián)事件需滿足兩個假設:

1)同一量測只能來自一個目標(包括虛警);

2)同一目標只能對應一個量測。

對于參數(shù)模型[1]而言,第i個可行關聯(lián)事件θi的后驗概率:

(3)

式中，λ為雜波密度;c為歸一化常數(shù),其值為k時刻所有可行關聯(lián)事件對應的聯(lián)合概率密度之和;Φ為可行關聯(lián)事件θi中的虛假量測數(shù);v為k時刻所有目標關聯(lián)門體積之和;Ntj(Zj(k))為量測j源自目標t時所對應的概率密度。

1.3 濾波更新

得到關聯(lián)概率βjt后即可對各個目標運動狀態(tài)及相應的協(xié)方差的進行更新,具體過程如下:

狀態(tài)預測:

(4)

量測預測:

(5)

協(xié)方差預測:

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

(6)

新息協(xié)方差:

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)

狀態(tài)更新:

(11)

估計協(xié)方差更新:

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算法中對確認矩陣進行拆分的本質(zhì)是為了求解每一個量測源自每一批目標的概率。本文的基本思想是跳過矩陣拆分過程而直接計算各候選量測源自每一批目標的概率,這樣一來,多目標數(shù)據(jù)關聯(lián)問題就能夠化作多個單目標的數(shù)據(jù)關聯(lián)問題。

在濾波更新過程中,波門中心和候選量測對最終的濾波結果都會產(chǎn)生影響。為此,首先定義:

濾波參與度:濾波參與度分為波門中心參與度和量測參與度,分別用a1,a2表示,代表的是在每次更新中波門中心和量測所起的作用。

對單個目標而言,當波門內(nèi)的所有量測全為雜波(包括其他目標的回波)時,波門中心參與濾波,否則量測參與濾波。假設在某一周期中,某一目標波門中共有n個回波,該n個回波要么全為雜波,要么有一個源自該目標,其余為雜波。

在假定落入目標波門的雜波個數(shù)服從泊松分布的情況下(即雜波數(shù)服從參數(shù)為λV的泊松分布,其中,λ為雜波密度,V為波門“體積”),波門中出現(xiàn)n個雜波和n-1個雜波的概率分別為:

(15)

(16)

其中,N代表雜波的個數(shù)。

考慮到檢測概率PD和門概率PG的影響,濾波參與度可用下式表示:

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

(17)

a2=P{N=n-1}PDPG

(18)

歸一化后,有

(19)

(20)

當量測參與濾波時,各量測對目標狀態(tài)更新的貢獻是不同的,離波門中心近的量測貢獻較大,離波門中心遠的量測其貢獻較小,而對于量測落入公共波門的情況還需要考慮各目標對量測的競爭。

首先,計算各目標的候選量測與波門中心的統(tǒng)計距離：

(21)

其中,i(i=1,…,mk)對應候選量測中的第i個量測,j(j=1,…,T)對應第j批目標,vij為量測i與目標j預測量測的新息,Sj為目標j對應的新息協(xié)方差。

構建量測與目標的互聯(lián)矩陣D={Dij}：

(22)

由上式可知D每行之和不為0而每列之和可能為0,因此某一量測屬于各目標的概率為

(23)

某一目標擁有各量測的概率為

(24)

再將Pt與Pm中的對應元素相乘得到Pc,此時得到的Pc既考慮了目標對量測的競爭,又考慮了量測對目標的競爭,再對Pc的列進行歸一化,有

(25)

最終,各候選量測與各目標的關聯(lián)概率為

(26)

同時,沒有量測與目標j關聯(lián)的概率為

β0j=a1(j)

(27)

其中a1(j)、a2(j)分別表示第j個目標對應的波門參與度和量測參與度。

計算完關聯(lián)概率后,即可按照標準JPDA算法的濾波過程完成對目標的狀態(tài)估計。

3 數(shù)值仿真

3.1 性能指標

為了便于比較分析,首先給出幾個性能指標的定義及計算方法。

單步耗時:單步耗時是指一次完整仿真實驗中每個采樣周期平均花費的時間,計算公式為

(28)

其中,Taver為每周期平均花費的時間也即單步耗時,Tall為一次完整仿真實驗中總共花費的時間,N為采樣周期數(shù)。

誤跟率:誤跟率是指在多次Monte Carlo仿真實驗中目標濾波軌跡嚴重偏離真實軌跡的航次占總航次的比率,假設目標濾波軌跡最終與真實軌跡的偏差大于三倍量測誤差即認為發(fā)生誤跟。誤跟率計算公式為

(29)

其中,False-rate代表誤跟率,False-num代表誤跟航次,MC-num代表Monte Carlo仿真次數(shù),Tn代表目標數(shù)。

均方根誤差:均方根誤差指的是估計值與真值偏差的平方之和與Monte Carlo仿真次數(shù)n比值的平方根。均方根誤差能夠很好地反映估計精度。均方根誤差計算公式為

(30)

其中,RMSE為均方根誤差,Xi為第i次仿真的估計值,X為真值,n為仿真次數(shù)。

3.2 態(tài)勢設置

為了比較改進算法(MJPDA)與標準算法(JPDA)及經(jīng)驗算法(Cheap JPDA)的性能,本文在相同環(huán)境下對三種算法進行Monte Carlo仿真實驗。目標批數(shù)分別為2、4、6,采樣周期為10s,檢測概率PD=0.9,雜波服從均勻分布且密度λ=0.3,量測誤差協(xié)方差R=diag([80 80])。目標初始狀態(tài)如表1所示。

表1 目標初始狀態(tài)

目標真實運動軌跡分別如圖1、圖2、圖3所示。

圖1 兩目標真實運動軌跡

圖2 四目標真實運動軌跡

圖3 六目標真實運動軌跡

3.3 均方根誤差對比

以四批目標的情形為例,三種算法在100次Monte Carlo試驗中的位置均方根誤差(僅考慮三種算法均未出現(xiàn)誤跟的情況)如圖4至圖7所示。

圖4 目標1位置均方根誤差

圖5 目標2位置均方根誤差

圖6 目標3位置均方根誤差

圖7 目標4位置均方根誤差

3.4 誤跟率對比

三種算法的三組100次以及一組10000次的Monte Carlo實驗誤跟率統(tǒng)計結果如表2、表3所示(λ=0.3),不同雜波密度下100次Monte Carlo實驗的誤跟率如表4所示。

表2 三組100次實驗誤跟率(%)

表3 10000次實驗誤跟率(%)

表4 誤跟率與目標數(shù)及雜波密度的關系(%)

3.5 實時性對比

不同目標數(shù)、不同雜波密度下三種算法的單步耗時如表5所示。(各目標航跡相交于同一點,相鄰航跡之間的夾角為20°)

表5 單步耗時與目標數(shù)及雜波密度的關系(單位:s)

為了更進一步考察改進算法的實時性,在雜波密度λ=0.3的條件下,分別對50、100、200、500批目標的單步耗時做了統(tǒng)計(標準算法耗時太久因此未作統(tǒng)計),結果如表6所示,同表5中的情況類似,CheapJPDA算法的單步耗時比本文所提算法略短。

表6 改進算法單步耗時與目標數(shù)的關系

4 結束語

本文提出了一種JPDA改進算法,該算法避免了復雜的矩陣拆分過程,簡化了關聯(lián)概率的計算過程。仿真實驗表明,改進算法在關聯(lián)精度、誤跟率方面雖比標準算法稍差,但基本相當,而在實時性上的改善非常明顯。同時本文還將改進算法與比較經(jīng)典的CheapJPDA算法進行了比較,結果表明本文所提算法在實時性方面與CheapJPDA幾乎完全一致,在正確關聯(lián)的條件下兩種算法的位置均方根誤差相當,但在誤跟率方面本文所提算法表現(xiàn)較好。在目標數(shù)目較多、回波密集的情況下,改進算法在實時性方面較標準算法的優(yōu)勢更為明顯,當目標數(shù)多至數(shù)百批時改進算法的實時性依然表現(xiàn)良好,滿足實時性要求。針對回波密集的應用背景,本文所提算法具有一定的應用價值。

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

[2] 何友,修建娟,關欣.雷達數(shù)據(jù)處理及應用[M].第3版.北京:電子工業(yè)出版社,2013.

[3] 秦衛(wèi)華,胡飛,秦超英.一種簡化的聯(lián)合概率數(shù)據(jù)關聯(lián)算法[J].西北工業(yè)大學學報,2005,23(2):276-279.

[4] 李首慶,徐揚.基于自適應聚概率矩陣的JPDA 算法研究[J].西南交通大學學報,2017,52(2):340-347.

[5] 張成寶,曹偉,匡華星.基于網(wǎng)格連通的聯(lián)合概率數(shù)據(jù)關聯(lián)算法[J].電光與控制,2013,20(9):34-36.

[6] 余周, 左現(xiàn)剛, 侯志松.一種改進的聯(lián)合概率數(shù)據(jù)關聯(lián)算法[J]. 火力與指揮控制,2010,35(4):106-110.

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

[8] 賈正望,張華陽.一種基于多目標跟蹤的改進概率數(shù)據(jù)關聯(lián)算法[J].指揮信息系統(tǒng)與技術,2010,1(3):36-40.

[9] 劉俊,劉瑜,何友,孫順.雜波環(huán)境下基于全鄰模糊聚類的聯(lián)合概率數(shù)據(jù)互聯(lián)算法[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-),男,湖北黃岡人,碩士研究生,研究方向為多目標數(shù)據(jù)關聯(lián)技術。袁富宇(1964-),男,研究員,博士生導師。蒲 勇(1981-),男,碩士,高級工程師。