佳點集的QMC粒子濾波算法及其應用

劉峰，宣士斌，劉香品

視頻目標跟蹤是近年來計算機視覺領域中的研究熱點，在人機交互、視頻監控、智能交通等方面都有著廣泛的應用。粒子濾波算法(particle filter，PF)因能有效地解決視頻目標跟蹤中普遍存在的非線性、非高斯性的問題[1]，在視頻跟蹤領域得到了足夠的重視[2-4]。而在實際應用中，粒子濾波卻存在權值退化現象，雖然通過采用重采樣技術可以復制大權值樣本[5]，但又不可避免地會導致粒子匱乏問題[6]，當系統噪聲較小時，易造成樣本的聚集。為解決這一問題，提高粒子濾波的采樣效率，一些學者提出選取更好的提議分布，采用復雜的抽樣策略。比如輔助采樣、分區采樣、退火重要性采樣等[7]。

擬蒙特卡洛(Quasi-Monte Carlo, QMC)方法是一種確定性的采樣方法，它利用準隨機數產生均勻分布在狀態空間的點，與MC方法的隨機樣本分布不同，QMC方法能產生低偏差序列的樣本，基于QMC方法的粒子濾波(Quasi-Monte Carlo particle filter, QMCPF)用更少的粒子就能達到所需的精度，能有效地解決基于MC的隨機采樣過程獲得的粒子在狀態空間積聚在一起或形成空隙的問題。

本文提出利用數論中的佳點集理論和方法[8]來構造一種新的擬蒙特卡洛序列。利用佳點集方法取的點要比隨機取點的偏差更小，并且佳點集序列與常用的擬蒙特卡洛序列Halton序列相比分布更均勻，在濾波過程中可提高狀態估計的精度和收斂速度，減少了樣本重疊，避免了運算的浪費，提高了樣本的質量。在非線性系統狀態估計精度要優于粒子濾波和現有的擬蒙特卡洛粒子濾波算法。將GPS-QMCPF應用于視頻目標跟蹤中，實驗結果表明，基于GPS-QMCPF的視頻目標跟蹤算法能較好地解決有遮擋情況下的跟蹤，同時還能一定程度上縮減跟蹤時間；實驗還比較了PSO-PF和PSO優化GPS-QMCPF算法在視頻目標跟蹤中的性能數據，發現在PSO-PF算法中加入佳點集思想同樣能起到增加粒子有效樣本數和降低重采樣次數的作用。

1 QMCPF算法

1.1 QMC方法

QMC方法采用低差異序列生成樣本，可有效地避免隨機抽樣中可能出現的樣本空隙和樣本聚焦現象[9]。目前已經提出的擬蒙特卡洛序列主要有Van der Corput序列、Faure序列、Sobol序列、Halton序列以及Niederreiter的(t,s)序列。

在實際應用中使用較多的是Halton序列，可以根據式(1)、(2)得到

(1)

(2)

式中:b為基數，m、dk分別為項數和系數。

1.2 QMCPF算法

QMCPF算法關鍵是以QMC方法代替MC方法來實現粒子濾波的采樣過程，QMC方法生成的低差異樣本序列能使QMCPF的精度優于PF[9]。QMCPF的主要思路如下：先以QMC方法生成初始低差異粒子集，通過生成支撐區間來映射k時刻低差異性的粒子集；隨后根據k-1時刻所有粒子的分布情況計算k時刻的權重。

2 基于佳點集擬蒙特卡洛的粒子濾波算法(GPS-QMCPF)

利用數論中的佳點集理論和方法來設計一個新的生成低差異樣本序列的QMC算法。因能構造出更均勻、更低偏差的點集?？商岣邤M蒙特卡洛的粒子濾波算法估計的準確度和加快算法的收斂速度。

2.1 佳點集理論

佳點集的定義與構造[8]：

1)設Gt是S維空間中的單位立方體，即x∈Gt，x=(x1,x2,…,xt)，其中0≤xi≤1(i=1,2,…,t)。

3)對任一給定Gt中的點〈r〉=(r1,r2,…，rt)，令Nn(〈r〉)=Nn(r1,r2,…，rt)表示pn(k)中滿足不等式(3)、(4)的點的個數：

