采用多特征共生矩陣的模板匹配

江蘇蓬，向 偉，劉云鵬，羅海波*

（1.中國科學院 沈陽自動化研究所，遼寧 沈陽110016；2.中國科學院 機器人與智能制造創新研究院，遼寧 沈陽110169；3.中國科學院大學，北京100049；4.中國科學院 光電信息處理重點實驗室，遼寧 沈陽110016；5.遼寧省圖像理解與視覺計算重點實驗室，遼寧 沈陽110016）

1 引 言

模板匹配是計算機視覺領域一個非常經典的問題，該技術在地圖與地形匹配、生理病變檢測、指紋識別等領域中都有著非常重要的應用價值［1-2］。模板匹配是通過使用特定的算法在目標圖像中尋找與模板圖像特征內容最為相似的區域。但在實踐過程中，由于圖像拍攝時間、角度、環境的不同使得目標圖像中目標區域與模板圖像會存在一定的差異。這些不確定因素所造成的復雜場景（如光照變化、背景變化、遮擋、剛性以及非剛性形變等）會為模板匹配技術帶來極大的挑戰。如何實現復雜場景下的成功匹配就成為當前模板匹配算法的研究重點之一。

相似性度量是模板匹配算法的核心，傳統的模板匹配算法通常采用直接對圖像中的所有像素點進行逐像素匹配計算（如：差值平方和（SSD）、絕 對 誤 差 和（SAD）、歸 一 化 互 相 關（NCC）等）。這類算法雖然運算過程簡單，但由于其面向所有特征點施加距離計算，對目標物體沒有針對性，所以對背景變化非常敏感。并且當模板圖像與目標圖像之間存在非剛性形變、遮擋等復雜變換時，匹配精度會大幅度下降。

此外，大多數的模板匹配算法需要在模板圖像和目標圖像之間建立一個特定的幾何參數模型，也就是說在其假定的幾何參數模型成立時，匹配效果會非常好，但當異常值存在時就容易出錯。這也使得這類算法只能解決某一類場景問題，從而限制了算法的適用范圍。所以在復雜場景下，使用傳統的模板匹配算法通常難以匹配到正確區域。

在對最新的模板匹配算法的研究中發現，Dekel等人［3］提出了一種可在無約束環境下進行匹配的最佳點對相似性算法BBS（Best-Buddies Similarity），其核心思想是判斷每一對像素點對是否互為最近鄰點對，并將最近鄰點對數量最多最密集的地方視為最終匹配區域。這種方法對大多數的離群點具有很強的魯棒性，可以在一定程度上克服復雜場景變化所帶來的影響［4］。此后，國內學者王剛等人用曼哈頓距離代替歐氏距離并對置信度圖進行閾值篩選和濾波，進一步提高了BBS算法的匹配精度［5］。但由于查找互為最近鄰點對的計算成本較大，耗時較長，Talmi等人對其進行了改進，提出了可變形差異相似性算法DDIS（Deformable Diversity Similarity）。該方法引入兩個關鍵思想：一是采用單向近似最近鄰代替雙向互為最近鄰的方式來減少計算量，提高算法實時性；二是考慮最近鄰域的形變，復雜場景下匹配精度更高［6］。但由于DDIS在原有最近鄰匹配的基礎上增加了空間形變量的計算，使得該方法在模板尺寸較大的情況下需要更長的運行時間。國內學者逯睿琦等人在DDIS算法的基礎上添加空間金字塔模型，并且在不同尺度下提取模板圖像點的顯著性區域，讓其更加關注目標物體本身，從而提高算法的抗遮擋和背景變化的能力［7］。Talkor等人提出的DIWU（Deformable Image Weighted Unpopularity）算法同樣選取最近鄰點對作為相似性度量，不同于以上方法需要每一個滑動窗口進行最近鄰匹配，該方法一次性針對整幅圖像進行最近鄰點對計算，并以第一個窗口的匹配分數為基礎通過位置差迭代計算其余窗口得分，該方法可在不降低匹配精度的基礎上實現算法加速［8］。

