王 堅(jiān)

(遼寧對外經(jīng)貿(mào)學(xué)院，遼寧 大連 116000)

圖像匹配即是應(yīng)用某種特殊的邏輯運(yùn)算和數(shù)學(xué)方法在兩幅圖片之間尋找共同點(diǎn)[1]。圖像匹配的研究工作很早就在國外開始了，70年代的美國為了軍事的需要開啟了關(guān)于圖像匹配的研究工作，主要是針對武器的飛行導(dǎo)航功能[2]。我國研究起步雖然比較晚，但是也有不少新的突破。其一，是圖像匹配過程中特征提取算法的改進(jìn)，包括SIFT檢測算法、CNN算法、KNN算法和AKAZE算法等。其二，是聯(lián)合算法的設(shè)計(jì)與實(shí)現(xiàn)，例如多尺度PCA-HOG聯(lián)合技術(shù)提高算法的運(yùn)行速度[3]；KNN與RANSAC相結(jié)合改變抽樣規(guī)格與匹配模式，提高算法的魯棒性[4]。其三，是快速匹配算法的開發(fā)，例如基于改進(jìn)SURF的快速匹配算法，與傳統(tǒng)算法相比提高30%的運(yùn)行效率[5]。本文以灰度圖像為研究對象，分別比較常用的灰度圖像匹配的算法、改進(jìn)的灰度圖像匹配的算法(序貫相似性算法)和局部灰度編碼算法在圖像快速匹配中的性能，為圖像匹配算法的開發(fā)提供理論基礎(chǔ)。

1 數(shù)字圖像匹配技術(shù)概述

1.1 基于模板法的圖像匹配方法

模板匹配是指通過尺寸更小的圖像模板與源圖像進(jìn)行比較分析。想要確定模板是否與源圖像有相同或相似的區(qū)，則需要求出相似區(qū)域的位置和坐標(biāo)，然后提取圖像。模板匹配的步驟如圖1所示?；谀０宸ǖ膱D像匹配算法有許多，比較常見的主要包括誤差平方和算法(SSD)和基于誤差平方和的序貫相似性檢測算法(SSDA)。

圖1 模板算法流程圖

1.1.1 誤差平方和算法(SSD)[6]

誤差平方和算法主要是通過求解模板圖像與源圖像相似區(qū)域的誤差平和進(jìn)行圖像的匹配。假設(shè)f(x,y)為M×N的源圖像，t(j,k)為J×K(J≤M,K≤N)的模板圖像，則誤差平方和測度定義為：

(1)

由上式展開可得：

(2)

(3)

(4)

(5)

其中，DS(x,y)稱為源圖像中與模板對應(yīng)區(qū)域的能量，其大小與像素的位置有關(guān)。DST(x,y)為模板與源圖像對應(yīng)區(qū)域的互相關(guān)性。DT(x,y)為模板的能量。

1.1.2 基于誤差平方和的序貫相似性檢測算法(SSDA)

序貫相似性檢測算法是對傳統(tǒng)模板匹配算法的改進(jìn)，增加了閾值參數(shù)。SSDA算法定義絕對誤差[7]：

(6)

其中，帶有上劃線的分別表示子圖、模板的均值：

(7)

(8)

實(shí)際上，絕對誤差就是子圖與模板圖各自去掉其均值后，對應(yīng)位置差的絕對值，然后設(shè)定閾值Th；在模板圖中隨機(jī)選取不重復(fù)的像素點(diǎn)，計(jì)算與當(dāng)前子圖的絕對誤差，將誤差累加，當(dāng)誤差累加值超過了Th時(shí)，記下累加次數(shù)H，所有子圖的累加次數(shù)H用一個表R(i,j)來表示。SSDA檢測定義為：

(9)

1.2 基于改進(jìn)的模板圖像匹配快速算法

