李道凱，原 達(dá)，王曉靜

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014；2.山東工商學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 煙臺(tái)264005）

0 引 言

Mean shift算法［1－4］由于運(yùn)算速度快、簡(jiǎn)單易實(shí)現(xiàn)和魯棒性等優(yōu)點(diǎn)，在目標(biāo)跟蹤領(lǐng)域受到廣泛關(guān)注。1975年，F(xiàn)ukunaga等人在一篇關(guān)于概率密度梯度函數(shù)估計(jì)的文中提出了 Mean shift概念。1995年，Yizong Cheng改進(jìn)了基本的Mean shift算法，擴(kuò)大了 Mean shift算法的適用范圍。Comaniciu和Meer將Mean shift算法應(yīng)用到目標(biāo)跟蹤領(lǐng)域并取得成功。Mean shift算法使用核直方圖描述目標(biāo)［5］，對(duì)目標(biāo)的形變和旋轉(zhuǎn)變化、部分遮擋等具有較強(qiáng)的魯棒性。然而，當(dāng)目標(biāo)運(yùn)動(dòng)速度過(guò)快或場(chǎng)景、光照變換導(dǎo)致顏色突變或有嚴(yán)重遮擋［6］時(shí)，往往容易出現(xiàn)定位偏差較大甚至跟蹤丟失現(xiàn)象。目前一般采用的解決方法使用卡爾曼濾波或粒子濾波等濾波算法對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行位置預(yù)測(cè)，然后結(jié)合 Mean shift搜索確定目標(biāo)最終位置。文獻(xiàn) ［7－8］采用Mean shift和粒子濾波算法相融合的方法跟蹤運(yùn)動(dòng)目標(biāo)。文獻(xiàn) ［9－11］提出 Mean shift和Kalman濾波相結(jié)合的目標(biāo)跟蹤算法。文獻(xiàn) ［12］提出基于卡爾曼濾波及粒子濾波的目標(biāo)跟蹤算法。這些方法能夠達(dá)到期望的跟蹤效果，但由于需要進(jìn)行比較復(fù)雜的濾波運(yùn)算，使得計(jì)算效率受到影響。本文提出一種基于 Mean shift和軌跡預(yù)測(cè)［13－16］的目標(biāo)跟蹤算法。首先根據(jù)運(yùn)動(dòng)目標(biāo)已知位置信息采用最小二乘法擬合出運(yùn)動(dòng)軌跡，得到運(yùn)動(dòng)目標(biāo)的預(yù)測(cè)位置，然后Mean shift以此位置為中心搜索目標(biāo)最終位置。實(shí)驗(yàn)表明，該算法能夠準(zhǔn)確地跟蹤快速運(yùn)動(dòng)目標(biāo)，對(duì)遮擋具有較強(qiáng)的魯棒性。

1 模型表述

Mean Shift算法是一種密度梯度的無(wú)參估計(jì)方法［17］，該算法經(jīng)過(guò)幾次迭代快速收斂到相似性函數(shù)的極大值點(diǎn)。首先選擇顏色特征空間來(lái)描述跟蹤目標(biāo)，用目標(biāo)概率密度函數(shù)q來(lái)描述目標(biāo)模型。當(dāng)前幀圖像中的候選目標(biāo)，我們用概率密度函數(shù)p（y）來(lái)描述。為了確保較低的計(jì)算代價(jià)，選用顏色特征直方圖進(jìn)行概率密度估計(jì)。兩個(gè)模型q和p的相似程度用ρ（y）≡ρ（p（y），q）表示。

1.1 目標(biāo)模型

通過(guò)手工方式選擇要跟蹤的目標(biāo)區(qū)域，該區(qū)域是以x0為中心，以h為邊長(zhǎng)的矩形區(qū)域。假設(shè)目標(biāo)區(qū)域顏色空間被均勻分成m個(gè)特征區(qū)間，用該區(qū)域上的所有特征值的概率值來(lái)描述目標(biāo)模型。用直方圖估計(jì)的每一個(gè)特征值u的概率密度為