BBS與DDIS是以計算最近鄰點對為相似性度量，通過圖像塊之間的相似性來解決復雜場景下的匹配問題，但這種相似性度量方法只考慮了圖像的局部信息，當目標物體（前景）與背景之間對比度較低時（如目標過小、目標與背景顏色相似、背景過于雜亂），或發生大面積遮擋、劇烈非剛性形變等情況時，匹配精度會下降；當同時包含多種復雜場景時，則很難匹配到正確區域。此外，傳統的模板匹配算法通常只提取一種圖像特征，這樣很難捕獲到足夠的圖像信息。針對這些問題，本文提出了以共生矩陣［9-11］作為相似性度量的模板匹配方法，通過統計圖像特征共生矩陣信息來收集全局信息；并采用多特征融合的方法將顏色特征、HOG特征、深度特征相結合從而實現多方位的圖像特征信息提取。

綜上所述，本文利用共生矩陣從多特征融合所獲取的大量數據中學習圖像之間的相似性，能夠很好的對抗光照變化、背景雜亂、幾何形變、遮擋等復雜情況。與BBS和DDIS算法相比，匹配精度等高、算法魯棒性更強。

2 基本原理

Hseu等人在1999年首次提出了利用共生矩陣進行模板匹配的思想，但當時只考慮了灰度圖像和二維平移的簡單情況［9］。通過對共生濾波器的研究發現，共生矩陣可以捕獲圖像的紋理屬性而不是像素值之間的直接差異，從而隱式地表達一定的紋理相似性［12］。通過捕獲并統計全局的共生信息可以得到每一個候選窗口的共生分數，我們認為來自相同紋理屬性區域的圖像可以獲得較好的共生分數［11］。本節中我們會對共生矩陣進行介紹，以及如何實現多特征融合下的模板匹配。

2.1 共生矩陣

定義一個共生矩陣C如公式（1）所示，C(a，b)表示在圖像中，像素值p，q同時出現的總次數，并根據像素之間的空間位置關系賦予不同的權重。

其中：p，q分別表示兩像素點在圖像中的位置，Ip，Iq則表示該位置上的像素值，δ是根據模板圖像大小而變化的自適應參數，Z代表歸一化因子。方括號中為判斷函數，若p位置的像素值等于a，則方括號值等于1，反之為0。

從上述公式中可以發現共生矩陣是一個對稱矩陣，其對角線上的元素為其自身像素在圖中出現的次數，而共生矩陣的求解實質上就是遍歷圖像修改權重累計求和的過程。通過共生矩陣我們可以了解到兩個像素值在同一區域內共同出現的概率。但共生矩陣有一個弊病，它會突顯經常出現的像素值所做的貢獻卻忽略那些不經常出現的像素值，而所忽略的這一部分也有可能是模板中的關鍵信息。所以我們借用機器學習中用于衡量兩個對象之間相關性的點互信息PMI來解決這一問題。PMI的基本原理如下：

根據概率論可知：若x，y不相關，則PMI(x，y)=0；若x，y相關，則x，y相關性越大，則PMI(x，y)越大，其中的log是取自于信息論中的概率量化轉換。根據這一原理，我們將共生矩陣C(a，b)除以其先驗概率h(a)，h(b)以獲得共生互信息矩陣。

圖1 共生互信息矩陣可視化Fig.1 Visualization of co-occurrence mutual information matrix

2.2 特征選取

圖像的特征提取是圖像處理過程中的關鍵一步，對后續的匹配計算有著重要的影響。本文選擇了3種常用的圖像特征：顏色特征、HOG特征、深度特征，它們分別表征了圖像的3類不同特征屬性。下文將對它們進行逐一說明。

2.2.1 顏色特征

顏色特征是一種通過像素值大小描述圖像中景物表面性質的全局特征，由于其數據量小，便于查找且觀感強烈，使得顏色特征成為圖像處理領域最常用的圖像特征。但因其對圖像區域的大小、方向、空間位置等信息缺乏敏感性，所以本文選擇將其與其它圖像特征結合使用。

常用的顏色空間有RGB、HSV、Lab等。其中，HSV不適合在光照模型中使用，Lab顏色空間色域最大，且不依賴于光線，能有效避免顏色損失；在計算同等精度時，運行速度不遜于RBG模式。所以本文選取Lab作為算法采用的顏色空間。

2.2.2 HOG特征

