一種改進的SAD目標跟蹤算法

趙柏山，劉佳琪，王禹衡

（沈陽工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，沈陽110870）

1 引言

目標跟蹤作為機器視覺研究領(lǐng)域的熱門話題之一，在軍事、醫(yī)學(xué)、工業(yè)等領(lǐng)域得到廣泛應(yīng)用，具有廣闊的應(yīng)用前景?；谀０迤ヅ涞哪繕烁櫵惴ǎ捎谄溆嬎懔康?，局部抗干擾能力強，在信噪比較低的情況下依然可以有效跟蹤目標，更是被廣為采用[1]。

模板匹配主要針對目標的外觀進行跟蹤。由于受外界因素的影響，目標往往會由于受到遮擋等干擾而跟蹤失敗。傳統(tǒng)的模板匹配算法是單純依據(jù)模板的灰度值，用待搜圖像與模板等大圖像進行灰度匹配，但是當(dāng)遮擋、干擾、形變等情況發(fā)生時，圖像的灰度值會隨之變化，致使目標跟蹤失敗。針對這一情況，國內(nèi)外學(xué)者通過研究提出了一些解決方法，例如：基于小波變換的圖像預(yù)測[2]、利用meanshift算法的迭代[3]、基于粒子濾波進行多目標跟蹤[4]、SSD與MCD融合算法[5]、基于核相關(guān)濾波器的TLD算法[6]、利用前后向光流法對目標跟蹤失敗進行補救[7]等。

針對模板匹配跟蹤算法抗遮擋能力差的缺點，對SAD算法進行了改進。以SAD矩陣為基礎(chǔ)，通過對目標區(qū)域和與目標區(qū)域有交集的背景區(qū)域設(shè)定不同權(quán)重的系數(shù)，增加目標區(qū)域權(quán)重，減小背景區(qū)域的影響，判斷目標跟蹤有效性，在判定目標跟蹤失敗時進行模板更新，來保證目標持續(xù)有效跟蹤，提高了目標跟蹤的有效性與準確性。

2 目標跟蹤算法

2.1 SAD算法

絕對誤差和SAD(Sum of Absolute Difference)算法是基于灰度的模板匹配算法[8]。其原理是，通過模板圖像與待搜索圖像進行相似性度量來作判斷，獲得目標圖像的準確位置，從而實現(xiàn)目標的跟蹤效果。如圖1所示，T是模板圖像，尺寸為m×n；S是待搜索圖像，尺寸是M×N；將模板圖像在待搜索圖像上進行遍歷。逐次令模板圖像與待搜圖中的大小與模板圖像相同的圖像進行相似性度量計算，相似度最相近的位置，即目標圖像的位置。SAD算法的計算公式為

其中i,j為子圖的左上角坐標。由圖1可知在模板圖像遍歷的過程中，SAD形成一個矩陣，大小為M-m+1，N-n+1。其中，每一個數(shù)值分別代表模板圖像與待搜索圖像對應(yīng)子圖的絕對誤差和。

圖1 SAD算法原理圖

由公式1可知，SAD矩陣中的每個值對應(yīng)的是模板圖像與搜索子圖對應(yīng)位置的像素差的絕對值求和，所以SAD矩陣中數(shù)值越小，表明兩個圖像越相似。當(dāng)數(shù)值為0時，代表兩個矩陣完全重合。

正常情況下，SAD矩陣內(nèi)的最小值即為目標圖像的位置。但是當(dāng)干擾出現(xiàn)時，目標圖像可能會受到遮擋等影響，造成最后的SAD矩陣內(nèi)最小值位置并不是實際目標的位置，從而發(fā)生目標跟蹤失敗。由圖2可知，模板在待搜索圖的遍歷過程中，SAD矩陣最小值對應(yīng)目標位置，但是在SAD矩陣周圍的圖像也會與目標圖像存在一定程度的交集，交集越多，SAD值越小。SAD矩陣最小值周圍數(shù)值的灰度與目標圖像存在一定的相似性，當(dāng)外界干擾出現(xiàn)時，這種相似性會不斷減弱，基于這一點，對SAD算法進行改進，以SAD矩陣最小值為中心，通過矩陣分塊設(shè)計，選取不同大小矩陣并設(shè)置不同權(quán)重系數(shù)，能提高目標跟蹤的準確性和有效性。

