基于距離加權平均絕對差的模板漂移抑制算法

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

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

1 模板漂移的機理分析

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

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

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

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

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

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

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

2 加權絕對差模板漂移抑制算法

2.1 模板漂移抑制原理

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

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

(1) 目標與背景相似性很小；

(2) 目標內部像素間相似性很高。

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

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

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

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

通過上面的分析發現理想的漂移誤差具有2個特點：

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

(2) 漂移誤差產生的區域EMAD大于0。

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

圖2 實驗模板與搜索區域Fig. 2 Experimental template and searching region

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

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

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

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

2.2 加權絕對差算法

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

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

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

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

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

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

(1) 與邊緣的相關性：

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

(2) 與誤差的相關性：

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

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

或

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

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

圖4 修改后的權重分布Fig. 4 Modified weight distribution

3 實驗結果與分析

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

3.1 單幀對比實驗

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

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

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

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

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

分別利用傳統的 MAD算法和基于距離加權的MAD算法對圖2所示模板圖與實時圖進行運算，得到的相關峰如圖5所示。

圖5 相關峰對比Fig. 5 Comparison of correlated peak

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

3.2 序列對比試驗

利用實際的視頻序列對傳統的MAD算法和改進后的加權絕對差算法進行對比試驗，結果如圖6所示。

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

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

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

4 結論

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

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

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

[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，Feig 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.