基于塊的Mean-shift跟蹤算法

陳 柱，李子印，朱明凌

(中國計量學院 光學與電子科技學院，浙江 杭州 310018)

基于塊的Mean-shift跟蹤算法

陳 柱，李子印，朱明凌

(中國計量學院 光學與電子科技學院，浙江 杭州 310018)

針對傳統Mean-shift跟蹤算法在目標發生遮擋和形態變化時跟蹤性能下降的缺點，提出了一種基于塊的Mean-shift跟蹤算法，該算法主要特點有：1)將跟蹤目標平均分塊，每小塊獨立進行傳統Mean-shift跟蹤，利用小塊跟蹤未被遮擋的目標部分；2)跟蹤檢測器檢測目標小塊跟蹤的有效性，篩選出無效跟蹤的目標小塊，解決了目標分塊造成跟蹤性能下降的問題；3)歸一化互相關檢測器和鄰域一致檢測增加了對目標空間信息的檢測，彌補了Mean-shift算法的局限性，增加了跟蹤的魯棒性。實驗表明，該算法在目標發生遮擋和形態變化時仍然可以有效地實現跟蹤。

目標跟蹤；目標遮擋；形態變化；目標分塊；Mean-shift跟蹤算法

運動目標跟蹤已經被廣泛應用到社會生活的各個方面，但在實際應用中仍面臨著諸多的挑戰，如目標遮擋、形態變化等[1-3]。Mean-shift跟蹤算法是一種基于核概率密度估計的無參數算法，具有實時性強、計算量小和跟蹤精度高等特點，成為典型的目標跟蹤算法。但傳統Mean-shift跟蹤算法的跟蹤窗口保持不變，這樣當目標發生旋轉或尺度變化時，其跟蹤性能將會受到很大的影響。因此，研究人員不斷嘗試其改進算法[4-7]，文獻[4]采用上下二分的方法跟蹤運動目標，但該方法只適用于柱狀對象；文獻[6]采用了七部分的分塊方法，用平均值的方法代表每一個跟蹤小塊的Bhattacharyya系數，但該方法沒有考慮每個目標小塊相似度的變化對運動目標總體相似度的影響。

基于本文提出了一種基于塊的Mean-shift跟蹤算法，首先將目標平均分塊，各子塊分別使用Mean-shift跟蹤算法進行跟蹤，然后通過檢測器表決各子塊是否正確跟蹤，利用正確跟蹤的子塊更新目標，從而實現跟蹤。

1 Mean-shift跟蹤算法

Mean-shift跟蹤算法是一種基于概率密度估計的無參數算法，其在概率密度函數中快速迭代收斂于局部極大值，在每一次迭代過程中都是朝著最優值進行的，是一種高效的實時跟蹤算法[8-10]。

1.1 目標模型

首先獲取運動目標的初始位置，然后對獲得的區域建立目標模型qu，假設其中有n個像素，{zi}i=1，2，…，n分別表示每個像素的位置，對獲得的目標區域的灰度顏色空間進行均勻的劃分，便可以得到有m個相等區間構成的灰度直方圖，這樣目標模型qu的概率密度可表示為

(1)

(2)

(x0，y0)代表目標的中心坐標，C代表歸一化系數，其值可表示為

(3)

1.2 候選模型

與目標模型表示類似，設{zi}i=1，2，…，n是候選目標區域的像素位置，候選區域的目標中心位置坐標為f，則候選模型的概率密度可表示為

(4)

其中，h為核函數窗口的大小，決定著權重的分布。

1.3 Bhattacharyya相關系數

用來表示目標模型和候選模型的相似度，可定義為

(5)

ρ(p,q)越大，則目標模型和候選模型越相似。

1.4 目標定位

為了使ρ(p,q)最大，對其進行泰勒展開，得到Bhattacharyya相關系數的近似表達

(6)

其中，ωi可表示為

(7)

ρ(p,q)的其他參數都已確定，只有ωi的值隨f的變化而變化，這樣求極大值的過程就可以通過目標候選區域的中心向目標真實區域的中心的Mean-shift迭代方程完成

(8)

其中，g(x)=K′(x)是核函數K(x)的影子核。Mean-shift方法即從fk起向目標模型和候選模型顏色變化最大的方向不斷地移動，直到最后2次移動的距離小于閾值，便找到了當前幀的目標位置，并以此作為下一幀的起始搜索窗口的中心，如此反復，即可不斷實現對目標的跟蹤。

2 基于塊的Mean-shift跟蹤算法

