王夢斐，王 沛，馬 燕，張 倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234 )

基于卡爾曼和圖像信息量的Mean Shift改進(jìn)跟蹤算法

王夢斐，王 沛，馬 燕，張 倩

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234 )

Mean Shift算法在目標(biāo)實(shí)時(shí)跟蹤領(lǐng)域取得了廣泛的應(yīng)用，但是對(duì)于速度過快或尺度變化大的目標(biāo)跟蹤存在較大的缺陷。提出了一種基于Mean Shift和Kalman預(yù)測帶寬的自適應(yīng)跟蹤算法。該算法提出以Kalman預(yù)測目標(biāo)在下幀中的中心位置作為Mean Shift迭代初始位置；同時(shí)引入圖像信息量度量方法以適應(yīng)目標(biāo)的尺度變化。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的跟蹤算法能很好地跟蹤尺度變化的目標(biāo)，跟蹤效果很好。

視覺跟蹤；均值漂移；信息度量；卡爾曼

在計(jì)算機(jī)視覺中，基于視頻的目標(biāo)跟蹤是一項(xiàng)關(guān)鍵技術(shù)，它是對(duì)視頻序列中運(yùn)動(dòng)的目標(biāo)進(jìn)行檢測、提取、識(shí)別和跟蹤的過程。在智能監(jiān)控、人機(jī)交互、視頻檢索、車輛監(jiān)控等方面有著廣泛的應(yīng)用[1]。

Mean Shift跟蹤算法[2-3]最初是由Fukunaga提出的一種無參概率密度估計(jì)方法，用于數(shù)據(jù)聚類，Comaniciu等將其應(yīng)用到實(shí)時(shí)目標(biāo)跟蹤領(lǐng)域中。Mean Shift算法具有快速匹配的特性，因其簡單、魯棒、計(jì)算負(fù)荷小等特點(diǎn)在目標(biāo)跟蹤中被廣為采用。

傳統(tǒng)的Mean Shift算法使用的目標(biāo)跟蹤框大小是固定不變的，由目標(biāo)初始大小確定固定的帶寬。但是當(dāng)跟蹤目標(biāo)尺度發(fā)生變化時(shí)，如果帶寬保持不變，就會(huì)導(dǎo)致跟蹤目標(biāo)偏差或丟失。因此一個(gè)自適應(yīng)窗口算法就很有必要。文獻(xiàn)[4]對(duì)核窗寬進(jìn)行±10%的修改，Bhattacharyya系數(shù)最大時(shí)的帶寬即為最佳窗口帶寬，此方法比較適合目標(biāo)物體變小的情況。文獻(xiàn)[5]將尺度空間理論運(yùn)用于Mean Shift算法，帶寬可以實(shí)時(shí)更改，但在復(fù)雜背景下的跟蹤效果不佳且計(jì)算量大。

本文針對(duì)在Mean Shift算法中尺度固定不變的跟蹤窗口不能有效地跟蹤存在明顯尺度變化的目標(biāo)，引入圖像信息量和Kalman濾波的方法，提出一種改進(jìn)的帶寬自適應(yīng)跟蹤方法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法取得較好的效果。

1 Mean Shift算法

Mean Shift算法[6]是在一個(gè)給定的條件下連續(xù)的迭代過程，首先對(duì)第一幀目標(biāo)模型初始化，確定初始窗口及其大小，計(jì)算核函數(shù)加權(quán)下跟蹤窗口內(nèi)的直方圖分布，然后計(jì)算后續(xù)圖像幀的候選目標(biāo)模型，以相似性函數(shù)最大來得出關(guān)于目標(biāo)的Mean Shift向量，按照收斂性，不斷迭代計(jì)算Mean Shift向量，使目標(biāo)跟蹤窗口沿相似度變化最快的方向移動(dòng)，直到滿足給定的收斂條件為止，從而實(shí)現(xiàn)跟蹤目標(biāo)。

2 自適應(yīng)優(yōu)化算法

2.1 Kalman目標(biāo)運(yùn)動(dòng)估計(jì)

