基于均值漂移的改進(jìn)目標(biāo)跟蹤算法

劉天鍵，邱立達(dá)，張 寧

（閩江學(xué)院物理學(xué)與電子信息工程系，福州350108）

基于均值漂移的改進(jìn)目標(biāo)跟蹤算法

劉天鍵，邱立達(dá)，張 寧

（閩江學(xué)院物理學(xué)與電子信息工程系，福州350108）

在可視化跟蹤過程中目標(biāo)窗經(jīng)常會(huì)由于遮擋、光照、姿勢(shì)等變化而發(fā)生跟蹤漂移，影響目標(biāo)跟蹤的準(zhǔn)確性和穩(wěn)定性。為解決該問題，提出一種基于圖層的離散域均值漂移算法，在離散域提取基于核的直方圖作為目標(biāo)模型，并對(duì)離散分區(qū)中的目標(biāo)函數(shù)進(jìn)行平滑以避免尋優(yōu)搜索陷入局部極小值，從而提高目標(biāo)跟蹤性能。實(shí)驗(yàn)結(jié)果表明，與多示例學(xué)習(xí)算法相比，該算法的跟蹤精度提高了16%，具有更好的實(shí)時(shí)性和魯棒性。

目標(biāo)跟蹤；目標(biāo)表示；離散域模型；均值漂移；迭代尋優(yōu)

1 概述

目前，目標(biāo)跟蹤已經(jīng)成為機(jī)器視覺領(lǐng)域的一個(gè)重要研究方向，現(xiàn)已提出許多針對(duì)目標(biāo)跟蹤的解決方案，主要有一般法和判別法2類可視跟蹤算法。一般法采用尋優(yōu)的方式解決目標(biāo)跟蹤問題，比如模板匹配、均值漂移和粒子濾波［1-3］；判別法通過區(qū)分目標(biāo)和背景的方法解決跟蹤問題，從而把跟蹤問題轉(zhuǎn)化為二值分類器設(shè)計(jì)問題，比如OAB（Online AdaBoost）［4］、多示例學(xué)習(xí)（M ultip le Instance Learning，M IL）［5-6］、跟蹤學(xué)習(xí)檢測(cè)（Tracking Learning and Detectiong，TLD）［7-8］。判別法需要通過多個(gè)目標(biāo)和背景樣本在線訓(xùn)練分類器。上述2種方法各有優(yōu)缺點(diǎn)，跟蹤效果依賴目標(biāo)表示模型。在目標(biāo)表示模型中，有基于模板的表示和基于特征的表示以及基于全局的表示和基于局部的表示。基于模板表示的模型簡單，但對(duì)目標(biāo)空間結(jié)構(gòu)過于敏感，如文獻(xiàn)［9］指出基于模板表示的模型存在的主要問題是目標(biāo)函數(shù)不夠平滑使得搜索易陷入局部最小值。通常采用高斯金字塔的方法模糊圖像以達(dá)到平滑目標(biāo)函數(shù)的目的。但近年來的研究結(jié)果表明，高斯金字塔并非是平滑目標(biāo)函數(shù)的最佳選擇。利用特征模型提取目標(biāo)的邊緣、顏色、紋理特征作為目標(biāo)特征，使用直方圖來描述目標(biāo)，對(duì)姿勢(shì)變化不敏感但對(duì)目標(biāo)空間結(jié)構(gòu)變化敏感。在特征模型表示目標(biāo)的算法中，均值漂移算法以其高效、實(shí)時(shí)性能引起學(xué)者們的廣泛關(guān)注。該算法是一種基于核密度估計(jì)的模式匹配算法，利用視覺特征，比如灰度、顏色等信息描述跟蹤目標(biāo)，通過迭代計(jì)算最新的樣本分布來估計(jì)非參概率密度，從而實(shí)現(xiàn)目標(biāo)的定位和跟蹤。均值漂移算法在引入到機(jī)器視覺領(lǐng)域后，用于解決圖像濾波、圖像校準(zhǔn)、目標(biāo)跟蹤等問題。但在跟蹤過程中，目標(biāo)表觀和背景變化會(huì)影響特征模型的表示，目前仍是跟蹤算法面臨的主要問題。文獻(xiàn)［10］提出一種基于背景加權(quán)的直方圖算法以消除目標(biāo)模型中的背景干擾，但該方法在減少背景信息的同時(shí)模糊了前景信息，導(dǎo)致跟蹤器性能下降。學(xué)者們對(duì)于改善直方圖的空間信息進(jìn)行了大量研究，包括多核、多片區(qū)方法［11］。文獻(xiàn)［12］提出一種方向梯度直方圖（Histogram of Gradient，HOG）方法，當(dāng)目標(biāo)表觀發(fā)生遮擋時(shí)，仍能穩(wěn)定跟蹤目標(biāo)，但該方法對(duì)噪聲敏感，跟蹤準(zhǔn)確性易受尺度、分辨率的影響。其他改進(jìn)方法，如增加高階統(tǒng)計(jì)矩、時(shí)域信息和特征選擇［1-2］，這些方法提高了傳統(tǒng)直方圖法的性能，但需要確定核函數(shù)的數(shù)量和形狀，增加了算法復(fù)雜度。文獻(xiàn)［13］提出一種新型的目標(biāo)表示模型，即分布域（D istribution Field，DF）目標(biāo)描述子模型，能夠平滑目標(biāo)函數(shù)的同時(shí)保留目標(biāo)的像素信息，在復(fù)雜環(huán)境下跟蹤目標(biāo)可獲得滿意的效果。文獻(xiàn)［14］提出一種基于分布域表示的多示例學(xué)習(xí)跟蹤器，在分布域選擇判別能力強(qiáng)的特征替換Harr特征，獲得了魯棒的跟蹤效果。基于此，本文提出一種離散域均值漂移（D iscrete Field M ean Shift，DFMS）算法，在均值漂移框架中引入離散域目標(biāo)表示模型，通過改進(jìn)均值漂移算法，實(shí)現(xiàn)對(duì)目標(biāo)由粗到細(xì)的跟蹤。