(3)

(4)

式中：|〈r〉|=r1,r2,…，rt，則稱點集pn(k)有偏差φ(n)。若對任一n，均有φ(n)=O(1)，則稱pn(k)在Gt上是一致分布的且偏差為φ(n)。

4)令〈r〉∈Gt，形成pn(k)={r1*k,r2*k,…,rt*k} (k=1,2,…,n)的偏差φ(n)滿足φ(n)=C(r,ε)n-1+ε，其中C(r,ε)是只與r,ε(ε>0)有關的常數，則稱pn(k)為佳點集，〈r〉稱為佳點。

5)取rk={2cos(2πk/p)}(1≤k≤t)或rk={exp(k)}(1≤k≤t)，p是滿足(p-s)/2≥s的最小素數，則〈r〉是佳點。

2.2 GPS-QMCPF算法的優點

擬蒙特卡洛方法計算的準確性及收斂速度主要取決于偏差，偏差用來度量點列在函數域上的均勻分布程度，點列分布越均勻，偏差就越小，收斂速度就越快，波動也相應地會減小，計算準確度也隨之提高?？梢杂肒oksma-Hlawka不等式給出擬蒙特卡洛方法的計算誤差如式(5)所示。

(5)

標準的擬蒙特卡洛粒子濾波算法一般采用Halton序列為初始采樣序列。構造400個二維佳點集和400個二維Halton點集，同時用隨機方法在二維空間內取400個點，圖1～3分別給出了它們的分布效果?？梢钥闯?，佳點集的分布要比Halton序列和隨機序列更均勻。而且只要取點個數一定，每次所得的分布效果是一致的，由此可知佳點集穩定性較好。其次佳點集的構造與空間維數無關，能夠很好地適應高維問題。

圖1 400個二維隨機點集Fig.1 400 two-dimensional random point set

圖2 400個二維Halton點集Fig.2 400 two-dimensional Halton sequence point set

圖3 400個二維佳點集Fig.3 400 two-dimensional good point set

GPS-QMCPF利用GPS-QMC方法的低偏差序列生成均勻分布的樣本，改善了樣本聚焦和樣本空隙的現象，使得GPS-QMCPF的精度明顯優于PF；并且通過圖2、3，可以看出GPS-QMC方法的低偏差序列比Halton序列更均勻，因為點列分布越均勻，偏差就越小，收斂速度也越快，因此GPS-QMCPF算法比標準的QMCPF算法的精度也要更好。

2.3 GPS-QMCPF的計算步驟

xi=α+(β-α)·ui

(6)

(7)

3)利用式(8)計算粒子的權值：

(8)

4)將權重歸一化：

(9)

5)狀態值估計：

(10)

3 實驗仿真

為了驗證文中GPS-QMCPF法的有效性，程序基于MATLAB R2012a和VC++ 6.0編程環境在CPU為AMD Athlon(tm) II X2 B24 Processor 2.99 GHz，內存為1.75 GB的PC機上運行。

3.1 單變量非靜態增長模型

選取單變量非靜態增長模型(UNGM模型)，仿真對象的過程模型和觀測模型如下。

過程模型：

8cos[1.2(t-1)]+w(t)

(11)

觀測模型：

(12)

式中：w(t)和v(t)為零均值高斯噪聲。

采用PF，文獻[11]中對QMCPF改進后的NQMCPF算法，文獻[12]中的TR-SQMC，GPS-QMCPF估計該非線性系統的狀態。實驗取過程噪聲方差Q為10、觀測噪聲方差R為1進行仿真，具體數據如表1所示(RMSE為均方根誤差)。

表1 UNGM模型仿真數據比較

表2 有效樣本數比較

由實驗結果可以看出，基于GPS-QMC方法的粒子濾波可以用較少的粒子達到所需要的精度。PF的誤差遠高于QMC-PF、TR-SQMC和GPS-QMCPF，其中GPS-QMCPF的誤差最小。并且GPS-QMCPF算法減少了樣本的重疊和聚焦現象，減輕了粒子的退化程度，所以有效樣本數大于PF、NQMCPF和TR-SQMC算法。