標(biāo)準(zhǔn)的Mean Shift跟蹤算法是將前一幀的目標(biāo)位置作為當(dāng)前幀迭代的初始位置。如果跟蹤目標(biāo)運(yùn)動(dòng)速度較快或者目標(biāo)尺度變化較大，極有可能出現(xiàn)跟蹤目標(biāo)丟失或誤定位的問題。

為了解決跟蹤目標(biāo)丟失或誤定位的問題，可以采用某些特定的方法來描述跟蹤目標(biāo)的運(yùn)動(dòng)特征及運(yùn)動(dòng)軌跡，從而提高算法的有效性。本文采用Kalman濾波算法，其作為一種有效的估計(jì)方法，被廣泛應(yīng)用在跟蹤領(lǐng)域中[7]。采用Kalman濾波對(duì)跟蹤目標(biāo)的位置進(jìn)行預(yù)測，將得到的運(yùn)動(dòng)目標(biāo)位置估計(jì)值作為Mean Shift算法的初始迭代位置，然后在其鄰域內(nèi)尋找最佳匹配位置，在減小了運(yùn)算量的同時(shí)，提高了算法的準(zhǔn)確性。

2.2 圖像信息量度量

Marr視覺理論[8]中指出，視覺處理得到的初始簡圖中要素的數(shù)量可作為一個(gè)很好的信息度量標(biāo)準(zhǔn)，其中的要素包括斑點(diǎn)、邊緣、端點(diǎn)還有棒。并且已有文獻(xiàn)根據(jù)這一理論[9]定義了兩類特征點(diǎn)，因此，圖像的信息量可以用圖像中特征點(diǎn)的數(shù)量來衡量。根據(jù)圖像信息量的理論，選擇如圖1a所示的汽車作為跟蹤實(shí)驗(yàn)對(duì)象，對(duì)每幀圖像內(nèi)的汽車劃定統(tǒng)一大小的矩形框使汽車正好全部包含在框內(nèi)，并統(tǒng)計(jì)矩形框內(nèi)的信息量。最后根據(jù)統(tǒng)計(jì)所得到的信息量，給出了隨著汽車尺寸變小，信息量變化的關(guān)系，如圖1b中曲線①。

圖1 汽車試驗(yàn)示意圖

由曲線①可知，當(dāng)汽車從大變小時(shí)，即汽車與觀察點(diǎn)的距離由近到遠(yuǎn)時(shí)，矩形跟蹤框內(nèi)信息量的變化趨勢是由大變小的。圖中曲線存在小幅波動(dòng)，是因?yàn)楦櫸矬w周圍存在干擾因素，但是誤差在允許范圍之內(nèi)。因此，可以利用信息量大小的變化情況來自動(dòng)更新跟蹤窗口的大小。

圖1b中曲線①②分別為原始跟蹤窗口內(nèi)的信息量與對(duì)跟蹤窗口乘以0.8后信息量的變化關(guān)系。由曲線②可知，在跟蹤窗口的寬度和高度變小之后，信息量的數(shù)值開始有增大的趨勢，在經(jīng)過中間一段相對(duì)平穩(wěn)的過度后，最后緩慢下降。這是由于最初0.8倍大小的跟蹤窗口并沒有包含完整的跟蹤目標(biāo)，如圖2a所示，所以它只含有貨車的部分信息量。隨著貨車由近到遠(yuǎn)，由大變小，信息量會(huì)逐漸上升直到較小的跟蹤窗口也剛好把貨車包含在內(nèi)，如圖2b所示。最后，貨車?yán)^續(xù)遠(yuǎn)去，在較小的跟蹤窗口的信息量也會(huì)下降。

圖2 信息量與目標(biāo)大小的對(duì)應(yīng)關(guān)系

根據(jù)原始跟蹤窗口和縮小后跟蹤窗口信息量的變化，可以得到如圖3所示的關(guān)系。

圖3 跟蹤目標(biāo)變小時(shí)信息量比值示意圖

圖3為兩種信息量的比值，由此可知，當(dāng)跟蹤框內(nèi)的跟蹤目標(biāo)尺寸變小時(shí)，兩種信息量的比值的整體變化趨勢是逐漸下降的。而如果跟蹤窗口內(nèi)的目標(biāo)尺寸變大時(shí)，則如圖4所示。