式中：C——一個(gè)標(biāo)準(zhǔn)化的常量系數(shù)；x0——搜索窗口中心像素坐標(biāo)，xi——第i個(gè)像素坐標(biāo)；k（·）——核函數(shù)；δ［b（xi）－μ］的作用是判斷xi的顏色值是否屬于特征值μ，若等于，值為1，否則為0。

1.2 候選模型

當(dāng)前幀圖像中可能包含目標(biāo)的區(qū)域稱(chēng)為候選區(qū)域，對(duì)候選區(qū)域的描述稱(chēng)為目標(biāo)候選模型。以y為中心，候選模型的特征值μ的概率密度為

1.3 相似性函數(shù)

使用Bhattacharyya系數(shù)作為相似性函數(shù)來(lái)描述目標(biāo)模型和候選模型的相似程度，定義如下

兩個(gè)模型的相似程度跟ρ（y）值成正比。使相似性函數(shù)最大的候選區(qū)域即是當(dāng)前幀目標(biāo)所在區(qū)域。

2 軌跡預(yù)測(cè)和Mean shift算法

2.1 基于最小二乘法的軌跡預(yù)測(cè)

基于最小二乘法［14，16］的軌跡預(yù)測(cè)算法是一種簡(jiǎn)單實(shí)用的預(yù)測(cè)算法，能夠快速準(zhǔn)確地對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行位置預(yù)測(cè)。首先應(yīng)確定前r幀序列圖像中目標(biāo)的中心位置。目標(biāo)中心位置的確定可采用兩種方式：一是手工獲取被跟蹤目標(biāo)的中心位置；二是采用Mean shift跟蹤算法得到的目標(biāo)位置作為中心位置。

已知前r個(gè)目標(biāo)位置（xi，yi），i＝1，2，…，r，根據(jù)最小二乘準(zhǔn)則，選定的擬合函數(shù)應(yīng)使得擬合誤差（目標(biāo)實(shí)際位置到曲線的距離di）的平方和D最小，即使得式（4）最小

其中

為擬合函數(shù)，ɑk（k＝0，1，…，s）為待定系數(shù)。問(wèn)題歸結(jié)為求待定系數(shù)使得D取最小值。根據(jù)多元函數(shù)求極值的必要條件：函數(shù)在某點(diǎn)具有偏導(dǎo)數(shù)且偏導(dǎo)數(shù)為零，得

上式轉(zhuǎn)化為

其矩陣形式如下

對(duì)上式求解得函數(shù)的系數(shù)a0，a1，…，as，從而得到目標(biāo)運(yùn)動(dòng)軌跡（如式（5）所示）。

設(shè)T為采樣周期，目標(biāo)在hT時(shí)刻的位置為 ［x（h），y（h）］，分別預(yù)測(cè)目標(biāo)在（h＋1）T時(shí)刻在X 和Y方向上的位置分量。算法步驟如下：

（1）確定采樣數(shù)據(jù)

（2）根據(jù)X方向上的位置分量SX＝｛［（h－r＋l）T，x（h－r＋l）］｜l＝1，…，r｝，由式（5）和式（8）得出X 方向目標(biāo)運(yùn)動(dòng)軌跡x＝Fs（t），計(jì)算目標(biāo)的X方向的預(yù)測(cè)位置xF（h＋1）。

（3）根據(jù)Y 方向上的位置分量SY＝｛［（h－r＋l）T，y（hr＋l）］｜l＝1，…，r｝，由式（5）和式（8）得到Y(jié) 方向目標(biāo)運(yùn)動(dòng)軌跡y＝Fs（t），計(jì)算目標(biāo)在Y 方向上的預(yù)測(cè)位置yF（h＋1）。

（4）輸出（h＋1）T時(shí)刻目標(biāo)的預(yù)測(cè)位置yf：［xF（h＋1），yF（h＋1）］。

2.2 Mean shift跟蹤算法

