結合尺度估計MST和粒子濾波的視頻目標跟蹤

孫新領，張 皓，趙 麗

1.河南工學院 計算機科學與技術系，河南 新鄉453003

2.山西大學 軟件學院，太原030013

1 引言

視覺跟蹤是計算機視覺中最重要的領域之一，已被應用于多個領域，例如監控和人機交互等。但是，當存在遮擋、外觀和尺度變化情況下，仍然會引起各種問題[1-3]。在各種視覺跟蹤算法中，均值漂移跟蹤（Mean Shift Tracking，MST）算法[4-6]是最常用的方法之一，它具有易于實現且計算時間消耗較少的優點。MST方法的基礎是非參數密度估計器，由于它是使用顏色直方圖來表示模型，所以對部分遮擋和旋轉具有魯棒性。然而，MST 方法不能解決尺度變化、完全遮擋和模型改變等問題。此外，在外觀和光照變化的條件下實現長期跟蹤也十分困難[7-8]。

為了解決MST 的這些缺點，研究者已經提出了多種基于MST 的改進型跟蹤方案。例如，文獻[9]給出了一種改進的MST算法（EM-Shift），其同時估計局部模式的位置和描述局部模式近似形狀的協方差矩陣。文獻[10]利用自適應背景加權直方圖（BWH）方法來改進MST算法，并嘗試將輪廓直方圖和空間直方圖結合起來，使其可以利用背景信息，有效地減少背景對目標定位的干擾。但是，它無法處理對象的尺度變化。文獻[11]提出了一種稱為尺度和方向自適應MST 算法（SOAMST），使用加權圖像作為密度分布函數的尺度和方向，使其可以在MST 框架下估計物體的尺度和方向。但是SOAMST 算法對于目標的遮擋問題也無法處理。為此，一些學者融入了卡爾曼濾波器。例如，文獻[12]提出了一種將卡爾曼濾波與SOAMST 相結合的算法（KSOAMST），如果目標被部分遮擋，則直接使用SOAMST跟蹤目標；如果完全遮擋，則使用卡爾曼濾波器估計目標下一幀的位置。但是，卡爾曼濾波的性能隨著非線性強度變大會明顯下降。文獻[13]使用MST進行跟蹤，并利用它的相似性來調整卡爾曼濾波器的協方差。這種方法可以在被遮擋的情況下追蹤物體，但當物體移動速度變化較大時，無法跟蹤物體。

在本文中，提出了一種結合MST算法、探測器和粒子濾波器的目標跟蹤方法。主要創新點為：提出一種具有半監督學習能力的探測器來在線更新目標模型，自適應校正目標尺度，以此解決傳統MST 方法無法應對尺度變化的缺陷。此外，在發生完全遮擋時采用粒子濾波器估計目標的位置，以此改善MST 無法處理完全遮擋的問題。實驗結果表明，該方法能夠成功跟蹤復雜環境中的目標。

2 目標跟蹤方法的框架

本文所提出的目標跟蹤方法的流程圖如圖1所示，主要包括MST、探測器和粒子濾波器。首先，通過MST算法跟蹤對象，基于Bhattacharyya系數來確定是否跟蹤成功。如果該系數值低于特定閾值，則判定未成功跟蹤對象。此時，使用探測器重新初始化MST 的目標位置和尺度。這個過程是基于模型匹配和學習過程。學習過程會不斷更新目標模型，以加強探測器的性能。另外，粒子濾波器還可以準確地估計目標的位置，在發生完全遮擋時，通過目標的先前行為來預測目標的位置，以此解決經典MST算法的缺點。

圖1 所提出跟蹤算法的流程圖

在發生完全遮擋的情況時，MST 和探測器都無法找到目標。如果跟蹤器和探測器的相似性快速降低，則確定已發生完全遮擋，并且啟動粒子濾波器預測目標的位置。在所提出的方法中，假設目標在x 和y 方向上以相同的速度移動。這種假設是合理的，因為完全遮擋通常會在短時間內發生，因此目標遵循幾乎恒定的速度模型。粒子濾波器可以根據目標的先前行為估計目標的位置和速度。在離開遮擋情況之后，再次由探測器找到目標并繼續跟蹤。

3 均值漂移跟蹤器

3.1 均值漂移算法

在經典的MST算法中，用戶在第一幀中選擇目標，并且使用歸一化的顏色直方圖來表示目標模型[14]。目標區域中的歸一化像素位置由確定，其中n 表示像素的數量。目標模型由下式計算得到：

其中：

式（5）中的第一項與位置y 無關，所以最大化相似性與最大化式（5）中的第二項相同。將式（5）對y 求導數，并使其等于零，得到迭代優化過程，稱為均值漂移迭代。在均值漂移迭代中，估計的目標從y0移動到新位置y1。經典MST的最終迭代公式定義為：

