基于分類采樣的目標(biāo)跟蹤方法

周飛菲

(鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院，河南 鄭州 451191)

0 引 言

粒子濾波在(particle filter, PF)目標(biāo)跟蹤[1]、導(dǎo)航定位[2]等領(lǐng)域具有廣泛應(yīng)用，其中，重采樣技術(shù)是克服粒子權(quán)值退化的重要手段，目前比較經(jīng)典的有有殘差重采樣(residual resampling, RR)[2]、多項(xiàng)式重采樣(multinomial resampling, MR)[3]和系統(tǒng)重采樣(systematic resampling, SR)[4]。雖實(shí)現(xiàn)的手段不同，但采樣的思想相同，都是通過丟棄小權(quán)值粒子，對(duì)大權(quán)值粒子重新分配權(quán)值獲取新的粒子集合。在一定程度上緩解了樣本退化的問題，但隨著時(shí)間的延長(zhǎng)，大權(quán)值粒子多次被復(fù)制，粒子集的多樣性喪失。經(jīng)過若干次迭代以后，用于估計(jì)的粒子集合只是部分有限狀態(tài)的子代粒子，嚴(yán)重喪失了狀態(tài)的遍歷性能，特別是在系統(tǒng)狀態(tài)分布具有嚴(yán)重拖尾現(xiàn)象的時(shí)候，迭代時(shí)間越長(zhǎng)、精度越差[5]。隨后出現(xiàn)了兩類改進(jìn)方法：一類是基于“優(yōu)選建議分布函數(shù)”，通過濾波技術(shù)將最新的觀測(cè)信息融入到建議分布函數(shù)中，增強(qiáng)當(dāng)前時(shí)刻觀測(cè)信息對(duì)粒子多樣性的修正作用，例如，常用的擴(kuò)展卡爾曼濾波(EKF)[6]、無跡卡爾曼濾波(UKF)[7]以及容積卡爾曼濾波(CKF)[8]等，通過該類濾波技術(shù)實(shí)現(xiàn)建議分布函數(shù)的實(shí)時(shí)估計(jì)。雖然這類基于建議分布函優(yōu)化的方法一定程度上增強(qiáng)了最新觀測(cè)信息對(duì)粒子多樣性的保持作用，但是改善的精度嚴(yán)重依賴觀測(cè)信息的估計(jì)方法，沒有改善重采樣的實(shí)現(xiàn)手段，無法避免權(quán)值衰退的產(chǎn)生。第二類是基于“優(yōu)化重采樣策略”的思想。通過智能尋優(yōu)的方法改變重采樣手段。Grisetti利用網(wǎng)格分割的思想權(quán)重的重新分配，提出了確定性重采樣方法[9]，由于網(wǎng)格整體風(fēng)格的計(jì)算量過大，限制了該技術(shù)的進(jìn)一步發(fā)展。Cheng通過設(shè)置權(quán)重閾值，將權(quán)值粒子集分為兩個(gè)采樣集合，保留大權(quán)值粒子，并結(jié)合小權(quán)值進(jìn)行分層采樣[10]，每一次采樣后都會(huì)摒棄大量的小權(quán)值粒子，降低了多樣性。在此基礎(chǔ)上，Zhang提出采用遺傳算法對(duì)剩余粒子進(jìn)行優(yōu)化分析，針對(duì)大小權(quán)值粒子采取不同的遺傳變異修正處理方式實(shí)現(xiàn)了遺傳算法重采樣方法(genetic algorithm resampling，GAR)[11]，提升了粒子濾波在機(jī)動(dòng)目標(biāo)跟蹤中的濾波精度，但是每一次重采樣都要對(duì)粒子集合的全體粒子操作，增加了算法本身的計(jì)算時(shí)間。

針對(duì)權(quán)值退化及樣本貧化問題，本文提出了一種分類進(jìn)化的重采樣(classification evolution resampling，CER)粒子濾波方法。首先，通過重采樣閾值的判斷，對(duì)滿足重采樣條件的建議分布函數(shù)進(jìn)行濾波估計(jì)，保證最新觀測(cè)信息對(duì)粒子的修正作用；接著，對(duì)重采樣粒子集合進(jìn)行種群劃分，依據(jù)權(quán)值大小聚類為小權(quán)值種群、保留種群和大權(quán)值裂變種群三類。在重采樣過程中，首先對(duì)大權(quán)值粒子進(jìn)行裂變，然后采用差分進(jìn)化方法同小權(quán)值種群進(jìn)行優(yōu)化，通過突變、交叉、選擇產(chǎn)生新粒子種群，避免了對(duì)歷史小權(quán)值信息的丟棄。最后，針對(duì)非線性系統(tǒng)模型進(jìn)行了詳細(xì)的仿真分析和指標(biāo)對(duì)比說明。

