基于均值漂移和粒子濾波相結合的水下運動目標跟蹤

雷 飛，張新穎，王 依

LEI Fei1,ZHANG Xin-ying1,WANG Yi2

（1. 北京工業大學 電子信息與控制工程學院，北京 100124；2. 東北石油大學 研究生院，大慶 163318）

0 引言

水下智能監控系統對保證游泳者生命安全起著至關重要的作用，而實時的運動目標跟蹤是其中關鍵的步驟。由于水下環境與其他自然場景不同，它受到光照、水波、倒影等的影響，是一個動態場景，且游泳者是非剛性目標，因姿態的變化目標會發生形變，這些都給水下的運動目標跟蹤帶來很大困難。因此水下視頻監控中的目標跟蹤算法既要適應目標和背景的復雜變化，又要保證快速、穩定的實時跟蹤目標。

近年來，研究人員提出了很多目標跟蹤算法，如基于特征的跟蹤，基于區域的跟蹤和基于變形模型的跟蹤等。其中均值漂移（Mean Shift）算法[1]是一種基于密度梯度上升的非參數方法。其計算量小，適合于實時跟蹤場合。粒子濾波（Particle Filter）為解決非高斯、非線性系統的目標跟蹤提供了有效的手段。它通過在狀態空間中傳播的隨機樣本的概率密度去逼近目標狀態的后驗概率密度，從而達到最優貝葉斯估計。該方法不受動態系統各 個隨機量分布形式的限制，有效地克服了卡爾曼濾波的缺點，能夠應用于非線性、非高斯的運動系統中。例如Isard[2]等人利用粒子濾波算法跟蹤連續圖像序列中的目標輪廓；Dallert[3]等將粒子濾波和移動機器人運動和感知的概率模型相結合，提出了移動機器人蒙特卡羅定位的思想；Okuma[4]等通過將自提升檢測與粒子濾波方法相結合實現了多目標的自動初始化及跟蹤。

但是以上算法都是針對背景相對簡單的室內監控，或者運動目標的形狀具有一定規律性的情況，暫未見有關水下復雜背景下的運動目標跟蹤算法。

本文結合Mean Shift算法中的核函數原理和目標模型，以RGB顏色直方圖為核心建立水下運動目標模型，采用粒子濾波算法實現水下運動目標跟蹤，并在跟蹤過程中利用Mean Shift收斂粒子。該方法融合了Mean Shift良好的實時性和粒子濾波的魯棒性。仿真試驗結果表明，該算法能夠克服氣泡、倒影、遮擋的影響，實現穩定、快速的目標跟蹤。

1 Mean Shift算法

Mean Shift是一種基于核密度估計的處理方法。給定一組n個一維空間的數據點的集合S＝，它的未知的概率密度函數為f (x)，取核函數Kh(x)，則在x點處的密度可按下式計算：

核密度函數估計的含義可以解釋為：將在每個采樣點為中心的局部函數的平均效果作為該采樣點概率密度的估計值。

由于水下目標是非剛性物體，其會隨著游泳姿勢的改變而發生形變，而利用顏色特征具有尺度、旋轉和平移不變性，因此采用顏色直方圖作為目標的特征具有很好的穩定性。本文結合Mean Shift算法中提到的核函數的概念，利用RGB顏色直方圖建立水下運動目標模型。核函數選擇Epanechikov Kernel，即：

設目標區域的中心為x0，區域內的像素點用{xi; i=1,2,,N}表示。將RGB每個顏色通道劃分為n個區間，則顏色的特征值u＝1,2,,M，M＝n3。按照下面公式建立模型：

其中，d是Delta函數，C是常量系數使得

計算得到

同理，以每個粒子為中心的候選目標模型為：

本文提出的跟蹤算法需要計算初始幀中目標的顏色直方圖作為模板，粒子區域的顏色分布與目標顏色分布越相似，權值越大，反之越小。本文使用Bhattacharyya系數作為度量直方圖之間相似性的函數：

Bhattacharyya距離為：

