基于分塊背景更新的均值飄移跟蹤算法

楊 莉，李茂林

（南昌大學(xué) 信息工程學(xué)院，江西 南昌330031）

0 引 言

研究者們對目標(biāo)跟蹤做了大量研究并取得了許多成果［1－3］。其中，均值飄移跟蹤算法因其高效性、簡便性等優(yōu)點(diǎn)被廣泛應(yīng)用。經(jīng)典均值飄移跟蹤算法多只對興趣目標(biāo)建立顏色直方圖，沒有考慮背景信息對其定位的影響，而直方圖只能反映目標(biāo)區(qū)域整體的統(tǒng)計(jì)特性，不能反映跟蹤目標(biāo)的空間特征狀態(tài)信息。Ning等［4］驗(yàn)證了背景加權(quán)跟蹤算法沒有起到實(shí)際效果，并采用改正后的權(quán)重背景直方圖有效地降低了背景對目標(biāo)定位的干擾，但是當(dāng)背景信息有較大改變時(shí)，該算法基于全部背景信息更新的策略，忽略了更新前的背景信息對目標(biāo)定位的作用；羅富貴等［5］采用賦予目標(biāo)區(qū)域內(nèi)像數(shù)點(diǎn)大權(quán)重的算法，但需要目標(biāo)模型包含非常少的背景信息；王建華等［6］提出了賦予背景信息內(nèi)像數(shù)點(diǎn)小權(quán)重的算法，但背景中出現(xiàn)與目標(biāo)區(qū)域相似度高的顏色信息時(shí)，缺乏有效處理。這兩種算法有相似之處，較好地排除了目標(biāo)窗口內(nèi)背景信息對目標(biāo)定位的干擾，但忽略了目標(biāo)窗口外圍的背景信息對目標(biāo)定位的問題。

為了利用目標(biāo)物體的空間信息并排除背景區(qū)域信息對目標(biāo)定位的干擾，本文提出了基于分塊背景更新的改進(jìn)算法。首先把背景區(qū)域分成4小塊，然后建立融合背景信息的顏色直方圖的目標(biāo)模型，再引入距離權(quán)重并在跟蹤過程中動態(tài)地更新背景信息。實(shí)驗(yàn)結(jié)果表明，與整塊背景信息更新策略和加權(quán)更新背景信息的策略相比，改進(jìn)算法具有更高的迭代收斂效率和更強(qiáng)的抗背景干擾能力。

1 經(jīng)典均值飄移跟蹤算法

在經(jīng)典均值飄移目標(biāo)跟蹤中，常用顏色直方圖描述興趣目標(biāo)。目標(biāo)模型可以表示為在目標(biāo)區(qū)域上的顏色特征值的概率值。令｛｝i＝1，…n為歸一化的目標(biāo)模型中心像素點(diǎn)的位置。相應(yīng)目標(biāo)模型特征（u＝1，2，…，m）的概率密度為

式中：k（x）——核函數(shù)，用于對像素進(jìn)行加權(quán)，n是目標(biāo)窗口中像數(shù)點(diǎn)的個(gè)數(shù)；m 是特征空間的元素個(gè)數(shù)；b（x＊i）將目標(biāo)區(qū)域中的每個(gè)像素點(diǎn)映射到對應(yīng)的特征空間；δ［b（x＊i）－u］是用于判斷目標(biāo)區(qū)中的任意像素x＊i的值是否等于第u個(gè)特征值，C 為歸一化常數(shù)。類似式 （1），令｛xi｝i＝1，…nh為當(dāng)前幀候選目標(biāo)區(qū)域中的像素點(diǎn)，同理可計(jì)算該跟蹤窗口中候選目標(biāo)的概率密度

式中：y——候選目標(biāo)的中心坐標(biāo)；h——跟蹤窗口帶寬；nh——目標(biāo)候選窗口中全部像素的數(shù)量；Ch——?dú)w一化常數(shù)。

為了確定待跟蹤目標(biāo)在新的幀中的位置，目標(biāo)直方圖與候選目標(biāo)直方圖之間的相似性常用巴氏系數(shù)來度量，巴氏系數(shù)計(jì)算方法如下

