基于卡爾曼粒子濾波框架的魯棒多人跟蹤算法

陳健虞，劉 闊，湛永松

（桂林電子科技大學 廣西高校圖像圖形智能處理重點實驗室，廣西 桂林541004）

0 引 言

近年來，視頻目標跟蹤技術在智能監控系統、人機交互和增強現實等領域獲得了廣泛應用。作為視頻中的一種重要檢測目標，行人的檢測與跟蹤技術獲得了學者們的廣泛關注，成為計算機視覺領域的一個熱點研究方向，也在近年取得了不斷的進步，如基于梯度方向直方圖 （histogram of oriented gradient，HOG）［1，2］特征的行人檢測方法。但是，由于行人之間存在相互遮擋、背景遮擋現象及復雜場景中易于發生光照劇烈變化的問題，如何開展魯棒的多人跟蹤成為了廣大研究者們面臨的一個難題。

目前常用的行人跟蹤方法主要分為兩類。①數據關聯方法。該方法需要將整個視頻分析一遍，檢測出行人在每一幀圖像中的位置信息，然后通過觀測模型匹配計算相似度，將同一個行人的位置信息關聯起來得到行人的運動軌跡。其中，觀測模型需要預先定義［3，4］，或通過在線學習以區分各個行人。如Huang 等［5］提出了分層的數據關聯方法，第一層根據視頻相鄰幀行人位置信息構建短跟蹤片段，第二層由外觀模型匹配關聯短跟蹤片段形成長跟蹤片段，以得到各個行人的運動軌跡。該方法雖然能有效解決目標長時間遮擋的問題，但無法滿足實時性要求。②邊檢測邊跟蹤方法。該方法首先對視頻進行行人檢測，提取相關特征作為參考目標模型，然后初始化跟蹤器并進行持續跟蹤。其中，常用的跟蹤器算法有均值漂移算法 （mean shift）［6］和粒子濾波算法 （particle filter）［7－9］。由于粒子濾波能有效解決行人的非線性非高斯性運動，成為近年的研究熱點，獲得了廣泛的應用。傳統粒子濾波算法主要以顏色特征作為觀測模型，通過計算顏色直方圖相似度來區分各個行人及背景。而顏色特征只是簡單統計某一像素區間內像素的個數，在相似顏色、光照變化及遮擋的影響下，像素值會發生明顯的變化，觀測模型也會隨之發生變化，從而導致跟蹤準確性不高。相入喜等［10］提出多特征融合的粒子濾波跟蹤算法，對相似顏色干擾及部分遮擋有較高的魯棒性，但仍然無法解決完全遮擋及光照劇烈變化條件下出現的問題。

本文基于前人的研究成果，結合個人的創新，提出一種基于卡爾曼粒子濾波框架的魯棒多人跟蹤算法。該算法以粒子濾波為基礎，引入卡爾曼濾波以解決行人相互遮擋或背景遮擋問題。此外，為了克服單一特征的局限性，算法所使用的觀測模型中融合了顏色、紋理特征，并提出改進的顏色特征以解決光照劇烈變化導致跟蹤精度不高的問題，最終實現了在完全遮擋及光照劇烈變化情況下魯棒的多人跟蹤。

1 算法總體框架

基于卡爾曼粒子濾波框架的多人跟蹤算法主要包含4個模塊：①行人檢測。該模塊是行人跟蹤的前提條件，其目的是從序列圖像中將變化區域的行人從背景圖像中進行提取；②粒子濾波。用若干個粒子來表示每個行人的狀態，包括位置、速度和加速度等，同時給每個粒子賦予一個權值，表示與行人模板的似然概率，這些粒子的加權平均值則表示被跟蹤行人的當前狀態；③觀測模型。該模型采用改進顏色和紋理特征相結合的方法，給出每個粒子的似然概率計算方法；④卡爾曼濾波。該模塊主要包括兩個階段，首先是預測階段：濾波器根據先前時刻行人狀態向量，對當前每個粒子狀態做出估計；其次是更新階段：濾波器利用對當前狀態的觀測值 （即加權粒子的期望值）優化在前一階段獲得的預測值，以獲得一個更精確的新估計值。

