改進的多擴展目標PHD濾波算法*

彭聰,王杰貴，朱克凡，程澤新

(國防科技大學 電子對抗學院，安徽 合肥 230037)

0 引言

傳統的目標跟蹤中一般將運動物體視為點目標，此時只考慮目標的運動信息，而忽略了目標的外形信息。隨著傳感器技術的提升，新型的傳感器可提供目標的多個量測值，這種在同一時刻能夠得到至少一個量測值的目標稱為擴展目標[1]。擴展目標不僅提供了目標的運動狀態，還提供了運動體的外形信息(大小、形狀和朝向等)。

基于數據關聯的多目標跟蹤算法一直是人們解決多目標跟蹤問題的一個途徑，但是這類算法會帶來“組合爆炸”的問題[2]，計算量龐大是這類算法的一個缺陷。2007年，Mahler在文獻[3]中提出了隨機有限集(random finite set,RFS)框架下的多目標跟蹤方法，該方法將所有的目標狀態和量測集看作隨機有限集，然后通過多目標貝葉斯濾波計算同時估計出目標的個數和狀態。由于算法中存在集值積分，求解十分困難，因此很多近似的濾波方法被提出，概率假設密度(probability hypothesized density,PHD)濾波器便是其中之一，它傳遞的目標概率密度的一階統計近似矩。2009年，Mahler在Giholm和Sallmond給出的非均勻泊松點過程的目標量測模型的基礎上，將PHD濾波技術應用于擴展目標，進行了擴展目標PHD(extended target PHD,ET-PHD)濾波的數學推導，給出了擴展目標PHD濾波器的更新方程[4]。2010年，Granstrom等學者給出了ET-PHD的高斯混合(Gauss mixture,GM)實現形式，即ET-GM-PHD濾波[5]。

量測集的劃分是多擴展目標跟蹤中的一個重要環節，2010年，Granstrom等人提出了一種基于距離閾值的劃分方法，該方法適用于目標距離較遠且量測密度相近的情況[6]；文獻[7]提出了k-means劃分方法，其跟蹤精度好于距離劃分，上述2種方法都是基于距離計算的，對于量測密度差別較大的情況，兩者劃分效果較差。針對這種情況，2015年，文獻[8]提出了一種基于SNN相似度的劃分方法，該方法在目標產生量測密度差異較大的情況下劃分效果較好，但存在計算量偏大的不足。

本文在文獻[8]的基礎上，提出了一種改進的ET-GM-PHD濾波算法，該算法首先通過LOF(local outlier factor)離群檢測進行雜波濾除；然后根據SNN(shared nearest neighbor)相似度對預處理后的量測數據進行劃分，從而達到縮短計算時間，提高跟蹤穩定性的效果。

1ET-GM-PHD濾波算法

1.1 ET-PHD濾波算法

2009年，Mahler在文獻[9]中將PHD濾波器推廣到了擴展目標跟蹤領域，并給出了數學推導：

(1) 預測部分

設k-1時刻的后驗強度vk-1，則ET-PHD預測強度為

βk|k-1(xk|xk-1)]vk-1(xk-1)dxk-1,

(1)

式中:γk(xk)為k時刻新生目標的RFS的強度函數；pS,k(xk-1)為目標在k時刻存活的概率；fk|k-1(xk|xk-1)為k時刻單目標的轉移概率密度；βk|k-1(xk|xk-1)為衍生目標的強度。

(2) 更新部分

設k時刻的預測強度vk|k-1(x)和量測集Zk，且量測個數服從Poisson分布，ET-PHD更新方程為

vk(x)=LZ(x)vk|k-1(x),

(2)

式中：LZ(x)為量測的偽似然函數,

(3)

式中：γ(·)為擴展目標所產生的量測值的均值；PD(·)為目標被檢測概率；p∠Zk為p為量測集合的Zk的一個劃分子集；ωp為劃分p的權值；|W|為子集W內元素的個數；dW為觀測子集W的非負系數；φZ(x)為擴展目標量測的似然函數；λk為單位空間內的雜波個數；ck(Zk)為雜波的分布函數[10]。

