基于分塊顏色直方圖的MS跟蹤算法

張紅穎，王賽男，胡文博

（中國民航大學(xué)電子信息與自動化學(xué)院，天津 300300）

基于視覺的目標(biāo)跟蹤一直是計算機視覺領(lǐng)域的一個熱門分支[1-2]，其廣泛應(yīng)用于智能人機交互、視頻監(jiān)控及國防安全等領(lǐng)域。自從Comaniciu等[3]使用結(jié)合顏色直方圖的MS（mean shift）算法進行目標(biāo)跟蹤后，MS跟蹤算法憑借其簡單、有效的優(yōu)勢受到廣泛關(guān)注，但當(dāng)目標(biāo)與背景顏色相近或出現(xiàn)遮擋時，使用該算法會出現(xiàn)跟蹤丟失的情況。

為解決該問題，許多學(xué)者提出了各種改進算法[4]。文獻[5]在MS算法中引入自適應(yīng)Kalman濾波作為輔助手段，使其能夠預(yù)測跟蹤發(fā)生短時間遮擋的目標(biāo)，但是該方法對運動模型有一定的要求。文獻[6]提出使用遮擋因子作為遮擋的判定條件，但由于增加了計算的復(fù)雜度，無法滿足跟蹤的實時性要求。文獻[7]首先利用Bhattacharyya系數(shù)下降率來判斷跟蹤目標(biāo)是否出現(xiàn)了遮擋，若系數(shù)急劇下降，判斷出現(xiàn)遮擋，然后利用改進的GM（1，1）預(yù)測模型，對后續(xù)幀中的目標(biāo)位置進行預(yù)測，若目標(biāo)脫離遮擋，則繼續(xù)使用MS算法進行后續(xù)跟蹤，該方法復(fù)雜且對遮擋的判斷易受其他因素影響。

針對復(fù)雜場景下目標(biāo)遮擋問題，提出了一種基于分塊顏色直方圖的MS跟蹤算法。首先將目標(biāo)的整體區(qū)域顏色特征劃分成幾個局部區(qū)域的顏色特征。然后利用分塊顏色直方圖作為目標(biāo)表征模型，這樣得到的目標(biāo)特征具有較強的局部特征表達能力。最后為了準(zhǔn)確跟蹤目標(biāo)，提出了一種基于分塊顏色直方圖的置信圖生成方式，相較于傳統(tǒng)MS算法中使用的反向投影圖，置信圖能夠更精確地表示目標(biāo)的位置信息。實驗結(jié)果表明，該方法簡單易行，能有效解決復(fù)雜環(huán)境下的遮擋問題，具有較好的魯棒性。

1 MS跟蹤算法

對于d維空間中的n個點，點x處的MS向量表示為

其中：k表示n個點中，只有k個點落入?yún)^(qū)域；Sr是一個半徑為r的高維球區(qū)域，定義如下

可看出，MS向量就是對落入?yún)^(qū)域Sr（x）中的k個樣本點相對于點x的偏移量求和后取平均。因此，MS算法會使當(dāng)前點向點密度最高的區(qū)域移動，如圖1所示。

圖1 MS原理圖Fig.1 Schematic diagram of MS

考慮到每個樣本點的重要程度不同，離中心點較近的樣本點對估計更有效，因此在計算MS向量時給不同樣本點賦以不同的權(quán)值，可提高算法的魯棒性。MS算法使用徑向?qū)ΨQ的核函數(shù)進行加權(quán)，即

其中，cd是d維單位球的體積。

引入核密度梯度估計后，MS向量變?yōu)?/p>

其中：g（x）=-K′（x）；h為核函數(shù)窗口寬。MS算法就是從xi起向兩個模型相比顏色變化最大的方向不斷移動，直到最后兩次的移動距離小于閾值，即找到當(dāng)前幀的目標(biāo)位置，并以此作為下一幀的起始點，直到視頻跟蹤結(jié)束。

