許偉村， 趙清杰， 王宇霞， 趙留軍

(北京理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，北京 100081)

?

基于重要性排序蒙特卡洛粒子濾波的物體跟蹤算法

許偉村， 趙清杰， 王宇霞， 趙留軍

(北京理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，北京 100081)

研究復(fù)雜背景下的物體跟蹤方法. 提出一種用于物體跟蹤的重要性排序馬氏鏈蒙特卡洛粒子濾波算法. 算法利用少量加權(quán)初始粒子得到后驗(yàn)概率分布的初步估計(jì)，并通過(guò)重要性排序馬氏鏈蒙特卡洛采樣技術(shù)從該初步估計(jì)抽取新的粒子，以構(gòu)建對(duì)應(yīng)不同模態(tài)的多條獨(dú)立馬氏鏈，從而充分逼近真實(shí)后驗(yàn)概率分布的多模態(tài). 所提出的算法自適應(yīng)地根據(jù)當(dāng)前模態(tài)分布構(gòu)建多條獨(dú)立馬氏鏈，因此能夠在多模態(tài)的復(fù)雜場(chǎng)景下準(zhǔn)確估計(jì)目標(biāo)狀態(tài)的后驗(yàn)概率分布；同時(shí)，在構(gòu)建馬氏鏈的過(guò)程中，算法采用重要性排序策略確定歷史樣本被選為狀態(tài)轉(zhuǎn)移核的似然度，提高了小權(quán)重樣本被選中的可能性，降低了在馬氏鏈構(gòu)建過(guò)程中陷入局部最優(yōu)的概率. 仿真實(shí)驗(yàn)以及真實(shí)視頻上所進(jìn)行的實(shí)驗(yàn)顯示，所提出的方法能夠?qū)崿F(xiàn)準(zhǔn)確穩(wěn)定的物體跟蹤，且效果優(yōu)于標(biāo)準(zhǔn)粒子濾波算法以及馬氏鏈蒙特卡洛粒子濾波算法.

目標(biāo)跟蹤；重要性排序；馬氏鏈蒙特卡洛；粒子濾波；多模態(tài)

物體跟蹤可應(yīng)用的范圍非常廣泛，如室內(nèi)外智能監(jiān)控系統(tǒng)中對(duì)人或車(chē)輛的跟蹤[1-2]，比賽中對(duì)運(yùn)動(dòng)員的跟蹤[3]等. 貝葉斯連續(xù)估計(jì)是物體跟蹤領(lǐng)域使用最為廣泛的技術(shù)手段之一，較為常用的有卡爾曼濾波算法和粒子濾波算法，其中粒子濾波算法[4]由于可以簡(jiǎn)單靈活地處理非線性非高斯問(wèn)題被廣泛使用[5-8]，然而，傳統(tǒng)粒子濾波算法的采樣效果與產(chǎn)生樣本的提議分布以及采樣密度相關(guān). 當(dāng)提議分布與真正的后驗(yàn)概率分布重疊較小將導(dǎo)致較大的狀態(tài)估計(jì)誤差，甚至造成跟蹤失敗. 擴(kuò)大樣本空間同時(shí)提高采樣密度可保證狀態(tài)估計(jì)精度，但過(guò)高的粒子數(shù)會(huì)導(dǎo)致計(jì)算負(fù)擔(dān)過(guò)重.

