基于Mean Shift算法視頻跟蹤研究

楊 輝，劉 軍，阮 松

（1.武漢工程大學 智能機器人湖北省重點實驗室，湖北 武漢430074；2.武漢工程大學 計算機科學與工程學院，湖北 武漢430074）

0 引 言

目標跟蹤融合了計算機視覺，模式識別，人工智能，自動控制，數學等領域的先進技術［1］，在航天、醫(yī)療、交通、安全、生產等領域有著廣泛的應用前景。在眾多的跟蹤算法中，Mean Shift算法因原理簡單，魯棒性好以及無參的特性，近幾年來在視頻跟蹤領域受到了廣泛的關注。然而，由于Mean Shift算法是一種基于概率密度梯度無參估計的匹配算法，采用跟蹤區(qū)域顏色反向投影圖的策略來建立目標模型和候選目標模型，大大限制了Mean Shift算法在跟蹤領域的廣泛應用。通過實驗可知，在背景簡單的情況下能夠達到良好的跟蹤目的；同時，理論上分析候選目標模型的建立依賴于前一幀的跟蹤結果，所以相鄰兩幀中必須要有重疊區(qū)域，這是Mean Shift算法實現良好跟蹤的前提，一旦視頻速度變快，相鄰兩幀失去重疊的區(qū)域就會導致跟蹤失敗。隨著視頻技術的快速發(fā)展，各種視頻類型層出不窮，其中高速，背景復雜的視頻占據了較大的比例，為了實現視頻的實時跟蹤，對這類視頻的研究是不可回避的。基于Mean Shift算法在跟蹤方面的良好性能，為了能進一步提高Mean Shift的跟蹤性能，不少學者對Mean Shift算法進行了探索和研究。文獻 ［2］提出的改進型Mean Shift方法提高了對目標的辨識能力和魯棒性，但分塊基于的標準和過程增加了算法的復雜性；文獻 ［3］提出基于特征匹配的運動目標檢測和 Mean Shift算法相結合的方法改善了一定速度目標跟蹤性能；文獻 ［4］采用多特征融合來實現跟蹤，這種方法加大了背景和目標的可分性，但是各種特征在各種情況下所占的比例需要時時跟新，過程比較繁瑣。

本文從跟蹤目標背景的復雜性以及幀速的角度出發(fā)，提出基于Mean Shift算法融合Harris角點特征和Surf算法的視頻跟蹤，旨在改善Mean Shift算法在目標背景復雜以及幀速過快情況下的視頻跟蹤性能。

1 Mean Shift算法的跟蹤原理及其局限性

1.1 Mean Shift算法原理簡介

Mean Shift算法是一種迭代算法。具體流程為：先算出待測點的偏移量的平均值 （也稱偏移均值或 Mean Shift向量），移動該點到其偏移均值點，然后以偏移均值點作為新的待測點，再次計算新待測點的偏移均值，如此迭代循環(huán)，直到滿足相應的條件就結束。取M維空間RM中的n個樣本點并標記為Xi（i＝1，2……n），Sh是一個以h為半徑高維球區(qū)域，其中有K個樣本點落在Sh范圍內，在X點處Sh范圍內的偏移均值定義為

在數學上概率密度梯度的值非零則表示為概率密度增加的最大方向，若樣本點采樣于概率密度函數，則概率密度梯度的方向即為偏移均值。由于樣本點離X的遠近的不同以及每個樣本點重要性的差異，偏移均值的最終效果也不同。為此在偏移均值中引入核函數GH （x）和權值函數W （x），得到擴展的偏移均值為

把式 （2）最右邊第一項記為m （x），則 Mean Shift算法可以理解為以下3個步驟：

（1）計算 m （x）；

（2）計算 m （x）－x 的值，與閾值ε進行比較，若大于轉 （3），否則算法結束；

（3）令x＝m （x），繼續(xù) （1）；

2002年Mean Shift算法在非剛體跟蹤方面的應用被提出，并近似為一個 Mean Shift向量的最優(yōu)化問題。Mean Shift算法在跟蹤過程中，對目標模型的描述利用的是跟蹤目標的灰度或色彩分布，類比擴展的偏移均值式 （2）可知，搜索框的作用即為核函數的作用，目標的灰度或色彩分布即為樣本的權值。具體跟蹤過程描述如下：

（1）在初始幀，用搜索框框定目標，記搜索框的中心為X0；

（2）計算搜索框內的顏色概率分布，根據概率分布求得搜索框的質心為Xc；

