一種利用量測(cè)空間聚類的多幀檢測(cè)前跟蹤算法

張佳琦，陶海紅，張修社，韓春雷

(1.西安電子科技大學(xué) 雷達(dá)信號(hào)處理國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.西安導(dǎo)航技術(shù)研究所，陜西 西安 710068)

多目標(biāo)跟蹤[1]是目標(biāo)跟蹤領(lǐng)域的研究熱點(diǎn)，經(jīng)過幾十年的發(fā)展獲取了大量的研究成果[2-4]。傳統(tǒng)的多目標(biāo)跟蹤方法[5]利用門限檢測(cè)后的點(diǎn)跡進(jìn)行目標(biāo)軌跡估計(jì)，門限檢測(cè)的目的是濾除大量雜波，保留真實(shí)目標(biāo)點(diǎn)跡。然而，在低信噪比(Signal Noise Ratio，SNR)環(huán)境下，傳統(tǒng)的多目標(biāo)跟蹤算法具有一定的局限性。檢測(cè)前跟蹤技術(shù)(Track Before Detect，TBD)[6]通過直接處理無門限或低門限點(diǎn)跡，并對(duì)目標(biāo)的多幀量測(cè)點(diǎn)跡進(jìn)行能量積累，能夠在低信噪比環(huán)境下實(shí)現(xiàn)弱小目標(biāo)的檢測(cè)和跟蹤。檢測(cè)前跟蹤技術(shù)經(jīng)過了幾十年的發(fā)展，形成了諸多流派[7-10]，其中基于動(dòng)態(tài)規(guī)劃的檢測(cè)前跟蹤算法(Dynamic Programming Track Before Detect，DP-TBD)[11-13]因其算法結(jié)構(gòu)簡(jiǎn)單、易于工程實(shí)現(xiàn)，受到了眾多學(xué)者的青睞。其中，文獻(xiàn)[14-17]研究了機(jī)動(dòng)目標(biāo)的DP-TBD算法，文獻(xiàn)[18-20]針對(duì)多目標(biāo)場(chǎng)景的DP-TBD算法開展研究，文獻(xiàn)[21-22]對(duì)多目標(biāo)臨近場(chǎng)景的DP-TBD算法進(jìn)行研究，文獻(xiàn)[23-24]開展了兩級(jí)處理結(jié)構(gòu)的DP-TBD算法研究，文獻(xiàn)[25-26]進(jìn)行了迭代框架的DP-TBD算法研究，文獻(xiàn)[27-28]進(jìn)行了多傳感器的DP-TBD融合算法研究。另外，文獻(xiàn)[29-30]針對(duì)檢測(cè)場(chǎng)景的雜波分布和目標(biāo)特性開展DP-TBD算法研究。

在實(shí)際應(yīng)用中，DP-TBD算法面臨最大的挑戰(zhàn)仍然是較高的運(yùn)算復(fù)雜度。在多目標(biāo)場(chǎng)景下，文獻(xiàn)[20-22]提出的基于連續(xù)目標(biāo)撤銷策略的DP-TBD算法(Succession Track Cancel Dynanic Progremming Track Before Detect，STC-DP-TBD)能夠有效改善目標(biāo)臨近時(shí)的多目標(biāo)檢測(cè)和跟蹤性能。然而，當(dāng)場(chǎng)景中目標(biāo)、虛警數(shù)量增加時(shí)，算法的運(yùn)算復(fù)雜度將呈現(xiàn)幾何級(jí)數(shù)增長。由于缺少目標(biāo)運(yùn)動(dòng)先驗(yàn)信息，算法采用觀測(cè)空間全局DP-TBD處理，導(dǎo)致運(yùn)算復(fù)雜度高的問題，筆者提出一種利用量測(cè)空間聚類的DP-TBD算法(Measurement Space Clustering Dynamic Programming Track Before Detect，MSC-DP-TBD)。該算法構(gòu)建在文獻(xiàn)[23-24]提出的兩級(jí)處理框架之上，利用跨多幀策略構(gòu)建狀態(tài)轉(zhuǎn)移集合，并依據(jù)狀態(tài)轉(zhuǎn)移集合對(duì)量測(cè)點(diǎn)跡進(jìn)行標(biāo)簽構(gòu)建，獲取點(diǎn)跡在量測(cè)空間上的分布信息，形成量測(cè)點(diǎn)跡的空間聚類，在各聚類的子空間內(nèi)獨(dú)立的運(yùn)行STC-DP-TBD算法。通過仿真實(shí)驗(yàn)可知，該算法與STC-DP-TBD算法檢測(cè)性能相當(dāng)，但運(yùn)算復(fù)雜度大幅降低。

