三種典型模板匹配算法性能比較

吳成茂， 郭 銳

(西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

三種典型模板匹配算法性能比較

吳成茂， 郭 銳

(西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

為了在圖像識別、配準(zhǔn)和拼接等具體問題中能夠針對不同條件來合理選取適當(dāng)?shù)钠ヅ渌惴?，詳?xì)介紹三種典型模板匹配算法，即基于索引表的圖像匹配算法、基于圖像相關(guān)性的圖像匹配算法和序貫相似性檢測算法(SequentialSimilarityDetectionAlgorithm，SSDA)，并從實時性、魯棒性和精確性等角度出發(fā)，對其匹配性能進(jìn)行差異分析。采用分組實驗的方法對匹配算法的各項性能指標(biāo)進(jìn)行測試和比較，結(jié)果表明，三種算法都具有良好的精確性，其中基于索引表的算法和序貫相似性檢測算法具有較好的實時性，而基于圖像相關(guān)性的算法在噪聲環(huán)境下具有良好的魯棒性。

模板匹配；性能比較；實時性；魯棒性；精確性

伴隨著計算機科學(xué)技術(shù)的發(fā)展，圖像匹配已經(jīng)成為圖像信息處理領(lǐng)域中不可或缺的一項重要技術(shù)，其應(yīng)用已從最早的軍事領(lǐng)域逐漸擴大到遙感監(jiān)測、地理測繪、導(dǎo)航制導(dǎo)[1]、醫(yī)療診斷、機器人視覺、圖像三維重構(gòu)[2]以及雷達(dá)圖像模板跟蹤[3]等各項軍事及民用領(lǐng)域。將匹配算法應(yīng)用在高分辨率遙感圖像中，有助于更好地獲取地理信息，準(zhǔn)確實現(xiàn)目標(biāo)定位與識別等，具有重要的軍用和民用價值，然而，實際應(yīng)用卻因為算法的檢索策略、魯棒性的差異以及外界環(huán)境的影響等，有時會導(dǎo)致匹配效果不理想。為了提高工作效率，并在噪聲環(huán)境下獲得較為理想的匹配效果，從眾多的算法中根據(jù)實際情況來選取適當(dāng)?shù)膱D像匹配算法是十分必要的。

本文從魯棒性，實時性和精確性三個方面來分析比較基于圖像相關(guān)性的算法[4]，基于索引表的算法[5]以及序貫相似性檢測算法(Sequential Similarity Detection Algorithm，SSDA)[6-7]三種匹配算法的性能，通過對算法的思想進(jìn)行理論分析并用Matlab進(jìn)行實驗仿真，根據(jù)實驗結(jié)果對三種算法的性能進(jìn)行比較和評述，從而服務(wù)于今后在實際應(yīng)用中匹配算法的適當(dāng)選取。

1 模板匹配算法描述

先介紹三種典型的圖像匹配算法，它們是基于索引表的算法，基于圖像相關(guān)性的算法和序貫相似性檢測算法(SSDA)，并對這三種算法的思想和步驟進(jìn)行詳細(xì)描述。

1.1 基于索引表的圖像匹配算法

給出一幅圖像，其矩陣表示如圖1所示。

圖1 圖像矩陣

根據(jù)圖像矩陣構(gòu)建圖像索引表[4]。先將矩陣中的每個元素，即圖像像素的灰度值列舉出來, 再依次將灰度值與之相等的元素的坐標(biāo)放在該灰度值所在的行中。

與原圖像相關(guān)的索引表如圖2所示。構(gòu)造索引表的時間復(fù)雜度為O(n2)，其中n為圖像的寬度(或長度)。

圖2 圖像索引表

模板的圖像矩陣如圖3所示,而圖1所示即為待匹配的圖像。

圖3 模板圖像矩陣

在最差情況下，即需經(jīng)過最多次的匹配才得到匹配結(jié)果，此時的時間復(fù)雜度為O(m2)，其中m為模板的寬度(或長度)。

引入邊界概念，不僅列舉出與模板中像素灰度值完全相等的元素，而且設(shè)置一個邊界值，將與模板中第一個像素的灰度值相差在邊界值范圍內(nèi)的待匹配像素都列舉出來。例如，設(shè)置邊界值為10,列舉符合邊界條件的待選圖像矩陣，如圖4所示。

圖4 待選圖像矩陣

