模板匹配跟蹤的哈希增強算法

徐　珩　賀飛越

(昆明理工大學國土資源工程學院　云南 昆明 650093)

?

模板匹配跟蹤的哈希增強算法

徐珩賀飛越

(昆明理工大學國土資源工程學院云南 昆明 650093)

摘要基于平方差匹配SSD(Sum of Squared Difference)、標準相關系數匹配NCC(Normalized Cross Correlation)的傳統模板匹配跟蹤算法十分依賴灰度信息。圖像灰度劇烈變化或光照強度改變明顯的情況下容易被圖像的高頻信息影響，導致產生目標偏移的現象，跟蹤精度降低。提出一種模板匹配跟蹤的哈希增強算法，用于減小灰度與亮度變化的影響，增強目標跟蹤的精度。其具體過程是：以感知哈希提取感知特征，對提取的特征二值化生成跟蹤目標的哈希序列；將哈希序列作為匹配跟蹤的模板，通過比較漢明距離在每一幀中尋找最為相似的目標以達到跟蹤的效果；運用抽屜原理縮短漢明距離比較的時間。給出一種基于漢明距離的自適應模板更新算法，保證了跟蹤的連續性。仿真實驗結果與基于SSD、NCC的模板跟蹤算法比較，在目標灰度或亮度變化情況下匹配精度高出一個數量級，跟蹤速度能夠滿足實時性需求。

關鍵詞哈希增強模板匹配目標跟蹤漢明距離

0引言

基于模板匹配的跟蹤方法原理簡單、便于實現，因此得到了廣泛應用。模板匹配一般分為基于特征提取的方法以及基于灰度值的方法?；谔卣魈崛〉哪０甯櫵惴?，如小波變換法[1,2]、SIFT特征提取算法[3,4]等，具有尺度不變性與仿射不變性，抗干擾能力較強，特別是小波特征可實現圖像的多尺度分解匹配[5]。但一般包含特征提取和特征匹配兩部分，涉及大量的幾何與圖像形態計算，運算量大，沒有一般模型可參考?；诨叶戎档哪０甯櫵惴╗6-13]簡單易行，有通用的數學模型對匹配進行誤差估計、相似程度判定，如文獻[6]對平方差匹配SSD進行了改進，使模板動態更新，并通過對數極坐標變換減小旋轉與比例變化帶來的影響；文獻[7]介紹了一種快速的模板匹配跟蹤算法。原理是通過粗糙到精細的方法CTF(Coarse to Fine)，先將圖像分成若干區域，選出所含像素屬于區域邊界線的區域，再對這些精選區域進行標準相關系數匹配NCC或序貫相似性檢測算法SSDA(Sequential Similarity Detection Algorithm)來達到模板匹配的效果。

以上基于灰度的模板跟蹤方法都較為依賴灰度信息，圖像灰度劇烈變化或光照強度改變明顯的情況下容易被圖像的高頻信息影響，導致產生目標偏移的現象，跟蹤精度降低。本文針對上述基于灰度值的模板跟蹤算法的缺陷，采用跟蹤目標的低頻信息，通過感知哈希提取跟蹤目標的感知特征，增強跟蹤目標的輪廓結構，并對提取的特征進行二值化生成跟蹤目標的哈希序列；將跟蹤目標的哈希序列作為跟蹤模板，在每一幀中尋找最為相似的目標；運用抽屜原理縮短漢明距離比較的時間，加快匹配速度；在匹配成功后對模板進行更新，提出一種基于漢明距離的自適應模板更新算法，保證了跟蹤的連續性。

1哈希增強

圖像感知哈希函數[14]能夠考慮圖像在視覺領域的變化，并且能夠捕捉基本的感知屬性。從理論上說，視覺內容相同的信息產生相同的感知哈希值，視覺內容不同的信息產生不同的感知哈希值[15]，記圖像感知哈希函數為PH：

PH:I→Hp

(1)

圖1　圖像感知哈希的一般生成步驟

其中I為圖像在計算機中的數字表示序列所構成的集合，Hp是感知數字摘要的集合，即感知哈希值，通過對感知特征降維得到。圖像感知哈希函數是由圖像數據到感知摘要集的單向映射，其一般生成步驟如圖1所示，數字圖像通過一系列操作能夠得到哈希序列。因此，將匹配目標的感知哈希序列作為模板，與搜索區域內其他圖像的哈希序列比較，若兩個哈希序列之間的感知距離在規定范圍內則認為匹配成功，反之則為匹配失敗。

1.1低頻信息提取

