高國棟，林 明

(江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003)

一種簡(jiǎn)化的擬蒙特卡洛-高斯粒子濾波算法*

高國棟*，林 明

(江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003)

提出了一種簡(jiǎn)化的擬蒙特卡洛-高斯粒子濾波(QMC-GPF)算法(SQMC-GPF),以解決將QMC方法應(yīng)用于GPF時(shí)計(jì)算復(fù)雜度高、運(yùn)算量大的問題。該算法中，在連續(xù)的迭代濾波過程開始之前，首先利用QMC采樣產(chǎn)生單位擬高斯分布粒子集，然后用其線性變換產(chǎn)生GPF算法中需要的高斯分布粒子集，省去了重新進(jìn)行QMC采樣步驟。該算法簡(jiǎn)化了新粒子集的產(chǎn)生過程，減少了運(yùn)算量和濾波時(shí)間，增強(qiáng)了算法的實(shí)時(shí)性。將粒子濾波算法(PF)、GPF 算法、QMC-GPF算法和SQMC-GPF算法用于單變量非靜態(tài)增長模型(UNGM)和二維純角度跟蹤模型(BOT)的仿真結(jié)果表明，SQMC-GPF算法的濾波性能與QMC-GPF算法的濾波性能相近，但有更為明顯的速度優(yōu)勢(shì)，具有重要的實(shí)際應(yīng)用價(jià)值。

高斯粒子濾波；擬蒙特卡洛采樣；線性變換；高斯分布

1 引 言

高斯粒子濾波(Gaussian Particle Filter,GPF)[1]是粒子濾波(Particle Filter,PF)[2]的改進(jìn)算法，用高斯分布來近似狀態(tài)的后驗(yàn)分布，用蒙特卡洛(Monte Carlo,MC)[3]方法模擬高斯分布采樣，替代了對(duì)全體粒子狀態(tài)的存儲(chǔ)，避免了重采樣過程，因此減少了運(yùn)算量，提高了算法的濾波效率。為進(jìn)一步提高精度，很多學(xué)者對(duì)GPF算法進(jìn)行了研究和改進(jìn)，其中一種就是改進(jìn)MC采樣方法。文獻(xiàn)[4]對(duì)GPF算法進(jìn)行了分析，并首次提出在GPF算法的框架內(nèi)，運(yùn)用擬蒙特卡洛確定性(Quasi-Monte Carlo,QMC)采樣[5]代替MC偽隨機(jī)采樣的構(gòu)想。文獻(xiàn)[6-8]分別給出QMC-GPF算法流程，并用于目標(biāo)跟蹤，取得了較好的濾波效果，但沒有討論算法的實(shí)時(shí)性問題。文獻(xiàn)[9]為了提升QMC-GPF算法的實(shí)時(shí)性，研究并給出了該算法的FPGA實(shí)現(xiàn)方案，將QMC采樣分為多組并行單元同時(shí)進(jìn)行，采樣完成后再進(jìn)行擬高斯序列的轉(zhuǎn)換，但具有較高的實(shí)現(xiàn)復(fù)雜度和較高硬件資源需求。

QMC方法是MC方法的一個(gè)變種，利用確定的低差異擬隨序列代替“隨機(jī)的”偽隨序列，因而具有更快的誤差收斂速度，且誤差是確定的[10]。QMC采樣致力于給出差異度最低、分布得“最均勻”的確定點(diǎn)列[5]，由此可以推斷，對(duì)于在某一固定空間上的求解問題，一次高質(zhì)量的QMC采樣即具有代表性，無需重復(fù)多次。而在QMC-GPF算法中，連續(xù)迭代濾波都需要重復(fù)調(diào)用QMC方法產(chǎn)生超均勻序列，因此基于以上推斷，本文對(duì)QMC-GPF算法進(jìn)行簡(jiǎn)化，提出SQMC-GPF算法，即在濾波前進(jìn)行QMC采樣，生成高質(zhì)量的超均勻樣本集，然后通過變換得到單位擬高斯分布序列，以其線性變換代替每一時(shí)刻迭代濾波中的QMC分布采樣，從而降低算法的復(fù)雜性和運(yùn)算量，提高運(yùn)算速度。