MST 算法適用于跟蹤通用對象。但是，當連續幀之間的目標位移相對較大時，它可能無法跟蹤對象。類似地，如果目標與其他對象重疊（遮擋），則算法可能會收斂到局部最小值。為解決這個缺點，需要重新初始化或重新啟動檢測過程。此外，經典MST 的一個局限是尺度適應性。因為它不考慮目標的尺度，所以無法準確估計目標的位置。

3.2 跟蹤器的模型更新

為了解決MST 的尺度問題，需要動態更新MST 跟蹤器的目標模型，為此本文采用一種探測器來實現模型的更新。如果跟蹤器無法跟蹤目標，此時探測器能夠以高可靠性找到目標，并更新目標模型。其以加權方式更新目標的顏色直方圖，表示如下：

4 具備在線學習的探測器

探測器有助于重新初始化MST 的目標尺度和位置。當采用半監督P-N 學習[17]的在線學習過程跟蹤物體時，探測器的性能得到有效改善。探測器基于滑動窗口方法[18]，由三個部分級聯組成：方差濾波器部分、集成分類部分和模型匹配部分。為了實時執行提出的算法，探測器在驗證區域中搜索目標，而不是執行窮舉搜索。

4.1 方差濾波器

探測器執行的第一步是使用方差濾波器在圖像中找到候選子窗口。通常，方差可以區分開結構良好的對象和均勻背景。在該階段，將灰度值方差小于特定閾值σVF的所有子窗口都丟棄。這個閾值定義為初始目標模型中方差的一半，因為方差會根據目標而改變。為了減少計算時間和內存使用量，通過積分圖像計算每個子窗口的方差。為了計算每個子窗口B 的方差，需要使用兩個積分圖像。其中一個是位置( x,y )處的積分圖像I′，包含了圖像中點（1，1）和( x,y )之間的所有像素值的總和，可以表述為：

另一個積分圖像I″表示圖像I 的平方值，表示如下：

使用這些積分圖像，子窗口B 的方差可以表示為：

其中n 是圖像中的像素數。

4.2 集成分類器

通過方差濾波器過濾掉背景以后，執行探測過程的第二步，即采用基于隨機化的集成分類器，通過比較幾個像素的強度值對像素進行分類。此階段的輸入是一組通過方差濾波器輸出的子窗口。對于每個候選子窗口，計算一個概率，用于表示子塊是否對應于正確標簽。如果概率值小于0.5，則子窗口被拒絕。

集成分類器由M 個子分類器組成，每個子分類器都執行像素的強度值比較。在算法開始時，從均勻分布中隨機提取像素的位置，并在跟蹤目標期間固定像素的位置。每個子分類器的輸出表示為：

其中，d1和d2是圖像I 中的隨機位置。最后，使用式（12）對每個子分類器的概率進行平均，當平均概率大于0.5時，集成分類器將子窗口分類為目標對象：

4.3 模型匹配

在通過分類器對目標像素進行分類后，執行探測器的最后一步，即使用模型匹配方法搜索目標。模型匹配過程會在探測圖像與目標模型之間進行逐像素的比較，當兩者相似性大于特定閾值時，判斷該探測圖像為探測器找到的目標模型。然后通過式（7）來更新MST 中的目標模型，獲得尺度更新過的新目標模型

為了減少計算時間，將輸入子窗口的大小調整為MtNt。在所提出的方法中，通過歸一化相關系數(NCC)來測量相似性。子窗口T1和T2之間的NCC 表示如下：

其中μ1和μ2,σ1和σ2分別是T1和T2的均值和標準差。使用NCC，兩個子窗口之間的距離計算如下：

在跟蹤期間，更新正類和負類的標準化模型。給定輸入子窗口Tin，正類和負類的距離表示為：

其中T+和T-分別是正類和負類的集合。那么，模型匹配概率的定義為：

該概率表示子窗口是否包括目標，如果概率大于特定閾值σTM，則確定相應的子窗口屬于目標。

4.4 在線學習

P-N學習方法是一種半監督學習方法，其使用兩種類型的約束從未標記數據中提取示例以增強訓練集。一個是P 約束，它可以識別假陰性示例，然后將它們放入一個正類訓練集中。另一個是N 約束，它可以識別假陽性示例，然后將它們添加到負類訓練集中。P-N學習的目標是通過在標記數據中的學習分類，并將未標記的數據進行分類以擴充標記數據集。

為了學習分類器，使用了檢測到的目標的反常子塊。P 約束的功能是找到目標的新外觀，以便于探測器的泛化。它基于跟蹤器結果附近的子窗口將具有正標簽的事實來搜索示例。也就是說，P 約束用于分類高度重疊的子塊。相比之下，N 約束的目的是在背景中發現雜亂像素點，以便于探測器的目標檢測。

