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

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

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

0 引 言

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

1 模型表述

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

1.1 目標(biāo)模型

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

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

1.2 候選模型

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

1.3 相似性函數(shù)

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

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

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

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

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

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

其中

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

上式轉(zhuǎn)化為

其矩陣形式如下

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

設(shè)T為采樣周期，目標(biāo)在hT時刻的位置為 ［x（h），y（h）］，分別預(yù)測目標(biāo)在（h＋1）T時刻在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)運動軌跡x＝Fs（t），計算目標(biāo)的X方向的預(yù)測位置xF（h＋1）。

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

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

2.2 Mean shift跟蹤算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

圖2 本文算法針對快速運動目標(biāo)的跟蹤結(jié)果

圖3 本文算法在運動目標(biāo)被遮擋時的跟蹤結(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ī)應(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］.自動化學(xué)報，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ī)研究與發(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ù)窗寬的自動選取 ［J］.軟件學(xué)報，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）.［鄭可彪，黃文清，張佐理，等.運動目標(biāo)跟蹤系統(tǒng)的遮擋問題處理 ［J］.計算機(jī)工程與設(shè)計，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）.［陳愛華，孟勃，朱明，等.多模式融合的目標(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ī)工程，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）.［歐陽寧，游錦海，莫建文，等.遮擋情況下的多目標(biāo)跟蹤算法 ［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é)報，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ī)工程與應(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ù)測 ［J］.華北電力大學(xué)學(xué)報，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ù)測 ［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）.［鐘建冬，蘇劍波.基于視覺預(yù)測的運動目標(biāo)實時跟蹤系統(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）.［朱勝利，朱善安，李旭超.快速運動目標(biāo)的Mean shift跟蹤算法 ［J］.光電工程，2006，33（5）：66－70.］