基于SURF和Camshift的目標(biāo)跟蹤算法研究

李建建，王春陽

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

近年來，對于運(yùn)動目標(biāo)的跟蹤一直是機(jī)器視覺領(lǐng)域一個關(guān)鍵的研究方向［1］。盡管出現(xiàn)了非常多的方法，但是如何快速有效的跟蹤目標(biāo)，仍然是一個非常值得研究的課題，隨著圖像處理技術(shù)的發(fā)展和開源代碼的發(fā)布使得許多目標(biāo)跟蹤算法得以實現(xiàn)并改進(jìn)，Camshift［2］算法就是其中一個。

Camshift算法是一種基于顏色直方圖信息的半自動跟蹤算法，需要人工選取第一幀的搜索窗口，而且只采用HSV顏色模型H通道的顏色信息，當(dāng)目標(biāo)發(fā)生遮擋或者背景有相似顏色干擾時，該算法容易丟失跟蹤目標(biāo)［3］。David G Lowe等提出的SIFT［4］算法在目標(biāo)發(fā)生旋轉(zhuǎn)、尺度縮放、亮度變化的情況下仍具有良好的魯棒性，但SIFT算法缺點(diǎn)是計算量大，耗時時間長［5］。Herbert Bay等人對SIFT算法作出改進(jìn)得到SURF［6］算法，SURF算法魯棒性好且時間復(fù)雜度低，適合實時性要求較高的場合。

針對上述問題，本文給出在Camshift算法基礎(chǔ)上結(jié)合SURF算法的目標(biāo)跟蹤技術(shù)方法。利用SURF特征的位置信息彌補(bǔ)了Camshift只依靠顏色信息的缺陷，提高了目標(biāo)在發(fā)生遮擋或者背景有相似顏色干擾時的跟蹤準(zhǔn)確性，并具有較強(qiáng)的魯棒性和有效性。

1 Camshift算法

Camshift算法是一種基于顏色直方圖的連續(xù)自適應(yīng)均值漂移算法。設(shè)(x,y)為搜索窗口中的像素位置，I(x,y)是概率分布圖中(x,y)的像素值，Camshift算法過程如下：

（1）人工確定第一幀搜索窗口；

（2）提取H分量計算出搜索窗口的顏色概率直方圖，根據(jù)顏色概率直方圖，得到新搜索窗口的大小和質(zhì)心位置，分別計算：

零階矩：

x、y的一階矩：

搜索窗口的質(zhì)心位置：

搜索窗口的寬度s=2M00256；長度l=1.2s；

（3）重復(fù)（2），直到質(zhì)心位置變化小于設(shè)定的閾值，或者當(dāng)循環(huán)運(yùn)算的次數(shù)達(dá)到設(shè)定的最大次數(shù)時，就停止運(yùn)算；

（4）在后一幀視頻圖像中用（3）中的結(jié)果初始化搜索窗口的大小和質(zhì)心位置，跳轉(zhuǎn)到步驟（2）繼續(xù)進(jìn)行目標(biāo)跟蹤。

2 SURF算法

2.1 特征點(diǎn)檢測和描述子生成

（1）特征點(diǎn)檢測

SURF算法通過計算相關(guān)Hessian矩陣并找到尺度空間的極值點(diǎn)來檢測特征點(diǎn)。對于圖像中某個像素點(diǎn)=(x,y)。箱式濾波同圖像卷積后的結(jié)果分別設(shè)為Dxx、Dxy、Dyy，引入誤差參數(shù)β，則Hessian矩陣的行列式表示為：

其中，β近似取0.9，當(dāng)det(H)值為負(fù)數(shù)時，該點(diǎn)為非極值點(diǎn)；當(dāng)其值為正數(shù)時，該點(diǎn)可能是局部極值點(diǎn)，當(dāng)局部極值點(diǎn)大于或者小于立體領(lǐng)域其他相鄰的26個點(diǎn)時，認(rèn)為該局部極值點(diǎn)作為立體領(lǐng)域的特征點(diǎn)。

（2）特征點(diǎn)主方向確定

在尺度空間σ下，以特征點(diǎn)為中心，以6σ為半徑，分別計算出該區(qū)域的每個點(diǎn)在x，y方向的哈爾小波響應(yīng)（波長為4σ），并給每個響應(yīng)值賦予相應(yīng)的高斯權(quán)重系數(shù)，然后以特征點(diǎn)為中心，用π 3扇形區(qū)域范圍遍歷整個圓形區(qū)域，選擇其中最長的向量作為該特征點(diǎn)的主方向，對圖像中每個特征點(diǎn)進(jìn)行相同運(yùn)算，得到每個特征點(diǎn)的主方向。

