基于Mean Shift多特征融合跟蹤的改進(jìn)算法

雷 川，黃 山，，張洪斌

（1.四川大學(xué) 電氣信息學(xué)院，四川 成都610065；2.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065）

0 引 言

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

傳統(tǒng)的Mean Shift算法存在當(dāng)跟蹤快速運(yùn)動(dòng)目標(biāo)和亮度環(huán)境改變過快或跟蹤目標(biāo)長時(shí)間變暗時(shí)，跟蹤性能變差的缺陷的問題。上述兩種改進(jìn)算法增加了算法的復(fù)雜程度、迭代次數(shù)，影響跟蹤的實(shí)時(shí)性。本文在分析算法跟蹤缺陷的基礎(chǔ)上，結(jié)合運(yùn)動(dòng)矢量，融合顏色特征和邊緣特征，提出了一種改進(jìn)的Mean Shift跟蹤算法。實(shí)驗(yàn)驗(yàn)證了該算法的良好效果。

1 傳統(tǒng)算法描述

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

1.1 Mean Shift跟蹤算法

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

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

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

其中

計(jì)算y1－y0，如果 y1－y0＜ε則停止迭代，目標(biāo)的中心由y1代替y0，每次迭代都可以從y0中得到一個(gè)新的位置y1

如此，運(yùn)動(dòng)目標(biāo)從原始的位置逐漸調(diào)整到當(dāng)前位置，實(shí)現(xiàn)對(duì)目標(biāo)的跟蹤。

1.2 邊緣特征

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

1.1節(jié)表明Mean Shift跟蹤算法根據(jù)顏色直方圖對(duì)目標(biāo)建模，使相似性度量Bhattaharry系數(shù)最大來確定運(yùn)動(dòng)目標(biāo)在下一幀中的位置，從而實(shí)現(xiàn)目標(biāo)的跟蹤。類似的，可以提取目標(biāo)邊緣的直方圖來描述運(yùn)動(dòng)目標(biāo)。

目標(biāo)模型的邊緣直方圖由下式表示

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

Bhattacharrya系數(shù)

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

2 運(yùn)動(dòng)矢量

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

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

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

3 本文算法

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

步驟1 運(yùn)動(dòng)矢量預(yù)測(cè)：在第一幀中初始化目標(biāo)中心y0，在下一幀中通過運(yùn)動(dòng)矢量預(yù)測(cè)在當(dāng)前幀中的候選區(qū)域中心y′0，計(jì)算y′0的公式如下）

式中：α∈（0，1），與目標(biāo)的運(yùn)動(dòng)速度成反比。

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

其中

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

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

4 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文算法的有效性，作者對(duì)快速運(yùn)動(dòng)的行人和復(fù)雜環(huán)境中運(yùn)動(dòng)的行人進(jìn)行了實(shí)驗(yàn)。本文中的實(shí)驗(yàn)使用的計(jì)算機(jī)硬件配置為Intel Core2 2.4GHz CPU，2G RAM），軟件環(huán)境為Windows XP操作系統(tǒng)，VS2010，Opencv2.4.8軟件編程環(huán)境。

4.1 針對(duì)快速運(yùn)動(dòng)的行人的實(shí)驗(yàn)

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

圖1 MMS算法跟蹤結(jié)果

由上述實(shí)驗(yàn)結(jié)果可知，由于物體運(yùn)動(dòng)速度較快MMS跟蹤算法無法預(yù)測(cè)到下一幀運(yùn)動(dòng)目標(biāo)的位置，圖1中第55幀圖，逐漸開始丟失目標(biāo)，第88幀圖，該算法已經(jīng)完全丟失對(duì)運(yùn)動(dòng)目標(biāo)的跟蹤。

本文算法跟蹤結(jié)果如圖2所示。

圖2 本文算法跟蹤結(jié)果

上述實(shí)驗(yàn)采用本文跟蹤算法的實(shí)驗(yàn)結(jié)果，初始狀態(tài)圖依然選取第26幀，依然是選取第55幀圖和第88幀圖的跟蹤結(jié)果圖與MSS跟蹤算法的跟蹤效果作對(duì)比，由于本文算法引入了運(yùn)動(dòng)矢量為運(yùn)動(dòng)目標(biāo)下一幀的位置做預(yù)測(cè)，故在目標(biāo)運(yùn)動(dòng)速度較快時(shí)也能有較好的跟蹤性能，第55幀圖和第88幀圖的跟蹤結(jié)果說明了這一點(diǎn)。同時(shí)，運(yùn)動(dòng)矢量的引入也減少了Mean Shift的迭代次數(shù)。

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

表1 兩種算法Mean Shift迭代次數(shù)比較

4.2 在復(fù)雜情況下的行人跟蹤實(shí)驗(yàn)

實(shí)驗(yàn)采集某銀行的監(jiān)控視頻，對(duì)在光照變化和顏色干擾的情況下，分別通過原始的Mean Shift算法和本文算法對(duì)行人進(jìn)行跟蹤。

圖3為使用傳統(tǒng)的Mean Shift算法對(duì)行人進(jìn)行跟蹤，圖3 （a）第10幀圖為初始狀態(tài)圖，手動(dòng)圈定跟蹤的目標(biāo)和跟蹤的范圍，第18幀圖和第42幀中有相似顏色和光照變化的干擾，原始的Mean Shift算法跟蹤性能降低，導(dǎo)致跟蹤目標(biāo)丟失。

圖3 Mean Shift算法結(jié)果

本文算法跟蹤結(jié)果如圖4所示。

圖4 本文算法跟蹤結(jié)果

表2是從10幀到60幀中選取5幀，每幀間隔為10幀，對(duì)中心誤距離進(jìn)行統(tǒng)計(jì)，得出兩種算法在相應(yīng)幀的中心距離誤差，該結(jié)果與上面的實(shí)驗(yàn)圖相對(duì)應(yīng)。

表2 兩種算法中心誤差距離對(duì)比

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

5 結(jié)束語

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

［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 預(yù)測(cè)的帶寬自適應(yīng)算法［J］.計(jì)算機(jī)科學(xué)與工程，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算法和卡爾曼濾波的視頻目標(biāo)跟蹤技術(shù)研究［D］.寧波：寧波大學(xué)，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）. ［鄭玉鳳，馬秀榮，趙曉琳，等.基于顏色和邊緣特征的均值遷移目標(biāo)跟蹤算法 ［J］.光電子激光，2011，22 （8）：1231－1235.］

［5］TIAN Wei.The summary of object tracking ［D］.Shenyang：Northeast University，2011 （in Chinese）. ［田維.目標(biāo)跟蹤綜述 ［D］.沈陽：東北大學(xué)，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）.［韓萍，徐建龍，吳仁彪.一種新的目標(biāo)跟蹤特征融合方法 ［J］.中國名航大學(xué)學(xué)報(bào)，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）.［劉晴，唐林波，趙寶軍，等.改進(jìn)的mean shift目標(biāo)跟蹤算法［J］.系統(tǒng)工程與電子技術(shù)，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.