(國防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院ATR實驗室，湖南 長沙，410073)

目標(biāo)跟蹤技術(shù)的研究和應(yīng)用是計算機視覺的一個重要分支，廣泛應(yīng)用于科學(xué)技術(shù)、國防建設(shè)、航空宇航、醫(yī)藥衛(wèi)生以及國民經(jīng)濟的各個領(lǐng)域。由于被跟蹤目標(biāo)的不確定性，視頻序列背景復(fù)雜等因素，基于模板的匹配跟蹤成為目前視頻跟蹤領(lǐng)域最為實用的算法之一，特別是當(dāng)目標(biāo)具有一定的紋理和面積特征時，匹配跟蹤是首選算法。理論上，在視頻序列中進行匹配跟蹤時，因為目標(biāo)的外觀在跟蹤過程中不斷變化，因此，模板也必須不斷更新。最簡單的更新策略是每幀更新模板，但是，由于跟蹤誤差的累積，當(dāng)長時間進行匹配跟蹤時，目標(biāo)在模板中的位置會很緩慢地移動，甚至?xí)瞥瞿０澹@個過程稱作模板漂移[2?4]。模板漂移將直接導(dǎo)致目標(biāo)丟失。為解決這一問題，Rasmussen等[5?7]提出利用初始模板加權(quán)來校正模板匹配的結(jié)果。但該方法僅在目標(biāo)外觀變化較小時有效，無法應(yīng)對目標(biāo)形變比較大的情況。Peacock等[8]在比較了不依賴于初始模板的各種模板更新策略后，認為用Kalman模板更新濾波器對模板進行濾波的策略對于漂移與噪聲具有最強的魯棒性。Nguyen 等[9?10]進一步研究了如何選取模板更新濾波器的 Kalman系數(shù)。但是，采用 Kalman模板更新濾波器需要對每個像素進行25次乘加計算，才能得到新的模板，當(dāng)執(zhí)行大尺度目標(biāo)跟蹤時，由于運算量過大，無法保證運算的實時性。為此，本文作者提出一種基于距離加權(quán)MAD的模板匹配算法。該算法對傳統(tǒng)的MAD相似性準(zhǔn)則進行改進，利用模板邊緣到中心的距離對模板與實時圖的絕對差進行加權(quán)，放大失配位置的漂移誤差，使期望位置的絕對差最小，從而抑制模板漂移現(xiàn)象。與MAD算法相比，計算時，模板每像素僅多1次乘法運算，因此，算法實時性好，便于實時實現(xiàn)。

1 模板漂移的機理分析

在匹配跟蹤中，模板漂移的本質(zhì)可以理解為：相似性度量函數(shù)最大的點與真實目標(biāo)位置有偏差，從而導(dǎo)致更新的模板是相似性度量函數(shù)最大位置的模板，而不是真實目標(biāo)位置的模板。其原因有以下 2點：(1) 由于目標(biāo)發(fā)生形變，導(dǎo)致原有模板與目標(biāo)當(dāng)前形狀有偏差，這一偏差稱為形變誤差，導(dǎo)致目標(biāo)真實位置相似性度量結(jié)果減??；(2) 由于光照、采樣、測量等引入產(chǎn)生的誤差統(tǒng)稱為測量誤差。由于測量誤差在圖像空間分布的隨機性，有可能在真實位置時，測量誤差影響大，降低了真實位置相似性度量結(jié)果；而在漂移位置時，測量誤差所起的作用很小，并沒有降低相似性度量結(jié)果。

為了研究該問題，引入漂移誤差的概念。漂移誤差是指在進行模板匹配的過程中，模板位置與目標(biāo)真實位置之間由于位移而引入的誤差。顯然，在真實位置時，漂移誤差為0。

在理想情況下，在跟蹤過程中需滿足：

式中：a表示目標(biāo)真實位置；b表示發(fā)生漂移的位置，即錯誤位置；Δs為漂移誤差；Δm為測量誤差；Δf為形變誤差。在理想情況下，因為真實位置的漂移誤差為0，所以，式(1)中左邊大于右邊，這說明漂移位置的誤差大，在匹配過程中被淘汰，最終選擇正確位置。所以，在理想情況下，目標(biāo)不會漂移。

分析不等式(1)可見：左邊的測量誤差與右邊的測量誤差不等，因為它們是在2個位置得到的，且測量誤差的分布是隨機的。而2邊的形變誤差是相等的，所以，式(1)可以化簡為下面的不等式：

當(dāng)搜索位移很小，即位置b的漂移誤差很小，而在真實位置(位置a)，雖然漂移誤差為0，但若其測量誤差比較大，則可能導(dǎo)致：

