基于改進的顏色和SURF特征的粒子濾波目標跟蹤

金志剛，衛津津，羅詠梅，劉曉輝

1.天津大學電子信息工程學院，天津300072

2.天津大學計算機科學與技術學院，天津300072

3.國家計算機網絡應急技術處理協調中心，北京100029

基于改進的顏色和SURF特征的粒子濾波目標跟蹤

金志剛1，衛津津1，羅詠梅2，劉曉輝3

1.天津大學電子信息工程學院，天津300072

2.天津大學計算機科學與技術學院，天津300072

3.國家計算機網絡應急技術處理協調中心，北京100029

針對視頻中運動目標的準確跟蹤問題，提出了一種改進的顏色直方圖特征和SURF特征的粒子濾波跟蹤算法。采用SURF算法提取特征點，利用分層迭代的KLT算法對特征點進行穩定跟蹤。將SURF特征與改進的視覺顯著性顏色特征進行乘性融合，作為粒子濾波的觀測概率。針對跟蹤過程中SURF匹配數下降和不穩定的現象，設計了SURF特征模板集的更新策略。與傳統特征的跟蹤進行多組對比實驗，其結果證明了該方法對光照和遮擋具有很好的魯棒性，對目標跟蹤的準確率更高。

目標跟蹤；視覺顯著性；顏色直方圖；加速魯棒特征（SURF）；粒子濾波；KLT算法

1　引言

目標跟蹤是絕大多數視覺系統中不可或缺的環節，同時也是計算機視覺和模式識別領域的熱點問題，在人機交互、機器人導航、智能視頻監控等方面有廣泛的應用。為了實現準確、穩定的目標跟蹤，許多學者已經提出不同的跟蹤算法［1-3］。作為運動目標跟蹤方法的常用數學工具，粒子濾波（Particle Filter）對運動模型的非線性、非高斯、多峰等問題表現出良好的適應性，已被大量應用于行人、車輛等運動目標的跟蹤［4-8］。

粒子濾波需要建立目標的觀測模型，為了提高跟蹤的魯棒性，多種類型的特征被用來表征目標。文獻［3-7］中算法大都是提取目標的顏色、紋理、運動等一種或多種特征，雖然一定程度上能夠完成對目標的跟蹤，但對目標的特征描述并不完備，無法適應目標和背景的變化。Tang等［8］提出了結合Mean-shift和粒子濾波的算法，該算法雖然對目標跟蹤有很好的魯棒性，但在目標遮擋以及相鄰幀出現較大的目標位移時，受Mean Shift算法搜索區域的限制，跟蹤會出現發散現象；Hossain等［9］利用SIFT（Scale Invariant Feature Transform）局部不變特征實現對目標的跟蹤，由于圖像的局部區域特征具有對光照、尺度、旋轉的不變性，因此以局部不變特征表征目標進行跟蹤效果比較好，但SIFT特征匹配計算復雜，無法滿足實時跟蹤的要求。近年來，SURF（Speeded Up Robust Features）［10］、RIFF（Rotation Invariant Fast Features）［11］、BRIEF（Binary Robust Independent Elementary Features）［12］等各種角點提取和描述算法陸續被提出，文獻［13］對這幾種優秀的特征點檢測算法進行了綜合性能比較，在旋轉測試、模糊測試等方面，SURF的綜合性能占優勢。SURF算法借鑒SIFT中簡化近似的思想，對DoH（Determinant of Hessian）中的高斯二階微分模板進行近似簡化，計算速度提高了3倍。如果對視頻的每一幀都進行特征點檢測，會消耗較長時間，這時基于相鄰幀連續信息的特征光流法進行跟蹤會更加快速有效。本文選用KLT（Kanade-Lucas-Tomasi）［14］來實現對特征點的匹配，文獻［15-16］中是利用屬于光流法的KLT算法實現對目標跟蹤。

以上述內容為基礎，本文提出基于SURF算法和KLT匹配算法，獲取特征點匹配結果，結合顏色直方圖特征，作為粒子濾波模型中的觀測函數，同時設計了特征點更新策略，最終實現對連續穩定的視頻中目標進行準確跟蹤。

