基于Mean Shift多特征融合跟蹤的改進算法

雷 川，黃 山，，張洪斌

（1.四川大學 電氣信息學院，四川 成都610065；2.四川大學 計算機學院，四川 成都610065）

0 引 言

由于Mean Shift目標跟蹤算法在目標跟蹤過程中能夠很快的找到最佳的匹配，故其非常適合用于對要求跟蹤響應快的實時跟蹤系統中［1，2］。Mean Shift目標跟蹤算法基于顏色模型，應用每一幀圖像顏色投影通過顏色直方圖來自動調節搜索窗口的位置和尺寸，且通過算法迭代收斂時得到最佳的中心位置作為目標的中心。該算法也存在缺陷，當目標運動過快時，在兩個相鄰幀圖像中的目標區域不能重疊，否則會導致跟蹤目標的丟失。為解決這種缺陷，文獻［3］將卡爾曼濾波與Mean Shift跟蹤算法相結合，先通過卡爾曼濾波器預測目標在下一幀圖像中的位置，然后調節使Mean Shift算法收斂的搜索窗口中心，使算法收斂的目標中心更準確，同時Mean Shift跟蹤算法僅僅以顏色特征描述目標，當跟蹤窗口中出現相似顏色干擾或者跟蹤目標變暗時，其跟蹤效果同樣不理想；文獻 ［4］通過融合顏色特征和邊緣特征，解決了在相似顏色干擾或者光照條件變化情況下，原始的Mean Shift 跟蹤算法效果不理想的缺陷。

傳統的Mean Shift算法存在當跟蹤快速運動目標和亮度環境改變過快或跟蹤目標長時間變暗時，跟蹤性能變差的缺陷的問題。上述兩種改進算法增加了算法的復雜程度、迭代次數，影響跟蹤的實時性。本文在分析算法跟蹤缺陷的基礎上，結合運動矢量，融合顏色特征和邊緣特征，提出了一種改進的Mean Shift跟蹤算法。實驗驗證了該算法的良好效果。

1 傳統算法描述

本文采用Mean Shift與特征融合算法來跟蹤運動目標，由于Mean Shift跟蹤算法是通過找到當前幀中顏色直方圖和目標模板中顏色直方圖之間的相似度最大值來跟蹤目標，故該跟蹤算法天然的融入了顏色特征。在視頻目標跟蹤中，顏色特征對遮擋有較強的魯棒性，但當環境亮度變化，運動目標變暗或相似顏色干擾時，基于顏色特征的目標跟蹤算法無法達到跟蹤要求，而邊緣特征可以很好的彌補顏色特征在環境變化的情況下跟蹤效果差的缺陷。

1.1 Mean Shift跟蹤算法

通常用跟蹤目標的灰度或色彩分布來描述該物體，假設物體中心位于x0，xi表示目標窗口中的第i 個像素點，則該物體模板概率密度可以表示為

候選的位于y 的物體模型的概率密度可以描述為

為使ρc（y）最大，對式 （3）泰勒展開

其中

計算y1－y0，如果 y1－y0＜ε則停止迭代，目標的中心由y1代替y0，每次迭代都可以從y0中得到一個新的位置y1

如此，運動目標從原始的位置逐漸調整到當前位置，實現對目標的跟蹤。

1.2 邊緣特征

多特征融合算法，是目標跟蹤領域中比較常用的算法。利用多特征描述目標是一種非常有效的實現穩健跟蹤的方法［5］。常見的描述跟蹤目標的特征有，彩色、輪廓、梯度、角點、紋理、邊緣等。常見的多特征融合有，彩色和輪廓，彩色和梯度，彩色和邊緣，角點、彩色和輪廓等。邊緣特征在圖像中表示為跟蹤目標的輪廓邊緣，在像素分布上則表示為圖像中亮度的變化最明顯部分，即其周圍像素有灰度的階躍變化。邊緣特征很好的彌補了原始Mean Shift算法中用單一的用顏色特征來描述跟蹤目標的缺陷。

1.1節表明Mean Shift跟蹤算法根據顏色直方圖對目標建模，使相似性度量Bhattaharry系數最大來確定運動目標在下一幀中的位置，從而實現目標的跟蹤。類似的，可以提取目標邊緣的直方圖來描述運動目標。

目標模型的邊緣直方圖由下式表示

候選的位于y 的物體可以描述為

Bhattacharrya系數

對式 （9）泰勒展開，并使上式最大，與1.1 中類似，可以得到目標在下一幀中的位置y1e。

2 運動矢量

由于Mean Shift跟蹤算法在搜索跟蹤目標過程中，只能在局部的某個搜索范圍內有效，當跟蹤目標運動過快時，特別是在前一幀和后一幀跟蹤目標在空間上沒有重疊時，算法的跟蹤效果不理想，容易導致跟蹤目標的丟失。其主要原因在于，在對Mean Shift跟蹤算法的推導過程中，上述公式對相似度量函數在跟蹤目標的初始中心位置的某個鄰域內即核函數的帶寬尺寸內進行泰勒展開；此時，若跟蹤目標的運動速度過快，致使在連續的兩幀圖像中，目標的運動距離超過了該鄰域，原始的Mean Shift已經不能在局部區域內搜索到使相似性度量函數的一階導數取得極值的最優點，從而導致跟蹤目標的丟失。

