基于代數(shù)圖論的修正貝葉斯群目標(biāo)航跡起始算法

姜 琦 王 銳 周 超 張?zhí)烊?胡 程

(北京理工大學(xué)信息與電子學(xué)院雷達技術(shù)研究所 北京 100081)

(北京理工大學(xué)衛(wèi)星導(dǎo)航電子信息技術(shù)教育部重點實驗室 北京 100081)

1 引言

針對空中集群生物的探測與跟蹤對人造設(shè)施防撞、農(nóng)業(yè)災(zāi)害預(yù)警、生物學(xué)研究等均具有重要意義，已成為雷達學(xué)界的熱門研究領(lǐng)域[1,2]。探測空中集群生物的雷達可分為監(jiān)測大范圍生物群體遷徙的雷達(如監(jiān)測鳥類、昆蟲遷徙的天氣雷達)[3]和獲取小范圍生物目標(biāo)的航跡、特征參數(shù)等信息的雷達(如機場防鳥撞雷達)[4]，本文以第2種雷達為研究背景。為了能夠持續(xù)跟蹤并提取集群生物目標(biāo)的特征信息，首先需要起始各個生物集群目標(biāo)的航跡，具體包括分群檢測與航跡確認(rèn)兩個步驟。

分群檢測的目的在于將監(jiān)測空間內(nèi)得到的量測集合按照一定的規(guī)則劃分為若干子集[5]。以態(tài)勢估計等應(yīng)用為背景的分群算法(如D-S證據(jù)理論[6]、模板匹配法[7]、貝葉斯網(wǎng)絡(luò)分群法[8]，聚類算法[9,10]等)需要事先給定分群數(shù)量或模板，適合編隊目標(biāo)的分群，不適用于生物集群目標(biāo)。近期，基于相似度矩陣的分群算法得到較多關(guān)注[11–13]，此類方法不需要目標(biāo)個數(shù)等先驗信息，分群結(jié)果不受點跡順序影響，能正確反映跟蹤期間群目標(biāo)的動態(tài)變化。但現(xiàn)有相似度矩陣法需要同一個群內(nèi)所有目標(biāo)兩兩相似，在集群生物場景中易導(dǎo)致邊緣個體被排除在外，或?qū)儆谀硞€子群的目標(biāo)被誤分至另一個子群內(nèi)等錯誤結(jié)果。

分群檢測后需要計算各個子群的等效量測，計算方法包括K-方法、集群引晶法[14]、幾何中心法[5]、重心法[15,16]、距離-幅度加權(quán)法[17]等。得到等效量測后轉(zhuǎn)入航跡確認(rèn)步驟，總體上可分為順序處理和批處理兩大類[18]?，F(xiàn)有群目標(biāo)航跡確認(rèn)方法通常沿用傳統(tǒng)單目標(biāo)航跡確認(rèn)策略，利用等效量測信息計算航跡為真的后驗概率，如修正的邏輯法[17]和基于運動補償?shù)暮桔E起始方法[19]等。然而航跡起始階段的非理想量測因素會導(dǎo)致等效量測點狀態(tài)不穩(wěn)定，降低了傳統(tǒng)航跡起始算法的效率。

基于以上問題，本文提出基于代數(shù)圖論的修正貝葉斯群目標(biāo)航跡起始算法，引入代數(shù)圖論定量描述監(jiān)測空間內(nèi)目標(biāo)間的相似關(guān)系，根據(jù)連通圖性質(zhì)完成分群計算；在經(jīng)典貝葉斯框架的基礎(chǔ)上對似然比的定義予以修正，用泊松分布描述群內(nèi)量測數(shù)目的特性，避免了因等效量測殘差過大導(dǎo)致航跡確認(rèn)出現(xiàn)錯誤。實測數(shù)據(jù)處理結(jié)果證明，本文提出的航跡起始算法能夠準(zhǔn)確劃分監(jiān)測空間內(nèi)的群目標(biāo)，擁有比傳統(tǒng)貝葉斯航跡確認(rèn)算法更優(yōu)的性能。

2 基于代數(shù)圖論的修正貝葉斯群目標(biāo)航跡起始算法

2.1 基于代數(shù)圖論的分群檢測算法