2　顏色特征與SURF局部特征

為避免對目標的特征提取中背景區域過多而引入噪聲，本文在獲取矩形窗口后，利用最小二乘法使用橢圓擬合目標形狀。

2.1目標顯著性顏色特征

顏色直方圖法［17］計算簡單且便于實現，對運動目標形變、目標的平面旋轉、非剛體以及部分遮擋有較強的魯棒性，本文基于目標形狀擬合的橢圓區域，在HSV空間定義目標的顏色直方圖。

其中，num（color（k））為第k種顏色的數目。sum（Pixel）代表圖像區域的總像素數。對視頻做視覺顯著性分析［18］，有助于實現目標的分割、識別和檢索。定義顯著性加權顏色直方圖為：

其中，SM為圖像的視覺顯著圖，sum（SM（color（k）））是顏色為color（k）的像素處的視覺顯著值之和，sum（SM）為視覺顯著圖中所有元素之和。

2.2特征點提取與匹配

2.2.1SURF特征點提取

SURF算法在SIFT基礎上做了許多改進，對DoH算法中的高斯二階微分模板進行簡化，通過采用不斷增大盒狀濾波模板尺寸的間接方法，逐步放大的近似高斯濾波器對輸入圖像的積分圖像做卷積操作形成尺度空間。然后使用Hessian矩陣［19］進行特征點檢測，其中用盒狀濾波模板對卷積計算做近似估計，以提高速度，可得到近似的Hessian矩陣行列式：

以此表示某像素點x處的角點響應值。其中，Dxx，Dxy，Dyy分別是二階偏導濾波器的近似估計。遍歷圖像中所有像素點，形成某一尺度下特征點檢測的響應圖像。使用不同的模板尺寸形成多尺度角點響應的圖像后，將所有小于預設極值的角點響應值舍棄。利用非極大值抑制方法，得到穩定的特征點位置及尺度值。

2.2.2KLT特征點匹配

利用SURF算法提取特征點后，一般采用距離準則進行匹配，但這需要求取特征點的SURF特征描述子，該方法非常耗時，不適合用于實時跟蹤。KLT算法是一種基于最優估計的匹配方法，以待跟蹤窗口H×W在視頻圖像幀間的灰度差平方和（SSD）作為度量的跟蹤算法。該算法利用每個特征點周圍小窗口的局部信息之間的相似性度量進行最優估計，耗時較少。因此，本文選用改進的KLT算法對特征點進行匹配。

（1）KLT算法理論

KLT算法假設了一個包含特征紋理信息的窗口區域H×W，用一個平移模型描述特征窗口內的像素點變化，t時刻的圖像幀I（x，y，t）和t+τ時刻的圖像幀I（x，y，t+τ）滿足如下關系：

運動量d=（Δx，Δy）為點（x，y）的偏移，該算法就是將運動參數的問題轉化為找到使SSD函數（用ε表示）最小化的特征窗口位移d，假設給定兩幅圖像I和J，定義ε為：

其中H×W表示特征窗口，ω（X）是加權函數，通常為1。d是遠小于X的量，故可將J（X+d）進行泰勒展開，去掉高次項，只保留前兩項，g是泰勒展開的一階泰勒系數，然后根據式（5）對d求導，最終化簡得：

式中，d表示特征窗口中心的平移，dk表示第k次牛頓迭代法計算得到的d值。迭代計算d需要初始估計值d0，本文初始迭代值設為0。

（2）改進的KLT算法

KLT算法匹配耗時少，精度高，適合于目標運動速度小，幀間位移較小的情況。但當目標快速運動時，幀間位移很大，小窗口匹配容易漏匹配，而選擇大的窗口，匹配精度會下降。因此，需要對上述KLT匹配算法進行分層迭代匹配。

首先根據高斯金字塔分解，對圖像I和J分別進行精度遞減的L層金字塔分解，可得到Il和Jl（其中l= 0，1，…，L），初始化=0，n=0，令l=L，n=n+1，根據公式（7）得到，判斷迭代次數是否達到規定要求或精度是否滿足要求，然后判斷若l=0則結束，最終令。

