嵌入卡爾曼預測器的粒子濾波目標跟蹤算法

摘 要:針對經典的粒子濾波視頻目標跟蹤算法進行粒子傳播采用隨機游走的方式，以及傳統顏色直方圖無法反映目標空間特征的問題，提出了一種改進的基于顏色的粒子濾波目標跟蹤算法。該算法在統計目標二階顏色直方圖的基礎上，獲得粒子的觀察概率密度函數，利用卡爾曼濾波確定粒子動態傳播模型中的確定性漂移部分，使粒子狀態估計值分布更精確地趨向目標的概率分布，大大提高了粒子的利用效率。實驗表明，該改進算法的性能優于經典基于單一顏色特征的粒子濾波算法。

關鍵詞:顏色直方圖; 粒子濾波; 卡爾曼預測; 目標跟蹤

中圖分類號:TP309

文獻標志碼:A

文章編號:1001-3695(2010)02-0468-04

doi:10.3969/j.issn.1001-3695.2010.02.017

Particle filter and embedded in Kalman predictor for target tracking

WANG Yue-ling， WANG Rang-ding

(CKC Software Laboratory， Ningbo University， Ningbo Zhejiang 315211， China)

Abstract:The standard color particle filter spreads each particle with random walk method for target tracking. The traditional color histogram is used that can not reflect the characteristics of the target space. This paper proposed a novel color-based particle filter target tracking algorithms. The second-order color histogram was applied to get the observation of particle probability density function. In addition， used the Kalman filter to determine the spread of particle dynamic model of the uncertainty in the drift of the state. The distribution of particles was more accurately close to the probability distribution of the target， thus the use efficiency of particles was greatly improved. Computer simulation results demonstrate that the proposed algorithm is more robust as compare to the traditional color-based particle filter tracking algorithm.

Key words:color histogram; particle filter(PF); Kalman predictor; target tracking

視頻對象跟蹤技術是計算機視覺領域中一個重要的研究課題，它廣泛應用于監視、伺服、視頻壓縮等領域[1]。目標跟蹤問題實質上是在連續的時間序列中找到用戶感興趣的目標，而目標可以由自身狀態(位置、大小等)來描述，因此跟蹤問題也就等價于對目標狀態變量的后驗概率分布的求解。根據貝葉斯概率模型，后驗概率分布可以通過狀態的先驗分布和狀態與觀測的似然函數來確定。近年來，隨著計算機性能的提高及成本的下降，粒子濾波(PF)已經成為研究非線性、非高斯動態系統最優估計問題的一個熱點和有效方法[2]，經Isard等人[3]引入到計算機視覺領域就迅速成為一個重要的研究方向，人們競相對粒子濾波目標跟蹤中存在的問題進行了深入研究與改進[4~6]。粒子濾波的性能在一定程度上也取決于粒子的動態傳播方法，這實際上就是粒子濾波中重要性采樣函數的設計選擇問題。目前傳統的基于單一顏色特征的粒子濾波跟蹤算法[7]用先驗轉移概率難以有效進行粒子傳播，僅采用隨機游走的方式來完成粒子傳播，這樣會使粒子采樣點過于分散，導致跟蹤性能下降。同時僅采用一階顏色直方圖作為粒子觀察模型的一個線索無法反映色彩分布的空間信息[8]，顏色信息容易被復雜背景干擾，外觀不同的圖像可能具有相同的直方圖。解決這些問題的辦法就是包含更多描述目標特征的信息。

本文提出了一種嵌入卡爾曼預測器的粒子濾波視頻目標跟蹤算法。首先利用Kalman濾波器以低廉的計算成本初步進行目標跟蹤定位，并以此初步跟蹤結果確定粒子濾波動態模型中的確定性漂移部分;然后只需加入一個較小的隨機擴散噪聲就能完成粒子的高效傳播;最后在基于顏色特征的粒子濾波跟蹤算法框架中對觀察模型僅包含顏色信息的前提下，融入目標像素的均值向量和協方差，可增強目標的空間特征。目標跟蹤仿真實驗表明了，其較采用傳統單一顏色特征的粒子濾波跟蹤算法[7]在可靠性、準確性方面有一定的提高。