均值漂移算法就是在新的幀中確定一個(gè)候選位置，使得巴氏系數(shù)最大。均值飄移向量表示為

在新的幀中，以目標(biāo)在前一幀的最佳位置yo作為當(dāng)前時(shí)刻目標(biāo)的初始位置。利用式 （4）計(jì)算得到目標(biāo)在該位置的均值飄移向量m（yo），再用此向量來移動初始位置得到新的位置y′，如此反復(fù)直到滿足一定的收斂條件 （最大迭代次數(shù)或者相鄰兩幀位置偏移足夠小）。最終的收斂位置就是目標(biāo)在當(dāng)前幀中的最終位置。

2 基于分塊背景更新的加權(quán)目標(biāo)跟蹤算法

2.1 基于分塊背景的目標(biāo)模型

為了體現(xiàn)各個(gè)方向上的背景信息對目標(biāo)定位的作用，進(jìn)一步提高改進(jìn)算法的效率，采用分塊背景模型。首先在目標(biāo)窗口周圍定義一個(gè)面積是目標(biāo)窗口3倍的背景區(qū)域［1］，如圖1所示，中部深色區(qū)域是目標(biāo)窗口，周圍是背景區(qū)域，把背景區(qū)域劃分成4個(gè)子塊 （每個(gè)子塊各為一種顏色），依次計(jì)算每個(gè)子塊的直方圖模型4）。賦予每個(gè)子塊一個(gè)加權(quán)系數(shù)，構(gòu)成整體背景信息模型

圖1 背景區(qū)域的劃分

為了使建立的顏色直方圖能更好地辨別背景區(qū)域和目標(biāo)區(qū)域，降低背景信息對目標(biāo)定位的干擾，采用融合背景信息的顏色直方圖。在目標(biāo)區(qū)域，計(jì)算目標(biāo)模型，然后與用式 （7）計(jì)算出來的背景模型的權(quán)重系數(shù)融合［4］，形成本文提出的基于分塊背景信息的目標(biāo)模型。而候選目標(biāo)模型則不融合背息信息，類似目標(biāo)顏色模型，候選目標(biāo)模型表示為（y）。

2.2 背景模型的更新

為了提高跟蹤的精度，需要?jiǎng)討B(tài)地更新背景模型。Ning等［4］提出了基于巴氏系數(shù)的全部背景信息更新算法，忽略了更新前的背景信息對目標(biāo)定位的作用。Wang等［7］提出基于巴氏系數(shù)的加權(quán)更新算法，需要設(shè)置較高的閾值，增加了計(jì)算時(shí)間。Vilaplana等［8］對每幀圖像都加權(quán)更新背景，該算法更新的過于頻繁。本文采用分塊背景的更新方法。首先，在當(dāng)前幀中，分別計(jì)算每個(gè)子塊的背景模型和整體背景模型然后計(jì)算新舊整體背景模型的巴氏系數(shù)

通過巴氏系數(shù)選擇性地更新背景模型，當(dāng)ρ大于或等于事先給定的閾值，說明新舊整體背景信息不更新背景模型。否則更新背景模型，并計(jì)算各個(gè)子塊的新舊模型的巴氏系數(shù)

其中l(wèi)＝1，2，3，4。為了充分利用更新前的背景信息，只更新其中巴氏系數(shù)較小的3個(gè)子塊模型，從而得到新的整體背景模型，并計(jì)算新背景的權(quán)重系數(shù)更新

2.3 距離權(quán)重

顏色直方圖描述的是不同色彩在整幅圖像中所占的比例，而并不關(guān)心每種色彩所處的空間位置，即無法描述圖像中的目標(biāo)空間信息。離目標(biāo)中心位置越近的點(diǎn)，對迭代貢獻(xiàn)越大，離中心位置越遠(yuǎn)的點(diǎn)，對迭代貢獻(xiàn)越小，因此根據(jù)目標(biāo)窗口中的像數(shù)點(diǎn)離中心位置的距離不同，可以定義一個(gè)距離權(quán)重。在目標(biāo)窗口中計(jì)算離中心位置最大距離Dmax，然后計(jì)算其中每個(gè)像數(shù)點(diǎn)離中心位置的距離d（i）（i＝1，…nh），得到像素點(diǎn)離中心位置的離差率