1 分類進(jìn)化重采樣原理分析

1.1 基本粒子濾波

非線性系統(tǒng)方程可以表示為[12]

(1)

其中，xt∈Rn,yt∈Rm為狀態(tài)向量和觀測(cè)向量，f(·)和h(·)是已知的非線性傳遞函數(shù)，ωt和vt是過程和量測(cè)噪聲，為不相關(guān)的零均值高斯白噪聲過程，協(xié)方差為Q、R，濾波的目的是在給定觀測(cè)信息p(xt|y1:t)的情況下計(jì)算狀態(tài)的后驗(yàn)概率密度。隨著觀測(cè)信息的不斷更新，可以將系統(tǒng)狀態(tài)的后驗(yàn)概率密度(PDF)表示為

(2)

條件概率密度p(yt|y1:t-1)為

(3)

PF基于蒙特卡洛仿真的思想采用權(quán)重粒子加和的方式近似計(jì)算積分，表示為

(4)

權(quán)重賦值：計(jì)算采樣粒子的權(quán)值大小

(5)

重采樣：隨著迭代時(shí)間的增加，粒子權(quán)重的方差趨于零，出現(xiàn)“粒子退化”問題，需要進(jìn)行重采樣。文獻(xiàn)[14]定義了有效粒子數(shù)Neff，當(dāng)Neff低于閾值情況進(jìn)行重采樣步驟

(6)

1.2 分類進(jìn)化重采樣實(shí)現(xiàn)

為了在采樣粒子中融入最新觀測(cè)信息的修正作用，采用UKF方法對(duì)建議分布函數(shù)進(jìn)行濾波優(yōu)化。與傳統(tǒng)方法不同的是，不是對(duì)全部的采樣粒子都進(jìn)行UKF濾波，而是在判斷需要進(jìn)行重采樣步驟以后，在進(jìn)行重采樣的同時(shí)，進(jìn)行建議分布函數(shù)的濾波估計(jì)優(yōu)化。判斷閾值的設(shè)置為Neff

1.3 粒子分類

為避免對(duì)所有粒子進(jìn)行重采樣，考慮對(duì)粒子集合進(jìn)行分塊處理。根據(jù)聚類的思想，基于粒子權(quán)值大小將整個(gè)粒子集合劃分為小權(quán)值種群、保留種群和大權(quán)值裂變種群三類，其中初始權(quán)值閾值設(shè)置為ωthrmax和ωthrmin，其中粒子權(quán)值低于ωthrmin的粒子被劃分為小權(quán)值種群需要進(jìn)行重采樣，權(quán)值大于ωthrmax的粒子被劃分為大權(quán)值裂變種群，需要和小權(quán)值種群進(jìn)行重組，獲取新一代粒子。權(quán)值介于兩者之間的定義為保留種群，在新一代粒子更新中保持不變。具體的分類原理如式(7)。圖1展示了具體的分類過程。

(7)

圖1 權(quán)值粒子集種群分類框圖

從圖1中可以清晰地看出三類粒子的具體劃分方法。其中，第一類粒子的個(gè)數(shù)為N-P-K，第二類粒子的個(gè)數(shù)為K，第三類大權(quán)值粒子的裂變個(gè)數(shù)主要取決于粒子的權(quán)值，其具體的計(jì)算方法為

(8)

分解后的粒子權(quán)值計(jì)算為

(9)

分解后的粒子滿足式(10)特性

(10)

(11)

分解后的粒子分布為高斯分布

(12)

(13)

1.4 差分進(jìn)化重采樣

(14)

(15)

(16)

(17)

(18)

新的種群通過突變、交叉和選擇進(jìn)行優(yōu)化，直到達(dá)到各個(gè)種群的最大數(shù)目，獲取最優(yōu)的擬合值以后，迭代終止。

2 計(jì)算機(jī)仿真分析

為分析所提方法的性能，將本文提出的分類進(jìn)化重采樣算法(CER)與RR、MR、SR以及文獻(xiàn)[11]提出的GAR方法進(jìn)行了對(duì)比分析。仿真中采用式(19)所示的單變量增長(zhǎng)模型進(jìn)行仿真分析，該模型具有較強(qiáng)的非線性且噪聲滿足高斯噪聲特性[15]。