為解決這一問(wèn)題，部分研究者通過(guò)產(chǎn)生更優(yōu)的提議分布提高采樣效率，提出了高斯粒子濾波(Gaussian particle filtering， GPF)[8]，Unsented粒子濾波(Unsented particle filtering， UPF)[10]等算法，其中UPF算法通過(guò)Unscented卡爾曼濾波器產(chǎn)生近似后驗(yàn)高斯分布的提議分布，提高了粒子濾波在非線性非高斯系統(tǒng)中的跟蹤性能，然而UPF等算法采用的提議分布往往是基于先驗(yàn)統(tǒng)計(jì)信息產(chǎn)生的，當(dāng)目標(biāo)運(yùn)動(dòng)狀態(tài)與先驗(yàn)統(tǒng)計(jì)不符時(shí)，仍有可能產(chǎn)生與真實(shí)后驗(yàn)分布重疊較小的提議分布，從而導(dǎo)致跟蹤漂移甚至失敗. 另外一部分研究者則傾向于在采用較優(yōu)的提議分布的基礎(chǔ)上，進(jìn)一步通過(guò)使初次采集的粒子向后驗(yàn)概率峰值區(qū)域移動(dòng)逐步擬合后驗(yàn)分布達(dá)到準(zhǔn)確跟蹤的目的，基于這種思路的代表性算法之一是Gilks等[11]提出的馬爾科夫鏈蒙特卡洛采樣粒子濾波(Markov Chain Monte Carlo particle filtering， MCMCPF)算法，這種方法通過(guò)MCMC移動(dòng)使粒子向高置信度區(qū)域偏置，最終在狀態(tài)空間中構(gòu)造一條平穩(wěn)分布等于系統(tǒng)狀態(tài)的后驗(yàn)概率分布的馬氏鏈. MCMCPF及其若干改進(jìn)算法，如自適應(yīng)MCMCPF(adaptive MCMCPF， AMCMCPF)算法等[12]，大幅降低了粒子濾波對(duì)提議分布的依賴程度，且能夠明顯提高采樣效率. 然而，目標(biāo)狀態(tài)的后驗(yàn)概率分布往往由于干擾存在而呈現(xiàn)多模態(tài)，此時(shí)，MCMCPF容易陷入某個(gè)局部最優(yōu)的干擾模態(tài)的峰值區(qū)域，從而導(dǎo)致跟蹤失敗. Maggio等[13]提出的混合粒子濾波(hybrid particle filters， HPF)在采樣得到加權(quán)粒子集合后，再令每個(gè)粒子進(jìn)行均值偏移，使之向與之最鄰近的概率峰值移動(dòng)，然而，無(wú)差別的對(duì)所有粒子進(jìn)行均值偏移可能導(dǎo)致其計(jì)算復(fù)雜度較高，不能滿足實(shí)時(shí)性要求，且均值偏移過(guò)程往往容易陷入局部最優(yōu).

本文提出一種重要性排序蒙特卡洛(importance ordering monte carlo， IOMC)粒子濾波算法. IOMC粒子濾波首先從初始提議分布抽取少量加權(quán)初始粒子，再進(jìn)行多次迭代，每次迭代通過(guò)重要性排序選擇一個(gè)權(quán)值較高的粒子作為狀態(tài)轉(zhuǎn)移核以產(chǎn)生新樣本，以構(gòu)建多條獨(dú)立馬氏鏈. IOMC的采樣過(guò)程始終在全局樣本空間中進(jìn)行，不會(huì)陷入局部最優(yōu).

1 基于粒子濾波的物體跟蹤

1.1 粒子濾波

物體跟蹤問(wèn)題可以描述為貝葉斯濾波問(wèn)題. 定義物體在t時(shí)刻的狀態(tài)為xt=(x，y，s)，其中(x，y)表示其中心坐標(biāo)，s表示其尺度. 假設(shè)物體的狀態(tài)轉(zhuǎn)移服從馬爾可夫過(guò)程，即

(1)

給定起始時(shí)刻至當(dāng)前時(shí)刻t的觀測(cè)值序列z1:t={z1，z2，…，zt}，貝葉斯濾波通過(guò)下式遞歸地更新目標(biāo)狀態(tài)的后驗(yàn)概率密度p(xt|z1:t)：

(2)

(3)

(4)

為得到加權(quán)樣本集，標(biāo)準(zhǔn)粒子濾波基于重要性采樣方法自提議分布q(·)中抽取粒子，并通過(guò)遞歸的方式更新粒子權(quán)值. 在一階馬爾科夫假設(shè)下，粒子的權(quán)值遞歸更新公式為

