江二華,王匯源
山東大學(xué) 信息科學(xué)與工程學(xué)院,濟(jì)南 250100
運(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)的中心位置,從而有效解決遮擋問題。
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á)到跟蹤的目的。
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è)
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)一步提高。
最小二乘法[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í)刻的位置。
本文算法首先用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)算法的主要步驟
本算法在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]算法的跟蹤速度比較
新算法結(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.