2 基于分塊顏色直方圖的MS跟蹤算法

2.1 分塊顏色直方圖

普通顏色直方圖統(tǒng)計的是目標(biāo)整體區(qū)域的顏色信息，因此無法有效地表達出目標(biāo)區(qū)域不同顏色的分布狀況。為解決上述問題，改進算法將HOG算法[8]的分塊思想引入顏色直方圖中，將目標(biāo)區(qū)域劃分成互不重疊的子單元box，將幾個box組成一個塊block，block之間相互重疊，如圖2所示。提取并記錄每個block的顏色直方圖特征，最后將所有的block特征組合形成整塊目標(biāo)區(qū)域的特征向量。

圖2 分塊子區(qū)域Fig.2 Block subregion

設(shè)目標(biāo)整體區(qū)域為寬高w×h的窗口，提取分塊顏色直方圖時，首先將該窗口分成m個大小為x×y的重疊子區(qū)域block，對每個block單獨提取顏色直方圖，然后將各block的短顏色直方圖按照固定順序連接成一個長顏色直方圖作為目標(biāo)區(qū)域的顏色特征。

為有效地提取分塊顏色直方圖特征的同時能盡量提高處理速度，計算分塊顏色直方圖特征前，需先對圖像進行降維處理。圖像的降維過程實際是采用線性差值法對圖像的尺寸進行比例縮小，降維因子scale根據(jù)跟蹤目標(biāo)大小和圖像質(zhì)量進行選擇。

2.2 HSV空間提取顏色信息

圖像多以RGB顏色空間的形式保存，但其空間各分量之間冗余信息較多，而HSV空間能獨立感知各分量的變化，較好地反映人眼對色彩的感知和鑒別能力。由RGB空間轉(zhuǎn)化為HSV空間的表達式如下

式中，0≤V≤1，0≤S≤1，0≤H≤360。在 HSV 空間提取顏色信息，為了減弱光照條件的影響，忽略亮度信息V，僅根據(jù)H和S通道像素值投票至顏色直方圖。在構(gòu)建顏色直方圖時遍歷子區(qū)域block中的每一個像素，得到每一子區(qū)域block的顏色直方圖后，逐一進行歸一化并按照各自的位置順序連接起來，組成完整的分塊顏色直方圖向量v。

2.3 基于分塊顏色直方圖的置信圖生成方法

如果一幅圖像的區(qū)域中顯示的是一種結(jié)構(gòu)紋理或一個獨特的物體，那么這個區(qū)域的直方圖可看成一個概率函數(shù)，其表現(xiàn)形式是某個像素屬于該紋理或物體的概率。改進算法所提出的置信圖[9-10]實質(zhì)上相當(dāng)于概率密度圖，其代表了目標(biāo)區(qū)域的特征在一幅新圖像中存在的概率，置信圖的灰度值越大則概率越高。

目標(biāo)模板和候選區(qū)域的直方圖之間的相似性選用相關(guān)方法，得到取值范圍為0～1的相似度系數(shù)d（H1，H2），可表示為

為了獲得置信圖，在獲得目標(biāo)區(qū)域完整的分塊顏色直方圖向量v0后，讀取下一幀圖像frame，按照如下步驟對圖像進行處理：

1）圖像降維；

2）按照從左到右，從上到下的順序用寬高為w×h的檢測窗口按照自定義的步長stride去移動檢測窗口；

3）求取當(dāng)前檢測窗口下的分塊顏色直方圖向量v，采用相關(guān)對比方法對 v[i]和 v0[i]，（i=0，1，…，m-1）進行直方圖對比，得到相似度系數(shù)di（v0[i]，v[i]）（i=0，1，…，m-1），對di（v0[i]，v[i]）相加并求出均值dmean，將dmean×255作為灰度值依次寫入到置信圖相應(yīng)的像素中；

