基于粒子濾波和在線訓練支持向量機的目標跟蹤新方法

摘要：序列圖像中運動目標跟蹤的有效性和魯棒性是一個非常富有挑戰性的課題。為提高在運動背景條件下視覺目標跟蹤的性能，克服復雜環境對跟蹤算法準確性的影響，提出了一種基于粒子濾波和在線訓練支持向量機的目標跟蹤新方法。從目標的特征描述和提取著手，引入了積分直方圖快速提取特征的方法，加快粒子濾波器運行速度，滿足一定的實時性要求。同時，分析了運動背景條件下具有代表性的跟蹤算法的本質和特性，結合目標識別創新性地提出在線訓練支持向量機的方法，通過在線識別信息和跟蹤信息的融合保證算法具備較強的魯棒性。實驗結果表明，該算法能有效的解決動態背景條件下遮擋、光照變化和運動模糊等復雜情況下，對目標進行準確、有效、近乎實時的跟蹤。

關鍵詞：目標跟蹤；粒子濾波；支持向量機；積分直方圖

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)32-1190-04

New Target Tracking Algorithm Based on Particle Filter and On-line Training Support Vector Machines

ZHENG Jian-bin

(School of Software Engineering，Tongji University， Shanghai 201804， China)

Abstract: It is a challenging task to track the object effectively and robustly in sequence image. In order to improve the performance of target tracking under moving background circumstance， and get over the influence of veracity of tracking algorithm under intricate conditions， This paper presents a new target tracking algorithm based on particle filter and on-line training support vector machines. This paper begins with object feature description and extraction; introduce some quick feature extraction ways to improve the speed of particle filter， thus achieving almost real-time performance. Meanwhile we discusses essence and speciality ofsome classical object tracking algorithms under moving background circumstance， we also guarantee the robustlyof the new algorithm by combining the classification information which from online-training Support Vector Machine and the tracking information. Experiments proved the new algorithm can deal with intricate conditions， such as occlusion， luminance changing， and abrupt motion blur happen， and track objects accurately， effectively and real time.

Key words: target tracking; particle filter; support vector machines; integral histograms

1 引言

序列圖像中進行運動目標的跟蹤是計算機視覺中一個必不可少的關鍵技術，一直以來備受人們關注。目標跟蹤技術被廣泛用于軍事、科技、工程和經濟等多個領域。然而目標跟蹤檢測存在兩大難點：其一是觀測模型和目標的概率分布的非線性和非高斯性，其二是遮擋和模糊現象。最常用的序列圖像目標跟蹤多采用卡爾曼濾波。雖然先后出現了廣義卡爾曼濾波(EKF)和無跡卡爾曼濾波(UKF)，但都因為他們不能對實際非線性函數或概率分布進行精確的描述，或是要求目標狀態必須滿足高斯分布而導致對于復雜背景或是有遮擋等造成的非高斯和非線性問題的性能表現不佳。另一種常用的非線性濾波方法是粒子濾波(Particle Filter，簡稱PF)[1]。該方法根據目標性質所生成的概率統計來跟蹤目標，而不受場景中具有相似性質的其它物體運動的影響。因而被廣泛應用到航空導航、機器學習和視頻監控等領域。除計算量大而導致實時性能差外，樣本貧化現象是PF的最大缺點。減輕該缺陷影響的最簡單方法是加大樣本集，但這將降低系統的實時性能。

本文針對PF的實時性差和樣本貧化提出了基于粒子濾波和在線訓練支持向量機的目標跟蹤新方法。該方法將在線訓練支持向量機(SVM)和粒子濾波相結合，從而獲取目標的識別和跟蹤信息的聯合數據分布圖，并采用積分直方圖方法進行快速的目標區域的直方圖提取。大量的實驗表明，該方法在保持了原有跟蹤魯棒性的前提下，很好的解決了樣本退化問題和不佳的實時性能，同時在出現遮擋和模糊復雜情況下也具有非常良好的魯棒性。

2 粒子濾波

粒子濾波是貝葉斯估計基于抽樣理論的一種近似算法，它將蒙特卡羅和貝葉斯理論結合在一起。其基本思想是用一組帶有相關權值的隨機樣本的加權和來表示后驗概率[2]。當樣本數目非常大時，這種概率估計將等同于后驗概率密度。其運作過程描述如下：

其中，權值wjk通過重要采樣法，從重要密度函數q(Xk|Z1:k)中采樣選擇。如果樣本Xjk可以由重要密度q(Xk|Z1:k)取得，則第i個粒子的權值可以定義為：

