一種改進的meanshift運動目標跟蹤算法

趙 欣，陳 峰，吳立知

（貴州大學 計算機科學與信息學院，貴州 貴陽 550025）

0 引言

運動目標跟蹤是指在已知的視頻序列中檢測目標的位置，形狀以及運動軌跡等時空變化特征。在眾多的目標跟蹤算法中，meanshift算法由于其簡單和魯棒性，近幾年受到了廣泛的關注，Cheng[1]在1995年首次將其引入圖像處理領域。Comaniciu等人[2]提出的meanshift跟蹤框架,計算復雜度低,對目標的外表變化、噪聲、遮擋、尺度變化等具有一定的自適應能力,成為目標跟蹤算法研究的熱點。但是在meanshift算法的應用過程中，通常是建立目標模型和候選模型的顏色直方圖，然后通過比較兩模型的相似度來實現目標跟蹤，很顯然，當目標顏色和背景顏色相似度較高時跟蹤算法的性能就會下降。同時meanshift算法本身缺少對目標位置的預測機制，所以在目標遭受較大比例遮擋時meanshift方法就會失效。

為了解決上述問題，文中利用harris角點檢測提取表示目標特征的角點，抑制背景特征對目標的干擾，然后利用卡爾曼濾波器一方面預測目標在下一幀中的位置；另一方面，通過分析卡爾曼濾波器關于目標位置的估計值和由meanshift算法得到的卡爾曼濾波器的觀測值之間殘差的大小來判斷是否出現了大比例的遮擋，從而有效地解決遮擋問題。

1 meanshift算法及其缺陷

meanshift跟蹤方法采用顏色直方圖對所選擇的目標區域進行建模。通過計算特征空間中每個特征值的概率來建立目標模型，目標模型的特征值u=1,2,…,m的概率密度由式（1）給出：，?是目標模型，是第u個特征的概

率，k(x)是核函數的輪廓函數，C為標準化的常量系數。同樣，在后續幀中計算目標候選模型的概率密度，由式(2)給出：

相似性函數()yρ⌒被用來度量目標模型和當前幀候選模型的相似性，它的值在0～1之間，其值越大，表示2個模型越相似。

通過求相似性函數最大得到關于目標的 menashitf向量，這個向量即是目標從初始位置向正確位置轉移的向量，由于maenshitf算法的收斂性，不斷迭代計算menashitf向量，在當前幀中，最終會收斂到目標的真實位置(一個靜止點)，從而達到跟蹤的目的。

從分析可以看出mean shift的跟蹤主要是根據目標顏色直方圖描述目標的特征，當背景和目標顏色分布比較接近時，往往會導致目標丟失。并且 menashitf向量在迭代的過程中沒有目標運動軌跡的預測機制，致使迭代次數較多，跟蹤時實行比較差。當目標被遮擋時沒有判斷是否被遮擋的條件，也會導致跟蹤失敗。一個典型的例子如圖2(a)所示。

2 改進的meanshift跟蹤算法

2.1 Harris角點檢測算法

Harris算法[3]是一種基于灰度圖像的點特征提取算法。在一幅圖像中，角點與自相關函數的曲率特性有關。自相關函數描述了局部圖像灰度的變化程度，可以表示為：

其中，E(x,y)是由于2個窗口偏移(x,y)而造成的圖像灰度的平均變化，Wu,v是圖像加權窗口，一般情況下窗口中心權值較大，窗口邊界處及其鄰域內權值較小。在角點處，圖像窗口的偏移造成 E(x,y)的顯著變化，對它在任意像素點進行泰勒展開，E(x,y)可近似表示成：

其中 T r(M)=A+B ,Det(M)=AB-C2，C是常量，一般取0.04既可以獲得比較好的效果，R (x,y)大于一個給定的閾值時,即認為相應局部區域窗口的中心點是一個角點。對圖2(a)進行Harris角點檢測的檢測結果如圖1所示。

圖1 對目標和背景的harris角點檢測

2.2 卡爾曼濾波器在目標跟蹤中的應用

卡爾曼濾波器的主要作用是對運動目標在下一幀中的位置進行預測并且根據既得信息對目標位置進行修正。在預測部分利用當前的狀態和誤差協方差估計下一時刻的狀態，得到先驗估計，預測方程如下所示：

狀態預測方程：

誤差協方差預測方程：

在修正部分將實際觀測值與先驗估計值放在一起考慮，從而獲得后驗估計。這里H設為常量，sk為觀測值。

狀態修正方程：

誤差協方差修正方程：

2.3 融合了角點和卡爾曼濾波的算法

新算法利用 Harris檢測到的角點信息建立運動目標的目標模型[4-5]，meanshift向量迭代的過程中，只把這些角點作為跟蹤的關鍵點，目標模型和背景之間就會有明顯的可分性，一方面能夠降低 meanshift的迭代次數，另一方面增強了原算法對目標定位的準確性。與此同時，在 meanshift向量迭代之前，利用卡爾曼濾波首先預測目標在下一幀中的位置[6-7]，不但可以減小目標的搜索范圍，同時可以有效地解決遮擋問題。

算法的具體過程可以表述為：

①利用 Harris算法在定義的目標區域中找出目標的角點，并計算顏色直方圖，建立目標模型?q。

②根據目標以往的位置信息，通過式(7)預測當前幀中目標可能出現的位置。

