基于CFSFDP的箱粒子CPHD擴展目標跟蹤①

王 海,楊小軍

（長安大學 信息工程學院,西安 710064）

傳統多目標跟蹤算法是基于“點目標”假設的[1],如果目標被檢測到,最多只占據傳感器的一個分辨率單元.隨著傳感器分辨率的提高和對目標形狀估計等要求的提出,單個目標占據多個分辨率單元的現象不可避免,跟蹤技術的“點目標”假設難以滿足現實需要,對可能占用多個傳感器單元的擴展目標跟蹤問題成為研究的重點.

在傳統的數據關聯思想下,當目標數增加時,所有目標的量測信息會大幅增長,必須枚舉度量集合的所有可能分區,然后以所有可能的方式分配分區單元來進行對象估計,這勢必會極大地增加運算復雜度.量測集劃分是多擴展目標跟蹤濾波中解決的關鍵問題,在多擴展目標跟蹤中,單目標或單量測單元對應多個量測,傳感器無法建立量測集與目標的對應關系,在Mahler的隨機集框架下考慮擴展目標跟蹤問題[2]成為一種有效的解決方案,針對擴展目標的量測劃分問題,在文獻[3]中提出了距離劃分的方法,該算法利用距離閾值來限定給出對應距離門限的所有劃分結果集,在目標量測很多時計算效率低; 在文獻[4]中提出K-means劃分方法,而該方法需要設定聚類K值,此先驗信息不好設定;在文獻[5]中提出將均值漂移劃分（mean shift）方法用于高斯混合概率假設濾波器（Gaussian Mixture Probability Hypothesis Density,GM-PHD）,有效降低了運算時間;在此基礎上,文獻[6]利用mean shift和圖結構來處理交叉時刻目標數漏估問題,在文獻[7]中提出了快速模糊自適應諧振理論（Adaptive Resonance Theory,ART）劃分方法,并將其應用于箱粒子PHD[8]; 擴展目標CPHD濾波[9]的提出有效提高了PHD在低檢測率高雜波等條件下的目標勢估計精度; 在文獻[10]中提出了基于區間箱粒子形式的擴展目標CPHD濾波,文獻[11]在此基礎上通過給箱粒子加標簽的方式來區分目標航跡.

密度峰值快速聚類算法CFSFDP（Clustering by Fast Search and Find of Density Peaks）[12]于2014年由Alex Rodriguez和Alessandro Laio在Science雜志上提出,通過多種實測數據驗證其準確檢測非球面聚類和快速找到正確聚類數量的良好性能,而后該算法被廣泛應用于各類數據分析中[13-15].

針對擴展目標量測集劃分的問題,本文提出將密度峰值快速聚類算法CFSFDP用于目標和雜波量測的劃分處理,利用箱粒子CPHD濾波器進行擴展目標的預測更新,在降低計算復雜度的前提下,該算法可以有效識別聚類中心和離群點,劃分之后直接剔除雜波量測,進一步降低運算時間,提高了算法的實時性和運算效率,在一定程度上也提高了目標估計精度.

1 密度峰值快速聚類算法

在機器學習中,把未知標記信息的訓練樣本稱為無監督學習,在無監督學習中利用聚類算法來尋找這些數據的內在聯系,根據不同的規則將數據集劃分為若干不相交的子集,達到數據處理的效果.

由于擴展目標處理的是多量測對應單目標的問題,在目標數增加、量測率增大、密集雜波等環境下,過多的量測勢必造成計算負擔,利用有效的劃分方法將屬于同一目標的量測聚到一起,將大大減少計算復雜度,提高運算效率.根據文獻[16],采用泊松分布來表示擴展目標量測,檢測點在目標周圍呈空間分布,而實際情況中的雜波量測又類似服從空間區域內的均勻分布,目標量測和雜波在密度上是可以區分的,故而考慮將基于密度的新型聚類算法CFSFDP用于擴展目標量測集劃分.

CFSFDP聚類算法是基于局部密度和距離的聚類算法.該算法具有能夠發現任意形狀的類簇、邏輯簡單易于理解、超參數少并且可以高效劃分數據的優點,克服了之前聚類算法只能識別和發現基于距離的圓形簇的缺陷,可以得到不同形狀的聚類簇,而且對噪聲不敏感,并高效進行非中心樣本點分配.