經上述分層迭代后，選擇小的搜索窗口，通過不斷將高分辨率層的迭代結果作為低分辨率層迭代的初始值繼續進行迭代，到最低層為止，可大大提高目標作快速運動時的特征點匹配精度。

3　基于顏色和SURF特征的粒子濾波跟蹤

獲取目標的視覺特征后，目標的跟蹤可以視為狀態估計問題，即根據目標在前一幀的狀態信息估計其當前幀的狀態。粒子濾波［20］又稱序列化的蒙特卡羅方法，以蒙特卡羅隨機模擬理論為基礎，將系統狀態的后驗分布用一組加權的隨機樣本近似表示，新的狀態通過這些隨機樣本的貝葉斯遞推估計。

其中Zk表示目標模板的觀測狀態。k時刻目標的估計狀態由式（9）計算得出。

3.1粒子跟蹤初始化

選定跟蹤目標以后，首先初始化目標模板狀態和粒子點集。目標狀態的粒子表示為：［x，y，a，b］，其中（x，y）是橢圓窗口的中心坐標，a和b分別表示橢圓窗口的長、短軸。設定粒子數目N，N個粒子的權重初始化為。在目標初始狀態附近隨機分布粒子狀態參數，得到初始時刻0的粒子集2，…，N｝。

粒子運動模型采用二階自回歸模型：

其中，Ut-1是4元隨機高斯噪聲，高斯分布均值為0，方差與目標尺度相關。C=｛C1，C2，C3，C4｝表示粒子的隨機傳播半徑。

3.2計算觀測概率

粒子觀測是指將新捕獲的圖像信息表示為觀測值，并計算狀態更新后的粒子與目標模板的相似程度，用觀測概率更新粒子的權值。

3.2.1顏色觀測概率

采用Bhattacharyya距離衡量目標模板和候選區域（粒子i=1，2，…，N）的顯著性顏色直方圖相似距離。

3.2.2SURF特征觀測概率

在跟蹤窗口的相鄰區域（基于上一幀窗口位置選擇3H×3W鄰域范圍）尋找匹配的SURF特征點，得到數目為M的匹配SURF特征模板集。對于某個粒子i，計算落入粒子區域（粒子i=1，2，…，N）中的匹配特征點的個數m。定義SURF觀測概率：：

3.2.3聯合的觀測概率

本文采用乘性融合框架，獲得目標的最終觀測概率如下：

3.3粒子權重更新

3.4目標狀態估計

估計目標狀態是指通過估計運動目標的狀態參數和粒子狀態參數的加權。

其中，［xt，yt，at，bt］i是t時刻粒子i的狀態，是t時刻粒子i的權重。加權求和后的狀態參數即為目標當前幀的狀態估計，獲得目標的位置和尺寸，從而完成對當前幀的跟蹤。

本文實現的粒子濾波跟蹤基本流程如圖1所示。

圖1　粒子濾波跟蹤流程

3.5模板更新和SURF特征點更新

受光照、運動形態的變化，目標的顏色特征和SURF特征點集也會產生變化。因此，需要以一定的時間間隔對目標模型進行更新，通過擴展橢圓跟蹤窗口，使其包含一定的背景區域，做顯著性檢測和分割，使用分割出的目標區域擬合出橢圓外接窗口，同時基于新的窗口區域重新計算模板顏色直方圖。另外，本文設計的SURF特征點集的更新包括增加特征點、刪除特征點和更新特征點三個方面，具體方法如下：

（1）對于模板中的SURF特征點，定義一個權值K，初始化為1。模板特征點集定義為Sm=｛fi，Ki|i=1，2，…，F｝。使用模板對t時刻的目標進行跟蹤時，通過狀態估計獲取目標新的狀態估計，使用新的目標窗口區域中的SURF對模板特征集進行更新。如果匹配的特征點數與模板總特征點的比值小于某個閾值，則SURF特征集不進行更新。

（2）模板特征集中沒有匹配的那些特征點，權值K值減少1，如果K≤x1，則從模板集中刪去（x1為變量，x1≤0）。