要使式（9）取得最大值，需要計算Mean Shift向量，通過迭代使其第二項取得最大值[5]。由于Mean Shift的收斂性，在不斷的迭代中，候選目標的中心y0會移動到新位置yi：

2 粒子濾波算法

2.1 粒子濾波原理

粒子濾波作為一種求解貝葉斯概率的實用方法又稱為蒙特卡羅方法（Sequential Monte Carlo methods），它利用狀態空間中的一系列隨機樣本（粒子）的加權和表示當前時刻的后驗概率密度。當粒子數目不斷增大時，所得的離散概率表示逐漸接近其真實值，理想情況下可以看作是最優估計。

假設系統的狀態變化模型和觀測模型如下：

其中，xk表示系統狀態變量，vk表示系統噪聲，zk表示系統觀測值，nk表示觀測噪聲。狀態概率密度分布可用如下經驗概率分布近似表述：

在實際中除了少數滿足高斯、均勻分布的系統外，對于大部分非標準分布的函數進行采樣是不可能的，通常要借助一些采樣算法。實際中多采用實現遞推估計的序貫重要性采樣(SIS)算法。在SIS算法中，重要性函數是概率分布與p (xk|z1：k)相同，概率密度分布q (x0：k|z1：k)已知并且容易從中采樣的分布函數。

若將重要性函數q (x0：k|z1：k)展開成如下連積形式：

并假設系統滿足馬爾科夫過程，通過推導得到權值的遞推更新公式：

更新概率密度函數為

其中

對權值歸一化后：

2.2 重要性函數選取

對于SIS粒子濾波器而言，其最大的缺陷就是粒子退化現象[6]，即隨迭代的深入，大部分粒子的權值變得很小，只有少數粒子具有較大權值，其多樣性逐漸減低。解決這個問題的方法之一是選擇合適的重要性分布。

選取重要性函數的準則是使重要性權值的方差最小。Lliu[7]在其文獻中證明了采用q (xk|x0：k-1,z1：k)＝ p (xk|x0：k-1,z1：k)作為重要性函數可以獲得最優估計的效果，但卻需要存儲之前所有時刻的狀態信息，在實際中，為了計算簡單，本文選取q(xk|x0：k-1,z1：k)＝ p (xk|xk-1)作為重要性函數。

2.3 重采樣過程

重采樣是解決粒子退化問題的另一個有效的方法。本文采用隨機采樣的方法，其過程是：

1）產生n個在[0，1]上均勻分布的隨機數[ml;l=1,2,,n]。

2）通過搜索算法找到滿足以下條件的整數m，使得

4）將區間[0，1]按式（21）分成n個小區間，當隨機數ml落在第m個區間Im=(lm-1,l)上時，對應的樣本將進行復制。

3 水下運動目標跟蹤算法步驟

本文以RGB顏色直方圖為核心建立水下運動目標模型，并在粒子濾波跟蹤水下目標的過程中，通過Mean Shift算法對粒子進行收斂，使粒子的分布更加接近目標真實的位置。具體算法步驟如下：

1） 初始化階段：

首先在水下視頻圖像的第一幀中手動選取目標，建立以RGB顏色直方圖為核心的參考目標模型，生成粒子集，并令其權重為N-1。

2） 根據狀態轉換方程，用k-1時刻的粒子集去預測k時刻每個粒子的狀態，得到新的粒子位置

3） 根據式（11），通過 Mean Shift算法對粒子在傳播半徑的鄰域內進行迭代，使其收斂到鄰域內的最大值，得到新的粒子狀態。

4） 更新粒子：

由每個粒子的候選區域與參考目標模型之間的巴氏距離，得到觀測值的概率密度函數：

其中s表示均方差。Bhattacharyya 距離越小，相似性越大，粒子所分配的權值也越大。因此，k時刻粒子的權值就可以更新為：

6） 重采樣：

7） 令 k=k+1，重復（2）～（6）。

算法流程如圖1所示。

4 試驗結果與分析

