基于KHM的多層采樣粒子濾波算法

李菊1,2,余燁1,戴歡2,李克清2,夏瑜2,曹明偉1

(1.合肥工業(yè)大學 計算機與信息學院,安徽 合肥 230009; 2.常熟理工學院 計算機科學與工程學院,江蘇 常熟215500)

摘要:文章通過多層采樣方式,將樣本空間劃分為多個部分,集中采樣點到使概率密度函數(shù)值大的地方,大大減小了采樣誤差;在重采樣階段嵌入KHM聚類算法,通過將空間特征與權重分布近似的粒子進行聚類,降低總的樣本數(shù),提高了計算效率。樣本經(jīng)聚類處理后,在保持粒子狀態(tài)后驗分布的幾何特征的同時,狀態(tài)空間中的粒子數(shù)明顯降低,計算效率顯著提高。

關鍵詞:多層采樣;聚類;粒子濾波;重采樣;運動目標跟蹤

收稿日期：2014-06-04；修回日期：2014-10-27

基金項目：國家自然科學基金資助項目(61300186);高等學校博士學科點專項科研基金資助項目(20120111110003);江蘇省自然科學基金資助項目(BK20140419);江蘇省高校自然科學研究資助項目(14KJB520001;13KJB510001)；蘇州市重點實驗室資助項目(SZS201407)和常熟市社區(qū)資助項目(CS201404)

作者簡介：李菊(1981-),女,江蘇常熟人,合肥工業(yè)大學博士生,常熟理工學院講師.

doi:10.3969/j.issn.1003-5060.2015.06.009

中圖分類號:TP391. 4文獻標識碼：A

收稿日期：2014-06-04；修回日期：2014-10-15

Stratified sampling particle filter algorithm based on KHM

LI Ju1，2,YU Ye1,DAI Huan2,LI Ke-qing2,XIA Yu2,CAO Ming-wei1

(1.School of Computer and Information, Hefei University of Technology, Hefei 230009, China; 2.School of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China)

Abstract:In this paper, by using the stratified sampling method, the sample space is divided into multiple parts, grouping sampling points to the part of high probability density function value, so the sampling error is greatly reduced. In the resampling phase, the KHM clustering algorithm is embedded, the particles with approximate spatial characteristics and weight distribution are clustered, thus reducing the total number of samples and improving the computing efficiency. After the clustering, the geometrical characteristics of particles state posterior distribution is maintained, while the number of particles in the state space is significantly reduced and the computing efficiency is improved.

Key words:stratified sampling; clustering; particle filter; resampling; moving object tracking

粒子濾波作為一種新的濾波算法,是從20世紀90年代中后期發(fā)展起來的,有效地克服了擴展卡爾曼濾波的缺點。但粒子濾波自身也有一些弱點,會導致樣本貧化現(xiàn)象[1-5],文獻[6]將微粒群算法引入粒子濾波,采用微粒群優(yōu)化方式,使粒子集向后驗概率密度值較大的方向移動,很好地克服了樣本貧化問題;文獻[7]將優(yōu)化組合引入粒子濾波,對被選取粒子和被拋棄粒子進行適當線性組合獲取新的粒子,粒子多樣性被大大增加,粒子濾波的估計精度也有很大的提高。針對計算量較大[8-12]的問題,文獻[13]指出當使用適當?shù)闹夭蓸臃椒〞r粒子濾波的計算復雜度為O(N)(N為粒子數(shù)目)；文獻[14]引入粒子濾波的并行結構算法并進行了在線實時應用。對于一些狀態(tài)空間模型中的線性組成部分,可以通過解析的最優(yōu)濾波方法獲取其狀態(tài)向量的一部分。各種方法都在一定程度上緩解了樣本貧化現(xiàn)象,降低了計算復雜度,但總的來說,并未從根本上解決這個問題。

本文通過多層采樣的方式,把樣本空間劃分為多個部分,集中采樣點到使概率密度函數(shù)值大的地方,采樣誤差大大減小。在重采樣階段嵌入KHM聚類算法,通過將空間特征與權重分布近似的粒子進行聚類,總的樣本數(shù)被降低,提高了計算效率。樣本經(jīng)聚類處理后,在保持狀態(tài)后驗分布的幾何特征的同時,狀態(tài)空間中的粒子數(shù)明顯降低,計算效率顯著提高。本文提出的改進算法可以用到對實時性要求高的場合，通過設定合理的閾值(聚類半徑)也可以自適應調節(jié)粒子數(shù)。

1粒子濾波算法原理

