一種基于蝙蝠算法的多目標跟蹤數據關聯方法

王宇杰，李 宇，黃海寧

(1. 中國科學院聲學研究所，北京100190；2. 中國科學院先進水下信息技術重點實驗室，北京100190；3. 中國科學院大學，北京100049)

0 引 言

數據關聯問題一直是多目標跟蹤方法中關鍵性的問題，它決定了目標更新時所使用的探測信息，所以數據關聯算法的性能直接決定了多目標跟蹤算法的跟蹤性能。國內外學者對數據關聯的方法進行了深入的研究，其中最早提出的數據關聯方法是最近鄰算法 (Nearest Neighbor, NN)[1]，它直接將量測與距離最近的目標關聯，方法簡單，運算量小，但在處理多目標關聯問題時，關聯正確率低。在理想化的建模假設下，多假設跟蹤算法 ( Multiple Hypothesis Tracking, MHT)[1-3]被認為是在貝葉斯角度的最優方法，但當目標數目增加時，它需要很大的計算量和內存。概率數據關聯算法(Probabilistic Data Association, PDA)[1,3]計算落入目標跟蹤門內的所有量測的關聯概率，依據概率進行關聯，但在目標數目增加時，PDA 難以滿足關聯性能要求。在此基礎上發展出的聯合概率數據關聯算法 (Joint Probabilistic Data Association,JPDA)[3]將PDA 推廣到了多個目標的情況，使用所有觀測值和所有目標進行概率計算，是對多目標進行跟蹤的比較優秀的方法，但是需要的計算量極大。

數據關聯問題和組合優化問題具有很高的類似度，對多目標數據關聯問題建模，演化為組合優化問題，再利用一些智能優化算法進行最優估計是解決多目標數據關聯問題的一個方向[4-5]，一些仿生優化算法[6]在多目標關聯領域也取得了較好的效果。蝙蝠算法(Bat Algorithm, BA)[7-9]是Yang于2010 年提出的一種仿生優化算法，近幾年蝙蝠算法已經在很多領域取得了應用。本文通過對數據關聯問題進行建模，并對蝙蝠算法的搜索更新規則進行改進，提出了一種適用于數據關聯的改進蝙蝠算法(Bat Algorithm Data Association,BADA)，使其可以成功應用于數據關聯問題。經過仿真驗證，改進的蝙蝠算法應用于數據關聯切實可行，并且有比較好的效果，在計算復雜度上也遠低于傳統算法。

1 數據關聯優化形式

(1) 對于每一個量測，最多只有一個目標與其關聯。

(2) 對于每一個目標，也只有一個量測與其關聯。

數據關聯的目標函數可以表示為

式中：gi,j表示目標i 和量測j 的關聯程度；uij為目標i 和量測j 關聯情況。

由上述兩個假設得到的約束條件為

由uij組成關聯矩陣U，uij的值為0 或1，當量測與第i 個目標關聯時，uij為1，否則為0，u0j表示第j 個量測來源于雜波信號。關聯矩陣U 的表達式為

對于量測與目標之間的關聯程度gi,j，本文使用似然函數來評價：

其中：

式(5)、(6)中：zi表示第i 個目標該時刻的預測值；yj表示第j 個目標的測量值。t 時刻目標一步預測的狀態矩陣為，S 表示殘差。

當目標的預測值和目標該時刻回波正確關聯時，則似然函數gi,j的值最大。在理想情況下，當所有目標的預測值都和目標該時刻的回波正確關聯，則目標函數J 的值最大。所以，通過將數據關聯問題建模成組合優化問題，最大化目標代價函數J，可以解決數據關聯問題。

2 蝙蝠算法描述

蝙蝠算法是模仿蝙蝠回聲定位系統提出的一種仿生算法。在自然界，蝙蝠通過向四周發射超聲波脈沖進行捕獵和定位。在接收到回波之后，它們可以確定自己的位置，并且發現周圍的獵物和障礙。再者，在蝙蝠群中，每一只蝙蝠都可以通過獨立搜索發現最有營養的區域，或者和種群中其它個體交流，向其它個體發現的最有營養的區域移動。蝙蝠算法最重要的思想是蝙蝠的定位系統運作方式，為了對其有一些合適的調整，Yang 提出了以下規則[7-9]：