2 離散域目標(biāo)表示

在文獻(xiàn)［3］中，離散域（DF）目標(biāo)模型定義像素為某一特征值的概率分布數(shù)組。例如，在灰度特征空間，每個(gè)像素在0～255之間存在一個(gè)概率分布。離散域模型用（2+N）維的矩陣d表示，前2維分別表示目標(biāo)圖像的高度和寬度，其余N維對(duì)應(yīng)不同的特征空間。對(duì)于灰度特征空間分辨率為h×w的圖像，輸出的三維離散域模型為h×w×m，m為灰度特征值的分區(qū)數(shù)。將一個(gè)圖像I按照分區(qū)數(shù)擴(kuò)展成矩陣d：

其中，i和j分別表示圖像的行和列；K表示可能的像素值，稱為分區(qū)中的一層。由于模型沿著特征維的向量和為1，因此可以看成是一個(gè)概率分布。DF首先在χ和y維分別用2D高斯濾波器進(jìn)行平滑，即對(duì)于每一圖層K進(jìn)行濾波，在傳播信息的同時(shí)不會(huì)損失信息。

其中，h是標(biāo)準(zhǔn)差為σs的高斯核；“*”表示卷積。卷積前，d（i，j，K）中為1的值可以解釋為在原始圖像中這個(gè)位置有一個(gè)灰度級(jí)為L的像素。卷積后，中為1值的語義為在原始圖像中靠近這個(gè)位置有一個(gè)灰度級(jí)為L的像素，這樣就在模型中引入了位置不確定性。由于在卷積過程中沒有引入其他圖層的像素值，因此不會(huì)造成目標(biāo)像素值信息的損失。如果式（2）中的卷積核本身符合概率分布，那么仍然可以保持沿特征維的和為1，滿足DF模型要求。在特征域進(jìn)行與空間域類似的操作，使得模型能夠適應(yīng)目標(biāo)表觀、姿勢(shì)和陰影的變化，如式（3）所示對(duì)進(jìn)行特征維平滑后輸出。