Mean-shift的跟蹤在實際應用中存在一些缺點。首先，Mean-shift跟蹤算法過分依賴運動目標的顏色信息，而忽略了運動目標的空間信息，這樣當顏色相似的物體重疊時，便可能導致對運動目標跟蹤的失??；再次，當運動目標發生形態發生變化時，容易造成跟蹤失?。蛔詈?，當運動目標發生遮擋時，Mean-shift算法獲得的運動目標的位置坐標有可能出現錯誤，從而導致跟蹤失敗。

針對實際復雜環境中出現的目標遮擋和形態變化的問題以及上述Mean-shift跟蹤算法存在的不足之處，本文提出了一種基于塊的Mean-shift跟蹤算法。

2.1 分塊跟蹤

設運動目標的區域為M，將M平均分割為x×y個目標小塊，如圖1所示，每個小塊的圖像尺寸不能過小，因為Mean-shift跟蹤算法本身是基于顏色直方圖的，當每個小塊的尺寸過小時，目標所包含的信息量就會很少，容易造成跟蹤的失敗，另外尺寸過小也不能適應運動目標的突變等運動。所以，本文采用把目標小塊分割成不小于10×10像素的方法，對分塊后的每一個目標小塊獨立地進行Mean-shift跟蹤，跟蹤前使用卡爾曼濾波預測目標位置，并在目標位置的基礎上確定對應目標小塊的具體位置信息，以此作為跟蹤的起點。這樣做的好處是：目標遮擋、形態變換的問題主要表現為目標信息的丟失，每一小塊獨立跟蹤，并分別判斷是否跟蹤有效，以此來判斷目標的局部信息是否丟失，這樣當目標出現部分遮擋或者形態變化時，可以通過跟蹤有效的目標小塊來實現對目標的跟蹤。

圖1 運動目標分塊

然而運動目標往往由幾個層次的顏色區域組成，均勻分塊會把同一個顏色區域分為不同的塊，以一輛汽車為例，車輛車身的顏色幾乎是一致的，將汽車進行均勻分塊可能導致有些塊與塊之間的圖像信息是相似的，這樣目標小塊就有可能無法跟蹤到真實的目標區域，針對該問題，本文加入了跟蹤檢測器，通過跟蹤檢測器來檢測每一小塊是否跟蹤有效。

2.2 跟蹤檢測器

本文的跟蹤檢測器由歸一化互相關檢測器和鄰域一致檢測器組成，這兩種檢測器分別按照各自的方法對目標小塊進行檢測，只有當2個檢測器都判斷為正確時，目標小塊才能被認為是跟蹤有效的小塊，否則剔除。

歸一化互相關檢測器是用NCC(NormalizedCrossCorrelation)算子[11]來衡量原目標小塊和跟蹤后得到的區域小塊之間的像素相似程度，NCC算子是一種經典的圖像匹配算子，表征2幅圖像的相似程度，其中I1，I2是尺寸為m×n的兩幅圖像

(9)

NCC的取值范圍為0～1，其值越大，則表示2幅圖像越相似。

歸一化互相關檢測器對每一個目標小塊依次進行檢測，計算每個目標小塊與跟蹤后得到的目標區域的NCC值，若該值大于設定的閾值Th，認為目標小塊有效，否則認為是無效的目標小塊。

(10)

對于閾值Th的取值，本文引入平均相關系數Rs，Rs表示兩幅圖像的像素灰度平均相似程度，IM為運動目標圖像，IP為當前幀圖像,則Rs可表示為

(11)

鄰域一致檢測器的假設前提是分塊后的目標小塊在各自跟蹤后，相鄰目標小塊的位移矢量是相似的。因此，鄰域一致檢測器通過檢測每個目標小塊與其四鄰域的目標小塊的跟蹤位移矢量是否相符，若位移矢量不相符，則認為該目標小塊是無效的塊。

跟蹤檢測器的作用是對目標分塊跟蹤后進行判斷，檢測出無效跟蹤的目標小塊，篩選出具有較高魯棒性的目標小塊作為目標跟蹤的依據。傳統的Mean-shift跟蹤缺少了對目標空間信息的描述，而歸一化互相關檢測器通過比較每一個目標小塊相鄰兩幀整體像素的相似程度來做出判斷，只有當目標小塊相鄰兩幀整體像素空間分布具有較高的相似度時才能通過該檢測器，鄰域一致檢測器通過檢測目標小塊的位移矢量來做出判斷。因此，這兩種檢測器都能夠對目標的空間信息進行檢測，在一定程度上彌補了Mean-shift跟蹤的不足之處。

2.3 算法實現步驟

本文算法實現步驟如下：

1)將當前幀的運動目標M平均分成x×y個目標小塊，使用卡爾曼濾波器預測運動目標位置，并在目標位置的基礎上確定對應目標小塊的具體位置信息。

2)對各目標小塊分別進行Mean-shift跟蹤。

