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

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

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

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

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

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

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

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

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

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

本文針對在Mean Shift算法中尺度固定不變的跟蹤窗口不能有效地跟蹤存在明顯尺度變化的目標，引入圖像信息量和Kalman濾波的方法，提出一種改進的帶寬自適應跟蹤方法。實驗結果表明，改進算法取得較好的效果。

1 Mean Shift算法

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

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

2.1 Kalman目標運動估計

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

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

2.2 圖像信息量度量

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

圖1 汽車試驗示意圖

由曲線①可知，當汽車從大變小時，即汽車與觀察點的距離由近到遠時，矩形跟蹤框內(nèi)信息量的變化趨勢是由大變小的。圖中曲線存在小幅波動，是因為跟蹤物體周圍存在干擾因素，但是誤差在允許范圍之內(nèi)。因此，可以利用信息量大小的變化情況來自動更新跟蹤窗口的大小。

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

圖2 信息量與目標大小的對應關系

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

圖3 跟蹤目標變小時信息量比值示意圖

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

圖4 跟蹤目標變大時信息量示意圖

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

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

(1)

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

W=W(1+S)

(2)

H=H(1+S)

(3)

2.3 基于Kalman-MeanShift的自適應跟蹤算法

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

具體的自適應跟蹤算法流程如圖5所示。

3 實驗及結果分析

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

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

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

圖5 自適應跟蹤算法流程

圖6 運動目標變小時跟蹤結果

圖7 運動目標變大時跟蹤結果

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

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

圖8 目標x軸坐標變化曲線

圖9 目標y軸坐標變化曲線

[1]楊戈，劉宏.視覺跟蹤算法綜述[J].智能系統(tǒng)學報，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的視覺目標跟蹤算法綜述[J].計算機科學，2012，39(12)： 16-24.

[7]王文江，黃山，張洪斌.一種基于Mean Shift和Kalman預測的帶寬自適應跟蹤算法[J].計算機工程與科學，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

國家自然科學基金項目(61373004)

TP391.41

A

10.16280/j.videoe.2015.05.011

2014-02-14

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

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

責任編輯：時 雯