粒子濾波的基本原理[15]如圖1所示,是采用隨機樣本描述概率分布,對采樣粒子的位置和權重進行調整,對實際的概率分布進行近似,并用樣本均值作為估計值,克服了擴展卡爾曼濾波器的缺點。

圖1　粒子濾波算法原理圖

2基于KHM的多層采樣粒子濾波算法

2.1　多層采樣

傳統(tǒng)的粒子濾波算法從一個方向進行采樣,造成粒子一般比較單一。而多層采樣從多方向、多角度進行采樣,采樣誤差被大大降低了。通過多層采樣,把采樣空間劃分為多個子空間,子空間被稱為層,這些不同的分層都具有相同的特性,在每一層中進行采樣,每一層的概率密度函數(shù)為pi(x),那么p(x)用(1)式表示:

(1)

2.2　K調和均值聚類

假設降低采樣密集度,會造成降低目標估計的準確性。所以,本文在粒子重采樣時引入K調和均值聚類,利用權重進行粒子分配,既可以維持高采樣率又可大大減少計算量,KHM算法的關鍵是運用了調和平均值這個概念,P個數(shù)a1,a2,…,aP的調合平均值HA的定義如下:

(2)

該函數(shù)有一特點,假如a1,a2,…,aP中任何一個元素小時,調和均值也會很小。如果元素中沒有很小的值,調和均值就會很大。它就像是一個賦予每個元素一些權重的極小化函數(shù)k調和均值中,對于任意點而言,目標函數(shù)都計算了該點到所有中心的距離。當該點離很多中心點都非常接近時,該算法會將這些多余的中心轉移到那些沒有最近中心點的區(qū)域,這樣獲得的目標函數(shù)的值就會較小。研究中心迭代公式發(fā)現(xiàn)整個數(shù)據(jù)集中的成員都會對每個類的中心迭代產(chǎn)生影響,所以不論初始點取何值,都不會對中心的迭代產(chǎn)生很大影響。

2.3　算法整體思路

通過多層采樣的方式,樣本空間被劃分為多個子空間,采樣點被集中到使概率密度函數(shù)值大的地方,大大降低了采樣誤差,提高了精度。在重采樣階段嵌入KHM聚類算法,利用權重進行粒子分配,提高了粒子的利用率,算法的復雜度大幅度降低。同時因為嵌入了KHM聚類算法,保持了目標的分布特征。算法流程如圖2所示。

圖2　算法流程圖

2.4　算法基本步驟

2.4.1　初始化

2.4.2　重要性采樣

(2) 評估新的權重。

(3)

(3) 歸一化權重。

(4)

2.4.3　輸出

(5)

其中δ(·)是狄克拉函數(shù)。

2.4.4　重采樣

(1) 從數(shù)據(jù)集K中,隨機抽取N個對象作為初始聚類中心K1,K2,K3，…，KN。

(2) 不斷地使用聚類中心進行迭代計算,公式如下:

(6)

(3) 直到評價函數(shù)(7)式開始收斂，即

(7)

(8)

2.4.5　多層采樣運用

對粒子集合進行更新，將多層采樣運用于(8)式，則有：

(9)

2.4.6　結果輸出

3仿真結果及性能分析

3.1　圖像理解和運動目標跟蹤

為了驗證算法的正確性,研究在局部擾動背景情況下和目標形狀發(fā)生變化時,改進算法的適應能力。

動態(tài)背景中的運動目標跟蹤如圖3所示。

圖3　動態(tài)背景中的運動目標跟蹤

分別對圖3所示的局部擾動背景情況下目標姿態(tài)發(fā)生變化的動態(tài)序列做實驗。VC++2010 和Open CV 編程實現(xiàn),實現(xiàn)環(huán)境為1.6 GHz CPU,內存6.0 GB。

本文中選擇了第2、13、16、30、114、132、166、236幀的實驗結果,一方面,環(huán)境光照比較昏暗,光照在隨時間發(fā)生變化,另一方面局部擾動背景是本圖像序列的難點,對圖3跟蹤結果進行研究發(fā)現(xiàn),本文算法在這2種情況下的跟蹤效果較好,體現(xiàn)了較好的穩(wěn)定性。此外，通過觀察圖3發(fā)現(xiàn),運動目標姿態(tài)發(fā)生了很大的變化,該改進算法依然能進行穩(wěn)定的跟蹤。

3.2　比較實驗

為了驗證改進算法的有效性,對hall圖像序列進行實驗,將Mean Shift跟蹤算法、傳統(tǒng)粒子跟蹤算法與改進的算法進行比較,實驗結果主要從魯棒性以及時效性進行分析。通過對粒子濾波中粒子權重的調整,很好地跟蹤到目標。

