改進(jìn)模板匹配的快速識(shí)別算法

李長有，付惠琪，陳國璽

(1.河南理工大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，河南 焦作454000；2.焦作市技師學(xué)院 電氣工程系，河南 焦作 454000)

0 引 言

模板匹配是計(jì)算機(jī)視覺領(lǐng)域中對(duì)目標(biāo)圖像進(jìn)行識(shí)別和理解的重要方法[1]，它是對(duì)模板圖像和目標(biāo)圖像進(jìn)行相似度的檢測[2]。傳統(tǒng)模板匹配算法在匹配過程中對(duì)噪聲比較敏感，因此，消除噪聲的干擾至關(guān)重要[3]。由于傳統(tǒng)模板匹配在運(yùn)算效率和魯棒性方面存在一定的缺陷，近年來，許多學(xué)者對(duì)其進(jìn)行了大量的研究。N.D.Salih等[4]提出利用快速FFT變換結(jié)合區(qū)域生長分割進(jìn)行圖像的目標(biāo)識(shí)別；YE Y等[5]利用像素的局部特征，結(jié)合三維快速傅里葉變換在頻域上進(jìn)行相似性度量；LI C等[6]提出一種圖像相關(guān)與卡爾曼預(yù)測結(jié)合的方法，加快目標(biāo)的識(shí)別速度；B.G.Shin等[7]利用基于灰度索引表的快速穩(wěn)健模板匹配算法，可以在噪聲環(huán)境中找到圖像的特定區(qū)域；LIU B等[8]提出一種八角形星型查詢模板算法，該算法大大減少了圖像搜索空間，從而加快了算法的運(yùn)行速度；S.K.Sahani等[9]利用兩階段搜索法對(duì)圖像進(jìn)行快速識(shí)別，有效地確定相關(guān)點(diǎn)的精確性和魯棒性；A.Emlek等[10]利用可變窗口對(duì)圖像邊緣可變區(qū)域進(jìn)行匹配，從而加快了算法的匹配速度；J.Y.Kim等[11]利用改進(jìn)的hausdorff距離作為相似性度量函數(shù)，降低了算法的復(fù)雜程度。上述方法在較強(qiáng)噪聲環(huán)境下，匹配速度和準(zhǔn)確率往往不太理想，并且其相似度函數(shù)具有一定的復(fù)雜性，因而降低了算法的運(yùn)行速度。為了更好地降低較強(qiáng)噪聲的影響，改善算法的運(yùn)行速度，本文提出一種改進(jìn)模板匹配的快速識(shí)別算法。該算法采用改進(jìn)的低通濾波器濾除圖像中的噪聲，使用同倫骨架算法對(duì)二值圖像進(jìn)行細(xì)化，減少冗余的邊緣點(diǎn)，采用加權(quán)的Hamming Distance作為相似度檢測函數(shù)，減少算法的復(fù)雜程度，并且采用設(shè)置的閾值，改善算法的運(yùn)行速度。

1 算法原理

1.1 改進(jìn)濾波器原理

針對(duì)傳統(tǒng)模板匹配在較強(qiáng)噪聲匹配過程中出現(xiàn)的誤匹配現(xiàn)象，提出一種改進(jìn)的線性平滑濾波器對(duì)圖像進(jìn)行噪聲濾除，其原理是利用n×n的相同元素模板A和模板覆蓋下的原圖像f(x，y)運(yùn)算得到子圖像f1(i,j)，中心像素為E(i，j)，然后子圖像與單位矩陣I的列向量運(yùn)算，可以得到新的圖像f2(i,j)，f2(i,j)與單位矩陣I的列向量再運(yùn)算得到圖像f3(i,j)，用此時(shí)圖像f3(i,j)的平均值與中心像素E(i，j)比較，數(shù)學(xué)模型為

(1)

β1=f1(i,j)*i1=

[a11x11a21x21…an1xn1]T，

(2)

(3)

由公式(2)可以寫出剩余項(xiàng)，即f2(i,j)，則

(4)

則去掉最大最小像素的f3(i,j)為

f3(i,j)={sort[f2(i,j)]}*I(i3,…,in×n-3)=

[f2max(i,j),f2(i,j+1),…,f2min(i,j+(n×n)-1)]*

[i3,…,in×n-3]=[f2(i,j+2),…,f2min(i,j+

(n×n)-3)]，

(5)

(6)

(7)

式中：(i1,i2,…,in)為單位矩陣I的列向量；sort為排序函數(shù)；E(i,j)為圖像的中心點(diǎn)像素。

文中相同元素矩陣A使用的是3×3矩陣。

1.2 同倫骨架算法細(xì)化邊緣

骨架思想由H.Blum[12]引入，并稱之為中軸變換或骨架?；凇安莸鼗鹧妗蹦Ｐ秃妥畲笄蚬羌躘13]得到的骨架是不同倫的，即不保持原來集合的連通性，并且在離散平面內(nèi)骨架線條要寬于一個(gè)像素。