式(3)說明真實位置(位置a)的誤差大于漂移位置(位置b)的誤差，在匹配過程中，就會將真實位置淘汰，而選取發(fā)生了少量漂移的位置，這樣就會產(chǎn)生漂移。這就是模板漂移產(chǎn)生的機理。

2 加權(quán)絕對差模板漂移抑制算法

2.1 模板漂移抑制原理

從模板漂移產(chǎn)生的機理可以得到：增大位置b(漂移位置)的漂移誤差，保證式(2)的左邊大于右邊，使位置b的總體誤差大于位置a(真實位置)的總體誤差，則可以有效抑制模板漂移，確保相似性度量的最大值為目標(biāo)真實位置。

為增加漂移誤差，下面分析漂移誤差的特性。為方便分析，進行如下假設(shè)：

(1) 目標(biāo)與背景相似性很??；

(2) 目標(biāo)內(nèi)部像素間相似性很高。

漂移誤差特性分析如圖1所示。假定目標(biāo)是1個白色正方形方塊，上一幀所選取的模板也是與目標(biāo)大小相同的白色方塊，在本幀圖像中進行搜索，采用MAD準(zhǔn)則對相似性進行度量。

圖1 漂移誤差特性分析圖Fig. 1 Analysis of drift error characteristics

令EMAD為模板與實時圖的平均絕對差。在圖 1中位置A，上幀模板與待測區(qū)域完全匹配，EMAD等于0；在位置B，上幀模板與待測區(qū)域只有部分匹配，所以，在位置B的EMAD可以表示為：

其中：A和B分別代表2個位置中模板匹配區(qū)域內(nèi)像素點的集合，按照假設(shè)(1)，目標(biāo)內(nèi)部像素相似性很高，所以，為0；由假設(shè)(2)，目標(biāo)與背景相似性很小，所以，不為 0，這即為漂移誤差。

通過上面的分析發(fā)現(xiàn)理想的漂移誤差具有2個特點：

(1) 漂移誤差產(chǎn)生的區(qū)域靠近候選模板的邊緣；

(2) 漂移誤差產(chǎn)生的區(qū)域EMAD大于0。

利用實際的視頻數(shù)據(jù)來驗證上述分析與實際情況是否相符。圖2所示為一段用模板匹配的方法跟蹤高速公路上汽車的圖像序列，其中左邊小圖為選取的汽車模板，右邊為匹配的搜索區(qū)域。

圖2 實驗?zāi)０迮c搜索區(qū)域Fig. 2 Experimental template and searching region

匹配誤差分布見圖 3，其中幅度代表模板在進行匹配運算時每個像素位置求絕對差的結(jié)果。圖 3(a)所示為真實位置進 行匹配運算后誤差的分布結(jié)果。從圖3(a)可以看出：幅度較大且較為連續(xù)的是形變誤差，幅度較小且分布比較隨機的是測量誤差。圖3(b)所示的是偏離真實位置1個像素距離的漂移位置匹配運算誤差分布，從圖3(b)可以看出：其中不僅包括了圖3(a)中出現(xiàn)的形變誤差與測量誤差，而且在右上方的邊沿地區(qū)出現(xiàn)了明顯的漂移誤差。

可以借助圖3分析1次模板漂移的過程。在理想情況下，圖3(a)中的誤差之和應(yīng)該小于圖 3(b)中的誤差之和。但是，由于測量噪聲隨機分布，導(dǎo)致圖3(b)中的誤差之和(雖然包括了圖3(a)中幾乎為0的漂移誤差)小于圖3(a)中的誤差之和，這樣就會認為位置b是最佳匹配位置，結(jié)果表現(xiàn)為目標(biāo)在模板中漂移了1個像素。

圖3 匹配誤差分布圖Fig. 3 Matching error distribution

從圖還可以看出：漂移誤差所具備的特點與上面所分析的2個特點完全相符。根據(jù)這2個特點就能找到漂移誤差，并且增大式(2)中的漂移誤差，從而保證存在漂移誤差的位置被淘汰，匹配結(jié)果得到的是目標(biāo)的真實位置。

2.2 加權(quán)絕對差算法

考慮未來實時實現(xiàn)的需要，采用MAD作為相似性度量即平均絕對差度量，定義其表達式為：

其中：xj+u,k+v為(u,v)位置候選模板的第(j,k)個像素值；yj,k為上幀模板的第(j,k)個像素值；模板寬×高為N1×N2。

式(5)可以理解為進行次差運算后共同影響的結(jié)果，其中每次差運算從空間域看對最終結(jié)果的影響權(quán)重是相同的。在此基礎(chǔ)上，差值越大即誤差越大，對最終結(jié)果的影響越大，可以理解為與模板的差距越大。最小的位置認為便為與上幀模板最相似的位置。