(1) 所有的蝙蝠都使用回聲定位系統對目標位置進行探測，并且可以區分獵物和障礙。

(2) 所有的蝙蝠在一定的位置以一定的速度隨機飛行去搜索目標，它們發射的聲波頻率、聲強和聲脈沖發射頻率以一定的規律變化。在理想化的規則里，假設每一個蝙蝠都可以自動地調整聲波頻率和脈沖發射的頻率，這種自動調節系統依據離目標獵物的遠近進行調節。

(3) 在真實的環境中，蝙蝠發聲聲強的變化可以依據多種方式。而我們假設聲強是從最大聲強向最小的聲強變化。

由上述規則，Yang 提出的經典蝙蝠算法，算法如下：

(1) 定義目標函數ξ ( x)；

(3) 對蝙蝠群中的每一只蝙蝠的位置xi進行步驟(4)；

(5) 對蝙蝠群中的每一只蝙蝠位置ix 進行步驟(6)～(11)；

(6) 使用式(7)、(8)、(9)產生新的蝙蝠位置；

(8) 本地搜索：在最優蝙蝠位置附近更新該只蝙蝠；

(10) 接受該蝙蝠為當前最優蝙蝠x?；

(12) n=n+1；

(13) 循環執行步驟(5)～(12)，直至達到結束條件；

(14) 排序蝙蝠群中的蝙蝠，輸出最優蝙蝠位置x?。在步驟(7)、(9)中rand[0,1]表示取0～1 之間的隨機數。

在每一次循環中，蝙蝠群中的每一只蝙蝠都會進行移動，對于每次移動，使用式(7)～(9)進行更新：

其中：β 是一個0～1 之間的隨機數；在算法流程中x?是蝙蝠群中當前時刻最優蝙蝠位置；和代表了第i 只蝙蝠在第n 次迭代中的速度和位置。式(7)被使用來限制蝙蝠移動的范圍和速度。算法流程中第(8)步本地搜索部分，是從當前時刻蝙蝠群中選擇最優蝙蝠，使用隨機漫步在最優蝙蝠附近生成新的蝙蝠方案更新該只蝙蝠。

這里 的α 和γ 是固定值，并且0＜α ＜1 ，γ＞ 0。從式(10)和(11)中可以看出，隨著n 趨向于無窮大時，趨向于0，趨向于。在很多文章中，為了簡化算法，α 和γ 的取值一般是相同的，在0.90～0.99 范圍內，本文選取α =γ = 0.98。

3 適用于數據關聯的蝙蝠算法

經典蝙蝠算法主要用于解決連續性優化問題，而組合優化問題是一種離散優化問題。受蝙蝠算法解決旅行商問題(Traveling Salesman Problem, TSP)[10]的啟發，需要對經典蝙蝠算法進行一些改進，以使其可以適用于數據關聯問題。

在本文所提出的算法中，蝙蝠群的每一只蝙蝠都代表一種可能的關聯方案。比如某時刻存在4個目標，傳感器探測到了9 個量測，則蝙蝠群中的第i 只蝙蝠位置可能為xi= (2,5,3,9)，其第一個位置的2 表示第二個量測和第一個目標關聯，其余類似。經典蝙蝠算法中的一些參數ri、 Ai、fi和iv 也并不都適用于離散的數據關聯，需要進行一些新的定義。

在經典的算法中，速度vi的更新由聲波頻率if 和該蝙蝠與最優蝙蝠之間的距離共同決定，如式(8)所示，其顯然是無法應用于離散的數據關聯問題。從式(8)中可以看出，速度的大小是依賴于該蝙蝠與最優蝙蝠之間的距離再乘上一個系數，聲波頻率fi。針對數據關聯問題，本文對其進行了調整，使用漢明距離DHamming來定義兩只蝙蝠的距離，定義該蝙蝠的速度為1 到漢明距離之間的一個隨機整數，表達式為

