一種基于ｍｅａｎ ｓｈｉｆｔ的魯棒性目標跟蹤方法

摘要：目標模型內的背景像素會造成目標跟蹤定位偏差，但為了將跟蹤目標全部包含在目標模型中，不可避免在目標模型內引入很多背景像素。為了減少背景對跟蹤造成偏差，在目標模型中引入帶權因子，可達到降低目標模型內背景像素對跟蹤定位精度的影響。帶權因子是這樣確定的：通過利用目標外圍矩形環中的背景信息和一個映射函數來生產一個新的特征向量，然后轉換為帶權因子。實驗表明，該方法具有更好的跟蹤精度，對遮擋具有更好的魯棒性。

關鍵詞：mean shift;目標跟蹤;目標模型; Bhattacharyya系數

中圖分類號：TP301；TP391文獻標志碼：A

文章編號：1001－3695(2008)06－1753－03

Mean shift是一個由Fukunaga和Hostetler在1975年提出的一種無監督聚類方法，它使每一個點漂移到密度函數的局部極大值點。1995年，Cheng[1]重新研究了mean shift，提出了更一般的表達形式并預示該算法在聚類和全局優化方面的巨大潛力。Comaniciu在1999年作了mean shift的應用方面研究。自此以后，mean shift已廣泛應用于目標跟蹤[2~4]、圖像分割[5]、聚類分析[6]等領域。

Comaniciu在文獻[2，3]中首先將mean shift算法應用到目標跟蹤領域中來，利用Bhattacharyya系數作為目標模型與候選目標之間的相似性度量標準，用mean shift算法來搜索最優候選目標，獲得了很好的跟蹤效果。此后，有更多的研究者投入到了此項研究之中，Comaniciu[7]和彭寧嵩等人[8]分別提出了針對mean shift算法的窗口自動選取方法；彭寧嵩等人[9]還提出了一種mean shift跟蹤算法中的目標模型更新的方法。但是mean shift跟蹤算法仍然存在跟蹤偏差或者完全跟不上目標的情況。目標模型內的背景像素會造成目標跟蹤定位的偏差。當目標模型中包含的背景像素較少時，mean shift目標跟蹤可以獲得好的效果。但為了將跟蹤目標全部包含在目標模型中，不可避免引入很多背景像素，必然會造成跟蹤的偏差。為了減少背景對跟蹤造成的偏差，一種直觀的思路是在計算目標的顏色核直方圖時不考慮背景像素，這樣在進行相似性度量時，對背景信息的干擾具有好的魯棒性，在一定程度上減少背景信息的影響，能增加目標跟蹤的抗干擾魯棒性，但這樣的方法在實現上存在困難。文獻[10]使用中心—周圍(center－surround)的方法從目標和背景中采樣像素。中心矩形部分表示目標，外圍的矩形環表示背景，分別建立規則化直方圖。通過特征分布的log似然率得到新目標模型表示方法，然后利用mean shift算法來實現目標跟蹤，這種方法有效地克服了目標模型中背景像素對跟蹤性能的影響。但另一方面由于定位的不準確或者發生遮擋，使得中心矩形包含的目標不完整，反而會引起跟蹤偏差的擴大。本文在目標模型中引入帶權因子，帶權因子表明背景特征與目標特征的相似程度，可以達到減少目標模型內背景像素對跟蹤定位精度的影響，同時也增強了對定位不精確和遮擋的魯棒性。

1基于mean shift的目標跟蹤方法

視頻目標跟蹤是mean shift算法應用的一個重要方面，大多文獻沿用Comaniciu[2，3]的方法，采用Bhattacharyya系數作為相似性度量標準，使用mean shift算法來獲取目標位置。基于mean－shift的跟蹤算法將顏色核直方圖作為目標特征的描述，假定目標模型和候選目標特征分別表示為q={qu}u=1，…，m和 p(y)={pu(y)}u=1，…，m。其中：y是候選目標的中心位置，且 ∑mu=1qu=1， ∑mu=1pu=1；m為特征值中bin的個數。兩者的Bhattacharyya系數為ρ(y)≡ρ[p(y)，q]。為了得到一個相對于空間位置y平滑的相似函數，目標模型的特征表示為 qu=C∑ni=1k(‖xi‖2)δ[b(xi)-u]。其中：δ(·)為Kronecker delta函數；{xi}i=1，…，n是歸一化的目標模型像素位置，歸一化后目標模型中心像素位置為0；b∶R2→{1，…，m}為像素點到像素特征的映射；C是歸一化常數。相應的候選目標的特征為