2 算法原理及分析

2.1 QMC-GPF算法原理及分析

QMC方法用確定性超均勻序列來模擬采樣空間中點(diǎn)的可能性分布，提高了點(diǎn)的利用率[10]。在計(jì)算機(jī)中，MC方法通常用確定的數(shù)學(xué)公式產(chǎn)生偽隨機(jī)數(shù)，用得比較多的是m序列法。QMC方法常采用的低偏差序列[11]包括Sobol序列、Faure序列和Halton序列等。本文選用Halton序列法生成擬隨機(jī)序列，然后再采用經(jīng)典的Box-Muller方法[12]，把超均勻分布的隨機(jī)數(shù)轉(zhuǎn)換為單位擬高斯隨機(jī)數(shù)，其算法步驟如下：

步驟1 運(yùn)用m序列法產(chǎn)生兩個(gè)隨機(jī)正整數(shù)n1和n2。

步驟2 根據(jù)Halton序列[11]產(chǎn)生原理，生成兩列個(gè)數(shù)為N的擬隨機(jī)序列：

(1)

步驟3 用Box-Muller方法產(chǎn)生單位擬高斯隨機(jī)序列：

(2)

或者

(3)

步驟4 根據(jù)高斯分布的線性不變性，將服從單位擬高斯分布的序列轉(zhuǎn)換為均值為m，協(xié)方差為Q的高斯分布序列。首先對(duì)協(xié)方差矩陣Q進(jìn)行Cholesky分解：Q=RTR，然后通過線性變換得到擬高斯序列：

x=Ry+m。

(4)

用QMC方法替換GPF算法中的MC方法就得到QMC-GPF算法[9]。本文以先驗(yàn)概率密度函數(shù)p(xn|xn-1)作為重要性密度函數(shù)π(xn|y0:n)，其算法步驟如下：

步驟1 初始化過程。根據(jù)先驗(yàn)知識(shí)，設(shè)定初始狀態(tài)的均值μ0和協(xié)方差Σ0。

步驟3 量測(cè)更新過程。按式(5)計(jì)算重要性權(quán)值:

(5)

并權(quán)值歸一化：

(6)

步驟4 估計(jì)n時(shí)刻狀態(tài)的均值和協(xié)方差：

(7)

(8)

由QMC-GPF算法步驟可知，每一次的時(shí)間更新過程都需要進(jìn)行一次QMC采樣及其轉(zhuǎn)換操作；而且在多維的情況，為保證精度，QMC方法得到的低差異度序列必須保證其二維投影服從均勻分布，這需要對(duì)原始擬隨機(jī)序列進(jìn)行額外的隨機(jī)化操作，從而將導(dǎo)致QMC-GPF算法的復(fù)雜度與運(yùn)算時(shí)間的增加。

2.2 SQMC-GPF算法

將QMC方法用于GPF算法中，實(shí)則是改變GPF算法中樣本粒子的采樣方式。本文提出的簡(jiǎn)化QMC-GPF算法，用對(duì)基本粒子集的線性變換取代了每次迭代濾波中的高斯分布采樣，只要在濾波開始前用QMC方法準(zhǔn)備好單位擬高斯隨機(jī)序列即可，在濾波過程中無需重新調(diào)用QMC方法。SQMC-GPF算法流程如下：

步驟2 初始化過程。根據(jù)先驗(yàn)知識(shí)，設(shè)定初始狀態(tài)的均值μ0和協(xié)方差Σ0。

步驟4 量測(cè)更新過程。按式(5)和式(6)計(jì)算重要性權(quán)值，并將其歸一化。