（3）移動搜索框使得搜索框的中心與X重合，移動前判斷若｜X0－Xc｜＞ε且在當前幀中移動次數小于常數C，則移動后繼續(xù)2；否則移動后輸入下一幀繼續(xù) （2），此幀搜索框的初始位置為上一幀搜索框的最終位置。

3.3 調節(jié)黏液合成與分泌 在 CRS 病理機制中，細菌脂多糖和炎性介質共同刺激黏膜杯狀細胞，使之分泌大量黏稠的黏液，導致炎癥遷延不止。黏蛋白 4、黏蛋白 5AC 和黏蛋白 5B 是氣道黏液中主要的 3 種成分，影響著黏液的彈性和黏性。黏液分泌受 IL-8 的調控，研究證實，紅霉素、阿奇霉素、麥迪霉素等可以抑制 IL-8、TNF-α、黏蛋白 5AC等的表達，從而減少黏液的分泌[21-22]。此外，MA可以改善黏液的清除、減少糖精傳輸時間，改變黏液的流變性能[23]。黏液中氯化物含量較高可能導致流變性能差，而 MA 通過減少氯化物含量使更多稀薄的黏液產生[24]。

1.2 Mean Shift算法在跟蹤方面的局限性

Mean Shift算法在跟蹤方面的局限性通過兩段視頻予以說明。

視頻1：被跟蹤目標為灰色，整個場景中由于燈光的原因整體呈現灰黑色，背景閃爍變化，過于復雜，跟蹤目標從954幀開始跟蹤，到第1938幀時跟蹤失敗共跟蹤984幀，如圖1和圖2所示。

視頻2：跟蹤目標為黑色，且始終在運動場上移動，與白色的運動場背景對比鮮明，跟蹤目標從第263幀開始進行跟蹤，跟蹤目標從左下角移動到右上角，到第540幀時出現跟蹤失敗，總共跟蹤277幀，運動視頻速度過快，導致前后幀沒有重疊的區(qū)域，跟蹤失敗，如圖3和圖4所示。

綜上所述，Mean Shift算法不適于跟蹤目標背景復雜，速度過快的視頻。

2 Harris角點檢測

在圖像中角點一般定義為亮度變化劇烈的點或邊緣曲線曲率的極大值點［5］。角點數目少，一般只占整幅圖像0.05%左右的像素，但角點卻含有圖像重要局部特征信息，由于不同圖像之間角點差異性很大，因此將角點作為特征提取的對象，在減少數據量的同時，又能夠提取豐富的特征信息。Harris角點檢測是一種基于灰度圖像亮度變化的角點檢測算法。基本思想是：在圖像中設計一個局部檢測窗口，當該窗口沿各個方向作微小移動時，考察窗口的平均能量變化，當該能量變化值超過設定的閾值時，就將窗口的中心像素點提取為角點［6］。優(yōu)點是在操作時只用到了一階差分及濾波，因此計算簡單，對圖像光照、旋轉、部分仿射變化以及噪聲干擾具有很好的魯棒性，比較適合于目標的定位。由于Harris角點檢測算法對尺度變化敏感，同一物體在不同尺度下提取的角點可能完全不同，在跟蹤過程中，攝像機和目標之間距離的變化會導致跟蹤目標的尺度發(fā)生變化，因此不能單純地用Harris角點檢測算法提取的特征來進行跟蹤。

Mean Shift算法利用目標顏色信息這一特征進行跟蹤，當背景過于復雜或者與跟蹤目標相似時很容易導致跟蹤失敗，這是因為單一的特征不足以描述跟蹤目標，為了提高Mean Shift算法在這方面的跟蹤性能，有必要引入更多更好的特征進行融合實現實時跟蹤。而Harris算法的優(yōu)點決定了它所提取目標的特征與周圍環(huán)境具有明顯的可分性。因此選擇Harris算法提取的特征與顏色特征進行融合在理論上是個不錯的選擇。融合的方法為將Mean Shift的跟蹤過程的第二步修改為，計算搜索框內的角點以及角點的顏色概率分布，根據概率分布求得搜索框的質心為Xc。

3 Surf算法

3.1 特征點檢測

Surf對于特征點的檢測是基于Hessian矩陣行列式的正負，而Hessian矩陣的行列式在計算的過程中采用了積分圖像法，這是Surf算法實現快速檢測的關鍵原因之一。

Hessian矩陣定義如下