1 粒子濾波算法

視頻序列的跟蹤問題可以看做是一個動態系統的狀態估計問題。粒子濾波對復雜環境下目標的狀態估計非常有效，它能夠為運動狀態估計提供一種概率框架。粒子濾波的主要思想是:用一組具有權值的粒子來完全地描述后驗概率分布。根據蒙特卡羅理論，當粒子的數目足夠多時，這組具有權值的粒子就能完全地描述后驗概率分布，此時，粒子濾波就是最優的貝葉斯估計。

設x0:k={xj，j=0，…，k}和y1:k={yj，j=0，…，k}分別表示各個時刻的系統狀態和觀測狀態，{wij，i=0，…，N}表示i時刻所對應粒子{xij，i=0，…，N}的歸一化權值，其中∑Ni=1wij=1。粒子濾波就是用{xi0:k，wij}Ni=1來完全描述后驗概率密度分布p(x0:k|y1:k)。文獻[5]提出了對p(x0:k|y1:k)進行重要性采樣的方法。假設存在重要性分布函數π(x)滿足p(x)∝π(x)，并且可以很方便地從π(x)中進行取樣，根據貝葉斯理論，有

π(x0:k|y1:k)=π(xk|x0:k-1，y1:k)π(x0:k-1|y1:k-1)(1)

這樣，就能很容易地對系統狀態進行估計，權值的遞推方程可以寫成

wik∝wik-1p(yk|xik)p(xik|xik-1)π(xik|xik-1，yk)∝wik-1p(yk|x(i)k)(2)

那么，在k時刻的后驗概率密度可以近似地表示為

p(x0:k|y1:k)≈∑Niw(i)jδ(x0:k-x(i)0:k)(3)