③在目標預測位置包括其鄰域內初始化跟蹤目標的位置y0。

④在以y0為中心的候選區域內利用Harris算法提取區域內的角點，計算角點的顏色直方圖，建立候選模型(y)。⌒

⑥從 y0開始進行 meanshift向量迭代尋找最優匹配目標，直到找到目標的真實位置y1，停止迭代。

⑦把 y1帶入式(8)的修正方程中，并且把此時的修正值作為下一幀中目標位置預測的初始信息。

⑧重復以上步驟直到當前幀為最后⌒一幀。⌒在以上的步驟中，當前幀的估計值的位置分量(k )、(k)與觀測值 的2個分量x(k)、y(k)做差，得到殘差分量r(k)[8-9]：

設定門限值a，當()rka＞時，目標可能遇到大的遮擋，這時卡爾曼濾波器停止工作，直到()rka＜時卡爾曼濾波器再開始預測。

3 實驗結果及分析

現通過 2個視頻對傳統算法和改進算法性能進行分析對比。首先，草坪上行走的行人，其衣服顏色和草坪的顏色很相近，在不存在外物遮擋時，RGB顏色模型下，量化空間為 16×16×16的視頻序列中，基于 matlab2008a對傳統的meanshift算法和加入角點的算法分別進行實驗，實驗結果如圖2和圖3所示。

從實驗結果可以看出，沒有遮擋物存在的條件下，加入了角點以后的跟蹤方法跟蹤效果明顯優于傳統的跟蹤方法，這說明改進算法在目標和背景顏色相近時能很好的定位目標。

第2個實驗是在室內進行的，目標顏色和背景色相近，并且有遮擋物存在，實驗環境同第1個實驗一樣在matlab2008a環境下進行仿真，實驗結果如圖4和圖5所示。

圖2 原始算法的跟蹤結果

圖3 加入角點后的算法跟蹤結果

圖5 加入了角點和卡爾曼濾波后的跟蹤算法

實驗時取出視頻序列的第2、第14、第39、第51幀進行對比，在改進的算法中，由于算法對角點的閾值選擇并不敏感，所以此處取R=10就可以的到比較好的效果。

從對比結果可以看出，在圖4中當目標沒有被遮擋且背景色和目標色相差較遠時，傳統的meanshift算法具有良好的跟蹤效果，但是在從14幀開始，目標被大面積遮擋，并且遮擋物的顏色與目標顏色接近時，跟蹤效果明顯變差，直到第51幀時目標定位完全出錯。改進算法用目標角點作為跟蹤的關鍵點，抑制了背景色的干擾，同時用卡爾曼濾波預測目標位置，解決了目標被大面積遮擋時定位不準的問題，從演示結果圖5可以看出，改進算法取得了比較好的跟蹤效果。

另一方面，改進算法用少量關鍵點的直方圖信息作為目標模板，并且利用卡爾曼濾波提前預測目標在下一幀中的大致范圍，與傳統的 meanshift算法相比，不但減少了搜索時間，同時也縮小了搜索范圍。圖6顯示的結果表明，改進算法跟蹤速度明顯優于傳統算法。

圖6 處理每一幀圖片所需要的時間

4 結語

新算法結合 Harris角點檢測和卡爾曼濾波對傳統的meanshift算法進行改進，改進的算法用少數的關鍵點來代替候選區域中的所有點，增強了目標和背景的可分性[10]，同時利用卡爾曼濾波器原理預測目標在下一幀中的位置，縮小了目標的搜索范圍，減少了meanshift向量的迭代次數，改進了meanshift算法在復雜環境下的跟蹤性能。文中給出了相應的實驗對原始算法和改進算法進行了對比，實驗結果證明，改進算法比傳統的算法具有更好的目標定位性和實時性。

[1] CHENG Y.Mean Shift, Mode Seeking, and Clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 1995,17(08):790-799.

[2] COMANICIUD,RAMESHV,MEERP.Kernel-based Object Trac-king[J].IEEE Trans on Pattern Analalysis and Machine Intelli-gence,2003,25(05): 564-577.

[3] 張小洪,李博,楊丹.一種新的Harris多尺度角點檢測[J].電子與信息學報, 2007,29(07): 1735-1738.

[4] 寧紀鋒,姜光,李鵬飛. 一種基于角點的 Mean Shift目標跟蹤算法[J].計算機應用研究, 2009,26(11): 4348-4350.

[5] 徐偉,王朔中.基于視頻圖像 Harris角點檢測的車輛測速[J].中國圖象圖形學報, 2006,11(11): 1650-1652.

[6] 梁春迎,王國營. 基于運動統計和關鍵幀的視頻檢索方法[J].通信技術，2009,42(04)：162-164.

[7] 朱勝利，朱善安，李旭超.快速運動目標的meanshift算法[J].光電工程, 2006,33(05): 65-70.

[8] LI P H,ZHANG T W,MA B.Unscented Kalman Filter for Visual Curve Tracking[J]. Image and Vision Computing,2004,22(02):157-164

[9] YILMAZA.Object Tracking by Asymmetric Kernel Mean Shift with Automatic Scale and Orientation Selection[C].USA: IEEE, 2007:1-6.

[10] 蔣欣欣,錢盛友. 基于FCM的彩色車牌圖像快速分割方法[J].通信技術，2011,44(03):66-67,79.