如果重要密度函數可以做如下的分解：

q(Xk|Z1:k)=q(Xk|Xk-1，Z1:k)q(Xk-1|Z1:k-1)

若滿足q(Xk|Xk-1，Z1:k)=q(Xk|Xk-1，Zk)，即重要密度函數僅依賴于Xk-1和Zk，則只需存儲樣本Xik，而不需要存儲樣本Xik-1及過去的觀測值Z1:k-1，從而可以極大地減少計算存儲量。

此時權值修正為：

所以，粒子濾波算法主要是由重要密度函數獲取樣本，并隨著測量值的依次到來迭代求得相應的權值，最終以其加權和的形式表征后驗概率密度，得到狀態的估計值。

3 特征選取

3.1 Haar特征

Haar型特征是P．Viola 在文獻[3]中提出的一種簡單矩形特征，因類似于Haar小波而得名。Haar型特征的定義是黑色矩形和白色矩形在圖像子窗口中對應的區域的灰度級總和之差，它反映了圖像局部的灰度變化。這些特征原形在x和Y方向獨立的縮放整數倍數，組成新的特征，一直放大x和Y方向到24。每一個特征在窗口每一個位置計算。故如此多的特征數對采樣很多的局部區域時效率是很低的。好的特征選取方法是分類的關鍵，本文引入了積分直方圖快速提取特征的方法。

3.2 積分直方圖算法

對于Haar小波特征的來說，Viola等在文獻[3]中提出的積分圖已經被證明為切實有效的快速提取算法。而本文所提的積分直方圖算法是基于積分圖算法的而提出的。以下加以說明：

首先建立全局的積分直方圖，即對于一定區域內的全局目標建立直方圖的累加直方圖，建立方法同文獻[1]中的積分圖建立方法，只需要將灰度值的總和換成需要的直方圖的特征級數的總和，直方圖的類型可以是上文敘述的多種中的某種，然后在計算局部區域的特征時采用積分圖中使用的查找表的方法，通過簡單的加減方式就可以得到目標區域的直方圖。這種方法在一張較大的圖像上需要采樣很多的局部區域時具有非常明顯的節約計算時間的優勢，因為只要計算一次全局的積分直方圖之后便可以通過查找的方式得到每一個圖像中的局部細節的直方圖。

積分直方圖建立查找表快速提取直方圖的方法的如下：

1）對于全圖或者目標周圍區域建立積分直方圖，將積分直方圖存入內存中。

2）確定目標的區域，在內存中積分直方圖中查找得到使用四塊矩形區域的內存位置

3）通過四塊矩形區域的加減運算得到目標區域的直方圖。

利用該方法，粒子濾波器的抽樣特性便能迅速地提取所抽樣的目標區域的直方圖。

3.3 基于主成分分析方法的特征降維

特征提取的目的是希望通過變換把原來的特征變換到新的特征空間，使得特征的可分性更好。提取特征后希望能對原始特征進行降維壓縮，用盡量少的數據來表示盡量多的信息，在保證特征數據不失真的前提下起到減少計算量的作用。本文采用主成分分析方法[4] (Principle Component Analysis ，PCA)，數據壓縮和降維中的一種最優正交變換，是一種基于目標統計的方法。其目的是基本思想是通過變換，將實測的多個指標，推導出新的變量，用新的潛在的相互獨立的變量線性組合來表示原多個實測指標的主要信息。這些新的變量成分按重要性降序排列，是原始變量的線性組合而且互不相關，當使用這些新變量去重建原始變量時使得均方誤差最小。這就導致了用較少維數的近似表示原來的對象，起到數據降維的效果，以此在特征的提取階段產生時間上的優勢。

利用主成分分析的方法提取目標特征的步驟如下：

首先，設xi為初步得到的目標的特征參數，共有p個，記為X(x1，x2，…，xp)；

其次，計算X的協方差矩陣∑，計算∑的特征值及相應的正交單位化特征向量分別為：λ1≥λ2≥λ3≥，…λp≥0和e1，e2，e3，…ep。

本文進行特征降維時使用將得到的原始特征值進行壓縮，使得降維后的數據滿足跟蹤算法的實時性需要。

4 在線訓練支持向量機

4.1 支持向量機

在20世紀90年代，統計學理論的創立人之一，ATT 實驗研究中心的Vapnik創立了支持向量機(SVM)學習理論[5]。它是一種分類器，和傳統的分類器如神經網絡相比，它從理論上解決了神經網絡難以控制自身推廣能力的問題。SVM是統計學習理論中最年輕，也是最實用的部分，正處于發展階段。