本文采用運動矢量來解決運動目標過快而使跟蹤目標丟失的問題。設mvx，mvy分別是運動矢量在x 軸和y 軸上的權值，運動矢量在水平和垂直分量間的夾角θ，其取值范圍的區間為（0，2π），將該取值范圍平均分成8份，即每份占，并且由θ的定義可得tanθ＝mvy／mvx，由此得到每個運動矢量對應的方向編碼，該編碼函數為

由于本文實驗都是在攝像頭靜止的情況下采集的視頻，而對于靜止的攝像頭，背景區域宏塊各個方向的運動矢量都為0，僅有存在目標運動的區域的各個方向上運動矢量不為0。在此情況下對目標運動方向和速度進行估計：設運動目標區域中所有運動矢量的方向編碼概率密度分布為，i∈（0，7），由該8個方向上的編碼概率密度分布，可以建立運動矢量方向上的編碼直方圖。根據上述的概率密度分布可以得到運動矢量方向編碼的最大概率密度，即＝max（），如果超過一定的閾值，說明跟蹤目標在同一運動方向上有整體的位移移動特性，此時可以根據該最大值估計跟蹤目標的運動方向和運動速度。否則可認為跟蹤目標沒有位移特性。取使＝Pmax的所有矢量。

3 本文算法

該算法首先應用運動矢量對候選模板中心y0進行修正得到修正后的中心y′0，以避免目標運動過快而使Mean Shift跟蹤算法丟失目標，然后在Mean Shift跟蹤算法中動態地融合顏色特征和邊緣特征來減少環境的改變給跟蹤性能帶來的影響。算法具體步驟如下：

步驟1 運動矢量預測：在第一幀中初始化目標中心y0，在下一幀中通過運動矢量預測在當前幀中的候選區域中心y′0，計算y′0的公式如下）

式中：α∈（0，1），與目標的運動速度成反比。

步驟2 Mean Shift算法搜索：根據第一步中計算出的當前幀候選中心y′0，通過Mean Shift算法搜索得到當前幀中目標的中心y1：根據基于顏色特征的Mean Shift算法搜索在當前幀中目標的中心y1c；根據基于邊緣特征的Mean Shift算法搜索在當前幀中目標的中心y1e；動態融合顏色特征和邊緣特征得到目標在當前幀中目標的中心y1，其計算公式如下

其中

式中：ρc（y）、ρe（y）——顏色特征和邊緣特征的Bhattacharrya系數；

步驟3 判斷 y1－y0＜ξ，如果該式成立則換下一幀，否則重復第二步，直到該式成立。

4 實驗結果及分析

為驗證本文算法的有效性，作者對快速運動的行人和復雜環境中運動的行人進行了實驗。本文中的實驗使用的計算機硬件配置為Intel Core2 2.4GHz CPU，2G RAM），軟件環境為Windows XP操作系統，VS2010，Opencv2.4.8軟件編程環境。

4.1 針對快速運動的行人的實驗

該實驗將攝像機固定在三腳架上采集視頻，視頻大小為450×320，幀率為30fps，長度為128。對兩個慢跑的行人中的某個人進行跟蹤。圖1是采用基于Mean Shift融合顏色和邊緣特征 （MMS算法）跟蹤算法的結果，圖1 （a）第26幀圖為原始狀態圖。

圖1 MMS算法跟蹤結果

由上述實驗結果可知，由于物體運動速度較快MMS跟蹤算法無法預測到下一幀運動目標的位置，圖1中第55幀圖，逐漸開始丟失目標，第88幀圖，該算法已經完全丟失對運動目標的跟蹤。

本文算法跟蹤結果如圖2所示。

圖2 本文算法跟蹤結果

上述實驗采用本文跟蹤算法的實驗結果，初始狀態圖依然選取第26幀，依然是選取第55幀圖和第88幀圖的跟蹤結果圖與MSS跟蹤算法的跟蹤效果作對比，由于本文算法引入了運動矢量為運動目標下一幀的位置做預測，故在目標運動速度較快時也能有較好的跟蹤性能，第55幀圖和第88幀圖的跟蹤結果說明了這一點。同時，運動矢量的引入也減少了Mean Shift的迭代次數。

從20幀到120幀中隨機抽取5幀，以15幀為間隔，統計兩種算法在相應幀下的Mean Shift迭代次數，見表1。從表1可以看出，本文算法可以減少跟蹤過程中Mean Shift的迭代次數，從而減少跟蹤的過程中的運算。

表1 兩種算法Mean Shift迭代次數比較

4.2 在復雜情況下的行人跟蹤實驗

實驗采集某銀行的監控視頻，對在光照變化和顏色干擾的情況下，分別通過原始的Mean Shift算法和本文算法對行人進行跟蹤。

