基于多尺度空間的mean shift目標跟蹤算法?

（海軍工程大學 武漢 430033）

1 引言

近些年目標跟蹤算法已取得了很大的進步，然而為了簡化跟蹤模型，幾乎所有的目標跟蹤算法都假設目標的運動是平滑的，不存在突然變化［1～7］。在物體運動速度過快導致目標在相鄰兩幀中不存在重疊區域時，常常會收斂到一個錯誤的位置。

模板匹配算法無需任何關于目標運動的假設。然而，由于需要對整個圖像進行窮盡搜索，算法時間復雜度過高。許多文獻提出了加快模板匹配速度的方法，主要可以分為三類［8～11］：1）由粗及精的策略，先在低分辨率上粗匹配再在高分辨率上進行精匹配，然而這種方法要求低分辨率上的粗匹配必須取得較好的效果；2）對圖像和模板進行下采樣，這種方法會略去很多像素點，包括具有全局或局部最佳的點；3）估計似然函數的上界或者下界并削減不必要的操作，然而不是所有的似然函數都能找到上界或者下界。

本文提出了一種基于多尺度空間的目標跟蹤算法。首先利用通過基于直方圖的模板匹配算法在整個圖像中尋找候選點，然后以這些點為初始點結合mean shift算法找到對應的局部極值，以最大局部極值對應點作為目標最終估計。最后利用尺度空間更新模板的尺寸和匹配窗口。

2 基于直方圖的模板匹配

直方圖是對旋轉、形變以及部分遮掩有一定的魯棒性。通過用直方圖來表征模板T，則模板匹配過程可以定義為在當前幀中尋找與模板具有相似直方圖的子圖像。用來表示模板T的歸一化直方圖，表示以y為中心的候選子圖像的直方圖，每個直方圖都含有m個分量。用Bhattacharyya系數作為相似度函數：

通過在當前幀中逐點比較q和p(y)可以構建一張似然圖。其中ρ(y)最大的點作為目標中心位置。

3 基于尺度自動選擇的由粗及精策略

設原始圖像為I(x，y)，高斯金字塔采用以下迭代方式進行定義：

其中w(m，n)為加權函數。L是多分辨率分層模型中的最低分辨率。L過大會導致第L層的抽象模型與原始模型有較大差別，從而無法反映原始模型的真實形象，過小的L則無法達到降低計算復雜度的效果。最好的L使得目標的抽象模型和原始模型相似的最低分辨率。

設目標模板當前縮小l倍，此時的目標模板為M(l)，在每一層上計算M(l)與M(0)之間的相似度S(l)。

f(l)是一個度量函數，例如，Bhattacharyya系數。M(0)表示原始的最高分辨率的目標模板。Lmax是一個事先確定的多分辨率分層模型的層數的最大值。有兩種方法確定最低分辨率L。一是使用固定閾值 Δ ：L=min{l|S(l)>Δ，l=1，2，…，Lmax}。二是使前后兩層模型之間相似度的差值達到最大：Lmax。

4 結合mean shift算法

當前幀中的所有候選點從最低分辨率到最高分辨率分層進行匹配，在低分辨率下未通過的候選點將不會傳遞到更高的層次進行進一步的評估。設在最高層所保留下來的候選點集為S：

δ是事先設定的閾值。I為當前幀。ρ(p)參考式（1）。記N為S中候選點的總個數。對S中每一個點p，以該點為初始位置利用mean shift算法找到它們各自對應的局部極值。這些mean shift過程將收斂到N個目標當前位置的估計其中，具有最大值的點作為目標位置的最終估計：

5 實驗

在本節，通過兩個實例來展示本文方法的優勢，跟蹤結果將和文獻［9］以及文獻［12］中的算法進行比較，分別稱為方法1和方法2。

如圖1所示，目標是跟蹤一輛靜止的軍用卡車。雖然卡車本身是靜止的，然而由于機載平臺的運動導致背景和卡車位置頻繁而無規則的變化。在這種情況下，方法1和方法2都無法跟蹤目標，而本文方法能有效地處理由于平臺運動所造成的問題并對目標進行準確跟蹤。

圖1 跟蹤卡車的實例

如圖2所示，目標跟蹤一個正在跑動中的人。該目標首先向前跑動，然后突然改變方向向后跑。運動方向的突然改變加大了跟蹤難度。開始時，所有方法都能正確跟蹤目標。然而，當目標突然改變運動方向時無論是方法1還是方法2都丟失了目標，只有本文方法仍然準確跟蹤目標。

表1給出了三種方法的定位誤差的均值和方差。跟蹤速度顯示在表2中。如表1所示，本文的方法比其他兩種方法能更魯棒和更準確的跟蹤目標。它具有最小的誤差均值和方差。如表2所示，雖然本文方法比其他兩種方法要慢，但是仍能基本滿足實時處理要求，特別是當目標的尺寸較小時。這種要求在大多數涉及機載平臺的應用中都能滿足。

第一行為方法1的結果，第二行為方法2的結果，第三行為本文的結果。

第一行為方法1的結果，第二行為方法2的結果，第三行為本文的結果。

表1 定位誤差的均值和方差

表2 三種方法的跟蹤速度

6 結語

本文提出了一種基于多尺度空間的mean shift目標跟蹤算法。該方法在諸如運動機載平臺等動態場景中能取得較好的效果。模板匹配方法用于處理全局運動而mean shift算法使得快速匹配方法具有更好的匹配結果。實驗證明這兩種方法的結合可以更準確和魯棒地跟蹤目標。