仿真試驗中用于跟蹤的視頻序列共350幀圖像，圖片尺寸為352×288，色彩深度為 24位。

在本文提出的水下運動目標跟蹤算法中，觀測值的概率密度函數為

圖1 水下運動目標跟蹤流程

取s=0.2，重要性函數采用均值為0，方差為1的標準正態函數。在以目標中心為中心，長度為30、寬度為20的矩形區域內進行跟蹤。

卡爾曼濾波是目前比較流行的目標跟蹤算法之一，其計算量小，預測具有無偏、穩定和最優的特點，但其無法適用于非線性系統中。為了驗證本算法的有效性，實驗中將本文采用的算法與目前常用的卡爾曼濾波算法[8]進行了比較。

圖2是原始視頻圖像，反應了水下視頻圖像中的運動目標受到氣泡、倒影、浮標對人的遮擋等影響。

圖2 原始視頻圖像

圖3是利用Kalman濾波器進行目標跟蹤的結果。由于跟蹤過程中受到水波、倒影和浮標遮擋的影響，且目標做非線性運動，導致卡爾曼濾波器無法有效的跟蹤到目標。從圖中可以看出跟蹤結果失真嚴重，到279幀時，完全丟失目標，跟蹤失敗。

圖4是采用本文提出的算法進行水下目標跟蹤的結果。在跟蹤初期，第17 幀的跟蹤結果與圖3中的17幀相比，沒有表現出明顯優勢；但隨時間的推移，目標受到水波、浮標遮擋、氣泡等的干擾，分別如圖4中第46幀、第124幀、第185幀和第225幀所示，本文采用的算法依舊能準確地跟蹤目標。在第279幀，目標受到自身倒影的影響，采用卡爾曼的跟蹤方法已經失效，而本文的算法則表現出了良好的跟蹤效果。

圖3 利用Kalman濾波器進行目標跟蹤的結果

5 結論

本文將Mean Shift和粒子濾波相結合實現了水下運動目標跟蹤算法。粒子濾波器的主要缺點是需要大量的粒子來近似描述目標的狀態，因而較費時。而本文中利用Mean Shift算法在重采樣之前將粒子收斂到靠近目標真實狀態的區域內，由于每個粒子表示的狀態更加合理，因而算法對粒子數量的需求大大降低，算法的實時性得到了提高。由仿真試驗結果可以看出，本文提出的水下運動目標跟蹤算法在背景混亂和發生目標遮擋的情況下實現了快速、穩定的實時目標跟蹤。進一步地，該算法有效地克服了卡爾曼濾波器的缺點，可以適用于非線性、非高斯的運動系統中。

[1] Cheng Y. Mean shift,mode seeking and clustering [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8)： 790-799.

[2] Isard M,Blake A. Condensation-conditional Density Propagation for Visual Tracking [J]. Int J of Computer Vision,1998,29(1)： 5-28.

[3] F Dellaert,W Burgard，D Fox. “Monte Carlo localisation for mobile robots” in Proceedings of the IEEE International Conference on Robotics and Automation,vol.2 Detroit,MI,May 1999,1322-1328.

[4] Okuma. K.,Taleghani,A.,de Freitas,J.,et al. A Boosted Particle Filter： Multi-target Detection and Tracking. In：European Conference on Computer Vision,2004,1(5)： 28-39.

[5] D. Comaniciu,V. Ramesh,and P. Meer. Kernel-based object tracking[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence,2003,(25)5： 564-577.

[6] 康健,芮國勝. 粒子濾波算法的關鍵技術應用[J]. 火力與指揮控制,2007(4)： 53-55.

[7] Liu J S,Chen R. Sequential Monte Carlo methods for dynamical systems [J]. J of the American Statistical Association,1998,93(5)： 1032-1044.

[8] Lei fei,Zhao Xiaoxia. Adaptive Background Estimation of Underwater Using Kalman-Filtering[C]. The 3rd International Congress on Image and Signal Processing.16-18 Oct. 2010： 64-67.