其中L（x，y，Ф）是圖像I（x，y）在尺度Ф下的圖像，由高斯函數G （Ф）與圖像I（x，y）卷積得到，Lxx（x，y，Ф），Lxy（x，y，Ф），Lyy（x，y，Ф）是L （x，y，Ф）的二階偏導數。實際計算時用盒形濾波器與模板的卷積近似得到二階偏導數的值Dxx，Dxy，Dyy。盒形濾波器由若干塊構成，在每一塊的連續(xù)區(qū)域具有相同的權值，因此做卷積運算實際上計算的就是這塊區(qū)域的積分圖。盒形濾波器和積分圖的引入大大加快了卷積的計算速度。Hessian矩陣的行列式為 （w為近似計算的誤差因子）

若det（H）＞0則該點即為極值點。依次計算各尺度下的極值點，并將各極值點與其同一尺度的領域8個點以及相鄰尺度的9個點共26個點比較大小。若該點是這些點中最大的或是最小的，則該點即為特征點。

3.2 特征點描述

Surf特征點的描述分為兩部分：確定主方向和構造特征描述向量。

為保證旋轉不變形，需要確定主方向。以每個特征點為中心，以6倍特征點所在尺度為半徑畫圓，計算圓內各點在X和Y方向上小波響應，其中Haar小波邊長為4倍特征點所在尺度，為了使靠近特征點的響應貢獻大，分別給這些響應賦高斯權重系數，然后將圓內每60度范圍內的響應相加形成矢量，選擇最長的矢量即為該特征點的主方向。

在描述每個特征點時，將坐標軸旋轉為該特征點的主方向。以特征點為中心，取20Ф＊20Ф的區(qū)域，其中Ф為特征點所在的尺度，將其分成5＊5個4Ф＊4Ф的子區(qū)域，將20Ф＊20Ф的區(qū)域看成是5＊5的采樣點，在每個采樣點上分別計算主方向和垂直方向的Haar小波響應dx和dy。對dx和dy進行高斯加權后，對各子區(qū)域的dx，dy，｜dx｜，｜dy｜分別累加求和，并歸一化為單位向量，這樣得到4＊4＊4共64個值，即Surf提取的特征的描述向量是64維的，相比128維的sift特征描述向量而言，數據量減少了一半，這也是Surf算法快于sift算的原因之一。這種采用區(qū)域方向性信息聯合的思想增強了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性［10］。

Mean Shift算法在實施跟蹤的過程中，后一幀的初始搜索框的位置，取決于前一幀的搜索結果。若幀速過快，相鄰兩幀失去重疊區(qū)域，則會導致跟蹤失敗。本文引入Surf算法解決幀速過快導致的跟蹤失敗，具體過程為，標定目標時，用Surf算法提取目標的Surf特征點集P，設Hi和Hi＋1為前后兩幀的搜索框內的顏色直方圖，利用Bhattacharyya距離判斷他們的相似程度，Bhattacharyya距離越大則越相似，若dBhattacharyya（Hi，Hi＋1）＜＝0.8則跟蹤失敗。一旦跟蹤失敗，用Surf算法在整幀畫面中提取與P相匹配的點集Q，選擇一個將不部分Q點集包含在內的矩形框，更新搜索框為該矩形框，繼續(xù)采用Mean shift實行跟蹤。

4 改進的Mean Shift算法流程及實驗結果與分析

融合Harris角點檢測算法和Surf算法后的Mean Shift視頻跟蹤完整流程如圖5所示。

從圖5可知，改進后的Mean Shift算法，在流程上與原Mean Shift相比，特征提取即第2步增加了Harris角點提取，新增加了第5步和第9步用于跟蹤失敗后的搜索框的重定位。按照此流程分別測試了二段視頻，用來檢驗改進后的跟蹤效果。本實驗采用C＋＋ （visual studio 2010）和 Opencv（2.3.1）庫實現。

圖5 改進后的Mean Shift算法

視頻一：對于背景過于復雜的視頻采用改進后的Mean Shift算法跟蹤效果如圖6所示。

圖6 改進后的Mean Shift算法跟蹤效果

分析：采用Harris角點提取目標所得的顏色概率分布圖作為特征對背景過于復雜的視頻進行連續(xù)跟蹤，效果圖如圖6所示，跟蹤效果良好，與圖1－2相比，效果得到明顯改善。

視頻二：幀速過快跟蹤失敗情況下采用改進Mean Shift跟蹤效果如圖7所示。