1 問題描述

傳統(tǒng)的DP-TBD算法通過對(duì)狀態(tài)空間進(jìn)行離散化，構(gòu)建航跡的狀態(tài)轉(zhuǎn)移集合對(duì)離散空間進(jìn)行遍歷，通過積累航跡的多幀量測(cè)點(diǎn)跡的能量，實(shí)現(xiàn)弱小目標(biāo)檢測(cè)。該處理方式需要對(duì)離散空間中可能存在的所有目標(biāo)進(jìn)行遍歷，算法的運(yùn)算復(fù)雜度隨著觀測(cè)空間和積累幀數(shù)的增加呈幾何級(jí)數(shù)增長。針對(duì)算法運(yùn)算復(fù)雜度高的問題，文獻(xiàn)[21]提出了一種兩級(jí)處理的DP-TBD算法(Two Stage Dynamic Programming Track Before Detect，TS-DP-TBD)，處理結(jié)構(gòu)如圖1所示。

圖1 TS-DP-TBD 處理結(jié)構(gòu)

該處理結(jié)構(gòu)與傳統(tǒng)結(jié)構(gòu)相比，可以利用一級(jí)檢測(cè)門限濾除虛警似然點(diǎn)跡，保留目標(biāo)似然點(diǎn)跡，減少無效的點(diǎn)跡狀態(tài)轉(zhuǎn)移關(guān)聯(lián)關(guān)系運(yùn)算，能夠大幅度降低算法的運(yùn)算復(fù)雜度。TS-DP-TBD算法在多目標(biāo)情況下，尤其是目標(biāo)位置鄰近時(shí)，強(qiáng)幅度目標(biāo)容易遮擋弱目標(biāo)，導(dǎo)致弱目標(biāo)難以檢測(cè)。針對(duì)上述問題，文獻(xiàn)[22]提出了STC-DP-TBD算法。該算法在航跡構(gòu)建過程中采用連續(xù)航跡撤銷策略，將確認(rèn)航跡包含的點(diǎn)跡進(jìn)行剔除處理，降低確認(rèn)航跡對(duì)潛在航跡構(gòu)建的干擾，并在文獻(xiàn)[31]中利用雷達(dá)真實(shí)量測(cè)數(shù)據(jù)對(duì)該算法的有效性進(jìn)行了驗(yàn)證。然而，STC-DP-TBD算法在對(duì)多目標(biāo)進(jìn)行檢測(cè)時(shí)，由于缺少目標(biāo)運(yùn)動(dòng)的先驗(yàn)信息，需要在全域量測(cè)空間內(nèi)進(jìn)行航跡遍歷，隨著場(chǎng)景中目標(biāo)、虛警數(shù)量的增加，運(yùn)算復(fù)雜度大幅提升。

2 量測(cè)空間聚類

如圖2(a)所示的多目標(biāo)場(chǎng)景，場(chǎng)景中目標(biāo)運(yùn)動(dòng)軌跡存在“交叉”“平行”等鄰近狀態(tài)，相互鄰近的目標(biāo)在航跡構(gòu)建時(shí)存在“共享”的量測(cè)點(diǎn)跡。利用“共享”的量測(cè)點(diǎn)跡構(gòu)建起航跡之間的關(guān)聯(lián)關(guān)系，依據(jù)這種關(guān)系可以對(duì)量測(cè)空間的點(diǎn)跡進(jìn)行聚類劃分，在空間上形成多個(gè)相互解耦的聚類，如圖2(b)所示?；谝陨纤枷耄P者提出利用根標(biāo)簽聚類的量測(cè)空間聚類劃分方法，詳細(xì)過程如下。

圖2 多目標(biāo)觀測(cè)空間及聚類劃分

圖3 跨幀狀態(tài)轉(zhuǎn)移集合構(gòu)建

構(gòu)建出的狀態(tài)轉(zhuǎn)移集合M可表示為

(1)

