基于代數圖論的修正貝葉斯群目標航跡起始算法

姜 琦 王 銳 周 超 張天然 胡 程

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

(北京理工大學衛星導航電子信息技術教育部重點實驗室 北京 100081)

1 引言

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

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

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

基于以上問題，本文提出基于代數圖論的修正貝葉斯群目標航跡起始算法，引入代數圖論定量描述監測空間內目標間的相似關系，根據連通圖性質完成分群計算；在經典貝葉斯框架的基礎上對似然比的定義予以修正，用泊松分布描述群內量測數目的特性，避免了因等效量測殘差過大導致航跡確認出現錯誤。實測數據處理結果證明，本文提出的航跡起始算法能夠準確劃分監測空間內的群目標，擁有比傳統貝葉斯航跡確認算法更優的性能。

2 基于代數圖論的修正貝葉斯群目標航跡起始算法

2.1 基于代數圖論的分群檢測算法

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

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

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

圖1 傳統相似度矩陣法在應用中的局限性

圖2 簡化后的相似度關系

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

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

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

2.2 修正的貝葉斯航跡確認算法

分群檢測完成后，需要判斷航跡是否為真，本文將此過程稱為群目標航跡的預起始階段。預起始階段的結果有兩種：確認航跡為真并轉入跟蹤濾波，或者確認為假并丟棄。基于貝葉斯框架的航跡確認算法是實際中常采用的方法，其核心是根據當次掃描得到的量測集合計算航跡為真的后驗概率，其遞推形式為[23,24]

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

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

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

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

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

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

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

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

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

如果某次掃描后某預起始航跡未能與任何等效量測進行關聯，則利用上一時刻的預測狀態作為該預起始航跡當前狀態的外推，似然比變為量測缺失情況下的表達式

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

修正的貝葉斯航跡確認算法完整步驟如下：

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

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

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

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

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

3 實驗數據處理與分析

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

3.1 實驗場地和設備介紹

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

3.2 實測鳥群數據處理結果分析

圖3 黃河南大堤觀測實驗位置和實驗現場圖

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

3.2.1 單群目標航跡起始性能對比

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

3.2.2 多群目標航跡起始性能對比

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

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

圖5 單個群目標航跡起始結果對比

圖6 多個單/群目標處理結果對比

4 結束語

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