江二華，王匯源

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

1 引言

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

2 Harris-mean shift跟蹤算法

2.1 Mean shift跟蹤算法

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

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

2.2 Harris角點(diǎn)檢測(cè)算法

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

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

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

圖1 對(duì)目標(biāo)和背景的Harris角點(diǎn)檢測(cè)

2.3 融合角點(diǎn)的跟蹤算法

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

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

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

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

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

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

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

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

3.1 最小二乘法

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

對(duì)于一組實(shí)驗(yàn)數(shù)據(jù)(xi,yi)(i=0,1,…,m)，需要根據(jù)這組實(shí)驗(yàn)數(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就是一個(gè)最小二乘算法擬合曲線的一個(gè)圖示。

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

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

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

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

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

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

圖3 改進(jìn)算法的主要步驟

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

表1 本文算法和文獻(xiàn)[9]算法的誤差分析

表2 本文算法和文獻(xiàn)[9]算法的跟蹤速度比較

5 結(jié)語

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

[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]皇甫高峻，費(fèi)樹岷.跟蹤窗口尺度自動(dòng)更新的Mean-Shift跟蹤算法[J].工業(yè)控制計(jì)算機(jī)，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]袁國(guó)武，徐丹.一種結(jié)合了紋理和顏色的運(yùn)動(dòng)目標(biāo)跟蹤算法[J].計(jì)算機(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ù)測(cè)的運(yùn)動(dòng)目標(biāo)跟蹤[J].海軍航空工程學(xué)院學(xué)報(bào)，2013，28（4）：378-382.

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

[10]張小洪，李博，楊丹.一種新的Harris多尺度角點(diǎn)檢測(cè)[J].電子與信息學(xué)報(bào)，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角點(diǎn)檢測(cè)方法比較研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（6）：95-97.

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

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

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