結(jié)合距離權(quán)重，得到改進(jìn)的權(quán)重

2.4 改進(jìn)算法偽代碼

改進(jìn)算法用偽代碼描述如下：

步驟2 初始化迭代次數(shù)k＝0。

步驟4 計(jì)算候選目標(biāo)坐標(biāo)y1。

圖2 抗背景干擾能力測試1

步驟6 設(shè)定背景模型更新閾值α2（默認(rèn)值：0.5）計(jì)算當(dāng)前幀的背景模型｝u＝1，…m利用式 （8）計(jì)算新舊整體背景模型的巴氏系數(shù)ρ。如果ρ≥α2，轉(zhuǎn)到步驟2進(jìn)去下一幀迭代。否則，更新背景模型及其權(quán)重系數(shù)｛vu｝u＝1，…m，利用顏色模型和新的背景模型的權(quán)重系數(shù)｛v′u｝u＝1，…m更新目標(biāo)模型。轉(zhuǎn)到步驟2進(jìn)去下一幀迭代。

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

實(shí)驗(yàn)在Intel（R）Core（TM）2 Duo CPU E7400 ＠2.80GHz處理器及1.98GB內(nèi)存的電腦上，用matlab實(shí)現(xiàn)。為了驗(yàn)證改進(jìn)算法的有效性，對標(biāo)準(zhǔn)型的視頻進(jìn)行對比實(shí)驗(yàn)，并分別用基于整塊背景信息更新的均值飄移跟蹤（whole background update，WBU）算法［5］、基于顏色特征的加權(quán)更新背景信息的均值漂移跟蹤 （weighted update background，WUB）算法和改進(jìn)算法進(jìn)行了詳細(xì)對比。其中深色矩形框?yàn)楸尘皡^(qū)域邊界，白色矩形框內(nèi)為目標(biāo)區(qū)域。

為了測試改進(jìn)算法抗背景干擾能力，本實(shí)驗(yàn)選擇行人行走測試序列，如圖2所示，起初行人站在墻柱前，依次經(jīng)過冰箱、第二個(gè)墻柱、屏幕顯示器、第三個(gè)墻柱、空調(diào)。WBU 算法，忽略了更新前背景信息對目標(biāo)定位的作用又沒考慮目標(biāo)的空間信息，導(dǎo)致跟蹤效果不佳；WUB算法雖然考慮了更新前背景信息對目標(biāo)定位的作用，但需要設(shè)置比較大的閾值，增加了計(jì)算時(shí)間并且該算法沒有考慮目標(biāo)的空間信息因此造成跟蹤效果不好，甚至跟丟目標(biāo)；改進(jìn)算法既考慮了更新前背景信息的重要性又在比較低的閾值下利用了目標(biāo)空間信息很好地跟蹤到了目標(biāo)。

為了進(jìn)一步測試改進(jìn)算法的抗背景干擾能力，選取“CCTV 風(fēng)云足球”欄目中足球比賽視頻作為測試序列。如圖3所示，有多個(gè)穿白色球服的運(yùn)動員在跟蹤目標(biāo)周圍，目標(biāo)周圍背景信息變化不大，但有較高相似目標(biāo)的干擾。WBU 算法和WUB算法均沒有考慮目標(biāo)空間信息，容易受到目標(biāo)周圍相似的運(yùn)動員干擾；改進(jìn)算法利用了目標(biāo)空間信息，有較好的跟蹤效果。通過上面兩個(gè)實(shí)驗(yàn)，說明改進(jìn)算法與上述兩種算法相比，有更強(qiáng)的抗背景干擾能力。

圖3 抗背景干擾能力測試2

迭代次數(shù)是均值飄移跟蹤算法計(jì)算效率的一個(gè)重要指標(biāo)，為了測試改進(jìn)算法的計(jì)算效率，選取測試各種算法的平均迭代次數(shù)。分別選取上述兩個(gè)視頻和文獻(xiàn) ［5］中提到的Table Tennis Player視頻作為測試序列。計(jì)算這3 個(gè)測試序列的平均迭代次數(shù)。如表1 所示，在背景變化不大的前兩個(gè)測試序列中，WBU 算法和WUB算法的迭代能力接近，但均沒有考慮目標(biāo)空間信息，因此平均迭代次數(shù)都比改進(jìn)算法大，在第三個(gè)測試序列，背景信息變化大，改進(jìn)算法基于分塊背景更新且考慮目標(biāo)空間信息，故平均迭代次數(shù)最小。通過分析比較，說明改進(jìn)算法具有更高的計(jì)算效率。