3.2 在視頻目標跟蹤中的應用

3.2.1 建立運動模型

跟蹤目標外輪廓通常采用橢圓或矩形，目標狀態可以表示為

(13)

本文采用一階常速模型描述跟蹤目標的運動規律，在整個運動過程中，目標中心(x,y)采用常速運動模型，而(Hx,Hy)采用隨機擾動模型，因此，建立運動方程[13]：

(14)

3.2.2 建立觀測模型

本文采用最常用的顏色直方圖作為目標特征觀測模型，采用巴特查理亞距離(Bhattacharyya)作為目標顏色直方圖與粒子區域的顏色直方圖相似性的量度。對于2個連續分布p(u)和q(u)的巴特查理亞系數為

(15)

巴特查理亞距離為[14]

(16)

當d值越小說明候選區域的顏色直方圖與目標區域的顏色直方圖越相似，應賦予較大的粒子權值，反之，則相似程度越低，粒子權值也越小。因此，觀測似然函數可以表示為

17)

粒子的權值為

(18)

3.2.3 在視頻目標跟蹤中的實驗仿真

為了驗證算法的有效性，進行了大量視頻目標跟蹤的實驗，分別對比PF、NQMCPF算法和GPS-QMCPF算法的跟蹤效果。

在實驗中，首先要在初始幀手動選取參考目標并計算目標區域的顏色直方圖，并在選定目標區域中隨機采樣N個粒子，如圖4～5所示，在一組遙控玩具直升飛機的視頻序列中的PF算法隨機采樣和GPS-QMCPF算法佳點集采樣情況，取粒子數為100，從圖中可以看出佳點集的分布均勻且集中。

圖4 初始幀目標區域隨機采樣Fig.4 Random sampling around the target in the first frame

圖5 初始幀目標區域佳點集采樣Fig.5 Good point set sampling around the target in the first frame

如圖6～8所示。這組視頻序列實驗中，361-365幀直升機部分被遮擋。從實驗效果圖可以看出GPS-QMCPF算法跟蹤效果比PF算法好，精度更高。

圖6 PF算法的跟蹤效果Fig.6 PF algorithm tracking performance

圖7 NQMCPF算法的跟蹤效果Fig.7 NQMCPF algorithm tracking performance

圖8 GPS-QMCPF算法的跟蹤效果Fig.8 GPS-QMCPF algorithm tracking performance

對這組視頻序列實驗中PF和GPS-QMCPF算法的計算量進行分析。取視頻第81～480幀，統計20次實驗數據的平均值。

表3 實驗性能數據對比

表4 運行時間對比

表3～4的數據表明，GPS-QMCPF算法可增加粒子的有效樣本數，減少重采樣次數，同時可降低計算量，運行時間相應也降低，跟蹤的實時性得到了提高。

本文再將文獻[15]提出的粒子群優化粒子濾波算法(particle swarm optimization particle filtering, PSO-PF)應用于視頻目標跟蹤中，并與粒子群優化的GPS-QMCPF算法進行對比，實驗性能數據對比見表5～6，實驗取視頻第81～480幀，統計20次實驗數據的平均值。

表5 實驗性能數據對比

表6 運行時間對比

表5～6的數據表明，在PSO-PF算法中加入佳點集思想進行初始采樣在視頻目標跟蹤領域同樣能增加粒子的有效樣本數，減少重采樣次數，加快算法收斂，進而降低算法的運行時間，提高跟蹤的實時性。

4 結束語

本文提出的GPS-QMCPF算法，利用佳點集確定性采樣代替了粒子濾波中的隨機采樣，使采樣粒子分布更加均勻，減少了樣本重疊，避免了運算的浪費，提高了樣本的質量，同時加快了收斂速度，在非線性系統狀態估計精度要優于粒子濾波和現有的擬蒙特卡洛粒子濾波算法。實驗結果表明，基于GPS-QMCPF的視頻目標跟蹤算法能較好地解決有遮擋情況下的跟蹤，同時還能一定程度上縮減跟蹤時間；實驗還比較了PSO-PF和PSO優化GPS-QMCPF算法在視頻目標跟蹤中的性能數據，發現在PSO-PF算法中加入佳點集思想同樣起到增加粒子有效樣本數和降低重采樣次數的作用。