3)計算運動目標的平均相關系數Rs，作為閾值Th，比較各目標小塊的NCC值與閾值Rs的大小，如果NCC的值大于閾值，則保留目標小塊，否則剔除。

4)統計保留下來的各目標小塊跟蹤后的位移矢量，比較每個小塊與其四鄰域小塊的位移矢量，如果存在矢量夾角大于90°，則認為該目標小塊跟蹤突變，予以剔除，否則保留。

5)將跟蹤檢測器保留下來的目標小塊作為跟蹤依據，并更新運動目標M，作為下一幀跟蹤的模型。

算法具體流程如圖2所示。

圖2 基于塊的Mean-shift算法流程圖

3 實驗結果及分析

為了驗證本文算法的性能，使用VS2010在Intel Core(TM)i3-2120 CPU 3.3 GHz，內存為2 Gbyte的計算機上，分別對傳統Mean-shift跟蹤算法、文獻[6]算法和本文算法進行測試。

1)跟蹤結果比較

實驗1為行人的跟蹤，其中目標行人伴隨著遮擋變化，跟蹤結果如圖3所示。圖3a為傳統Mean-shift算法的跟蹤結果，圖3b為文獻[6]算法的跟蹤結果，圖3c為本文算法的跟蹤結果。在未發生遮擋時，傳統算法、文獻[6]算法和本文算法都能很好地進行跟蹤，當目標發生遮擋時，由于傳統 Mean-shift 跟蹤算法缺少足夠的目標信息，進而陷入局部極大值，從而使跟蹤的結果產生較大的偏移，最終導致跟蹤的失??；文獻[6]算法采用了七部分的分塊方法，用平均值的方法代表每一個跟蹤小塊的Bhattacharyya系數，能夠在一定程度上實現跟蹤，但跟蹤窗口的中心與運動目標的中心有一定的偏差；本文算法由于采用了目標的分塊跟蹤，當目標發生部分遮擋時，可以對未被遮擋的目標很好地進行Mean-shift跟蹤，并且每一幀目標小塊的初始位置經卡爾曼濾波估計確定了其位置信息，這樣跟蹤后的目標小塊經過跟蹤檢測器的檢測后，有效的目標小塊被保留下來，同時最終的跟蹤結果整合了所有小塊的跟蹤信息，從而能夠很好地實現跟蹤。

圖3 跟蹤結果比較

實驗2同樣為行人的跟蹤，其中目標行人的視角由遠到近，跟蹤結果如圖4所示。其中，圖4a為傳統Mean-shift算法的跟蹤結果，圖4b為文獻[6]算法的跟蹤結果，圖4c為本文算法的跟蹤結果。由于傳統Mean-shift算法在目標跟蹤過

圖4 跟蹤算法比較

程中跟蹤窗口的大小保持不變，這樣在跟蹤過程中目標模式總是使得Bhattacharyya系數在同樣大小的跟蹤窗口中達到局部最大，從而不能準確的實現跟蹤；文獻[6]算法采用了七部分的分塊方法，用平均值的方法代表每一個跟蹤小塊的Bhattacharyya系數，這樣跟蹤窗口可以隨著目標的變化而變化，從而能夠很好地實現跟蹤，但跟蹤窗口的中心與運動目標的中心有一定的偏差；本文算法采用了目標的分塊，對每個小塊分別進行Mean-shift跟蹤，當目標的視覺角度發生變化時，利用分割后的目標小塊進行Mean-shift跟蹤，并且每一幀目標小塊的初始位置經卡爾曼濾波估計確定了其位置信息，這樣跟蹤后的目標小塊經過跟蹤檢測器的檢測后，有效的目標小塊被保留下來，同時最終的跟蹤結果整合了所有小塊的跟蹤信息，從而能夠很好地實現跟蹤。

2)跟蹤成功率統計

為了更準確地統計跟蹤結果的成功率，采用PASCALVOC標準[12]對運動目標跟蹤的成功率進行統計，其示意圖如圖5所示。

圖5 重合度計算示意圖

其中，真實目標區域為Sa，跟蹤結果區域為Sb，則跟蹤結果與真實目標的重合度Rc可表示為二者交集與二者并集的面積之比，即

(12)

其中，area表示每個區域的面積，area(Sa∩Sb)表示兩者的重疊面積，area(Sa∪Sb)表示兩者的面積之和。對于每一幀的跟蹤結果，如果Rc大于0.5，則代表跟蹤成功；否則代表跟蹤失敗。

表1為本文算法、傳統Mean-shift跟蹤算法和文獻[6]算法在兩個實驗視頻中的跟蹤成功率統計。從表中可以看出，本文算法在兩個實驗中都有很好的跟蹤成功率。