（3）特征點(diǎn)描述子生成

以特征點(diǎn)為中心，選取一邊垂直于主方向邊長為20σ的正方形窗口，將該窗口分為4×4的子窗口，計算每個子窗口主方向和垂直方向的哈爾小波響應(yīng)，分別記為dx、dy，然后對每個子窗口的響應(yīng)值和響應(yīng)值的絕對值分別求和表示為∑dx、∑dy、∑|dx|、∑ |dy|，這樣每個子窗口形成一個四維分量的矢量V=(∑||dx,∑|dy|,∑|dy|)，每個特征點(diǎn)的描述子則由64維特征向量構(gòu)成。

2.2 SURF特征匹配定位目標(biāo)

對于兩幅圖像中的每個特征點(diǎn)，本文采用快速近似最近鄰搜索算法進(jìn)行匹配［7］。為了驗證SURF算法的快速有效性，運(yùn)用SURF算法和SIFT算法分別對同一組目標(biāo)模板和視頻幀進(jìn)行特征點(diǎn)、檢測描述子生成和特征點(diǎn)匹配，如圖1所示。圖1（a）為SURF算法的匹配結(jié)果，圖1（b）為SIFT算法的匹配結(jié)果，表1為SURF和SIFT算法的性能比較。

圖1 SURF和SIFT算法的匹配結(jié)果

表1 SURF和SIFT算法性能比較

從表1可以看出，SURF算法總耗時大約是SIFT算法的1/3，時間復(fù)雜度更低，雖然SIFT算法檢測出的特征點(diǎn)更多，但是耗時過長，難以滿足本文快速定位的要求，所以SURF算法相比SIFT算法更適合用于實時目標(biāo)跟蹤。

圖2（a）中，運(yùn)用SURF算法將目標(biāo)模板與含有目標(biāo)的視頻幀進(jìn)行匹配時，可以定位目標(biāo)，并獲得目標(biāo)質(zhì)心及大小，圖2（b）中，運(yùn)用SURF算法將目標(biāo)模板與不含目標(biāo)的視頻幀進(jìn)行匹配時，未定位出目標(biāo)位置。由此，在獲得目標(biāo)先驗知識的情況下，可利用SURF算法定位目標(biāo)，繼續(xù)進(jìn)行動態(tài)目標(biāo)跟蹤。

圖2 SURF算法定位目標(biāo)效果

3 基于SURF和Camshift的目標(biāo)跟蹤算法

首先運(yùn)用SURF算法將幀圖像與目標(biāo)模板進(jìn)行特征匹配，計算出目標(biāo)在幀圖像中的位置和大小，并將結(jié)果作為Camshift算法第一幀的搜索窗口，然后利用當(dāng)前幀搜索窗口與目標(biāo)模板兩者之間的顏色概率直方圖的Hellinger距離判定跟蹤結(jié)果是否準(zhǔn)確。采用k個bin的顏色概率直方圖，目標(biāo)模板的顏色概率直方圖P=(p1,...pk)，當(dāng)前幀搜索窗口的顏色直方圖為Q=(q1,...qk)，則Hellinger距離計算公式為：

兩個直方圖越相似，則H(P,Q)值越??；兩個直方圖相差越大，則H(P,Q)值越大［8］。經(jīng)過多次實驗，當(dāng)H(P,Q)大于0.5時，本文認(rèn)為跟蹤失敗，再次運(yùn)用SURF算法重定位運(yùn)動目標(biāo)，將跟蹤繼續(xù)進(jìn)行下去，如果H(P,Q)小于0.5，則認(rèn)為跟蹤成功，將當(dāng)前幀的跟蹤結(jié)果作為目標(biāo)模板。

基于SURF和Camshift的目標(biāo)跟蹤算法流程圖如圖3所示。

圖3 基于SURF和Camshift的目標(biāo)跟蹤算法流程圖

4 實驗結(jié)果及分析