整個圖像被劃分成k×k處的大小和非重疊正方形中，然后對圖像進(jìn)行分塊，如果我們把圖像分割以后剩下的部分?jǐn)?shù)量不是k的倍數(shù)，則底部和剩余行的最右邊、列切割。R-塊中，R，S(Ri)的R-塊表示像素Ri的灰度值和。塊R-附近的組成(圖2b)，D-Block的定義和其周圍的八個塊相鄰的R(圖2a：R1，R2，R3，R4，R6，R7，R8，R9示出)；將R-塊的鄰域分為4個部分，分別為D1，D2，D3，D4(如圖2b)，稱為R-塊的D-鄰域；R-塊R5分別屬于4個D鄰域，即D1=R1∪R2∪R4∪R5；D2=R4∪R5∪R7∪R8；D3=R5∪R6∪R8∪R9；D4=R2∪R3∪R5∪R6。

圖2 圖像劃分

對每一個D-R-附近的四大模塊，需要一個序列(圖2的逆時(shí)針順序)像素對Dj灰度總值進(jìn)行表示。包括：S(Rj1)、S(Rj2)、S(Rj3)、S(Rj4)共有24(4!)種可能；可以用五位二進(jìn)制代碼來表示。稱作P(Dj)∈{00000，00001，L10111}來表示。這樣的24種就是所謂的對應(yīng)的位置關(guān)系，它們有24種，如果采取對D塊內(nèi)扭轉(zhuǎn)(逆序)R-4塊。其中每個對應(yīng)于灰度排序之間的位置關(guān)系，我們可以進(jìn)行編碼再固定，當(dāng)然，我們也可以使用序列。將R-塊Ri所在的4個D-塊的P(Dj)做位串并接得到：F(Ri)=P(D1)P(D2)P(D3)P(D4)，接著對4個(Dj)具體操作是：F(Ri)=(P(D1)<<15)+(P(D2)<<10)+(P(D3)<<5)+P(D4)。其中P(Dj)是Rj鄰域Dj的二進(jìn)制碼，后面的數(shù)字表示移位。2F(Ri)是塊20的二進(jìn)制編碼的表示，稱為塊編碼。通過上述簡單的推論可以得知，Ri編碼塊的類型可有244種，但是F(Ri)表示位置的關(guān)系應(yīng)該在相鄰的八領(lǐng)域塊的灰度和(R-塊Rj之間)排布。當(dāng)D1中塊之間的位置關(guān)系被確定，以及灰度值總值被確后，D2和D4塊之間的關(guān)系(總值灰度)就不可能24種，是12種。R4和R5再加上R2和R5倆對關(guān)系已經(jīng)很明顯的，所以D3只有六個可能的種類，雖然我們做了這么多的簡化推論，看起來少了不少種類，但是仍然要計(jì)算至少24*12*12*6=20736種，導(dǎo)致了計(jì)算量仍然不小，因此在計(jì)算整幅圖像的時(shí)候出現(xiàn)的重碼的概率應(yīng)該是非常低的，這也是種方法的準(zhǔn)確性的體現(xiàn)。此外，該編碼方法反映了灰度圖像的灰度相對值。所以，相對穩(wěn)定的灰度值也使得計(jì)算少了許多干擾，抗噪聲能力很強(qiáng)。用k的選擇粒度的大小可以改變圖像處理的大小，方便在不同的噪聲情況下對象圖像進(jìn)行處理。

用搜索圖S搜索以模板T的長度、寬度水平、垂直步長為標(biāo)準(zhǔn)。從左上方以T的大小分割至S稱為限制塊C(i，j))。由它開始，其中(i，j)為限制塊左上角頂點(diǎn)在搜索圖S上的坐標(biāo)。這種劃分之后，如果我們還可以在右側(cè)或底部搜索到S的沒有被覆蓋的部分，那么我們就可以從相應(yīng)起始位置的最右側(cè)向S的左側(cè)搜索，或從底部開始重新劃分成塊或限制線，使得全部限制塊可以完全覆蓋搜索圖S。限制塊C(i，j))和T是N×N模板圖像的尺寸，其中，每個組可用塊R-矩陣A(C(i，j))與A(T)表示已知特征編碼矩陣，其中K是一個側(cè)R-塊的邊長。比較A(C(i，j))和A(T)的每個元素相同的行號列號，記錄行列號。和分形編碼檢索中遇到的問題一樣，也是在兩圖中很顯然的問題，就是說怎么對準(zhǔn)R-塊。我們來看(圖3a)是模板圖的陰影部分和搜索圖和圖S的模板T匹配。然而，在對模板T和搜索圖S進(jìn)行塊R分割后，就沒有兩者之間的相同的R-塊了，這是R-塊就不能很好的表示兩幅圖像的局部相似度了，匹配率將受到不同程度的影響。因此，有必要對模板T做合適的剪切，在圖中移除陰影部分。如(圖3b)，剩余的子區(qū)域可被配置為如圖3c中，然后圖3b中的右下側(cè)4個R塊對齊。