(19)

2.1 評(píng)價(jià)指標(biāo)

為定量評(píng)價(jià)不同采樣方法的性能指標(biāo)，給出了均方根誤差(RMSE)以及RMSE的均值MeRMSE和方差VarRMSE，具體計(jì)算表達(dá)式為

(20)

(21)

2.2 仿真結(jié)果分析

實(shí)驗(yàn)一：粒子樣本空間分布多樣性分析。

通常用有效粒子數(shù)Neff度量粒子濾波算法的退化程度,其定義如式(6)所示。其中，Neff的大小與退化程度成反比關(guān)系。在采樣粒子數(shù)N=100的情況下，分別對(duì)幾種重采樣方法進(jìn)行了100次的獨(dú)立運(yùn)行，并取兩種算法的Neff平均值來驗(yàn)證GFA-PF算法確實(shí)能改善粒子濾波算法中的粒子退化問題。有效粒子數(shù)Neff實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同迭代次數(shù)的由效粒子數(shù)

從表1中可以看出，本文方法的平均有效粒子數(shù)保持了最大值，因此，本文方法能夠很地解決粒子退化問題。經(jīng)過重采樣之后，PF算法雖然可以在一定程度上避免粒子退化問題,但是卻帶來了粒子貧化問題。為了度量本文方法在迭代100次以后的粒子樣本分布情況，圖2中繪制了由圖2可以看出，圖2(a)粒子分布均勻，多樣性豐富，而圖2(b)中的粒子出現(xiàn)了明顯的聚集現(xiàn)象，單一性強(qiáng)，驗(yàn)證了GFA-PF算法在解決粒子退化問題的同時(shí)還能保證粒子的多樣性,解決粒子貧化問題.

實(shí)驗(yàn)二：固定仿真周期T=50，分析不同采樣粒子數(shù)情況下的估計(jì)效果。

為分析不同采樣方法的精確性，首先對(duì)固定仿真周期、不同采樣粒子數(shù)情況下的估計(jì)精度進(jìn)行了分析。圖2、圖3和圖4給出了在粒子采樣數(shù)分別為300、100和20情況下的狀態(tài)估計(jì)結(jié)果，EE曲線以及RMSE曲線?？梢钥闯?，隨著粒子數(shù)的減少，傳統(tǒng)的重采樣方法估計(jì)精度較低，主要因?yàn)閭鹘y(tǒng)方法只是考慮了對(duì)粒子的權(quán)值進(jìn)行重新優(yōu)化分配，沒有考慮觀測(cè)信息的修正作用，同時(shí)舍棄了大量的小權(quán)值粒子導(dǎo)致。從圖中可以明顯看出，傳統(tǒng)的重采樣方法中RR方法的精度最低，SR的采樣精度最好，原因是因?yàn)镽R僅考慮了有區(qū)別粒子的采樣，隨著粒子遍歷性能的降低，父代粒子越來越少，導(dǎo)致估計(jì)精度越來越差。在粒子數(shù)N=300的情況下，GAR和本文方法都保持了較好的跟蹤精度，主要原因是GAR對(duì)小權(quán)值粒子進(jìn)行了優(yōu)化遺傳重組，有效增加了粒子的多樣性。但是隨著粒子數(shù)的減少，GAR方法的精度明顯降低，主要缺少最新觀測(cè)信息的修正作用，產(chǎn)生了估計(jì)的累積誤差效應(yīng)。在粒子數(shù)N=20的情況下，本文方法的估計(jì)精度明顯優(yōu)于其他采樣方法，并且其跟蹤精度和粒子數(shù)N=100基本相近。根據(jù)本文方法的這一特性，可以明顯改善粒子濾波的計(jì)算復(fù)雜度和濾波精度間的矛盾，提升高精度應(yīng)用的實(shí)時(shí)性。

圖2 N=300時(shí)估計(jì)精度分析

圖3 N=100時(shí)估計(jì)精度分析

圖4 N=20估計(jì)精度分析

實(shí)驗(yàn)三：固定采樣粒子個(gè)數(shù)N=100，分析不同仿真周期情況下的估計(jì)效果。