引入懲罰數(shù)概念，當(dāng)已選出待選匹配方案后，待選圖像的下一像素的灰度值和模板中相應(yīng)的像素灰度值相差超過邊界值的范圍時，懲罰數(shù)加1；若未超過邊界值，則懲罰數(shù)保持不變，然后再與下一個比較，直到遍歷模板中的所有元素后，得到懲罰數(shù)表，如圖5所示。

圖5 懲罰數(shù)表

在遍歷模板中所有元素后，選取懲罰數(shù)累加和最小的項。從圖5的懲罰數(shù)表中容易看出，圖4中以點(1,2)為起始點的待選圖像是最優(yōu)解。圖6中的深色陰影部分就是待匹配圖像中與模板相符的圖像。

圖6 匹配結(jié)果

1.2 基于圖像相關(guān)性的圖像匹配算法

首先考慮一個3×3的參考圖像Ir，待匹配的目標(biāo)圖像為It。參考圖像矩陣Ir的中心點Ir(x,y)，坐標(biāo)為(x,y)，如圖7所示[3]。

圖7 3×3圖像矩陣

當(dāng)評估矩陣中相鄰像素的順序一致性時，需要對每個像素跟與它相鄰的其他8個像素間進(jìn)行計算，即共有72個像素對。為了簡化運算，現(xiàn)只考慮水平和垂直方向的像素對，如圖7所示，僅有18個像素對。分別定義Ir(x,y)的水平與垂直的左差值為

(1)

(2)

Ir(x,y)的水平與垂直的中心差值為

(3)

(4)

φ(x,y)=

(5)

在實際應(yīng)用中，將上述的方法擴展到一個大小為M×N的區(qū)域中，然后逐點計算區(qū)域中的每一個元素的φ(x,y)。為了不重復(fù)運算，對于每一個像素，僅需計算其水平方向的左差值與中心差值，以及垂直方向的左差值與中心差值，即將之前的18次運算縮減為4次運算。由此，在大小為M×N的區(qū)域中，從點(x1,y1)開始的參考圖像和與其相對應(yīng)的從位置點(x2,y2)開始的目標(biāo)圖像，二者的匹配函數(shù)為四個相關(guān)量的和,即

(6)

其中

(d∈{v,h},s∈{l,c})。

(7)

最后采用歸一化步驟，將Φ(x1,y1,x2,y2)除以其各項的范數(shù)，得

ΦN(x1,y1,x2,y2)=

(8)

其中

‖R(x1,y1)‖=

(9)

‖T(x2,y2)‖=

(10)

(11)

1.3 序貫相似性檢測算法

序貫相似性檢測算法[7]是對傳統(tǒng)模板匹配算法的改進(jìn)。設(shè)待匹配圖像S大小為N×N，匹配的模板T大小為M×M，Si,j為模板覆蓋下的搜索子圖，其中(1

定義絕對誤差

ε(i,j,mk,nk)=|Si,j(mk,nk)-

(12)

(13)

(14)

選取一個固定閾值Tk。在搜索子圖Si,j中隨機抽取像素點，計算其與T中所對應(yīng)點的誤差值ε，再把該點的差值跟其它點對的差值累加，經(jīng)R次累加后，誤差超過閾值Tk時，停止并記錄累加的次數(shù)R，在這里將SSDA的檢測曲面定義為

I(i,j)=

(15)

若計算不超過Tk，則繼續(xù)計算(i,j)處的下一個隨機點的誤差值，直至超過了閾值Tk，記錄下次數(shù)。

當(dāng)I(i,j)取到最大值時，將其坐標(biāo)(i,j)作為匹配點，即最終匹配結(jié)果。在該點上需很多次累加才能使得總誤差超過選定的閾值。

2 算法性能及復(fù)雜性分析

根據(jù)三種算法各自的特點，分別分析它們的性能和復(fù)雜性。

2.1 索引表算法分析

基于索引表的圖像匹配算法的性能從很大程度上來說，是取決于對邊界值(相當(dāng)于閾值)的選取。當(dāng)邊界值選取較大時，匹配時抗噪性得到提高，但會額外增加計算量；而當(dāng)邊界值取得過小時，雖然提高了匹配速度，但若圖像中存在噪聲干擾，就可能得不到匹配結(jié)果或者得到錯誤的最優(yōu)值。因此，根據(jù)待匹配圖像的大小、紋理復(fù)雜程度等情況并通過調(diào)試來選取適當(dāng)?shù)倪吔缰?，會增強算法對?yīng)用環(huán)境的適應(yīng)能力，提高算法的魯棒性。