（3）模板中與新的目標窗口中匹配的那些特征點，使用新的窗口中相應的特征點對其特征矢量進行更新，同時K加1。設定一個變量x2（x2＞1），如果K≥x2，該特征點將永久保留。

（4）將新的目標窗口中出現的，但沒有匹配的SURF也加入特征點集S，作為新增加的特征點，設置權值K= 1，并保存目標窗口尺寸、中心坐標和該特征點坐標。

其中，參數x1，x2的設置對SURF特征集的有用性和冗余性會產生關鍵的影響，因此本文通過實驗選擇合適的參數x1，x2。采用Crowd_PETS09跟蹤數據庫中的視頻（#S2#L1）和L1_BPR的car兩段視頻進行實驗，實驗視頻如圖2所示，紅色矩形標注的為用于更新特征集的目標。

圖2　用于參數選擇的實驗視頻

先假設x2為一個不變大數，模板集的平均總數和平均每幀正確匹配點數隨x1變化如表1所示。

表1　模板集規模和平均匹配數隨參數x1變化

由結果可以看出，隨著x1的增加，雖然模板集規模在變大，但是平均正確匹配數并沒有明顯的增加。x1的選擇實質上是增加了前些幀沒有正確匹配的特征點，而模板集規模的增加，容易導致誤匹配的增加，因此選擇參數x1=0，即只將前1幀沒有正確匹配的特征點加入模板集。確定x1=0后，調整x2的大小，獲得模板集規模和平均正確匹配數的變化如表2所示。

表2　模板集規模和平均匹配數隨參數x2變化

從表2中看出，隨著參數x2的增加，模板集的規模和平均正確匹配點數都有所下降。x2=2顯然是不可取的，模板集總數會一直增加。設置x2的實質是保存那些能夠連續正確匹配的特征點，本文選擇x2=4。

4　實驗結果及分析

本文提出了基于顏色特征和SURF特征的粒子濾波跟蹤算法。為了驗證顯著性特征的跟蹤效果，將本文算法與傳統的基于顏色直方圖的粒子濾波跟蹤（Color based Particle Filter tracking，Color PT）相比較。

4.1實驗環境

實驗環境和實驗參數如下：筆記本電腦Acer-4741g，Intel CoreTMi5 CPU@2.53 GHz，內存2 GB；操作系統為Windows XP Professional，SP2；仿真軟件采用Matlab R2010b和Microsoft VC++2008以及opencv2.3視覺庫。目標的初始位置通過手工的方式給出，粒子數目N設為200；初始分布為均勻分布U（x）=1/N。本文采用的視覺顯著圖生成算法為LC［21］。

4.2實驗結果

為了驗證本文方法的效果，本文進行了以下幾組實驗。實驗1為了驗證算法對遮擋和類似目標影響的魯棒性；實驗2為了驗證算法對光照變化的魯棒性。

實驗1遮擋對算法的跟蹤性能影響。測試視頻采用CAVIAR的視頻序列（OneLeaveShopReenter2cor，分辨率384×288）。其中圖3（a）顯示的是使用顏色直方圖粒子跟蹤的結果，可以看出，從193幀開始，跟蹤行人開始被走廊中新出現的行人遮擋，而且具有相似的顏色特征，基于顏色特征的粒子濾波跟蹤從此開始失效，一直持續到視頻第400幀附近。而本文提出的跟蹤算法（如圖3（b））由于利用了SURF特征匹配，其對伸縮、旋轉、光照等具有不變性的特點，彌補了顏色特征的不足，另外，基于粒子濾波的方法能夠對下一時刻的目標進行預測，使其在遮擋結束后能夠準確找到原來的跟蹤目標。該視頻序列具有人工標定的運動目標位置和尺寸信息，圖3（c）計算出了跟蹤過程中估計的目標中心與手工標定的目標中心的距離。從跟蹤準確性看，本文方法明顯優于僅使用顏色直方圖的粒子濾波跟蹤。