圖2 模板遍歷過程

矩陣大小的選取如圖3所示。正常情況下模板在待搜索圖中遍歷的過程會有一部分與目標圖像存在交集，這些交集在SAD矩陣中反映出來的就是目標坐標（i,j）周圍的數(shù)值。模板圖像大小為m×n，目標的中心往往也是處于模板圖像的中心位置。由此，以目標位置（i,j）為中心，構(gòu)建不同大小矩陣,可使背景圖像所占比例減少。

圖3 矩陣分塊區(qū)域選擇

以(i,j)為中心，其中實線矩形邊框表示矩陣I1，長和寬分別選取m和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)成矩陣包含了所有與目標圖像有交集的搜索矩陣。降低遍歷范圍，提高搜索有效性。矩陣分塊具體計算公式如下：

2.2 SSD算法與MCD模板更新

以SAD矩陣為模板，通過SSD算法對矩陣進行目標跟蹤匹配。SSD（Sum of Squared Difference）即誤差平方和算法，與SAD算法類似，它利用模板圖像與待搜索圖像進行遍歷，通過計算對應(yīng)位置像素進行做差求平方和。模板T由第一幀獲得，S(i,j)為待搜索圖像，與之后每幀圖像獲取的目標進行SSD匹配，公式如下：

為了判定目標跟蹤效果，采用MCD(Maximum Close Distance)算法來作判斷[9]，MCD即最大鄰近距離,又叫相關(guān)置信度,如下式：

MCD反映的是模板圖像之間的相似數(shù)目的多少，MCD值越大，兩個模板越相似，反之兩個模板不匹配。設(shè)定閾值T_MCD（本設(shè)計T_MCD選取為40），通過比較第一幀模板圖像與當(dāng)前幀獲取的目標圖像，進行對應(yīng)點的灰度絕對差值運算。當(dāng)差值小于T_MCD時，那么認為兩點相似。MCD值計數(shù)為1，否則MCD值為0。最后MCD會形成一個相關(guān)曲面，峰值點即為最相似點，也就是我們要找的目標位置。

由于目標遮擋、干擾、甚至目標本身發(fā)生微小的形變等情況的存在，采取MCD的值作為判斷是否需要模版更新的依據(jù)，由于本設(shè)計以SAD矩陣為模版核心，取SAD內(nèi)包含全部目標和部分背景區(qū)域的圖像為跟蹤基礎(chǔ)，所以MCD模版為第一幀獲取的SAD跟蹤圖像，大小為2(m-1)×2(n-1)。MCD最大值即為2(m-1)×2(n-1)，代表完全匹配。判定模版更新條件如下式：

如果單純依靠初始模版進行匹配跟蹤，很容易造成目標的錯跟和漏跟。所以就需要在跟蹤失敗時能及時、準確地更新目標模版。在文獻[9]中采用的方法是，將前一幀模版和當(dāng)前幀進行融合，通過匹配不同的權(quán)值，按照其權(quán)重的大小進行有效融合。此法雖在一定程度上提高了匹配的魯棒性，但單純的兩幀仍然會受到外界因素的很大影響。鑒于此，本設(shè)計的模版更新采用多幀更新的方法。由于初始模版包含圖像的基本信息，前一幀圖像和當(dāng)前幀圖像反映了目標圖像的變化，所以可將初始模版圖像、前一幀圖像、當(dāng)前幀圖像分別賦予一定權(quán)值，分別為ɑ0、ɑ1、ɑ2，如式(6)所示，最終權(quán)重系數(shù)和為 1，合成一個新的模版繼續(xù)進行目標的匹配跟蹤。