圖像細(xì)化和粗化是擊中擊不中變換的一個(gè)應(yīng)用，對(duì)于圖像f(x,y)用復(fù)合結(jié)構(gòu)元素M進(jìn)行順序細(xì)化時(shí)可以得到一個(gè)同倫的目標(biāo)骨架。

順序細(xì)化的結(jié)構(gòu)元素L(n)和D(n)如圖1所示，利用圖1中的8個(gè)結(jié)構(gòu)元素對(duì)圖像多次細(xì)化，圖像能夠保持拓?fù)渫瑐惽沂諗坑跀嗝鏋閱蝹€(gè)像素寬度及8鄰域是連通的目標(biāo)骨架。

圖1結(jié)構(gòu)元素L={L1,L2,L3,L4}分別消除目標(biāo)上方、右方、下方和左方的外層圖像，D={D1,D2,D3,D4}分別消除目標(biāo)右上、右下、左下和左上的外層圖像。其中“*”為該元素在匹配過程中沒有被用到，取值可以任意。

同倫骨架[14]算法能夠保持圖像骨架集合的連通性和拓?fù)湫?，其定義為

E{f(c,y),L,D,k}=f(x,y)Θ{M(n)}k=

{(((…((f(x,y)ΘL1)ΘD1)…)ΘL4)ΘD4)}k，

(8)

式中：Θ為結(jié)構(gòu)元素與圖像之間的腐蝕運(yùn)算；k為細(xì)化次數(shù)，圖像復(fù)雜程度不同，k值不同。

1.3 改進(jìn)的Hamming Distance

為了解決特征向量相似度函數(shù)過于復(fù)雜，并加快算法的運(yùn)行速度，本文提出用改進(jìn)的Hamming Distance(海明距離)作為模板圖像和目標(biāo)圖像的相似度函數(shù)，以此減少算法的復(fù)雜程度，從而提高運(yùn)行速度。

Hamming Distance[15]是用來計(jì)算兩個(gè)等長二進(jìn)制序列中對(duì)應(yīng)位數(shù)不同的數(shù)字位置個(gè)數(shù)，假設(shè)g={g1,…,gm}和v={v1,…,vn}是兩個(gè)不同點(diǎn)集，當(dāng)m=n時(shí)，海明距離Hd公式為

Hd=∑(g⊕v)，

(9)

式中，符號(hào)“⊕”為兩個(gè)序列異或運(yùn)算。

為了更好地降低圖像噪聲帶來的影響，本文采用加權(quán)海明距離作為相似度函數(shù)，當(dāng)模板圖像大小為m×n時(shí)，則其數(shù)學(xué)模型為

(10)

式中：round為取整函數(shù)；Gtemplate、Vsub-image分別為模板圖像和目標(biāo)圖像子圖像。

1.4 閾值的確定原則

模板匹配是模板圖像在整幅目標(biāo)圖像上逐行逐列進(jìn)行移動(dòng)并進(jìn)行相關(guān)性計(jì)算的過程，在模板圖像移動(dòng)過程中有很多非目標(biāo)區(qū)域的像素也參與運(yùn)算，因此,降低了算法的運(yùn)行速度。為了更好地減少算法的運(yùn)行時(shí)間，在進(jìn)行模板匹配時(shí)把大小為m×m的模板分成兩塊并與設(shè)置的閾值Tk進(jìn)行比較，以此提高算法的運(yùn)行效率。將模板圖像分成兩塊，并取出R=round[(m×m)/2]個(gè)像素構(gòu)成的圖像，用相似度檢測函數(shù)計(jì)算出的向量距離值與閾值進(jìn)行比較，從而減少算法的運(yùn)行時(shí)間，提高運(yùn)行效率。通過實(shí)驗(yàn)選取閾值Tk的基本原則為

(11)

本文算法的流程圖如圖2所示。

圖2 算法流程圖

2 結(jié)果與分析

為了驗(yàn)證本文算法的有效性，選擇52幅不同背景下的圖像作為實(shí)驗(yàn)對(duì)象，并在圖像中加入了σ1=0.08的椒鹽噪聲和均值m=0.02、方差v=0.001的高斯噪聲。使用MATLAB R2016a軟件平臺(tái)，并用Intel Core i5-2450M CPU@2.5 GHz處理器對(duì)不同背景的噪聲圖像進(jìn)行目標(biāo)識(shí)別。其中在傳統(tǒng)模板匹配過程中，使用傳統(tǒng)的中值濾波器對(duì)圖像進(jìn)行降噪，文獻(xiàn)[11]中Canny算子的高低閾值人工設(shè)置，其高低閾值分別為0.4和0.16，高斯濾波器中的σ=0.9。本文算法使用N.Otsu[16]確定Canny算子的高低閾值，與其他模板匹配算法在運(yùn)行效率和算法魯棒性方面進(jìn)行比較，實(shí)驗(yàn)效果對(duì)比如圖3所示。通過實(shí)驗(yàn)對(duì)比圖能夠很容易看出，本文算法在目標(biāo)識(shí)別過程魯棒性較好，為了更好地說明本文算法的有效性和魯棒性，表1列出了算法的平均運(yùn)行時(shí)間和識(shí)別準(zhǔn)確率。