(5)

式(5)的具體推導(dǎo)過(guò)程可參考文獻(xiàn)[4].

1.2 MCMCPF算法

(6)

2 基于IOMC粒子濾波的物體跟蹤

復(fù)雜場(chǎng)景中由于存在與目標(biāo)特征相似的背景區(qū)域或其他物體，可能在目標(biāo)可能出現(xiàn)的區(qū)域內(nèi)同時(shí)存在多個(gè)模態(tài). 由于MCMCPF算法在采樣初期無(wú)法對(duì)每個(gè)模態(tài)的重要性進(jìn)行準(zhǔn)確估計(jì)，導(dǎo)致其采樣過(guò)程容易陷入局部最優(yōu)，進(jìn)而不能充分估計(jì)后驗(yàn)分布的每個(gè)模態(tài)，也無(wú)法從中找出真正的目標(biāo)模態(tài). 為解決這一問(wèn)題，本文提出重要性排序蒙特卡洛(importance ordering Monte Carlo， IOMC)粒子濾波算法. 算法采用延遲判斷的策略，同時(shí)創(chuàng)建和充分增長(zhǎng)多條獨(dú)立馬氏鏈，以對(duì)所有可能的模態(tài)都進(jìn)行充分?jǐn)M合逼近，最后再?gòu)亩鄠€(gè)模態(tài)中準(zhǔn)確選擇最優(yōu)模態(tài). 當(dāng)場(chǎng)景中僅有一個(gè)模態(tài)時(shí)，IOMC粒子濾波近似于普通的MCMCPF. 另外，傳統(tǒng)的權(quán)值歸一化方法可能造成個(gè)別樣本權(quán)值過(guò)高，進(jìn)而使采樣陷入局部最優(yōu). 為避免這一問(wèn)題，以保證每條馬氏鏈都能得到充分增長(zhǎng)，在每次迭代中，算法采用重要性排序策略選擇作為狀態(tài)轉(zhuǎn)移核的歷史樣本. 由于對(duì)多模態(tài)進(jìn)行了更充分的逼近擬合，算法能夠更為有效的從多模態(tài)后驗(yàn)分布中估計(jì)后驗(yàn)概率分布.

(7)

(8)

集合St中的每一粒子被視作一條獨(dú)立馬氏鏈的初始樣本點(diǎn)，通過(guò)Mb(Mb≥Ma)次迭代更新，最終得到多條獨(dú)立馬氏鏈. 每次迭代中，選擇重要性較高的一條馬氏鏈通過(guò)MH采樣對(duì)其進(jìn)行更新.

(9)

IOMC粒子濾波在t時(shí)刻的詳細(xì)步驟如下所示：

③ 重要性MH采樣：

Ⅰ)從均勻分布抽取隨機(jī)數(shù)c～U(1，Ma)，從均勻分布抽取隨機(jī)數(shù)d～U(1，Ma)；

Ⅱ)自索引為c的粒子開(kāi)始遍歷尋找滿足以下條件的粒子：

(10)

⑤ 執(zhí)行重要性重采樣：

Ⅰ) 歸一化粒子權(quán)值；

Ⅱ) 消除權(quán)值較小的粒子，并復(fù)制權(quán)值較大的粒子，獲得Ma個(gè)新樣本；

Ⅲ) 為每個(gè)再采樣之后的樣本賦予相同的權(quán)值.

