基于積分直方圖分塊的MeanShift跟蹤算法

陳瑞卿

摘 要：該文提出了一種新的基于積分直方圖分塊的MeanShift運動目標(biāo)跟蹤算法，采用積分圖分塊作為目標(biāo)描述算子，融合了顏色直方圖和空間信息，有效地解決了原始MeanShift跟蹤算法僅僅利用了顏色信息，而造成顏色相似運動目標(biāo)之間的誤匹配，大量的試驗結(jié)果表明，該文提出的方法，即使在復(fù)雜的場景中，也能夠魯棒準(zhǔn)確地實現(xiàn)運動目標(biāo)的定位并跟蹤。

關(guān)鍵詞：MeanShit算法 跟蹤算法 改進(jìn)

中圖分類號：G420 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2015）03（a）-0056-01

視頻圖像中運動目標(biāo)跟蹤是計算機(jī)視覺領(lǐng)域中一個關(guān)鍵問題，在視覺監(jiān)控、智能交通、感知用戶接口、虛擬現(xiàn)實、智能房間、遠(yuǎn)程醫(yī)療以及視頻編碼等領(lǐng)域都有著廣泛的研究價值和應(yīng)用前景。MeanShift算法作為一種高效的模式匹配算法，就是在每一幀圖像中尋找一個與目標(biāo)模板特征最相似的候選目標(biāo)區(qū)域，由于不需要進(jìn)行窮盡式的搜索，已經(jīng)成功地應(yīng)用在實時目標(biāo)跟蹤領(lǐng)域中。MeanShift算法僅僅考慮到跟蹤目標(biāo)的顏色信息，沒有考慮到空間信息，所以當(dāng)場景中出現(xiàn)和運動目標(biāo)顏色直方圖相似的目標(biāo)時，MeanShift算法會跟蹤失效。

該文所提出的運動目標(biāo)跟蹤算法，融合了目標(biāo)的顏色直方圖和空間信息，與單純地應(yīng)用基本的MeanShift相比，跟蹤的魯棒性和效果要提升很多。積分圖算法大大降低了鄰域匹配中不必要的計算，提高了算法的實時性。

該文第1節(jié)介紹基本的MeanShift跟蹤算法和基于積分直方圖的分塊跟蹤算法，第2節(jié)介紹本文提出的改進(jìn)算法，試驗結(jié)果在第3節(jié)給出，最后是結(jié)論和展望。

1 MeanShift算法與基于積分直方圖的分塊跟蹤算法

MeanShift算法對運動目標(biāo)進(jìn)行描述，采用了RGB顏色空間中的三通道彩色直方圖。在給定的RGB特征空間中，以概率密度函數(shù)q來表達(dá)目標(biāo)模型，候選目標(biāo)模型記作為p（y）。q與p（y）的相似性度量就是考慮目標(biāo)模板圖像和候選目標(biāo)圖像各個樣本點對之間的距離關(guān)系。距離越大表明相似性越小，反之相似性越大。故目標(biāo)的定位就轉(zhuǎn)化為測量相鄰兩幀圖像之間目標(biāo)模型和候選目標(biāo)模型的相似性系數(shù)。

文獻(xiàn)中介紹了一種基于積分直方圖的分塊跟蹤算法，其較MeanShift算法對目標(biāo)的定位準(zhǔn)確，但計算量較大，因為在跟蹤過程中，要計算圖像序列中各幀的積分直方圖和跟蹤目標(biāo)區(qū)域的積分直方圖，用20個跟蹤塊來描述運動目標(biāo)，且每一塊都要計算其積分直方圖，每一塊的搜索都是在給定區(qū)域中窮盡式搜索，這些都大大增加了跟蹤的時間消耗，對于跟蹤實時性無疑是一個巨大的挑戰(zhàn)。但這種跟蹤方法考慮了運動目標(biāo)的空間信息，較基本的MeanShift算法對目標(biāo)的定位是準(zhǔn)確的。

2 對目標(biāo)模型描述的改進(jìn)