為分析不同采樣方法的穩(wěn)定性，針對(duì)給定采樣粒子數(shù)、不同仿真周期情況下的估計(jì)精度進(jìn)行了仿真分析。仿真中，設(shè)置采樣粒子數(shù)N=100，仿真周期T分別為50 s、100 s和500 s，并給出了100步迭代的RMSE均值MeRMSE和方差VarRMSE，具體結(jié)果如表1和表2所示。

表1 N=100時(shí)的MeRMSE

表2 N=100時(shí)的VarRMSE

從表中可以看出，隨著仿真周期的增加，五種方法的估計(jì)精度都在降低，其中，RR方法的降低幅度較大，本文方法和GAR方法表現(xiàn)的相對(duì)平穩(wěn)，在50s到500s的變化過程中，GAR方法的MeRMSE增加了0.5952，而本文方法增加了0.4008。由表2可以看出，GAR的VarRMSE波動(dòng)范圍為0.0977，而本文方法的波動(dòng)范圍為0.065。因此，本文方法不僅具有更好的估計(jì)精度，同時(shí)具有較好的穩(wěn)定性。

實(shí)驗(yàn)四：計(jì)算復(fù)雜度分析。

計(jì)算的復(fù)雜度主要取決于采樣、重采樣和權(quán)值計(jì)算三個(gè)階段。在DE中迭代數(shù)目k和粒子數(shù)目M決定著本文方法的復(fù)雜度，由于進(jìn)行了粒子分類處理，需要處理的粒子不會(huì)超過全部粒子的2/3。該部分基于Matlab2015軟件，在Intel Core5Duo@4GHzPC上進(jìn)行了計(jì)算復(fù)雜度分析。仿真中仍然采用式(19)給定的模型，在相同參數(shù)設(shè)置情況下進(jìn)行150次迭代估計(jì)。對(duì)不同采樣粒子數(shù)情況下的計(jì)算復(fù)雜度進(jìn)行了對(duì)比分析，結(jié)果如表3所示。可以看出，隨著粒子數(shù)的增多，五種重采樣方法的時(shí)間都呈遞增趨勢(shì)，其中，MR、GAR和CER的采樣時(shí)間接近，說明本文建議分布函數(shù)的優(yōu)化和粒子分類進(jìn)化重采樣步驟實(shí)現(xiàn)了計(jì)算復(fù)雜度的這種，在相同采樣粒子個(gè)數(shù)情況下，計(jì)算復(fù)雜性并沒有增加。

表3 計(jì)算時(shí)間消耗比較

3 結(jié) 語

針對(duì)粒子濾波方法存在的“粒子退化”及“樣本貧化”問題，本文針對(duì)“重采樣”的具體實(shí)現(xiàn)方法進(jìn)行了研究，并提出了一種權(quán)值分類進(jìn)化重采樣方法。對(duì)傳統(tǒng)重要性概率密度函數(shù)的優(yōu)化思想進(jìn)行了閾值分割，只對(duì)退化情況下的建議分布函數(shù)進(jìn)行優(yōu)化，既有效增強(qiáng)了最新觀測(cè)信息對(duì)粒子的修正作用，也較好地降低了粒子狀態(tài)優(yōu)化的時(shí)間消耗。同時(shí)，在重采樣階段依據(jù)粒子的權(quán)值大小將采樣粒子集分別聚類為小權(quán)值種群、保留種群和大權(quán)值裂變種群。對(duì)大權(quán)值粒子裂變后的粒子和小權(quán)值粒子進(jìn)行差分進(jìn)化，通過突變、交叉、選擇產(chǎn)生新粒子種群，避免了對(duì)歷史小權(quán)值信息的丟棄。仿真分析結(jié)果表明，本文方法有效提升了采樣粒子空間分布的多樣性，在合理計(jì)算復(fù)雜性的基礎(chǔ)上，有效提升了算法的粒子多樣性，在不增加運(yùn)算負(fù)擔(dān)的前提下提升了濾波的精度，比現(xiàn)有的重采樣方法具有更好的精度和穩(wěn)定性。但是本文在分析中對(duì)粒子的采樣數(shù)是固定的，后續(xù)的研究中，需要探索研究采樣粒子數(shù)同不同濾波精度需求之間的關(guān)系，構(gòu)建重采樣粒子數(shù)目的自適應(yīng)規(guī)則，實(shí)現(xiàn)完整的智能重采樣和自適應(yīng)濾波性能，提升在模型和噪聲統(tǒng)計(jì)特性失配情況下的濾波精度。