實驗2兩種算法在明顯光照變化下的跟蹤效果比較。如圖4所示，在ETH的測試序列（sunny_day-img-left，分辨率640×480）中的目標進行跟蹤。使用CPT的跟蹤從101幀開始，由于光照的變化跟蹤明顯開始不穩定；到286幀（如圖4（a）的第三幅圖像），CPT跟蹤了錯誤的目標，一直到第350幀以后跟蹤才逐步正常。而本文所提的方法跟蹤效果如圖4（b）所示，結合SURF特征提取方法彌補了基于顏色直方圖特征對目標跟蹤的缺點，基本上沒有受到光照的影響，跟蹤穩定性明顯好于CPT。

圖3　視頻OneLeaveShopReenter2cor的實驗結果

圖4　視頻ETH（sunny_day-img-left）的跟蹤結果

在粒子數目有限的前提下，由于粒子的隨機分布和運動的隨機性，粒子濾波跟蹤并不是完全穩定的跟蹤。為了定量地衡量算法的效果，對兩次實驗分別做5次獨立重復實驗，計算跟蹤的平均失敗幀數。跟蹤失敗的定義為：真實狀態與估計狀態的重合程度低于50%，即基本上偏離了目標。表3是重復實驗得到的兩次跟蹤實驗中平均失敗幀數。

表3　兩個實驗場景中對目標的跟蹤結果

經過大量的實驗發現，本文跟蹤算法對行人目標具有良好的跟蹤效果，特別是對于目標被遮擋、光照變化等情況也能夠實現較為準確的跟蹤。由于跟蹤計算量和耗時的因素主要包括跟蹤窗口的大小、粒子數目和特征的計算復雜度。本文通過利用改進的KLT算法，對特征點進行匹配，與通常利用距離的特征點匹配算法相比，在處理速度上有所提高，實驗1中平均每幀的處理時間為0.067 s，實驗2中平均每幀的處理時間為0.071 s，能夠較好地滿足實時處理的要求。

5　結論

跟蹤目標的尺度、形狀變化，遮擋，光照變化等都影響視覺跟蹤的魯棒性，本文在粒子濾波框架下，提出了改進的視覺顯著性顏色直方圖和SURF特征聯合跟蹤的方法，其中對SURF特征點的匹配是利用了改進的分層迭代KLT特征匹配方法，大大提高了特征點匹配的速度。針對快速運動的目標，SURF特征匹配中可能出現的匹配數目急劇減少的問題，提出一種SURF特征集的更新策略，并通過實驗驗證了本文所提方法在跟蹤速度和跟蹤準確度方面，較Color PT方法都有所提高。

［1］Shiina Y，Ikenaga T.Recovery method based particle filter for object tracking in complex environment［C］//Signal& Information Processing Association Annual Summit and Conference（APSIPA ASC），Hollywood，CA，2012：1-4.

［2］吳垠，李良福，肖樟樹，等.基于尺度不變特征的光流法目標跟蹤技術研究［J］.計算機工程與應用，2013，49（15）：157-161.

［3］Jiang Zhengqiang，Huynh D Q，Moran W，et al.Multiple pedestrian tracking using colour and motion models［C］// Digital Image Computing：Techniques and Applications（DICTA），2010：328-334.

［4］Ying Hongwei，Qiu X，Song Jiatao，et al.Particle filtering object tracking based on texture and color［C］//Intelligence Information Processing and Trusted Computing（IPTC），2010：626-630.

［5］陳金廣，馬麗麗，陳亮.基于邊緣粒子濾波的目標跟蹤算法研究［J］.計算機工程與應用，2010，46（28）：128-131.

［6］Pérez P，Vermaak J，Blake A.Data fusion for tracking with particles［J］.Proceedings of the IEEE，2004：495-513.

［7］Li P，Chaumette F.Image cues fusion for object tracking based on particle filter［C］//Int’l Conf Articulated Motion and Deformable Objects，2004：99-107.

［8］Tang Da，Zhang Yujin.Combining mean-shift and particle filter for object tracking［C］//Image and Graphics（ICIG），Hefei，Anhui，2011：771-776.

［9］Hossain K，Oh Chi-min，Lee Chi-Woo，et al.Multi-part SIFT feature based particle filter for rotating object tracking［C］//Informatics，Electronics&Vision（ICIEV），2012：1016-1020.