其中:δ(#8226;)為沖激函數，粒子的權值w(i)j滿足∑Ni=1wij=1，因此利用加權準則可確定視頻序列中感興趣運動目標的最終位置為

xoptk=∑Ni=1xik×wik(4)

2 本文算法

2.1 包含卡爾曼預測器的粒子動態傳播模型

在基于傳統單一顏色的粒子濾波算法中[7]，粒子的傳播是利用先驗轉移概率p(xk|xk-1)完成的，也即通過一階或二階AR動態模型進行粒子傳播。舉例來講，對于一階AR模型，即

xt=Axt-1+Bωt-1(5)

其中:xt為目標在t時刻的狀態;隨機數ωt-1∈[0，1]是歸一化噪聲量;A、B為常數，B為粒子傳播半徑。對于復雜的運動目標而言，很難用一個固定不變的A來描述目標的確定性漂移運動部分，因此一些跟蹤系統消極地只保留運動模型中隨機擴散部分，即采用隨機游走的方式來進行傳播，難以有效解決粒子的動態傳播問題[9]。如果在跟蹤過程中對動態模型中的確定性漂移部分作出較為準確預測，這將在很大程度上減少動態模型的隨機性，只需加入一個小的隨機擴散便可完成粒子的傳播。為實現上述思想，本文在原粒子傳播過程中嵌入一個低復雜度的跟蹤器Kalman濾波器[10]，并用所得的初步跟蹤結果計算粒子動態傳播模型中的確定性漂移部分。

Kalman預測器是一種遞推估計器，無須考慮多個過去的輸入信號，而且每次遞歸運算時，只考慮前一個輸入信號，便于系統對信號的實時處理。在Kalman預測的基礎上，很容易得出從t-1幀到t幀的目標狀態轉移矢量為

Δxt=xt-xt-1(6)

其中:xt和xt-1分別表示第t幀和第t-1幀中卡爾曼預測器所給出的跟蹤結果，進而可以把式(5)所示的AR動態模型改寫成下面的顯性確定性漂移隨機擴散的形式，即

xt=Axt-1+Δxt-1+Bωt-1(7)

2.2 系統觀測模型的建立

本文是在視頻序列的RGB空間采用二階直方圖[11]建模的方法來描述目標顏色特征，它比顏色直方圖包含更豐富的目標信息，使用了基于核函數的目標跟蹤中提到的核函數[12]的概念，選用加權彩色直方圖作為目標模型。加權彩色直方圖反映了目標區域的全局統計特征，核函數選擇了Epanechnikov Kernel，即

KE(x)=c(1-‖x‖2)‖x‖<10otherwise(8)

從式(8)可以看出，Κ是一個凸的單調下降函數，此函數給目標中的像元分配權值。由于跟蹤目標受到背景和一些遮擋的影響，周邊的像元可靠性低，離中心越遠的像元分配的權值越小， 即位于目標中央的區域貢獻最大，這樣處理可以提高估計值的魯棒性。通過式(9)建立目標顏色直方圖為

p(u)y=f∑Ni=1k(‖xi-y‖h)δ[h(xi)-n](9)

其中:f為歸一化系數;p(u)y表示以y為中心點的第n階直方圖的權值;N表示區域內的像素個數;k(#8226;)為Epanechnikov Kernel;xi為區域內任意一點;‖xi-y‖為xi到y的距離;δ[#8226;]為單位沖激函數，判斷n是否為當前像素;h(xi)為xi所對應的顏色空間的色階;h為當前窗口的帶寬，本文取運動目標矩形框長寬的一半。

在目標跟蹤中，被估計的目標狀態在每進行一次觀測就被更新一次，并且合并到新的觀測中去，因此，就需要一個基于顏色分布的相似性測量。在相似性度量方面選擇加權的Bhattacharryya系數計算相似性:

ρy[p，q]=∑mn=1ωbp(n)yq(n)(10)

其中:ρy[p，q]表示在y處建立的二階直方圖作為目標模型的概率分布p(u)y和預先建立的模板概率分布q(n)之間的相似程度，ρy[p，q]∈(0，1)越大，相似性程度越高。

ωb=η exp{-12(μb(y)-μ′b)T∑Λ-1b(μb(y)-μ′b)}

為高斯核函數。在一階顏色直方圖中ωb=1，而在二階直方圖中不為1;η為高斯常數，其中∑Λ-1b=(∑-1b(y)+(∑′b)-1);μ′b和∑′b分別為預先建立模板空間信息的均值和協方差矩陣。由文獻[13]可知，多元正態分布完全被式(11)和(12)得到的反映目標像素空間特征的均值向量和協方差所決定，即

μb(y)=1∑Νhj=1δjb∑Νhi=1(xi-y)δib(11)

∑b(y)=1∑Νhj=1δjb∑Νhi=1((xi-μb(y))T(xi-μb(y)))δib(12)

其中:Nh表示區域內的像素個數;(xi-μb(y))T為矩陣(xi-μb(y))的轉置;m表示顏色量化的階數。兩種分布之間的差距定義為

d(y)=1-ρy[p，q](13)

統計量d(y)對目標尺度的變化不敏感，因此對于隨機分布密度很有效。如果感興趣的那些樣本的顏色分布與預先建立的目標模型相似，較小的Bhattacharryya系數距離分配大的權值。這樣可以計算觀察值的概率密度函數為

p(zk|x(m)k)=12πσe-d22σ2=12πσe-(1-ρ[px(m)，q])2σ2(14)

由式(2)可知粒子的權值更新為

wik∝wik-1p(zk|x(i)k)=wik-112πσe-(1-ρ[px(i)，q])2σ2(15)

2.3 算法實現

本文的算法是基于RGB空間二階顏色直方圖的粒子濾波算法，嵌入卡爾曼預測器可以產生較為準確的粒子確定性漂移，使粒子能較為精確地集中分布在狀態的真實區域附近。具體跟蹤過程包括初始化、預測、更新和重采樣，如圖1所示。

算法一個迭代過程的具體描述如下:

a)初始化

首先通過在目標周圍感興趣的區域手動選取一個矩形區域，取一定量的粒子數N，并賦予每個粒子的初始權值為1/N，所有粒子的權值之和為1，每個粒子代表目標的一個可能的運動狀態，即目標的一個可能的位置為

xi=x0+bξ(16)

其中:ξ∈[-1，1]的隨機數，b是常數。然后通過式(10)計算目標區域的二階直方圖，構建目標初始的系統觀測模型。

b)預測