1.2 ET-GM-PHD濾波算法

2006年，VO等人在文獻[11]中給出了PHD濾波的高斯混合實現形式，在此基礎上，2010年，Granstrom等人提出了ET-GM-PHD濾波。ET-GM-PHD濾波算法和標準的GM-PHD濾波算法的預測步和更新步一致，本文只給出了標準GM-PHD濾波算法的預測和更新方程。

GM-PHD濾波器滿足以下假設條件:

(1) 每個目標的運動模型和量測模型均為高斯線性的；

(2) 目標的生存概率和檢測概率與目標狀態相互獨立；

(3) 新生目標的RFS強度為高斯混合形式。

基于以上假設，GM-PHD濾波器的預測步可表示為

(4)

更新步可表示為

(5)

1.3 量測劃分問題描述

可見，隨著量測點的增加，劃分數目將急劇增加，計算量將大幅增大，影響跟蹤的實時性，因此尋找準確快速的量測劃分算法，是ET-GM-PHD濾波中的重要環節。針對這個問題，本文提出了一種基于LOF檢測的SNN相似度的量測劃分算法。

2 基于LOF檢測的SNN相似度的聚類算法

本文針對不同擴展目標產生量測密度差異較大的情況，結合局部異常因子離群檢測技術和SNN相似度，提出了一種改進的ET-GM-PHD濾波算法，減小了算法的運行時間，提高跟蹤的穩定性。

2.1 基于LOF的量測集預處理

定義1第k距離dk(p)：對于點p的第k距離dk(p)有如下定義：dk(p)=d(p,o)，d(p,o)表示p，o2點之間的歐式距離，即直線距離，并且dk(p)滿足以下要求：①在集合中至少有不包含p點在內的k個點o，∈C{x≠p}，滿足d(p,o,)≤d(p,o)；②在集合中最多有不包括p在內的k-1個點o，∈C{x≠p}，滿足d(p,o,)

圖1 點p的第5距離Fig.1 The fifth distance of point p

定義2第k距離鄰域Nk(p)：p的第k距離以內的所有點，包括第k距離點。

定義3可達距離reach-distk(p,o)：點o到點p的可達距離定義為reach-distk(p,o)=max{dk(o),d(p,o)}，如圖2所示，o1到p點的第5可達距離為d(p,o1)，o2到p點的第5可達距離為d5(o2)。

圖2 可達距離示意圖Fig.2 Reachable distance schematic diagram

定義4局部可達密度lrdk(p)：表示點p的第k鄰域內的點到p點的平均可達距離的倒數，定義為

(6)

定義5局部異常因子LOFk(p)：表示點p的鄰域Nk(p)的局部可達密度與點p的局部可達密度之比的平均數，定義為

(7)

這個比值越接近于1，說明p和其鄰域點的密度越接近，p可能和鄰域屬于同一簇；如果這個比值小于1，說明p點的密度大于其鄰域點，p為密集點；如果比值大于1，則p點密度小于其鄰域，p點傾向于異常點[12]。

圖3是LOF的實例圖，量測點周圍的圓的半徑與局部異常因子成正比，圓的半徑越大，量測點越偏向于異常值[13]。通過選取合適的LOF閾值，對量測集進行雜波濾除，將局部異常因子大于閾值的量測點視為雜波濾除。LOF閾值可以通過以下方法來選擇：將局部異常因子從大到小排列，并繪制曲線，選取斜率最大部位的點作為LOF閾值即可。經過LOF異常值檢測過濾后，雜波大量被剔除，算法計算復雜度降低25%～35%。

圖3 LOF實例圖Fig.3 LOF instance diagram

2.2 基于SNN相似度的聚類算法