根據(jù)漂移誤差的2個特點，在進行N1×N2次差運算中找出滿足這2個條件的運算過程，即找出漂移誤差。故意增大這次進行差運算的結(jié)果，即故意增大漂移誤差對結(jié)果的影響，這樣會直接導(dǎo)致帶有漂移誤差的候選模板在模板匹配運算中被淘汰，從而保證沒有漂移的真實位置的模板在模板更新中被選中。

要精確指出某一次差運算帶來的誤差是否為漂移誤差是不現(xiàn)實的，只能根據(jù)概率進行估計[11?13]。

根據(jù)漂移誤差滿足的2個條件，設(shè)滿足條件(1)和(2)的概率分別表示為Pa和Pb，則其合理的表達式如下。

(1) 與邊緣的相關(guān)性：

其中：(j,k)為本次做差運算在模板中的位置；cx和cy為模板的中心位置；d為模板的半徑。對式(6)可以直觀地理解為：本次絕對差運算越靠近邊緣，則得到的誤差是漂移誤差的概率越大。

(2) 與誤差的相關(guān)性：

其中：u和v表示候選模板的位置。式(7)的含義很直觀，就是這次運算必須有誤差，才有可能是漂移誤差，若沒有誤差，那就一定不是漂移誤差。漂移誤差的表達式可以寫成：

式(8)可以有效地增大漂移誤差對相似性度量的影響，從而保證在匹配運算中把含有漂移誤差的位置淘汰，得到目標(biāo)的真實位置，則修改后的絕對差為：

或

式(11)可以理解為對 MAD進行加權(quán)。傳統(tǒng)的MAD方法認為對每個像素點進行差運算對結(jié)果的影響是相同的，而式(11)則是根據(jù)每次做差運算產(chǎn)生漂移誤差的概率給每次絕對差運算分配不同權(quán)重。

修改后的權(quán)重分布見圖4。圖4直觀地給出了這種加權(quán)的方式，其中水平方向的坐標(biāo)表示每次做差運算在模板中的位置，豎直方向的坐標(biāo)表示根據(jù)這次做差運算產(chǎn)生漂移誤差的概率給每次做差運算所分配的權(quán)重。通過加權(quán)，若產(chǎn)生了漂移誤差，則漂移誤差就會依據(jù)權(quán)重被擴大，從而保證式(2)成立，產(chǎn)生了漂移誤差的位置就會在匹配運算中被淘汰，得到目標(biāo)的真實位置。

圖4 修改后的權(quán)重分布Fig. 4 Modified weight distribution

3 實驗結(jié)果與分析

利用實際的視頻圖像對傳統(tǒng)的MAD算法和基于距離加權(quán)的MAD算法分別進行單幀和視頻序列2組對比試驗。

3.1 單幀對比實驗

匹配跟蹤時，模板與輸入圖像進行相似性度量運算后，會得到1個相關(guān)性曲面即相關(guān)峰。相關(guān)峰質(zhì)量直接影響匹配結(jié)果，是反映算法性能的最重要依據(jù)。為了對相關(guān)峰進行定量描述，定義以下 3個特征參數(shù)[14?15]。

(1) 峰噪比(RPN)。峰噪比為相關(guān)峰中有用信號與噪聲信號的比率，其值越大，說明相關(guān)峰中有用的信號越強烈，但是，并不代表峰值越尖銳。其表達式為：

其中：Cx,y(u,v)為x與y之間的相關(guān)信號；I0為相關(guān)峰的最大值；為所有相關(guān)信號能量之和；HP為大于等于最大相關(guān)峰值能量一半的所有能量之和；LP則為小于最大相關(guān)峰能量一半的所有能量之和；m和n分別表示HP和LP在相關(guān)曲面中所占的點數(shù)。

(2) Horner效率(RHO)。Horner效率指大于等于最大峰值一半以上的所有相關(guān)峰的能量與總能量的百分比。這是1個全局性參數(shù)，對目標(biāo)占整個視場的比例較敏感。其表達式如下：

(3) 相關(guān)峰值能量(EPC)。相關(guān)峰值能量描述了相關(guān)峰的尖銳程度，相關(guān)峰值能量越大，相關(guān)峰就越尖銳，說明相關(guān)峰越容易識別。其表達式如下：

分別利用傳統(tǒng)的 MAD算法和基于距離加權(quán)的MAD算法對圖2所示模板圖與實時圖進行運算，得到的相關(guān)峰如圖5所示。

圖5 相關(guān)峰對比Fig. 5 Comparison of correlated peak

表 1所示為圖 5(a)和(b)中RPN，RHO和EPC這 3個參數(shù)的計算結(jié)果。從表1可以看出：基于距離加權(quán)的MAD算法其相關(guān)峰的3個衡量指標(biāo)與傳統(tǒng)的MAD算法相比均大幅度提高，這表明改進后的算法相關(guān)峰更加銳利，抗噪能力強，其性能比傳統(tǒng)的MAD算法性能有大幅度改進。

