韋 迅，盧志茂，孫 海

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001)

目標(biāo)跟蹤廣泛應(yīng)用于區(qū)域監(jiān)控、交通控制、視頻壓縮和人機(jī)交互等領(lǐng)域.如何對視頻中感興趣的目標(biāo)進(jìn)行實(shí)時(shí)有效地跟蹤是目標(biāo)跟蹤的重點(diǎn)和難點(diǎn).目標(biāo)在運(yùn)動過程中存在著遮擋、放大、縮小、旋轉(zhuǎn)等情況，同時(shí)目標(biāo)運(yùn)動的環(huán)境中也會存在多種干擾，這就對跟蹤算法提出了很高的要求，不僅要求計(jì)算量小來滿足實(shí)時(shí)跟蹤，還要求適應(yīng)目標(biāo)和環(huán)境的變化.

由Fukunaga等人于1975年在文獻(xiàn)[1]中提出的均值漂移是一種高效的目標(biāo)跟蹤算法，Yizong Cheng對該算法進(jìn)行了改進(jìn)，Comaniciu等人把它應(yīng)用于目標(biāo)跟蹤中.均值漂移算法具有特征穩(wěn)定，能部分抗干擾，受目標(biāo)形狀變化影響小，能實(shí)現(xiàn)實(shí)時(shí)跟蹤等優(yōu)點(diǎn)，因此在目標(biāo)跟蹤中得到廣泛應(yīng)用.窗口寬度的選擇影響到算法的計(jì)算量，從而影響到跟蹤的實(shí)時(shí)性及有效性，因此，跟蹤算法中的核函數(shù)的窗口寬度對目標(biāo)跟蹤起著關(guān)鍵作用.均值漂移跟蹤算法是個(gè)半自動跟蹤算法，其核函數(shù)的窗口寬度是人為決定的，即在初始幀中選定跟蹤窗口寬度，且在目標(biāo)跟蹤過程中寬度不變.當(dāng)目標(biāo)變小時(shí)，跟蹤窗口相對較大，導(dǎo)致跟蹤窗口內(nèi)背景區(qū)域過多使跟蹤效果變差;當(dāng)目標(biāo)變大時(shí)，跟蹤窗口相對較小，跟蹤窗口內(nèi)的信息就減少，從而不能有效地進(jìn)行跟蹤甚至導(dǎo)致目標(biāo)消失.文獻(xiàn)[2]提出了對跟蹤框加減百分之十增量的方法，即在當(dāng)前幀中分別選擇相對于前一幀跟蹤窗口的90%、100%、110%來獨(dú)立計(jì)算Bhattacharyya系數(shù)，選擇最大的Bhattacharyya系數(shù)所對應(yīng)的窗口作為本幀中的跟蹤窗口.當(dāng)目標(biāo)變小時(shí)該算法對于跟蹤效果較好，但是目標(biāo)變大時(shí)，跟蹤窗口不僅不會變大，反而經(jīng)常變小，這是由Bhattacharyya系數(shù)的性質(zhì)決定的，它往往在跟蹤窗口較小時(shí)較大.文獻(xiàn)[3]基于Lindeberg理論，結(jié)合聯(lián)合DOG算子和Epanicinikov核，在跟蹤過程中不斷用DOG算子和搜索窗作卷積，運(yùn)算量非常大，影響了算法的實(shí)時(shí)性.文獻(xiàn)[4]利用角點(diǎn)匹配來選取核窗寬，不適合跟蹤目標(biāo)變小及目標(biāo)運(yùn)動過快的情況.文獻(xiàn)[5]采用均值漂移和連續(xù)兩幀中匹配窗口的最大相關(guān)系數(shù)來得到變換參數(shù)，同樣計(jì)算量大，很難滿足實(shí)時(shí)性要求.文獻(xiàn)[6]使用不變矩的帶寬估計(jì)方法，但矩陣特征的計(jì)算量大，影響跟蹤的實(shí)時(shí)性.文獻(xiàn)[7]提出一種基于運(yùn)動矢量分析的均值漂移算法，但是需要特定的硬件來支持.文獻(xiàn)[8]提出基于SIFT匹配的跟蹤算法，但是非常依賴目標(biāo)圖像的內(nèi)容和質(zhì)量.