定義1(共享最近鄰相似度)：共享最近鄰相似度的基本思想是：當2個量測點包含一定數量的最鄰近點時，則認為這2個量測點相似。本文中引用文獻[14-15]的相關概念對SNN相似度進行定義：假設量測集X={x1,x2,x3,…,xN},xi,xj∈X，定義xi的k-鄰域為

(8)

式中：Vk(xj)為xj的k-鄰域。

如果xi∈Vk(xj)且xj∈Vk(xi)，則xi和xj的共享最近鄰SNN(i,j)=|Vk(xi)∩Vk(xj)|，|·|表示集合中元素的個數；否則SNN(i,j)=0。

SNN相似度計算的偽代碼如下

初始化k；

令Xun=X；

計算數據集X的距離矩陣；

IfXun≠?，則

{任意選擇一個x∈Xun;

計算x的k-領域Vk(x)={x1,x2,…,xk},

其中x1,x2,…,xk是x的k-領域中的數據點

Fori=1,i≤k

{ifx∈Vk(xi)則

SNN(x,xi)=Vk(x)∩Vk(xi);

else SNN(x,xi)=?;}

Xun=Xun-Vk(x);}

End If

算法中的k值需要人為設定，k值的大小與單個目標產生量測點的個數有關，量測值數目的多少由傳感器精度和擴展目標距離傳感器的距離決定。當傳感器精度較差或者擴展目標距傳感器距離較遠的情況下，單個擴展目標產生的量測點可能少于20個；反之，若傳感器精度較好或者擴展目標距傳感器較近時，單個目標可能會產生大于20個量測值。在控制其他變量的情況下，改變單個目標產生的量測點個數，對劃分結果進行分析，統計k值的合適取值。本文借鑒文獻[8]的統計結果，結論中覆蓋范圍較廣，本文假設單個目標產生的量測值個數均值分別為10個、20個和30個，在表1的統計結論范圍之內。

表1 參數k的設定范圍Table 1 Setting range of parameter k

SNN聚類是將SNN相似度大于一定閾值sl的量測劃分到同一簇中，具體的實現步驟如下：

步驟1:計算經過LOF檢測濾波后的量測兩兩之間的歐式絕對距離，找到每個點的k個最近鄰點。

步驟2:計算每2個量測值之間的SNN相似度，并建立n維SNN相似度矩陣S，n是量測點的個數，矩陣S建立的示意圖如圖4所示。

圖4 建立SNN相似度矩陣Fig.4 Establishing SNN similarity matrix

步驟3:從{0,k-1}之間選取合適的相似度閾值sl，不同的sl得到不同的劃分結果，經過多次的實驗結果分析統計，本文選取sl=k/2。

步驟4:對于相似度矩陣S中≥sl的相似度用1

表示，其余用0表示，得到矩陣Sth，圖5是圖4b)在sl取3時得到的矩陣，將矩陣Sth中同一個的1連通域對應的量測置于同一個簇，連通域的個數即為簇的個數。

圖5 SNN相似度矩陣SthFig.5 SNN similarity matrix Sth

2.3 SNN聚類仿真實驗

如圖6所示，分別是采用k-means劃分算法和本文算法對量測密度差異較大的3個量測集產生的劃分結果，圖6a)中2個目標量測集劃分出現了混淆，這是因為目標兩目標量測密度差異較大，且距離相近；圖6b)是本文算法得到的劃分結果，可以看到，量測集得到了正確的劃分。

3 仿真實驗與分析

在本次仿真實驗中，采用ET-GM-PHD濾波器，進行100次蒙特卡羅仿真，共設置4個量測密度相差較大的跟蹤目標，其中目標1，2的量測密度服從λ=10的Poisson分布，目標3，4的量測密度分別服從λ=20和λ=30的Poisson分布，使用基于距離劃分的算法和基于k-means劃分的算法和本文提出的算法進行比較，驗證本文算法的可行性。

圖6 k-means劃分和SNN相似度劃分效果圖Fig.6 k-partition and SNN similarity partition effect diagram

3.1 仿真場景設置