Mean shift算法是一種無(wú)參密度估計(jì)算法，通過(guò)迭代計(jì)算相似性函數(shù)最大值，搜索當(dāng)前幀中與目標(biāo)模型最相似的候選目標(biāo)，實(shí)現(xiàn)目標(biāo)跟蹤。算法步驟如下：

已知目標(biāo)模型 ｛qu｝u＝1，2，…，m和預(yù)測(cè)位置y0。

（1）初 始 化 當(dāng) 前 幀 的 目 標(biāo) 位 置 y0，計(jì) 算 ｛pu（y0）｝u＝1，2，…，m和

（3）確定候選目標(biāo)的新位置

（4） 計(jì) 算 ｛pu（y）｝u＝1，2，…，m和 ρ（p（y），q）＝

（5）若ρ（p（y），q）＜ρ（p（y0），q），令y←（y0＋y）/2，重新計(jì)算ρ（p（y），q）。

（6）若 y－y0＜ε，則結(jié)束；否則，令y0←y，返回（1）。

3 基于Mean shift和軌跡預(yù)測(cè)的目標(biāo)跟蹤

Mean shift算法具有實(shí)時(shí)性、魯棒性和執(zhí)行效率高等特點(diǎn)，但迭代過(guò)程中容易陷入局部最優(yōu)值，且如果運(yùn)動(dòng)目標(biāo)的速度過(guò)快或出現(xiàn)嚴(yán)重遮擋情況，則該算法的跟蹤效果就會(huì)受到影響，無(wú)法實(shí)現(xiàn)準(zhǔn)確跟蹤。基于最小二乘法的軌跡預(yù)測(cè)方法運(yùn)算簡(jiǎn)單且能準(zhǔn)確預(yù)測(cè)運(yùn)動(dòng)目標(biāo)位置，從而縮小了目標(biāo)跟蹤算法的搜索范圍，提高搜索效率。因此本文將兩種算法結(jié)合，根據(jù)已知的前r個(gè)目標(biāo)位置，采用最小二乘法擬合出目標(biāo)運(yùn)動(dòng)軌跡，進(jìn)而得到運(yùn)動(dòng)目標(biāo)的預(yù)測(cè)位置，然后Mean shift算法以預(yù)測(cè)位置為起始位置，在其鄰域內(nèi)搜索目標(biāo)最終位置。該算法對(duì)快速運(yùn)動(dòng)目標(biāo)和場(chǎng)景中存在的光照變化、嚴(yán)重遮擋等影響因素有較強(qiáng)的魯棒性。

對(duì)于嚴(yán)重遮擋的問(wèn)題，由于目標(biāo)運(yùn)動(dòng)的連續(xù)性和規(guī)律性，采用軌跡預(yù)測(cè)算法不會(huì)出現(xiàn)較大偏差，與之相反，Mean shift算法卻不能得出正確的目標(biāo)位置。此時(shí)，采用預(yù)測(cè)位置更新算法輸出的最終位置。本文采用搜索誤差（算法輸出的目標(biāo)位置（yX，yY）和預(yù)測(cè)位置 ［xF（h＋1），yF（h＋1）］之間的距離）來(lái)作為更新評(píng)價(jià)標(biāo)準(zhǔn)，定義為

正常情況下，算法得到的最終位置和預(yù)測(cè)位置很接近，δ較小。當(dāng)出現(xiàn)嚴(yán)重遮擋問(wèn)題時(shí)，Mean shift以預(yù)測(cè)位置為起始點(diǎn)迭代搜索到的目標(biāo)位置可能會(huì)遠(yuǎn)離起始點(diǎn)，此時(shí)的δ值會(huì)遠(yuǎn)大于平時(shí)的δ值。因此，我們?cè)O(shè)置一個(gè)閾值a＝10，若δ＞a，則采用預(yù)測(cè)位置yf來(lái)代替算法輸出的目標(biāo)位置。

本文改進(jìn)的跟蹤算法步驟如下：