步驟5 按式(7)和式(8)，估計(jì)n時(shí)刻狀態(tài)的均值和協(xié)方差。

根據(jù)以上算法步驟，在SQMC-GPF算法中，只需要在濾波開始前進(jìn)行一次QMC采樣和BoxMuller方法生成單位擬高斯序列，然后用其線性變換來代替時(shí)間更新過程中的高斯分布采樣，因此QMC采樣和BoxMuller方法雖然需要大量的運(yùn)算時(shí)間，但只運(yùn)行一次，所以并沒有影響濾波的實(shí)時(shí)性。用線性變換產(chǎn)生一個(gè)高斯隨機(jī)數(shù)，只需要1次乘法、1次加法和很少硬件資源；運(yùn)用Halton序列和BoxMuller方法產(chǎn)生一個(gè)高斯隨機(jī)數(shù)，至少需要2次查找判斷操作、2次異或操作[13]、1次乘法、1次三角函數(shù)運(yùn)算、1次開方運(yùn)算和1次對(duì)數(shù)運(yùn)算等，即使在BoxMuller方法階段運(yùn)用查找表法極大提高運(yùn)算速度，整體的運(yùn)算時(shí)間和所需要的資源也都遠(yuǎn)遠(yuǎn)超過線性變換。所以SQMC-GPF算法能顯著減少算法的運(yùn)算時(shí)間，尤其當(dāng)粒子數(shù)量很大時(shí)，這種優(yōu)勢(shì)更加明顯。

因?yàn)楸疚乃惴ㄊ沁\(yùn)用單次QMC方法代替多次QMC方法，所以單次進(jìn)行的QMC采樣產(chǎn)生的擬隨機(jī)序列的均勻性直接決定估計(jì)的精度和穩(wěn)定性。可以先對(duì)擬隨機(jī)序列進(jìn)行隨機(jī)化操作，以消除不同維之間的相關(guān)性，提高經(jīng)式(2)或式(3)轉(zhuǎn)換而成的擬高斯序列的質(zhì)量。

3 仿真實(shí)驗(yàn)及分析

本文采用文獻(xiàn)[14]和文獻(xiàn)[15]中用到的兩種經(jīng)典非線性模型分別在估計(jì)精度、估計(jì)穩(wěn)定性和計(jì)算時(shí)間3個(gè)方面來驗(yàn)證算法的有效性：變量非靜態(tài)增長模型(UnivariateNonstationaryGrowthModel,UNGM)和二維純方位跟蹤(2DimensionBearing-OnlyTracking,BOT)模型。其中UNGM模型普遍應(yīng)用于經(jīng)濟(jì)領(lǐng)域，其高度的非線性以及其狀態(tài)量分布的雙模態(tài)性，使其經(jīng)常作為驗(yàn)證非線性濾波算法的基準(zhǔn)模型。純方位跟蹤(Bearing-OnlyTracking,BOT)是一類典型的目標(biāo)運(yùn)動(dòng)分析問題，常用于被動(dòng)跟蹤系統(tǒng)中，由于其隱蔽性好，抗干擾性強(qiáng)，歷來是研究的熱點(diǎn)和難點(diǎn)。由于系統(tǒng)本身的弱觀測(cè)性和狀態(tài)空間模型的強(qiáng)非線性，卡爾曼等傳統(tǒng)濾波方法在精度方面往往不能滿足要求。在處理純方位跟蹤問題，粒子濾波算法有很好的表現(xiàn)。

3.1UNGM模型的仿真

UNGM模型狀態(tài)空間方程為

(9)

(10)

(11)

(12)

圖1 PF、GPF、QMC-GPF和SQMC-GPF算法估計(jì)誤差的比較