一張圖片就是一個二維信號，它包含了許多不同頻率的成分。這里的高頻和低頻指的是圖像的空間頻率，所謂的空間頻率是指特定頻率在單位間距內重復的次數，圖像細節越精細，單位間距內重復的次數越多，頻率就高；反之，則越低。換句話說，高頻部分主要是對圖像邊緣和細節的度量，對應的是亮度或灰度變化劇烈的區域，如物體的紋理，提供圖像的詳細信息。而低頻部分主要是對整幅圖像強度的綜合度量，提供圖像的一個輪廓框架。

為了減小圖像灰度與亮度變化的影響，需要將圖像轉換到頻域空間，選取重要的低頻頻域，丟棄影響低的高頻頻域?？紤]到需要保留圖像的低頻信息，本文使用離散余弦變換DCT來獲取圖像的低頻成分。離散余弦變換是與傅里葉變換相關的一種變換，經常被信號處理和圖像處理使用，用于對信號和圖像進行有損數據壓縮。這是由于離散余弦變換具有很強的能量集中特性，大多數的自然信號的能量都集中在離散余弦變換后的低頻部分。圖2是對圖像進行離散余弦變換的結果，可以看到經過變化后圖像的能量幾乎都集中在左上角的低頻系數上，而越到右下方的高頻系數能量越小。

圖2　灰度圖像的離散余弦變換

因此，可以對圖像進行離散余弦變換后提取左上角的部分來降低圖像的頻率。為了簡化離散余弦變換的計算，將選定的跟蹤目標圖像I(x，y)縮小為32×32的尺寸；接著將縮小后的圖像轉化為灰度圖像G(x，y)進一步減少計算量；之后對G(x，y)進行離散余弦變換，N×N的圖像進行離散余弦變換如式(2)所示：

(2)

其中：

u=1，2，…，N-1;v=1，2，…，N-1；F(u，v)是變化系數矩陣；u、v為頻率域采樣值；x、y為空間域采樣值。

計算出32×32的離散余弦變換系數矩陣F(u，v)后，只需保留左上角的8×8矩陣f(x，y)，這部分圖像呈現了整個圖像中的最低頻率，也是最重要的部分。接著將變化系數矩陣還原成灰度圖像，需要用到逆離散余弦變換IDCT(Inverse Discrete Cosine Transform)，其效果如圖3所示。

圖3　灰度圖像的逆離散余弦變換

對f(x，y)進行逆離散余弦變換，公式如下：

(3)

得到大小為8×8的跟蹤目標低頻分量g(x，y)，即跟蹤目標最重要的部分。

1.2差異增強

圖像均值對于目標跟蹤有一定的貢獻，但SSD與NCC方法受圖像均值的影響非常大。圖像顏色非線性比例變化導致圖像均值改變會造成跟蹤精度下降，需要考慮減小圖像均值的影響。

圖像灰度變化較大的邊沿區域梯度值較大，灰度變化平緩的區域梯度值較小，而在灰度均勻的區域梯度值為零。一般圖像增強過程使用圖像的灰度變化梯度提取邊緣，將梯度值大的像素設置為0，梯度值小的像素設置為1就可以強化邊緣。為了簡化計算，本文使用一種類似梯度但是更快速的差異增強方法：計算相鄰兩像素間的灰度值差異，當差異大于一定閾值時，將左側像素設置為0；反之，將其設置為1，該方法能夠更加快速地得到圖像的輪廓結構信息。

將1.1節中得到8×8的圖像低頻信息g(x，y)，按行自第一個像素開始與下一元素進行比較，計算相鄰像素的差異δg：

(4)

其中i=0，1，…，6；j=0，1，…，7；τ為預先設定的閾值，對于灰度圖像一般取τ=5。對每一行的相鄰像素點進行比較，若左側與右側像素灰度值之差大于等于τ，將它們的差異值設為1，否則設為0。將式(4)得到的56個相鄰像素灰度差異值δg保存為8×7的矩陣。

1.3哈希序列生成

式(4)得到的差異值矩陣δg完全消除了圖像均值的影響，但圖像均值對于目標跟蹤仍有一定的貢獻?？紤]到圖像每一行像素與圖像整體的相關性，計算g(x，y)每行均值μj與g(x，y)整體均值μ的差異δμ：

(5)

H=[δgδμ]

(6)

將δg與δμ橫向合并得到8×8的矩陣H按照從左到右從上到下的順序二進制保存，生成跟蹤目標哈希增強后的64位感知哈希序列。

哈希增強利用DCT變換提取圖像低頻信息，確保圖像重要信息的保留。通過差異增強抑制圖像灰度均值的影響，同時加強圖像每行像素與圖像整體的相關性，最終得到基于感知特征的64位哈希序列。哈希增強能夠良好地適應跟蹤目標灰度或亮度劇烈變化的影響，其計算出的感知哈希值不會改變。