本文引入代數(shù)圖論思想，用 nk個頂點(vertex)表示量測集合內(nèi)的nk個 點跡，頂點集記為{ v1,v2,···,vnk}；如果兩個目標(biāo)點跡根據(jù)一定準(zhǔn)則判為相似，則用1條邊(edge)將兩個相似點跡對應(yīng)的頂點vi和vj連接起來，稱 vi和vj相 似；將得到的圖記為 Γ；定義圖Γ的相似度矩陣A (Γ)內(nèi)的元素為

由此得到相似度矩陣。各個點跡默認(rèn)同自身相似，因此相似度矩陣為對角線元素全為1的0-1二值對稱矩陣。若多個點跡被劃分至同一個群目標(biāo)內(nèi)，該群對應(yīng)的圖中任意兩個頂點都能通過一定的步長(walk)相連，這種圖稱為連通圖(connected graph)。對相似度矩陣進行初等行列變換，將1元素匯聚到對角線上的多個分塊方陣內(nèi)，檢查各個非零分塊方陣內(nèi)的元素對應(yīng)哪些點跡，即可得知各個群目標(biāo)包含哪些目標(biāo)。

相似度矩陣法需要檢測對角線上的非零分塊方陣，要求分塊方陣內(nèi)的元素全部為1，即同一個群內(nèi)的所有目標(biāo)兩兩相似。如果分塊方陣內(nèi)元素不全為1，分群結(jié)果就會出錯。該方法對密集機群等編隊目標(biāo)可取得較好的效果，此類目標(biāo)內(nèi)部個體相互間的距離通常較為接近。但由于生物集群目標(biāo)(如遷徙鳥群)常采用“人字形”、“一字形”等編隊方式，隊形邊緣個體之間的距離通常遠(yuǎn)大于相鄰個體間的距離。此時為了保證群內(nèi)所有個體兩兩相似，相似門限必須大于相距最遠(yuǎn)的兩個體間的距離，導(dǎo)致相似門限過大，很容易將不屬于該群的目標(biāo)誤分至該群內(nèi)。以圖1為例，監(jiān)測空間內(nèi)有2個鳥群，分別以“人字形”和“一字形”編隊飛行，需分別跟蹤；在分群檢測時，為了保證上方“人字形”編隊邊緣的 a1個 體與a2個體相似，門限必須大于狀態(tài)空間的距離 l1； 由于l1>l2，這會導(dǎo)致下方“一字形”編隊的個體b1同 樣與a1相似，造成分群結(jié)果出錯。

圖1 傳統(tǒng)相似度矩陣法在應(yīng)用中的局限性

圖2 簡化后的相似度關(guān)系

根據(jù)代數(shù)圖論的結(jié)論，擁有 m個頂點的圖 Γ是陣M1,M2,···,Mk，將同一個子群內(nèi)的目標(biāo)全部排列至對角線上的分塊矩陣內(nèi)，即連通圖的充要條件是其相似度矩陣 A 的m ?1次冪Am?1內(nèi)部元素均為非零元素[22]；容易證明，當(dāng)擁有 m 個頂點的圖是連通圖時，矩陣An?1(n ≥m)內(nèi)部同樣均為非零元素。根據(jù)上述性質(zhì)，如果監(jiān)測空間內(nèi)的 nk個 點跡同屬一個群目標(biāo)，那么矩陣Ank?1內(nèi)部均為非零元素。實際情況中，監(jiān)測空間內(nèi)常含有不止1個群目標(biāo)，假設(shè)nk個 點跡屬于lk個子群，根據(jù)相似度矩陣的定義，如果能找到初等行列交換矩

(3)完成步驟(1)和(2)后，若從第2行第3列元素開始，直至第2行第i列的矩陣元素值連續(xù)不為0，則判定此連續(xù)若干列所對應(yīng)的量測同屬一個群目標(biāo)；再從第i+1行第i+2列開始，按照同樣的步驟進行行列交換和判定操作，以此類推直至完成第nk+1行 第nk+1列操作，所有非0元素構(gòu)成多個分塊矩陣B1,B2,···,Blk，即

(4) 提取并記錄向量n1,n2,···,nlk內(nèi)部的數(shù)字，得到各個群目標(biāo)內(nèi)點跡的編號，計算 lk個子群的等效 量測。