圖2是估計(jì)穩(wěn)定性的比較，從圖中可以看出，SQMC-GPF算法在粒子數(shù)超過300時(shí)，估計(jì)穩(wěn)定性接近于GPF和QMC-GPF算法，說明其繼承了QMC-GPF算法穩(wěn)定性的優(yōu)點(diǎn)。當(dāng)粒子數(shù)量不超過250時(shí)，SQMC-GPF算法的穩(wěn)定性優(yōu)于其他3種算法，原因是SQMC-GPF算法用確定性采樣代替了偽隨機(jī)采樣，用單次高質(zhì)量的QMC采樣代替了多次“偽隨機(jī)”QMC采樣，減少了不確定性，因而具有更好的穩(wěn)定性。進(jìn)一步比較可發(fā)現(xiàn)，當(dāng)過程噪聲的方差不同時(shí)，SQMC-GPF算法依然保持較好的濾波精度和穩(wěn)定性，說明其有較強(qiáng)的魯棒性。

圖2 PF、GPF、QMC-GPF和SQMC-GPF算法估計(jì)誤差方差的比較

圖3為4種算法單次濾波運(yùn)行時(shí)間的比較，可以明顯看出，QMC-GPF算法所需要的時(shí)間遠(yuǎn)超過其他3種算法，說明其獲得高精度估計(jì)的同時(shí)，損失了實(shí)時(shí)性，而SQMC-GPF算法因?yàn)橛镁€性運(yùn)算代替了擬高斯分布采樣，其所需時(shí)間遠(yuǎn)低于QMC-GPF算法。同時(shí)可以看到，粒子數(shù)量越大，運(yùn)算時(shí)間上的優(yōu)勢(shì)越明顯，驗(yàn)證了算法分析的結(jié)論。

圖3 PF、GPF、QMC-GPF和SQMC-GPF算法單次濾波運(yùn)算時(shí)間的比較

3.2 BOT模型的仿真

BOT模型僅通過方位角度來對(duì)目標(biāo)進(jìn)行跟蹤。在直角坐標(biāo)系下，模型的狀態(tài)方程和觀測(cè)方程分別為

(13)

表1 粒子數(shù)為100時(shí)PF、GPF、QMC-GPF和SQMC-GPF算法的跟蹤性能比較

表2 粒子數(shù)為500時(shí)PF、GPF、QMC-GPF和SQMC-GPF算法的跟蹤性能比較

在表1和表2中，通過對(duì)4種算法在x、y方向的位置和速度估計(jì)精度的比較可以得出,在粒子數(shù)量較少(100)或者在粒子數(shù)量較多(500)的條件下，SQMC-GPF算法的跟蹤精度與QMC-GPF相近，且兩種算法都優(yōu)于GPF和PF算法，且在粒子數(shù)量為較少時(shí)更明顯，這與UNGM模型仿真分析得到的結(jié)論一致。通過對(duì)穩(wěn)定性的比較可以發(fā)現(xiàn)，當(dāng)該模型有500個(gè)粒子時(shí)，SQMC-GPF算法的穩(wěn)定性比QMC-GPF稍差，但在100個(gè)粒子時(shí)，這種差距變得很小，這同樣說明SQMC-GPF算法在粒子數(shù)量少時(shí)具有較好的穩(wěn)定性。最后，濾波時(shí)間的比較再次證明了SQMC-GPF算法的快速性。

圖4是其中一次目標(biāo)跟蹤結(jié)果，圖中PF跟蹤算法出現(xiàn)了發(fā)散，SQMC-GPF和QMC-GPF算法均能較好地實(shí)現(xiàn)目標(biāo)跟蹤。

圖4 PF、GPF、QMC-GPF和SQMC-GPF算法的跟蹤結(jié)果

