一種基于灰度的快速模板匹配方法

鄭劍斌，鄭力新,2，朱建清

（1.華僑大學(xué)工學(xué)院，泉州 362021；2.工業(yè)智能化技術(shù)與系統(tǒng)福建省高校工程研究中心，泉州 362021）

模板匹配;序貫相似性檢測(cè);圖像金字塔;高斯濾波

0 引言

隨著圖像處理、模式識(shí)別和機(jī)器人產(chǎn)業(yè)的快速發(fā)展，機(jī)器視覺技術(shù)的應(yīng)用越來越廣泛。傳統(tǒng)機(jī)器人一般采用“示教”或離線編程來控制機(jī)器人的運(yùn)動(dòng)，難以適應(yīng)目前工業(yè)生產(chǎn)中的實(shí)時(shí)性要求與復(fù)雜的工作環(huán)境。結(jié)合視覺技術(shù)，使機(jī)器人具有更高的智能化程度和更好的環(huán)境適應(yīng)性。

對(duì)于大多數(shù)二維平面機(jī)器人視覺應(yīng)用，工件需要通過可視化模塊進(jìn)行識(shí)別和定位。在圖像中定位一個(gè)已知目標(biāo)的最直接的方法是在像素級(jí)搜索需要識(shí)別控制的目標(biāo)[1]。二維平面應(yīng)用中模板匹配是一種計(jì)算量較小的有效目標(biāo)識(shí)別算法。模板匹配的思想是比較已知模板和原始圖像中相同大小的區(qū)域之間的灰度值等信息[2]。將匹配對(duì)象稱為模板，并將其與搜索圖像進(jìn)行比較，以在未知圖像中找到模板的位置，這個(gè)過程是圖像匹配。模板匹配算法涉及兩個(gè)關(guān)鍵方面：相似性度量和搜索策略[3]。這兩個(gè)方面都決定了目標(biāo)識(shí)別的計(jì)算匹配時(shí)間[4-5]。模板匹配是目標(biāo)識(shí)別、醫(yī)學(xué)成像、工業(yè)自動(dòng)檢測(cè)、特征跟蹤和數(shù)字?jǐn)z影測(cè)量等方面最重要的課題之一[6-7]。

經(jīng)典的模板匹配方法具有機(jī)理簡(jiǎn)單，檢測(cè)準(zhǔn)確率高的特點(diǎn)，被用作一般模型評(píng)估和誤差估計(jì)。傳統(tǒng)的像素灰度匹配算法SAD和SSD[8]，時(shí)間復(fù)雜度較高，光照條件變化影響算法穩(wěn)定性。歸一互相關(guān)系數(shù)算法[9]通過計(jì)算標(biāo)準(zhǔn)差解決了光照變化使得圖像中灰度值不相等問題。去均值歸一化算法則通過增加算法的計(jì)算量[10]，通過計(jì)算可能匹配位置的圖像與模板之間的均值，得到零均值圖像，使得算法具有抗亮度干擾能力，提高了模板匹配的精度。傳統(tǒng)的匹配方法影響速度的主要因素是搜索計(jì)算和匹配的操作，適當(dāng)減小位置和相似度計(jì)算精度可顯著提高模板匹配的速度。這正成為這個(gè)領(lǐng)域的一個(gè)研究熱點(diǎn)。

針對(duì)上述問題，本文首先對(duì)圖像進(jìn)行處理，提取對(duì)象的特征圖像，減少匹配干擾。為使待匹配點(diǎn)快速被檢測(cè)，結(jié)合序貫相似性檢測(cè)算法，通過圖像金字塔搜索策略減少待匹配圖像與模板上的匹配點(diǎn)來加快匹配速度。通過建立多角度模板來解決匹配中角度偏差較大不匹配或者匹配概率低的問題。

1 序貫相似性檢測(cè)算法

設(shè)參考模板T，其大小為Mt×Nt，搜索圖像S，其大小為Ms×Ns，且Mt≤Ms，Nt≤Ns，搜索圖像中以(u,v)為左上角坐標(biāo)，大小Mt×Nt的子圖像塊為Su,v。序貫相似性檢測(cè)算法（SSDA）[11][12]則通過定義以累計(jì)差值，來停止某一點(diǎn)的匹配計(jì)算，進(jìn)而切換至下一點(diǎn)位置上計(jì)算，通過這樣的方式可加快匹配的速度。

序貫相似檢測(cè)算法與傳統(tǒng)模板匹配一樣，需要度量(Ms-Mt+1)?(Ns-Nt+1)個(gè)像素點(diǎn)，但與其他傳統(tǒng)算法不一樣的是SSDA通過計(jì)算子圖像Su,v與模板T對(duì)應(yīng)像素的累計(jì)差值，且兩者對(duì)應(yīng)像素點(diǎn)對(duì)以隨機(jī)的次序 (mr1,nr2)(r1=1,2,…,Mt;r2=1,2,…,Nt)做比較，加快了累計(jì)差值的增加。序貫相似檢測(cè)算法的非歸一化與歸一化的匹配差值定義如下：