4）若遍歷未結(jié)束，跳轉(zhuǎn)到第2步；

5）對置信圖的灰度值歸一化到區(qū)間0～255，并采用線性插值方法進行上采樣，調(diào)整到與圖像frame的尺寸一致。

傳統(tǒng)MS算法是在反向投影圖中進行迭代來尋找最佳匹配目標(biāo)位置，而改進算法則是采用置信圖的方式。置信圖的概念與反向投影類似但不完全一樣，置信圖相比反向投影圖具有更優(yōu)越的表達性能，在目標(biāo)跟蹤中具有更出色的表現(xiàn)，如圖3所示。

圖3 目標(biāo)區(qū)域的反向投影圖和置信圖對比Fig.3 Comparison between back projection and confidence map of target area

從圖3中反向投影圖和置信圖對比可知，反向投影圖目標(biāo)區(qū)域位置分散，不能精確地反映目標(biāo)區(qū)域特征，而置信圖中目標(biāo)區(qū)域位置集中，能夠很好地反映出目標(biāo)區(qū)域特征在下一幀圖像frame中的位置。

2.4 算法框架

MS算法是一種不需要任何先驗知識而完全依靠特征空間中樣本點來計算其密度函數(shù)值的核密度估計法。針對目標(biāo)遮擋問題，提出的基于分塊顏色直方圖的改進算法，整體流程圖如圖4所示。

圖4 改進算法流程圖Fig.4 Flow chart of impoved algorithm

首先在第1幀圖像中標(biāo)注目標(biāo)位置，然后對目標(biāo)區(qū)域提取分塊顏色直方圖特征作為目標(biāo)表征模型，接著讀取下一幀圖像，生成置信圖，最后利用MS算法在置信圖中迭代從而尋找目標(biāo)區(qū)域，實現(xiàn)跟蹤。循環(huán)直至整個視頻序列全部讀取完畢。

3 實驗結(jié)果與分析

為保持較好的精度，又能大幅縮短運行時間，實驗采用分塊重疊的子區(qū)域block提取顏色直方圖特征，參數(shù)設(shè)置為 m=9，scale=2，stride=6。

3.1 目標(biāo)未被遮擋情況分析

該情況下采用Visual Tracker Benchmark[11]中BoBot數(shù)據(jù)集的部分圖片序列，針對的主要是圖片中移動的人物目標(biāo)，背景較為復(fù)雜。該圖片序列為RGB三通道彩色圖像序列，分辨率為320×240。仿真結(jié)果如圖5～圖8所示。

由圖5～圖8分析可知：在第100幀，兩種算法都能較好地找到目標(biāo)區(qū)域；在第619幀，置信圖仍能夠較好地反映目標(biāo)區(qū)域位置，而反向投影圖的目標(biāo)區(qū)域已被嚴重干擾；在第924幀，改進算法依然精確地找到目標(biāo)區(qū)域位置，而傳統(tǒng)MS算法已完全跟丟目標(biāo)。

圖5 BoBot反向投影圖Fig.5 Back projection of BoBot

圖6 BoBot改進算法的置信圖Fig.6 Confidence map of BoBot based on improved algorithm

圖8 改進算法在BoBot中的跟蹤結(jié)果Fig.8 Tracking result of BoBot based on improved algorithm

3.2 目標(biāo)部分被遮擋情況分析

該情況下采用Visual Tracker Benchmark中faceocc1數(shù)據(jù)集的圖片序列，針對的主要是圖片中被遮擋的人臉目標(biāo)，遮擋情況由輕微遮擋到大面積遮擋，變化范圍較大。該圖片序列為RGB三通道彩色圖像序列，分辨率為352×288。仿真結(jié)果如圖9～圖12所示。

