一種改進(jìn)的meanshift運(yùn)動(dòng)目標(biāo)跟蹤算法

趙 欣，陳 峰，吳立知

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽(yáng) 550025）

0 引言

運(yùn)動(dòng)目標(biāo)跟蹤是指在已知的視頻序列中檢測(cè)目標(biāo)的位置，形狀以及運(yùn)動(dòng)軌跡等時(shí)空變化特征。在眾多的目標(biāo)跟蹤算法中，meanshift算法由于其簡(jiǎn)單和魯棒性，近幾年受到了廣泛的關(guān)注，Cheng[1]在1995年首次將其引入圖像處理領(lǐng)域。Comaniciu等人[2]提出的meanshift跟蹤框架,計(jì)算復(fù)雜度低,對(duì)目標(biāo)的外表變化、噪聲、遮擋、尺度變化等具有一定的自適應(yīng)能力,成為目標(biāo)跟蹤算法研究的熱點(diǎn)。但是在meanshift算法的應(yīng)用過(guò)程中，通常是建立目標(biāo)模型和候選模型的顏色直方圖，然后通過(guò)比較兩模型的相似度來(lái)實(shí)現(xiàn)目標(biāo)跟蹤，很顯然，當(dāng)目標(biāo)顏色和背景顏色相似度較高時(shí)跟蹤算法的性能就會(huì)下降。同時(shí)meanshift算法本身缺少對(duì)目標(biāo)位置的預(yù)測(cè)機(jī)制，所以在目標(biāo)遭受較大比例遮擋時(shí)meanshift方法就會(huì)失效。

為了解決上述問(wèn)題，文中利用harris角點(diǎn)檢測(cè)提取表示目標(biāo)特征的角點(diǎn)，抑制背景特征對(duì)目標(biāo)的干擾，然后利用卡爾曼濾波器一方面預(yù)測(cè)目標(biāo)在下一幀中的位置；另一方面，通過(guò)分析卡爾曼濾波器關(guān)于目標(biāo)位置的估計(jì)值和由meanshift算法得到的卡爾曼濾波器的觀測(cè)值之間殘差的大小來(lái)判斷是否出現(xiàn)了大比例的遮擋，從而有效地解決遮擋問(wèn)題。

1 meanshift算法及其缺陷

meanshift跟蹤方法采用顏色直方圖對(duì)所選擇的目標(biāo)區(qū)域進(jìn)行建模。通過(guò)計(jì)算特征空間中每個(gè)特征值的概率來(lái)建立目標(biāo)模型，目標(biāo)模型的特征值u=1,2,…,m的概率密度由式（1）給出：，?是目標(biāo)模型，是第u個(gè)特征的概

率，k(x)是核函數(shù)的輪廓函數(shù)，C為標(biāo)準(zhǔn)化的常量系數(shù)。同樣，在后續(xù)幀中計(jì)算目標(biāo)候選模型的概率密度，由式(2)給出：

相似性函數(shù)()yρ⌒被用來(lái)度量目標(biāo)模型和當(dāng)前幀候選模型的相似性，它的值在0～1之間，其值越大，表示2個(gè)模型越相似。

通過(guò)求相似性函數(shù)最大得到關(guān)于目標(biāo)的 menashitf向量，這個(gè)向量即是目標(biāo)從初始位置向正確位置轉(zhuǎn)移的向量，由于maenshitf算法的收斂性，不斷迭代計(jì)算menashitf向量，在當(dāng)前幀中，最終會(huì)收斂到目標(biāo)的真實(shí)位置(一個(gè)靜止點(diǎn))，從而達(dá)到跟蹤的目的。