非歸一化：

歸一化：

式中：

通過比較e(u,v,mr1,nr2)與一個(gè)預(yù)定義的固定閾值W或者單調(diào)遞增的閾值序列W(k)，在子圖像的累計(jì)差值e(u,v,mr1,nr2)等于或者大于W或W(k)時(shí)，結(jié)束此次度量計(jì)算，記下相應(yīng)的k值，進(jìn)行下一個(gè)待匹配點(diǎn)子圖像差值的計(jì)算；當(dāng)然，如果累計(jì)差值e(u,v,mr1,nr2)小于閾值W或W(k)，則繼續(xù)計(jì)算該子圖像在(u,v)處的下一個(gè)隨機(jī)點(diǎn)的累計(jì)差值，直到e(u,v,mr1,nr2)大于W或W(k)，記下相應(yīng)的k值。整個(gè)度量計(jì)算是對(duì)不同的待匹配點(diǎn)進(jìn)行上述計(jì)算，最后取最大k值對(duì)應(yīng)的待匹配點(diǎn)位置即為相似點(diǎn)。計(jì)算過程中，子圖像需要越多的對(duì)應(yīng)點(diǎn)差值才能累加達(dá)到W或W(k)的值，則子圖像就越趨近于匹配對(duì)象。SSDA通過選取合適的閾值，使得誤差累計(jì)較快的子圖像所需測(cè)試的像素點(diǎn)遠(yuǎn)小于模板大小Mt×Nt。所以SSDA匹配速度比傳統(tǒng)相關(guān)法提高了一個(gè)數(shù)量級(jí)。

2 圖像金字塔分層搜索策略

2.1 圖像金字塔原理

從相似度量計(jì)算的過程中，可知函數(shù)的計(jì)算復(fù)雜度為O(whn)，w和h是圖像的寬和高,n是模板中點(diǎn)的數(shù)量。雖然在序貫相似性檢測(cè)的相關(guān)性函數(shù)中改變了停止標(biāo)準(zhǔn)，算法的處理速度提升了一定常數(shù)比例，但不能降低算法的計(jì)算復(fù)雜度。因此，需要一種快速的搜索策略，通過減少需要檢測(cè)的位姿數(shù)量以及模板中點(diǎn)的數(shù)量，來提高算法的速度，滿足系統(tǒng)的實(shí)時(shí)性。一般情況下，圖像多次縮小2倍至一個(gè)倍數(shù)與直接將圖像縮小至這一倍數(shù)的效果更好。如圖1所示，將圖像多次縮小2倍，按照分辨率從大到小分層堆放，圖像形如金字塔狀，所以將這樣的數(shù)據(jù)結(jié)構(gòu)稱為圖像金字塔[13-16]。

圖1 圖像金字塔

圖像金字塔思想是先在最上層低分辨率的圖像中，利用相關(guān)測(cè)度算法進(jìn)行初步搜索匹配，將得到的度量計(jì)算的結(jié)果回溯到分辨率比其高的下一層圖像中，在下一層中選取匹配結(jié)果得到的相似點(diǎn)的一個(gè)鄰域，這層中則在該鄰域中進(jìn)行搜索，以此一層層回溯，最后則可以得到最高分辨率圖像中的一個(gè)小范圍鄰域，再進(jìn)行相似度量函數(shù)的精確匹配。

構(gòu)建金字塔的速度是非常重要的，通常為了不考慮頻率響應(yīng)問題，采用2×2的均值濾波器來平滑圖像。為了避免圖像壓縮后的折疊失真，在采樣前可對(duì)圖像進(jìn)行低通濾波來去除高于采樣頻率的空間頻率。所以在構(gòu)建圖像金字塔的過程中本文使用高斯函數(shù)濾波器來實(shí)現(xiàn)平滑[17]。

2.2 分層搜索策略

圖像金字塔算法首先要對(duì)被搜索圖像和模板圖像進(jìn)行采樣，根據(jù)搜索對(duì)象的大小以及分層后最上層圖像的可辨識(shí)度，確定搜索過程中需要?jiǎng)澐值慕鹱炙訑?shù)。如圖2所示為圖像金字塔分層策略。

實(shí)驗(yàn)中為了避免分層使得圖像產(chǎn)生鋸齒以及保證整個(gè)匹配的穩(wěn)定性，采用的分層策略是將金字塔低一層的圖像中某個(gè)鄰域塊中的像素取平均值，或者是用給定的函數(shù)模板進(jìn)行加權(quán)擬合，得到的像素值作為上一層金字塔圖像的像素點(diǎn)。

圖2 金字塔分層策略