若模板大小為m×m，在最糟糕的情況下，即需經(jīng)過最多次匹配，遍歷模板中的所有元素才能得到匹配結(jié)果，此時算法的時間復(fù)雜度為O(m2)。由于本算法中的懲罰數(shù)的計數(shù)步驟均為加法運算，運算量較小，所以具有較高的運行效率。

2.2 相關(guān)性算法分析

基于相關(guān)性的圖像匹配算法在傳統(tǒng)的基于絕對差和(SAD)以及基于平方差和(SSD)的算法基礎(chǔ)上，結(jié)合了歸一化互相關(guān)方法(NCC)和零均值歸一化互相關(guān)方法(ZNCC)的思想，利用其相對抗噪能力強的特點，降低了外界因素對匹配的影響，提高了算法的抗噪性。在不同的光照及噪聲條件下，基于相關(guān)性的算法，表現(xiàn)出良好的魯棒性和精確性；ZNCC的匹配效果要遜色于相關(guān)性算法；而傳統(tǒng)的NCC和SSD在光照變化較大的情況中，效果十分不理想?，F(xiàn)已有學(xué)者提出了基于NCC的加權(quán)算法(WNCC)[12]，其對二值化閾值的敏感性較小，具有一定抗噪性，但其計算量較大，每一次循環(huán)運算都需要執(zhí)行數(shù)次累加、求平方以及求平方差運算等，因此運行效率較低。

2.3 序貫相似性檢測算法分析

SSDA算法是對傳統(tǒng)匹配策略的改進(jìn)，通過隨機選取像素和設(shè)定閾值來快速的丟棄不匹配的點，減少計算量從而提高效率，算法簡單也容易實現(xiàn)。然而傳統(tǒng)SSDA算法并不具備較強的抗噪能力，為提高其魯棒性，可采用如下方法對噪聲進(jìn)行預(yù)處理：計算每個待匹配區(qū)域中第k點的誤差ε(i,j,mk,nk)，與定義的閾值Tk進(jìn)行比較，若大于Tk，則認(rèn)為誤差由噪聲引起，丟棄該結(jié)果，不加入誤差總和中，并對該噪聲點計數(shù)，若待匹配區(qū)域內(nèi)噪聲點個數(shù)大于定義的閾值，停止運算并記錄次數(shù)；若第k點誤差小于Tk，認(rèn)為誤差并非由噪聲引起，仍使用傳統(tǒng)SSDA算法。這種改進(jìn)方法通過設(shè)置閾值進(jìn)行預(yù)處理，以此提高SSDA的魯棒性。

此外，盡管SSDA算法通過隨機選取像素點減小了運算量，但由于閾值Tk選定后，仍需對誤差ε進(jìn)行累加直至超過Tk。為減少運算量，可利用序列代替原先的固定閾值，并采用隔點采樣及粗匹配結(jié)合精確匹配等方法[12]降低運算量，進(jìn)一步提高原算法的運算效率。

3 仿真測試與分析

實驗選用的計算機配置為Intel Core(TM)2 Duo CPU E7300 2.66GHz，2.98GB內(nèi)存，Windows XP系統(tǒng)，實驗使用的編譯工具為Matlab 7.0.1。選取三組圖像，即標(biāo)準(zhǔn)Lena圖像、指紋圖像和遙感圖像，進(jìn)行試驗仿真，以比較各算法的性能，即匹配準(zhǔn)確度、匹配運算的實時性和魯棒性。

觀察匹配點的位置，對于Lena圖像和指紋圖像，若匹配誤差在2個像素內(nèi)，則視為匹配成功；對于遙感圖像，若匹配誤差在5個像素內(nèi)，視為成功。記下匹配點位置，經(jīng)過20次匹配計算平均成功率。至于匹配運算的實時性，主要指圖像匹配耗時，在實驗中也通過20次運算取平均值。關(guān)于魯棒性的試驗，是對原圖像和模板圖像都加上在Matlab參數(shù)中均值為0，方差分別取0.01，0.05和0.1的高斯噪聲來進(jìn)行匹配，如果此時匹配誤差仍在3個像素內(nèi)，則視為對上述噪聲具有較好的魯棒性。

標(biāo)準(zhǔn)Lena圖像如圖8所示，待搜索圖像大小為256×256,目標(biāo)圖像大小為40×40。