2.2 修正的貝葉斯航跡確認(rèn)算法

分群檢測完成后，需要判斷航跡是否為真，本文將此過程稱為群目標(biāo)航跡的預(yù)起始階段。預(yù)起始階段的結(jié)果有兩種：確認(rèn)航跡為真并轉(zhuǎn)入跟蹤濾波，或者確認(rèn)為假并丟棄?；谪惾~斯框架的航跡確認(rèn)算法是實際中常采用的方法，其核心是根據(jù)當(dāng)次掃描得到的量測集合計算航跡為真的后驗概率，其遞推形式為[23,24]

其中， T 表示量測屬于真實航跡的事件， F表示量測來自虛假回波的事件，L (Dk)為似然比

其中，P (Dk|T)表示航跡為真條件下得到量測集合Dk的概率，P (Dk|F)表示航跡為假條件下得到量測集合 Dk的概率，P (T|Dk)表示第k時刻航跡為真的后驗概率。

意美(即建筑美)。這三個翻譯版本來看，題目是不同的，首先，這三個版本都采用形容詞修飾名詞的結(jié)構(gòu)，“未選擇的路”“未選之路”“未踏之徑”。區(qū)別在于顧版譯文采用白話文的形式。詩的題目為“Theroad not taken”是過去分詞做后置定語，可見題目翻譯與原詩歌在句式結(jié)構(gòu)上較為貼合。

經(jīng)典單目標(biāo)、多目標(biāo)跟蹤場景中，P (Dk|T)的定義為航跡為真條件下在已知的具體位置得到量測點的條件概率。由于群目標(biāo)在航跡起始階段受到多種非理想因素(如分辨率受限、部分目標(biāo)未進入監(jiān)測空間、視線遮擋等)的干擾，導(dǎo)致等效量測的計算值和預(yù)測值存在較大殘差，降低了似然比的值，從而導(dǎo)致航跡確認(rèn)性能的下降。

本文所提修正的貝葉斯航跡確認(rèn)算法，對P(Dk|T)的定義進行修正，以1個子群內(nèi)有nk個量測點為例

式(10)的計算涉及復(fù)雜的條件概率求解。空中集群生物通常飛行高度較低，雷達回波內(nèi)存在較多雜波干擾分量，在雷達進行跟蹤前應(yīng)首先進行雜波點跡剔除。本文針對的是雜波剔除處理后的群目標(biāo)航跡起始問題，此時可認(rèn)為在監(jiān)測空間內(nèi)殘留虛假點跡是小概率事件，同時出現(xiàn)多個虛假點跡的概率更小，因此可以對P (Dk|T)做以下簡化處理

該處理方法通過犧牲一定的數(shù)值結(jié)果換取計算效率的提升。本文利用泊松分布描述當(dāng)群目標(biāo)真實存在時量測集合包含nk個點跡的概率

其中， Vk表 示群體積，μ 表示與群目標(biāo)密度相關(guān)的系數(shù)。本文認(rèn)為虛假量測在整個空域中滿足獨立、均勻分布，則P (Dk|F)的表達式可寫為

其中，βF表 示監(jiān)測空間中的虛假量測密度系數(shù)。完整的似然比表達式為

如果某次掃描后某預(yù)起始航跡未能與任何等效量測進行關(guān)聯(lián)，則利用上一時刻的預(yù)測狀態(tài)作為該預(yù)起始航跡當(dāng)前狀態(tài)的外推，似然比變?yōu)榱繙y缺失情況下的表達式

其中， P (nk=0|T)是雷達在群目標(biāo)存在的條件下未能檢測到任何真實量測的概率，令式(12)中的nk=0 即可求得；PF是雷達在監(jiān)測空間內(nèi)至少得到1個虛假點跡的概率

修正的貝葉斯航跡確認(rèn)算法完整步驟如下：

(1) 雷達在第k時刻對回波進行恒虛警檢測和分群檢測后得到某個新群目標(biāo)的量測集合 Dk，計算 Dk的等效量測z ?k；此時等效量測z ?k無法與任何現(xiàn)有航跡或預(yù)起始航跡進行關(guān)聯(lián)，將z ?k記錄為預(yù)起始航跡點，該預(yù)起始航跡為真的先驗概率記為P0(T)；根據(jù)目標(biāo)的自身性質(zhì)設(shè)定下一時刻的關(guān)聯(lián)門范圍；