利用構(gòu)建的狀態(tài)轉(zhuǎn)移集合對(duì)量測(cè)空間的點(diǎn)跡進(jìn)行根標(biāo)簽標(biāo)記，標(biāo)記過程如圖4所示。對(duì)第一幀中包含的量測(cè)點(diǎn)跡標(biāo)記為根標(biāo)簽，依據(jù)狀態(tài)轉(zhuǎn)移集合依次對(duì)第2至第L幀量測(cè)點(diǎn)跡進(jìn)行根標(biāo)簽標(biāo)記。利用根標(biāo)簽的傳遞性和繼承性，在第L幀量測(cè)點(diǎn)跡的根標(biāo)簽集合中能夠獲取根標(biāo)簽的連通性信息。

圖4 標(biāo)簽標(biāo)記

依據(jù)第L幀量測(cè)點(diǎn)跡的根標(biāo)簽信息進(jìn)行根標(biāo)簽連通性判斷，相互連通的根標(biāo)簽劃分為同一個(gè)聚類，則有

(2)

(3)

(4)

其中，|C(i)|表示量測(cè)空間聚類個(gè)數(shù)，|C(i，j)|表示第i個(gè)聚類中的第j個(gè)目標(biāo)的所有量測(cè)點(diǎn)跡。

3 算法描述

針對(duì)STC-DP-TBD算法運(yùn)算復(fù)雜度高的問題，提出了MSC-DP-TBD算法。該算法采用跨多幀構(gòu)建關(guān)聯(lián)集合，依據(jù)狀態(tài)轉(zhuǎn)移集合對(duì)量測(cè)點(diǎn)跡進(jìn)行根標(biāo)簽標(biāo)記，通過根標(biāo)簽聯(lián)通性計(jì)算形成量測(cè)點(diǎn)跡的空間聚類劃分，并在各聚類內(nèi)采用STC-DP-TBD處理，可有效降低算法的運(yùn)算復(fù)雜度。算法步驟如圖5所示。

圖5 MSC-DP-TBD處理結(jié)構(gòu)

3.1 算法處理步驟

3.1.1 量測(cè)空間聚類

利用最大速度約束在不同幀的點(diǎn)跡之間計(jì)算狀態(tài)轉(zhuǎn)移關(guān)系，構(gòu)建出多幀量測(cè)點(diǎn)跡的狀態(tài)轉(zhuǎn)移集合。依據(jù)狀態(tài)轉(zhuǎn)移集合對(duì)量測(cè)空間中的點(diǎn)跡進(jìn)行標(biāo)記并形成空間聚類，生成的不同聚類之間的量測(cè)點(diǎn)跡不相交。聚類之間的點(diǎn)跡關(guān)系如下：

C(i)∩C(j)=?，i，j=1，2，…，N，

(5)

(6)

3.1.2 航跡構(gòu)建

在各聚類內(nèi)獨(dú)立的執(zhí)行基于STC策略的航跡構(gòu)建算法，通過積累量測(cè)點(diǎn)跡的幅度信息計(jì)算出臨時(shí)航跡的得分函數(shù)F()及可回溯狀態(tài)τ()：

(7)

(8)

其中，z表示航跡中關(guān)聯(lián)點(diǎn)跡的幅度信息。

3.1.3 航跡確認(rèn)

利用二級(jí)檢測(cè)門限γ2和構(gòu)建的航跡的得分函數(shù)進(jìn)行對(duì)比，對(duì)構(gòu)建航跡進(jìn)行確認(rèn)或刪除，

(9)

3.1.4 航跡平滑

通過對(duì)確認(rèn)航跡的量測(cè)點(diǎn)跡序列進(jìn)行平滑處理，獲得更高跟蹤精度的航跡狀態(tài)。

3.2 運(yùn)算復(fù)雜度分析

STC-DP-TBD算法的運(yùn)算復(fù)雜度主要集中在計(jì)算狀態(tài)轉(zhuǎn)移集合和構(gòu)建航跡兩個(gè)步驟，計(jì)算狀態(tài)轉(zhuǎn)移集合平均時(shí)間復(fù)雜度約為O(PL[(NrNθ-K)FFAR+KPd]2)，其中，P為航跡允許缺失最大點(diǎn)跡數(shù)量，L為積累的量測(cè)數(shù)據(jù)幀數(shù)，Nr和Nθ分別為距離和方位角的分辨單元數(shù)量，K∈{1，…，NrNθ}為場(chǎng)景中的目標(biāo)數(shù)量，F(xiàn)FAR為虛警率，Pd為檢測(cè)概率。假定航跡構(gòu)建步驟的時(shí)間復(fù)雜度為O(TFstc)，則STC-DP-TBD算法的運(yùn)算復(fù)雜度約為

