, ,,,
(浙江理工大學(xué) 信息學(xué)院,杭州 310018)
在計(jì)算機(jī)視覺領(lǐng)域中,目標(biāo)跟蹤是研究的重點(diǎn)之一,應(yīng)用非常廣泛,在智能視頻監(jiān)控、人機(jī)交互、計(jì)算機(jī)視覺導(dǎo)航、虛擬現(xiàn)實(shí)和醫(yī)學(xué)診斷等領(lǐng)域中都有涉及。目標(biāo)跟蹤是對連續(xù)視頻圖像進(jìn)行特征提取,分析獲得目標(biāo)的位置、大小、選擇角度和速度等信息,并且持續(xù)地顯示目標(biāo)在每幀圖像中的位置[1]。目前已有大量目標(biāo)跟蹤算法,這些算法可以分為以下5大類:a) 基于梯度場決策模型的跟蹤算法,主流算法有基于Mean-shift跟蹤算法[2]和基于均值漂移的目標(biāo)跟蹤算法[3]等;b) 基于概率決策的模型跟蹤算法,主流算法有卡爾曼濾波跟蹤算法[4]和基于粒子濾波的跟蹤算法[5]等;c) 基于分類器決策模型的跟蹤算法,主流算法有基于支持向量機(jī)跟蹤算法[6]和TLD (Tracking learning detection)算法[7]等;d) 基于子空間表示模型跟蹤算法,主流算法有增量視覺跟蹤IVT(Incremental learning for robust visual tracking)算法[8]和基于增量PCA (Principal component analysis)跟蹤算法[9]等;e) 基于稀疏表示模型的跟蹤算法,主要算法有l(wèi)1范數(shù)最小化視頻跟蹤算法[10]和局部稀疏表示跟蹤算法(Local sparse representation tracking algorithm,LSRTA)[11]等。
基于稀疏表示模型的跟蹤算法首先是由Mei等[10]提出的l1范數(shù)最小化的目標(biāo)跟蹤算法,該算法首次將稀疏表示的理論知識(shí)應(yīng)用到目標(biāo)跟蹤領(lǐng)域,跟蹤過程中需要人為設(shè)置初始模板以及正負(fù)最小模板,通過最小模板構(gòu)造稀疏字典并進(jìn)行粒子濾波產(chǎn)生粒子,最后用稀疏字典[12]對粒子進(jìn)行l(wèi)1范數(shù)最小化處理,選擇構(gòu)造誤差最小的粒子得到目標(biāo)的位置,該算法運(yùn)行速度較快,能初步實(shí)現(xiàn)目標(biāo)的跟蹤。之后,許多學(xué)者開始加入到稀疏表示跟蹤算法的研究中,提出了一系列算法,如:詹曙等[13]提出了Gabor特征稀疏表示目標(biāo)跟蹤算法,該算法在稀疏表示模板字典的更新過程中加入主元分析理論,在目標(biāo)發(fā)生形變時(shí),該算法有較好的跟蹤效果。胡昭華等[14]提出了特征聯(lián)合的稀疏表示跟蹤算法,該算法用字典模板對候選粒子進(jìn)行聯(lián)合稀疏表示,改善了跟蹤效果。Wang等[11]提出了LSRTA算法,將模板進(jìn)行了分塊并獨(dú)立構(gòu)造稀疏字典,再獲得每個(gè)小塊在幀圖像中的投票圖,最后合并為全局投票圖,從而估計(jì)目標(biāo)的位置。LSRTA算法能夠在目標(biāo)發(fā)生形變或者部分遮擋時(shí)具有較好的跟蹤效果,但是當(dāng)目標(biāo)被遮擋面積過大、運(yùn)動(dòng)過快或形變量過大等情況存在時(shí),跟蹤過程中仍然會(huì)發(fā)生目標(biāo)偏移現(xiàn)象。針對LSRTA算法的這個(gè)不足,本文提出了一種具有自動(dòng)修正目標(biāo)功能的稀疏表示跟蹤算法。該算法在LSRTA算法的基礎(chǔ)上,融入了模板匹配算法,通過不斷計(jì)算新模板與當(dāng)前模板的匹配值來判斷跟蹤是否發(fā)生偏移。當(dāng)目標(biāo)發(fā)生偏移時(shí),通過模板與幀圖像之間匹配來重新確定目標(biāo)位置以修正偏移,改善跟蹤效果。
本文中,模板匹配算法采用surf、flann和knn相結(jié)合的算法。surf算法找到兩幅圖像中感興趣點(diǎn)的位置;flann算法對這些感興趣點(diǎn)進(jìn)行匹配,找出匹配成功的點(diǎn)對;knn算法對匹配成功的點(diǎn)進(jìn)行篩選,去除零散的點(diǎn)對。該算法可以有效找出兩幅圖像之間相似點(diǎn)的集合。
surf算法通過計(jì)算一幅圖像上所有像素點(diǎn)的Hessian矩陣的行列式與特征值,來判斷整幅圖像上哪些是感興趣點(diǎn)[15]。Hessian矩陣可用式(1)表示為:
(1)
圖1(a)是高斯濾波器濾波后的圖像,其在x、y和xy方向上的離散二階導(dǎo)數(shù)用Lxx、Lyy和Lxy表示。圖1(b)是盒濾波器濾波后的圖像,其在x、y和xy方向上的離散二階導(dǎo)數(shù)用Dxx、Dyy和Dxy表示。圖1中用簡單權(quán)值表示黑色為1,白色為-1。在計(jì)算Hessian矩陣的過程中,可以使用盒濾波器近似計(jì)算,得出了Hessian矩陣行列式公式:
det(Happrox)=DxxDyy-(0.9Dxy)2
(2)
計(jì)算圖像中所有點(diǎn)的行列式與特征值,如果行列式的值為負(fù),并且特征值異號(hào),則該點(diǎn)不是感興趣點(diǎn),如果行列式為正,并且特征值同號(hào),則該點(diǎn)是感興趣點(diǎn)。
圖1 高斯濾波器與盒濾波器濾波后的圖像
flann算法[16]是對兩幅圖像中的感興趣點(diǎn)進(jìn)行匹配,找出匹配成功的點(diǎn)對。圖2為flann算法示意圖。圖2左邊是包含感興趣點(diǎn)的圖像,圖像根據(jù)一定的分割規(guī)則分成多塊,每一塊包含一個(gè)感興趣點(diǎn)。圖2右邊是將包含感興趣點(diǎn)的圖像以樹型結(jié)構(gòu)表示。先將兩幅圖像分別按以上方式分塊樹狀結(jié)構(gòu)表示,再從第一幅圖像頂部根節(jié)點(diǎn)塊開始,在第二副圖像中搜索與第一幅圖像頂部塊最相似圖像塊,通過計(jì)算兩幅圖像塊的歐氏距離來判斷兩個(gè)圖像塊是否相似,如果歐氏距離大于設(shè)定的閾值,則兩幅圖像塊中感興趣點(diǎn)匹配成功。否則進(jìn)行下一個(gè)點(diǎn)的匹配,直至搜索到最底部;如果還沒有找到匹配點(diǎn),則第一幅圖像中的感興趣點(diǎn)沒有匹配成功的點(diǎn)。再從第一幅圖像中按自頂向下的原則尋找第二個(gè)塊的匹配塊,如此循環(huán)遍歷第一幅圖像中所有圖像塊,得到兩幅圖像中匹配的感興趣點(diǎn)對集合。
圖2 flann算法示意圖
knn算法[17]對感興趣點(diǎn)進(jìn)行篩選,去除零散的感興趣點(diǎn)對。先設(shè)定一個(gè)距離閾值,低于這個(gè)閾值的歸為一類,否則歸結(jié)到另一類;如此對圖像中感興趣點(diǎn)對進(jìn)行分類;當(dāng)某一類的數(shù)目小于數(shù)目閥值時(shí),則該類可以被刪除。圖3(a)是經(jīng)過surf和flann算法的匹配圖,圖3(b)是經(jīng)過surf、flann和knn算法的匹配圖。
圖3 模板與幀圖像匹配示例圖像
本文在LSRTA算法的基礎(chǔ)之上,融入模板匹配算法,提出了一種基于局部稀疏表示模板匹配跟蹤算法(Local sparse representation template matching tracking algorithm,LSRTMTA),以實(shí)現(xiàn)在發(fā)生目標(biāo)跟蹤偏移時(shí),自動(dòng)修正重新定位功能。
圖4為LSRTMTA跟蹤算法整體流程圖,先選定初始目標(biāo)從而獲得初始模板,再利用LSRTA跟蹤算法對初始的目標(biāo)進(jìn)行跟蹤。當(dāng)?shù)玫叫履0鍟r(shí),計(jì)算新模板與當(dāng)前模板的匹配值。如果匹配值大于閾值,說明新模板沒有發(fā)生太大變化,目標(biāo)并沒有發(fā)生偏移現(xiàn)象,則將新模板保存到模板集中。如果匹配值小于閾值,說明模板發(fā)生了大的變化,目標(biāo)發(fā)生了偏移現(xiàn)象,則舍棄該模板,并且停止LSRTA算法,通過當(dāng)前模板與幀圖像進(jìn)行模板匹配重新查找目標(biāo)位置,如果目標(biāo)在當(dāng)前幀沒有被找到時(shí),該模板與下一幀圖像匹配查找,直到找到目標(biāo);然后再次執(zhí)行LSRTA算法,如此循環(huán)跟蹤。
圖4 LSRTMTA跟蹤算法流程
圖5為LSRTA算法跟蹤示意圖,先將模板進(jìn)行均勻分塊處理,左側(cè)模板圖像中PT=(dx,dy,h,ω)是模板分塊后的一個(gè)矩形小塊,模板中心滑動(dòng)到該候選位置時(shí),用PF:(x,y)表示幀圖像F中對應(yīng)模板PT的矩形塊。
圖5 LSRTA算法跟蹤示意圖
再通過計(jì)算幀圖像中的矩形塊PF:(x,y)與目標(biāo)模板中的PT矩形塊兩幅圖像的歐氏距離,來衡量它們之間的相似性,定義了投票函數(shù)VPT(x,y)來直觀的反應(yīng)他們之間的相似性,投票值越大,則相似程度越高。
VPT(x,y)=d(PF:(x,y),PT)
(3)
在式(3)的求解過程中,先對圖像進(jìn)行稀疏表示,其基本思想是用盡可能少的元素表示元素圖像,用完備字典A={a1,a2,…,am}線性疊加表示圖像y,圖像y的表示模型為:
(4)
式(4)中:x為圖像y在字典A上的稀疏表示,e為逼近精度??梢詫⑸鲜鰈1范數(shù)最小化求解問題轉(zhuǎn)化為l1正則最小均方問題:
(5)
對于式(5)的求解,選擇基追蹤(BP)算法[18]進(jìn)行求解,得到稀疏值,再對稀疏值進(jìn)行歐氏距離求解。為了能夠求出每個(gè)小塊PF:(x,y)的稀疏表示,需要對目標(biāo)模板中所有的矩形小塊PT構(gòu)造各自獨(dú)立的稀疏字典BF:(x,y),使模板在周圍8個(gè)方向抖動(dòng)來獲得一個(gè)包含9個(gè)目標(biāo)模板的稀疏字典,設(shè)PF:(x,y)在當(dāng)前F中的觀測值是yF:(x,y),則有:
(6)
在得到觀測yF:(x,y)的系數(shù)向量c之后,計(jì)算得到其他與對應(yīng)模板的似然:
(7)
通過相同的方法可以得到模板中其他矩形小塊的投票圖VPT(·,·)。最后需要將所有小塊投票圖合并成一個(gè)整體投票圖。圖6為投票圖的合并流程圖,在所有的矩形小塊的投票圖中選取投票值最大的作為該點(diǎn)最終得分,得分最大的點(diǎn)作為下一幀目標(biāo)的位置。
C(x,y)=VPT(x,y)
(8)
圖6 投票圖的合并流程
圖7為模板與模板匹配圖,左邊表示當(dāng)前模板,右邊表示新模板,通過模板匹配算法得到匹配圖,計(jì)算匹配值,匹配值公式為:
(9)
式(9)中:m、n分別表示兩幅模板圖經(jīng)過surf算法后得到的感興趣點(diǎn)數(shù)量,k表示經(jīng)過flann算法和knn濾波后感興趣點(diǎn)數(shù)量。模板與模板匹配的示例見圖7。圖7中k=14,m=18,n=22,根據(jù)匹配值公式可以得到匹配值p=0.78,假設(shè)匹配閾值為0.62,由于匹配值p大于閾值,說明目標(biāo)并沒有發(fā)生偏移,新模板存入模板集中。
圖7 模板與模板匹配圖
圖8為模板的存儲(chǔ)過程,模板集中模板空間是固定的,新模板按照棧的形式依次保存在模板集中,在追蹤過程中會(huì)產(chǎn)生大量模板,當(dāng)模板存滿時(shí),最先存入的模板會(huì)被刪除來保證不斷的新模板被存入。
圖8 模板存儲(chǔ)過程
為了驗(yàn)證本文的算法,在Matlab軟件環(huán)境下編程實(shí)現(xiàn)LSRTMTA跟蹤算法,采用tracker benchmark數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)對比。tracker benchmark數(shù)據(jù)庫中有50組視頻,其中:目標(biāo)外觀變形的有19組,目標(biāo)遮擋的有29組,目標(biāo)快速移動(dòng)的有17組,這些視頻已經(jīng)基本考慮到實(shí)際運(yùn)行過程中受到的各種干擾,在實(shí)際應(yīng)用中有一定的代表性。選取ORIA算法[19](Online robust image alignment)、CT算法[20](Real-time compressive tracking)、IVT(Incremental learning for robust visual tracking)算法、CPF算法[21](Color-based probabilistic tracking)、LSRTA算法和本文提出的LSRTMTA算法進(jìn)行對比。
在目標(biāo)快速移動(dòng)的視頻中,其中boy視頻6種算法實(shí)時(shí)跟蹤結(jié)果如圖9所示。在目標(biāo)外觀變形的視頻中,其中mountainBike視頻6種算法實(shí)時(shí)跟蹤結(jié)果如圖10所示。在目標(biāo)遮擋的視頻中,其中faceocc1視頻6種算法實(shí)時(shí)跟蹤結(jié)果如圖11所示。
圖9 boy視頻運(yùn)行效果
圖10 mountainBike視頻運(yùn)行效果
圖11 faceocc1視頻運(yùn)行效果
為了直觀反映每一幀圖像與實(shí)際跟蹤目標(biāo)的差距,本文定義了中心誤差函數(shù)。中心誤差值越小,代表目標(biāo)跟蹤越準(zhǔn)確。某一幀圖像中目標(biāo)實(shí)際中心位置為M(x1,y1),跟蹤標(biāo)記的中心位置N(x2,y2),中心誤差r(M,N)的計(jì)算公式為:
r(M,N)=[(x1-x2)2+(y1-y2)2]1/2
(10)
分別對每組測試視頻繪制6種算法的中心誤差圖,計(jì)算每組視頻中6種算法下的平均中心誤差。x軸代表第幾組測試視頻,y軸代表每組視頻中6種算法下的平均中心誤差,得到平均中心誤差,如圖12所示。
計(jì)算50組視頻中6種算法的總平均中心誤差值,得到總平均中心誤差、標(biāo)準(zhǔn)差與標(biāo)準(zhǔn)誤見表1。
為了進(jìn)一步反應(yīng)算法跟蹤效果與實(shí)際跟蹤區(qū)域的覆蓋程度,引用了覆蓋率,表示實(shí)際目標(biāo)區(qū)域與算法跟蹤區(qū)域的交集部分占并集部分的比例。實(shí)際目標(biāo)矩形區(qū)域A,算法跟蹤矩形區(qū)域?yàn)锽,s(C)表示C區(qū)域的面積,覆蓋率c(A,B)計(jì)算公式為:
(11)
圖12 6種算法下的平均中心誤差
算法ORIACTIVTCPFLSRTALSRTMTA總平均中心誤差1110.48.88.78.16.8標(biāo)準(zhǔn)差1.201.391.051.921.471.10標(biāo)準(zhǔn)誤0.380.440.330.610.460.35
分別對每組測試視頻繪制6種算法的覆蓋率圖,計(jì)算每組視頻中6種算法下的平均覆蓋率,x軸代表第幾組測試視頻,y軸代表每組視頻中6種算法下的平均覆蓋率,得到平均覆蓋率,如圖13所示。
圖13 6種算法下的平均覆蓋率
計(jì)算50組視頻中6種算法的總平均覆蓋率值,得到總平均覆蓋率、標(biāo)準(zhǔn)差與標(biāo)準(zhǔn)誤見表2。
表2 6種算法的總平均覆蓋率
為了整體評估算法的運(yùn)行效果,引用了一次通過的評估(OPE)成功率圖,x軸表示覆蓋閾值,y軸表示成功率,首先對應(yīng)一個(gè)給定的覆蓋閾值x0,對于每一幀圖片計(jì)算覆蓋率,如果覆蓋率大于覆蓋閾值,則判斷成功,l(n)=1,否則判斷失敗,l(n)=0,n表示所有測試視頻中所有圖片的總數(shù),sum(l(n))表示n張圖片中l(wèi)(n)的和,成功率s(x,y)公式為:
(12)
其中:
在OPE成功率圖中,函數(shù)曲線下的面積越大,代表目標(biāo)跟蹤的效果是越好。分別選取19組目標(biāo)外觀變形的視頻、29組目標(biāo)在遮擋情況下的視頻、17組目標(biāo)在快速移動(dòng)的視頻和整個(gè)50組視頻,得到6種算法的OPE成功率,如圖14所示。
選取整個(gè)50組視頻,通過計(jì)算得到6種算法的OPE平均成功率,如表3所示。
最后為了說明文算法的實(shí)時(shí)性,選取了boy視頻前200幀(從第二幀開始)的檢測時(shí)間繪制算法處理時(shí)間圖,如圖15所示。
圖14 6種算法下的OPE成功率
算法ORIACTIVTCPFLSRTALSRTMTA平均OPE成功率0.330.310.360.360.380.44
圖15 采用本文算法對boy視頻的跟蹤處理時(shí)間
從圖9—圖11中可以明顯地看出,在目標(biāo)快速移動(dòng)的boy視頻、目標(biāo)外觀變形的mountainBike視頻、目標(biāo)遮擋的faceocc1視頻中,本文提出的LSRTMTA跟蹤算法在顯示的那些圖像中跟蹤效果比較準(zhǔn)確。
從圖12中可以看出,對于50組測試數(shù)據(jù),在6種算法中,LSRTMTA算法平均中心誤差曲線下的面積最??;從表1中可以看出,50組總平均中心誤差值也最小,說明LSRTMTA算法的中心位置與實(shí)際目標(biāo)的中心位置最接近。
從圖13中可以看出,對于50組測試數(shù)據(jù),在6種算法中,LSRTMTA算法平均覆蓋率曲線下的面積最大;從表2中可以看出,50組總平均覆蓋率值也最大,說明LSRTMTA算法的矩形跟蹤區(qū)域與實(shí)際目標(biāo)矩形跟蹤區(qū)域的覆蓋程度最大。
從圖14中可以看出,在19組目標(biāo)外觀變形的視頻、29組目標(biāo)在遮擋情況下的視頻、17組目標(biāo)在快速移動(dòng)的視頻和整個(gè)50組視頻下,6種算法中LSRTMTA算法的OPE成功率曲線下的面積都最大;從表3中可以看出,在整個(gè)50組視頻中,LSRTMTA算法的平均OPE成功率值最大。
從圖15中可以看出,選取boy視頻前200幀的處理時(shí)間計(jì)算出的平均處理時(shí)間為43.4 ms(Windows 7,4核),即每秒可處理約23幀圖像,可以應(yīng)用于實(shí)際場景實(shí)現(xiàn)實(shí)時(shí)目標(biāo)跟蹤。
綜上所述,LSRTMTA跟蹤算法在6種算法中跟蹤效果最好,改善了LSRTA算法的跟蹤效果。
本文針對目標(biāo)偏移時(shí)跟蹤無法修正的問題,在LSRTA算法的基礎(chǔ)上,加入模板匹配算法,提出了LSRTMTA算法以解決目標(biāo)跟蹤偏移問題。該算法通過不斷計(jì)算新模板與當(dāng)前模板的匹配值來判斷是否發(fā)生偏移,當(dāng)目標(biāo)發(fā)生偏移時(shí),停止LSRTA算法的跟蹤,通過模板與幀圖像之間匹配來重新確定目標(biāo)位置,當(dāng)確定目標(biāo)位置后,再次進(jìn)行LSRTA算法的跟蹤。實(shí)驗(yàn)結(jié)果表明,該算法不僅保留了LSRTA算法的優(yōu)點(diǎn),還具有自動(dòng)修正偏移功能,改善了跟蹤效果,增加了人物跟蹤的容錯(cuò)性。
[1] 李博,張凌.基于視覺顯著性的監(jiān)控視頻動(dòng)態(tài)目標(biāo)跟蹤[J].信息技術(shù),2014(4):60-65.
[2] 李霞.基于Mean-Shift算法的目標(biāo)跟蹤技術(shù)研究[J].自動(dòng)化與儀器儀表,2016(4):20-22.
[3] 同鑫,熊紅凱.基于均值漂移的視頻目標(biāo)跟蹤改進(jìn)算法[J].信息技術(shù),2010(3):40-43.
[4] 李晶,范九倫.一種基于卡爾曼濾波的運(yùn)動(dòng)物體跟蹤算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(8):3162-3164.
[5] 張明杰,康寶生.一種基于圖模型的粒子濾波跟蹤方法[J].計(jì)算機(jī)應(yīng)用研究,2016,33(2):590-593.
[6] 胡昭華,徐玉偉,趙孝磊,等.基于支持向量機(jī)的多特征選擇目標(biāo)跟蹤[J].應(yīng)用科學(xué)學(xué)報(bào),2015,33(5):502-517.
[7] Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(7):1409-1422.
[8] Ross D A, Lim J, Lin R S, et al. Incremental learning for robust visual tracking[J]. International Journal of Computer Vision,2008,77(1):125-141.
[9] 孫濤,谷士文,費(fèi)耀平.基于PCA算法的人臉識(shí)別方法研究比較[J].現(xiàn)代電子技術(shù),2007,30(1):112-114.
[10] Mei X, Ling H. Robust visual tracking using l1 minimization[C]//Proceedings of the IEEE International Conference on Computer Vision (ICCV09),2009:1436-1443.
[11] Wang Q, Chen F, Xu W, et al. Online discriminative object tracking with local sparse representation[C]//Proceedings of the Workshop on the Applications of Computer (WACV12),2012:425-432.
[12] Fan J, Liang R Z. Stochastic learning of multi-instance dictionary for earth mover’s distance-based histogram comparison[J]. Neural Computing & Applications,2016:1-11.
[13] 詹曙,王俊,楊福猛,等.基于Gabor特征和字典學(xué)習(xí)的高斯混合稀疏表示圖像識(shí)別[J].電子學(xué)報(bào),2015,43(3):523-528.
[14] 胡昭華,徐玉偉,趙孝磊,等.多特征聯(lián)合的稀疏跟蹤方法[J].計(jì)算機(jī)應(yīng)用,2014,34(8):2380-2384.
[15] 林曉帆,林立文,鄧濤.基于SURF描述子的遙感影像配準(zhǔn)[J].計(jì)算機(jī)工程,2010,36(12):216-218.
[16] 鐘華,金國平,鄭林華.基于擴(kuò)展卡爾曼濾波的FLANN網(wǎng)絡(luò)學(xué)習(xí)算法[J].信號(hào)處理,2009,25(10):1555-1559.
[17] 肖輝輝,段艷明.基于屬性值相關(guān)距離的KNN算法的改進(jìn)研究[J].計(jì)算機(jī)科學(xué),2013,40(11):157-187.
[18] 張曉偉,李明,左磊,等.基于基追蹤-Moore-Penrose逆矩陣算法的稀疏信號(hào)重構(gòu)[J].電子與信息學(xué)報(bào),2013,35(2):388-393.
[19] Wu Y, Shen B, Ling H. Online robust image alignment via iterative convex optimization[C]//Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR12),2012:1808-1814.
[20] Zhang K, Zhang L, Yang M H. Real-time compressive tracking[C]//Proceedings of the European Conference on Computer Vision(ECCV12),2012:864-877.
[21] Perez P, Hue C, Vermaak J, et al. Color-Based probabilistic tracking[C]//Proceedings of the European Conference on Computer Vision(ECCV02),2002:661-675.