陳 柱，李子印，朱明凌

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

基于塊的Mean-shift跟蹤算法

陳 柱，李子印，朱明凌

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

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

目標(biāo)跟蹤；目標(biāo)遮擋；形態(tài)變化；目標(biāo)分塊；Mean-shift跟蹤算法

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

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

1 Mean-shift跟蹤算法

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

1.1 目標(biāo)模型

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

(1)

(2)

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

(3)

1.2 候選模型

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

(4)

其中，h為核函數(shù)窗口的大小，決定著權(quán)重的分布。

1.3 Bhattacharyya相關(guān)系數(shù)

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

(5)

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

1.4 目標(biāo)定位

為了使ρ(p,q)最大，對其進(jìn)行泰勒展開，得到Bhattacharyya相關(guān)系數(shù)的近似表達(dá)

(6)

其中，ωi可表示為

(7)

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

(8)

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

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

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

針對實(shí)際復(fù)雜環(huán)境中出現(xiàn)的目標(biāo)遮擋和形態(tài)變化的問題以及上述Mean-shift跟蹤算法存在的不足之處，本文提出了一種基于塊的Mean-shift跟蹤算法。

2.1 分塊跟蹤

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

圖1 運(yùn)動目標(biāo)分塊

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

2.2 跟蹤檢測器

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

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

(9)

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

歸一化互相關(guān)檢測器對每一個目標(biāo)小塊依次進(jìn)行檢測，計(jì)算每個目標(biāo)小塊與跟蹤后得到的目標(biāo)區(qū)域的NCC值，若該值大于設(shè)定的閾值Th，認(rèn)為目標(biāo)小塊有效，否則認(rèn)為是無效的目標(biāo)小塊。

(10)

對于閾值Th的取值，本文引入平均相關(guān)系數(shù)Rs，Rs表示兩幅圖像的像素灰度平均相似程度，IM為運(yùn)動目標(biāo)圖像，IP為當(dāng)前幀圖像,則Rs可表示為

(11)

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

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

2.3 算法實(shí)現(xiàn)步驟

本文算法實(shí)現(xiàn)步驟如下：

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

2)對各目標(biāo)小塊分別進(jìn)行Mean-shift跟蹤。

3)計(jì)算運(yùn)動目標(biāo)的平均相關(guān)系數(shù)Rs，作為閾值Th，比較各目標(biāo)小塊的NCC值與閾值Rs的大小，如果NCC的值大于閾值，則保留目標(biāo)小塊，否則剔除。

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

1)跟蹤結(jié)果比較

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

圖3 跟蹤結(jié)果比較

實(shí)驗(yàn)2同樣為行人的跟蹤，其中目標(biāo)行人的視角由遠(yuǎn)到近，跟蹤結(jié)果如圖4所示。其中，圖4a為傳統(tǒng)Mean-shift算法的跟蹤結(jié)果，圖4b為文獻(xiàn)[6]算法的跟蹤結(jié)果，圖4c為本文算法的跟蹤結(jié)果。由于傳統(tǒng)Mean-shift算法在目標(biāo)跟蹤過

圖4 跟蹤算法比較

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

2)跟蹤成功率統(tǒng)計(jì)

為了更準(zhǔn)確地統(tǒng)計(jì)跟蹤結(jié)果的成功率，采用PASCALVOC標(biāo)準(zhǔn)[12]對運(yùn)動目標(biāo)跟蹤的成功率進(jìn)行統(tǒng)計(jì)，其示意圖如圖5所示。

圖5 重合度計(jì)算示意圖

其中，真實(shí)目標(biāo)區(qū)域?yàn)镾a，跟蹤結(jié)果區(qū)域?yàn)镾b，則跟蹤結(jié)果與真實(shí)目標(biāo)的重合度Rc可表示為二者交集與二者并集的面積之比，即

(12)

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

表1為本文算法、傳統(tǒng)Mean-shift跟蹤算法和文獻(xiàn)[6]算法在兩個實(shí)驗(yàn)視頻中的跟蹤成功率統(tǒng)計(jì)。從表中可以看出，本文算法在兩個實(shí)驗(yàn)中都有很好的跟蹤成功率。

表1 跟蹤成功率統(tǒng)計(jì)

視頻本文算法傳統(tǒng)Mean-shift算法文獻(xiàn)[6]算法實(shí)驗(yàn)一096063084實(shí)驗(yàn)二098038093

4 小結(jié)

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

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

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

[3] 魯超，滕國偉，鄒雪妹，等. 一種適應(yīng)運(yùn)動前景的快速行人檢測算法[J]. 電視技術(shù)，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] 陳定坤，楊艷. 一種改進(jìn)的Mean-shift運(yùn)動目標(biāo)跟蹤算法[J]. 半導(dǎo)體光電，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].系統(tǒng)仿真學(xué)報(bào)，2009，21(10)：2936-2940.

[8] 王田，劉偉寧，韓廣良，等.基于改進(jìn)MeanShift的目標(biāo)跟蹤算法[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]. 現(xiàn)代電子技術(shù)，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— )，博士，副教授，碩士生導(dǎo)師，主要研究方向?yàn)閳D像處理、模式識別、視頻壓縮與通信等；

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

責(zé)任編輯：閆雯雯

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

國家自然科學(xué)基金項(xiàng)目(61007012)；國家科技支撐計(jì)劃項(xiàng)目(2012BAF07B05-3)

TN911.73

A

10.16280/j.videoe.2015.20.002

2015-04-08

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