［10］Bay H，Tuytelaars T，Gool L V.SURF：Speeded up robust features［C］//Computer Vision-ECCV 2006，2006：404-417.［11］Takacs G，Chandrasekhar V，Tsai S，et al.Unified realtime tracking and recognition with rotation-invariant fast features［C］//IEEE Computer Conference on Computer Vision and Pattern Recognition（CVPR），San Francisco，CA，2010：934-941.

［12］Calonder M，Lepetit V，Strecha C，et al.BRIEF：binary robustindependentelementaryfeatures［C］//Computer Vision-ECCV 2010，2010：778-792.

［13］Khvedchenya E.Feature descriptor comparision report［R/OL］.［2012-08-18］.http：//computer-vision-talks.com/.

［14］Tomasi C，Kanade T.Detection and tracking of point features，Carnegie Mellon University Technical Report CMUCS-91-132［R/OL］.［1991］.http：//www.lira.dist.unige.it/teaching/ SINA/slides-current/tomasi-kanade-techreport-1991.pdf.

［15］Gong J，Liu F Q，Song C L，et al.Research on the moving vehicle detection algorithm based on the motion vector［J］.Advances in Intelligent and Soft Computing，2012，127：41-49.

［16］劉玉，王敬東，李鵬.一種基于SIFT和KLT相結合的特征點跟蹤方法研究［J］.宇航學報，2011，32（7）：1618-1625.

［17］Yang Hanxuan，Shao Ling，Zheng Feng，et al.Recent advances and trends in visual tracking：a review［J］.Neurocomputing，2011，74（18）：3823-3831.

［18］Montabone S，Soto A.Human detection using a mobile platform and novel features derived from a visual saliency mechanism［J］.Image and Vision Computing，2010：89-94.

［19］王永明，王貴錦.圖像局部不變性特征與描述［M］.北京：國防工業出版社，2010.

［20］胡仕強，敬忠良.粒子濾波原理及其應用［M］.北京：科學出版社，2010.

［21］Achanta R，Hemami S，Estrada F，et al.Frequency-tuned salient region detection［C］//IEEE Int’l Conf Computer Vision and Pattern Recognition（CVPR），2009：1597-1604.

Targets tracking based on improved color histogram and SURF features using particle filter.

JIN Zhigang1，WEI Jinjin1，LUO Yongmei2，LIU Xiaohui3

1.School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China
2.School of Computer Science and Technology，Tianjin University，Tianjin 300072，China
3.National Computer Network Emergency Treatment Coordination Center，Beijing 100029，China

In order to track moving targets of video exactly，a novel tracking scheme is proposed using particle filter based on improved color histogram features and Speeded Up Robust Features（SURF）.SURF algorithm is applied to extracting features.The features are tracked stably by the hierarchically iterative matching of the Kanade-Lucas-Tomasi（KLT）matching algorithm.Based on fusion mode of multiplicative weights，the SURF and improved saliency weighted color histogram are used to the joint observation probability.Meanwhile，for avoiding the drop of SURF matching numbers and the instability in tracking process，a SURF feature-point-set update method is presented.Through using multi-group experiments，the results demonstrate that this approach has great robustness for either sunlight or block and has high accuracy in tracking. Key words:target tracking；visual saliency；color histogram；Speeded Up Robust Features（SURF）；particle filter；KLT algorithm

A

TP391

10.3778/j.issn.1002-8331.1310-0297

國家高技術研究發展計劃（863）（No.2009AA01A336）。

金志剛（1972—），男，教授，博士生導師，研究領域為網絡與信息安全，圖像/視頻處理；衛津津（1987—），通訊作者，女，博士研究生，研究領域為模式識別，視頻圖像處理；羅詠梅（1974—），女，工程師，研究領域為計算機網絡技術與應用；劉曉輝（1986—），男，博士生，研究領域為模式識別，視頻圖像處理。E-mail：weijin525@163.com

2013-10-23

2014-01-16

1002-8331（2015）22-0193-06

CNKI網絡優先出版：2014-03-18，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0297.html