綜合上述仿真實(shí)驗(yàn)可知，在不同的粒子數(shù)量下，SQMC-GPF算法估計(jì)精度和穩(wěn)定性都接近于QMC-GPF算法，且在絕大多數(shù)情況下都優(yōu)于GPF和PF算法；當(dāng)粒子數(shù)量較少時(shí)，SQMC-GPF算法具有相對(duì)于其他3種算法較好的估計(jì)穩(wěn)定性;同時(shí),SQMC-GPF算法在運(yùn)算時(shí)間方面都優(yōu)于其他3種算法，具有較強(qiáng)的實(shí)時(shí)性。

4 結(jié)束語

本文分析了QMC-GPF算法的優(yōu)缺點(diǎn)，提出了SQMC-GPF算法，以線性變換代替原算法中的高斯分布采樣，即運(yùn)用一次QMC方法代替多次QMC方法，大大提高了運(yùn)算速度。仿真實(shí)驗(yàn)表明，SQMC-GPF算法在提高速度的同時(shí)，估計(jì)性能接近于QMC-GPF算法，使得QMC方法與GPF算法結(jié)合產(chǎn)生的實(shí)時(shí)性問題得以解決，具有重要的實(shí)際應(yīng)用價(jià)值。本文的下一步工作就是研究SQMC-GPF算法的硬件實(shí)現(xiàn)結(jié)構(gòu)，在實(shí)際應(yīng)用背景下驗(yàn)證該算法的可靠性。

[1] KOTECHA J H,DJURIC P M. Gaussian particle filtering[J].IEEE Transaction on Signal Processing,2003,51(10):2592-2601.

[2] 王法勝,魯明羽,趙清杰,等. 粒子濾波算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(8):1679-1694. WANG Fasheng,LU Mingyu,ZHAO Qingjie,et al. Particle filtering algorithm[J].Chinese Journal of Computer,2014,37(8):1679-1694.(in Chinese)

[3] CHEN R. Sequential Monte Carlo methods for dynamic systems[J].Journal of the American Statistical Association,2014,93(443):1032-1044.

[4] WU Y,HU X,HU X,et al. Comments on Gaussian particle filtering[J].IEEE Transactions on Signal Processing,2005,53(8):3350-3351.

[5] LEMIEUX C. Monte Carlo and quasi-Monte Carlo sampling[J].Berlin:Springer,2009.

[6] 陳曦. 基于粒子濾波的檢測(cè)前跟蹤算法研究[D].西安：西安電子科技大學(xué),2009. CHEN Xi. Sdudies on track before deteck algorithm based on particle filter[D].Xi′an:Xidian University,2009.(in Chinese)

[7] 武斌,李鵬. 一種新的紅外弱小目標(biāo)檢測(cè)前跟蹤算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,38(3):107-113. WU Bing,LI Peng. Novel track-before-detect algorithm for small infrared target[J].Journal of Xidian University,2011,38(3):107-113.(in Chinese)

[8] 張俊根,趙培宇. 基于QMC-GPF的被動(dòng)測(cè)角目標(biāo)跟蹤算法[J].控制工程期刊(中英文版),2013,3(2):52-58. ZHANG Jungen,ZHAO Peiyu. Quasi-Monte Carlo Gaussian particle filter based passive bearing-only target tracking[J].Scientific Journal of Control Engineering,2013,3(2):52-58.(in Chinese)

[9] 李倩,姬紅兵,郭輝. 擬蒙特卡洛-高斯粒子濾波算法研究及其硬件實(shí)現(xiàn)[J].電子與信息學(xué)報(bào),2010,32(7):1737-1741. LI Qian,JI Hongbin,GUO Hui. Research and hardware implementation of quasi-Monte Carlo Gaussian particle filter[J].Journal of Electronics & Information Technology，2010,32(7):1737-1741.(in Chinese)

[10] RUSSEL E,CAFLISCH. Monte Carlo and quasi-Monte Carlo methods[M]// Functionals of Multidimensional Diffusions with Applications to Finance.Berlin:Springer International Publishing,2013:343-358.