帶權因子vu是結合目標模型及其周圍背景像素而得到，表明背景像素對目標模型中單個特征的影響程度。對vu有如下要求：滿足1≥vu≥0；當vu=0時，則表示該目標特征與背景特征相似，對目標模型中的特征值影響大，這樣就可以剔除目標模型內的背景特征；當vu=1時，則該目標特征與背景特征相差很大，對目標模型中的特征值影響最小，這時保留該特征值。為此，需要考慮背景像素和目標像素來獲取vu，獲取加權核直方圖的方法如圖1所示。本文使用中心—周圍的方法[10]從目標和背景中來采樣像素。首先選擇一個覆蓋目標的像素矩形集來描述目標模型，而選擇目標外圍的矩形環內像素來描述背景。假設內部矩形框包含h×w個像素，背景像素的外部邊緣的尺寸為rh×rw，一般r>1，取r＝2。獲取目標矩形像素，形成顏色核直方圖，并歸一化形成離散的概率目標分布pu；另外獲取目標外圍的矩形環內背景像素，形成顏色直方圖，并歸一化形成離散的概率背景分布qu。其中1≤u≤m。對于每個目標和背景特征，通過一個映射函數f(pu，qu)合成一個新的特征L(u)來增加目標和背景差異，即L(u)＝f(pu，qu)。函數f(pu，qu)的選擇有這樣的要求：合成的特征L(u)描述了目標內的表示目標的像素，而不包含背景像素。也就是說當qu較大時，表明該特征描述了背景信息，則L(u)應小，即刪除該特征。當qu較小時，表明該特征受背景的影響小，盡量保留或增加該特征的值。根據上述要求，函數f(pu，qu)采用特征分布的log似然率函數，如式(4)。

這種通過計算目標與背景特征值分布的log似然率來實現特征值的變換方法，在獲得的新特征中剔除了目標中背景像素的影響，增加了目標像素特征的影響，降低了背景像素的影響，從而實現增大候選目標模型之間差別的目標，在每次跟蹤準確或者沒有遮擋的前提下，單純使用這種特征L(u)來實現mean shift跟蹤能獲得好的效果。在這種情況下，目標模型和背景信息的描述準確，但當目標被遮擋或者部分遮擋時，目標描述本身不完整導致特征L(u)的歧義，反而會增加跟蹤目標的定位偏差，使得跟蹤更不準確，而且上述方法忽略了目標的顏色信息。為了克服這種影響，本文融合上述方法和顏色核直方圖，以減少歧義L(u)對目標跟蹤精度的影響。新特征L(u)對目標跟蹤的影響是通過帶權因子對顏色核直方圖影響來實現的。為此，本文將新特征L(u)轉換為核直方圖的帶權因子，滿足上面對帶權因子的兩個要求，以提高抗遮擋的魯棒性和目標跟蹤的準確性。新特征滿足log δ≤f(pu，qu)≤-log δ，必須通過一個映射方法轉換到[0，1]范圍內，且滿足對帶權因子的要求。本文采用映射方法如式(5)。

3跟蹤方法的實施

采用上述基于mean shift 的跟蹤方法，但這里除了上述目標模型和候選模型引入帶權因子外，還有三個問題需要解決：

a）對于核函數的選擇，比較常用的有高斯核函數k(x)=e-x、Epanechnikov、截斷高斯函數。對于高斯核函數來說，當x較大時，高斯核函數的值很小，對目標跟蹤的精度影響很小，但會增加了計算量。而對于Epanechnikov核，mean shift算法相當于每次迭代時求目標的質心點坐標，具有Epanechnikov核的mean shift的收斂性沒有得到證明。截斷的高斯函數是通過參數λ來限制計算的范圍，相比高斯核函數來說計算量要大大減少，而且能保證算法的收斂性[11]。參數λ的選擇對于目標跟蹤的穩定性是很重要的。假如λ太小，則目標易丟失，太大，則計算時間太長，實時性能差。一般 λ=1．5-2．5，實驗中取2。