本算法的實驗硬件環(huán)境為Intel（R）Core（TM）i7-4710HQ，主頻是2.5GHz，8G內(nèi)存，軟件開發(fā)環(huán)境是Windows7操作系統(tǒng)，Microsoft Visual Studio 2010配置OpenCV庫。標(biāo)準(zhǔn)測試視頻名為David3，總幀數(shù)為252幀。

下面分別使用傳統(tǒng)的Camshift算法和本文提出的算法對測試視頻進(jìn)行測試，對比兩種算法的跟蹤效果，試驗中選取黃色上衣男子為跟蹤目標(biāo)并存儲為目標(biāo)模板，如圖4所示，選取第176幀，181幀，187幀，195幀作跟蹤效果對比。

圖4 傳統(tǒng)的Camshift算法和本文算法跟蹤效果對比

如圖4（a）所示，在第176幀中，人工確定的搜索窗口難以收斂到跟蹤物體的邊緣［9］，而使用本文算法，如圖（b）所示，目標(biāo)的特征點(diǎn)一般位于邊緣處，利用目標(biāo)模板和圖像幀進(jìn)行SURF特征匹配定位目標(biāo)，并自動快速確定首幀的搜索窗口，減少了其他非目標(biāo)像素點(diǎn)的干擾；在第181幀中，跟蹤目標(biāo)過程中背景出現(xiàn)相似顏色像素干擾，傳統(tǒng)的Camshift算法跟蹤窗口發(fā)生擴(kuò)大，本文算法具有較好的跟蹤精確性；如圖4（a）所示，在187幀中，目標(biāo)發(fā)生遮擋，跟蹤窗口誤跟蹤到與目標(biāo)有相似顏色的樹木，本文算法中檢測到目標(biāo)模板與搜索窗口的顏色概率直方圖Hellinger距離大于給定閾值，利用SURF算法將目標(biāo)模板與圖像幀進(jìn)行特征匹配，將得到的包含目標(biāo)的最小立式矩形作為Camshift算法的搜索窗口，如圖4（b）所示，在第195幀中，本文算法繼續(xù)對原目標(biāo)進(jìn)行有效跟蹤。通過圖4傳統(tǒng)的Camshift算法和本文算法的跟蹤效果對比，本文算法具有較好的魯棒性和有效性。

5 結(jié)論

本文提出一種基于SURF和Camshift的目標(biāo)跟蹤算法，驗證了SURF算法在實時性要求較高的場合有更好的應(yīng)用，使用Hellinger距離作為跟蹤效果的判定標(biāo)準(zhǔn)，利用SURF算法匹配結(jié)果得到特征點(diǎn)的位置、方向信息對Camshift算法進(jìn)行約束和更新，經(jīng)過實驗證明本文算法具有較強(qiáng)的魯棒性，可對單目標(biāo)進(jìn)行有效實時跟蹤。

［1］翟衛(wèi)欣，程承旗.基于Kalman濾波的Camshift運(yùn)動跟蹤算法［J］.北京大學(xué)學(xué)報：自然科學(xué)版，2015，51（05）：799-804.

［2］HSIEH C J，LUM K Y.Automated image tracking based on the Camshift algorithm with adaboost and target trajectory and size estimation［C］.11th IEEE International Conference on Control& Automation（ICCA），2014：918-923.

［3］修春波，魏世安.顯著性直方圖模型的Camshift跟蹤方法［J］.光學(xué)精密工程，2015，23（06）：1749-1757.

［4］Amerini I，Barni M，Caldeli R，et al.Removal and injection of keypoints for SIFT-based copy-move counter-forensics［J］.Eurasip Journal on Information Secutity，2013（1）：1-12.

［5］彭欣，劉富強(qiáng)，宋華軍.基于SURF目標(biāo)跟蹤算法研究［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，2011，34（02）：138-141.

［6］張銳娟，張建奇，楊翠.基于SURF的圖像配準(zhǔn)方法研究［J］.紅外與激光工程，2009，38（01）：160-165.

［7］趙璐璐，耿國華，李康，等.基于SURF和快速近似最近鄰搜索的圖像匹配算法［J］.計算機(jī)應(yīng)用研究，2013，30（03）：921-923.

［8］李偉湋，賈修一.基于Hellinger距離的特征選擇算法［J］.計算機(jī)應(yīng)用，2010，30（06）：1530-1532.

［9］張宏志，張金換，岳卉，等.基于CamShift的目標(biāo)跟蹤算法［J］.計算機(jī)工程與設(shè)計，2006，27（11）：2012-2014.