本文針對現(xiàn)有算法的缺陷，提出了一種基于均值漂移自適應(yīng)跟蹤算法，根據(jù)候選目標(biāo)邊緣加權(quán)直方圖與模板中心加權(quán)直方圖計(jì)算出Bhattacharyya系數(shù)，通過Bhattacharyya系數(shù)來判斷目標(biāo)變化情況.若目標(biāo)變小或不變，則根據(jù)Bhattacharyya系數(shù)來確定目標(biāo)縮小的比例;若目標(biāo)變大，則采用形心定位和特征點(diǎn)仿射模型對跟蹤窗口進(jìn)行更新.實(shí)驗(yàn)表明，該算法能有效、實(shí)時(shí)地跟蹤大小變化的目標(biāo).

1 均值漂移算法

1.1 均值漂移向量

均值漂移算法是一種非參數(shù)概率估計(jì)算法，通過迭代的方式使每一個(gè)點(diǎn)朝著概率密度較大的方向移動.在d維的空間中，設(shè)x是其中的一個(gè)點(diǎn)，則其概率密度為:

均值漂移向量為:

其中:g(x)=－k'(x)為輪廓函數(shù)，當(dāng)g(x)=1時(shí)，式(2)為:

圖1中的黑點(diǎn)為核函數(shù)的中心點(diǎn)，用x表示，周圍的白點(diǎn)為xi，圖中的箭頭表示核函數(shù)的中心點(diǎn)與樣本點(diǎn)之間的偏移向量，樣本點(diǎn)越密的區(qū)域箭頭越多，平均偏移量就會指向該區(qū)域，也就是梯度方向表示每個(gè)采樣點(diǎn)的權(quán)值.

圖1 均值漂移向量示意圖

1.2 均值漂移跟蹤算法

均值漂移算法是一種半自動跟蹤算法，它以人工的方式畫出所要跟蹤的窗口.

1)目標(biāo)模型

假設(shè)選中的目標(biāo)區(qū)域中心為x0，其中有n個(gè)像素，分別是{xi}i=1，…，nu=1，…，n，特征值的個(gè)數(shù)為m，分別為u=1，…，m，則目標(biāo)特征值的概率密度函數(shù)估計(jì)為:

2)候選目標(biāo)模型

候選目標(biāo)區(qū)域的中心坐標(biāo)為y，和目標(biāo)模型同樣的道理，計(jì)算候選目標(biāo)特征值的概率密度函數(shù)估計(jì)為:

3)Bhattacharyya函數(shù)計(jì)算相似度

均值漂移跟蹤算法是基于顏色直方圖特征來進(jìn)行跟蹤的，使用相似性函數(shù)描述目標(biāo)模型和候選目標(biāo)之間的相似度.相似性函數(shù)有很多種，如Fisher linear discrimant，直方圖交集，Bhattacharyya 函數(shù)等，通常我們選用Bhattacharyya函數(shù)來判斷相似性，其定義為:

4)目標(biāo)定位

這樣目標(biāo)中心就從上一幀的y0移動到下一幀的y1，即移動到和原來目標(biāo)模板最相似的區(qū)域.

2 帶寬自適應(yīng)均值漂移算法

2.1 Bhattacharyya系數(shù)計(jì)算

均值漂移中的核函數(shù)是凸函數(shù)，表示靠近中心點(diǎn)所占的權(quán)重較大，邊緣的權(quán)重較小，這樣對邊緣具有較好的抑制，有利于目標(biāo)跟蹤的穩(wěn)定性，函數(shù)的定義如下式所示:

邊緣對判斷目標(biāo)的縮放起著重要的作用.邊緣所占的權(quán)重越大，則中心點(diǎn)占的權(quán)重越小，核函數(shù)變?yōu)橄率?

目標(biāo)模板特征值中心加權(quán)概率密度估計(jì)qd可由式(6)和(9)得出，目標(biāo)模板特征值邊緣加權(quán)概率密度估計(jì)qe可由式(6)和(10)得出，根據(jù)qd和qe可以得出模板自身的Bhattacharyya系數(shù)為ρde=跟蹤窗內(nèi)特征值邊緣加權(quán)概率密度估計(jì)pe由式(6)和(10)得出，由此可以計(jì)算出候選目標(biāo)與模板Bhattacharyya系數(shù)為

1)當(dāng) ρde＞ ρ'de時(shí)，目標(biāo)變小.

2)當(dāng) ρde= ρ'de時(shí)，目標(biāo)大小不變.

3)當(dāng) ρde＜ ρ'de時(shí)，目標(biāo)變大.