表1 3種算法的平均迭代次數(shù)

4 結(jié)束語

本文在研究基于顏色特征的目標(biāo)跟蹤的基礎(chǔ)上，引入一種融合分塊背景模型更新的加權(quán)跟蹤算法。為降低背景對目標(biāo)定位的影響，并選擇性地分塊更新背景信息，并引入距離權(quán)重以適應(yīng)背景變化較大的環(huán)境中的跟蹤。同基于全部背景更新算法和加權(quán)更新算法相比，能夠在一些背景干擾條件下對目標(biāo)進(jìn)行準(zhǔn)確、有效的跟蹤。在未來的工作中，將針對在目標(biāo)變形、目標(biāo)快速運(yùn)動情況下的跟蹤進(jìn)行研究，以期得到一種適用面更廣、魯棒性更強(qiáng)的跟蹤算法。

［1］Bousetouane Fouad，Dib Lynda，Snoussi Hichem.Improved mean shift integrating texture and color features for robust real time object tracking［J］.Visual Computer，2013，29 （3）：155－170.

［2］Yinghong M，Zhi－Hong M，Wenyan J，et al.Magnetic hand tracking for human－computer interface ［J］.IEEE Trans Magn，2011，47 （5）：970－973.

［3］Souza DFL，Machado LS，Moraes RM.Integration of tracking systems for the development of virtual reality applications［J］.IEEE Lat Am Trans，2010，8 （6）：714－721.

［4］Ning J，Zhang L，Zhang D，et al.Robust mean－shift tracking with corrected background－weighted histogram ［J］.Computer Vision，IET，2012，6 （1）：62－69.

［5］LUO Fugui，XUAN Shibin，XU Junge，et al.A valid Mean Shift target tracking algorithm under a complex background［J］.Journal of Guangxi University for Nationalities，2011，17（1）：58－63 （in Chinese）.［羅富貴，宣士斌，徐俊格，等.復(fù)雜背景下一種有效的Mean Shift目標(biāo)跟蹤算法 ［J］.廣西民族大學(xué)學(xué)報(bào) （自然科學(xué)版），2011，17 （1）：58－63.］

［6］WANG Jianhua，WANG Chunping，LIANG Wei，et al.Background optimization and dynamic analysis of mean shift tracking［J］.Electronics Optics ＆ Control，2012，19 （2）：17－20 （in Chinese）.［王建華，王春平，梁偉，等.Mean Shift跟蹤的背景優(yōu)化及動態(tài)分析［J］.電光與控制，2012，19 （2）：17－20.］

［7］Wang Lingfeng，Pan Chunhong，Xiang Shiming.Mean－shift tracking algorithm with weight fusion strategy ［C］//International Conference on Image Processing，2011：473－476

［8］Vilaplana V，Varas D.Face tracking using a region based mean－shift algorithm with adaptive object and background models［J］.International Workshop on Image Analysis for Multimedia Interactive Services，2009：9－12.

［9］CHEN Aibin，CAI Zixing，DONG Deyi.A tracking method based on weighted object and background ［J］.Control and Decision，2010，25 （8）：1246－1250 （in Chinese）.［陳愛斌，蔡自興，董德毅.一種基于目標(biāo)和背景加權(quán)的目標(biāo)跟蹤方法［J］.控制與決策，2010，25 （8）：1246－1250.］

［10］DONG Wenhui，CHANG Faliang，LI Tianping.Adaptive fragments－based target tracking fusing color histogram and SIFT features ［J］.Journal of Electronics ＆ Information Technology，2013，4 （1）：770－776 （in Chinese）. ［董文會，常發(fā)亮，李天平.融合顏色直方圖及SIFT 特征的自適應(yīng)分塊目標(biāo)跟蹤方法 ［J］電子與信息學(xué)報(bào)，2013，4 （1）：770－776.］