圖3 S搜索示意圖

在為了實(shí)現(xiàn)圖R-塊對齊的模板T和S中的特征匹配，模板T可正確切割，在模板圖T的行x、列y被切割(0

ph，j.right=Dright+k

(10)

ph，j.left=Dleft-Tx，y-D.width-k

(11)

其中左，右，寬度，分別是矩形的左和右邊緣坐標(biāo)和寬度。由以上可以得出我們在進(jìn)行局部灰度編碼算法匹配時(shí)候的步驟為：對樣本模板T與做K2次剪切，并計(jì)算T(x，y)的特性；計(jì)算出基于搜索圖S所有的R-塊的特征；以C(i，j))確定搜索圖S大小(圖S的最右面或最低部有很大的可能被限制快重影)；對于每塊限制C(i，j))的模塊，包含在R塊排序的特征編碼矩陣A(C(i，j))，再對模板T的K2剪切后的有序特征集做有序比較。發(fā)現(xiàn)限制塊C(i，j))與裁剪模板T(x，y)的最相似的特性；重新有序比較對C(i，j))與模板T(x，y)的特征值。用兩個一維數(shù)組linecolL來表示累計(jì)矩陣A(C(i，j))各行、列的特征比較結(jié)果；求得限制塊C(i，j))內(nèi)匹配子區(qū)域D的邊界，需要對linecolL數(shù)組做邊緣檢測濾波；求出模板T在搜索圖S中匹配的參考點(diǎn)。由D與限制塊C(i，j))的相對位置關(guān)系與裁剪情況T(x，y)得出。

2 結(jié)果分析

2.1 圖像匹配結(jié)果

以網(wǎng)絡(luò)上下載的遼寧對外經(jīng)貿(mào)學(xué)院的正門圖像(簡稱“ZM”)做為實(shí)驗(yàn)對象。第一步，輸入源圖像讀出兩個圖像ZM1和ZM0，如圖4。以這兩個圖像為匹配的模板。

圖4 從Matlab中提取目標(biāo)文件

第二步：選取ZM0/ZM1中的各一個區(qū)域，定義新的名稱。(選取的圖像區(qū)域要事先選定好，不能太過偏離圖像特征區(qū)域，以免實(shí)驗(yàn)的匹配效果不佳)顯示選中的區(qū)域圖像。第三步，在兩幅圖像中進(jìn)行歸一化互相關(guān)計(jì)算。就是比較匹配圖像和待匹配圖像之間的互相關(guān)點(diǎn)，然后確定互相關(guān)點(diǎn)的峰值；最后確定待匹配圖像在匹配圖像的位置，但該計(jì)算能更直接的顯示圖像特征點(diǎn)。通過Matlab軟件顯示一個三維的峰值圖像，找到圖像最佳匹配點(diǎn)，特征點(diǎn)結(jié)果如圖5所示。

圖5 相似度比較峰值-特征點(diǎn) 圖6 圖像匹配結(jié)果