圖4 跟蹤目標(biāo)變大時(shí)信息量示意圖

圖4中曲線①②分別為原始跟蹤窗口內(nèi)的信息量與對(duì)跟蹤窗口乘以0.8后信息量的變化關(guān)系。

由上述分析可知：目標(biāo)尺寸的變化和信息量的變化是存在一定關(guān)系的。因此可以得到如下尺度更新的方法。假如滿足I1/I2-I3/I4>0，則目標(biāo)尺寸可能減小，更新尺度比例為S，否則判斷目標(biāo)尺寸可能增大。具體計(jì)算如下

(1)

式中：I1，I2分別為當(dāng)前幀在原始跟蹤窗和乘以0.8系數(shù)中的信息量；I3，I4分別為目標(biāo)變化下一幀后在原始跟蹤窗和乘以0.8系數(shù)中的信息量。參數(shù)α，β的作用是分別是消除背景對(duì)信息量的影響，可根據(jù)不同的應(yīng)用具體設(shè)定，計(jì)算得到跟蹤窗口尺度變化的比例S后，就可以更新跟蹤窗口的寬度W和高度H為

W=W(1+S)

(2)

H=H(1+S)

(3)

2.3 基于Kalman-MeanShift的自適應(yīng)跟蹤算法

本文所采用的基于圖像信息量、Kalman及MeanShift窗口自適應(yīng)跟蹤算法的步驟為：首先確定起始搜索窗口的中心點(diǎn)位置。在開始連續(xù)的(k-1)幀中，將跟蹤目標(biāo)中心點(diǎn)位置的運(yùn)動(dòng)軌跡作為Kalman濾波器的觀測值，用Kalman濾波器計(jì)算第k幀跟蹤目標(biāo)的位置，作為MeanShift目標(biāo)的起始位置，MeanShift會(huì)在這個(gè)位置的附近區(qū)域遞歸尋找跟蹤目標(biāo)的最優(yōu)位置，再以這個(gè)位置作為Kalman濾波器的觀測值，繼續(xù)進(jìn)行計(jì)算。

具體的自適應(yīng)跟蹤算法流程如圖5所示。

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

為了驗(yàn)證上面所提出的跟蹤算法，分別進(jìn)行了本文所提出的窗口自適應(yīng)算法和采用標(biāo)準(zhǔn)的MeanShift算法進(jìn)行視頻跟蹤實(shí)驗(yàn)。程序在MATLAB編程環(huán)境下調(diào)試，并在i5 2.0GHzCPU、2Gbyte內(nèi)存的計(jì)算機(jī)上調(diào)試通過。

圖6、圖7給出兩組圖像序列，采用彩色圖像序列對(duì)提出的目標(biāo)跟蹤算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，分別驗(yàn)證跟蹤目標(biāo)變大與變小的情況，圖像初始化是在第一幀中手工完成的。

其中，圖6a和圖7a為采用標(biāo)準(zhǔn)的MeanShift算法的跟蹤結(jié)果；圖6b和圖7b為采用本文所提出的窗口自適應(yīng)跟蹤算法的跟蹤結(jié)果。從圖中可以看出，當(dāng)跟蹤目標(biāo)變化尺度較大時(shí)，標(biāo)準(zhǔn)的MeanShift算法的跟蹤框內(nèi)不是包含了除跟蹤目標(biāo)以外的信息就是沒有完全包含跟蹤目標(biāo)。當(dāng)跟蹤時(shí)間較長時(shí)，極有可能出現(xiàn)跟蹤目標(biāo)丟失或者誤定位等問題。而本文所提出的跟蹤算法，可根據(jù)跟蹤窗口內(nèi)圖像信息量的變化進(jìn)行跟蹤窗口的尺度變化，來適應(yīng)跟蹤目標(biāo)的尺寸變化，保證了跟蹤的精確性。

圖5 自適應(yīng)跟蹤算法流程

圖6 運(yùn)動(dòng)目標(biāo)變小時(shí)跟蹤結(jié)果

