基于多尺度空間的mean shift目標(biāo)跟蹤算法?

（海軍工程大學(xué) 武漢 430033）

1 引言

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

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

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

2 基于直方圖的模板匹配

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

通過在當(dāng)前幀中逐點(diǎn)比較q和p(y)可以構(gòu)建一張似然圖。其中ρ(y)最大的點(diǎn)作為目標(biāo)中心位置。

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

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

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

設(shè)目標(biāo)模板當(dāng)前縮小l倍，此時的目標(biāo)模板為M(l)，在每一層上計(jì)算M(l)與M(0)之間的相似度S(l)。

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

4 結(jié)合mean shift算法

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

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

5 實(shí)驗(yàn)

在本節(jié)，通過兩個實(shí)例來展示本文方法的優(yōu)勢，跟蹤結(jié)果將和文獻(xiàn)［9］以及文獻(xiàn)［12］中的算法進(jìn)行比較，分別稱為方法1和方法2。

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

圖1 跟蹤卡車的實(shí)例

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

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

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

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

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

表2 三種方法的跟蹤速度

6 結(jié)語

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