基于多維分配的被動多傳感器多目標跟蹤方法

卜石哲,周共健

(1.哈爾濱工業(yè)大學(xué),黑龍江 哈爾濱 150001；2.對海監(jiān)測與信息處理工業(yè)和信息化部重點實驗室，黑龍江 哈爾濱 150001)

在多傳感器多目標跟蹤領(lǐng)域中,為了有效利用多傳感器觀測數(shù)據(jù)提高目標狀態(tài)估計精度,需要確定各傳感器觀測數(shù)據(jù)的目標來源,即進行將數(shù)據(jù)關(guān)聯(lián)處理。從20世紀60年代開始，已有文獻對數(shù)據(jù)關(guān)聯(lián)問題進行研究,發(fā)展出一系列算法[1-4],這些算法在復(fù)雜度和跟蹤性能上各不相同。

解決多傳感器多目標數(shù)據(jù)關(guān)聯(lián)問題的方法有最近鄰法(NN)[5],聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)(JPDA)[6]以及多假設(shè)跟蹤(MHT)[7]等。其中，最近鄰法是最簡單的數(shù)據(jù)關(guān)聯(lián)解決方案,該方法將統(tǒng)計意義上與目標預(yù)測位置最近的觀測數(shù)據(jù)作為關(guān)聯(lián)上的觀測數(shù)據(jù),僅適用于信噪比高且目標密度低的場景,在實際應(yīng)用中效率低。JPDA方法通過最后一幀掃描中觀測數(shù)據(jù)的一對多和多對一關(guān)聯(lián)關(guān)系計算概率來解決數(shù)據(jù)關(guān)聯(lián)問題,適合雜波少的環(huán)境。MHT方法試圖考慮所有的關(guān)聯(lián)假設(shè)以提供最優(yōu)的解決方案,但直接實施MHT方法會導(dǎo)致關(guān)聯(lián)假設(shè)數(shù)量隨時間呈指數(shù)增長。為了滿足MHT方法的計算量要求,需利用截斷技術(shù)減少不太可能的假設(shè)數(shù)量。除此之外,多維分配(MDA)技術(shù)[8-10]是解決數(shù)據(jù)關(guān)聯(lián)問題的另一類方案。利用該技術(shù)可將多目標跟蹤中的數(shù)據(jù)關(guān)聯(lián)問題描述為一定條件下的離散優(yōu)化問題,可通過有限長度的滑窗處理逼近MHT跟蹤性能,避免了MHT算法中的暴力窮舉,它被證明是一種實用可行的MHT的替代選擇。

本文基于多維分配方法開展被動多傳感器多目標跟蹤方法的研究。在被動多傳感器多目標跟蹤中,傳感器只能獲得目標的角度觀測數(shù)據(jù),只利用角度觀測數(shù)據(jù)進行數(shù)據(jù)關(guān)聯(lián)處理更具有挑戰(zhàn)性[11]。為了實現(xiàn)多目標的有效跟蹤,首先要進行多傳感器觀測數(shù)據(jù)之間的關(guān)聯(lián),也稱為點跡-點跡關(guān)聯(lián),利用多維分配處理找出來源于同一目標的觀測數(shù)據(jù)集合,并利用集合中多傳感器觀測數(shù)據(jù)在最大似然準則下估計目標位置。在傳感器數(shù)目大于3時,多維分配問題被判為NP-hard問題,解決此問題的核心是合理利用拉格朗日松弛算法[12-13]對多維分配問題進行降維并尋找滿足實時性要求的次優(yōu)解。隨后,利用二維分配方法解決目標位置估計和目標航跡之間的關(guān)聯(lián)問題,也稱為點跡-航跡關(guān)聯(lián),利用關(guān)聯(lián)上的位置估計更新目標航跡,實現(xiàn)多傳感器多目標跟蹤。

1 問題描述