式中，rand[]?表示取隨機數。

式(9)是蝙蝠算法中蝙蝠的更新運算，該式同樣無法應用于數據關聯問題中，本文定義運算⊕進行蝙蝠的更新，公式為

運算⊕參照以下規則進行：

(1) 如某一蝙蝠為(2,5,3,9)，首先隨機確定一個位置，比如第三個位置，然后隨機生成一個量測編號，比如4，使用新生成的量測編號代替原來位置的量測編號，則該只蝙蝠的鄰近蝙蝠就是(2,5,4,9)。

(2) 如果隨機產生的量測編號發生重復，比如第三個位置隨機生成的量測編號為2，而(2,5,2,9)不滿足前文提出的第二條假設。這時對調產生重復的兩個量測編號的位置，則該只蝙蝠的鄰近蝙蝠就是(3,5,2,9)。

使用上述提出的產生鄰近蝙蝠位置的方法，在每一次迭代過程中，產生個該蝙蝠的鄰近蝙蝠，在其中選擇最優的一只更新位置，得到位置。

下面給出了適用于數據關聯的改進后的蝙蝠BADA 算法如下：

(1) 使用式(1)定義目標函數J ( x )；

(3) 對蝙蝠群中的每一只蝙蝠ix 進行步驟(4)；

(5) 對蝙蝠群中的每一只蝙蝠位置ix 進行步驟(6)～(11)；

(6) 使用式(12)、(13)產生新的蝙蝠；

(8) 本地搜索：在最優蝙蝠位置附近更新該只蝙蝠位置；

(10) 接受該蝙蝠位置為最優蝙蝠位置x?；

(12) n=n+1；

(13) 循環執行步驟(5)～(12)，直至達到結束條件；

(14) 排序蝙蝠群中的蝙蝠位置，輸出最優蝙蝠位置x?。

結束條件一般為目標函數達到要求或者循環次數到達預設值。在本文中，設置當循環次數n達到15 次時，算法結束，排序蝙蝠群中的蝙蝠位置，輸出的最優蝙蝠位置x?為最終的數據關聯結果。

4 仿真實驗與實測數據處理

4.1 仿真實驗

為驗證BADA 算法的性能，仿真了雙目標情況下的方位歷程信息。兩個目標起始方位分別為250°和280°，在65 s 附近發生了一次交叉，如圖1 所示。圖1 中圓圈和三角分別表示目標1 和目標2 的回波，干擾回波沒有在圖中體現。設檢測概率Pg=0.95，干擾回波在觀測門限內均勻分布，雜波密度為0.1，目標回波服從正態分布，存在均值為0，標準差為0.6 的加性高斯白噪聲，使用卡爾曼濾波進行跟蹤。用NN 算法和JPDA 算法進行對比，結果如圖2 所示。JPDA 算法和BADA 算法在兩個目標發生交叉時都可以進行正確的關聯，而NN 算法在目標發生交叉時，發生關聯錯誤的概率較大。

圖1 兩目標回波仿真數據Fig.1 Echo simulation data of two targets

圖2 NN 算法、JPDA 算法和BADA 算法仿真結果比較Fig.2 Comparisons between the simulation results of NN algorithm, JPDA algorithm and BADA algorithm

分別使用BADA 算法、JPDA 算法和NN 算法進行1 000 次的獨立重復試驗，統計其平均絕對誤差、平均運算時間和正確關聯概率。一次正確的關聯為兩個目標的跟蹤結果始終保持在目標真實位置的附近，如圖2 中JPDA 算法和BADA 算法的結果，而NN 算法對于目標2 的跟蹤在交叉時發生了錯誤。兩個目標中只要存在一個目標發生關聯跟蹤錯誤，即認為關聯跟蹤錯誤。正確關聯概率使用式(14)計算：

其中：η 為正確關聯概率；l 為正確關聯跟蹤次數；K 為獨立重復試驗總數，本文中取1 000 次。