CFSFDP聚類算法基于以下兩個假設來識別和查找聚類中心:聚類中心周圍都是密度比其低的點,同時這些點距離該聚類中心的距離相比于其他聚類中心來說是最近的.基于這兩個核心假設來識別聚類中心和離群點.對于每一個數據點,要計算兩個量:點的局部密度和該點到具有更高局部密度的點的距離,而這兩個值都取決于數據點間的距離.

根據文獻[12],CFSFDP簡要算法流程如下:

首先計算每一個數據點的局部密度,計算該點到具有更高局部密度點的距離; 將同時具有較大局部密度和距離的數據點判定為聚類中心點,有較小局部密度和較大距離的數據點判定為離群點; 然后對非聚類中心的數據點進行歸類; 最后利用邊界區域劃分核心點和離群點.

2 基于CFSFDP的擴展箱粒子CPHD算法

2.1 擴展目標動態模型

基于隨機有限集理論,首先對擴展目標狀態方程和量測方程建模,使用兩個隨機有限集xk和Zk來分別表示k時刻的目標狀態和量測信息.

其中,Nx和Nz表示目標數量和量測數量,假設多個擴展目標運動狀態獨立且是線性運動,則目標狀態方程為:

其中,xk表示擴展目標在k時刻的運動狀態,Fk為對應時刻的狀態轉移矩陣,wk為過程噪聲,本文仿真取加性噪聲.

多個擴展目標的量測方程為:

其中,zk為k時刻量測值,Hk為對應時刻的量測矩陣,vk為量測噪聲.過程噪聲和量測噪聲均為均值為零的高斯白噪聲.

2.2 距離劃分

距離劃分基于同一目標產生的多個測量值可能彼此接近,而不同目標產生的多個測量值可能彼此很遠的思想,該方法利用距離閾值測度標準,將擴展目標量測信息進行聚類,利用兩個最值閾值來限定所有可能的分區結果.

k時刻兩個目標源量測之間的馬氏距離為:

其中,R為量測協方差,Δij服從自由度等于量測向量維度的χ2分布.給定概率PG條件下距離閾值用逆分布表示為:

2.3 CFSFDP量測劃分

基于CFSFDP算法的主要思想和核心計算流程,該算法利用局部密度和相對距離識別聚類中心和離群點,由此區分不同密度的聚類簇.

將CFSFDP算法在數據聚類方面的優勢用于擴展目標跟蹤的量測集劃分.與傳統基于距離劃分的量測劃分方法相比,由于CFSFDP聚類算法可以給出目標量測集的一種近似最優劃分結果,而距離劃分則給出所有可能的劃分結果,所以可以有效提高算法實時性;劃分之后根據標識集區分目標聚類簇和離散雜波點,利用此性質可以有效剔除雜波量測.

下面具體給出CFSFDP聚類算法用于擴展目標跟蹤時進行量測集劃分的算法流程.

2.4 基于CFSFDP的擴展箱粒子CPHD算法

由于CFSFDP算法在聚類方面的良好特性,將該算法用于量測集劃分,并加入擴展目標箱粒子CPHD算法[9-11]的框架中,下面給出基于CFSFDP量測劃分的箱粒子擴展CPHD完整算法流程.

2.4.1 初始化生成箱粒子

2.4.2 量測劃分

由于在多擴展目標跟蹤問題中,存在單目標或單量測單元對應多個量測信息的情況,傳感器無法建立量測集與目標的對應關系,所以量測集劃分是多擴展目標跟蹤中需要解決的關鍵問題.

2.4.3 預測

目標的狀態和權值預測為:

其中,ps為存活概率.

利用馬爾科夫轉移矩陣M預測目標數的高階勢分布為:

其中,利用新生勢分布ρbir（n）和存活概率ps得到馬爾科夫轉移矩陣M進一步得到目標的預測勢分布.

2.4.4 更新

勢分布也隨之更新:

具體來說,

2.4.5 數目估計

2.4.6 重采樣

2.4.7 狀態提取

箱粒子點化后利用K-means聚類進行多目標狀態提取,并將聚類狀態均值作為每一時刻的狀態估計值.

3 仿真實驗

3.1 實驗參數設置

實驗仿真平臺使用Win10 64位操作系統,Intel（R）Core（TM）i5-4258UCPU@2.40GHz2.10GHz處理器,運行軟件為Matlab R2012a.仿真實驗場景構建為[-200 m,400 m]×[-800 m,600 m]的二維監控平面,4個擴展目標的初始狀態及生死時刻如表1所示.

表1 目標初始狀態及生死時刻

根據式（3）采用文獻[18]中近勻速狀態方程為:

箱粒子下目標狀態為:

根據式（4）取量測方程為:

3.2 實驗結果分析

在單次蒙特卡洛運行下,圖1為4個擴展目標的運動軌跡和雜波的區間量測圖,每步采樣時刻目標有多個量測.圖2為最大距離劃分區間量測圖,圖3為CFSFDP聚類劃分區間量測圖,根據文獻[9]的理論利用包含函數將聚類后屬于同一個目標的量測點利用區間的箱形式包含起來.圖4為利用CFSFDP去除雜波量測后的目標量測圖,可以看到每個采樣時間內只有目標量測,后續則利用該量測進行濾波.

圖1 目標軌跡及量測圖

圖2 最大距離劃分量測圖

圖3 CFSFDP劃分量測圖

圖4 去除雜波后CFSFDP劃分量測圖

在100次蒙特卡洛運行下,圖5顯示了每個采樣時刻的劃分數,由于距離劃分采用距離閾值門限給出所有可能的劃分結果,在目標數增多時量測劃分數目急劇增加,CFSFDP則利用局部密度和相對距離劃分目標量測和雜波量測,每次劃分只有一種近似最優結果,劃分出目標和雜波并記錄個數.圖6為兩種算法的平均運行時間,可以看出距離劃分目標數增加時,隨著劃分數增加,運算時間增加,CFSFDP算法基于一種劃分結果,運行效率較高.

圖5 劃分數比較

圖6 運行時間比較

本文采用最優子模型分配距離（Optimal SubPattern Assignment,OSPA）[19]對算法的估計精度進行評估.c為目標數目估計懲罰參數,c值越大,在OSPA距離中目標數目估計誤差所占比重越大,p為階數,也稱目標位置懲罰參數,p值越大,在OSPA距離中對目標位置估計誤差越敏感,位置估計誤差所占比重越大.本文實驗中p=2,c=70.

圖7為兩種劃分方法OSPA距離比較,可以看出在目標新生時由于延時的存在,會有較大的OSPA距離,其余時刻基本無差別.從圖8中可以看到在新目標出生時有1 s的延時,是因為提取目標狀態時是基于上一秒的目標信息,延時之后可以進行有效估計.使用兩種量測劃分方法后箱粒子CPHD濾波器都可以準確估計目標數變化和穩定跟蹤.

圖7 OSPA比較

圖8 目標數估計

表2所示為兩種算法在不同雜波泊松平均率下的運行時間對比,由于距離劃分給出所有劃分可能且無法去除雜波,在雜波密度增加時,運行效率下降.在利用CFSFDP算法去除雜波之后,由于后續的預測更新直接處理的是目標量測,泊松雜波率的變化則不再影響運行時間,從表2 可以看出在提高雜波密度情況下對比兩種劃分方法,CFSFDP劃分方法運行效率顯著提升,基于距離劃分性能提升從61.59%到92.22%.故而在高雜波等復雜情況下,先利用CFSFDP算法進行量測預處理,剔除雜波量測后只利用目標量測,可以大大提高運算效率,提高算法實時性.

表2 不同雜波下平均運行時間

圖7所示為剔除雜波之前,泊松雜波率λ=10時兩種算法的OSPA距離比較,兩者相差無幾.與圖7不同,圖9和圖10顯示在剔除雜波之后,泊松雜波率分別為30和50的情況下,兩種算法的OSPA比較,可以看出使用CFSFDP剔除雜波量測之后,直接用目標量測信息進行預測更新,其OSPA距離基本不再受雜波變化影響,而使用距離劃分方法時目標估計精度會隨著雜波率的提高而降低,說明使用CFSFDP剔除雜波量測可以在一定程度上提高目標估計精度.

圖9 雜波率=30時OSPA比較

圖10 雜波率=50時OSPA比較

4 實驗結論

針對多擴展目標跟蹤問題,本文將機器學習中經典的無監督學習密度峰值快速聚類算法CFSFDP用于擴展目標量測集的劃分,利用CFSFDP進行量測預處理,區分目標量測與雜波量測.然后利用箱粒子CPHD濾波算法進行目標跟蹤.仿真實驗表明在量測劃分步驟中采用CFSFDP量測劃分方法代替傳統的距離劃分,CFSFDP在達到相似跟蹤性能的前提下,減少了運算時間,提高了運算效率; 使用CFSFDP方法剔除雜波量測之后,可以充分利用目標量測準確估計目標數變化和運動狀態,雜波的變化不再影響濾波精度,在一定程度上提高了目標估計精度,并具有良好的魯棒性.