圖3第一列表示目標(biāo)圖像和模板圖像，紅色標(biāo)識(shí)的為模板圖像;第二列是噪聲環(huán)境下傳統(tǒng)NCC算法的效果圖，該算法對(duì)不同噪聲圖像目標(biāo)識(shí)別有較好的魯棒性，但從表1可以看出，該算法在識(shí)別準(zhǔn)確率方面存在一定缺陷，并且平均運(yùn)行時(shí)間比其他算法運(yùn)行時(shí)間長，從而導(dǎo)致該算法運(yùn)行速度比較慢；第三列是文獻(xiàn)[6]中FNNPROD算法的效果圖，該算法對(duì)噪聲的魯棒性相對(duì)較差，存在一定誤匹配現(xiàn)象。但從表1可以看出，該算法的平均運(yùn)行時(shí)間相對(duì)較少，運(yùn)算速度比較快；第四列是文獻(xiàn)[11]可改進(jìn)的hausdorff算法效果圖，對(duì)噪聲的魯棒性比較差，出現(xiàn)了誤匹配現(xiàn)象，但從表1可以看出，該算法的平均運(yùn)行時(shí)間較少，運(yùn)行速度較快；第五列是本文算法的效果圖，從圖3可以看出，本文算法對(duì)噪聲有較好的魯棒性，表1更進(jìn)一步說明了本文算法的優(yōu)越性，算法的識(shí)別準(zhǔn)確率與平均運(yùn)行時(shí)間較少，運(yùn)行速度較快。

表1 算法的有效性對(duì)比

圖3 實(shí)驗(yàn)效果對(duì)比

Fig.3 Comparisons of experimental results

為了更進(jìn)一步說明本文算法的魯棒性，對(duì)不同背景下的噪聲圖像進(jìn)行實(shí)驗(yàn)，本文濾波器與傳統(tǒng)濾波器濾除噪聲后的效果圖如圖4所示。從圖4可以看出，本文濾波器能夠?yàn)V除圖像中較強(qiáng)的噪聲，并根據(jù)文獻(xiàn)[17]對(duì)圖像質(zhì)量的評(píng)價(jià)方法評(píng)價(jià)本文濾波器濾除噪聲的能力，以及濾除噪聲后的圖像與目標(biāo)圖像的相似程度。圖5所示分別計(jì)算了圖像峰值信噪比(PSNR)和結(jié)構(gòu)相似性指數(shù)測量(SSIM)，從而佐證本文算法對(duì)噪聲的魯棒性。其中PSNR表示濾波器對(duì)噪聲的去除能力，其值越大，表示對(duì)噪聲的濾除能力越強(qiáng)，圖像的失真也越小。從圖5可以看出，本文設(shè)計(jì)的濾波器比高斯濾波器和均值濾波器的PSNR值都大，與中值濾波器相差不大，表明本文算法的去噪聲能力較強(qiáng)，圖像在濾除噪聲后比較清晰。

圖4 本文濾波器與傳統(tǒng)濾波器對(duì)比

SSIM是度量兩幅圖像的相似性，它是通過檢測圖像3個(gè)因素(相關(guān)性、亮度和對(duì)比度)的損失，比較兩幅圖像的相似性，其值介于-1到1內(nèi)，計(jì)算數(shù)值越接近1，表示圖像的相似度越高，圖像噪聲的濾除越好。從圖5可以看出，本文算法的SSIM值相對(duì)較大，表明本文算法對(duì)噪聲消除后的圖像失真相對(duì)較小，從而佐證了本文算法的魯棒性。

3 結(jié) 語

本文提出的快速識(shí)別算法對(duì)較強(qiáng)噪聲干擾圖像能夠很好地識(shí)別出目標(biāo)位置，并且算法運(yùn)行速度較快。通過改進(jìn)的低通濾波器濾除噪聲，降低噪聲對(duì)圖像的干擾，提高了算法的識(shí)別率，使用改進(jìn)海明距離作為圖像的特征向量檢測函數(shù)，降低了算法的復(fù)雜程度，并且提出了閾值的選取原則以及使用同倫骨架算法，大大提高了算法的運(yùn)行速度。因此，本文算法可以彌補(bǔ)傳統(tǒng)NCC算法、文獻(xiàn)[6]和[11]算法的不足，并且能夠提高算法的運(yùn)行速度和識(shí)別準(zhǔn)確率，可為目標(biāo)識(shí)別、安防監(jiān)控和其他工業(yè)應(yīng)用提供一定參考。

圖5 不同濾波器噪聲濾除能力對(duì)比