圖像分層后，則進(jìn)行由粗到精的匹配[18-20]。在得到了一個(gè)k層的金字塔圖像后，在Sk和Tk中通過遍歷的方式，使用預(yù)定的序貫相似性度量檢測(cè)算法計(jì)算各層中點(diǎn)的累計(jì)差值，并設(shè)定好閾值來確定一系列的回溯點(diǎn)(xk,yk)，回溯到搜索圖像Sk-1和模板圖像Tk-1中的鄰域δ(xk,yk)，在得到的鄰域中，再進(jìn)行相似度檢測(cè)，重新得到一定數(shù)量的相似點(diǎn)鄰域(xk-1,yk-1)，直到計(jì)算至出金字塔最低層，分辨率最高圖像中的最佳匹配點(diǎn)。由于目標(biāo)物體通過分層變換后，在高層金字塔的圖像中灰度值的變化細(xì)節(jié)不那么明顯。為了保證所有可能的匹配位置，保證匹配的準(zhǔn)確性，在圖像金字塔中層數(shù)越高，應(yīng)該使用越寬松的閾值進(jìn)行序貫相似性度量檢測(cè)。

3 旋轉(zhuǎn)處理

傳統(tǒng)的灰度模板匹配相似度度量的方法中，待匹配圖像與模板之間只允許小角度的旋轉(zhuǎn)，即限定了模板與待匹配圖像的方向。這使得傳統(tǒng)的模板匹配方法不能匹配對(duì)象或者匹配概率低，不適用于待匹配圖像與模板之間具有較大角度偏差的情況。

實(shí)驗(yàn)中選取待匹配圖像中一區(qū)域，對(duì)該區(qū)域圖像進(jìn)行角度旋轉(zhuǎn)，取一定角度偏差的圖像進(jìn)行創(chuàng)建模板，得到多角度的模板，如圖3所示。

圖3 多角度模板圖像

4 實(shí)驗(yàn)驗(yàn)證

4.1 圖像處理

實(shí)驗(yàn)中，首先是對(duì)待匹配圖像進(jìn)行數(shù)字圖像處理，如圖4為圖像處理前后的待匹配圖像。

4.2 創(chuàng)建模板

圖4 待匹配圖像預(yù)處理

實(shí)驗(yàn)中，首先在獲取的待匹配原圖像（圖4（a））中選取模板區(qū)域來創(chuàng)建模板，記錄模板的中心坐標(biāo)位置和模板旋轉(zhuǎn)的角度信息，如圖5所示。

圖5 創(chuàng)建模板圖像

在選取的模板圖像基礎(chǔ)上，對(duì)其進(jìn)行旋轉(zhuǎn)處理得到不同角度的模板圖像，在0～360°之間，實(shí)驗(yàn)中每2.6°創(chuàng)建一個(gè)模板。

4.3 模板匹配

利用創(chuàng)建好的模板，結(jié)合圖像金字塔分層搜索策略，根據(jù)相似度測(cè)量方法對(duì)圖像預(yù)處理后的圖像進(jìn)行匹配計(jì)算。對(duì)匹配的感興趣區(qū)域記錄其中心位置坐標(biāo)信息以及當(dāng)前匹配區(qū)域相對(duì)于上一匹配區(qū)域的旋轉(zhuǎn)角度。每一個(gè)匹配區(qū)域匹配結(jié)果如圖6所示。最終模板匹配完成后的圖像如圖7所示。在整個(gè)匹配的過程中，執(zhí)行不到0.2s，滿足系統(tǒng)實(shí)時(shí)性的要求。

圖6 模板匹配過程

4.4 坐標(biāo)轉(zhuǎn)換

在模板圖像中通過鼠標(biāo)示教出一些位置坐標(biāo)，如圖8所示。

圖7 模板匹配結(jié)果

圖8 示教位置

表2 各匹配圖像位置的圖像坐標(biāo)

獲取并記錄模板中位置的圖像坐標(biāo)系下位置信息，如表1所示。

表1 模板示教位置圖像坐標(biāo)

通過模板匹配獲取的各器件圖像的中心坐標(biāo)和旋轉(zhuǎn)角度，可計(jì)算出各個(gè)器件中示教位置在圖像坐標(biāo)系下的位置信息，其中匹配器件1為模板圖像，匹配器件2與3分別圖7中另外兩個(gè)匹配器件圖像。實(shí)驗(yàn)中計(jì)算的各器件的位置信息如表2所示。

5 結(jié)語

本文利用序貫相似性檢測(cè)算法作為匹配的相似性測(cè)度，結(jié)合圖像金字塔分層搜索策略，大大提高了模板匹配速度，且通過建立多角度模板來解決基于灰度模板匹配對(duì)角度偏差較大圖像不匹配或匹配概率低的問題。實(shí)驗(yàn)中整個(gè)匹配計(jì)算過程在0.2s內(nèi)完成，滿足工業(yè)應(yīng)用中實(shí)時(shí)性的要求，利用匹配得到的中心坐標(biāo)與角度信息，計(jì)算了圖像各區(qū)域匹配后相關(guān)坐標(biāo)、角度信息，驗(yàn)證了匹配精確度，證明了方法的可行性。