梯度方向直方圖（HOG）最早由Dalal等人在2005年提出，常用于行人檢測，很少有人將其應用于模板匹配中，本文嘗試利用其所捕獲的結構輪廓信息來增強匹配的可靠性。HOG特征主要通過劃分cell和block的方法來計算局部像素點之間的梯度方向與梯度強度分布。對于圖像來說，梯度即為像素值變化最快的方向，由于圖像的邊緣與梯度是垂直關系，所以圖像的局部邊緣輪廓特征能被梯度的方向密度分布很好地描述。HOG作為一種對邊緣形狀和梯度非常敏感且能夠高效捕獲圖像邊緣信息的算子，在對圖像進行檢測時它能夠對位置與方向空間進行量化從而削弱圖像位置變化帶來的影響，所以HOG特征對幾何形變與光照變化都能保持良好的不變性。HOG特征的提取主要分為5個步驟：圖像預處理、計算圖像梯度、梯度方向統計、重疊塊特征標準化、生成特征向量。圖2為HOG特征提取的直觀流程圖。

圖2 HOG特征提取Fig.2 HOG feature extraction

2.2.3 深度特征

圖像的顏色特征和HOG特征只是提取物體的表面特征（淺層特征），而通過深度學習的自主學習能力能夠幫助我們尋找圖像數據背后的規律，捕獲更加本質的圖像深層特征。本文利用卷積神經網絡CNN來提取圖像的深度特征，CNN的局部感知、池化以及參數共享特性能夠有效減少參數，降低機器負載加快運行速度。本文使用當 下 流 行 的VGG19網 絡 模 型［13-14］，選 取 來 自conv1_2，conv3_4和conv4_4三個卷積層輸出的特征圖。我們對得到的特征圖進行歸一化處理，之后再通過雙線性插值的方法縮放到原始圖像大小。

2.3 多特征融合

不同的圖像特征可以表征不同的圖像信息，而得到的圖像信息越多對模板匹配就越有利［15］，所以我們想到通過特征融合的方法將3種圖像特征進行整合，提供更加完備的圖像信息，從而提高匹配算法的準確性和魯棒性［16］。

多特征融合需要經歷特征提取、特征串聯、PCA降維以及k-means聚類四個步驟。首先將所提取的3種圖像特征進行特征串聯（本文為等比例），但是這樣做會加大特征空間的維數導致后續的分類困難，同時也可能會包含一些無關或冗余的信息。為了降低特征維度減少計算的復雜度，同時減少無用信息，消除特征之間的相關性，需要對串聯后的特征進行特征抽取。本文采用主成分分析法（PCA）來解決這一問題，通過用較少的主成分來表示特征以實現特征降維［17］。研究發現，當貢獻率等于0.95時能夠達到最好的匹配效果，在降低特征空間維度保證匹配算法實時性的同時盡量減少信息損失保證匹配精度。

如果圖像匹配算法只考慮一般的256級灰度圖像，那所得的共生互信息矩陣M的大小就為256×256，假設采用的是三通道的彩色圖像，則的大小將變成256×256×3，這使得矩陣M將過大而無法進行應用。所以PCA降維后的特征仍無法直接用于匹配計算，還需要進行分類量化。本文采用k-means聚類［18］算法將圖像特征分為k個簇類（本文中k=256），此時M矩陣的大小為k×k。

2.4 圖像匹配

圖3 為本文算法的流程圖，經過圖像預處理、多特征提取與融合后，我們將圖像特征量化為k個簇類，通過求解共生矩陣C（如公式1）來統計每個簇類對在目標圖像中共同出現的次數，之后通過計算共生互信息矩陣M（如公式3）來體現每個簇類對的共現概率。最后采用共生統計的方法來求解給定模板T與候選區τ?I的匹配概率。

圖3 算法流程圖Fig.3 Algorithm flow chart

3 實驗結果與討論

本文在Dekel等人建立的公共數據集上進行了實驗評估［19-20］，該數據集是從OTB數據集中選擇35個標準彩色視頻序列，通過恒定幀差[f，f+20]進行采樣（f為隨機選?。?，每個視頻截取3對圖像，總共采集105對模板圖像。每一對圖像的第一幅作為參考圖像用于提取模板，第二幅圖像作為待匹配的目標圖像，所得到的圖像數據集涵蓋各種各樣的挑戰：復雜的幾何形變，光照變化，尺度差異，旋轉，局部遮擋等。下面從定量分析與定性分析兩方面對本文的實驗結果進行評估。

3.1 定量分析

我們借鑒目標跟蹤中常用的準確率度量方法，將實驗的檢測結果與預測真值框之間的重疊率視為衡量匹配成功與否的度量標準：

其中：|?|表示一個區域的像素點的個數，Rest代表實驗測試結果區域，Rtruth代表人工事先標定的預測真值區域。