式(6)中，Tnew為合成后的新模版圖像，T1、T2、T3分別為初始模版、前一幀模版和當(dāng)前幀模版圖像；權(quán)重的取值則為 ɑ0＝0.4，ɑ1＝0.3，ɑ2＝0.3。

3 仿真實驗結(jié)果

3.1 目標發(fā)生遮擋的情況

本次測試共150幀，圖4是單獨使用SAD算法進行匹配的跟蹤效果，目標是路上行走的行人。在行人行進的過程中會被前面的人遮擋。

圖4 目標被遮擋情況下的SAD算法跟蹤效果

圖4(a)是目標模版，在第一幀圖像中目標無遮擋，目標能被準確找到、獲取位置并用邊框標記出來；圖4(b)所示為第15幀圖像，目標行人在行走過程中被前面行人部分遮擋，遮擋面積小于20%，目標仍被正確跟蹤并標記邊框；圖4(c)所示為第41幀圖像，目標被遮擋面積超過90%，目標跟蹤失敗，沒有準確捕獲到目標的正確坐標；圖4(d)為第45幀圖像，目標重新出現(xiàn)，正確捕獲目標并標記目標位置。

圖5為使用本算法對相同場景下的遮擋目標進行跟蹤的效果。

圖5 本算法在目標遮擋時的跟蹤效果

圖5(a)是目標模板圖像；圖5(b)是目標被少部分遮擋的情況，本算法可以準確追蹤目標；圖5(c)是目標被遮擋面積超過90%的情況，通常的SAD算法已無法找到目標，但本算法依然可以準確找到目標位置并進行準確標記；在圖5(d)中，目標擺脫遮擋重新出現(xiàn)，目標被準確地找到并進行標記?？梢姡惴▽崿F(xiàn)了在不利情況下對目標的準確有效的跟蹤。目標跟蹤判斷統(tǒng)計結(jié)果如表1。

表1 目標被遮擋時的判定結(jié)果統(tǒng)計

3.2 目標發(fā)生形變的情況

本視頻共100幀，如圖6所示，圖中的目標本身會發(fā)生形變。圖6(a)所示為目標模板圖像；圖6(b)為第30幀圖像，SAD算法跟蹤的結(jié)果，由于目標人物的走動及臉部的變化，算法無法捕獲正確目標；圖6(c)為相同的圖像，應(yīng)用改進后的算法，能夠正確找到目標位置并標記邊框。發(fā)生形變情況下的目標跟蹤判斷統(tǒng)計結(jié)果如表2。

圖6 SAD與本算法對發(fā)生形變的目標跟蹤效果對比

表2 目標發(fā)生形變時的判定結(jié)果統(tǒng)計

4 結(jié)束語

通過改進的SAD模板匹配目標跟蹤算法，并利用SSD算法，進行模板的相似性匹配。利用多幀MCD算法判斷模板更新需求，實時準確地更新目標模板，保證目標跟蹤的準確性。實驗表明，在目標受到遮擋或者目標本身發(fā)生形變的情況下，改進后的算法仍能夠準確搜索到目標位置并進行標記。相比于原SAD算法，改進算法在目標抗遮擋和抗形變的能力上得到了顯著的提高，具有十分可觀的實用價值和推廣潛力。

[1]高文,朱明,賀柏根,等.目標跟蹤技術(shù)綜述[J].中國光學(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)目標跟蹤算法[J].兵工學(xué)報,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]李天成,范紅旗,孫樹棟.粒子濾波理論、方法及其在多目標跟蹤中的應(yīng)用[J].自動化學(xué)報,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é)報,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)濾波器的目標跟蹤算法[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]馮俊惠,肖陽輝,王恩德,等.一種基于SAD的相關(guān)跟蹤有效性判斷方法[J].微電子學(xué)與計算機,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的目標跟蹤算法的設(shè)計與實現(xiàn)[D].北京：中國科學(xué)院大學(xué),2014.ZHAO Qinghua.Design and implementation of object tracking algorithm based on FPGA[D].BeiJing:University of Chinese Academy of Sciences,2014.