（1）初始化當(dāng)前時(shí)刻及目標(biāo)位置；

（2）讀取圖像，根據(jù)軌跡預(yù)測(cè)算法得到目標(biāo)預(yù)測(cè)位置yf，將yf賦給y0。

（3）用 Mean shift算法計(jì)算目標(biāo)位置y。

（4）利用式（9）計(jì)算搜索誤差δ，若δ＜a，則以y作為最終位置；否則，用預(yù)測(cè)位置yf作為目標(biāo)最終位置。

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

為了驗(yàn)證本文算法的跟蹤效果，通過(guò)道路交通視頻序列和足球運(yùn)動(dòng)員視頻序列對(duì)本文算法進(jìn)行實(shí)驗(yàn)，分別驗(yàn)證算法對(duì)快速運(yùn)動(dòng)目標(biāo)和被遮擋目標(biāo)的跟蹤效果，并與Mean shift跟蹤算法結(jié)果進(jìn)行比較。實(shí)驗(yàn)環(huán)境：Intel Pentium Dual Core E5300的 CPU，1G 內(nèi)存，Windows XP系統(tǒng)，用Matlab 7.0編程實(shí)現(xiàn)。圖1為 Mean shift算法的跟蹤結(jié)果，如第3、6、9、12、14、16幀圖片所示。從第9幀開(kāi)始，該算法跟蹤效果就開(kāi)始受到影響，出現(xiàn)偏差問(wèn)題，到第16幀時(shí)，算法給出的目標(biāo)中心位置已經(jīng)嚴(yán)重偏離目標(biāo)實(shí)際位置。圖2為本文算法的跟蹤結(jié)果，本文算法選取s＝3，r＝6。從圖2中可知，本文算法不僅在前8幀具有良好跟蹤效果，而且在第9幀以后仍能夠很好地跟蹤目標(biāo)，到16幀時(shí)能夠準(zhǔn)確定位目標(biāo)實(shí)際位置。圖1和圖2兩種算法的誤差分析見(jiàn)表1，其中M位置表示傳統(tǒng) Mean shift算法得到的目標(biāo)位置，N表示本文新算法得到的目標(biāo)位置；dm表示M位置和實(shí)際位置之間的距離，dn表示N位置和實(shí)際位置之間的距離。由表1的誤差分析可知，dn遠(yuǎn)小于dm，這表明本文算法的定位誤差明顯小于傳統(tǒng) Mean shift跟蹤算法，即本文算法的定位精度大大高于傳統(tǒng)Mean shift跟蹤算法，本文算法更具可靠性。圖3為本文算法對(duì)遮擋問(wèn)題的處理結(jié)果，從第7幀開(kāi)始，有運(yùn)動(dòng)員擋住目標(biāo)運(yùn)動(dòng)員，如第7、9、11幀所示，但跟蹤算法并不受遮擋因素的影響，到視頻序列結(jié)束，算法能準(zhǔn)確定位實(shí)際目標(biāo)，成功實(shí)現(xiàn)跟蹤。

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

5 結(jié)束語(yǔ)