圖4所示為采用Mean Shift算法的跟蹤效果圖,Mean Shift算法計算量較小,框選已知的區(qū)域,目標跟蹤實時較好,但模板更新能力較差,要想保持好的跟蹤效果,在跟蹤過程中必須保持窗口寬度不變。一旦目標尺度發(fā)生變化,跟蹤就會失敗。

圖5所示為采用粒子濾波算法的跟蹤效果圖,粒子濾波算法用隨機樣本來描述概率分布,通過對采樣粒子的位置和權重進行調整,來近似實際的概率分布,估計值采用了樣本均值,但本身也具有計算量大的弱點,實時性較差。圖6所示為采用本文改進算法的跟蹤效果圖,改進算法的復雜度大幅度降低,適用實時性要求高的場合。

為了比較改進粒子濾波算法和傳統(tǒng)的粒子濾波算法的性能,本文分別對2種算法做了80次獨立實驗,結果見表1所列,改進算法的差錯率更低,執(zhí)行時間更短，大大提高了跟蹤算法的穩(wěn)健性、準確性和實時性。

圖4　Mean Shift跟蹤算法跟蹤效果圖

圖5　粒子濾波跟蹤算法跟蹤效果圖

圖6　改進的粒子濾波算法跟蹤效果圖

項 目改進粒子濾波算法傳統(tǒng)粒子濾波算法粒子數(shù)600600差錯率1.11.4執(zhí)行時間/ms2478

4結束語

本文通過多層采樣的方式,把樣本空間劃分為多個部分,集中采樣點到使概率密度函數(shù)值大的地方,減小了采樣誤差,只有傳統(tǒng)算法的1/2。在重采樣階段嵌入KHM聚類算法,利用權重進行粒子分配,保持了粒子多樣性,提高了粒子的利用率和實際應用中的計算效率。本文提出的改進算法可以用于對精度要求高與實時性要求高的場合。

[參考文獻]

[1]蔣建國,李明,齊美彬.基于TMS320DM6437的運動目標實時檢測與跟蹤[J].合肥工業(yè)大學學報:自然科學版,2011,34(7):1007-1010,1023.

[2]Kwok C,Fox D,Meila M.Adaptive real-time particle filter for robot localization[C]//Proceedings of IEEE International Conference on Robotics and Automation,Vol 2,2003:2836-2841.

[3]Li P,Zhang T.Visual contour tracking based on particle filters[C]//Proceedings of Generative Model Based Vision, Copenhagen, 2002:61-70.

[4]Shan C,Wei Y,Tan T,et al.Real time hand tracking by combining particle filtering and mean shift[C]//Proceedings of Automatic Face and Gesture Recognition, 2004:669-674.

[5]Hue C,Cadre J L,Perez P.A particle filter to track multiple objects[C]//IEEE Workshop on Multi-Object Tracking, 2001:61-68.

[6]Hu W M, Tan T N, Wang L, et al. A survey on visual surveillance of object motion and behaviors[J].IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 2004,34(3): 334-352.

[7]Paragios N, Deriche R. Geodesic active contours and level set for the detection and tracking of moving objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(3):266-280.

[8]李安平.復雜環(huán)境下的視頻目標跟蹤算法研究[D].上海：上海交通大學,2006.

[9]Doucet A,Godsill S J,Andrieu C.On sequential simulationbased methods for Bayesian filtering[J].Statist Comput,2000,10(3):197-208.

[10]Doucet A,Gordon N J,Krishnamurthy V.Particle filters for state estimation of jump Markov linear systems[J].IEEE Trans Signal Processing,2001,49:613-624.

[11]Gordon N J.A hybrid bootstrap filter for target tracking in clutter[J].IEEE Trans Aerosp Electron Syst,1997,33:353-358.

[12]Thrun S,Fox D,Dellaert F,et al.Particle filters for mobile robot localization[M]//Doucet A, de Freitas N,Gordon N.Sequential Monte Carlo Methods in Practice,Eds. New York: Springer-Verlag, 2001.

[13]Kashef B G,Sawchuk A A. A survey of new techniques for image registration and mapping[C]//Proceedings of the SPIE 0432: Applications of Digital Image Processing Ⅵ,1983:222-239.

[14]Anders E N. A constrained extended Kalman Filter for target tracking [C]//Proceedings of the IEEE International Conference of Radar, Philadelphia, USA,2004:123-127.

[15]Cho J U,Jin S H,Pham X D,et al.A real-time object tracking system using a particle filter[C]//International Conference on Intelligent Robots and Systems, 2006:2822-2827.

(責任編輯馬國鋒)