一種改進的運動目標(biāo)跟蹤算法

江二華，王匯源

山東大學(xué) 信息科學(xué)與工程學(xué)院，濟南 250100

1 引言

運動目標(biāo)跟蹤是指在已知的視頻序列中檢測目標(biāo)的位置，形狀以及運動軌跡等時空變化特征。在目標(biāo)跟蹤領(lǐng)域中，mean shift算法[1-4]由于簡單易實現(xiàn)、運算速度快和魯棒性等優(yōu)點，受到廣泛關(guān)注。但由于其收斂于局部極值點，故在某些背景干擾及遮擋情況下往往出現(xiàn)定位偏差較大甚至跟蹤丟失現(xiàn)象。目前一般采用的解決辦法包括采用粒子濾波和mean shift相結(jié)合的算法[5]、結(jié)合紋理信息的mean shift算法[6]、融合了粒子濾波和卡爾曼濾波器的跟蹤算法[7]、surf和卡爾曼濾波器相結(jié)合的算法[8]等，這些算法能夠達到預(yù)期的跟蹤效果，但由于需要進行復(fù)雜的運算工程，使得計算效率得到影響，進而影響跟蹤速度。文獻[9]采用了基于角點的mean shift跟蹤算法，但跟蹤準(zhǔn)確度有待提高，所以本文在文獻[9]算法的基礎(chǔ)上，提出一種融合Harris-mean shift和最小二乘法的方法，文中利用Harris-mean shift算法進行前N幀的目標(biāo)搜索，根據(jù)運動目標(biāo)前N幀位置信息采用最小二乘法擬合出運動軌跡，得到運動目標(biāo)的預(yù)測位置，再用mean shift算法得到目標(biāo)的中心位置，從而有效解決遮擋問題。

2 Harris-mean shift跟蹤算法

2.1 Mean shift跟蹤算法

Mean shift跟蹤算法采用顏色直方圖對所選擇的目標(biāo)區(qū)域進行建模。通過計算特征空間中每個特征值的概率來建立目標(biāo)模型，目標(biāo)模型的特征值u=1,2,…,m的概率密度為：

通過相似性函數(shù)的最大化，得到關(guān)于目標(biāo)的mean shift向量，這個向量即是目標(biāo)從初始位置向正確位置轉(zhuǎn)移的向量，由于mean shift算法的收斂性，不斷迭代計算mean shift向量，在當(dāng)前幀中，最終會收斂到目標(biāo)的真實位置（一個靜止點），從而達到跟蹤的目的。

2.2 Harris角點檢測算法

Harris角點[10-12]對于旋轉(zhuǎn)、光照、灰度、平移和噪聲變化具有一定的不變性，而且僅用到灰度的一階差分，使各個方向的變化都包含進去，所以其實時性強，定位精度較高，Harris具有算法簡單、提取角點均勻合理、穩(wěn)定等優(yōu)點。受信號處理中自相關(guān)函數(shù)的啟發(fā)，Harris算子給出與自相關(guān)函數(shù)相聯(lián)系的矩陣N。自相關(guān)函數(shù)的一階曲率是N的特征值，對圖像中的任意一點，如果它的水平曲率值和垂直曲率都高于局部鄰域中其他點，則認(rèn)為該點是特征點。Harris算子的角點檢測公式為：

其中，Iy為圖像中每個像素點垂直方向上的梯度，Ix為圖像中每個像素點水平方向上的梯度。在計算梯度后對矩陣進行高斯濾波，然后對式（4）進行相似對角化處理，得：

式中，α為常數(shù)，一般取0.04～0.06，本文取α=0.06。當(dāng)R大于某一閾值且在某鄰域內(nèi)取得局部極值時，標(biāo)記該點為角點（本文中閾值為0.01Rmax）。圖1為Harris算子在圖像區(qū)域內(nèi)提取的角點。

圖1 對目標(biāo)和背景的Harris角點檢測

2.3 融合角點的跟蹤算法

Harris-mean Shift目標(biāo)跟蹤算法[9]，利用少量的角點作為關(guān)鍵點，建立目標(biāo)模型和候選目標(biāo)模型，增強目標(biāo)與背景的可分性，從而改進mean Shift算法在復(fù)雜環(huán)境下的跟蹤性能。