本文針對(duì)目標(biāo)跟蹤中的定位偏差問(wèn)題進(jìn)行研究，提出了Mean shift算法和軌跡預(yù)測(cè)相結(jié)合的運(yùn)動(dòng)目標(biāo)跟蹤算法。在Mean shift搜索之前，先用軌跡預(yù)測(cè)算法得到目標(biāo)的預(yù)測(cè)位置，然后再用Meanshift算法搜索目標(biāo)的最終位置。文中給出了對(duì)嚴(yán)重遮擋問(wèn)題的判斷方法和處理措施。通過(guò)實(shí)驗(yàn)對(duì)本文提出的新算法進(jìn)行了檢驗(yàn)，并將跟蹤結(jié)果與Mean shift算法進(jìn)行比較。實(shí)驗(yàn)表明本文算法對(duì)跟蹤過(guò)程中的定位偏差問(wèn)題有較強(qiáng)的魯棒性，克服了目標(biāo)運(yùn)動(dòng)速度過(guò)快和場(chǎng)景出現(xiàn)嚴(yán)重遮擋等情況對(duì)跟蹤效果的影響，實(shí)現(xiàn)了快速運(yùn)動(dòng)目標(biāo)的準(zhǔn)確跟蹤。由于本文只是對(duì)小型車(chē)輛的快速運(yùn)動(dòng)和足球運(yùn)動(dòng)員被遮擋情況引發(fā)的定位偏差問(wèn)題進(jìn)行了實(shí)驗(yàn)，因此以后的工作中還將對(duì)各種運(yùn)動(dòng)物體的定位偏差問(wèn)題進(jìn)行研究。并對(duì)目標(biāo)軌跡預(yù)測(cè)方法進(jìn)一步優(yōu)化，建立多種預(yù)測(cè)方法結(jié)合的軌跡預(yù)測(cè)模型，提高軌跡預(yù)測(cè)效率。

圖2 本文算法針對(duì)快速運(yùn)動(dòng)目標(biāo)的跟蹤結(jié)果

圖3 本文算法在運(yùn)動(dòng)目標(biāo)被遮擋時(shí)的跟蹤結(jié)果

表1 本文算法和Mean shift算法的誤差分析

［1］Amir Babaeian，Saeed Rastegar，Mojtaba Bandarabadi，et al.Mean shift－based object tracking with multiple features ［C］.41st Southeastern Symposium on System Theory.Tullahoma：IEEE Press，2009：68－72.

［2］LIN Qing，CHEN Yuanxiang，WANG Shitong，et al.Meanshift tracking algorithm with adaptive bandwidth of target ［J］.Journal of Computer Applications，2008，29（12）：3329－3331（in Chinese）.［林慶，陳遠(yuǎn)祥，王士同，等.目標(biāo)窗口尺寸自適應(yīng)變化的 Mean－shift跟蹤算法 ［J］.計(jì)算機(jī)應(yīng)用，2008，29（12）：3329－3331.］

［3］LI Peihua.An improved Mean Shift algorithm for object tracking［J］.Acta Automatica Sinica，2007，33（4）：347－354（in Chinese）.［李培華.一種改進(jìn)的Mean Shift跟蹤算法 ［J］.自動(dòng)化學(xué)報(bào)，2007，33（4）：347－354.］

［4］YUAN Guanglin，XUE Mogen，HAN Yusheng，et al.Mean shift object tracking based on adaptive multi－features fusion［J］.Journal of Computer Research and Development，2010，47（9）：1663－1671（in Chinese）.［袁廣林，薛模根，韓裕生，等.基于自適應(yīng)多特征融合的 Mean shift目標(biāo)跟蹤 ［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（9）：1663－1671.］

［5］PENG Ningsong，YANG Jie，LIU Zhi，et al.Automatic selection of kernel－bandwidth for Mean－Shift object tracking ［J］.Journal of Software，2005，16（9）：1542－1550（in Chinese）.［彭寧嵩，楊杰，劉志，等.Mean－Shift跟蹤算法中核函數(shù)窗寬的自動(dòng)選取 ［J］.軟件學(xué)報(bào)，2005，16（9）：1542－1550.］

［6］ZHENG Kebiao，HUANG Wenqing，ZHANG Zuoli，et al.Occlusion handling in moving object tracking system ［J］.Computer Engineering and Design，2009，30（11）：2816－2818（in Chinese）.［鄭可彪，黃文清，張佐理，等.運(yùn)動(dòng)目標(biāo)跟蹤系統(tǒng)的遮擋問(wèn)題處理 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（11）：2816－2818.］

［7］CHEN Aihua，MENG bo，ZHU Ming，et al.Multi－pattern fusion algorithm for target tracking ［J］.Optics and Precision Engineering，2009，17（1）：185－190（in Chinese）.［陳愛(ài)華，孟勃，朱明，等.多模式融合的目標(biāo)跟蹤算法 ［J］.光學(xué)精密工程，2009，17（1）：185－190.］