2基于哈希增強的模板跟蹤

2.1模板匹配

第一幀得到跟蹤目標的感知哈希序列，隨后對目標進行跟蹤。將目標的感知哈希序列視為目標模板，對之后每一幀通過掃描上一幀目標周圍圖像區域，計算每個搜索窗口圖像的感知哈希序列，尋找最接近目標感知哈希序列的窗口。使用漢明距離表示感知哈希值的相似度：

(7)

考慮到跟蹤目標可能發生的變化，將與目標模板漢明距離在7以內的搜索窗口圖像視為候選跟蹤目標，漢明距離超過7的視為非跟蹤目標。如圖4所示，圖中一個方塊代表4位，黑色區域表示x與x′不同的部分，白色區域表示相同的部分。根據抽屜原理將64位哈希序列平均分為8段子序列，若漢明距離不超過7，說明匹配的兩串哈希序列之間至少有一段子序列是完全相同的。因此若搜索窗口內圖像的哈希序列x′與模板x沒有任何一段子序列完全一致，則可視為此搜索窗口沒有匹配到跟蹤目標，繼續計算下一個搜索窗口的感知哈希序列；若至少有一段子序列完全一致，再對其他子序列計算漢明距離；若漢明距離不超過7，保存為候選目標；如此循環最終找到漢明距離最小的候選目標，即為最終匹配目標。

圖4　漢明距離的快速對比

2.2模板自適應更新

通過計算漢明距離找到與目標模版最為相似的搜索窗口，即當前幀匹配窗口。為了適應目標的變化，需要動態更新目標模板。

設當前幀模板為M，當前幀匹配目標為T，更新后的模板為M′，模板更新的基本公式如下：

M′=αT+(1-α)M

(8)

其中α為更新參數，α = Dh/ n，Dh為當前幀的模板M與匹配目標T之間的漢明距離，Dh∈[0，7]，n=max(Dh+ 1)，即Dh的可能取值個數。α取值與當前幀匹配窗口與目標模版感知哈希序列的漢明距離成正比。Dh大，則M與T的差異大，跟蹤目標發生了一定的變化，T的權重α大；Dh小，則M與T差異小，跟蹤目標基本無變化，T的權重α小。將α = Dh/n代入式(8)得：

(9)

模板更新公式可根據當前幀模板M與匹配目標T間的漢明距離進行自適應調整。實驗結果表明，模板更新的自適應調節能夠良好地適應跟蹤目標的灰度或亮度變化，提高跟蹤的精度以及魯棒性。

2.3算法過程

整個實驗的算法過程如圖5所示。首先在輸入視頻中選取跟蹤目標，利用離散余弦變換DCT提取目標的低頻信息；通過圖像感知哈希增強生成跟蹤目標的哈希序列；在目標周圍區域進行掃描，通過比較漢明距離尋找感知哈希序列與跟蹤目標最接近的掃描窗口，也就是該幀的目標所在位置；最后為了適應目標的變化，在成功跟蹤后每一幀都要更新跟蹤的目標。

圖5　模板匹配跟蹤的哈希增強算法步驟

輸入：一組視頻序列，跟蹤目標的坐標

輸出：跟蹤結果的坐標

1) 輸入視頻序列，選取跟蹤目標I(x，y)；

2) 將I(x，y)轉化為灰度圖像G(x，y)，并根據式(2)計算離散余弦變換系數矩陣F(u，v)；

3) 選取F(u，v)左上角8×8矩陣f(x，y)，根據式(3)得到跟蹤目標的低頻分量g(x，y)；

4) 根據式(4)得到g(x，y)相鄰像素灰度差異值δg，根據式(5)得到g(x，y)每行像素與整體均值的差異δμ，之后根據式(6)得到模板的哈希序列H；

5) 根據式(7)計算模板哈希序列H與搜索區域內其他窗口圖像的哈希序列H′的哈希距離Dh，若得到哈希距離最小的窗口坐標，且Dh≤7，即為跟蹤目標的坐標，進行步驟6；若Dh>7，則結束跟蹤；