考慮使用S個傳感器的情況,各傳感器采樣率相同且觀測時刻同步,每幀掃描中可得到S個觀測數(shù)據(jù)列表,此時的多維分配問題也稱為S維分配問題。假設(shè)k時刻傳感器s獲得ns個觀測數(shù)據(jù),觀測數(shù)據(jù)zsis,is=1,…,ns，來源于目標或雜波。

(1)

(2)

所有傳感器觀測數(shù)據(jù)構(gòu)成集合Z(k)

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

(3)

從每個傳感器觀測數(shù)據(jù)集合中選擇一個觀測數(shù)據(jù)構(gòu)建觀測數(shù)據(jù)的S元組Zi1i2…iS,表示可能來源于同一目標p的數(shù)據(jù)組合。觀測數(shù)據(jù)集合Z(k)可以劃分為多個S元組,多傳感器數(shù)據(jù)關(guān)聯(lián)就是找出最有可能來源于同一目標的S元組的集合。

2 觀測數(shù)據(jù)關(guān)聯(lián)的多維分配模型

2.1 S元組代價函數(shù)構(gòu)建

當S元組中的觀測數(shù)據(jù)來源于同一目標p時,對應(yīng)的似然概率為

(4)

其中，u(is)為二值函數(shù),當is=0時u(is)=0,否則u(is)=1。同時,S元組中的觀測數(shù)據(jù)可能來源于雜波,此時的似然概率表示為

(5)

其中，ψs表示傳感器s觀測區(qū)域的體積。

為每個S元組分配代價函數(shù)ci1i2…iS,用于表示該元組中觀測數(shù)據(jù)來源于同一個目標代價,可表示為

(6)

將式(4)和式(5)代入式(6),可得代價函數(shù)為

(7)

由于多傳感器觀測數(shù)據(jù)和目標之間存在相互對應(yīng)關(guān)系,存在下面的約束條件:

(8)

利用上述過程完成了多傳感器觀測數(shù)據(jù)S元組代價函數(shù)的構(gòu)建。

2.2 多維分配模型的引出

進行數(shù)據(jù)關(guān)聯(lián)時多維分配模型可看作一定條件約束下的全局離散優(yōu)化問題,其目標是最小化全局關(guān)聯(lián)代價,即在式(8)的約束條件下找出使得全局關(guān)聯(lián)代價函數(shù)最小的S元組的分配結(jié)果,完成多傳感器觀測數(shù)據(jù)關(guān)聯(lián)處理。由此引出下面的S維分配問題和S個約束集

(9)

滿足以下的約束條件:

(10)

在S≥3時，該問題為NP-hard問題,需用拉格朗日松弛算法對多維分配問題的約束條件進行松弛,通過連續(xù)的降維處理將其轉(zhuǎn)化成二維分配問題進行處理。

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,則對應(yīng)的二維分配子問題可描述為

(15)

滿足以下的約束條件:

(16)

對偶解為最優(yōu)解的下界,一般不可行。需要依次附加各維的約束條件,同時對拉格朗日乘子進行更新,獲得各維子問題的可行解。通過對偶解和可行解的差值判斷是否需要進行迭代。

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 迭代停止原則

設(shè)定S維分配的停止原則,預(yù)先給定最小的差值mingap和最大迭代次數(shù)maxiter。最優(yōu)可行解與對偶解的相對差值為

gap=(fprimal-fdual)/|fprimal|

(22)

3 點跡-航跡關(guān)聯(lián)的二維分配模型

3.1 位置極大似然估計

完成S維分配后,利用得到的S元組中的觀測數(shù)據(jù)計算目標在k時刻位置的極大似然估計

(23)

3.2 點跡-航跡關(guān)聯(lián)

(24)

目標航跡可用與之關(guān)聯(lián)的點跡進行更新,航跡在更新過程中需設(shè)立相應(yīng)的準則。本算法采用6/10邏輯進行判斷,即每隔10個周期對當前所有航跡進行查詢,若滿足10個周期中至少有6個周期航跡被更新,且最后一個周期航跡被更新,則繼續(xù)對航跡進行維持。否則，當不滿足準則時，停止航跡更新,并對航跡進行撤銷,從而實現(xiàn)航跡整個過程的管理。