其中，hσf是標(biāo)準(zhǔn)差為σf的高斯核。為便于推導(dǎo)，將h×w×m維的d～重構(gòu)為n×m維的矩陣ν，n= h×w。

擴(kuò)展和平滑后的DF可以看成在目標(biāo)表觀模型中引入不確定性。DF模型反映了原始圖像在表觀和位置的小范圍變化結(jié)果，是相鄰圖像集合中的一種緊湊表示模型。模型中的權(quán)值滿足簡單假設(shè)，即相鄰圖像中像素值保持不變的概率較大、發(fā)生變化的概率較小。采用DF模型衡量目標(biāo)相似度時(shí)，可以用不同的距離度量函數(shù)比較目標(biāo)模型和候選模型，本文采用巴氏距離度量。在跟蹤過程中，DF模型的更新采用FIR濾波實(shí)現(xiàn)。

為評(píng)價(jià)DF模型的性能，基于引力盆特性對(duì)DF與其他描述子進(jìn)行比較。引力盆定義為圍繞點(diǎn)P的一個(gè)區(qū)域，在這個(gè)區(qū)域中的任何位置都能通過目標(biāo)函數(shù)梯度下降最后達(dá)到點(diǎn)P。采用廣泛性和專注性評(píng)估引力盆的性能［3］。廣泛性是指描述子適用的對(duì)象廣度，廣泛性越廣表現(xiàn)為引力盆的引力半徑越大；專注性是描述子適用單一對(duì)象的程度，專注性高的描述子表現(xiàn)為引力盆斜坡陡、半徑小。圖1顯示了不同描述子的引力盆作用范圍，可以看出，DFMS描述子具有比基于核的均值漂移（M ean Shift，M S）描述子更寬的收斂半徑，同時(shí)比基于直方圖的Bhatta描述子更平滑的特性。對(duì)于Bhatta描述子而言，由于模糊化的DF模型使得亮度加權(quán)范圍更大，因此DF模型廣泛度更廣；同時(shí)由于沒有混入不同亮度級(jí)的像素，對(duì)于MS描述子，DF模型專注度更高。

圖1 各目標(biāo)描述子的目標(biāo)函數(shù)比較

3 基于均值漂移算法的目標(biāo)跟蹤

假設(shè)t時(shí)刻跟蹤目標(biāo)選擇為像素位置為｛χi｝i=1，2，…，n的矩形區(qū)域，用K：R2→R+表示核函數(shù)，不同位置對(duì)應(yīng)不同權(quán)值。基于核的目標(biāo)DF模型可以表示為：

其中，c為核函數(shù)的中心位置；ν（i，j）表示第j層DF模型；C為歸一化因子，使得∑mj=1qj=1。對(duì)于每一個(gè)圖層ν有νj=νj（t）=DF（χi，t）=ν（：，j）。將這些νj組合成n×m的矩陣。定義核函數(shù)向量為Ki（c）= K（χi，c），得到目標(biāo)模型。

假設(shè)時(shí)刻t′，目標(biāo)候選模型的中心為c，候選DF模型表示為：

目標(biāo)函數(shù)采用離散域的巴氏距離度量，尋優(yōu)過程求距離最小值等同于求相似度最大值。因此，可以通過估計(jì)目標(biāo)位置求得相似度函數(shù)最大值。

其中，尋優(yōu)過程通過計(jì)算梯度，并使梯度等于0得到相似度函數(shù)最大值。式（11）圍繞P（c）進(jìn)行泰勒級(jí)數(shù)展開，忽略高次項(xiàng)后，得到距離最小化的條件為：

最優(yōu)解可以表示為加權(quán)平均的形式：