(2) 若k+1時刻有量測集合Dk+1的等效量測點z?k+1落入關(guān)聯(lián)門，則轉(zhuǎn)入步驟(3)；若沒有等效量測點落入關(guān)聯(lián)門，轉(zhuǎn)入步驟(4)；

(3) 根據(jù)當(dāng)前時刻(記為i， 泛指i ≥k+1的任意時刻)量測集合 Di的目標(biāo)個數(shù)信息ni和群體積信息Vi，利用式(14)計算似然比結(jié)果；根據(jù)式(8)計算航跡為真的后驗概率 P (T|Di) ；如果P (T|Di)>γT，則判定預(yù)起始航跡為真并轉(zhuǎn)入航跡狀態(tài)初始化處理；如果P (T|Di)<γF，則判定預(yù)起始航跡為假并丟棄；如果 γF

(4) 利用上一時刻的預(yù)測狀態(tài)作為預(yù)起始航跡在當(dāng)前時刻狀態(tài)的外推；利用式(15)計算似然比結(jié)果；根據(jù)式(8)計算當(dāng)前時刻(記為i， 泛指i ≥k+1的任意時刻)航跡為真的后驗概率 P (T|Di)；如果P (T|Di)>γT，則判定預(yù)起始航跡為真并轉(zhuǎn)入跟蹤濾波處理；如果P (T|Di)<γF，則判定預(yù)起始航跡為假并丟棄；如果 γF

(5) 將外推狀態(tài)與當(dāng)前時刻計算得到的等效量測進行關(guān)聯(lián)，如果有新的等效量測關(guān)聯(lián)成功，則重復(fù)步驟(3)的處理流程，直至航跡為真的后驗概率P (T|Di)在 第i時 刻大于門限γT(判斷航跡為真)或小于門限 γT(判定航跡為假)；如果未能和任何新等效量測關(guān)聯(lián)成功，則重復(fù)步驟(4)的處理流程，直至航跡為真的后驗概率 P (T|Di) 在第i時刻大于門限γT(判斷航跡為真)或小于門限γT(判定航跡為假)。

3 實驗數(shù)據(jù)處理與分析

本論文依托的項目課題組于2019年10月在東營實驗基地采集了鳥群的雷達回波數(shù)據(jù)，本節(jié)利用鳥群實測數(shù)據(jù)的距離和數(shù)量信息驗證分群檢測與航跡確認(rèn)算法的有效性，給出了實測數(shù)據(jù)處理結(jié)果和與經(jīng)典方法的對比分析。

3.1 實驗場地和設(shè)備介紹

課題組于2019-10-10—2019-10-11, 2019-10-12—2019-10-13分別在東營市天鵝湖公園和黃河南大堤開展了雷達探鳥實驗。實驗地點附近濕地、水域面積較大，鳥類的種類和數(shù)量豐富，又處于候鳥遷徙通道，適合開展鳥類觀測實驗。實驗地點和現(xiàn)場圖如圖3所示。

3.2 實測鳥群數(shù)據(jù)處理結(jié)果分析

圖3 黃河南大堤觀測實驗位置和實驗現(xiàn)場圖

為全面對比分析本文提出的航跡起始算法針對不同場景的處理性能，本小節(jié)選取不同場景下的實測數(shù)據(jù)對比了本文提出的航跡起始算法和經(jīng)典航跡起始算法的性能，具體包括：(1)單目標(biāo)航跡起始性能對比；(2)單群目標(biāo)航跡起始性能對比；(3)多群目標(biāo)航跡起始性能對比。所有數(shù)據(jù)在分群檢測和航跡起始處理前已經(jīng)過雜波抑制和虛假點跡剔除，可認(rèn)為虛假點跡滿足稀疏和均勻分布條件。

3.2.1 單群目標(biāo)航跡起始性能對比

