圖像模板匹配概述

王凱 馬龍敏 劉妍

摘 要：圖像處理發展迅速，許多智能算法涌現，其檢測識別精度不斷提高，但是這些算法的性能大量依賴樣本的訓練，在某些特定場合，如敵對目標的識別，樣本稀缺，無法適用于智能算法。模板匹配算法發展最早，雖然對目標姿態、光照環境較為敏感，但需要樣本少，其結果的可靠性是其他智能算法無法比擬的，在一些特定場合應用效果較好，本文主要介紹模板匹配算法的種類及發展。

把實時圖像當作一個模板圖像（Template image），在參考圖像中設定一個和模板圖像大小相同的窗口，滑動窗口，比較窗口中圖像和模板圖像的差別，差別最小處為最佳匹配點。

一、絕對平衡搜索（ABS）算法

ABS算法對參考圖像進行絕對平衡搜索，搜索窗口掃過參考圖像中的每一個像素點，將窗口圖像和模板圖像之間的像素點做比較，把它們之間的差別大小作為相關性衡量標準，差別最小的那個窗口的圖像區域即為匹配區域，比較方法有以下幾種：

其中為模板圖像，掃描過程中的窗口圖像，取MAD或者SSD最小處的，作模板圖像在參考圖像中的最佳匹配點。但是，這種方法在圖像的灰度值發生線性變化時（灰度值加一個常數或者乘以一個常數），就失效了，兩種誤差都不能對匹配點做出正確衡量。這種方法只能用于模板圖像嚴格地為參考圖像的一部分的情況。

二、歸一化互相關度量算法

構造歸一化互相關函數（NCD）：

若將模板大小的區域作為向量描述，上述公式描述的為兩個向量夾角的余弦值，夾角越小，說明參考圖與實時圖之間的方向越接近。最大時的為最佳匹配位置。這種方法實際上消除了一部分關照變換的影響（對比度不變性，每個灰度值都乘以一個常數因子），對于很小的旋轉和縮放也有一定的容忍度。但對于圖像亮度變化（灰度值加減一個常數）、較大的旋轉和縮放就失效了，而且該方法計算量太大。

三、幅度排序相關算法

首先把模板圖像中的像素點按照灰度值的大小進行排序;然后根據像素點個數進行二進制編碼（個數為奇數時中間一個像素點不進行編碼）;最后根據二進制位數形成陣列圖。下面以大小的模板圖為例進行說明：

首先，對圖1（a）所示的模板圖像進行幅度排序，結果見圖1（b）中的第二列。

然后，對排序后的像素點進行二進制編碼，如圖1（b）第三列所示。

最后，對圖1（b）所示的二進制序列，從高到低（1，2，3）分別抽取各個位上的數值。

量化后的模板圖像陣列圖和窗口圖像的積相關函數為（二進制1代表正，0為負）：

這是第一步的粗匹配，上式可以簡單的表示為像素點灰度值大的位置和小的位置相減，當為匹配點時，窗口圖像也有相同的性質。設定一個閾值，當進行第一次粗匹配搜索時，記錄所有的點為第一次檢測點;在第一次檢測點上，計算第二個陣列圖與窗口圖像的積相關函數值：

表示了更精細的相關值，同樣設定一個閾值，記錄所有的點為第二次檢測點;依次類推，直到二進制序列的最后一位：

在閾值為時檢測到的像素點即為匹配點，如果不唯一，則取最大的點為匹配點。上述中有，每一步的檢測更加精細，檢測點也更加稀少。

四、序列相似性檢測算法

這種算法最大的特征點是能夠較快的丟棄不匹配點，提高匹配速度，是一種快速的模板匹配算法。它來自于平均絕對誤差（MAD），但并不計算所有的誤差和，其基本原理如下：

a.定義SSDA計算時的絕對誤差：

其中：分別為參考圖像中的搜索窗口和模板圖像的平均值。

b.設定閾值為Th;在搜索窗口中隨機選取像素點，計算其絕對誤差;不停的隨機選取像素點并累加其絕對誤差（可以提前生成偽隨機序列以節省時間），當絕對誤差和超過設定閾值Th后，停止選取，記錄累計次數。

c.滑動圖像窗口，比較所有的，最大處為匹配點。

如果絕對誤差和在隨機選取的次數較小時就超過了閾值，說明其和模板圖像差別較大，不是匹配點;若果絕對誤差和隨著選取次數的增長而呈線性均勻增長，并增長緩慢（累計次數較大），說明其為匹配點或近似匹配點。由此可以看出，相比較MAD，SSDA在參考圖像非匹配點上隨機選取幾個像素值計算后就很快跳過了，每個窗口處的計算次數要大大減少。

為了進一步提高速度，可以把匹配搜索分成兩步來進行，第一步搜索窗口間隔個像素點進行一次序列相似性檢測，找出匹配位置，而后在的區域內按照SSDA進行精確匹配，找出最佳匹配位置，的選取不能過大，否則容易跳過匹配位置;同時累計誤差閾值采用自適應值，閾值隨著累計次數的增長而增長，這樣能更快的丟棄非匹配點（隨機選取次數降低），進一步降低時間消耗。

以上為四種常見的模板匹配算法，分別從灰度值差值、向量角度、統計排序等來衡量實時圖與模板圖的相似性，模板匹配的發展更加能夠適應環境的變化，例如光照、角度、縮放等變換，這些變化在實際應用中是不可避免的，因為圖像中包含了大量的信息，其有效模式及有意義的像素排列組合是及其少數的，所以利用統計的方法進行匹配，在原理上可以避免由于光照、角度和尺度的變換。