在當高斯噪聲均值為0、標準差為0.3 時的情況下，3 種算法都有很高的正確關聯概率，NN 算法的運算時間最短，誤差最大，比較結果列于表1中。當高斯噪聲均值為0、標準差為0.6 時算法性能比較結果見表2。BADA 算法在誤差和正確關聯概率與JPDA 算法相近的情況下，運算時間極大的減小，而NN 算法雖然運算時間極快，但其誤差較大，正確關聯概率過低，在應用中會出現大量的關聯錯誤。

表1 雙目標情況下3 種算法性能比較(噪聲標準差=0.3)Table 1 Performance comparison of three algorithms in the case of two targets ( noise standard deviation = 0.3)

表2 雙目標情況下3 種算法性能比較(噪聲標準差=0.6)Table 2 Performance comparison of three algorithms in thecase of two targets ( noise standard deviation = 0.6)

為驗證更為復雜情況下的算法性能，仿真了同時存在6 個目標的方位歷程數據，6 個目標發生了多次交叉，復雜度較高。圖3 是使用BADA 算法的關聯跟蹤結果，不同標記分別代表不同目標的回波。干擾回波在觀測門限內均勻分布，雜波密度為0.1，目標回波服從正態分布，存在均值為0，標準差為0.35 的加性高斯白噪聲，干擾回波同樣存在但未在圖中體現，不同顏色的軌跡是使用BADA 算法對不同目標進行關聯跟蹤的結果。可以看出在軌跡更為復雜的多目標情況下，BADA算法對6 個目標進行了準確的關聯，未出現關聯跟蹤錯誤。

圖3 基于BADA 算法六目標跟蹤結果Fig.3 Tracking results of six targets based on BADA algorithm

同樣，用上述的6 個目標方位仿真數據，分別對BADA 算法、JPDA 算法和NN 算法進行1000 次獨立、重復試驗，計算3 種算法的平均絕對誤差、平均運算時間和正確關聯概率。在正確關聯概率的計算中，只要有一個目標關聯錯誤即為錯誤關聯。算法性能比較結果見表3，BADA 算法的運算時間相較于JPDA 算法有了明顯的降低，只有不到后者的10%，具有更好的實時運算性能，且正確關聯概率也處于較高水平。

表3 6 個目標情況下3 種算法性能比較Table 3 Performance comparison of three algorithms in the case of six targets

4.2 實測數據處理

圖4 是對某次海試的某段數據進行頻域波束形成之后的結果。在這段時間內存在多個目標并且目標的方位軌跡之間存在交叉、平行和逐漸靠近，也存在有大量的干擾和噪聲，復雜度極高，且具有一定代表性。閾值檢測之后使用BADA 算法進行關聯跟蹤，結果如圖5 所示。圖5 中白色圓圈是對方位歷程圖進行閾值檢測的結果，閾值檢測過程中每10 s 得到一個方位檢測結果，不同顏色分別代表不同目標的跟蹤結果。

由圖5 可見，BADA 算法對6 個較強目標進行了正確的關聯，在復雜軌跡情況和干擾回波影響下都沒有發生關聯跟蹤錯誤。

圖4 某次海試的某段方位歷程圖Fig.4 A section of bearing-time-record in a certain sea trial

圖5 BADA 算法關聯跟蹤結果Fig.5 Tracking results of the BADA algorithm

5 結 論

針對多目標跟蹤中的數據關聯問題，本文提出了一種基于蝙蝠算法的數據關聯方法。將數據關聯問題建模成組合優化問題，然后通過改進蝙蝠算法，使其可以適用于解決多目標跟蹤中的數據關聯問題，并且取得了較好的效果。該方法本質上是一種近似最優的方法。通過仿真結果可以看出，該方法在多目標、多雜波、多航跡交叉的情況下可以正確地關聯目標，關聯跟蹤性能與JPDA 處于同一級別，運算復雜度迅速減小，實時性更好。通過對試驗數據的分析，證明基于蝙蝠算法的數據關聯方法應用于真實情況是切實可行的，并且有較好的關聯跟蹤效果。