趙柏山,劉佳琪,王禹衡
(沈陽(yáng)工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,沈陽(yáng)110870)
目標(biāo)跟蹤作為機(jī)器視覺研究領(lǐng)域的熱門話題之一,在軍事、醫(yī)學(xué)、工業(yè)等領(lǐng)域得到廣泛應(yīng)用,具有廣闊的應(yīng)用前景?;谀0迤ヅ涞哪繕?biāo)跟蹤算法,由于其計(jì)算量低,局部抗干擾能力強(qiáng),在信噪比較低的情況下依然可以有效跟蹤目標(biāo),更是被廣為采用[1]。
模板匹配主要針對(duì)目標(biāo)的外觀進(jìn)行跟蹤。由于受外界因素的影響,目標(biāo)往往會(huì)由于受到遮擋等干擾而跟蹤失敗。傳統(tǒng)的模板匹配算法是單純依據(jù)模板的灰度值,用待搜圖像與模板等大圖像進(jìn)行灰度匹配,但是當(dāng)遮擋、干擾、形變等情況發(fā)生時(shí),圖像的灰度值會(huì)隨之變化,致使目標(biāo)跟蹤失敗。針對(duì)這一情況,國(guó)內(nèi)外學(xué)者通過研究提出了一些解決方法,例如:基于小波變換的圖像預(yù)測(cè)[2]、利用meanshift算法的迭代[3]、基于粒子濾波進(jìn)行多目標(biāo)跟蹤[4]、SSD與MCD融合算法[5]、基于核相關(guān)濾波器的TLD算法[6]、利用前后向光流法對(duì)目標(biāo)跟蹤失敗進(jìn)行補(bǔ)救[7]等。
針對(duì)模板匹配跟蹤算法抗遮擋能力差的缺點(diǎn),對(duì)SAD算法進(jìn)行了改進(jìn)。以SAD矩陣為基礎(chǔ),通過對(duì)目標(biāo)區(qū)域和與目標(biāo)區(qū)域有交集的背景區(qū)域設(shè)定不同權(quán)重的系數(shù),增加目標(biāo)區(qū)域權(quán)重,減小背景區(qū)域的影響,判斷目標(biāo)跟蹤有效性,在判定目標(biāo)跟蹤失敗時(shí)進(jìn)行模板更新,來(lái)保證目標(biāo)持續(xù)有效跟蹤,提高了目標(biāo)跟蹤的有效性與準(zhǔn)確性。
絕對(duì)誤差和SAD(Sum of Absolute Difference)算法是基于灰度的模板匹配算法[8]。其原理是,通過模板圖像與待搜索圖像進(jìn)行相似性度量來(lái)作判斷,獲得目標(biāo)圖像的準(zhǔn)確位置,從而實(shí)現(xiàn)目標(biāo)的跟蹤效果。如圖1所示,T是模板圖像,尺寸為m×n;S是待搜索圖像,尺寸是M×N;將模板圖像在待搜索圖像上進(jìn)行遍歷。逐次令模板圖像與待搜圖中的大小與模板圖像相同的圖像進(jìn)行相似性度量計(jì)算,相似度最相近的位置,即目標(biāo)圖像的位置。SAD算法的計(jì)算公式為
其中i,j為子圖的左上角坐標(biāo)。由圖1可知在模板圖像遍歷的過程中,SAD形成一個(gè)矩陣,大小為M-m+1,N-n+1。其中,每一個(gè)數(shù)值分別代表模板圖像與待搜索圖像對(duì)應(yīng)子圖的絕對(duì)誤差和。
圖1 SAD算法原理圖
由公式1可知,SAD矩陣中的每個(gè)值對(duì)應(yīng)的是模板圖像與搜索子圖對(duì)應(yīng)位置的像素差的絕對(duì)值求和,所以SAD矩陣中數(shù)值越小,表明兩個(gè)圖像越相似。當(dāng)數(shù)值為0時(shí),代表兩個(gè)矩陣完全重合。
正常情況下,SAD矩陣內(nèi)的最小值即為目標(biāo)圖像的位置。但是當(dāng)干擾出現(xiàn)時(shí),目標(biāo)圖像可能會(huì)受到遮擋等影響,造成最后的SAD矩陣內(nèi)最小值位置并不是實(shí)際目標(biāo)的位置,從而發(fā)生目標(biāo)跟蹤失敗。由圖2可知,模板在待搜索圖的遍歷過程中,SAD矩陣最小值對(duì)應(yīng)目標(biāo)位置,但是在SAD矩陣周圍的圖像也會(huì)與目標(biāo)圖像存在一定程度的交集,交集越多,SAD值越小。SAD矩陣最小值周圍數(shù)值的灰度與目標(biāo)圖像存在一定的相似性,當(dāng)外界干擾出現(xiàn)時(shí),這種相似性會(huì)不斷減弱,基于這一點(diǎn),對(duì)SAD算法進(jìn)行改進(jìn),以SAD矩陣最小值為中心,通過矩陣分塊設(shè)計(jì),選取不同大小矩陣并設(shè)置不同權(quán)重系數(shù),能提高目標(biāo)跟蹤的準(zhǔn)確性和有效性。
圖2 模板遍歷過程
矩陣大小的選取如圖3所示。正常情況下模板在待搜索圖中遍歷的過程會(huì)有一部分與目標(biāo)圖像存在交集,這些交集在SAD矩陣中反映出來(lái)的就是目標(biāo)坐標(biāo)(i,j)周圍的數(shù)值。模板圖像大小為m×n,目標(biāo)的中心往往也是處于模板圖像的中心位置。由此,以目標(biāo)位置(i,j)為中心,構(gòu)建不同大小矩陣,可使背景圖像所占比例減少。
圖3 矩陣分塊區(qū)域選擇
以(i,j)為中心,其中實(shí)線矩形邊框表示矩陣I1,長(zhǎng)和寬分別選取m和n,四個(gè)坐標(biāo)點(diǎn)分別為(i-m/2,j-n/2)、(i-m/2,j+n/2)、(i+m/2,j-n/2)、(i+m/2,j+n/2),虛線矩形表示矩陣I2,同樣為以(i,j)為中心,大小為2(m-1),2(n-1)并且剝除I1矩陣位置的像素。
I1和I2矩陣所占的權(quán)重設(shè)為w1和w2,取值為w1=1和w2=0.5,這樣新構(gòu)成矩陣包含了所有與目標(biāo)圖像有交集的搜索矩陣。降低遍歷范圍,提高搜索有效性。矩陣分塊具體計(jì)算公式如下:
以SAD矩陣為模板,通過SSD算法對(duì)矩陣進(jìn)行目標(biāo)跟蹤匹配。SSD(Sum of Squared Difference)即誤差平方和算法,與SAD算法類似,它利用模板圖像與待搜索圖像進(jìn)行遍歷,通過計(jì)算對(duì)應(yīng)位置像素進(jìn)行做差求平方和。模板T由第一幀獲得,S(i,j)為待搜索圖像,與之后每幀圖像獲取的目標(biāo)進(jìn)行SSD匹配,公式如下:
為了判定目標(biāo)跟蹤效果,采用MCD(Maximum Close Distance)算法來(lái)作判斷[9],MCD即最大鄰近距離,又叫相關(guān)置信度,如下式:
MCD反映的是模板圖像之間的相似數(shù)目的多少,MCD值越大,兩個(gè)模板越相似,反之兩個(gè)模板不匹配。設(shè)定閾值T_MCD(本設(shè)計(jì)T_MCD選取為40),通過比較第一幀模板圖像與當(dāng)前幀獲取的目標(biāo)圖像,進(jìn)行對(duì)應(yīng)點(diǎn)的灰度絕對(duì)差值運(yùn)算。當(dāng)差值小于T_MCD時(shí),那么認(rèn)為兩點(diǎn)相似。MCD值計(jì)數(shù)為1,否則MCD值為0。最后MCD會(huì)形成一個(gè)相關(guān)曲面,峰值點(diǎn)即為最相似點(diǎn),也就是我們要找的目標(biāo)位置。
由于目標(biāo)遮擋、干擾、甚至目標(biāo)本身發(fā)生微小的形變等情況的存在,采取MCD的值作為判斷是否需要模版更新的依據(jù),由于本設(shè)計(jì)以SAD矩陣為模版核心,取SAD內(nèi)包含全部目標(biāo)和部分背景區(qū)域的圖像為跟蹤基礎(chǔ),所以MCD模版為第一幀獲取的SAD跟蹤圖像,大小為2(m-1)×2(n-1)。MCD最大值即為2(m-1)×2(n-1),代表完全匹配。判定模版更新條件如下式:
如果單純依靠初始模版進(jìn)行匹配跟蹤,很容易造成目標(biāo)的錯(cuò)跟和漏跟。所以就需要在跟蹤失敗時(shí)能及時(shí)、準(zhǔn)確地更新目標(biāo)模版。在文獻(xiàn)[9]中采用的方法是,將前一幀模版和當(dāng)前幀進(jìn)行融合,通過匹配不同的權(quán)值,按照其權(quán)重的大小進(jìn)行有效融合。此法雖在一定程度上提高了匹配的魯棒性,但單純的兩幀仍然會(huì)受到外界因素的很大影響。鑒于此,本設(shè)計(jì)的模版更新采用多幀更新的方法。由于初始模版包含圖像的基本信息,前一幀圖像和當(dāng)前幀圖像反映了目標(biāo)圖像的變化,所以可將初始模版圖像、前一幀圖像、當(dāng)前幀圖像分別賦予一定權(quán)值,分別為ɑ0、ɑ1、ɑ2,如式(6)所示,最終權(quán)重系數(shù)和為 1,合成一個(gè)新的模版繼續(xù)進(jìn)行目標(biāo)的匹配跟蹤。
式(6)中,Tnew為合成后的新模版圖像,T1、T2、T3分別為初始模版、前一幀模版和當(dāng)前幀模版圖像;權(quán)重的取值則為 ɑ0=0.4,ɑ1=0.3,ɑ2=0.3。
本次測(cè)試共150幀,圖4是單獨(dú)使用SAD算法進(jìn)行匹配的跟蹤效果,目標(biāo)是路上行走的行人。在行人行進(jìn)的過程中會(huì)被前面的人遮擋。
圖4 目標(biāo)被遮擋情況下的SAD算法跟蹤效果
圖4(a)是目標(biāo)模版,在第一幀圖像中目標(biāo)無(wú)遮擋,目標(biāo)能被準(zhǔn)確找到、獲取位置并用邊框標(biāo)記出來(lái);圖4(b)所示為第15幀圖像,目標(biāo)行人在行走過程中被前面行人部分遮擋,遮擋面積小于20%,目標(biāo)仍被正確跟蹤并標(biāo)記邊框;圖4(c)所示為第41幀圖像,目標(biāo)被遮擋面積超過90%,目標(biāo)跟蹤失敗,沒有準(zhǔn)確捕獲到目標(biāo)的正確坐標(biāo);圖4(d)為第45幀圖像,目標(biāo)重新出現(xiàn),正確捕獲目標(biāo)并標(biāo)記目標(biāo)位置。
圖5為使用本算法對(duì)相同場(chǎng)景下的遮擋目標(biāo)進(jìn)行跟蹤的效果。
圖5 本算法在目標(biāo)遮擋時(shí)的跟蹤效果
圖5(a)是目標(biāo)模板圖像;圖5(b)是目標(biāo)被少部分遮擋的情況,本算法可以準(zhǔn)確追蹤目標(biāo);圖5(c)是目標(biāo)被遮擋面積超過90%的情況,通常的SAD算法已無(wú)法找到目標(biāo),但本算法依然可以準(zhǔn)確找到目標(biāo)位置并進(jìn)行準(zhǔn)確標(biāo)記;在圖5(d)中,目標(biāo)擺脫遮擋重新出現(xiàn),目標(biāo)被準(zhǔn)確地找到并進(jìn)行標(biāo)記??梢?,算法實(shí)現(xiàn)了在不利情況下對(duì)目標(biāo)的準(zhǔn)確有效的跟蹤。目標(biāo)跟蹤判斷統(tǒng)計(jì)結(jié)果如表1。
表1 目標(biāo)被遮擋時(shí)的判定結(jié)果統(tǒng)計(jì)
本視頻共100幀,如圖6所示,圖中的目標(biāo)本身會(huì)發(fā)生形變。圖6(a)所示為目標(biāo)模板圖像;圖6(b)為第30幀圖像,SAD算法跟蹤的結(jié)果,由于目標(biāo)人物的走動(dòng)及臉部的變化,算法無(wú)法捕獲正確目標(biāo);圖6(c)為相同的圖像,應(yīng)用改進(jìn)后的算法,能夠正確找到目標(biāo)位置并標(biāo)記邊框。發(fā)生形變情況下的目標(biāo)跟蹤判斷統(tǒng)計(jì)結(jié)果如表2。
圖6 SAD與本算法對(duì)發(fā)生形變的目標(biāo)跟蹤效果對(duì)比
表2 目標(biāo)發(fā)生形變時(shí)的判定結(jié)果統(tǒng)計(jì)
通過改進(jìn)的SAD模板匹配目標(biāo)跟蹤算法,并利用SSD算法,進(jìn)行模板的相似性匹配。利用多幀MCD算法判斷模板更新需求,實(shí)時(shí)準(zhǔn)確地更新目標(biāo)模板,保證目標(biāo)跟蹤的準(zhǔn)確性。實(shí)驗(yàn)表明,在目標(biāo)受到遮擋或者目標(biāo)本身發(fā)生形變的情況下,改進(jìn)后的算法仍能夠準(zhǔn)確搜索到目標(biāo)位置并進(jìn)行標(biāo)記。相比于原SAD算法,改進(jìn)算法在目標(biāo)抗遮擋和抗形變的能力上得到了顯著的提高,具有十分可觀的實(shí)用價(jià)值和推廣潛力。
[1]高文,朱明,賀柏根,等.目標(biāo)跟蹤技術(shù)綜述[J].中國(guó)光學(xué),2014,7(3):365-375.GAO Wen,ZHU Ming,HE Baigen,et al.Overview of object tracking technology[J].Chinese Optics,2014,7(3):365-375.
[2]GHASEMBAGLOU M,Toroghihaghighat A Haar wavelet based distributed predictive target tracking algorithm for wireless sensor networks[M]//Advances in Computational Science,Engineering and Information Technology.Springer International Publishing,2013:207-219.
[3]郭曉冉,崔少輝,曹歡,等.跟蹤窗自適應(yīng)的捷聯(lián)導(dǎo)引系統(tǒng)目標(biāo)跟蹤算法[J].兵工學(xué)報(bào),2014,35(10):1604-1611.GUO Xiaoran,CUI Shaohui,CAO Huan,et al.Object tracking algorithm for strapdown guidance system with adaptive tracking window[J].Acta Armamentarii,2014,35(10):1604-1611.
[4]李天成,范紅旗,孫樹棟.粒子濾波理論、方法及其在多目標(biāo)跟蹤中的應(yīng)用[J].自動(dòng)化學(xué)報(bào),2015,41(12):1981-2002.LI Tiancheng,FAN Hongqi,SUN Shutong.Theory and method of particle filtering and its application in multiobject tracking[J].Acta Automatica Sinica,2015,41(12):1981-2002.
[5]胡銦,楊靜宇.適用于遮擋情況的SSD和MCD融合跟蹤算法[J].系統(tǒng)仿真學(xué)報(bào),2010,22(4):908-911.HU Yin,YANG Jingyu.SSD and MCD fusion tracking algorithm for occlusion[J].Journal of System Simulation,2010,22(4):908-911.
[6]諸小熊,江加和.基于核相關(guān)濾波器的目標(biāo)跟蹤算法[J].應(yīng)用科技,2017,44(3):48-53.ZHU Xiaoxiong,JIANG Jiahe.Object tracking algorithm based on kernel correlation filter[J].Applied Science and Technology,2017,44(3):48-53.
[7]KALAL Z,MIKOLAJCZYK K,MATAS J.Forwardbackward error:Automatic detection of tracking failures[C]//International Conference on Pattern Recognition.IEEE Computer Society,2010:2756-2759.
[8]馮俊惠,肖陽(yáng)輝,王恩德,等.一種基于SAD的相關(guān)跟蹤有效性判斷方法[J].微電子學(xué)與計(jì)算機(jī),2015,32(11):101-104.FENG Junhui,XIAO Yanghui,WANG Ende,et al.A correlation tracking validity judgment method based on SAD[J].Microelectronics&Computer,2015,32(11):101-104.
[9]趙清華.基于FPGA的目標(biāo)跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)[D].北京:中國(guó)科學(xué)院大學(xué),2014.ZHAO Qinghua.Design and implementation of object tracking algorithm based on FPGA[D].BeiJing:University of Chinese Academy of Sciences,2014.