O(STC-DP-TBD)≈O(PL[(NrNθ-K)FFAR+KPd]2)+O(TFstc) 。

(10)

假定MSC-DP-TBD算法的聚類個(gè)數(shù)為N，航跡構(gòu)建算法的時(shí)間復(fù)雜度為O(TFmsc)，則有如下關(guān)系：

O(TFstc)/N≤O(TFmsc)≤(TFstc) 。

(11)

則MSC-DP-TBD算法的運(yùn)算復(fù)雜度約為

O(MSC-DP-TBD)≈O(PL[(NrNθ-K)FFAR+KPd]2)+O(TFmsc) 。

(12)

因此，有

O(MSC-DP-TBD)≤O(STC-DP-TBD) 。

(13)

當(dāng)聚類個(gè)數(shù)N增加時(shí)，MSC-DP-TBD算法的運(yùn)算復(fù)雜度會(huì)得到明顯改善。

表1給出了兩種算法運(yùn)算復(fù)雜度的對(duì)比。

表1 運(yùn)算復(fù)雜度對(duì)比表

4 數(shù)值分析

為了評(píng)價(jià)TS-DP-TBD、STC-DP-TBD及MSC-DP-TBD等算法的檢測(cè)性能，特采用的評(píng)估指標(biāo)如下：

(1)有效檢測(cè)航跡數(shù)(Nvd)，即真實(shí)航跡被檢測(cè)到的數(shù)量；

(2)虛假檢測(cè)航跡數(shù)(Nfd)，即檢測(cè)到的非真實(shí)航跡的數(shù)量；

(3)漏檢航跡數(shù)(Nld)，即真實(shí)航跡未被檢測(cè)到的數(shù)量。

仿真場(chǎng)景設(shè)置如圖6所示。場(chǎng)景構(gòu)建了X-Y兩維平面空間，空間尺度大小為14 km×14 km，包含12批勻速運(yùn)動(dòng)目標(biāo)，在空間上可簡(jiǎn)單地劃分為5個(gè)聚類，目標(biāo)1和目標(biāo)2、目標(biāo)7和目標(biāo)8為兩組平行運(yùn)動(dòng)，目標(biāo)3和目標(biāo)4、目標(biāo)5和目標(biāo)6為兩組交叉運(yùn)動(dòng)，目標(biāo)9、目標(biāo)10、目標(biāo)11及目標(biāo)12為相互臨近運(yùn)動(dòng)，目標(biāo)的運(yùn)動(dòng)方向如圖6的箭頭所示。算法多幀積累的幀數(shù)L=10，跨幀構(gòu)建狀態(tài)轉(zhuǎn)移集合的最大丟點(diǎn)個(gè)數(shù)P=3，輸出航跡有效長度Q=5，連續(xù)幀構(gòu)建狀態(tài)轉(zhuǎn)移集合的航跡外推點(diǎn)數(shù)R=3，最大加速度Vmax=600 m/s。1級(jí)檢測(cè)門限γ1依據(jù)FFAR確定，2級(jí)檢測(cè)門限γ2由105次蒙特卡羅仿真實(shí)驗(yàn)確定。

圖6 仿真場(chǎng)景設(shè)置

圖7為FFAR=10-1時(shí)，3種算法在不同信噪比下的檢測(cè)性能對(duì)比，圖7(a)～(c)分別為有效檢測(cè)目標(biāo)數(shù)、漏檢目標(biāo)數(shù)及虛假檢測(cè)目標(biāo)數(shù)的對(duì)比曲線。由圖7(a)和(b)可知，TS-DP-TBD算法的檢測(cè)性能最差，原因是該算法采用航跡剪枝機(jī)制，在目標(biāo)臨近時(shí)難以檢測(cè)弱回波目標(biāo)。STC-DP-TBD、MSC-DP-TBD兩種算法的檢測(cè)性能相當(dāng)，原因是上述兩種算法均采用STC處理策略，能夠?qū)εR近目標(biāo)進(jìn)行有效檢測(cè)。由圖7(c)可知信噪比小于等于7 dB時(shí)，3種算法采用跨多幀構(gòu)建狀態(tài)轉(zhuǎn)移集合，在狀態(tài)轉(zhuǎn)移集合的構(gòu)建過程中，關(guān)聯(lián)波門逐步擴(kuò)大，導(dǎo)致虛假航跡在運(yùn)動(dòng)空間進(jìn)行積累，產(chǎn)生大量的虛假航跡；當(dāng)信噪比大于7 dB時(shí)，以上算法幾乎不存在虛假航跡，原因是在高SNR下通過得分函數(shù)的能量積累能夠有效區(qū)分真實(shí)航跡和虛假航跡。