5 基于粒子濾波的位置估計

由于傳統MST 只會鎖定領域內的局部最大值，當遇到大面積遮擋時，MST 鎖定的目標位置會與真實位置有偏差。這個偏差會隨著遮擋視頻幀的增加而持續擴大，以致最后丟失目標。為此，在發生嚴重遮擋時，本文啟動粒子濾波器，用來估計遮擋時的目標位置。在遮擋過后，根據所估計的位置，使MST 能夠快速搜索到目標。

粒子濾波器能夠為發生遮擋時的目標跟蹤提供很強的魯棒性，這是因為它既不受限于線性系統，也不要求噪聲服從高斯分布。粒子濾波中，將目標可能的位置是真實位置的概率作為粒子。前一幀中的所有粒子會以狀態傳遞函數的形式轉換到當前幀，雖然粒子位置和權重都發生變化，但它仍能提供最近似實際位置的目標位置。

為了估計系統的后驗狀態，定義一個目標模型，如下所示：

式中，fm-1為目標狀態的非線性函數；wm-1為白噪聲序列，代表狀態預測的不確定性。當前時間m(m ≥1)的在線離散預測zm由下式確定：

式中，hm為非線性函數，um為零均值的白噪聲序列，表示預測中的誤差。

粒子濾波的迭代過程分為兩個部分：（1）預測；（2）更新。

在預測階段，利用系統模型及m 時刻的初始概率密度，通過積分運算獲得m-1 時刻的概率密度，表達式如下：

其中，zm={ }zi:i=1,2,…,m 為給定的在線觀測序列。

在更新階段，在給定先驗概率密度p(x1|z0)≡p(x1)、狀態函數形式(f)、外觀模型(h)以及最終預測時刻的情況下，每一時間步長處估計后驗密度p(x0:m|z1:m)表達式如下：

對于目標跟蹤的應用，需要從初始給定的概率密度p(x1)中獲取N 個觀測樣本。為了獲得一致性的粒子觀測值，需要為這些粒子樣本分配一致性權重，表示如下：

由于假設目標狀態變化為馬爾可夫鏈，則后驗概率可以描述為：

式中，δ(?)表示狄拉克δ 函數。

本文提出的實時目標跟蹤方法的偽代碼如算法1所示。

算法1 提出的目標跟蹤算法

初始化：

1. 通過式（1）計算目標模型q?，并初始化位置y0；

2. 初始化參數；

3. 基于在第一幀中的目標選擇進行學習；

執行：

6. 確定是否目標跟蹤成功

則通過式（16）計算跟蹤器輸出的子塊和正類樣本集中子塊的相似性STM（模型匹配概率）；

如果(STM＞σTM)

則跟蹤器提供正類和負面圖像子塊，并執行學習。

否則

通過粒子濾波，基于跟蹤器中的目標位置來估計位置。

否則

通過粒子濾波預測目標的位置；

通過式（16）計算探測器探測的子塊與正類樣本集的相似性STM；

如果(STM＞σTM)

通過粒子濾波估計位置和尺度；

為跟蹤器更新目標模型；

否則

通過粒子濾波預測目標的位置；

7. 返回到第4步驟；

輸出：

估計的目標位置和尺度。

6 實驗及分析

6.1 實驗設定

實驗使用的測試視頻序列來自PETS 2009數據集，這些視頻中包含了遮擋、背景雜亂和外觀變化在內的各種環境。實驗在具有英特爾酷睿i7-3.40 GHz CPU，8 GB RAM PC機上的MATLAB上編程執行。

使用這些視頻序列進行性能評估，并與一些基于MST的改進方法進行比較，分別為經典MST跟蹤器、文獻[10]提出的結合自適應背景加權直方圖的BWH-MST方法、文獻[12]提出的卡爾曼濾波與SOAMST相結合的算法（K-SOAMST）。MST算法使用基于顏色直方圖的目標模型迭代估計對象的位置。BWH-MST 使用背景加權直方圖解決了背景復雜的問題。K-SOAMST算法改善了MST 在尺度估計和方向估計等方面存在的問題，并結合卡爾曼濾波提高對遮擋的應對能力。

對于基于均值漂移框架的跟蹤器，使用RGB 顏色空間，并且每個通道被均等地分成16 個區域以表示目標和候選，而且都應用Epanechnikov內核。對于本文提出的算法，Bhattacharyya 系數的閾值σVF（用于確定跟蹤是否成功）設置為0.65。粒子濾波器中的粒子數量設置為30。對于探測器，相似性的閾值σTM定義為0.6。用于更新目標模型的β 設置為0.9。這些值是通過多次實驗結果確定的。