Harris-mean Shift目標(biāo)跟蹤算法步驟如下：

（1）初始化當(dāng)前時刻及目標(biāo)位置y0。

（2）利用Harris算法在初始的目標(biāo)區(qū)域中找出目標(biāo)的角點，并計算顏色直方圖，建立目標(biāo)模型?。

（3）在以y0為中心的候選區(qū)域內(nèi)利用Harris算法提取區(qū)域內(nèi)的角點，計算角點的顏色直方圖，建立候選模型?(y)。

（5）從y0開始進行mean shift向量迭代尋找最優(yōu)匹配目標(biāo)，直到找到目標(biāo)的真實位置y1，停止迭代。

Harris-mean Shift跟蹤算法主要是使用角點特征減少了迭代次數(shù)，一定程度上提高了跟蹤準(zhǔn)確性，但跟蹤實時性和準(zhǔn)確性還可以通過改進進一步提高。

3 改進的目標(biāo)跟蹤算法

3.1 最小二乘法

最小二乘法[13-15]是一種數(shù)學(xué)優(yōu)化技術(shù)，其目的是通過最大限度地減少偏差的平方和來尋找最佳匹配的功能，最小二乘曲線擬合方法被廣泛應(yīng)用于目標(biāo)跟蹤。

對于一組實驗數(shù)據(jù)(xi,yi)(i=0,1,…,m)，需要根據(jù)這組實驗數(shù)據(jù)找到自變量xi和相關(guān)變量yi之間的關(guān)系。y與x滿足以下關(guān)系式：

最小二乘算法的目的在于找到能使I(a0,a1,…,an)最小的最優(yōu)曲線s(x)=a0φ0(x)+a1φ1(x)+… +anφn(x)，則最終曲線就是y=s(x)，如圖2就是一個最小二乘算法擬合曲線的一個圖示。

圖2 最小二乘算法擬合曲線

在目標(biāo)跟蹤中，基于目標(biāo)運動軌跡的連續(xù)性，用最小二乘算法計算目標(biāo)的運動軌跡，然后預(yù)測目標(biāo)在下一時刻的位置。

3.2 融合最小二乘法的目標(biāo)跟蹤

本文算法首先用Harris-mean Shift跟蹤算法得到運動目標(biāo)的前N個目標(biāo)位置，然后以前N個目標(biāo)位置為已知信息，用最小二乘算法預(yù)測運動目標(biāo)的位置，然后以預(yù)測位置為搜索點，用Harris-mean Shift目標(biāo)跟蹤算法得到運動目標(biāo)的最終位置。假設(shè)x和y分別為時間t的三次方程：

用Harris-mean Shift目標(biāo)跟蹤算法得到的前N幀目標(biāo)中心位置作為樣本點，即(xi,ti)，(yi,ti)，i=k-1,k-2,…,k-N。由公式（12）和（13）得到最終曲線方程，令t=tk，獲得目標(biāo)在當(dāng)前幀的預(yù)測位置。把最小二乘算法的預(yù)測結(jié)果作為Harris-mean Shift目標(biāo)跟蹤算法的初始搜索中心，進而得到運動目標(biāo)的最終位置。由于減少了初始點和收斂點之間的距離，所以相對于文獻[9]跟蹤算法，計算速度得到提高。本文改進算法的主要步驟如圖3所示。

由文獻[9]可知Harris-mean Shift算法的跟蹤效果相對于傳統(tǒng)mean shift跟蹤算法已經(jīng)得到較好改善，本文算法的目的只是進一步提高跟蹤準(zhǔn)確度，所以在本文算法的前N幀，采用Harris-mean Shift算法實現(xiàn)目標(biāo)跟蹤（并且N的取值一般較小，本文取值為5），即使出現(xiàn)偏差，該偏差也不至于影響后續(xù)步驟的跟蹤效果。

圖3 改進算法的主要步驟

4 實驗結(jié)果及分析

本算法在Intel i3-3110、4 GB內(nèi)存的PC機上用Matlab7.0實現(xiàn)，實驗中N=5，即采用前5幀的運動目標(biāo)中心位置作為樣本點。

在實驗視頻TEST1中，路上走的行人，其上衣顏色和背景顏色很相近，在不存在外物遮擋時，量化空間為16×16×16的RGB顏色模型下，實驗結(jié)果如圖4所示，圖中TEST1的4幀依次是第2幀、18幀、39幀和74幀。