b）實際中，H采用對角矩陣 H=diag[h21，…，h2d]或為h2I，I為d×d為單位矩陣。一種簡單的方法[3]是令hprev是前一幀的帶寬，分別使用三個不同的帶寬通過mean shift算法獲得具有最大Bhattacharyya系數的h。這種方法的缺點是三次使用mean shift算法，會增加目標跟蹤的計算時間，降低實時性。mean shift算法中向量y中包含目標中心坐標(x， y)的計算，為方便起見，本文使帶寬矩陣H中包含目標的寬和高，即取H為H=diag[h2x，h2y]。其中hx， hy分別描述了運動目標的寬和高。為提高目標跟蹤的實時性，本文使用mean shift算法找到目標的中心坐標(x， y)后，搜索最優hx， hy使得ρ[p(y)，q]最大。帶寬搜索區域不能太大，否則實時性差，本文采用hx， hy各伸縮10%的范圍內進行搜索最優帶寬。

c）對于迭代初始點，一般以前一幀目標的中心位置作為當前幀mean shift迭代的起始點，如果目標運動較慢，能取得好的效果，但當目標運動較快或者目標被遮擋時，mean shift算法無法搜索到目標位置。為了保證跟蹤的實時性，本文采用線性預測來獲取初始位置。

4實驗結果及分析

從室外環境獲取視頻，并截取120幀視頻來進行目標跟蹤實驗。目標及其初始位置假設已知，通過mean shift算法，能實現目標的跟蹤，甚至目標被遮擋了也能找到目標位置，但是這遮擋的時間不能太長，否則目標將會丟失。為了更準確更直觀地比較跟蹤效果，實驗中使用下式來計算第i幀位置跟蹤的偏差：errori=|Ti-Ci|，Ti表示跟蹤的第i幀位置，Ci表示準確的第i幀位置，errori表示偏離準確位置的偏差，可用來衡量跟蹤定位方法的準確性。另外用下式來衡量目標跟蹤的平均偏差： average∑Ni=1errori/N。實驗中分別用上面兩式來計算各幀中目標位置在x，y方向的偏差和平均偏差。Ci的值是通過手工方法獲的，雖然這種方法對單幀中目標精確定位帶有很強的主觀性，會帶來一些誤差，但從整體上來看對比較結果不會有太大影響，特別是對計算的平均偏差幾乎不會有影響。

4．1實驗結果及分析

本文方法與標準mean shift方法[3]實驗比較結果如圖2~5所示。圖2分別表示視頻中14、22、40、51、59、91、104、107幀跟蹤的對比結果，從中可看出本文方法的優越性。

在x，y方向的定位偏差的比較如圖3，圖中IMS表示本文方法，MS表示mean shift方法，以下相同。本文方法與mean shift方法在x方向的定位平均偏差分別是3．21，5．03；在y方向的定位平均偏差分別是3．62，7．08。偏差的減少的原因主要有兩個：a)顏色核直方圖中帶權因子的引入，減少了目標模型中背景像素的影響，增加了候選目標模型之間的差異，使得定位更精確；b)由于線性預測的引入使得具有一定的抗遮擋魯棒性。迭代次數的比較如圖4，本文方法與mean shift方法的平均迭代次數分別為22．49、27．55。迭代次數的減少主要是由于引入了線性預測機制來進行初始位置的預測，使得初始位置在精確位置附近，從而使的mean shift算法更容易找到目標位置。本文方法對于Bhattacharyya系數值的影響總的來說不大，但當目標被遮擋時，本文方法的系數值比mean shift方法大。Bhattacharyya系數值的比較如圖5，本文方法與mean shift方法的Bhattacharyya系數平均值分別為0．948、0．947。

4．2參數B的影響