系統狀態轉移，即粒子的傳播，指的是目標狀態時間的更新過程。由于運動目標的自主運動趨勢一般比較明顯，粒子傳播可以是一種隨機運動過程，一般采用一個較大的隨機擴散噪聲矩陣，這樣會使粒子分布過于分散，很大一部分粒子點對狀態的估計貢獻很小，使得大量的計算浪費在對狀態估計微不足道的粒子點上，影響跟蹤效果。因此，本文采用嵌入卡爾曼預測器的方法，即式(7)進行粒子的動態傳播。

c)更新

文中算法更新主要是目標模型的更新，考慮到目標有可能會被暫時遮擋或受到與之具有相近特征的其他目標的影響，在每一時刻，根據更新條件:πX^[s]>πT。其中:πX^[s]為粒子狀態X[s]的概率分布歸一化的權;πT為目標模型更新的權重閾值，按照式(17)進行目標觀測模型的更新以克服目標狀態的變化。

q(u)t=(1-α)q(u)t-1+αp(u)X[S](17)

其中:q(u)t表示t時刻對應顏色空間第u個特征值更新后的目標顏色模型;p(u)X[S]表示采集到X[S]的對應第u個特征值的目標模型;α為目標模型更新的權重。

d)重采樣

當描述運動狀態方程不是精確目標的運動情況時，粒子權重的方差會隨著時間的推移而不斷增大，小權值的粒子對問題的求解貢獻很小，如果遞推繼續進行下去，大量的計算浪費在這些小權值粒子上，顯然是沒有必要的。對退化程度的大小在文獻[14]中提出有效采樣尺寸的概念，定義為