參考文獻:

[1]姚劍敏,辛琦,郭太良. 一種基于粒子濾波的自適應相關跟蹤算法[J].武漢理工大學學報, 2008, 30(1): 6-9

YAO Jianmin, XIN Qi, GUO Tailiang. Adaptive correlation tracking algorithm based on particle filter[J]. Journal of Wuhan University of Technology, 2008, 30(1): 6-9.

[2]朱明清,王智靈,陳宗海.基于改進Bhattacharyya系數的粒子濾波視覺跟蹤算法[J].控制與決策, 2012, 27(10): 1579-1583.

ZHU Mingqing, WANG Zhiling, GHEN Zonghai. Modified Bhattacharyya coefficient for particle filter visual tracking [J]. Control and Decision, 2012, 27(10): 1579-1583.

[3]MADRIGAL F ,RIVERA M, HAYET J B. Learning and regularizing motion models for enhancing particle filter-based target tracking[J]. Advances in Image and Video Technology Lecture Notes in Computer Science, 2012, 7088: 287-298.

[4]王愛俠,李晶皎,王青,等.基于多核的并行粒子濾波運動目標跟蹤[J].計算機科學, 2012, 39(8): 296-299.

WANG Aixia, LI Jingjiao, WANG Qing, et al. Target tracking based on multi-core parallel particle filtering[J]. Computer Science, 2012, 39(8): 296-299.

[5]GORDON N，SALMOND D J，SMITH A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation[C]//IEE Proceedings of Radar and Signal Processing. Cambridge, UK: IEE,1993: 107-113.

[6]DOUCET A, GODSILL S. On sequential Monte Carlo sampling methods for Bayesian filtering[J]. Statistics and Computing, 2000, 10(1): 197-208.

[7]DING Xiaofeng, XU Lizhong, WANG Xin. Roubust visual object tracking using covariance features in quasi-Monte Carlo filter[J]. Intelligent Automation and Soft Computing, 2011, 17(5): 571-582.

[8]華羅庚,王元.數論在近似分析中的應用[M].北京:科學出版社,1978: 22-26.

[9]GUO D, WANG X D. Quasi-Monte Carlo filtering in nonlinear dynamic systems[J]. IEEE Transactions on Signal Processing, 2006, 54(6): 2087-2098.

[10]WANG Y, FANG K T. Number-theoretic methods in statistics[M]. New York: Chapman & Hall, 1994: 20-25.

[11]陳志敏,薄煜明,吳盤龍,等.擬蒙特卡羅粒子濾波改進算法及其在雷達目標跟蹤中的應用[J]. 應用科學學報, 2012, 30(6): 607-612.

CHEN Zhimin, Bo Yuming, WU Panlong, et al. Improved quasi-Monte-Carlo particle filtering and its application to radar target tracking[J]. Journal of Applied Sciences, 2012, 30(6): 607-612.

[12]徐立中,丁曉峰,王鑫,等.基于信賴域的序貫擬蒙特卡羅濾波算法[J]. 電子學報, 2011, 39 (3A): 24-29.

XU Lizhong, DING Xiaofeng, WANG Xin, et al. Trust region based sequential quasi-Monte Carol filter[J]. Acta Electronica Sinica, 2011, 39 (3A): 24-29.

[13]李安平.復雜環境下的視頻目標跟蹤算法研究[D].上海：上海交通大學， 2006： 20-31.

LI ANPING. Research of tracking algorithm for visual target under complex environments[D]. Shanghai：Shanghai Jiao Tong University, 2006: 20-31.

[14]KATJA N, ESTHER K, LUC V G. Object tracking with and adaptive color based particle filter[C]//Proceedings of the 24th DAGM Symposium on Pattern Recognition. Zurich, Switzerland, 2002: 353-360.

[15]方正,佟國峰,徐心和.粒子群優化粒子濾波方法[J].控制與決策, 2007, 22(3): 273-277.

FANG Zheng, TONG Guofeng, XU Xinhe. Particle swarm optimized particle filter[J]. Control and Decision, 2007, 22(3): 273-277.