(a)有效檢測(cè)目標(biāo)數(shù) (b)漏檢測(cè)目標(biāo)數(shù) (c)虛假檢測(cè)目標(biāo)數(shù)

圖8、圖9分別為FFAR=10-2、Pfa=10-3時(shí)，3種算法在不同信噪比下的檢測(cè)性能對(duì)比，由圖8以及圖9(a)和(b)可知，在信噪比小于等于7 dB時(shí)以上算法均存在不同程度的漏檢，原因是在低FFAR下一級(jí)檢測(cè)門限升高會(huì)剔除部分目標(biāo)真實(shí)點(diǎn)跡導(dǎo)致漏檢，而當(dāng)SNR>7dB時(shí)，僅TS-DP-TBD算法存在漏檢，另外兩種算法均不存在漏檢且檢測(cè)性能相當(dāng)。由圖8和圖9(c)可知，在低FFAR下以上算法僅存在較少數(shù)量的虛假航跡，原因是在低Pfa下一級(jí)檢測(cè)門限升高會(huì)剔除絕大部分虛假點(diǎn)跡，抑制虛假航跡的產(chǎn)生。

(a)有效檢測(cè)目標(biāo)數(shù) (b)漏檢測(cè)目標(biāo)數(shù) (c)虛假檢測(cè)目標(biāo)數(shù)

(a)有效檢測(cè)目標(biāo)數(shù) (b)漏檢測(cè)目標(biāo)數(shù) (c)虛假檢測(cè)目標(biāo)數(shù)

由表2可知，在不同F(xiàn)FAR下MSC-DP-TBD相較STC-DP-TBD算法在運(yùn)算效率上均有明顯提升。該算法采用根節(jié)點(diǎn)標(biāo)簽對(duì)量測(cè)數(shù)據(jù)進(jìn)行空間聚類劃分，在不同聚類之間進(jìn)行解耦的獨(dú)立處理，可有效剔除無效點(diǎn)跡對(duì)航跡構(gòu)建的關(guān)聯(lián)干擾。另外，由STC-DP-TBD與MSC-DP-TBD兩種算法在不同Pfa下的運(yùn)算復(fù)雜度對(duì)比可知，聚類步驟最多能夠降低算法50%以上的運(yùn)算復(fù)雜度。

表2 執(zhí)行時(shí)間對(duì)比表 s

5 結(jié)束語

筆者分析了TS-DP-TBD算法和STC-DP-TBD算法的特點(diǎn)和不足，針對(duì)TS-DP-TBD算法在多目標(biāo)鄰近時(shí)檢測(cè)性能下降，STC-DP-TBD算法的運(yùn)算復(fù)雜度高，工程上難以實(shí)現(xiàn)，提出了一種對(duì)量測(cè)空間進(jìn)行聚類的MSC-DP-TBD算法。該算法通過構(gòu)建狀態(tài)轉(zhuǎn)移集合并對(duì)量測(cè)點(diǎn)跡進(jìn)行標(biāo)簽標(biāo)記，獲取多目標(biāo)在量測(cè)空間的分布特征，通過聚類處理對(duì)量測(cè)空間進(jìn)行劃分，并在不同聚類內(nèi)獨(dú)立運(yùn)行STC-DP-TBD算法。通過數(shù)學(xué)分析與仿真實(shí)驗(yàn)可知，所提算法的檢測(cè)性能與STC-DP-TBD相當(dāng)，同時(shí)運(yùn)算復(fù)雜度大幅度降低。仿真實(shí)驗(yàn)和性能分析驗(yàn)證了該算法的有效性和工程的可行性。