圖4 本文算法與其他算法在TEST1視頻上的比較

在圖4中，本文算法和文獻[9]的算法能夠?qū)崿F(xiàn)對目標(biāo)的跟蹤，但本文算法在目標(biāo)定位上更加準(zhǔn)確。兩種算法的誤差分析見表1，其中M位置和N位置分別表示文獻[9]算法和本文改進算得到的目標(biāo)位置，dm和dn分別表示M位置和N位置和實際位置之間的距離，由表的誤差分析可知，dn小于dm，這表明本文算法的定位誤差小于文獻[9]算法，即本文算法的跟蹤精度高于文獻[9]算法，本文算法更具有可靠性，表2是本文算法和文獻[9]跟蹤速度的比較，可知本文算法相對于文獻[9]算法跟蹤速度得到了提高。

表1 本文算法和文獻[9]算法的誤差分析

表2 本文算法和文獻[9]算法的跟蹤速度比較

5 結(jié)語

新算法結(jié)合最小二乘法對Harris-mean Shift算法進行改進，改進的算法采用最小二乘法擬合曲線預(yù)測目標(biāo)在下一幀的位置，改進了Harris-mean Shift算法在復(fù)雜環(huán)境下的跟蹤性能，文中給出了相應(yīng)的實驗對Harris-mean Shift算法和改進算法做出了對比，實驗表明本文算法對跟蹤過程中的定位偏差問題有較強的魯棒性。

[1]Du M T，Jie Y L.Mean-shift-based defect detection in multicrystalline dolar wafer surfaces[J].IEEE Trans on Industrial Informatics，2011，7（1）：125-135.

[2]Deilamani M J，Asli R N.Moving object tracking based on mean shift algorithe and feature fusiion[C]//Proc of the InternationalConference on ArtificialIntelligence and Signal Processing，2011：48-53.

[3]Yuan Guanglin，Xue Mogen，Han Yusheng，et al.Meanshift object tacking based on adaptive multi-features fusion[J].Journal of Computer Research and Development，2010，47（9）：1663-1671．

[4]皇甫高峻，費樹岷.跟蹤窗口尺度自動更新的Mean-Shift跟蹤算法[J].工業(yè)控制計算機，2009，22（11）：69-71.

[5]Jiang Min，Xu Qin，Shang Tao，et a1.Tracking algorithm based on particle filtering and mean-shift[J].Computer Engineering，2010，36（5）：21-22.

[6]袁國武，徐丹.一種結(jié)合了紋理和顏色的運動目標(biāo)跟蹤算法[J].計算機應(yīng)用與軟件，2011，28（11）：81-84.

[7]Du Cbao，Liu Weining，Liu Lian.Target tracking algorithm based on kalman filter and particle filter[J].Chinese Journal of Crystals and Displays，2011，26（3）：384-389.

[8]宿德志，王坤，王玉良，等.基于SURF算法和Kalman預(yù)測的運動目標(biāo)跟蹤[J].海軍航空工程學(xué)院學(xué)報，2013，28（4）：378-382.

[9]寧紀(jì)鋒，姜光，李鵬飛.一種基于角點的Mean Shift目標(biāo)跟蹤算法[J].計算機應(yīng)用研究，2009，26（11）：4348-4350.

[10]張小洪，李博，楊丹.一種新的Harris多尺度角點檢測[J].電子與信息學(xué)報，2007，29（7）：1735-1738.

[11]Loog M，Lauze F.The Inprobability of Harrris interest points[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2010，32（6）：1141-1147.

[12]盧瑜，郝興文，王永俊.Moravec和Harris角點檢測方法比較研究[J].計算機技術(shù)與發(fā)展，2011，21（6）：95-97.

[13]王可，毛志.基于Matlab實現(xiàn)最小二乘法曲線擬合[J].自然科學(xué)報，2005，12（2）：52-56.

[14]張起貴，張魁.基于最小二乘直線擬合的小目標(biāo)檢測[J].電子設(shè)計工程，2010，18（7）：176-180.

[15]徐瑜，楊紹清，孫牧.最小二乘濾波在目標(biāo)跟蹤中的應(yīng)用[J].指揮控制與仿真，2007，29（4）：41-42.