實(shí)際中，由于擬合同一模態(tài)的馬氏鏈在多次迭代后可能重合，在每次迭代后合并重合馬氏鏈以減少馬氏鏈數(shù)可以進(jìn)一步提高IOMC采樣的效率. 由于IOMC粒子濾波算法的采樣數(shù)是固定的數(shù)目(Ma+Mb)，因此其運(yùn)算時(shí)間與采用同樣粒子數(shù)的MCMCPF算法基本相同，并不受模態(tài)數(shù)或者馬氏鏈數(shù)的影響.

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證IOMC粒子濾波算法的有效性，進(jìn)行了仿真實(shí)驗(yàn)與真實(shí)視頻跟蹤場(chǎng)景中進(jìn)行的實(shí)驗(yàn)，并與傳統(tǒng)粒子濾波算法、HPF算法以及MCMCPF算法進(jìn)行比對(duì). 在實(shí)驗(yàn)中，傳統(tǒng)粒子濾波算法、HPF算法和本文算法采用狀態(tài)轉(zhuǎn)移方程作為提議分布，MCMCPF算法則采用狀態(tài)預(yù)測(cè)值作為初始樣本. 仿真實(shí)驗(yàn)以及真實(shí)場(chǎng)景實(shí)驗(yàn)中比對(duì)算法使用150個(gè)粒子，同時(shí)令Ma=50，Mb=100.

3.1 仿真實(shí)驗(yàn)

人工生成一個(gè)非線性非高斯系統(tǒng)，用x0表示系統(tǒng)初始狀態(tài)，實(shí)驗(yàn)中令x0=1;用xt表示系統(tǒng)的當(dāng)前狀態(tài). 系統(tǒng)的狀態(tài)轉(zhuǎn)移方程和觀測(cè)方程可分別表示為

(11)

(12)

為分析所測(cè)試的算法在仿真實(shí)驗(yàn)中的表現(xiàn)，計(jì)算每次實(shí)驗(yàn)不同算法的根均方差(root mean square error， MRSE)的均值及方差，以測(cè)試不同方法狀態(tài)估計(jì)的準(zhǔn)確性以及方法的魯棒性. 其中一次獨(dú)立實(shí)驗(yàn)的根均方差的計(jì)算公式為

(13)

圖1展示了在一次獨(dú)立實(shí)驗(yàn)中不同算法得到的狀態(tài)估計(jì)值以及真實(shí)狀態(tài)值和虛警；圖2展示了不同算法的根均方差. 表1中給出了不同算法的根均方差均值及方差.

由于HPF算法難以用仿真的方式實(shí)現(xiàn)，因此僅給出其他3種方法的結(jié)果. 由于在仿真實(shí)驗(yàn)中存

表1 不同算法的根均方差均值及方差

Tab.1 Mean value and covariance of RMSE of different methods

算法θRMSE均值方差本文算法0.01570.0004標(biāo)準(zhǔn)粒子濾波0.38250.0057MCMCPF0.62800.0102

在虛警，因此后驗(yàn)分布中包含了目標(biāo)模態(tài)和干擾模態(tài). 標(biāo)準(zhǔn)粒子濾波算法沒(méi)有考慮不同的模態(tài)，對(duì)任何一種模態(tài)都沒(méi)有進(jìn)行充分逼近；MCMC算法由于容易陷入局部最優(yōu)，在采樣過(guò)程中傾向于向單一模態(tài)逼近，當(dāng)所逼近的模態(tài)為干擾模態(tài)時(shí)狀態(tài)估計(jì)精度明顯下降；IOMC粒子濾波對(duì)兩種模態(tài)都進(jìn)行了充分逼近，輸出結(jié)果為最優(yōu)模態(tài)的值，因此如圖中以及表中的結(jié)果顯示，IOMC粒子濾波的表現(xiàn)明顯優(yōu)于其他兩種算法.

3.2 真實(shí)場(chǎng)景實(shí)驗(yàn)

使用標(biāo)準(zhǔn)數(shù)據(jù)集中的視頻進(jìn)行真實(shí)視頻實(shí)驗(yàn). 所測(cè)試的算法均采用一階恒速模型作為狀態(tài)轉(zhuǎn)移方程，并采用歸一化的HSV顏色直方圖作為觀測(cè)模型. 選取數(shù)據(jù)PETS2009[15]中的低幀率視頻“View_001”測(cè)試不同算法跟蹤突然運(yùn)動(dòng)的目標(biāo)的魯棒性. 所測(cè)試算法皆通過(guò)手動(dòng)初始化. 表2中給出了4種方法的定量分析結(jié)果，其中運(yùn)行速度用算法1 s處理的幀數(shù)衡量，成功率為目標(biāo)被成功跟蹤的時(shí)長(zhǎng)與目標(biāo)從初始幀至被完全遮擋前出現(xiàn)的總時(shí)長(zhǎng)的比值.