2019年10月13日下午14:17，實驗團隊在黃河南大堤采集到了約700 m高度處的6只雁類個體組成的鳥群回波數(shù)據(jù)，鳥群在雷達波束內(nèi)的駐留時間約2.5 s，如圖4所示。圖5給出了本文提出的基于代數(shù)圖論的修正貝葉斯群目標(biāo)航跡起始算法和傳統(tǒng)貝葉斯航跡起始算法應(yīng)用于群目標(biāo)回波的效果對比，其中紅色五星代表初始幀的群目標(biāo)等效量測，洋紅方塊代表預(yù)起始階段等效量測，綠色圓圈代表航跡確認(rèn)起始并轉(zhuǎn)入跟蹤濾波的等效量測，紅色叉號代表航跡被丟棄。本文提出的算法首先完成量測空間的子群劃分，再利用修正的貝葉斯航跡確認(rèn)算法計算航跡為真的后驗概率，經(jīng)過3幀數(shù)據(jù)后成功確認(rèn)航跡存在，轉(zhuǎn)入跟蹤濾波流程；而傳統(tǒng)貝葉斯航跡起始算法由于第3幀數(shù)據(jù)等效量測的預(yù)測值和真實值之間的殘差過大，導(dǎo)致后驗概率低于門限，被錯判為虛假航跡。

3.2.2 多群目標(biāo)航跡起始性能對比

2019年10月13日下午15:46，實驗團隊在黃河南大堤采集到了300～400 m高度范圍內(nèi)的多個鳥群回波數(shù)據(jù)，包括1個單目標(biāo)和2個群目標(biāo)，從中截取了一段同時存在1個單目標(biāo)和2個群目標(biāo)的數(shù)據(jù)進行處理。圖6給出了本文所提分群檢測算法對多個單/群目標(biāo)的分群結(jié)果，以及航跡起始算法的結(jié)果對比。其中紅色五星代表初始幀的目標(biāo)等效量測，洋紅方塊代表預(yù)起始階段等效量測，綠色圓圈代表航跡確認(rèn)起始并轉(zhuǎn)入跟蹤濾波的等效量測。由圖6(a)可知，本文提出的分群檢測算法能夠正確劃分監(jiān)測空間內(nèi)的3個單/群目標(biāo)；單目標(biāo)經(jīng)過4幀數(shù)據(jù)后確認(rèn)航跡存在，2個群目標(biāo)分別經(jīng)過2幀和3幀數(shù)據(jù)后確認(rèn)航跡存在；在正確分群的基礎(chǔ)上，傳統(tǒng)貝葉斯航跡起始算法的處理結(jié)果如圖6(b)所示，單目標(biāo)經(jīng)過3幀數(shù)據(jù)后確認(rèn)航跡存在；2個群目標(biāo)經(jīng)過3幀數(shù)據(jù)后確認(rèn)航跡存在。由于該組數(shù)據(jù)等效量測變化較為平穩(wěn)，傳統(tǒng)算法未出現(xiàn)航跡誤丟棄的現(xiàn)象，總體來看，該場景下本文算法對群目標(biāo)的航跡起始效率優(yōu)于傳統(tǒng)算法。

圖4 6只個體組成的鳥群現(xiàn)場照片和雷達回波

圖5 單個群目標(biāo)航跡起始結(jié)果對比

圖6 多個單/群目標(biāo)處理結(jié)果對比

4 結(jié)束語

本文針對空中集群生物目標(biāo)跟蹤問題，提出一種基于代數(shù)圖論的修正貝葉斯群目標(biāo)航跡起始算法。引入代數(shù)圖論和連通圖的性質(zhì)后，本文所提基于代數(shù)圖論的分群檢測算法能準(zhǔn)確劃分量測集合內(nèi)的各個子群目標(biāo)，放寬了現(xiàn)有分群矩陣方法對群內(nèi)目標(biāo)的相似度限制，實現(xiàn)了群目標(biāo)量測集合的準(zhǔn)確劃分；對經(jīng)典貝葉斯航跡起始算法的似然比定義進行修正后，本文所提航跡確認(rèn)算法提升了針對群目標(biāo)(特別是密集群目標(biāo))的航跡確認(rèn)效率，避免了經(jīng)典貝葉斯航跡起始算法因等效量測殘差過大導(dǎo)致航跡誤丟棄。實測數(shù)據(jù)處理結(jié)果證明本文提出的算法針對群目標(biāo)的航跡起始性能超過了經(jīng)典貝葉斯算法，同時保留了針對單目標(biāo)的優(yōu)良航跡起始性能。