2.2 目標(biāo)變小時(shí)跟蹤窗口的調(diào)整

設(shè)當(dāng)前幀的兩個(gè)窗寬分別為h1=hprev、h2=hprev+Δh，其中:Δh=0.1hprev，hprev為前一幀窗寬，通過均值漂移算法來計(jì)算當(dāng)前幀兩個(gè)窗寬所對應(yīng)的Bhattacharyya系數(shù)，最大的Bhattacharyya系數(shù)所對應(yīng)的窗寬為hopt，為了避免跟蹤窗口的改變過于敏感，改變后的跟蹤窗寬如下式所示:

其中:式(11)中 β 的值為0.3.

以 hnew為跟蹤窗口再次計(jì)算 ρ'de，當(dāng) ρde＞ ρ'de，則跟蹤窗口小于目標(biāo)，按照以上步驟重新計(jì)算窗寬，直到 ρde＜ ρ'de.

2.3 目標(biāo)變大或不變時(shí)跟蹤窗口的調(diào)整

目標(biāo)變大時(shí)的跟蹤，首先對跟蹤目標(biāo)形心進(jìn)行定位，然后通過相鄰兩幀中特征點(diǎn)和匹配計(jì)算出變大的后的窗口大小.

設(shè)Oi為第i幀目標(biāo)形心，ci為i跟蹤窗口的中心，當(dāng)目標(biāo)增大時(shí)i+1幀目標(biāo)形心和跟蹤窗口中心分別為Oi+1和Ci+1，則目標(biāo)形心和跟蹤窗口中心偏移量d=ci+1－oi+1，因此要通過d來補(bǔ)償空間定位的偏移.第i幀到第i+1幀視頻中，目標(biāo)是逐漸變大的，根據(jù)后向跟蹤方法，從第i+1幀到第i幀，目標(biāo)是逐漸變小的，均值漂移跟蹤算法對縮小的目標(biāo)能夠很好的跟蹤其形心，且目標(biāo)形心與跟蹤窗口中心重合，即采用后向跟蹤方法得到的跟蹤窗口中心c'i+1就是在第i幀用均值漂移跟蹤算法找到的目標(biāo)形心，這樣就存在另外一個(gè)偏移量d'=c'i+1－ci，由于視頻中目標(biāo)運(yùn)動速度不是很快，所以d'近似等于d.這樣目標(biāo)的形心位置就是:

目標(biāo)尺度的變化是通過仿射模型和特征點(diǎn)匹配的方法算出的.首先在候選目標(biāo)窗口內(nèi)檢測目標(biāo)測角點(diǎn)，然后通過歸一化交叉相關(guān)法得到相鄰兩幀的匹配特征點(diǎn)對，根據(jù)仿射變換原理，特征點(diǎn)對滿足下式:

其中:ex和ey分別是x軸和y軸上的平移分量，sx和sy分別為x軸和軸y上的伸縮幅值.跟蹤窗口的寬度可由下式進(jìn)行更新:

角點(diǎn)能夠很好的刻畫出跟蹤目標(biāo)的空間結(jié)構(gòu)，且比較容易檢測，因此，選用匹配角點(diǎn)作為樣本來對仿射模型參數(shù)進(jìn)行估算.

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

為了驗(yàn)證算法的有效性以及實(shí)時(shí)性，采用傳統(tǒng)固定核窗寬的均值漂移跟蹤算法和本文提出的算法對目標(biāo)逐漸增大和目標(biāo)逐漸減小的車輛視頻序列進(jìn)行實(shí)驗(yàn)分析.視頻幀數(shù)是40，周圍環(huán)境為校園馬路，測試環(huán)境為Windows XP系統(tǒng)，內(nèi)存1 G，編程工具M(jìn)atlab2010a.跟蹤實(shí)驗(yàn)結(jié)果如圖2、圖4所示.

圖2 本文算法與均值漂移跟蹤算法結(jié)果對比

圖2所示為跟蹤目標(biāo)變大時(shí)跟蹤實(shí)驗(yàn)結(jié)果的對比圖.其中，圖2(A)中圖像序列是使用固定核窗寬對目標(biāo)增大時(shí)的跟蹤效果.可以看出跟蹤效果不理想，由于跟蹤框不變，當(dāng)跟蹤目標(biāo)增大時(shí)，跟蹤框相對較小，跟蹤的尺度就會產(chǎn)生偏差，且空間的定位也不準(zhǔn)確.圖2(B)中圖像序列為本文提出的采用形心定位和特征點(diǎn)仿射模型對目標(biāo)增大時(shí)的跟蹤效果，從圖2中可以看出，跟蹤窗口隨著目標(biāo)的增大及時(shí)、有效地更新，跟蹤窗口隨之變大，且空間定位也很準(zhǔn)確，解決了文獻(xiàn)[2]方法對目標(biāo)增大時(shí)跟蹤窗口有時(shí)反而縮小的不足.跟蹤的效果如圖3所示.