從分析可以看出mean shift的跟蹤主要是根據(jù)目標(biāo)顏色直方圖描述目標(biāo)的特征，當(dāng)背景和目標(biāo)顏色分布比較接近時(shí)，往往會(huì)導(dǎo)致目標(biāo)丟失。并且 menashitf向量在迭代的過(guò)程中沒(méi)有目標(biāo)運(yùn)動(dòng)軌跡的預(yù)測(cè)機(jī)制，致使迭代次數(shù)較多，跟蹤時(shí)實(shí)行比較差。當(dāng)目標(biāo)被遮擋時(shí)沒(méi)有判斷是否被遮擋的條件，也會(huì)導(dǎo)致跟蹤失敗。一個(gè)典型的例子如圖2(a)所示。

2 改進(jìn)的meanshift跟蹤算法

2.1 Harris角點(diǎn)檢測(cè)算法

Harris算法[3]是一種基于灰度圖像的點(diǎn)特征提取算法。在一幅圖像中，角點(diǎn)與自相關(guān)函數(shù)的曲率特性有關(guān)。自相關(guān)函數(shù)描述了局部圖像灰度的變化程度，可以表示為：

其中，E(x,y)是由于2個(gè)窗口偏移(x,y)而造成的圖像灰度的平均變化，Wu,v是圖像加權(quán)窗口，一般情況下窗口中心權(quán)值較大，窗口邊界處及其鄰域內(nèi)權(quán)值較小。在角點(diǎn)處，圖像窗口的偏移造成 E(x,y)的顯著變化，對(duì)它在任意像素點(diǎn)進(jìn)行泰勒展開，E(x,y)可近似表示成：

其中 T r(M)=A+B ,Det(M)=AB-C2，C是常量，一般取0.04既可以獲得比較好的效果，R (x,y)大于一個(gè)給定的閾值時(shí),即認(rèn)為相應(yīng)局部區(qū)域窗口的中心點(diǎn)是一個(gè)角點(diǎn)。對(duì)圖2(a)進(jìn)行Harris角點(diǎn)檢測(cè)的檢測(cè)結(jié)果如圖1所示。

圖1 對(duì)目標(biāo)和背景的harris角點(diǎn)檢測(cè)

2.2 卡爾曼濾波器在目標(biāo)跟蹤中的應(yīng)用

卡爾曼濾波器的主要作用是對(duì)運(yùn)動(dòng)目標(biāo)在下一幀中的位置進(jìn)行預(yù)測(cè)并且根據(jù)既得信息對(duì)目標(biāo)位置進(jìn)行修正。在預(yù)測(cè)部分利用當(dāng)前的狀態(tài)和誤差協(xié)方差估計(jì)下一時(shí)刻的狀態(tài)，得到先驗(yàn)估計(jì)，預(yù)測(cè)方程如下所示：

狀態(tài)預(yù)測(cè)方程：

誤差協(xié)方差預(yù)測(cè)方程：

在修正部分將實(shí)際觀測(cè)值與先驗(yàn)估計(jì)值放在一起考慮，從而獲得后驗(yàn)估計(jì)。這里H設(shè)為常量，sk為觀測(cè)值。

狀態(tài)修正方程：

誤差協(xié)方差修正方程：

2.3 融合了角點(diǎn)和卡爾曼濾波的算法

新算法利用 Harris檢測(cè)到的角點(diǎn)信息建立運(yùn)動(dòng)目標(biāo)的目標(biāo)模型[4-5]，meanshift向量迭代的過(guò)程中，只把這些角點(diǎn)作為跟蹤的關(guān)鍵點(diǎn)，目標(biāo)模型和背景之間就會(huì)有明顯的可分性，一方面能夠降低 meanshift的迭代次數(shù)，另一方面增強(qiáng)了原算法對(duì)目標(biāo)定位的準(zhǔn)確性。與此同時(shí)，在 meanshift向量迭代之前，利用卡爾曼濾波首先預(yù)測(cè)目標(biāo)在下一幀中的位置[6-7]，不但可以減小目標(biāo)的搜索范圍，同時(shí)可以有效地解決遮擋問(wèn)題。

算法的具體過(guò)程可以表述為：