圖3為使用傳統的Mean Shift算法對行人進行跟蹤，圖3 （a）第10幀圖為初始狀態圖，手動圈定跟蹤的目標和跟蹤的范圍，第18幀圖和第42幀中有相似顏色和光照變化的干擾，原始的Mean Shift算法跟蹤性能降低，導致跟蹤目標丟失。

圖3 Mean Shift算法結果

本文算法跟蹤結果如圖4所示。

圖4 本文算法跟蹤結果

表2是從10幀到60幀中選取5幀，每幀間隔為10幀，對中心誤距離進行統計，得出兩種算法在相應幀的中心距離誤差，該結果與上面的實驗圖相對應。

表2 兩種算法中心誤差距離對比

本文算法由于動態融合顏色特征和邊緣特征，當出現顏色相似干擾和光照條件變化時，由式 （12）、式 （13）可知，邊緣特征的Bhattacharrya系數將增大，此時該算法以邊緣特征為主來跟蹤目標，受相似顏色干擾的影響就減小，能保持良好的跟蹤性能。

5 結束語

本文針對Mean Sihft算法在跟蹤方面的缺陷，在MMS跟蹤算法的基礎上引入運動矢量來預測運動目標在下一幀中的位置，解決運動過快導致跟蹤目標丟失的缺陷，同時減少了算法的迭代次數；多特征融合解決了顏色干擾和光照變化對跟蹤效果影響的問題。實驗結果表明，該算法具有較強的魯棒性。由于本文采用的是固定窗寬來跟蹤目標，為了防止目標運動過快而使跟蹤窗口內的顏色特征和邊緣特征變化過大，即便采用運動矢量做預測也無法使Mean Shift跟蹤算法收斂，故在目標運動過快時，需要限制窗寬的大小。下一步，可以考慮采用自適應變窗寬的方法，解決本文算法的不足。

［1］WANG Wenjang，HUANG Shan，ZHANG Hongbin.Band－Width－adaptivate tracking algorithm based on Mean Shift and Kalman prediction ［J］.Computer Engineering ＆ Science，2013，35 （5）：87－92 （in Chinese）. ［王文江，黃山，張紅斌.一種基于Mean Shift和Kalman 預測的帶寬自適應算法［J］.計算機科學與工程，2013，35 （5）：87－92.］

［2］LI Ning，ZHOU Jianjiang，ZHAO Xingxing.Moving object tracking in dynaminc image sequence based on estimation of motion vectors of feature points［J］.Transactions of Nanjing University of Aeronautics ＆Astronautics，2009，26 （4）：295－300.

［3］HU Bo.Research on video object tracking technology based on Mean－Shift algorithm and Kalman filter［D］.Ningbo：Ningbo University，2010（in Chinese）.［胡波.基于Mean－shift算法和卡爾曼濾波的視頻目標跟蹤技術研究［D］.寧波：寧波大學，2010.］

［4］ZHENG Yufeng，MA Xiurong，ZHAO Xiaolin，et.al.Mean shift target tracking algorithm based on color and edge features［J］.Journal of Optoelectronics Laser，2011，22 （8）：1231－1235 （in Chinese）. ［鄭玉鳳，馬秀榮，趙曉琳，等.基于顏色和邊緣特征的均值遷移目標跟蹤算法 ［J］.光電子激光，2011，22 （8）：1231－1235.］

［5］TIAN Wei.The summary of object tracking ［D］.Shenyang：Northeast University，2011 （in Chinese）. ［田維.目標跟蹤綜述 ［D］.沈陽：東北大學，2011.］

［6］Tang Da，Zhang Yujin.Combing Mean－shift and particle filter for object tracking ［C］／／Proc of the 6th Int’l Conf on Image and Graphic，2011：771－776.

［7］SONG Yuqing，YUE Dongpeng.Multi－feature fusion for video object tracking ［C］／／Fifth International Conference on Intelligent Net－Works and Intelligent Systems.IEEE，2012：33－36.

［8］HAN Ping，XU Jianlong，WU Renbiao.New feature fusion method for target tracking ［J］.Journal of Civil Aviation University of China，2010，28 （4）：21－26 （in Chinese）.［韓萍，徐建龍，吳仁彪.一種新的目標跟蹤特征融合方法 ［J］.中國名航大學學報，2010，28 （4）：21－26.］

［9］LIU Qing，TANG Linbo，ZHAO Baojun，et al.Improved mean shift target tracking algorithm ［J］.Systems Engineering and Electronics，2013，35 （6）：1318－1323 （in Chinese）.［劉晴，唐林波，趙寶軍，等.改進的mean shift目標跟蹤算法［J］.系統工程與電子技術，2013，35 （6）：1318－1323.］

［10］LI Ning，ZHOU Jianjiang，ZHAO Xingxing.Moving object tracking in dynaminc image sequence based on estimation of motion vectors of feature points［J］.Transactions of Nanjing University of Aeronautics ＆Astronautics，2009，26 （4）：295－300.

［11］WANG Honglin，YANG Bo，TIAN Guodong，et al.Object tracking by applying mean－shift algorithm into particle filtering ［C］／／Proceeding of ICBNMT，2009：550－554.