表2 不同算法的跟蹤結(jié)果

如表2中所示，本文算法以及HPF的跟蹤成功率明顯高于粒子濾波算法和MCMCPF算法，但是HPF算法運(yùn)行速度較低，不能滿足實(shí)時(shí)性需求.

圖3給出了定性分析結(jié)果. 在該低幀率視頻中，由于目標(biāo)運(yùn)動(dòng)缺乏連續(xù)性，導(dǎo)致從提議分布位于概率分布的邊緣區(qū)域，從提議分布采樣的有效率極低，因此傳統(tǒng)粒子濾波跟蹤器在較短的時(shí)間內(nèi)就丟失了目標(biāo). MCMCPF跟蹤器的跟蹤失敗則主要是由于在采樣初期選擇了不恰當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移核，同時(shí)陷入了局部最優(yōu)，在目標(biāo)運(yùn)動(dòng)不連續(xù)的情況下，這種情況出現(xiàn)的概率很高. 本文提出算法通過(guò)同時(shí)構(gòu)建多條互相獨(dú)立的馬氏鏈，增大了采樣范圍，保證了在高置信度區(qū)域能夠采集足夠數(shù)量的樣本，在目標(biāo)運(yùn)動(dòng)不連續(xù)的情況下仍能實(shí)現(xiàn)較為準(zhǔn)確的跟蹤.

4 結(jié) 論

提出一種用于物體跟蹤的IOMC粒子濾波算法，并通過(guò)仿真實(shí)驗(yàn)以及真實(shí)視頻中的實(shí)驗(yàn)證明了其性能的優(yōu)異性.當(dāng)場(chǎng)景中存在與目標(biāo)相似的背景區(qū)域或者物體時(shí)，目標(biāo)的后驗(yàn)概率分布往往存在多模態(tài).IOMC粒子濾波算法采用延遲判斷的策略，首先通過(guò)重要性排序同時(shí)構(gòu)建多條獨(dú)立馬氏鏈，以分別對(duì)不同的模態(tài)進(jìn)行充分逼近擬合，然后選擇最優(yōu)模態(tài)的峰值作為狀態(tài)估計(jì)值，能夠在后驗(yàn)分布呈多模態(tài)的復(fù)雜背景下實(shí)現(xiàn)魯棒的視頻跟蹤.在將來(lái)的工作中作者將著重研究將本文算法與自適應(yīng)性以及辨識(shí)性較強(qiáng)的物體表征模型結(jié)合，以更好地應(yīng)對(duì)跟蹤中目標(biāo)與其他物體交互、遮擋以及場(chǎng)景中光線突變等復(fù)雜情況.

[1] Cue H，Cadre J-P L， Perez P. Tracking multiple objects with particle filtering[J]. IEEE Transactions on Aerospace Electronic System， 2002，38(3):791-812.

[2] Kang H，Kim D，Bang S Y. Real-time multiple people tracking using competitive condensation[J]. Pattern Recognition， 2002，38(7):1045-1058.

[3] Okuma K， Taleghan A， Freitas J F G， et al. A boosted particle filter: multitarget detection and tracking[J]. Computer Vision-ECCV, 2004,3021:28-39.

[4] 王法勝，趙清杰.一種用于解決非線性濾波問(wèn)題的新型粒子濾波算法[J].計(jì)算機(jī)學(xué)報(bào)，2008，31(2):346-352.

Wang Fasheng， Zhao Qingjie. A new particle filter for nonlinear filtering problems[J]. Chinese Journal of Computers，2008，31(2):346-352. (in Chinese)