在式(5)中，參數B的大小影響目標跟蹤的效果，控制vu 在[0，1]內的分布密度，B越大，則vi分布越廣，否則vi分布越集中。因此分析B對目標跟蹤精度的影響是非常必要的。實驗中B對跟蹤影響分析的結果如圖6所示。從圖6中可看出，B＝10~18，有較好的跟蹤效果，本文實驗中取B=10。

4．3算法的時間復雜度分析

標準的mean shift算法的平均時間代價是Nmax(ncs，m)，max(x， y)表示求x與y之間的最大者，這里N是平均迭代次數，n是目標區域的像素個數，cs是額外的做除法和開方的代價。如果假設bin的個數m與目標區域的像素個數在相同的范圍，則平均代價是Nncs[3]。相比于標準的mean shift算法，f(p(i)，q(i))需要在每次迭代時進行計算，其時間代價是max(n′，m)，n′是外部矩形框區域中像素個數，因此改進后的算法的時間代價是Nmax(n′，ncs，m)，當n′≤ncs時，不會增加算法的時間代價，只是在計算時少許增加了計算的時間。

5結束語

本文主要解決目標模型中的背景信息影響跟蹤精度的問題。為了減少目標模型中背景信息的影響，在目標模型中引入帶權因子。帶權因子是這樣確定的：通過利用目標外圍矩形環中的背景信息，利用一個映射函數（log似然率函數）來生產一個新的目標特征向量，然后轉換為帶權因子。這種帶權因子的引入能增加候選目標模型之間差異，更精確定位目標位置。另外通過線性預測確定初始迭代位置，減少了迭代次數，增強了抗遮擋的魯棒性。實驗表明，本文方法具有更好的跟蹤精度，對遮擋具有更好的魯棒性。雖然該方法實現的跟蹤效果有所改進，但實際上還有其他一些因素會影響跟蹤的精度，如上述mean shift算法是通過對Bhattacharyya系數泰勒展開近似獲得的，這種近似會引起定位的偏差；另外mean shift算法采用顏色核直方圖作為目標模型的表示方式，沒有考慮目標的空間信息或其他目標內在信息。這些都是筆者下一步的工作。希望作的這些研究能為mean shift算法的應用添磚加瓦。

參考文獻：

［1］ CHENG Y. Mean shift， mode seeking， and clustering[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1995，17(8):790－799.

［2］COMANICIU D， RAMESH V， MEER P. Real－time tracking of non－rigid objects using mean shift[C]//Proc ofIEEE Conf on Computer Vision and Pattern Recognition. Hilton Head Island:[s.n.]，2000: 142－149.

［3］COMANICIU D， RAMESH V， MEER P. Kernel－based object trac－king[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2003，25(5):564－577.

［4］COLLINS R T. Mean shift blob tracking through scale space[C]//Proc ofConf on Computer Vision and Pattern Recognition. Madison， Wisconsin:[s.n.]:2003: 234－240.

［5］COMANICIU D. Image segmentation using clustering with saddle point detection[C]//Proc of IEEE Int’l Conf on Image Processing， Rochester. New York:[s.n.]，2002: 297－300.

［6］GEORGESCU B， SHIMSHONI I， MEER P. Mean shift based clustering in high dimensions: a texture classification example[C]//Proc ofICCV. Nice:[s.n.]，2003: 456－ 463.

［7］COMANICIU D. An algorithm for data－driven bandwidth selection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，2003，25(2): 281－288.

［8］彭寧嵩，楊杰，劉志，等.Mean shift跟蹤算法中核函數窗寬的自動選取[J].軟件學報，2005， 16(9):1542－1550.

［9］PENG N S，YANG J， LIU Z. Mean shift blob tracking with kernel histogram filtering and hypothesis testing[J]. Pattern Recognition Letters， 2005， 26(5): 605－614.

［10］COLLINS R T， LIU Y， LEORDEANU M. Online selection of discriminative tracking features[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2005，27(10): 1631－1643.

［11］COMANICIU D， MEER P. Mean shift: A robust approach toward feature space analysis[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2002，24(5): 603－619.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文