一種模板匹配的改進(jìn)算法

張?zhí)祜w，龍海燕，丁 嬌，張 磊

（安徽信息工程學(xué)院，安徽 蕪湖 241000）

1 引言

模板匹配理論是按照相關(guān)策略，根據(jù)已知模塊在搜索圖像中尋找逼近模塊匹配的過(guò)程，是一種簡(jiǎn)單有效、使用廣泛的圖像處理方法[1-3].模板匹配主要通過(guò)模板按照一定的準(zhǔn)則在待匹配圖像中尋找出相似性最大的對(duì)象，使用的準(zhǔn)則有很多，例如平方差、相關(guān)、相關(guān)系數(shù)、歸一化平方差、歸一化相關(guān)、歸一化相關(guān)系數(shù)等.為了使運(yùn)算過(guò)程既簡(jiǎn)單又快速，本文使用歸一化平方差作為模板匹配的相似性度量.

2 模板匹配原理

本文模板匹配采用將模板在待匹配圖中按照從左到右、從上到下的原則掃描待匹配圖，在掃描過(guò)程中用歸一化平方差準(zhǔn)則計(jì)算兩者的匹配度，以確定是否有最適合的對(duì)象.模板和待匹配圖像可以直接進(jìn)行歸一化平方差運(yùn)算，但是這樣可能會(huì)使得一些不必要的特征如灰度信息等讓運(yùn)算結(jié)果出現(xiàn)偏差甚至是出現(xiàn)錯(cuò)誤匹配.而邊緣檢測(cè)既能減少待匹配圖像的部分干擾信息，又能保留圖像中物體的形狀信息，所以在做歸一化平方差之前，我們需要對(duì)模板和待匹配圖做一定的邊緣檢測(cè).

圖1 待匹配圖

圖2 模板

3 歸一化平方差

為使計(jì)算的數(shù)據(jù)在一定的范圍內(nèi)變化以及使計(jì)算值能夠快速收斂到想要的結(jié)果，本文使用歸一化平方差作為模板匹配的準(zhǔn)則，下面首先簡(jiǎn)單介紹一下歸一化平方差.平方差能夠描述兩個(gè)像素點(diǎn)p1、p2的相似性，如果像素點(diǎn)p1、p2完全相同，那么平方差值為0；如果像素點(diǎn)p1、p2差別越大，平方差值就越大.對(duì)于二維圖像，如果兩個(gè)圖像塊的平方差的和越小，那么表示這兩個(gè)圖像塊越接近；當(dāng)結(jié)果為零時(shí)，可以認(rèn)為兩圖像塊完全相同.本文采用的歸一化平方差如式（1）所示：

通過(guò)該式能夠看出，歸一化平方差值越小，表示待匹配的圖像與模板越相近.

4 邊緣檢測(cè)

使用模板匹配時(shí)，我們可以不對(duì)模板和待匹配圖像進(jìn)行處理而直接進(jìn)行匹配，這樣在一些情況下可以正確匹配，而在其他一些情況下會(huì)由于光照等條件的影響使得目標(biāo)不能正確匹配，其魯棒性不好.所以我們常常需要對(duì)模板和待匹配圖像做進(jìn)一步的處理.由于邊緣是位置的標(biāo)志，對(duì)灰度的變化不敏感，因此，邊緣可以作為圖像匹配的一個(gè)重要特征.在實(shí)時(shí)圖像處理中，使用Sobel算子對(duì)圖像進(jìn)行邊緣檢測(cè)是常用的算法之一[4-5].Sobel算子是一種一階差分的邊緣檢測(cè)算子，其計(jì)算簡(jiǎn)單，能夠提供目標(biāo)相對(duì)準(zhǔn)確的邊緣信息，在實(shí)際計(jì)算中我們使用5x5的模板與圖像做卷積運(yùn)算，就可得到邊緣檢測(cè)圖像.5x5的Sobel算子x、y方向的模板如下表所示.

表1 Sobel x方向模板

表2 Sobel y方向模板

將模板x方向的Sobel運(yùn)算結(jié)果與待匹配圖像x方向的Sobel運(yùn)算結(jié)果運(yùn)用歸一化平方差的方法，得到結(jié)果Gx(i,j)，其中|Gx(i,j)|中的值越小的點(diǎn)，其相似性就越大，同理將模板y方向的Sobel運(yùn)算結(jié)果與待匹配圖像y方向的Sobel運(yùn)用歸一化平方差方法，得到結(jié)果為Gy(i,j)，其中|Gy(i,j)|中的值越小的點(diǎn)，其相似性同樣越大.我們既要考慮x方向的邊緣，也要考慮y方向的邊緣，所以最終匹配結(jié)果值用式（2）表示：