分析：當后一幀以前一幀搜索框最后的位置作為初始搜索框的位置時，有可能幀速過快，目標已經不在后一幀初始搜索框內如圖7（b）所示，此時根據前后兩幀顏色概率直方圖的Bhattacharyya距離判斷出跟蹤失敗，啟動Surf算法，在整幅幀中查找目標。圖7（c）中目標再次出現，查找到目標，之后繼續(xù)用Mean Shift算法進行跟蹤。與圖3－4相比，跟蹤失敗的情況得到改善。

圖7 幀速過快跟蹤失敗情況下采用改進Mean Shift跟蹤效果

5 結束語

用2段視頻實驗得出Mean Shift跟蹤時在背景過于復雜，以及幀速過快方面的局限性，針對Mean Shift算法的局限性，分別予以改進。Harris角點檢測算法提取的角點具有很好的定位性，將Harris角點檢測算法與Mean Shift算法特征提取過程進行融合，得到融合的目標特征信息進行跟蹤，通過實驗得出效果圖6與圖1和圖2對比可知，背景過于復雜情況的跟蹤性能明顯得到改善。幀速過快情況下的跟蹤失敗采用的是Surf算法與Mean Shift算法的融合，實驗得出的效果圖7可知，跟蹤效果很好。雖然，本文涉及到3個算法的融合，但是Harris角點算法計算簡單，Surf算法速度很快，算法的實現基于Opencv（2.3.1版本）庫和VS2010，所以本文提出的算法可以很好進行實時跟蹤。

：

［1］SUN Xin.Based on the level set target contour tracking algorithm ［D］.Harbin：Harbin Institute of Technology，2010：4－5（in Chinese）.［孫鑫.基于水平集的目標輪廓跟蹤算法的研究 ［D］.哈爾濱：哈爾濱工業(yè)大學，2010：4－5.］

［2］HU Yin，YANG Jingyu.Based on block color histogram Mean shift tracking algorithm ［J］.Journal of System Simulation，2009，5 （10）：2936－2939 （in Chinese）.［胡銦，楊靜宇.基于分塊顏色直方圖的 Mean shift跟蹤算法 ［J］.系統(tǒng)仿真學報，2009，5 （10）：2936－2939.］

［3］YAO Fangwu，XU Chenming.Mean shift tracking algorithm based on the target centroid［J］.Computer Technology and Development，2012，6 （22）：104－106 （in Chinese）.［姚放吾，許辰銘.基于目標質心的Mean shift跟蹤算法 ［J］.計算機技術與發(fā)展，2012，6 （22）：104－106.］

［4］YUN Xiao，XIAO Gang.Vessel tracking algorithm based on multi－feature adaptive fusion of the Camshift［J］.Optical Engineering，2011，5 （38）：52－58 （in Chinese）.［云霄，肖剛.基于Camshift的多特征自適應融合船舶跟蹤算法 ［J］.光電工程，2011，5 （38）：52－58.］

［5］GONG Ping，LIU Xiangbin.An improved Harris corner detection algorithm ［J］.Computer Engineering and Aplications，2010，46 （11）：173－175 （in Chinese）.［龔 平，劉 相 濱，周鵬.一種改進的Harris角點檢測算法 ［J］.計算機工程與應用，2010，46 （11）：173－175.］

［6］liuw ＿9.The idea of the Harris corner detection algorithm ［EB／OL］.［2007－11－28］.http：／／http：／／blog.csdn.net／liuw ＿9／article／details／1906245 （in Chinese）.［liuw＿9.Harris角點檢測算法的 思 想 ［EB／OL］.［2007－11－28］.http：／／http：／／blog.csdn.net／liuw＿9／article／details／1906245.

［7］XIONG Yin，MA Huimin.Extraction and application of 3dimensional objects SIFT feature［J］.China Journal of Graphics，2010，15 （5）：814－819 （in Chinese）.［熊英，馬惠敏.3維物體SIFT特征的提取與應用 ［J］.中國圖像圖形學報，2010，15 （5）：814－819.］

［8］FENG Jia.Study and improving of sift algorithm ［D］.Changchun：Jinlin Technology，2010：6－7 （in Chinese）.［馮嘉.Sift算法的研究和改進 ［D］.長春：吉林大學，2010：6－7.］

［9］BAY H，Tuytelaars T，GOOL L V.SURF：Speeded up robust features ［C］／／Proceedings of the European Conference on Computer Vision.Graz，Austria，2006：404－417.

［10］Yong.Learning experience of Surf algorithm ［EB／OL］.［2011－11－17］.http：／／http：／／www.yongblog.com／archives／123.html（in Chinese）.［Yong.Surf算法學習心得［EB／OL］. ［2011－11－17］.http：／／http：／／www.yongblog.com／archives／123.html.］