由圖9～圖12分析可知：在第41幀，由于目標(biāo)區(qū)域僅被輕微遮擋，兩種算法都能較好地找到目標(biāo)區(qū)域；在第555幀，目標(biāo)區(qū)域被嚴重遮擋，由于手部的顏色與面部顏色接近，置信圖出現(xiàn)了誤差，但由于MS算法是在局部尋找極值，所以手部的干擾并不會造成影響，置信圖仍能夠較好地反映目標(biāo)區(qū)域位置，而反向投影圖的目標(biāo)區(qū)域已被嚴重干擾，跟蹤錯誤；在第899幀，目標(biāo)區(qū)域幾乎恢復(fù)到了未被遮擋狀態(tài)，改進算法依然精確地找到了目標(biāo)區(qū)域位置，而傳統(tǒng)MS算法已無法再次找到目標(biāo)。

圖9 faceocc1反向投影圖Fig.9 Back projection of faceocc1

圖10 faceocc1改進算法的置信圖Fig.10 Confidence map of faceocc1 based on improved algorithm

圖11 傳統(tǒng)MS算法在faceocc1中的跟蹤結(jié)果Fig.11 Tracking result of traditional faceocc1 based on MS algorithm

圖12 改進算法在faceocc1中的跟蹤結(jié)果Fig.12 Tracking result of faceocc1 based on improved algorithm

3.3 目標(biāo)大面積被遮擋情況分析

該情況下采用VisualTrackerBenchmark中的Babenko數(shù)據(jù)集的部分圖片序列，針對的主要是圖片中移動的人臉目標(biāo)，背景顏色與人臉顏色相似，且存在大面積遮擋。該圖片序列為RGB三通道彩色圖像，分辨率為320×240。仿真結(jié)果如圖13～圖16所示。

由圖13～圖16分析可知：在第47幀，雖然人臉外形稍微變大，但兩種算法都能較好地找到目標(biāo)區(qū)域；在第105幀，人臉完全背向鏡頭，但由于在初始目標(biāo)區(qū)域中，分塊顏色直方圖包含了黑色頭發(fā)的顏色特征，即使人臉完全背向鏡頭，改進算法也能檢測出黑色的頭發(fā)，而反向投影圖的目標(biāo)區(qū)域已經(jīng)丟失；在第308幀，圖像背景顏色和初始區(qū)域目標(biāo)顏色相近，改進算法的置信圖仍然給出了精確的目標(biāo)位置，而反向投影圖已無法找到目標(biāo)區(qū)域，這是因為分塊顏色直方圖細致地劃分了初始目標(biāo)區(qū)域的顏色特征。

圖13 Babenko反向投影圖Fig.13 Back projection of Babenko

圖14 Babenko改進算法的置信圖Fig.14 Confidence map of Babenko based on improved algorithm

圖15 傳統(tǒng)MS算法在Babenko中的跟蹤結(jié)果Fig.15 Tracking result of Babenko based on traditional MS algorithm

圖16 改進算法在Babenko中的跟蹤結(jié)果Fig.16 Tracking result of Babenko based on improved algorithm

4 結(jié)語

針對復(fù)雜場景中的目標(biāo)遮擋問題，對MS跟蹤算法進行了研究和改進。為了得到較強的局部特征表達能力，將目標(biāo)的整體區(qū)域顏色特征劃分成幾個局部區(qū)域的顏色特征，利用分塊顏色直方圖作為目標(biāo)表征模型。為了準(zhǔn)確跟蹤目標(biāo)，提出了一種基于分塊顏色直方圖的置信圖生成方式，使MS算法在置信圖中迭代，得到目標(biāo)最佳區(qū)域。從目標(biāo)未被遮擋、目標(biāo)被部分遮擋、目標(biāo)與背景相似且存在大面積遮擋3種情況進行實驗，改進算法的效果優(yōu)于傳統(tǒng)MS跟蹤算法。由于改進算法對目標(biāo)的顏色直方圖進行了細致的劃分，且得到了可靠的置信圖，該算法對于目標(biāo)遮擋問題具有較好的魯棒性。