6) 將I(x，y)與Dh代入式(9)，得到更新后的模板I((x，y)，轉至步驟2。

3實驗與分析

為了驗證本文提出的模板匹配跟蹤的哈希增強算法的跟蹤效果，將其用于對人臉的跟蹤，與基于SSD和基于NCC的模板跟蹤方法比較。實驗一數據為自攝視頻序列，實驗二與實驗三數據源于Visual Tracker Benchmark的David視頻(https://sites.google.com/site/trackerbenchmark/benchmarks/v10)，包含存儲目標真實位置的groundtruth_rect.txt文件。

實驗環境：處理器Intel Core i7 2.10 GHz，內存4 GB RAM，顯卡NVIDIA NVS 5400M，開發軟件采用VS 2010和Windows 7系統，用到軟件開發庫為Opencv 2.4。

實驗一是對靜止背景下灰度亮度變化微小的目標跟蹤。在分辨率為640×480像素、背景穩定且光照不變的視頻序列中，跟蹤一張大小為193×179像素的移動人臉，選取第20、40、70和80幀作為參考，如圖6所示。可以看到，在視頻的前40幀三種方法都能較好地跟蹤目標；從第70幀起，SSD跟蹤產生了一定的偏移，而NCC與本文方法則能準確地跟蹤目標。相對于目標真實位置，平均每幀SSD模板跟蹤偏移30個像素，NCC模板跟蹤偏移16個像素，本文方法則僅偏移9個像素，可見NCC模板跟蹤與本文方法均能在靜止背景下良好地跟蹤灰度與亮度變化微小的目標。

圖6　靜止背景下三種算法跟蹤結果

實驗二是對復雜背景下灰度亮度變化劇烈的目標跟蹤。如圖7所示，視頻序列分辨率為640×480像素，背景保持變動并且光照變化明顯，一個面部尺寸為80×85像素的行人面對移動的手持攝像機快速地不規則走動，同時摘下眼鏡后再戴上，跟蹤目標的灰度與亮度均產生劇烈的變化。分別選取視頻序列的第30、110、167、311以及398幀作為參考，可以看到視頻前30幀三種方法均能準確地跟蹤目標，之后到110幀附近時SSD與NCC方法跟蹤已經產生偏移；從第167幀跟蹤目標開始摘下眼鏡起，到第311幀目標重新戴上眼鏡，SSD與NCC方法跟蹤的偏移量十分巨大，已經無法進行精確跟蹤；而本文方法從始至終十分精準地跟蹤目標。實驗二中SSD與NCC方法平均每幀偏移35與30個像素，跟蹤精度大幅降低，不能準確跟蹤目標；本文方法平均每幀偏移3個像素，能在復雜背景下精準地跟蹤灰度亮度變化劇烈的目標。

圖7　復雜運動情況下三種算法跟蹤結果

實驗三為室外場景下對運動目標的跟蹤。如圖8所示，頻序列分辨率為640×480像素，跟蹤場景為室外小路；跟蹤目標為慢跑的路人，大小為55×185像素。選取視頻序列的第40、78、165以及221幀進行比較，可以發現隨著時間的推移，SSD方法偏移量逐漸增大，到221幀時只能跟蹤住目標的半個身體；NCC方法能夠較為準確地跟蹤目標，但跟蹤窗口也逐漸偏移；本文方法則自始至終能夠精確地跟蹤目標。相對于目標真實位置，平均每幀SSD模板跟蹤偏移37個像素，NCC模板跟蹤偏移11個像素，本文方法則僅偏移8個像素，可見本文方法能在室外背景下良好地跟蹤運動的目標。

圖8　室外場景下三種方法目標跟蹤結果

通過手工獲取實驗一視頻中目標真實位置，實驗二與實驗三視頻中目標真實位置從groundtruth_rect.txt文件得到。表1中陳列了三種方法跟蹤的目標與目標真實位置的平均差與標準差，三種方法的跟蹤速度則在表2中可見。

表1　三種算法跟蹤的平均差與標準差(像素)

表2　三種算法跟蹤的平均匹配時間

從表1能夠看出，本文提出的哈希增強方法跟蹤精度高于SSD與NCC方法，擁有距目標真實位置最小的平均差與標準差，跟蹤精度比SSD與NCC方法高出一個數量級。通過分析表2發現，哈希增強方法的運行速度與SSD方法接近，高于NCC方法，能滿足實時性跟蹤的要求。綜合兩種因素考慮，本文提出的哈希增強方法表現最為優異。

4結語

傳統基于灰度值的模板跟蹤算法對圖像的灰度與光照變化極為敏感，影響了跟蹤的適用范圍和效果。針對以上缺點，本文提取跟蹤目標的低頻信息，運用哈希增強的方法生成跟蹤目標的哈希序列；計算哈希序列的漢明距離匹配跟蹤目標，并使模板自適應更新。經實驗證明，本文算法有效克服了目標灰度與光照變化對圖像均值帶來的影響，達到更好的跟蹤效果。圖像的整體結構保持不變，其計算出的感知哈希序列就不會變化，增強了對跟蹤目標灰度亮度變化的適應性，提高了跟蹤精度。若跟蹤目標整體結構變化，跟蹤精度會有所下降，速度也會有所下降，解決這些問題是今后研究的方向。

參考文獻

[1] Singh R,Purwar R K,Rajpal N.A better approach for object tracking using dual-tree complex wavelet transform[C]//2011 International Conference on Image Information Processing (ICIIP 2011),2011:1-5.

[2] Qi Zhang,Jinlin Zhang,Ting Rui.Target Tracking Based on Wavelet Features in the Dynamic Image Sequence[C]//2011 Sixth International Conference on Image and Graphics (ICIG),2011:811-815.

[3] Haopeng Li,Flierl M.Sift-based multi-view cooperative tracking for soccer video[C]//2012 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP),2012:1001-1004.

[4] Kai Du,Yongfeng Ju,Gang Li,et al.Object tracking based on improved MeanShift and SIFT[C]//2012 2nd International Conference on Consumer Electronics,Communications and Networks(CECNet),2012:2716-2719.

[5] Cho H J,Park T H.Template Matching Method for SMD Inspection using Discrete Wavelet Transform[C]//2008 SICE Annual Conference,2008:3198-3201.

[6] Qiang Zhu,Kwangting Cheng,Hongjiang Zhang.SSD Tracking Using Template and Log-polar Transformation[C]//Fifth International Conference on Multimedia and Exposition,2004:723-726.

[7] Sahani S K,Adhikari G,Das B K.A Fast Template Matching Algorithm for Aerial Object Tracking[C]//2011 International Conference on Image Information Processing (ICIIP 2011),2011:1-6.

[8] Di Caterina G,Soraghan J J.Adaptive Template Matching Algorithm Based on SWAD for Robust Target Tracking[J].Electronics Letters,2012,48(5):261-262.

[9] Hager G D,Dewan M,Stewart C V.Multiple Kernel Tracking with SSD[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2004:790-797.

[10] Schreiber D.Robust Template Tracking with Drift Correction[J].Pattern Recognition Letters,2007,28(12):1483-1491.

[11] Zhen Jia,Balasuriya A,Challa S.Target Tracking with Bayesian Fusion Based Template Matching[C]//2005 International Conference on Image Processing (ICIP 2005),2005:826-829.

[12] 任仙怡,廖云濤,張桂林,等.一種新的相關跟蹤方法研究[J].中國圖象圖形學報,2002,7(6):553-557.

[13] 朱永松,國澄明.基于相關系數的相關跟蹤算法研究[J].中國圖象圖形學報,2004,9(8):963-967.

[14] Venkatesan R,Koon S M,Jakubowski M H,et al.Robust Image Hashing[C]//2000 International Conference on Image Processing (ICIP 2000),2000:664-666.

[15] 牛夏牧,焦玉華.感知哈希綜述[J].電子學報,2008,36(7):1405-1411.

收稿日期：2015-01-13。國家自然科學基金項目(41161061，4090 1197)。徐珩，碩士生，主研領域：圖像模式識別。賀飛越，碩士生。

中圖分類號TP391.41

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.039

HASH ENHANCEMENT ALGORITHM FOR TEMPLATE MATCHING TRACKING

Xu HengHe Feiyue

(FacultyofLandResourceEngineering,KunmingUniversityofScienceandTechnology,Kunming650093,Yunnan,China)

AbstractTraditional template matching tracking algorithms based on sum of squared difference (SSD) and normalised cross-correlation (NCC) depend on grey information very much. In circumstance of dramatic greyscale change or significant illumination intensity variation in image, they are prone to be affected by high-frequency information of the image and this leads to the phenomenon of target drifting followed by the decrease in tracking accuracy. We proposed a hash enhancement algorithm for template matching tracking used to reduce the impacts of greyscale and luminance variations, and to enhance the tracking accuracy as well. The specific progress is as follows: It extracts the perceptual features of the target with perceptual hashing, and binarises the extracted features to generate hash string of the tracking targets. Then it saves the hash string as a template of matching tracking, by comparing the hamming distances it searches the most similar targets from each frame so as to reach the effect of tracking. By using drawer principle it shortens the time of hamming distances comparison. We also proposed a hamming distance-based adaptive model updating algorithm which guarantees the continuity of tracking. Comparing the results of simulative experiments with SSD-based and NCC-based template tracking algorithms, the matching accuracy reaches an order of magnitude higher in the case of target’s greyscale and luminance varying. What’s more, the tracking speed is able to meet the requirement of real-time property.

KeywordsHash enhancementTemplate matchingTarget trackingHamming distance