表1 跟蹤成功率統計

視頻本文算法傳統Mean-shift算法文獻[6]算法實驗一096063084實驗二098038093

4 小結

針對傳統Mean-shift跟蹤算法在目標發生遮擋和形態變化時，跟蹤性能下降的問題，本文提出了一種基于塊的 Mean-shift跟蹤算法，首先將目標平均分塊，并利用卡爾曼濾波預測目標的位置，每一個目標小塊分別獨立地進行Mean-shift跟蹤，然后通過跟蹤檢測器檢測目標小塊跟蹤的有效性，進而對目標模型進行更新。實驗表明，當運動目標發生遮擋或形態發生變化等復雜場景時，本文算法能夠有效地實現跟蹤，改善了傳統Mean-shift跟蹤算法的局限性，具有更高的魯棒性，但本算法的運算復雜度還比較高，下一步可嘗試改進分塊的方法。

[1] 張鈺婷，王沛，馬燕，等. 改進的多特征融合粒子濾波視頻跟蹤算法[J].電視技術，2014，38(19)：47-50.

[2] 劉雪琴，楊媛，李潔，等. 一種基于特征點的快速跟蹤算法[J]. 電視技術，2013，37(5)：34-37.

[3] 魯超，滕國偉，鄒雪妹，等. 一種適應運動前景的快速行人檢測算法[J]. 電視技術，2015，39(1)：113-117.

[4] OKUMA K，TALEGHANI A，DE F N，et al. A boosted particle filter： multi-target detection and tracking [C]// Proc of the European Conference on Computer Vision. Prague：IEEE Press，2004：28-39.

[5] 陳定坤，楊艷. 一種改進的Mean-shift運動目標跟蹤算法[J]. 半導體光電，2015，36(1)：160-164.

[6] MAGGIO E，CAVALLARO A. Multi-part target representation for color tracking[C]//Proc. IEEE Int. Conference on Image Processing. Genoa：IEEE Press，2005：729-732.

[7] 胡銦，楊靜宇.基于分塊顏色直方圖的Mean-Shift跟蹤算法[J].系統仿真學報，2009，21(10)：2936-2940.

[8] 王田，劉偉寧，韓廣良，等.基于改進MeanShift的目標跟蹤算法[J]. 液晶與顯示，2012，27(3)：396-400.

[9] COMANICIU D， MEER P. Mean Shift： a robust approach toward feature space analysis[C]//Proc. IEEE Trans. Pattern Analysis and Machine Intelligence，2002，24(5)：603-619.

[10] COLLINS R. Mean-Shift blob tracking through scale space[C]// Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]：IEEE Press，2003，2：234-240.

[11] 楊通鈺，彭國華.基于NCC的圖像匹配快速算法[J]. 現代電子技術，2010(22)：107-109.

[12] EVERINGHAM M，GOOL L，WILLIAMS C， et al. The Pascal Visual Object Classes (VOC) challenge [J]. International Journal of Computer Vision，2010，88(2)：303-338.

陳 柱(1989— )，碩士生，主研圖像處理、模式識別；

李子印(1978— )，博士，副教授，碩士生導師，主要研究方向為圖像處理、模式識別、視頻壓縮與通信等；

朱明凌(1989— )，碩士生，主研圖像處理、視頻壓縮與通信。

責任編輯：閆雯雯

Mean-shift Tracking Algorithm Based Block

CHEN Zhu, LI Ziyin, ZHU Mingling

(College of Optical and Electronic Technology, China Jiliang University, Hangzhou 310018, China)

The mean-shift tracking algorithm based on block is proposed to solve the problem that tracking performance of traditional mean-shift algorithm decline under the occlusion and variation of target. Firstly, the target is divided into some similarly sized blocks which are tracked unobstructed part of target by traditional Mean-shift algorithm. Secondly, the effectiveness of target blocks are estimated by tracking detector and the invalid blocks are screened from the target, so the problem that the reduction of tracking performance which is caused by target blocks is solved. Thirdly, much more spatial information can be detected by normalized cross correlation detector and neighborhood homogeneity detector, so the limitation of mean-shift algorithm is made up and the robustness of tracking is increased. Experiment results indicate that the proposed algorithm can track under the occlusion and variation of target efficiently and accurately.

target tracking; target occlusion; variation of target; target blocked; Mean-shift tracking algorithm

國家自然科學基金項目(61007012)；國家科技支撐計劃項目(2012BAF07B05-3)

TN911.73

A

10.16280/j.videoe.2015.20.002

2015-04-08

【本文獻信息】陳柱，李子印，朱明凌.基于塊的Mean-shift跟蹤算法[J].電視技術,2015，39(20).