[5] Isard M，Blake A. Condensation-conditional density propagation for visual tracking[J]. International Journal of Computer Vision， 1998，29(1):5-28.

[6] Zhou S K， Chellappa R， Moghaddam B. Visual tracking and recognition using appearance-adaptive models in particle filters[J]. IEEE Transactions on Image Processing， 2004，13(11):1491-1505.

[7] Stasiak L， Pacut A， Gordon N. Particle filters for multi-face detection and tracking with automatic clustering[C]∥Proceedings of IEEE International Workshop on Imaging Systems and Techniques. Krakow: IEEE， 2007:1-6.

[8] Vermaak A，Doucet A，Perez P. Maintaining multi-modality through mixture tracking[C]∥Proceedings of IEEE International Conference on Computer Vision. Washington D C: IEEE Computer Society Press, 2003:1110-1116.

[9] Kotecha， J H， Djuric P M. Gaussian particle filtering[J]. IEEE Transactions on Signal Processing， 2003，51(10):2592-2601.

[10] Rui Y， Chen Y. Better proposal distributions: object tracking using unscented particle filter[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D C: IEEE Computer Society Press， 2001:786-793.

[11] Gillks W， Berzuini C. Following a moving target: Monte Carlo inference for dynamic Bayesian models[J]. Journal of Royal Statistic Society B， 2001，63(1):127-146.

[12] Pei F， Cui P， Chen Y. Adaptive MCMC particle filter for nonlinear and non-Gaussian state estimation[C]∥Proceedings of International Conference on Innovative Computing Information and Control. Washington D C: IEEE Computer Society Press， 2008:494-498.

[13] Maggio E， Cavallaro A. Hybrid particle filter and mean shift tracker with adaptive transition model [C]//Proceeding of IEEE Signal Processing Society International Conference on Acoustics， Speech， and Signal Processing. Philadelphia: IEEE， 2005:221-224.

[14] Geyer Charles J. Introduction to Markov Chain Monte Carlo [M]. [S.l.]: Chapman and Hall/CRC Press， 2011.

[15] Cite Seer X. PETS 2009 benchmark data set.[2009-01-02]. http://www.cvg.rdg.ac.uk/PETS2009/a.html.

(責(zé)任編輯：劉芳)

Object Tracking Arithmetic Based on Importance Ordering Monte Carlo Particle Filtering

XU Wei-cun， ZHAO Qing-jie， WANG Yu-xia, ZHAO Liu-jun

(School of Computer Science， Beijing Institute of Technology， Beijing 100081, China)

In order to obtain efficient object tracking under cluttered scenes, a method was proposed based on importance ordering Markov Chain Monte Carlo (MCMC) particle filtering. Firstly, a few authorized initial particles were made use to approximate the true posterior particle distribution. And then the new particles were drawn from the rough approximation with the proposed importance ordering MCMC sampling strategy to build several independent Markov Chains, corresponding one-to-one to the modes of the true posterior distribution, so as to approximate the multimode of the true posterior distribution. According to the current mode distribution, the method could establish several adaptive independent Markov Chains to approximate the posterior distribution of objects under multimode cluttered scenes. An importance ordering strategy was taken to make fully use of the history samples for state transfer decision, to increase the possibility that small weight samples could be selected and to decrease the probability that build process of Markov Chains got in local optimized. Simulation and verity experiment show that the proposed method can achieve stably and exactly object tracking, its performance is better than the standard particle filtering method and the MCMC particle filtering method.

object tracking; importance ordering; Markov Chain Monte Carlo; particle filtering； multiple modes

2013-09-20

國(guó)家自然科學(xué)基金資助項(xiàng)目(60772063，61175096)

許偉村(1985—)，男，博士生，E-mail:xuwcun@gmail.com.

TP 273

A

1001-0645(2016)01-105-06

10.15918/j.tbit1001-0645.2016.01.019