圖1顯示了本文算法的總體框架，包含7個步驟：

（1）待檢測的圖像序列中，在運動前景區域應用行人檢測算法。

（2）如果當前檢測到的行人沒有被跟蹤，則重新提取外觀特征模型，并初始化跟蹤該行人的粒子。否則，根據上一幀估計結果更新粒子分布，用于當前幀的估計。

（3）將顏色直方圖及局部二值模式 （local binary patterns，LBP）紋理直方圖兩種互補性特征融合于本文算法框架中，用于表示每個粒子的觀測模型。

（4）將各個粒子的顏色及紋理特征分別與外觀模型進行相似度計算，融合兩種似然概率，得到各個粒子的似然概率。

（5）將融合得到的似然概率與預先設定的閥值進行比較，判斷是否存在遮擋。若存在遮擋則利用卡爾曼濾波預測估計行人狀態向量，否則直接利用似然概率估計得出行人狀態向量。

（6）將行人相應所有粒子狀態向量的加權平均作為其在當前時刻的狀態向量估計，即該行人的跟蹤結果。

（7）為解決粒子權重退化問題，重新抽取權值高的粒子作為新的粒子，并循環處理視頻下一幀。

圖1 本文算法框架

2 行人檢測

本文算法中，所采取的是基于HOG 特征與支持向量機 （support vector machine，SVM）［11］相結合的行人檢測技術。作為目前廣泛應用的行人檢測方法，HOG 能夠較好地表征圖像局部邊緣梯度方向和梯度強度分布特性；SVM 則在解決小樣本、非線性和高維模式識別問題中具有許多特有的優勢。具體操作可參考文獻 ［11］。

3 跟蹤算法

在傳統粒子濾波跟蹤算法中，首先提取目標特征作為外觀模型，然后在上一幀得到的目標附近按照高斯分布投放大量的粒子，并計算每個粒子區域的特征，與外觀模型進行比較，每個粒子位置的加權和即為目標所在當前幀的位置。雖然傳統粒子濾波跟蹤算法在目標平面旋轉、非剛體以及部分遮擋等方面有較好性能，但在目標完全遮擋情況下，其無法準確提取目標特征直方圖，造成特征比較失效，導致出現跟蹤偏離。為了有效克服行人完全遮擋的影響，本文基于傳統粒子濾波算法，并引入卡爾曼濾波預測估計，以解決遮擋后不能精確跟蹤的問題。

3.1 粒子濾波算法

該算法是通過采用遞歸蒙特卡羅采樣狀態估計實現的，其主要思想是使用粒子分布的密集程度來近似表示概率分布，并通過計算粒子加權平均，以獲得狀態最小方差估計的過程。

根據貝葉斯定理，采用粒子加權平均值作為行人的最終跟蹤結果，如式 （2）所示

但是，當出現完全遮擋情況時，每個粒子的權值并不能真實反映其與目標模型的相似度，容易導致跟蹤失敗。為此，本文通過引入卡爾曼粒子濾波算法來解決目標完全遮擋所帶來的問題。

3.2 卡爾曼粒子濾波算法

當目標行人完全被遮擋后，粒子濾波跟蹤器無法獲得關于行人的任何特征信息。因此，僅由粒子濾波算法估計獲得的狀態向量可靠性不高，必須采用一定的策略來估計當前狀態向量。在解決這個問題之前，首先需要獲取遮擋發生的時間。設P（b）為當前目標模板特征直方圖，Q（b）為當前最優估計位置的特征直方圖，計算巴氏距離d（P，Q）。當d 大于預先設定的閥值T 時，表明目標行人存在一定的遮擋。

