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

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

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

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

關(guān)鍵詞:多層采樣;聚類;粒子濾波;重采樣;運(yùn)動(dòng)目標(biāo)跟蹤

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

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

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

doi:10.3969/j.issn.1003-5060.2015.06.009

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

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

1粒子濾波算法原理

粒子濾波的基本原理[15]如圖1所示,是采用隨機(jī)樣本描述概率分布,對采樣粒子的位置和權(quán)重進(jìn)行調(diào)整,對實(shí)際的概率分布進(jìn)行近似,并用樣本均值作為估計(jì)值,克服了擴(kuò)展卡爾曼濾波器的缺點(diǎn)。

圖1　粒子濾波算法原理圖

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

2.1　多層采樣

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

(1)

2.2　K調(diào)和均值聚類

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

(2)

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

2.3　算法整體思路

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

圖2　算法流程圖

2.4　算法基本步驟

2.4.1　初始化

2.4.2　重要性采樣

(2) 評估新的權(quán)重。

(3)

(3) 歸一化權(quán)重。

(4)

2.4.3　輸出

(5)

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

2.4.4　重采樣

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

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

(6)

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

(7)

(8)

2.4.5　多層采樣運(yùn)用

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

(9)

2.4.6　結(jié)果輸出

3仿真結(jié)果及性能分析

3.1　圖像理解和運(yùn)動(dòng)目標(biāo)跟蹤

為了驗(yàn)證算法的正確性,研究在局部擾動(dòng)背景情況下和目標(biāo)形狀發(fā)生變化時(shí),改進(jìn)算法的適應(yīng)能力。

動(dòng)態(tài)背景中的運(yùn)動(dòng)目標(biāo)跟蹤如圖3所示。

圖3　動(dòng)態(tài)背景中的運(yùn)動(dòng)目標(biāo)跟蹤

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

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

3.2　比較實(shí)驗(yàn)

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

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

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

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

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

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

圖6　改進(jìn)的粒子濾波算法跟蹤效果圖

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

4結(jié)束語

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

[參考文獻(xiàn)]

[1]蔣建國,李明,齊美彬.基于TMS320DM6437的運(yùn)動(dòng)目標(biāo)實(shí)時(shí)檢測與跟蹤[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,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]李安平.復(fù)雜環(huán)境下的視頻目標(biāo)跟蹤算法研究[D].上海：上海交通大學(xué),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.

(責(zé)任編輯馬國鋒)