4 仿真結(jié)果及分析

本文以4個被動傳感器對區(qū)域內(nèi)4個目標進行跟蹤的場景為例進行實驗。多傳感器進行100次采樣,各傳感器觀測同步且采樣周期均為T=1 s,探測概率均為PDs=0.95,觀測噪聲標準差為σt=0.5°。4個目標初始狀態(tài)為(-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)。拍賣算法的最大迭代次數(shù)設(shè)為50次。

每一時刻區(qū)域內(nèi)均存在50個呈均勻分布的雜波,用來模擬復(fù)雜電磁環(huán)境。單次仿真中多目標的跟蹤航跡如圖1所示。在雜波環(huán)境下,利用本文算法可實現(xiàn)多傳感器觀測數(shù)據(jù)的正確關(guān)聯(lián),區(qū)域內(nèi)產(chǎn)生的虛假少,可實現(xiàn)多目標的有效跟蹤。為了驗證算法的收斂性,本算法還進行50次Monte Carlo仿真,給出多目標位置估計和多目標速度估計的均方根誤差(RMSE),如圖2和圖3所示。

圖1 多目標跟蹤航跡

圖2 多目標位置估計RMSE

圖3 多目標速度估計RMSE

由圖中結(jié)果可看出,多目標位置和速度估計的RMSE均呈現(xiàn)收斂的趨勢,且收斂值較小。說明利用多維分配方法能實現(xiàn)多傳感器觀測數(shù)據(jù)的正確關(guān)聯(lián),利用二維分配方法能實現(xiàn)位置極大似然估計和多目標航跡的正確關(guān)聯(lián),有效利用多傳感器觀測數(shù)據(jù)提高目標的跟蹤性能。此外,給出各個時刻成功跟蹤的目標數(shù)以及虛假航跡數(shù),進一步表明本文算法的跟蹤效果。如圖4，5所示。

由圖4可知,每時刻成功跟蹤的目標數(shù)逐漸維持在4個,說明本算法在目標跟蹤發(fā)現(xiàn)方面,能實現(xiàn)對全部目標的有效跟蹤。

圖4 成功跟蹤目標數(shù)

由圖5可知,每時刻的虛假航跡數(shù)維持在0.4附近,這說明本算法有較好的虛假航跡剔除能力,能將虛假航跡保持在較低水平。因此，本文算法在未損失目標跟蹤發(fā)現(xiàn)能力的條件下,維持了較低的虛假航跡數(shù),具有較強分辨目標與虛警的能力,能實現(xiàn)被動多傳感器系統(tǒng)中多目標的有效跟蹤。

圖5 虛假航跡數(shù)

5 結(jié)束語

本文提出了一種基于多維分配數(shù)據(jù)關(guān)聯(lián)方法實現(xiàn)被動多傳感器系統(tǒng)中多目標跟蹤的有效跟蹤。利用多維分配方法通過約束松弛的處理解決多傳感器觀測數(shù)據(jù)之間的關(guān)聯(lián)問題,確定來源于同一目標的觀測數(shù)據(jù)的集合,并用集合中的觀測數(shù)據(jù)對目標完整的位置信息進行最大似然估計。二維分配方法用于進行各個位置最大似然估計和多目標航跡之間的關(guān)聯(lián),用關(guān)聯(lián)上的位置估計更新目標航跡。Monte Carlo仿真表明,本文算法在含有雜波和噪聲的環(huán)境下,每時刻能保持較高的航跡關(guān)聯(lián)正確率以及較低的虛假航跡數(shù),算法的關(guān)聯(lián)精度高,能實現(xiàn)被動多傳感器系統(tǒng)中多目標的有效跟蹤。