①利用 Harris算法在定義的目標(biāo)區(qū)域中找出目標(biāo)的角點(diǎn)，并計(jì)算顏色直方圖，建立目標(biāo)模型?q。

②根據(jù)目標(biāo)以往的位置信息，通過(guò)式(7)預(yù)測(cè)當(dāng)前幀中目標(biāo)可能出現(xiàn)的位置。

③在目標(biāo)預(yù)測(cè)位置包括其鄰域內(nèi)初始化跟蹤目標(biāo)的位置y0。

④在以y0為中心的候選區(qū)域內(nèi)利用Harris算法提取區(qū)域內(nèi)的角點(diǎn)，計(jì)算角點(diǎn)的顏色直方圖，建立候選模型(y)。⌒

⑥從 y0開始進(jìn)行 meanshift向量迭代尋找最優(yōu)匹配目標(biāo)，直到找到目標(biāo)的真實(shí)位置y1，停止迭代。

⑦把 y1帶入式(8)的修正方程中，并且把此時(shí)的修正值作為下一幀中目標(biāo)位置預(yù)測(cè)的初始信息。

⑧重復(fù)以上步驟直到當(dāng)前幀為最后⌒一幀。⌒在以上的步驟中，當(dāng)前幀的估計(jì)值的位置分量(k )、(k)與觀測(cè)值 的2個(gè)分量x(k)、y(k)做差，得到殘差分量r(k)[8-9]：

設(shè)定門限值a，當(dāng)()rka＞時(shí)，目標(biāo)可能遇到大的遮擋，這時(shí)卡爾曼濾波器停止工作，直到()rka＜時(shí)卡爾曼濾波器再開始預(yù)測(cè)。

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

現(xiàn)通過(guò) 2個(gè)視頻對(duì)傳統(tǒng)算法和改進(jìn)算法性能進(jìn)行分析對(duì)比。首先，草坪上行走的行人，其衣服顏色和草坪的顏色很相近，在不存在外物遮擋時(shí)，RGB顏色模型下，量化空間為 16×16×16的視頻序列中，基于 matlab2008a對(duì)傳統(tǒng)的meanshift算法和加入角點(diǎn)的算法分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

從實(shí)驗(yàn)結(jié)果可以看出，沒(méi)有遮擋物存在的條件下，加入了角點(diǎn)以后的跟蹤方法跟蹤效果明顯優(yōu)于傳統(tǒng)的跟蹤方法，這說(shuō)明改進(jìn)算法在目標(biāo)和背景顏色相近時(shí)能很好的定位目標(biāo)。

第2個(gè)實(shí)驗(yàn)是在室內(nèi)進(jìn)行的，目標(biāo)顏色和背景色相近，并且有遮擋物存在，實(shí)驗(yàn)環(huán)境同第1個(gè)實(shí)驗(yàn)一樣在matlab2008a環(huán)境下進(jìn)行仿真，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖2 原始算法的跟蹤結(jié)果

圖3 加入角點(diǎn)后的算法跟蹤結(jié)果

圖5 加入了角點(diǎn)和卡爾曼濾波后的跟蹤算法

實(shí)驗(yàn)時(shí)取出視頻序列的第2、第14、第39、第51幀進(jìn)行對(duì)比，在改進(jìn)的算法中，由于算法對(duì)角點(diǎn)的閾值選擇并不敏感，所以此處取R=10就可以的到比較好的效果。

從對(duì)比結(jié)果可以看出，在圖4中當(dāng)目標(biāo)沒(méi)有被遮擋且背景色和目標(biāo)色相差較遠(yuǎn)時(shí)，傳統(tǒng)的meanshift算法具有良好的跟蹤效果，但是在從14幀開始，目標(biāo)被大面積遮擋，并且遮擋物的顏色與目標(biāo)顏色接近時(shí)，跟蹤效果明顯變差，直到第51幀時(shí)目標(biāo)定位完全出錯(cuò)。改進(jìn)算法用目標(biāo)角點(diǎn)作為跟蹤的關(guān)鍵點(diǎn)，抑制了背景色的干擾，同時(shí)用卡爾曼濾波預(yù)測(cè)目標(biāo)位置，解決了目標(biāo)被大面積遮擋時(shí)定位不準(zhǔn)的問(wèn)題，從演示結(jié)果圖5可以看出，改進(jìn)算法取得了比較好的跟蹤效果。