確定了遮擋發生的時間后，再采用卡爾曼濾波估計最優狀態向量。首先，對當前卡爾曼預測狀態進行確定，如式 （3）所示

式中：x——目標先前幀的狀態向量。

然后，根據先前誤差協方差獲取當前誤差協方差，如式 （4）所示

式中：Q——系統誤差協方差矩陣。根據式 （4）可得到卡爾曼增益矩陣，如式 （5）所示

式中：R——觀測噪聲協方差；H 描述了觀測矩陣。

最后，將上述式 （2）計算得到的粒子濾波最優估計作為卡爾曼濾波測量值＾Zk，則基于卡爾曼粒子濾波的最優估計狀態可表示為式 （6）

誤差協方差可更新如式 （7）所示

4 觀測模型及相似度計算

傳統視頻圖像序列跟蹤中，通常需要提取目標特征作為觀測模型，如顏色、形狀和紋理等特征。目標跟蹤過程實際上就是對狀態預測值進行更新的過程，而更新則首先要計算觀測模型和粒子之間的相似度，其中每個粒子表示當前目標狀態的一個可能值，相似度越高粒子的權值越大，相反權值越小，系統觀測就是為了給與真實目標相近的粒子分配較大的權值，而與真實目標相差較大的粒子分配較小的權值。

4.1 顏色特征

作為常用的外觀特征，顏色特征經常應用于視頻目標跟蹤的外觀模型提取，該特征實現方法簡單，計算時間復雜度低，且能有效克服平面旋轉、非剛體和部分遮擋等問題。

4.1.1 傳統顏色特征

顏色直方圖是被廣泛采用的顏色特征提取方法，其所描述的是某一顏色區間中像素的個數占總像素的比例。常用的直方圖顏色空間為HSV，H 表示色調，S 表示飽和度，V 表示高度分量。顏色直方圖的計算方法為：首先，對顏色范圍進行等量劃分，每一個分量表示一個bin （直方圖區間）；然后，統計顏色在每個分量中的像素數量，以得到顏色直方圖。將直方圖總區間表示為B＝bhbsbv，則矩形區域S 的顏色直方圖可表示為式 （8）

式中：W——目標區域中像素的個數；δ——狄拉克函數；I（xi）——像素xi的亮度值；b——直方圖區間bin。

雖然顏色特征具有很多優點，但其并不包含每種色彩所處的空間位置信息；此外，若光照劇烈變化，會導致直方圖變化明顯，影響跟蹤效果。為此，本文提出一種改進的顏色特征，以解決光照劇烈變化帶來的問題。

4.1.2 改進的顏色特征

為解決不同光照條件對目標外觀產生較大影響的問題，本文所提出的改進的顏色特征充分考慮了所有像素對中心像素的貢獻，具有光照不變特征，其基本原理是將原始圖像轉化為一張不隨光照變化影響的新圖像。

假設光照的變化呈線性關系，每一個像素的亮度都會相應變大或變小，同時該像素所在直方圖區間bin也會隨之改變，但像素變化的個數保持恒定。例如：假設像素x0從所在的直方圖區間bin1變換到區間bin2，則具有相同亮度值的像素xi也會從bin1變換到bin2，即光照變化前的bin1約等于光照變化后的bin2。

為使位于行人目標中央的區域有較高權值，可對顏色直方圖每一區間引入加權計算，則以x0為中心的行人目標區域歸一化直方圖可定義如式 （9）

由于真實世界中的光照變化是不均勻的，為了充分考慮所有像素對中心像素的貢獻，可同時通過引入高斯函數以減少量化誤差。因此，針對像素x，其光照不變特征可用式 （10）求取

式中：Hx（b）由式 （9）計算得到，表示以像素x 為中心的加權直方圖；σ——尺度因子。

圖2直觀地描述了該改進顏色特征的光照不變特征。其中，第一行為原圖像，其對應像素的亮度各不相同；第二行為經過光照不變特征處理的新圖像。顯然，新圖像不受光照變化影響。