圖8 Lena圖像

指紋圖像如圖9所示，待搜索圖像大小為129×199,目標(biāo)圖像大小為25×25。

圖9 指紋圖像

遙感圖像如圖10所示，待搜索圖像大小為1 000×1 000,目標(biāo)圖像大小為200×200。

圖10 遙感圖像

實驗1 當(dāng)圖像中不存在噪聲的情況下，對于三組圖像，分別采用前述的三種算法進(jìn)行匹配。考慮準(zhǔn)確率，匹配所耗時間和匹配位置(代碼初次運行結(jié)果的位置)三個方面。對于索引表算法，邊界值選為20；對于SSDA算法，閾值選為40。實驗所得數(shù)據(jù)對比結(jié)果如表1,表2和表3所示。

表1 針對無噪Lena圖像的各算法性能比較

表2 針對無噪指紋圖像的各算法性能比較

表3 針對無噪遙感圖像的各算法性能比較

實驗1的結(jié)果如圖11所示。

圖11 無噪聲匹配結(jié)果

從實驗1的圖表中可以看出，當(dāng)圖像中不存在噪聲時，針對Lena圖像，指紋圖像和遙感圖像三組圖像，文中的三種算法都具有較高的匹配精度。其中索引表算法耗時最短，其次為SSDA算法，相關(guān)性算法耗時最久。

實驗2 給原圖像分別加上方差為0.01，0.05和0.1的高斯噪聲后，再用前述三種算法進(jìn)行匹配。實驗所得數(shù)據(jù)對比結(jié)果如表4至表12所示。

表4 針對含噪(σ2=0.01)Lena圖像的各算法性能比較

表5 針對含噪(σ2=0.01)指紋圖像的各算法性能比較

表6 針對含噪(σ2=0.01)遙感圖像的各算法性能比較

表7 針對含噪(σ2=0.05)Lena圖像的各算法性能比較

表8 針對含噪(σ2=0.05)指紋圖像的各算法性能比較

表9 針對含噪(σ2=0.05)遙感圖像的各算法性能比較

表10 針對含噪(σ2=0.1)Lena圖像的各算法性能比較

表11 針對含噪(σ2=0.1)指紋圖像的各算法性能比較

表12 針對含噪(σ2=0.1)遙感圖像的各算法性能比較

實驗2的具體結(jié)果如圖12所示。

圖12 含高斯噪聲匹配結(jié)果

從實驗2的圖表中可以看出，當(dāng)存在方差為0.01的高斯噪聲時，對圖像匹配精度幾乎沒有影響。當(dāng)存在方差為0.05的高斯噪聲時，基于索引表的算法和SSDA算法的匹配精度明顯下降，而基于圖像相關(guān)性的算法則具有良好的魯棒性。當(dāng)存在方差為0.1的高斯噪聲時，基于索引表的算法和SSDA算法的匹配精度較差，而基于圖像相關(guān)性的算法則仍然具有較高的匹配精度。另外，綜合三組圖像實驗結(jié)果來看，噪聲存在與否對于圖像匹配的實時性影響不大。

4 結(jié) 語

基于索引表的算法具有良好的實時性，在較小的噪聲環(huán)境下具有一定的魯棒性。在加入噪聲的情形下，將該算法的邊界值適當(dāng)放大，取到50，此時對于方差為0.1的高斯噪聲仍具有較好的魯棒性；然而當(dāng)高斯噪聲增至方差0.1以上后，魯棒性則較差。若邊界值選取過大，將增加匹配所耗時間，此時若在較強噪聲影響下，匹配效果也不理想。為了提高該算法的匹配效果，應(yīng)根據(jù)待匹配圖像的特點選取合適的邊界值。

基于圖像相關(guān)性的算法具有十分良好的魯棒性和精確性，在高斯噪聲環(huán)境下仍然具有很高的匹配精度。但其缺點是實時性較差，對于較大的圖像，例如遙感圖像，匹配所耗時間太久。

SSDA具有較好的實時性和精度，在低噪聲環(huán)境下也具有一定的魯棒性。在不同場合要求下，對SSDA進(jìn)行改進(jìn)[13-14]。例如使用序列代替固定閾值[6]的自適應(yīng)匹配算法等方法，提高了原算法的魯棒性和計算效率，增大了算法的使用范圍。

