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

吳成茂， 郭 銳

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

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

吳成茂， 郭 銳

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

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

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

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

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

1 模板匹配算法描述

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

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

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

圖1 圖像矩陣

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

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

圖2 圖像索引表

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

圖3 模板圖像矩陣

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

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

圖4 待選圖像矩陣

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

圖5 懲罰數表

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

圖6 匹配結果

1.2 基于圖像相關性的圖像匹配算法

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

圖7 3×3圖像矩陣

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

(1)

(2)

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

(3)

(4)

φ(x,y)=

(5)

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

(6)

其中

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

(7)

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

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

(8)

其中

‖R(x1,y1)‖=

(9)

‖T(x2,y2)‖=

(10)

(11)

1.3 序貫相似性檢測算法

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

定義絕對誤差

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

(12)

(13)

(14)

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

I(i,j)=

(15)

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

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

2 算法性能及復雜性分析

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

2.1 索引表算法分析

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

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

2.2 相關性算法分析

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

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

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

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

3 仿真測試與分析

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

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

標準Lena圖像如圖8所示，待搜索圖像大小為256×256,目標圖像大小為40×40。

圖8 Lena圖像

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

圖9 指紋圖像

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

圖10 遙感圖像

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

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

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

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

實驗1的結果如圖11所示。

圖11 無噪聲匹配結果

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

實驗2 給原圖像分別加上方差為0.01，0.05和0.1的高斯噪聲后，再用前述三種算法進行匹配。實驗所得數據對比結果如表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的具體結果如圖12所示。

圖12 含高斯噪聲匹配結果

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

4 結 語

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

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

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

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

[1] 李壯.異源圖像匹配關鍵技術研究[D].長沙:國防科技大學,2011:1-135.

[2] 施陳博.快速圖像配準和高精度立體匹配算法研究[D].北京:清華大學,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].航空計算技術,2010,40(1):54-57.

[7] 王立新,劉彤宇,李陽.SSDA圖像匹配算法的研究及實現[J].光電技術應用,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] 王剛.數字圖像中模板抽取及匹配方法的研究與應用[D].濟南:山東師范大學,2013:1-47.

[13] 吳培景,陳光夢.一種改進的SSDA圖像匹配算法[J].計算機工程與應用,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.

[責任編輯:王輝]

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

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

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

TP

A

2095-6533(2014)03-0015-07