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

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

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

1 模板漂移的機(jī)理分析

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

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

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

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

分析不等式(1)可見：左邊的測量誤差與右邊的測量誤差不等，因?yàn)樗鼈兪窃?個(gè)位置得到的，且測量誤差的分布是隨機(jī)的。而2邊的形變誤差是相等的，所以，式(1)可以化簡為下面的不等式：

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

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

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

2.1 模板漂移抑制原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

或

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 單幀對比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

3.2 序列對比試驗(yàn)

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

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

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

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

4 結(jié)論

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

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

(3) 提出的算法是對傳統(tǒng)MAD算法的改進(jìn)，算法運(yùn)算量小，便于實(shí)時(shí)實(shí)現(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.