其中，g（χ）=-K′（χ）。尋優(yōu)過程可以看成是在目標(biāo)函數(shù)上的梯度降過程。為進(jìn)一步提高算法性能，采用多個(gè)DF模型描述目標(biāo)，這些模型按照對(duì)應(yīng)的σs值遞減排列，即調(diào)整空間模糊度，使得DF模型包含不同頻率的信息。在跟蹤過程中，采用從粗到細(xì)的DF模型進(jìn)行搜索，最平滑的DF模型最先用于搜索，達(dá)到局部最小值后，啟用第2個(gè)DF繼續(xù)搜索，從而提高算法實(shí)時(shí)性。本文在均值漂移算法框架中，引入離散域目標(biāo)表示，用模糊數(shù)組代替目標(biāo)模型中的函數(shù)，使得目標(biāo)函數(shù)伸展平滑，從而提高系統(tǒng)性能。設(shè)置空間平滑參數(shù)，亮度平滑參數(shù)σf=0.625，?f=5，分區(qū)數(shù)m=16，學(xué)習(xí)因子λ= 0.95，目標(biāo)跟蹤過程具體如下：

（1）初始化目標(biāo)離散域模型，并對(duì)二維空間X，Y及特征空間進(jìn)行平滑：

（2）初始化目標(biāo)位置（χ1；y1）。

（3）計(jì)算候選目標(biāo)離散域模型：

（4）對(duì)目標(biāo)函數(shù)尋優(yōu)，得到目標(biāo)位置估計(jì)（χ′；y′）。

（5）更新如下模型并返回步驟（3）循環(huán)操作直到最后一幀：

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文算法性能，在公開測(cè)試集上［15］與OAB（Online AdaBoost）［4］，SBT（Sem i-supervised Tracking）［5］，BSBT（Beyond Semi-supervised Tracking）［6］，多示例學(xué)習(xí)（Multiple Instance Learning，M IT）［7］，跟蹤學(xué)習(xí)檢測(cè)（Tracking Learning andDetecting，TLD）［8］算法進(jìn)行性能比較。在6個(gè)不同視頻序列中進(jìn)行對(duì)比測(cè)試，包含遮擋、姿勢(shì)變化、光照變化和目標(biāo)形變等場景。測(cè)試平臺(tái)在一臺(tái)硬件為Intel i7 3770 CPU 3.4 GHz、6 GB RAM，軟件為Matlab7.8的PC上進(jìn)行。為定量比較跟蹤器性能，采用預(yù)測(cè)邊界框與基準(zhǔn)邊界框的中心位置誤差（Center Location Error，CLE）和重疊率（Overlap Rate，OVR）2個(gè)評(píng)價(jià)指標(biāo)。OVR比CLE更具參考價(jià)值，因?yàn)楫?dāng)跟蹤失敗時(shí)，CLE可以是某個(gè)任意值，而OVR值總為0。DFMS參數(shù)設(shè)置如第3節(jié)所示。圖2給出了定性比較的結(jié)果。

圖2 算法定性比較結(jié)果

可以看出，在適當(dāng)遮擋、光照變化和姿勢(shì)變化的序列中，DFMS獲得了魯棒的跟蹤結(jié)果和較高的跟蹤精度。在coke序列中包含劇烈的光照變化和適當(dāng)遮擋，第189幀，當(dāng)跟蹤的可樂罐從臺(tái)燈移動(dòng)到葉子中時(shí)，由于發(fā)生了光照變化和部分遮擋，其他跟蹤算法跟蹤失敗，而本文算法仍可以正確地跟蹤目標(biāo)。在其他序列中，本文算法也具有較好的跟蹤性能。在這些序列中，DFMS能在一個(gè)很寬的引力盆范圍中按照梯度降的方法回到基準(zhǔn)位置。表1給出了定量比較結(jié)果。

表1 算法跟蹤性能比較

圖3是6種算法在coke序列上的中心位置誤差（CLE）和重疊率（OVR）指標(biāo)，其中，CLE的門限值為20個(gè)像素；OVR的門限值為25%，可以看出，DFMS明顯優(yōu)于其他算法。采用正確率、成功率進(jìn)行性能比較［15］，并進(jìn)一步利用曲線下面積（AUC）排名［15］綜合評(píng)價(jià)跟蹤器的性能。

圖3 算法在coke序列上的定量評(píng)價(jià)結(jié)果