圖2 光照不變特征

4.2 紋理特征

由于顏色特征無法體現每種色彩所處的空間位置信息，在視頻目標跟蹤過程中，可通過目標的紋理信息來捕獲物體空間的有效特征。因此，本算法在顏色特征基礎上融入紋理特征，以消除相似背景顏色的影響。

紋理特征提取可采用局部二值模式 （local binary patterns，LBP）方法完成。該方法的原理是：首先構建一個大小為3×3的模板，針對每一個像素，若該模板邊緣位置對應像素的值大于模板中心像素的值，則該位置賦值為1，反之賦值為0。然后按照順時針順序提取，進而得到一個二進制數。最后將得到的二進制數作為該中心像素的顏色值，以生成相應的紋理特征，如式 （11）所示

4.3 相似度計算

為計算粒子的觀測值，通常采用巴氏距離來度量兩個直方圖之間的相似性。根據前述討論，將各粒子所在的區域作為候選目標區域，可獲得候選目標模型Pj＝｛（xj）｝。其中，i表示第i個特征，j表示第j 個粒子；b表示直方圖區間；xj表示中心位置。參考目標模型（y）和候選目標子模型（xj）的相似度可用式 （12）求取

對于多個觀測特征，可對各子模型相似度進行加權混合，從而計算獲得總的直方圖相似度，如式 （13）所示

粒子的觀測值可通過式 （14）求取

5 實驗結果與分析

算法時間復雜度分析：考慮有k 個行人需要跟蹤，每個行人分配的粒子數為N，每個粒子特征數為Nt，視頻幀寬度為W，高度為H。為提高效率，紋理及顏色特征直方圖采用積分直方圖方式計算。跟蹤算法主要計算復雜度為：轉移矩陣O（kNN2t），計算積分直方圖O（WHNt），粒子特征向量、相似度計算均為O（kNNt），總體復雜度為：O（kNN2t）。其中N＝80，W ＝320，H＝240，Nt＝2。對于幀率為30fps的視頻，目前的主流CPU 可以實時完成該數量級的運算，若采用GPU 加速以及并行運算，則效果能進一步提升。

圖3和圖4分別為背景遮擋和相互遮擋情況下的跟蹤結果，各圖的第一行表示傳統粒子濾波算法的跟蹤結果，第二行表示本文算法的跟蹤結果。如圖可見，當行人完全遮擋后 （如圖3 第120、132、186 幀、圖4 第292、337、380幀），由于粒子無法獲取關于行人的任何信息，傳統粒子濾波算法無法有效持續跟蹤。而本文引入了卡爾曼濾波算法，通過預測估計下一幀行人所在的位置，有效消除了遮擋的影響，因此仍能夠進行很好跟蹤。

圖3 背景遮擋情況下跟蹤結果 （第一行為傳統粒子濾波算法結果；第二行為本文算法結果）

圖4 目標相互遮擋情況下跟蹤結果 （第一行為傳統粒子濾波算法結果；第二行為本文算法結果）

圖5給出了光照劇烈變化情況下的跟蹤結果，其中第一、第二行分別為傳統算法和本文算法的跟蹤結果。如圖可見，當出現明顯光照變化后 （如圖第352、376 幀），基于傳統算法的跟蹤出現偏離現象，而由于本算法所提出的改進顏色特征具有良好的光照不變性，在環境光照劇烈變化條件下，仍能夠保持準確跟蹤。

圖7給出了光照變化情況下的傳統顏色特征直方圖和本文所提出的改進顏色特征直方圖。如圖所示，傳統顏色特征直方圖在光照變化前后的分布變化明顯，而改進的顏色特征直方圖在光照變化前后無明顯變化，充分驗證了本文提出的改進顏色特征具有較好的光照不變性。

圖5 光照劇烈變化情況下跟蹤結果 （第一行為傳統算法結果；第二行為本文算法結果）