算法1基于多特征共生矩陣模板匹配算法Algorithm 1 Template matching algorithm based on multi-feature co-occurrence matrix

BBS算法與DDIS算法都只是單一的使用顏色或者深度特征進行圖像匹配，這種方法得到的圖像信息較少，使得算法在一些復雜場景下容易發生匹配失敗。并且它們都沒有考慮到目標的局部結構和整體輪廓特征，所以我們嘗試加入HOG特征以彌補這一不足。本文通過將顏色特征、HOG特征和深度特征三者進行特征融合來獲取更多的圖像信息增強算法的可靠性。我們將本文算法與目前一些匹配效果較好的模板匹配算法進行了性能對比，進行比較的算法有：DDIS，BBS，SSD，NCC，SAD以及HM（顏色直方圖匹配算法）?？紤]到深度特征的特征空間維度較大，普通算法采用深度特征很難達到匹配實時性要求，所以在對比實驗中我們只對DDIS算法分別采用了深度特征（DDIS-D）和顏色特征（DDIS-C），其余算法均使用顏色特征。通過對105組圖像進行匹配實驗，根據實驗結果繪制了成功率曲線圖并計算了曲線下面的面積（AUC）。

表1 中展示了各種算法的AUC，圖4中展示各種算法的成功率曲線。通過對比計算可以發現，本文算法的AUC值為0.6586，相比于目前最好的幾種模板匹配算法DDIS-D、DDIS-C、BBS分別提高了7.88%，8.14%，20.16%，并且明顯優于其它傳統的模板匹配算法。實驗結果證明了采用特征融合的方法比簡單地使用單一特征能夠獲得更好的匹配結果。

表1 不同模板匹配算法的AUC得分Tab.1 AUC score of different template matching algorithms

圖4 不同模板匹配算法的成功率曲線Fig.4 Success rate curves of different template matching algorithms

不同于BBS算法和DDIS算法需要對最近鄰進行搜索查找，本文采用通過求解共生矩陣來對圖像特征進行共生信息統計，算法原理簡單且易于實現。本文在電腦配置為8GB RAM、i7-7500CPU環境下分別對105組圖像進行實驗，對基于共生矩陣的匹配核心算法進行運行時間統計，其中匹配平均耗時為1.934 8 s，最短耗時為0.147 5 s，最長耗時為6.899 7 s。而BBS與DDIS算法的匹配耗時受模板尺寸影響下較大，當模板圖像較大時，匹配耗時可達百秒以上。

3.2 定性分析

通過對比實驗結果，我們選取了6組具有代表性的匹配結果（如圖5），這6組圖像包含了常見的一些具有挑戰性的復雜場景：幾何形變、近似目標區域干擾、背景雜亂、光照變化、局部遮擋、目標對象過小等；且一般為幾種復雜情況同時存在。圖5中的前兩列分別代表模板圖像和待匹配圖像，后4列則表示各種算法的置信度圖。從匹配結果上看（綠色為真值框、紫色框為本文算法匹配結果），DDIS算法只能成功匹配上很少一部分，BBS算法全部以失敗告終，而我們的算法能夠成功匹配到正確目標位置。從置信度圖上對比可以發現，本文算法的置信度圖是非常干凈的，并且在正確位置上具有非常強烈的響應。由此可見，在這些復雜的場景下本文算法匹配成功率更高、算法的魯棒性更強。

圖5 不同模板匹配算法匹配結果Fig.5 Results on different template matching algorithms

4 結 論

鑒于傳統的基于相似性信息統計的模板匹配算法未能充分利用各類圖像特征信息，且在多種復雜情況共存的場景下算法匹配精度較低這一缺點，本文提出了一種基于共生矩陣的多特征融合模板匹配算法。提取圖像的顏色特征、HOG特征與深度特征進行，并通過PCA與Kmeans算法對圖像特征進行降維分類實現特征融合，從而捕獲更充足的局部特征信息，再通過對共生矩陣進行信息統計的方法得到全局信息共生得分，從而將高分數區域作為模板匹配結果。本文算法的AUC得分為0.658 6，較目前較好的幾種模板匹配算法都有較好提升。且該算法能夠適應更為復雜的匹配場景，算法的魯棒性更強，匹配精度更高。但是本文的算法仍然存在一定的局限性，當匹配的目標存在明顯的尺度變換時，我們的方法有可能失敗，這也是我們下一步努力的方向。