從圖4可以看出，DFMS的目標(biāo)中心平均距離的正確率比M IL算法提高了16%，DFMS在保持成功率（s）的基礎(chǔ)上，顯著提高了正確率（P）。可見，DFMS算法可以適應(yīng)復(fù)雜環(huán)境的變化，如適當(dāng)遮擋、表觀變化、姿勢(shì)和光照變化等。例如，當(dāng)發(fā)生遮擋時(shí)，DF模型隨著遮擋物變化而更新，由于遮擋物與目標(biāo)處于不同圖層，因此模型被遮擋像素在目標(biāo)圖層附近呈現(xiàn)較小的概率。如果在接下來的數(shù)幀中，遮擋物消失，DF模型將不會(huì)被遮擋物污染，并能成功地避免漂移。這正是本文算法能夠能在多個(gè)視頻序列中獲得滿意效果的原因。而且參數(shù)σs和σf的選擇也很重要，如果σs選得太大，模糊范圍增大，目標(biāo)函數(shù)平滑，對(duì)目標(biāo)空間結(jié)構(gòu)不敏感，DF模型趨同，將導(dǎo)致目標(biāo)細(xì)節(jié)信息的丟失。如果選得太小，模糊程度不夠，目標(biāo)函數(shù)不夠平滑，跟蹤器易陷入局部最小值。因此，需要根據(jù)按照目標(biāo)尺寸選擇σs，通常是大目標(biāo)選擇大σs，小目標(biāo)選擇小σs。另外，σf的選擇也受到其他因素的影響，例如，表觀模型中灰度的方差，如果σf減小，則跟蹤小目標(biāo)的性能趨向變好；如果σf增大，則跟蹤大目標(biāo)的性能趨向變好。核函數(shù)的選擇對(duì)結(jié)果影響不大，為使g（χ）=-K′（χ）= 1，選擇Epanechnikov核函數(shù)。參數(shù)λ控制模型的更新速度，如果λ值較大，則更新慢，容易克服遮擋，但不容易適應(yīng)表觀變化；如果λ值較小，則更新快、適應(yīng)變化快。綜上所述，應(yīng)根據(jù)應(yīng)用場景的需要在克服遮擋和適應(yīng)表觀變化之間進(jìn)行折中選擇。

圖4 算法在6個(gè)視頻序列上的定量評(píng)價(jià)結(jié)果

5 結(jié)束語

本文提出一種基于圖層的改進(jìn)型均值漂移（DFMS）算法。該算法在跟蹤過程中采用DF模型，該模型對(duì)姿勢(shì)變化不敏感，對(duì)目標(biāo)幾何結(jié)構(gòu)敏感，并且在實(shí)現(xiàn)目標(biāo)模型模糊的同時(shí)，能避免目標(biāo)模型被污染。因此，DFMS應(yīng)用于表觀、姿勢(shì)、光照等適當(dāng)變化的場景時(shí)，能取得較好的跟蹤性能。下一步將結(jié)合梯度方向、尺度變化的跟蹤場景對(duì)本文提出的均值漂移算法進(jìn)行改進(jìn)，從而實(shí)現(xiàn)目標(biāo)的魯棒跟蹤。

［1］ Cannons K J，Gryn J M，Wildes R P.Visual Tracking Using a Pixelwise Spatiotemporal Oriented Energy Representation［C］//Proceedings of the 11th European Conference on Computer Vision.New York，USA：ACM Press，2010：511-524.

［2］ Liu Tianjian，Zhang Zutao.Adaptive Double Kalm an Filter and Mean Shift for Robust Fast Object Tracking［J］.International Journal of Advancements in Computing Technology，2013，5（6）：349-356.

［3］ 詹建平，黃席樾，沈志熙，等.基于均值漂移和卡爾曼濾波的目標(biāo)跟蹤方法［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，24（3）：76-80.

［4］ Stalder S，Grabner H，van Gool L.Beyond Semisupervised Tracking：Tracking Should Be as Simple as Detection，but Not Simpler than Recognition［C］// Proceedings of IEEE International Conference on Computer Vision Workshops.Washington D.C.，USA：IEEE Press，2009：1409-1416.