本次實驗對[1 000,1 000] m×[1 000,1 000] m的二維空間區域進行觀測，如圖8所示，擴展目標的運動區域限定在x軸的-1 000 m至1 000 m，y軸的-1 000 m至1 000 m。擴展目標的運動狀態和始末時間如表2所示。

表2 目標初始狀態和始末時間Table 2 Target initial state and start-end time

(9)

(2 m/s)2I2的高斯白噪聲，I2是二維單位矩陣。

量測方程為

(10)

式中：量測噪聲vk是均值為0，協方差為Rk=(20 m/s)2I2的高斯白噪聲，各目標產生的量測相互獨立。

新生目標強度為

衍生目標強度為

γβ(x)=0.05N(x;ξ,Pβ)，

式中:ξ為本體狀態，Pβ=diag(100,100,400,400)。

高斯混合相關修剪與合并參數：最大高斯分量數J=100，修剪門限T=1e-5，合并門限U=5，勢誤差與狀態誤差的調節因子c=10，OSPA取二階距離p=2。

3.2 仿真結果分析

圖7給出了目標和雜波的態勢圖，目標1,2起始于1 s，消亡于100 s；目標3,4起始于66 s，消亡于100 s，雜波的個數服從λ=10的Poisson分布。

圖8給出了3種算法進行一次濾波遞推的運行時間，從圖8中可以看出，基于距離劃分和基于k-means劃分的ET-GM-PHD濾波耗時明顯高于本文提出的算法。這是因為本文算法在進行量測劃分階段前進行了LOF檢測雜波濾除，并且基于SNN相似度的劃分算法在劃分量測密度差異較大的量測集時具有優勢。

圖7 目標和雜波的態勢圖Fig.7 Situation map of target and clutter

圖9是3種算法對目標個數估計的方針圖，從圖9中可以看到，在k=16,34,50～63,67～72,75,90,96 s時刻，基于距離劃分的ET-GM-PHD濾波算法對目標個數的估計與真實值出現了誤差；k=11,25,47,60,61,63,64,67～71,82,83,92,98,99 s時刻，基于k-means劃分的算法對目標個數出現錯誤估計；本文算法只在k=31,60,61,67～71,86 s時刻出現了目標個數的誤估。這是由于本次實驗仿真中的目標產生量測密度差異較大，當目標接近時，傳統的基于歐式距離的劃分方法會出現量測集的錯分，因而出現目標個數估計的偏差，而本文的算法是基于SNN相似度，考慮的是量測值周圍的信息，因此劃分效果比較理想，提高了濾波器跟蹤的穩定性。

最優子模式指派(optimalsubpatternassignment,OSPA)距離是一種評價隨機有限集框架下多目標跟蹤性能的指標[16]，它是度量2個集合間差異度的誤差距離，其表達式為

(11)

圖10給出了3種算法的OSPA距離，可以看到，代表基于距離劃分算法的藍色虛線和代表k-means劃分算法的紫色點畫線波動次數較多，并且波動時間較長，而代表本文算法的紅色實線僅有4處波動，且波動時間持續較短，說明本文算法的跟蹤穩定性更好。

從上述仿真結果中可見，本文提出的算法相較于傳統的基于距離和k-means劃分的算法具有明顯的優勢，算法的運行時間和跟蹤的穩定性都有一個較好的優化。

圖8 一次濾波遞推耗時對比Fig.8 Comparison of once filter recurrence time consuming

圖9 目標估計個數對比Fig.9 Comparison of the number of target estimates

圖10 OSPA距離對比Fig.10 OSPA distance contrast

4 結束語

在擴展目標產生的量測密度差異較大的情況下，傳統基于距離劃分的ET-GM-PHD濾波算法跟蹤效果不佳。針對這個問題，本文提出了一種基于LOF檢測的SNN相似度的ET-GM-PHD濾波算法，并進行了仿真對比實驗。實驗結果表明，本算法在減少計算時間的同時，跟蹤性能的穩定性也得到了保證，對比于傳統方法具有較大優勢。