另一方面，改進(jìn)算法用少量關(guān)鍵點(diǎn)的直方圖信息作為目標(biāo)模板，并且利用卡爾曼濾波提前預(yù)測(cè)目標(biāo)在下一幀中的大致范圍，與傳統(tǒng)的 meanshift算法相比，不但減少了搜索時(shí)間，同時(shí)也縮小了搜索范圍。圖6顯示的結(jié)果表明，改進(jìn)算法跟蹤速度明顯優(yōu)于傳統(tǒng)算法。

圖6 處理每一幀圖片所需要的時(shí)間

4 結(jié)語(yǔ)

新算法結(jié)合 Harris角點(diǎn)檢測(cè)和卡爾曼濾波對(duì)傳統(tǒng)的meanshift算法進(jìn)行改進(jìn)，改進(jìn)的算法用少數(shù)的關(guān)鍵點(diǎn)來(lái)代替候選區(qū)域中的所有點(diǎn)，增強(qiáng)了目標(biāo)和背景的可分性[10]，同時(shí)利用卡爾曼濾波器原理預(yù)測(cè)目標(biāo)在下一幀中的位置，縮小了目標(biāo)的搜索范圍，減少了meanshift向量的迭代次數(shù)，改進(jìn)了meanshift算法在復(fù)雜環(huán)境下的跟蹤性能。文中給出了相應(yīng)的實(shí)驗(yàn)對(duì)原始算法和改進(jìn)算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果證明，改進(jìn)算法比傳統(tǒng)的算法具有更好的目標(biāo)定位性和實(shí)時(shí)性。

[1] CHENG Y.Mean Shift, Mode Seeking, and Clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 1995,17(08):790-799.

[2] COMANICIUD,RAMESHV,MEERP.Kernel-based Object Trac-king[J].IEEE Trans on Pattern Analalysis and Machine Intelli-gence,2003,25(05): 564-577.

[3] 張小洪,李博,楊丹.一種新的Harris多尺度角點(diǎn)檢測(cè)[J].電子與信息學(xué)報(bào), 2007,29(07): 1735-1738.

[4] 寧紀(jì)鋒,姜光,李鵬飛. 一種基于角點(diǎn)的 Mean Shift目標(biāo)跟蹤算法[J].計(jì)算機(jī)應(yīng)用研究, 2009,26(11): 4348-4350.

[5] 徐偉,王朔中.基于視頻圖像 Harris角點(diǎn)檢測(cè)的車輛測(cè)速[J].中國(guó)圖象圖形學(xué)報(bào), 2006,11(11): 1650-1652.

[6] 梁春迎,王國(guó)營(yíng). 基于運(yùn)動(dòng)統(tǒng)計(jì)和關(guān)鍵幀的視頻檢索方法[J].通信技術(shù)，2009,42(04)：162-164.

[7] 朱勝利，朱善安，李旭超.快速運(yùn)動(dòng)目標(biāo)的meanshift算法[J].光電工程, 2006,33(05): 65-70.

[8] LI P H,ZHANG T W,MA B.Unscented Kalman Filter for Visual Curve Tracking[J]. Image and Vision Computing,2004,22(02):157-164

[9] YILMAZA.Object Tracking by Asymmetric Kernel Mean Shift with Automatic Scale and Orientation Selection[C].USA: IEEE, 2007:1-6.

[10] 蔣欣欣,錢盛友. 基于FCM的彩色車牌圖像快速分割方法[J].通信技術(shù)，2011,44(03):66-67,79.