3.2 序列對比試驗

利用實際的視頻序列對傳統(tǒng)的MAD算法和改進后的加權(quán)絕對差算法進行對比試驗，結(jié)果如圖6所示。

表1 圖5中RPN，RHO和EPCTable 1 RPN, RHO and EPC in Fig.5

圖6 抑制模板漂移的實驗結(jié)果Fig. 6 Experimental results of suppressing template drfit

由于給定的試驗測試序列目標(biāo)存在較大的形變，因此，在跟蹤過程中需要逐幀更新模板。從圖6所示的對比試驗結(jié)果可見：采用傳統(tǒng)的MAD方法進行相似性度量(見圖6(a1)～(a6))，當(dāng)跟蹤進行到200幀時，開始出現(xiàn)模板漂移；當(dāng)跟蹤進行到470幀時，目標(biāo)幾乎全部漂移出模板，這樣會導(dǎo)致目標(biāo)完全丟失。采用本文給出的加權(quán)絕對差作為相似性度量時(見圖6(b1)～(b6))，結(jié)果顯示目標(biāo)一直被鎖定在跟蹤框內(nèi)，沒有發(fā)生模板漂移現(xiàn)象，整個視頻序列可以穩(wěn)定保持對目標(biāo)跟蹤。由此可見：改進后的算法有效抑制了模板漂移現(xiàn)象。

4 結(jié)論

(1) 針對跟蹤中模板漂移導(dǎo)致目標(biāo)丟失的現(xiàn)象，采用模板邊緣到中心的距離對傳統(tǒng)的MAD算法進行加權(quán)，放大失配位置的漂移誤差，確保期望位置的絕對差最小。

(2) 所提出的算法在單幀匹配時得到的相關(guān)峰更加銳利，與傳統(tǒng)的MAD算法相比，RPN，RHO和EPC大幅度提高。在序列跟蹤時，可以長時間穩(wěn)定跟蹤目標(biāo)，抑制模板漂移現(xiàn)象。

(3) 提出的算法是對傳統(tǒng)MAD算法的改進，算法運算量小，便于實時實現(xiàn)。

[1] Matthews I, Ishikawa T ,Baker S. The template update problem[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(6): 810?815.

[2] Kaneko T, Hori O. Template update criterion for template matching of image sequences[C]//Proc IEEE Int Conf on Pattern Recognition IEEE. Quebec, Canada, 2002: 1?5.

[3] Haworth C, Peacock A M, Renshaw D. Performance of reference block updating techniques when tracking with the block matching algorithm[C]//Proc IEEE Int Conf on Image Processing. Thessaloniki, Greece: IEEE, 2001: 365?368.

[4] Liu L K，F(xiàn)eig E. A block based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Trans on Circuits and Systems for Video Technology, 1996, 6(4):419?422.

[5] Rasmussen C, Hager G. Probabilistic data association methods for tracking complex visual objects[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2001, 23(6): 560?576.

[6] Jia Z, Balasuriya A, Challa S. Target tracking with bayesian fusion based template matching [C]//Proc IEEE Int Conf on Image Processing. Singapore: IEEE, 2005: Ⅱ-826?829.

[7] Black M J, Yacoob Y. Recognizing facial expressions in image sequences using local parameterized models of image motion[J].Int J Computer Vision, 1997, 25(1): 23?48.

[8] Peacock A M. Reference block updating when tracking with block matching algorithm[J]. Electronic Letters, 2000, 36(4):309?310.

[9] Nguyen H T, Smeulders A W M. Fast occluded object tracking by a robust appearance filter[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(8): 1099?1104.

[10] Nguyen H T. Occlusion robust adaptive template tracking[C]//Proc IEEE Int Conf on Computer Vision.Vancouver, Canada, IEEE, 2001: 678?683.

[11] Jepson A D, Fleet D J, EI-Maraghi T F. Robust online appearance model for visual tracking[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2003, 25(10): 1296?1311.

[12] Zhou S K, Chellappa R, Moghaddam B. Visual tracking and recognition using appearance-adaptive models for particle filters[J]. IEEE Trans on Image Processing, 2004, 13(11):1491?1506.

[13] Stauffer C, Grimson W E L. Adaptive background mixture models for real-time tracking[C]//Computer Vision and Pattern Recognition 1999(CVPR'99 ). Fert Collins Colorado, USA, 1999:337?345.

[14] Hariharakrishnan K, Schonfeld D. Fast object tracking using adaptive block matching[J]. IEEE Trans on Multimedia, 2005,7(5): 853?859.

[15] Lipton A, Fujiyoshi H, Patil R S. Moving target detection and classification from real-time video[C]//Proceedings of IEEE Workshop on Applications of Computer Vison. Princeton: IEEE Press, 1998: 8?14.