模板匹配

模板匹配是一種最原始、最基本的模式識別方法，研究某一特定對象物的圖案位於圖像的什麼地方，進而識別對象物，這就是一個匹配問題。它是圖像處理中最基本、最常用的匹配方法。模板匹配具有自身的局限性，主要表現在它只能進行平行移動，若原圖像中的匹配目標發生旋轉或大小變化，該算法無效。

基本介紹

• 中文名：模板匹配
• 外文名：template matching
• 本質：匹配問題
• 地位：最原始、最基本的模式識別方法
• 相關算法：相關法、誤差法、二次匹配誤差法
• 時間：20世紀70年代

定義

模板就是一副已知的小圖像，而模板匹配就是在一副大圖像中搜尋目標，已知該圖中有要找的目標，且該目標同模板有相同的尺寸、方向和圖像元素，通過一定的算法可以在圖中找到目標，確定其坐標位置。

算法

相關法

以8位灰度圖像為例，模板T(m,n)疊放在被搜尋圖S(W,H)上平移，模板覆蓋被搜尋圖的那塊區域叫子圖 ，i,j為子圖左下角在被搜尋圖S上的坐標，搜尋範圍是：1≤i≤W-n，1≤j≤H-m。可以用下式衡量T和 的相似性：

將其歸一化，得模板匹配的相關係數：

當模板和子圖一樣時，相關係數R(i,j)=1，在被搜尋圖S中完成全部搜尋後，找出R的最大值 ，其對應的子圖 即為匹配目標。顯然，用這種公式做圖像匹配運算量最大、速度最慢。

誤差法

誤差法即衡量T和 的誤差，其公式為：

其中E(i,j)為最小值處即為匹配目標。為提高計算速度，取一誤差閾值 ，當E(i,j)> 時便停止該點的計算，繼續計算下一點。

模板越大，匹配速度越慢；模板越小，匹配速度越快。

二次匹配誤差算法

二次匹配誤差算法中匹配分兩次進行。

第一次匹配是粗略匹配。取模板的隔行隔列數據，即四分之一的模板數據，在被搜尋圖上進行隔行隔列掃描匹配，即在原圖的四分之一範圍內匹配。由於數據量大幅度減少，匹配速度顯著提高。

誤差閾值 ： ，其中， 為各點平均的最大誤差，一般取40~50即可；m,n分別為模板的長和寬。

第二次匹配是精確匹配。在第1次誤差最小點 的領域內，即在對角點為，的矩形內進行搜尋匹配，得到最後結果。實驗結果表明，二次匹配誤差法的速度比其他算法快10倍左右。

方法改進

高速模板匹配法

與邊緣檢測中使用的模板不同，模板匹配中使用的模板相當於（8×8~32×32）。從大幅面圖像尋找與模板最一致的對象，計算量大，要喔花費相當多的時間。為使模板匹配高速化，Barnea等人提出了序貫相似性檢——SSDA法（sequential similiarity detection algorithm）。

SSDA法計算圖像f(x,y)在像素（u,v）的非相似度m(u,v)為：

以m(u,v)作為匹配尺度。式中（u,v）表示的不是模板與圖像重合部分的中心坐標，而是重合部分左上角像素坐標。模板的大小為：n×m。

如果在圖像（u,v）處有和模板一致的圖案，則m(u,v)值很小，相反則較大。特別是在模板和圖像重疊部分完全不一致的場合下，如果在模板內的各像素與圖像重合部分對應像素的差的絕對值依次增加下去，其和就會急劇地增大。因此，在做加法的過程中，如果差的絕對值部分和超過了某一閾值時，就認為這位置上不存在和模板一致的圖案，從而轉移到下一個位置上計算m(u,v)。由於計算m(u,v)只是加減運算，而且這一計算在大多數位置中途便停止了，因此能大幅度地縮短計算時間，提高匹配速度。

還有一種把在圖像上的模板移動分為粗檢索和細檢索兩個階段進行的匹配方法。首先進行粗檢索，它不是讓模板每次移動一個像素，而是每隔若干個像素把模板和圖像重疊，並計算匹配的尺度，從而求出對象物大致存在的範圍。然後，在這個大致範圍內，讓模板每隔一個像素移動一次，根據求出的匹配尺度確定對象所在的位置。這樣，整體上計算模板匹配的次數減少，計算時間短，匹配速度就提高了。但是使用這種方法存在漏掉圖像中最適當位置的危險性。

高精度定位的模板匹配

一般的圖像中有較強的自相關性，因此，進行模板匹配計算的相似度就在以對象物存在的地方為中心形成平緩的峰。這樣，即使模板匹配時從圖像對象物的真實位置稍微離開一點，也表現出相當高的相似度。上面介紹的粗精檢索高速化恰好利用了這一點。但為了求得對象物在圖像中的精確位置，總希望相似度分布儘可能尖銳一些。

為了達到這一目的，人們提出了基於圖案輪廓的特徵匹配方法。圖案輪廓的匹配與一般的匹配法比較，相似度表現出更尖銳的分布，從而利於精確定位。

一般來說，在檢測對象的大小和方向未知的情況下進行模板匹配，必須具備各式各樣大小和方向的模板，用各種模板進行匹配，從而求出最一致的對象及其位置。

另外，在對象的形狀複雜時，最好不把整個對象作為一個模板，而是把對象分割成幾個圖案，把各個分圖案作為模板進行匹配，然後研究分圖案之間的位置關係，從而求圖像中對象的位置。這樣即使對象物的形狀稍微變化，也能很好地確定位置。

注意事項

在套用模板匹配法進行圖像匹配時，應注意以下幾點：
（1）歸一化互相關注進行匹配，模板應在（M-P+1）×（N-Q+1）個參考位置上進行相關計算，計算量非常大，必要時可以採用序貫相似檢驗算法、幅度排序相關算法、FFT相關算法、分層搜尋序貫判決等方法對其進行改進，以提高運算速度。

（2）模板匹配具有自身的局限性，主要表現在它只能進行平行移動，若原圖像中的匹配目標發生旋轉或大小變化，該算法無效。

（3）若原圖像中要匹配的目標只有部分可見，該算法也無法完成匹配。