［8］JIANG Min，XU Qin，SHANG Tao，et al.Tracking algorithm based on particle filtering and Mean－shift ［J］.Computer Engineering，2010，36（5）：21－22（in Chinese）.［蔣旻，許勤，尚濤，等.基于粒子濾波和 Mean－shift的跟蹤算法 ［J］.計(jì)算機(jī)工程，2010，36（5）：21－22.］

［9］OU Yangning，YOU Jinhai，MO Jianwen，et al.Tracking multiple objects in occlusions ［J］.Application Research of Computers，2010，27（5）：1984－1986（in Chinese）.［歐陽(yáng)寧，游錦海，莫建文，等.遮擋情況下的多目標(biāo)跟蹤算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（5）：1984－1986.］

［10］ WANG Jiangtao，YANG Jingyu.Object tracking based on Kalman－Mean Shift in occlusions ［J］.Journal of System Simulation，2007，19（18）：4216－4220（in Chinese）.［王江濤，楊靖宇.遮擋情況下基于Kalman均值偏移的目標(biāo)跟蹤［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19（18）：4216－4220.］

［11］WANG Zhanqing，F(xiàn)AN Youfu，ZHANG Guilin.Roubust algorithm for occlusion problem in tracking ［J］.Computer Engineering and Applications，2007，43（27）：50－53（in Chinese）.［王展青，凡友福，張桂林.跟蹤遮擋目標(biāo)的一種魯棒算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（27）：50－53.］

［12］DU Chao，LIU Weining，LIU Lian.Target tracking algorithm based on Kalman filter and particle filter ［J］.Chinese Journal of Crystals and Displays，2011，26（3）：384－389（in Chinese）.［杜超，劉偉寧，劉戀.一種基于卡爾曼濾波及粒子濾波的目標(biāo)跟蹤算法 ［J］.液晶與顯示，2011，26（3）：384－389.］

［13］Kim S W，Won J I，Kim J D，et al.Path prediction of moving objects on road networks through analyzing past trajectories［C］.Proc of the 11th Int’1Conf on Knowledge－Based Intelligent Information and Engineering Systems.Berlin：Springer－Verlag，2007：379－389.

［14］LIU Wenying，WU Qing，YANG Yihan.Power system perturbed trajectory online prediction method based on improved least squares support vector machine ［J］.Journal of North China Electric Power University，2008，35（3）：6－11（in Chinese）.［劉文穎，吳瓊，楊以涵.基于改進(jìn)最小二乘法支持向量機(jī)的電力系統(tǒng)受擾軌跡在線預(yù)測(cè) ［J］.華北電力大學(xué)學(xué)報(bào)，2008，35（3）：6－11.］

［15］PENG Qu，DING Zhiming，GUO Limin.Prediction of trajectory based on markov chains ［J］.Computer Science，2010，37（8）：189－193（in Chinese）.［彭曲，丁治明，郭黎敏.基于馬爾可夫鏈的軌跡預(yù)測(cè) ［J］.計(jì)算機(jī)科學(xué)，2010，37（8）：189－193.］

［16］ZHONG Jiandong，SU Jianbo.A real－time moving object tracking system based on visual prediction ［J］.Robot，2010，32（4）：516－521（in Chinese）.［鐘建冬，蘇劍波.基于視覺(jué)預(yù)測(cè)的運(yùn)動(dòng)目標(biāo)實(shí)時(shí)跟蹤系統(tǒng) ［J］.機(jī)器人，2010，32（4）：516－521.］

［17］ZHU Shengli，ZHU Shanan，LI Xuchao.Algorithm for tracking of fast motion objects with Mean shift ［J］. Opto－Electronic Engineering，2006，33（5）：66－70（in Chinese）.［朱勝利，朱善安，李旭超.快速運(yùn)動(dòng)目標(biāo)的Mean shift跟蹤算法 ［J］.光電工程，2006，33（5）：66－70.］