只要找到G(i,j)中的最小值，即MIN(G(i,j))，就是待匹配圖中與模板最匹配的目標(biāo)位置.此方法一定程度上可以減少模板與待匹配圖像中的噪聲、灰度變換的影響，尋找的位置相對(duì)準(zhǔn)確.能夠適用一些情況，但是當(dāng)圖像中含有高頻信息的噪聲時(shí)，則可能導(dǎo)致匹配的失敗.為了解決此問(wèn)題，我們需要對(duì)模板和待匹配圖像做進(jìn)一步優(yōu)化.

5 優(yōu)化模板和待匹配圖像

由于待匹配圖中可能含有高頻噪聲，經(jīng)過(guò)Sobel算子進(jìn)行邊緣檢測(cè)后并不能將其去除掉，所以需要進(jìn)一步的處理.本文提出對(duì)經(jīng)過(guò)Sobel算子邊緣檢測(cè)后的圖像進(jìn)一步作閾值化處理，如式（3）（4）所示：

其中，Gx(i,j)、Gy(i,j)分別為 x、y方向 Sobel算子，Th為所用閾值.

將經(jīng)過(guò)Sobel算子邊緣檢測(cè)后的待匹配圖像按照式（3）（4）進(jìn)行處理得到 Gx'、Gy'，然后將 Gx'、Gy'分別代入歸一化平方差公式（即式（1））進(jìn)行匹配，綜合考慮 x、y方向的邊緣檢測(cè)將 Gx'、Gy'代入式（2）得到G'，然后尋找G’中的最小值處的位置，就是與模板最相近的目標(biāo).本方法可以有效地抑制噪聲中的高頻部分，使得匹配的穩(wěn)定性及可靠性增強(qiáng).

6 實(shí)驗(yàn)分析

本文設(shè)計(jì)的實(shí)驗(yàn)是在連續(xù)的圖像序列中進(jìn)行匹配，圖像大小為640x480，實(shí)驗(yàn)軟件環(huán)境是在win7系統(tǒng)、VS2013平臺(tái)，實(shí)驗(yàn)的硬件環(huán)境是Intel(R)Core(TM)2 Duo CPU T6570，內(nèi)存 2G.在不同環(huán)境中測(cè)試物體跟蹤效果得到實(shí)驗(yàn)數(shù)據(jù).

實(shí)驗(yàn)一：在室內(nèi)分別用經(jīng)過(guò)Sobel算子邊緣檢測(cè)處理后的圖像與本文對(duì)其改進(jìn)的優(yōu)化算法實(shí)現(xiàn)對(duì)水杯的跟蹤，實(shí)驗(yàn)分別在圖像序列的第10幀，第50幀，第120幀，第121幀進(jìn)行截圖，從圖中可以看出Sobel邊緣檢測(cè)處理的圖像進(jìn)行匹配時(shí)，在第121幀時(shí)出現(xiàn)誤匹配而本文的改進(jìn)方法可以進(jìn)行正確跟蹤.

圖3 10幀匹配結(jié)果

圖4 30幀匹配結(jié)果

圖5 120幀匹配結(jié)果

圖6 121幀匹配結(jié)果

實(shí)驗(yàn)二：在室內(nèi)分別用經(jīng)過(guò)Sobel邊緣檢測(cè)處理后的圖像與本文對(duì)其的優(yōu)化算法實(shí)現(xiàn)對(duì)化妝品盒子的跟蹤，實(shí)驗(yàn)分別在圖像序列的第180幀，第210幀，第330幀，第343幀進(jìn)行截圖，從圖中可以看出Sobel邊緣檢測(cè)處理的圖像進(jìn)行匹配時(shí)，在第343幀時(shí)出現(xiàn)誤匹配而本文的改進(jìn)方法可以進(jìn)行正確跟蹤.

圖7 180幀匹配結(jié)果

圖8 210幀匹配結(jié)果

圖9 330幀匹配結(jié)果

圖10 343幀匹配結(jié)果

7 結(jié)論

本文提出的閾值化Sobel邊緣檢測(cè)后的模板與待匹配圖像的方法，能夠有效地實(shí)現(xiàn)對(duì)物體的正確匹配，并且具有一定的魯棒性，能夠較好地實(shí)現(xiàn)實(shí)時(shí)跟蹤.