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

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

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

0 引言

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

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

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

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

1 序貫相似性檢測算法

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

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

非歸一化：

歸一化：

式中：

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

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

2.1 圖像金字塔原理

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

圖1 圖像金字塔

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

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

2.2 分層搜索策略

圖像金字塔算法首先要對被搜索圖像和模板圖像進行采樣，根據搜索對象的大小以及分層后最上層圖像的可辨識度，確定搜索過程中需要劃分的金字塔層數。如圖2所示為圖像金字塔分層策略。

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

圖2 金字塔分層策略

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

3 旋轉處理

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

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

圖3 多角度模板圖像

4 實驗驗證

4.1 圖像處理

實驗中，首先是對待匹配圖像進行數字圖像處理，如圖4為圖像處理前后的待匹配圖像。

4.2 創(chuàng)建模板

圖4 待匹配圖像預處理

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

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

在選取的模板圖像基礎上，對其進行旋轉處理得到不同角度的模板圖像，在0～360°之間，實驗中每2.6°創(chuàng)建一個模板。

4.3 模板匹配

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

圖6 模板匹配過程

4.4 坐標轉換

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

圖7 模板匹配結果

圖8 示教位置

表2 各匹配圖像位置的圖像坐標

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

表1 模板示教位置圖像坐標

通過模板匹配獲取的各器件圖像的中心坐標和旋轉角度，可計算出各個器件中示教位置在圖像坐標系下的位置信息，其中匹配器件1為模板圖像，匹配器件2與3分別圖7中另外兩個匹配器件圖像。實驗中計算的各器件的位置信息如表2所示。

5 結語

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