支持向量機的基本思想是通過非線性變換將輸入空間的變換到一個高維的特征空間，然后在這個新的高維特征空間中求取最優分類超平面。所謂最優分類超平面就是要求分類線不能將兩類樣本無錯誤的分開，而且要使兩類之間的距離最大。設線性可分樣本集為(xi，yi)， i=1，2，…，n， x∈Rd， y∈{+1，-1}是類別標號。SVM的判別函數(分類器)表達式為：

式中：k(xi·x)為核函數，用以實現非線性變換，常用的核函數有以下幾種:

1）線性內積函數K(x，y)=x·y

2）多項式內積函數K(x，y)=[(x·y)+1]d

3）徑向基內積函數K(x，y)=exp{-|x-y|2/σ2 }

4）二層神經網絡內積函數K(x，y)=tanh(k(x·y)+c)

ai為每個樣本對應的Lagrange系數。兩類樣本中離分類面最近的點且平行于最優分類面的超平面上的訓練樣本就稱為支持向量(Support Vectors)，即少量不為零的ai對應的樣本xi，將最終影響劃分結果。

由于SVM本質上是一個非負的二次型優化問題，在理論上可以得到全局最優解，因此SVM不存在局部最優化問題。另外，SVM的重要特征之一就是解的稀疏性，即需要少量樣本就可以構成最優分類器，這使得有用的樣本數據將大大壓縮。因此，支持向量機在解決小樣本、非線性及高維模式識別問題中表現出許多特有的優勢，并且能夠推廣到函數逼近和概率密度估計等其他機器學習問題中。本文采用Platt提出的SMO(Sequential Minimal Optimization)算法訓練SVM。

4.2 在線訓練

在線訓練和識別信息的跟蹤思想是階段目標跟蹤鄰域內研究的熱點，通過分類器訓練跟蹤過程中的目標模板，一方面提供實時的數據更新，另外能為跟蹤過程提供識別和檢測的信息，使得跟蹤中目標分布獲取更為真實可信。

本文在傳統支持向量機離線訓練跟蹤目標的基礎上，提出了在線訓練這一思想。采用C-SVM算法對目標特征數據進行在線訓練，其訓練流程如圖1所示。

通過在線的訓練分類器，可以不斷的對于目標模板的識別進行更新，另外也可以為跟蹤提供識別的打分依據，最終要的是通過不斷的訓練和在線的更新模板在時間序列中不斷自適應變化，使得算法在目標處于光照變化，復雜背景干擾等情況下能夠繼續穩定地運行。

5 基于粒子濾波和在線SVM目標跟蹤算法

5.1 算法設計流程

本文提出了一種基于在線識別和訓練的動態背景下的目標跟蹤算法是稱為基于粒子濾波和在線SVM的目標跟蹤算法。所使用的方法和工具包括前面介紹和分析的積分直方圖，主成分分析降維，粒子濾波器算法，支持向量機等。

整個跟蹤算法的設計分析如下:

首先，假設已經得到了需由此查找得到各個抽樣目標區域的直方圖，通過特征提取和降維獲取候選目標的特征，對于每個抽樣目標運行支持向量機進行判別，給出正負打分和其類屬。將上述兩個打分分布進行聯合，獲取一個聯合分布，作為粒子濾波器的粒子加權，然后結合加權的粒子位置給出目標在本幀中的最終區域。

在此過程中，每隔一定幀數對于支持向量機進行訓練更新，獲得更新好的支持向量，用于模板的更新和提供更為適合當前條件的識別打分。要跟蹤目標的初始位置，完成了各類初始化工作，從圖像或視頻序列的第一幀開始運行整個算法。

然后對于該初始位置運行粒子濾波器進行隨機抽樣，計算目標區域周圍的積分直方圖。最終將得到識別和跟蹤信息的聯合數據分布，從而對目標模板進行更新，進而通過粒子加權獲取目標定位。整個算法的流程設計如圖2所示。

5.2 識別和跟蹤信息的融合

支持向量機，也就是使用的分類器其實給出的定量判斷數據是對于當前得到的目標樣本的打分，該打分體現了樣本近似某一類物體的程度，所以當跟蹤中的特征由于算法不魯棒等情況出現位置偏移真實目標不能提供準確目標信息時，識別的打分給出一個反饋，告訴跟蹤系統當前的目標位置出現異常、偏離。所以融合跟蹤中的目標信息和識別檢測的打分信息，對于提高跟蹤算法的魯棒性極為重要。