第四步，確定圖像最大匹配點(diǎn)，繼續(xù)進(jìn)行圖像的線性預(yù)算，為后續(xù)的圖像匹配做準(zhǔn)備。第五步，繼續(xù)為最后的圖像匹配做準(zhǔn)備。在圖像內(nèi)提取區(qū)域，找出區(qū)域?qū)儆谠磮D像的哪部分，提取出區(qū)域和原圖像進(jìn)行比較。第六步，為防止圖像匹配中可能出現(xiàn)圖像的不規(guī)則，圖像傾斜或者畸變，導(dǎo)致進(jìn)行圖像匹配時(shí)間延遲。先定義一個零矩陣，把圖像定義在一個黑色的背景下，方便圖像的匹配，使圖像在匹配中可以以點(diǎn)的形式一點(diǎn)點(diǎn)匹配，防止圖像在匹配后出現(xiàn)的畸變，省去匹配后的校正過程。第七步，先是圖像的灰度處理，然后設(shè)計(jì)結(jié)果顯示。把彩色圖像匹配到灰色圖像中，結(jié)果如圖6所示。

2.2 耗時(shí)性比較分析結(jié)果

誤差平方和算法的優(yōu)點(diǎn)，計(jì)算簡單，易學(xué)易用；缺點(diǎn)是計(jì)算量比較大，需要的時(shí)間比較久。不滿足匹配快速的要求，而且匹配原理簡單，容易受到外界噪聲的干擾。序貫相似性算法的優(yōu)點(diǎn)，各步驟的計(jì)算量要比誤差平方和快2-3倍；缺點(diǎn)是時(shí)間復(fù)雜度高，對搜索圖尺寸要求比較高?？偟膩碚f這兩種算法僅是基于灰度信息的相似性來比較差值，需要比較大量的像素點(diǎn)，所以計(jì)算量還是比較大的，達(dá)不到快速匹配的目的。而局部灰度編碼算法把要匹配的圖像劃分割成若干塊，然后計(jì)算每塊的灰度值，接著把整個圖像的局部灰度值按照順序劃分排序，進(jìn)行編碼。最后和模板圖像進(jìn)行比較，實(shí)現(xiàn)圖像的匹配。由于把圖像從空間上的層次轉(zhuǎn)換到編碼的層次，所以它的計(jì)算量有了很大的縮減，速度有極大的提高(見表1)。所以說局部灰度編碼算法還是可以達(dá)快速匹配(計(jì)算量小、匹配時(shí)間短、匹配精確)的要求。為了比較經(jīng)典的圖像匹配算法與深度學(xué)習(xí)算法的耗時(shí)性能，選取了魯棒性較好的基于學(xué)習(xí)的不變特征變換算法(LIFT)[8]進(jìn)行圖像匹配分析。LIFT算法采用了一種改進(jìn)的SIFT圖像特征點(diǎn)提取技術(shù)，通過Kd-Tree特征結(jié)構(gòu)、BBF搜索策略和HOUGH聚類進(jìn)行圖像匹配，完成圖像匹配耗時(shí)為1324.210ms。

表1 各個算法運(yùn)行時(shí)間記錄(ms)

3 結(jié)論

圖像匹配將計(jì)算機(jī)視覺、多維信號處理和數(shù)值計(jì)算緊密聯(lián)合形成了密切相關(guān)的近領(lǐng)域交叉技術(shù)。本文所使用的灰度圖像匹配方法的基礎(chǔ)是圖像的相似度，即灰度信息所代表的灰度值的大小之間的關(guān)系。尋找塊匹配灰色信息區(qū)域的相似度的大小，可以用波形的峰值確定最大相似度區(qū)域以提高搜索的效率和準(zhǔn)確性。通過測試發(fā)現(xiàn)，傳統(tǒng)的模板匹配算法和序貫相似性算法具有較好的魯棒性，而序貫相似性所要的時(shí)間要比傳統(tǒng)的模板匹配算法少得多。傳統(tǒng)的模板匹配算法的主要時(shí)間都用在匹配圖像和模板圖像之間的平滑過程，序貫相似性算法則首先設(shè)定了閾值，閾值越是接近相似度最高點(diǎn)，匹配的時(shí)間越短，精確度也越高。而基于學(xué)習(xí)的不變特征變換算法(LIFT)盡管具有較好的魯棒性[11]，但復(fù)雜的運(yùn)算過程增加了圖像匹配的耗時(shí)。所以，相對于一般傳統(tǒng)的模板匹配算法而言，序貫相似性已經(jīng)可以實(shí)現(xiàn)圖像的快速匹配的要求。