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

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

（1.中國科學(xué)院 沈陽自動(dòng)化研究所，遼寧 沈陽110016；2.中國科學(xué)院 機(jī)器人與智能制造創(chuàng)新研究院，遼寧 沈陽110169；3.中國科學(xué)院大學(xué)，北京100049；4.中國科學(xué)院 光電信息處理重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽110016；5.遼寧省圖像理解與視覺計(jì)算重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽110016）

1 引 言

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

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

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

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

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

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

2 基本原理

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

2.1 共生矩陣

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

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

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

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

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

2.2 特征選取

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

2.2.1 顏色特征

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

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

2.2.2 HOG特征

梯度方向直方圖（HOG）最早由Dalal等人在2005年提出，常用于行人檢測(cè)，很少有人將其應(yīng)用于模板匹配中，本文嘗試?yán)闷渌东@的結(jié)構(gòu)輪廓信息來增強(qiáng)匹配的可靠性。HOG特征主要通過劃分cell和block的方法來計(jì)算局部像素點(diǎn)之間的梯度方向與梯度強(qiáng)度分布。對(duì)于圖像來說，梯度即為像素值變化最快的方向，由于圖像的邊緣與梯度是垂直關(guān)系，所以圖像的局部邊緣輪廓特征能被梯度的方向密度分布很好地描述。HOG作為一種對(duì)邊緣形狀和梯度非常敏感且能夠高效捕獲圖像邊緣信息的算子，在對(duì)圖像進(jìn)行檢測(cè)時(shí)它能夠?qū)ξ恢门c方向空間進(jìn)行量化從而削弱圖像位置變化帶來的影響，所以HOG特征對(duì)幾何形變與光照變化都能保持良好的不變性。HOG特征的提取主要分為5個(gè)步驟：圖像預(yù)處理、計(jì)算圖像梯度、梯度方向統(tǒng)計(jì)、重疊塊特征標(biāo)準(zhǔn)化、生成特征向量。圖2為HOG特征提取的直觀流程圖。

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

2.2.3 深度特征

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

2.3 多特征融合

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

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

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

2.4 圖像匹配

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

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

3 實(shí)驗(yàn)結(jié)果與討論

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

3.1 定量分析

我們借鑒目標(biāo)跟蹤中常用的準(zhǔn)確率度量方法，將實(shí)驗(yàn)的檢測(cè)結(jié)果與預(yù)測(cè)真值框之間的重疊率視為衡量匹配成功與否的度量標(biāo)準(zhǔn)：

其中：|?|表示一個(gè)區(qū)域的像素點(diǎn)的個(gè)數(shù)，Rest代表實(shí)驗(yàn)測(cè)試結(jié)果區(qū)域，Rtruth代表人工事先標(biāo)定的預(yù)測(cè)真值區(qū)域。

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

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

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

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

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

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

3.2 定性分析

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

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

4 結(jié) 論

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