圖3 幾種算法所得目標(biāo)尺度與目標(biāo)實(shí)際尺度對比

圖4 本文算法與均值漂移跟蹤算法結(jié)果對比

圖4所示為目標(biāo)縮小時(shí)跟蹤實(shí)驗(yàn)結(jié)果的對比圖.圖4(A)中圖像序列是使用固定核窗寬對目標(biāo)縮小時(shí)的跟蹤效果，從圖4中可以看出空間定位準(zhǔn)確，但是跟蹤的視覺效果欠佳，跟蹤框不能隨著目標(biāo)的縮小而響應(yīng)縮小，導(dǎo)致計(jì)算量相對較大，影響跟蹤的實(shí)時(shí)性.圖4(B)中圖像序列為使用本文跟蹤算法對目標(biāo)縮小時(shí)的跟蹤效果，從圖4中可以看出，隨著跟蹤目標(biāo)尺寸逐漸縮小，跟蹤窗口尺寸也能及時(shí)、有效地隨之變小，且空間定位也很準(zhǔn)確，能夠很好的滿足跟蹤的有效性，而且在時(shí)間復(fù)雜度上本文算法也具有很大的優(yōu)勢.時(shí)間復(fù)雜度是通過算法中迭代循環(huán)次數(shù)算出，如表1所示.

表1 時(shí)間復(fù)雜度分析

4 結(jié)語

本文針對傳統(tǒng)的均值漂移跟蹤算法不能很好的縮放跟蹤目標(biāo)的缺陷，提出了自適應(yīng)跟蹤改進(jìn)算法.通過邊緣概率密度來判斷目標(biāo)的縮放，如果目標(biāo)是縮小的，則通過Bhattacharyya系數(shù)來對跟蹤窗口的更新，如果目標(biāo)是增大的，則通過后向跟蹤的方法對跟蹤窗口的更新.通過跟蹤實(shí)驗(yàn)表明，本文提出的算法對提高均值漂移跟蹤算法的適應(yīng)性有重要意義，有效地解決了尺度變化的目標(biāo)定位困難和跟蹤窗口更新的問題.但是本算法不適合對遮擋情況下的目標(biāo)跟蹤，遮擋情況下目標(biāo)縮放的自適應(yīng)跟蹤是進(jìn)一步需要研究的問題.

[1] FUKUNAGA K，HOSTETLER L D.The estimation of the gradient of a density function，with applications in pattern recognition[J].IEEE Trans.On Information Theory，1975，21(1):32 －40.

[2] COMANICIU D，RAMESH V，MEER P.Kernel－based object tracking[J].IEEE Trans.on Pattern Analysis and Machine Intelligence，2003，25(5):564 －577

[3] COLLINS R.Mean－shift blob tracking through scale space[C]//IEEE International Conference on Computer Vision and Pattern Recognition Baltimore，Victor Graphics:IEEE press，2003:234－240.

[4] 彭寧嵩，楊 杰，劉 志，等.Mean－Shift跟蹤算法中核函數(shù)窗寬的自動選取[J].軟件學(xué)報(bào)，2005，16(9):1542 －1550.

[5] 朱勝利，朱善安.核函數(shù)帶寬自適應(yīng)的Mean－shift目標(biāo)跟蹤算法[J].光電工程，2006，33(8):11 －16.

[6] BRADSKI G R.Computer vision face tracing for use in a perceptual user interface[J].Intel Technology Journal，1998，2:1 －15.

[7] 田 剛，胡瑞敏，王中元.一種基于運(yùn)行矢量分析的 Mean shift目標(biāo)跟蹤算法[J].中國圖像圖形學(xué)報(bào)，2010，15(1):85－90

[8] HU X L，TANG Y C，ZHANG Z H.Video object matching based on SIFT algorithm[C]//International Conference on Neural Networks and Signal Processing(ICNNSP)，[S.l.]:[s.n.]，2008:412－415.