6.2 性能指標

為了評估跟蹤算法性能，使用兩個性能指標。第一個是中心位置誤差（CLE），它可以測量估計物體的中心位置與實際數據之間的誤差，定義如下：

其中，xe和ye表示跟蹤結果的中心位置，xg和yg表示實況數據的中心位置。

第二個性能指標是成功率（SR），定義如下：

其中，Re是跟蹤結果的邊界框，Rg是實況數據的邊界框。如果SR 大于0.5，則判定跟蹤結果為成功。

6.3 性能評估

為客觀地評估所提出的算法與其他基于均值漂移的跟蹤算法（MST、BWH-MST 和K-SOAMST），選擇了四個具有挑戰性的視頻序列來構建測試數據集，分別為Ball序列，Car1序列，Car2序列，和Person1序列。其中，Ball 序列存在目標快速移動，Car1 序列包含了遮擋情況，Car2序列包含了尺度變化情況，Person1序列存在光照變化。

圖2 舉例顯示了在Car1 序列和Car2 序列上各種算法的跟蹤結果。圖2（a）顯示了在存在完全遮擋情況下的跟蹤情況。在完全遮擋之前，每個跟蹤器都可以估計目標位置。然而，在經過完全遮擋之后，只有本文算法可以跟蹤目標。K-SOAMST 也具有處理遮擋的能力，但是在該視頻序列中，汽車目標移動較快，非線性較強，導致卡爾曼濾波的性能下降。在本文方法中，粒子濾波可以很好地應對非線性和非高斯環境，為此能夠糾正跟蹤過程。在圖2（b）的序列中，目標發生了尺度變化。在這個視頻序列中，所有算法都可以跟蹤目標，其中本文算法和K-SOAMST 算法的尺度估計準確性較高，能夠自適應調整目標的尺度。這是因為本文算法中融入了用于尺度調整的探測器過程。

圖2 各種基于MST算法的跟蹤結果

各種算法在4個視頻序列上的平均CLE和SR性能指標如表1和表2所示。

表1 平均中心位置誤差（CLE）

表2 平均跟蹤成功率（SR） %

從表1 和表2 所示的結果可以看到，本文算法都獲得了最佳結果。對于Ball 序列，目標快速移動，使得它在連續幀之間的位移很大。雖然MST算法無法跟蹤目標，但本文算法在此序列上表現良好。這是因為粒子濾波器基于先前的目標運動軌跡，精確地估計目標位置，從而減少目標在連續幀之間的位移，這使得MST 算法能夠成功地跟蹤對象。此外，當MST 算法無法跟蹤對象時，探測器會找到目標位置并重新初始化MST 算法。在Car1 序列中，目標在15 幀中經歷完全遮擋。本文算法在目標重新出現后表現良好，這是因為粒子濾波器在目標完全遮擋時預測目標位置，并且當目標再次出現時，MST 算法可以使用所預測的目標位置成功跟蹤目標。在Car2 序列中，目標的尺度變小。本文方法在探測器的幫助下估計目標尺度。在Person1 序列中，當目標模型由于光照變化而改變時，MST和BWH-MST算法無法跟蹤目標。

另外，各種算法每幀目標跟蹤的平均計算時間如表3所示。其中，基于MST的跟蹤器最顯著的優勢在于可以在較短時間內跟蹤目標，為此各種方法的計算時間都不是很高，都在15 ms 以內。其中，傳統MST 算法計算時間最短為3.85 ms。盡管所提出的算法包含探測和學習過程，但本文在探測過程中調整了輸入子窗口的大小，使其計算速度并沒有增加太多，為11.55 ms。

表3 跟蹤算法的執行時間

上述實驗結果表明，本文算法不僅具有良好的跟蹤性能，且所需要的計算時間也較少，因此可以成功地應用于實時跟蹤應用。這是因為本文提出的算法結合了傳統MST 算法和粒子濾波算法，具備了MST 算法運算量少，跟蹤速度快，以及粒子濾波算法的魯棒性高和抗干擾、抗遮擋能力強的優點。

7 結語

本文提出了一種基于改進MST 的實時跟蹤算法，將MST 與粒子濾波器和基于在線學習的探測器相結合，這使得算法能夠在包含完全遮擋或對象重新出現的復雜環境中跟蹤目標，且可以使用探測器估計目標的尺度。與具有挑戰性的視頻序列上的比較表明，所提出的算法在準確性方面表現良好。

但是，本文算法仍有一些局限性。例如，在發生遮擋時，本文假設目標以相同的速度移動。為了解決這個缺點，在今后的工作中將考慮引入一個基于復雜運動模型的非線性濾波框架。