表1 背景遮擋跟蹤誤差

表2 相互遮擋跟蹤誤差

圖6 兩種遮擋情況誤差對比（X 軸表示視頻序列，Y 軸表示跟蹤誤差比率）

圖7 光照變化前后顏色特征直方圖（X 軸為直方圖區間bin，Y 軸為像素個數）

6 結束語

本文以粒子濾波為基礎，提出一種基于卡爾曼粒子濾波框架的魯棒多人跟蹤算法，在出現目標遮擋時采用卡爾曼濾波估計目標位置，從而提高跟蹤精度；改進觀測模型，通過計算光照不變特征以解決光照劇烈變化問題。實驗結果表明，該算法較傳統算法具有更優性能，在完全遮擋及光照劇烈變化情況下能夠準確跟蹤目標，魯棒性更強。

在下一步工作中，將著重通過并行計算技術優化算法效率，以減少算法計算時間，同時探索將算法集成到實際應用系統中。

［1］Leng Bin，He Qing，Xiao Hanzhang，et al.An improved pedestrians detection algorithm using HOG and ViBe［C］／／IEEE International Conference on Robotics and Biomimetics，2013：240－244.

［2］Soojin Kim，Kyeongsoon Cho.Trade－off between accuracy and speed for pedestrian detection using HOG feature ［C］／／IEEE 3rd International Conference on Consumer Electronics－Berlin，2013：207－209.

［3］Pirsiavash H，Ramanan D，Fowlkes CC.Globally－optimal greedy algorithms for tracking a variable number of objects［C］／／IEEE Conference on Computer Vision and Pattern Recognition，2011：1201－1208.

［4］Xing J，Ai H，Lao S.Multi－object tracking through occlusions by local tracklets filtering and global tracklets association with detection responses ［C］／／IEEE Conference on Computer Vision and Pattern Recognition，2009：1200－1207.

［5］Kuo CH，Huang C，Nevatia R.Multi－target tracking by on－line learned discriminative appearance models［C］／／IEEE Conference on Computer Vision and Pattern Recognition，2010：685－692.

［6］WANG Lu，YANG Linyun，ZHUO Qing，et al.Illumination robust Mean－Shift tracking ［J］.Computer Application，2008，28 （7）：1672－1674 （in Chinese）.［王路，陽琳赟，卓晴，等.光照魯棒的Mean－Shift跟蹤方法 ［J］.計算機應用，2008，28（7）：1672－1674.］

［7］YUAN Guanglin，XUE Mogen，XIE Kai，et al.Kernel－based particle filter for target tracking with adaptive multiple features fusion ［J］.Journal of Computer Aided Design ＆ Computer Graphics，2009，21 （12）：1774－1784 （in Chinese）. ［袁 廣林，薛模根，謝愷，等.基于核函數粒子濾波和多特征自適應融合的目標跟蹤 ［J］.計算機輔助設計與圖形學學報，2009，21 （12）：1774－1784.］

［8］Kumar A，Mishra SK，Dash PP.Robust detection ＆tracking of object by particle filter using color information ［C］／／4th IEEE Conference on Computing，Communications and Networking Technologies，2013：1－6.

［9］Chu Hongxia，Xie Zhongyu，Nie Xiangju，et al.Particle filter target tracking method optimized by improved mean shift［C］／／IEEE Conference on Information and Automation，2013：991－994.

［10］XIANG Ruxi，LI Jianwei.Particle filter tracking algorithm of multiple features adaptive fusion ［J］.Journal of Computer Aided Design and Graphics，2012，24 （1）：97－103 （in Chinese）.［相入喜，李見為.多特征自適應融合的粒子濾波跟蹤算法 ［J］.計算機輔助設計與圖形學報，2012，24 （1）：97－103.］

［11］Liu Yucheng，Liu Yubin.Incremental learning method of least squares support vector machine［C］／／IEEE Conference on Intelligent Computation Technology and Automation，2010：529－532.