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

楊 莉，李茂林

（南昌大學 信息工程學院，江西 南昌330031）

0 引 言

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

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

1 經典均值飄移跟蹤算法

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

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

式中：y——候選目標的中心坐標；h——跟蹤窗口帶寬；nh——目標候選窗口中全部像素的數量；Ch——歸一化常數。

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

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

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

2 基于分塊背景更新的加權目標跟蹤算法

2.1 基于分塊背景的目標模型

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

圖1 背景區域的劃分

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

2.2 背景模型的更新

為了提高跟蹤的精度，需要動態地更新背景模型。Ning等［4］提出了基于巴氏系數的全部背景信息更新算法，忽略了更新前的背景信息對目標定位的作用。Wang等［7］提出基于巴氏系數的加權更新算法，需要設置較高的閾值，增加了計算時間。Vilaplana等［8］對每幀圖像都加權更新背景，該算法更新的過于頻繁。本文采用分塊背景的更新方法。首先，在當前幀中，分別計算每個子塊的背景模型和整體背景模型然后計算新舊整體背景模型的巴氏系數

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

其中l＝1，2，3，4。為了充分利用更新前的背景信息，只更新其中巴氏系數較小的3個子塊模型，從而得到新的整體背景模型，并計算新背景的權重系數更新

2.3 距離權重

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

結合距離權重，得到改進的權重

2.4 改進算法偽代碼

改進算法用偽代碼描述如下：

步驟2 初始化迭代次數k＝0。

步驟4 計算候選目標坐標y1。

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

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

3 實驗結果及分析

實驗在Intel（R）Core（TM）2 Duo CPU E7400 ＠2.80GHz處理器及1.98GB內存的電腦上，用matlab實現。為了驗證改進算法的有效性，對標準型的視頻進行對比實驗，并分別用基于整塊背景信息更新的均值飄移跟蹤（whole background update，WBU）算法［5］、基于顏色特征的加權更新背景信息的均值漂移跟蹤 （weighted update background，WUB）算法和改進算法進行了詳細對比。其中深色矩形框為背景區域邊界，白色矩形框內為目標區域。

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

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

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

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

表1 3種算法的平均迭代次數

4 結束語

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

［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）.［羅富貴，宣士斌，徐俊格，等.復雜背景下一種有效的Mean Shift目標跟蹤算法 ［J］.廣西民族大學學報 （自然科學版），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跟蹤的背景優化及動態分析［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）.［陳愛斌，蔡自興，董德毅.一種基于目標和背景加權的目標跟蹤方法［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）. ［董文會，常發亮，李天平.融合顏色直方圖及SIFT 特征的自適應分塊目標跟蹤方法 ［J］電子與信息學報，2013，4 （1）：770－776.］