圖7 運(yùn)動(dòng)目標(biāo)變大時(shí)跟蹤結(jié)果

圖8和圖9是運(yùn)動(dòng)目標(biāo)像素變化曲線。從圖中可以看出，加入Kalman的Mean Shift與原算法相比，像素變化更加平穩(wěn)，抖動(dòng)性小。更重要的是，結(jié)合圖7所示，加入Kalman的Mean Shift算法跟蹤框的中心點(diǎn)位置更加逼近跟蹤目標(biāo)的中心點(diǎn)位置。

本文提出了一種新型的窗口自適應(yīng)跟蹤算法，改善了傳統(tǒng)的Mean Shift跟蹤算法中窗口不變的不足。加入Kalman濾波來初步預(yù)測跟蹤目標(biāo)的中心位置，在減少運(yùn)算量的同時(shí)防止由于目標(biāo)運(yùn)動(dòng)過快而造成的目標(biāo)丟失。并通過論證圖像信息量與目標(biāo)尺度的關(guān)系加入了尺度更新項(xiàng)目，提高了跟蹤的準(zhǔn)確性。

圖8 目標(biāo)x軸坐標(biāo)變化曲線

圖9 目標(biāo)y軸坐標(biāo)變化曲線

[1]楊戈，劉宏.視覺跟蹤算法綜述[J].智能系統(tǒng)學(xué)報(bào)，2010，5(2)：95-105.

[2] YILMAZ A，JAVED O，SHAH M.Object tracking：a survey[J].ACM Computing Surveys， 2006，38(4)：13.

[3]COMANICIU D，RAMESH V，MEER P.Real-time tracking of non-rigid objects using mean shift[C]//Proc.IEEE Conference on Computer Vision and Pattern Recognition，2000.[S.l.]：IEEE，2000：142-149.

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

[5]COLLINS R T.Mean-shift blob tracking through scale space[C]//Proc.IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2003.[S.l.]：IEEE，2003：234.

[6]顧幸方，茅耀斌，李秋潔.基于Mean Shift的視覺目標(biāo)跟蹤算法綜述[J].計(jì)算機(jī)科學(xué)，2012，39(12)： 16-24.

[7]王文江，黃山，張洪斌.一種基于Mean Shift和Kalman預(yù)測的帶寬自適應(yīng)跟蹤算法[J].計(jì)算機(jī)工程與科學(xué)，2013，35(5)：87-92.

[8]SONKA M，HLAVAC V，BOYLE R.Image processing，analysis，and machine vision[M].Toronto：Thomson，2008.

[9]WANG Z Y，CHENG Z X，TANG S J.Information measures of scale-space based on visual characters[J].Chinese Journal of Image and Graphics，2005(10)：922-928.

Improved Mean Shift Tracking Algorithm Based on Kalman and Image Information Measure Method

WANG Mengfei，WANG Pei，MA Yan，ZHANG Qian

(CollegeofMechanicalandElectronicEngineering，ShanghaiNormalUniversity，Shanghai200234，China)

Mean Shift algorithm is widely used in high real-time field of target tracking.However，it cannot adapt to the size change of the target or locate accurately when the target is moving fast.In this article，a bandwidth-adaptive tracking algorithm based on Mean Shift and Kalman prediction is proposed.The Kalman filter is used in the algorithm to predict the positions of fast moving objects in the successive frame，which are as the initial positions for Mean Shift tracking.Also，the information measure of multi-scale image in scale space is used to differentiate the scale.The experimental results indicate that the improved algorithm can adapt to the size change of the target and the tracking result is improved.

visual tracking；Mean Shift；information measure；Kalman

國家自然科學(xué)基金項(xiàng)目(61373004)

TP391.41

A

10.16280/j.videoe.2015.05.011

2014-02-14

【本文獻(xiàn)信息】王夢斐，王沛，馬燕,等.基于卡爾曼和圖像信息量的Mean Shift改進(jìn)跟蹤算法[J].電視技術(shù),2015，39(5).

王夢斐(1989— )，女，碩士生，主研圖像處理、視頻跟蹤。

責(zé)任編輯：時(shí) 雯