[11] 朱平. 擬蒙特卡洛方法的若干研究與應(yīng)用[D].杭州：浙江大學(xué),2010. ZHU ping. Thestudies and application of quasi Monte Carlo methods[D].Hangzhou:Zhejiang University,2010.(in Chinese)

[12] 陳雷成,王華華,江彥鯉,等. 一種低復(fù)雜度信道模擬器的設(shè)計(jì)[J].電訊技術(shù),2014,54(9):1275-1279. CHEN Leicheng,WANG Huahua,JIANG Yanli,et al. Design of a low complexity channel simulator[J].Telecommunication Engineering,2014,54(9):1275-1279.(in Chinese)

[13] DALAL I L,STEFAN D,HARWAYNE-GIDANSKY J. Low discrepancy sequences for Monte Carlo simulations on reconfigurable platforms[C]//International Conference on Application-Specific Systems,Architectures and Processors(ASAP).Leuven,Belgium:IEEE,2008:108-113.

[14] 李海君,趙國榮. 基于快速高斯變換的輔助邊緣粒子濾波算法[J].數(shù)據(jù)采集與處理,2014,29(6):998-1002. LI Haijun,ZHAO Guorong. Auxiliary marginal particle filter algorithm based on fast Gaussian transformation[J],Journal of Data Acquisition Processing,2014,29(6):998-1002.(in Chinese)

[15] 李善姬,禹愛蘭. 一種改進(jìn)重采樣的粒子濾波算法[J].電訊技術(shù),2011,51(9):35-38. LI Shanji,YU Ailan. An improved resampling particle filtering algorithm[J].Telecommunication Engineering,2011,51(9):35-38.(in Chinese)

A Simplified Quasi-Monte Carlo Based Gaussian Particle Filter

GAO Guodong,LIN Ming

(School of Electronics Information,Jiangsu University of Science and Technology,Zhenjiang 212003,China)

A simplified Quasi-Monte Carlo Gaussian particle filtering(QMC-GPF)(SQMC-GPF) algorithm is presented to solve the problems of high complexity and large amount of computation that QMC method is faced with when it is applied to GPF. In this algorithm,a basic set of particles which obey unit quasi-Gaussian distribution are pregenerated with the method of QMC before the successive iterative filering process,and then they are converted to the particles needed during iterative filering by means of linear transformation,without the QMC method called again. This algorithm simplifies the generation of new particles,reduces the amount of computation and filtering time,and improves the real-time performance of the QMC-GPF algorithm. Finally,the PF,GPF,QMC-GPF and SQMC-GPF algorithms are simulated with univariate nonstationary growth model(UNGM) and bearing-only tracking model(BOT).Results show that,SQMC-GPF algorithm has much higher filtering speed than QMC-GPF algorithmon on the premise of the same filtering performance,which proves that the former has important practical application value.Key words：Gaussian particle filter;quasi-Monte Carlo sampling;linear transformation;Gaussian distribution

10.3969/j.issn.1001-893x.2017.04.015

高國棟，林明.一種簡(jiǎn)化的擬蒙特卡洛-高斯粒子濾波算法[J].電訊技術(shù)，2017,57(4):457-462.[GAO Guodong,LIN Ming.A simplified quasi-Monte Carlo based Gaussian particle filter[J].Telecommunication Engineering,2017,57(4):457-462.]

2016-07-08；

2016-09-28 Received date:2016-07-08；Revised date：2016-09-28

國家自然科學(xué)基金資助項(xiàng)目(61401179)

TN713

A

1001-893X(2017)04-0457-06

高國棟(1990—)，男，江蘇淮安人，碩士研究生，主要研究方向?yàn)樾盘?hào)與信息處理；

Email:ggdffic@163.com

林 明(1960—)，男，遼寧大連人，教授、研究生導(dǎo)師，主要研究方向?yàn)槔走_(dá)信號(hào)處理、船舶電子。

*通信作者：ggdffic@163.com Corresponding author：ggdffic@163.com