MeanShift算法中對運動目標(biāo)的描述中，沒有考慮到運動目標(biāo)各個部分的空間信息，也就是說，對于一個框定目標(biāo)的矩形框或橢圓框來說，目標(biāo)處于該框的任何位置，其直方圖都是一樣的，假設(shè)在一種很極端的情況下，即要跟蹤的目標(biāo)上半部分是白色，下半部分是黑色，而后在視頻幀的某一幀中，在該目標(biāo)的附近出現(xiàn)了一個上半部分是黑色，下半部分是白色的目標(biāo)，其直方圖的分布可以看到，只利用目標(biāo)的顏色信息，其直方圖的分布是相似的，這時，如果利用MeanShift算法跟蹤時，很有可能跟蹤錯誤，但利用積分直方圖的分塊跟蹤方法時，由于其在描述目標(biāo)的時候，考慮到了跟蹤目標(biāo)各部分之間的空間信息，不會跟錯目標(biāo)，但跟蹤的實時性得不到滿足。

2.1 對分塊跟蹤算法的改進(jìn)

首先將分塊跟蹤算法中對于目標(biāo)的分塊操作進(jìn)行修改，即在選定的特征空間里，并假設(shè)運動目標(biāo)是用矩形框框住的前提下，對運動目標(biāo)分為五部分來描述，即將運動目標(biāo)從目標(biāo)中心位置開始，水平方向分為上下兩部分，垂直方向分為左右兩部分，并且在與跟蹤窗口的中心位置重合處得到一個小的跟蹤窗口，用這五部分的描述來反應(yīng)給定的跟蹤目標(biāo)。在跟蹤的過程中，也是分開跟蹤這五部分，最終將這五部分的跟蹤結(jié)果進(jìn)行加權(quán)組合，從而得到目標(biāo)在當(dāng)前幀中的最終位置。

2.2 綜合分塊跟蹤算法和MeanShift算法

為了滿足實時性的要求，不是將運動目標(biāo)的各個跟蹤塊在給定的區(qū)域進(jìn)行窮盡式搜索，而是用顏色直方圖來描述運動目標(biāo)的五部分，這樣會考慮到運動目標(biāo)的空間信息，不會像基本的MeanShift算法那樣丟失了目標(biāo)的空間信息，然后在給定搜索區(qū)域內(nèi)對每一部分進(jìn)行MeanShift算法的跟蹤，從而每一塊都會得到當(dāng)前幀中的目標(biāo)的位置，從而根據(jù)該塊與目標(biāo)中心的關(guān)系，可得到5個目標(biāo)位置，最后，將這5個位置進(jìn)行加權(quán)組合，從而得到目標(biāo)在當(dāng)前幀中的最終位置。

3 試驗結(jié)果

我們所做的跟蹤測試，都是在初始幀圖像中選定一個固定形狀的區(qū)域，譬如圓形、矩形或者是橢圓等等，并使得這個固定的區(qū)域能夠?qū)⑦\動目標(biāo)包圍，在隨后的各幀圖像中，只要搜索到的區(qū)域和這個固定區(qū)域包含的區(qū)域最相似即可。

4 結(jié)論和展望

該文算法只是考慮到了在對目標(biāo)模板進(jìn)行描述的過程中，加入了目標(biāo)模板的空間信息，與基本的MeanShift跟蹤算法相比，只是目標(biāo)的定位準(zhǔn)確了一些，但時間的消耗比基本的MeanShift算法大，且沒有考慮到所選擇的特征空間的更新和目標(biāo)模板的更新操作。

特征空間是從跟蹤一開始就給定了，在跟蹤的過程中，沒有對特征空間進(jìn)行更新，并且在整個跟蹤過程中，目標(biāo)模板始終保持不變，目標(biāo)在運動過程中，其外觀和背景都會發(fā)生相應(yīng)的變化，在跟蹤開始選定的特征空間或許就不能很好的區(qū)分跟蹤過程中的目標(biāo)和背景，肯定需要重新選擇合適的特征空間，也需對目標(biāo)模板進(jìn)行某種更新操作來達(dá)到跟蹤準(zhǔn)確的目的。

在下一步的工作中，我們將盡力解決這個問題。

參考文獻(xiàn)

[1] D.Comaniciu，V.Ramesh， and P.Meer.Kernel-based object tracking.IEEE Trans.Pattern Anal.Mach.Intell.2003，25（5）：564-577.

[2] D.Comaniciu，V.Ramesh，and P.Meer.Real-Time tracking of non-rigid objects using mean shift.In：Werner B，ed.IEEE Intl Proc.of the Computer Vision and Pattern Tecognition，Vol 2.Stoughton：Printing House，2000：142-149.