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

陳瑞卿

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

關鍵詞：MeanShit算法 跟蹤算法 改進

中圖分類號：G420 文獻標識碼：A 文章編號：1674-098X（2015）03（a）-0056-01

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

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

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

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

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

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

2 對目標模型描述的改進

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

2.1 對分塊跟蹤算法的改進

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

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

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

3 試驗結果

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

4 結論和展望

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

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

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

參考文獻

[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.