［5］ Ning Jifeng，Shi Wuzhen，Yang Shuqin，et al.Visual Tracking with Online Multiple Instance Learning［J］. Image and Vision Computing，2009，31（11）：983-990.

［6］ 黃葉玨，鄭河榮.基于在線多示例提升隨機(jī)蕨叢的目標(biāo)跟蹤［J］.計(jì)算機(jī)應(yīng)用，2012，32（11）：3178-3181.

［7］ Kalal Z，Matas J，Mikolajczyk K.P-N Learning：Bootstrapping Binary Classifiers by Structural Constraints［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2010：49-56.

［8］ 王守超，李小霞.基于在線學(xué)習(xí)和結(jié)構(gòu)約束的目標(biāo)跟蹤算法［J］.計(jì)算機(jī)工程，2012，38（18）：140-143.

［9］ Szeliski R.Image Alignment and Stitching：A Tutorial［J］.Foundations and Trends in Computer Graphics and Vision，2006，2（1）：101-104.

［10］ Ning Jifeng，Zhang Lei.Robust Mean-shift Tracking with Corrected Background-weighted Histogram［J］.IET Computer Vision，2012，6（1）：62-69.

［11］ Mobahi H，Zitnick C L，Ma Y.Seeing Through the Blur［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA：IEEE Press，2012：1736-1743.

［12］ Dalal N，Triggs B.Histogram s of Oriented Gradients for Human Detection［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D.C.，USA：IEEE Press，2005：886-893.

［13］ Sevilla-lara L，Learned-miller E.Distribution Fields for Tracking［J］.IEEE Conference on Computer Vision& Pattern Recognition，2012，157（10）：1910-1917.

［14］ Ning Jifeng，Shi Wuzhen，Yang Shuqi，et al.Visual Tracking Based on Distribution Fields and Online Weighted Multiple Instance Learning［J］.Image and Vision Computing，2013，31（11）：853-863.

［15］ Wu Yi，Lim Jong-Woo，Yang Ming-Hsuan.Online Object Tracking：A Benchmark［C］//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D.C.，USA：IEEE Press，2013：2411-2418.

編輯 陸燕菲

ImProved Object Tracking Algorithm Based on Mean Shift

LIU Tianjian，QIU Lida，ZHANG Ning
（Department of Physics and Electronic Inform ation Engineering，Minjiang University，F(xiàn)uzhou 350108，China）

In the process of visual tracking，target window is always drifted for the illumination light change，deformation and poses change which affect the accuracy and robust tracking performance.To solve this problem，this paper proposes a novel M ean Shift（MS）algorithm based on picture layer which represents target model by the kernel histogram in the discrete fields.In order to improve the tracking performance，the objective function is smoothed to avoid falling into the localminimum in the search procedure.Experimental results show that the tracking precision of proposed algorithm increases by 16%com pared with Multiple Instance Learning（M IL）algorithm，and it has better real-time and robustness.

object tracking；object representation；discrete domain model；M ean Shift（MS）；iterative optimization

劉天鍵，邱立達(dá)，張 寧.基于均值漂移的改進(jìn)目標(biāo)跟蹤算法［J］.計(jì)算機(jī)工程，2015，41（9）：281-285，291.

英文引用格式：Liu Tianjian，Qiu Lida，Zhang Ning.Im proved Object Tracking Algorithm Based on M ean Shift［J］. Computer Engineering，2015，41（9）：281-285，291.

1000-3428（2015）09-0281-05

A

TP242.6

10.3969/j.issn.1000-3428.2015.09.052

福建省教育廳基金資助項(xiàng)目（JA12263，JB11127）；福州市科技合作基金資助項(xiàng)目（2013-G-86）。

劉天鍵（1975-），男，副教授、博士，主研方向：目標(biāo)檢測(cè)與跟蹤；邱立達(dá)、張 寧，講師、碩士。

2015-03-03

2015-05-14 E-m ail：skybright@aliyun.com