綜上所述，在無噪聲以及低噪聲的環(huán)境下，可采用基于索引表的算法和SSDA算法，具有良好的實時性；在較強的噪聲環(huán)境下，可采用基于圖像相關(guān)性的算法，具有良好的魯棒性。根據(jù)實際情況的要求來選用合適的算法，能夠大大地提高圖像匹配工作的效率，更好地發(fā)揮圖像匹配在圖像處理領(lǐng)域中的作用。在下一步的研究工作中，可以結(jié)合幾種算法各自的優(yōu)點，進(jìn)一步對算法的性能進(jìn)行改進(jìn)，開發(fā)一種新的高性能快速魯棒性算法，使其精度，速度和抗噪性等方面都能滿足多數(shù)應(yīng)用的要求。

[1] 李壯.異源圖像匹配關(guān)鍵技術(shù)研究[D].長沙:國防科技大學(xué),2011:1-135.

[2] 施陳博.快速圖像配準(zhǔn)和高精度立體匹配算法研究[D].北京:清華大學(xué),2011:1-138.

[3] 劉興淼,王仕成,趙靜.基于圖像多尺度熵的紅外圖像匹配跟蹤算法[J].控制與決策,2011,26(5):768-772.

[4] Tombari F, Di Stefano L, Mattoccia S. A robust measure for visual correspondence[C]//Proceeding of 14th International Conference on Image Analysis and Processing. Italy Modena: ICIAP, 2007:376-381.

[5] Shin Bong Gun, Park So-Youn, Lee Ju Jang. Fast and Robust Template Matching Algorithm in Noisy Image[C]//International Conference on Control, Automation and Systems. Korea Seoul: ICCAS,2007:6-9.

[6] 劉曉光,陳曦,陳政偉,等.基于圖像灰度的SSDA匹配算法[J].航空計算技術(shù),2010,40(1):54-57.

[7] 王立新,劉彤宇,李陽.SSDA圖像匹配算法的研究及實現(xiàn)[J].光電技術(shù)應(yīng)用,2005,20(3):53-55.

[8] Crow F. Summed-area tables for texture mapping[J].Computer Graphics,1984,18(3):207-212.

[9] McDonnel M. Box-filtering techniques[J].Computer Graphics and Image Processing,1981,17(1):65-70.

[10] Rosenfeld A, Vanderburg G. Coarse-fine template matching[J]. IEEE Transactions on Systems, Man and Cybernetics,1977,7(2):104-107.

[11] Di Stefano L, Mattoccia S, Tombari F. Zncc-based template matching using bounded partial correlation[J]. Pattern Recognition Letters, 2005,26(14):2129-2134.

[12] 王剛.數(shù)字圖像中模板抽取及匹配方法的研究與應(yīng)用[D].濟南:山東師范大學(xué),2013:1-47.

[13] 吳培景,陳光夢.一種改進(jìn)的SSDA圖像匹配算法[J].計算機工程與應(yīng)用,2005,41(33):76-78.

[14] Shao Xigao, Wu Kun, Duan Xiangbin. An Improved Algorithm for Gray Image Matching[J]. Journal of Information and Computational Science, 2013,10(7):1947-1957.

[責(zé)任編輯:王輝]

Comparison and research on three typical template matching algorithms

WU Chengmao, GUO Rui

(School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to reasonably select an appropriate algorithm for different conditions in particular problems such as image recognition, registration and mosaicking, three typical template matching algorithms, i.e. index table algorithm; an algorithm based on visual correspondence; and sequential similarity detection algorithm (SSDA), are explained in details in this paper. Differences analysis of matching performance of these algorithms is processed on their robustness, speed and precision. Experimental simulations data under different circumstances show that all three algorithms perform perfectly in precision, the index table algorithm and SSDA perform better in speed and the algorithm based on visual correspondence performs well on robustness in noise circumstance.

template matching, performance comparison, speed, robustness, precision

10.13682/j.issn.2095-6533.2014.03.004

2013-11-29

國家自然科學(xué)基金重點資助項目(90607008)；國家自然科學(xué)基金資助項目(61073106)；陜西省教育廳專項基金資助項目(2013JK1129)

吳成茂(1968-)，男，高級工程師，從事圖像處理研究。E-mail:wuchengmao123@sohu.com郭銳(1988-)，男，碩士研究生，研究方向為圖像信息處理。E-mail:304352014@qq.com

TP

A

2095-6533(2014)03-0015-07