Neff=N1+var(ω#8226;ik)(18)

其中:ω#8226;ik為第i個粒子的真實權值，一般很難得到，通常采用一種近似估計，即

Neff=1∑Ni=1ωik(19)

其中:ωik表示第i個粒子在第k次迭代的權值(式(2));N為粒子數目。小的Neff意味著大的退化程度，減少Neff的最有效方法是盡量增大采樣的粒子數，但是粒子數的增加是以犧牲跟蹤速度為代價的，所以要采取有效的重采樣方法減少粒子的退化現象。本文通過當Neff小于一定的閾值時，運用折半查找法進行重采樣，同時重置每個粒子的權值為1/N。

3 實驗結果及分析

在本算法實驗中，通過人機交互的方式對被跟蹤目標進行初始化。取粒子數為N=80，其權值初始值為1/N，所有粒子的權值之和為1，每個粒子代表目標的一個可能的運動狀態，即目標的一個可能的位置，模型更新的權值α=0.2，計算目標區域的二階顏色直方圖、初始化卡爾曼濾波器的狀態值和誤差協方差陣。各個部分的參數設置如前所述，隨后在跟蹤過程中，對每個粒子進行狀態轉移，更新粒子權重，所有粒子進行加權以輸出目標狀態的估計值，然后進行重采樣，轉入下一幀。

為了驗證本文提出跟蹤算法的有效性，對不同視頻序列進行了實驗。圖2~6分別給出了80個粒子點的標準基于顏色粒子濾波算法和40個粒子點的本文粒子濾波算法。圖2~4的視頻段共357幀，尺寸為320×240大小的室外拍攝序列，圖2和3中的矩形框表示跟蹤結果。從給出的4幀可以看出，感興趣目標行人即使在發生運動方向改變即旋轉一定角度和粒子數目僅僅是標準粒子濾波算法一半的情況下，仍取得比標準粒子濾波算法較好的跟蹤效果。圖4則給出了在跟蹤過程中目標估計位置區域和目標模板之間的相似程度，相似度值是在0~1分布，相似度值越大代表了跟蹤效果越好，在這個方面也可以表征算法的精度。從圖中可以看出，本文算法在采用較少粒子數目的前提下相似度值同樣達到標準粒子濾波算法的效果，此時，平均跟蹤耗時遠低于標準粒子濾波算法，相似度函數Bhattacharryya系數的變化很好地詮釋了本文算法(PF+Kalman)無論在跟蹤目標的相似程度，還是在計算復雜度上都優于粒子濾波經典算法(PF)。

圖5、6是一段在戶外拍攝的共222幀視頻采樣序列，選擇了117、127和128幀圖片。該序列中跟蹤的汽車顏色與其他汽車顏色相近，周圍不斷地有其他運動汽車影響，在此條件下，進行對目標的跟蹤。從實驗中可以看出，本算法在粒子數目減半的基于顏色信息跟蹤的同時，充分利用目標的空間結構特性，在跟蹤精度上優于傳統的粒子濾波算法。另外，卡爾曼濾波器實質上是一套遞推線性濾波公式，費時少，而每次獲取觀測值都是一步完成，計算量小，并且加入預測后，產生了較為準確的粒子確定性漂移向量，粒子的動態分布更能趨于在目標真實狀態區域附近，大大提高了粒子的利用效率，因此可以用較少的粒子點完成目標跟蹤，同時減少了計算負擔，這比嵌入卡爾曼濾波的耗時是微不足道的。

4 結束語

本文在對傳統的基于顏色的粒子濾波算法分析的基礎上，提出了嵌入卡爾曼預測器的粒子濾波跟蹤算法，對視頻中感興趣目標跟蹤仿真，將仿真結果與經典基于顏色的粒子濾波算法進行比較。結果表明，在非線性強的條件下，本文通過嵌入卡爾曼預測器的粒子濾波跟蹤算法明顯優于傳統的基于顏色粒子濾波算法，也提高了算法的實時性。本文較強的跟蹤特性，為智能視頻監控后續進行計算機高層次的分析提供了保障。但不能忽視粒子濾波固有的退化問題，而且隨著粒子數目增加，系統時間復雜度呈現級數提高，還需要進一步研究。

參考文獻:

[1]PEREC P， VERMAAK J， BLAKE A. Data fusion for visual tracking with particles[J]. Proceeding of the IEEE， 2004，92(3):495-513.

[2]DOUCET A， FREITAS N D， GORDON N. Sequential Monte Carlo in

practice[M]. New York:Springer， 2001:9-19.

[3]ISARD M， BLAKE A. Visual tracking by stochastic propagation of conditional density[C]//Proc of the 4th European Conference on Computer Vision.Cambridge:[s.n.]， 1996: 343-356.

[4]DOUCET A，GODSILL S，ANDRIEU C. On sequential Monte Carlo sampling methods for Bayesian filtering[J]. Statistics and Computing， 2000，10(3):197-208.

[5]GORDON N J， SALMOND D J， SMITH A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J]. IEEE Proceedings Fin Radar and Signal Processing， 1993，140(2):107-113.

[6]CHENG Chang， ANSARI R. Kernel particle for visual tracking[J]. IEEE Signal Processing Letters， 2005， 12(3):242-245.

[7]NUMMIARO K， KOLLER-MEIER E， GOOL L van. An adaptive color-based particle filter[J]. Image and Vision Computing， 2003，21(1):99-110.

[8]張笑微，師改梅，周建雄，等. 結合顏色和結構信息的粒子濾波跟蹤算法[J].光電工程， 2008， 35(10):1-6.

[9]高建坡，韋志輝，孟迎軍，等. 基于均值移動確定性漂移的改進CONDENSATION人臉跟蹤[J].光電工程， 2009， 36(2):137-142.

[10]YU Dan， WEI Wei， ZHANG Yuan-hui. Dynamic target tracking with Kalman filter as predictor[J]. Opto-Electronic Engineering， 2009，36(1):52-56.

[11]BIRCHFIELD S T， RANGARAJAN S. Spatiograms versus histograms for region-based tracking[C]//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington DC:IEEE Computer Society，2005:1158-1163.

[12]COMANICIU D， RAMESH V， MEER P. Real-time tracking of non-rigid objects using mean shift[C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ:IEEE Compu-ter Society，2000:142-149.

[13]邊肇祺，張學工. 模式識別[M].北京:清華大學出版社，1999.