基于粒子濾波和在線SVM的目標跟蹤算法的設計思路是利用了支持向量機對于目標的打分分布來實現的，注意到了支持向量機在給出目標識別判斷的同時給出了一個定量的識別打分，該打分為正值和負值時分別說明目標的兩類所屬，打分越大說明目標越“像”某類物體。在此處利用了該打分原理，將其改造為結合了粒子濾波器的觀測概率分布的一個聯合分布，在跟蹤的過程中加入了檢測和識別的信息，使得目標的觀測分布更為合理準確。

具體的方法為是將所有的粒子候選目標的SVM打分進行歸一化處理，通過如下公式使其成為(0，1)范圍內的分布：

其中SvmSco[i]為各個粒子的支持向量機原始打分，SvmMin為其中的最小打分，SvmMax為最大值，λ為經驗系數，這里選取7。

然后使用如下公式了來對于各個目標的SVM打分和粒子濾波的特征加權系數進行統一：

其中，SvmSco[i]為各個粒子的支持向量機歸一化打分，TempHist[i]為模板的直方圖打分，PtlHist[i]為粒子的直方圖打分，經過試驗測試，當經驗系數取20時，色彩直方圖的打分和SVM的打分能在算法中發揮最佳的效果，使其既包含了跟蹤信息，又包含了檢測和識別的信息。

通過在線識別信息和跟蹤信息的融合保證算法具備較強的魯棒性。

6 實驗結果

本實驗主要觀測和分析基于粒子濾波和在線訓練SVM目標跟蹤算法的跟蹤性能。本文在同一硬件系統和相同粒子數目條件下，分別對傳統粒子濾波器和本文完成的算法，針對實時性和跟蹤的魯棒性做了測試。測試的結果如圖3，圖4和圖5所示。

由圖3可見，本文的算法在訓練的間隔能穩定在每秒12到14幀。本文的算法的實時性基本達到視頻目標跟蹤可以接受的速度，相對于傳統的粒子濾波算法每秒4到6幀的速度，本文結合在線檢測和識別的設計有了較大的改進，滿足了實時性要求。

圖4是目標真實運動軌跡、本文算法跟蹤軌跡和傳統PF算法跟蹤軌跡的對比圖。如圖所示，傳統PF雖然跟蹤效果也不錯，但隨著時間的推移產生了一定的漂移，而本文算法卻始終能準確的跟蹤到目標。

圖5給出了部分圖片的檢測結果。跟蹤目標為一輛轎車，方框區域為使用算法得到的目標的位置。其中綠色方框為本文算法，紅色方框為標準粒子濾波算法的。結果表明本文算法具有較強的魯棒性，對于不同的復雜場景都具有較強的適應性。

從實驗結果看，因為只要計算一次全局的積分直方圖之后便可以通過查找的方式得到每一個圖像中的局部細節的直方圖，故明顯提高了算法的實時性能。同時將跟蹤中的目標信息和識別檢測的打分信息相融合，使算法在復雜背景下的跟蹤性能更具魯棒性。

7 結論

本文提出了一種基于粒子濾波和在線訓練SVM的目標跟蹤算法，該算法能夠在一些復雜條件下對目標進行準確、有效、實時的跟蹤。實驗結果表明，該算法可以較好的適應光線變化、被部分遮擋或色彩質量很差等復雜背景條件下的圖像序列中的目標跟蹤，改善了標準粒子濾波算法的局限性，提高了跟蹤算法的魯棒性。

參考文獻：

[1] PACHTER M，CHANDLER P R. Universal Linearization Concept for Extended Filters[J].IEEE Trans on Aerospace and Elec-Tronic System，1993，29(3):946-961.

[2] Doucet A， Freitas J F G， Gordon N J. An introduction to sequential Monte Carlo methods，in Sequential Monte Carlo Methods in Practice[C].New York:Springer-Verlag，2001.

[3] Viola P， Jones M. Rapid Object Detection using a Boosted Cascade of Simple Features[A]. In: IEEE Proceedings International Conference on Computer Vision and Pattern Recognition， Hawaii， USA， 2001:511-518.

[4] Keren T， Chen S C. Adaptively weighted sub-pattern PCA for face recognition[J]. Neurocomputing， 2005，(64):505-511.

[5] Richard O， Duda Peter E. David G. 模式分類[M].2版.李宏東，姚天翔，譯.北京：機械出版社，2003.