【信息科學(xué)與控制工程】

模板匹配的一種快速算法

戴憲策，劉昌錦

(新星技術(shù)研究所，合肥230031)

摘要：圖像匹配是計(jì)算機(jī)視覺中的重要應(yīng)用之一，常用的算法是基于歸一化相關(guān)系數(shù)的模板匹配算法；針對原有算法計(jì)算量大，匹配時(shí)間長的問題，提出了基于降采樣和分塊快速傅里葉變換(FFT)的方法，對原始算法進(jìn)行了改進(jìn)，并設(shè)計(jì)了兩組對比實(shí)驗(yàn)進(jìn)行驗(yàn)證；結(jié)果證明算法不僅匹配準(zhǔn)確，對外界條件具有良好的適用性，而且匹配時(shí)間縮短為原始算法的1/5，提高了匹配速度。

關(guān)鍵詞：模板匹配；降采樣；分塊FFT

收稿日期：2014-07-10

作者簡介：戴憲策(1990—)，男，碩士研究生，主要從事立體視覺研究。

doi:10.11809/scbgxb2015.01.031

中圖分類號：TP391.4

文章編號：1006-0707(2015)01-0111-04

本文引用格式：戴憲策，劉昌錦.模板匹配的一種快速算法[J].四川兵工學(xué)報(bào)，2015(1):111-113.

Citationformat:DAIXian-ce,LIUChang-jin.FastTemplate-MatchingAlgorithm[J].JournalofSichuanOrdnance,2015(1):111-113.

FastTemplate-MatchingAlgorithm

DAIXian-ce,LIUChang-jin

(NewStarInstituteofAppliedTechnology,Hefei230031,China)

Abstract:Image matching is one of the important applications in computer vision. Common algorithm of template-matching is based on normalized correlation coefficient. However, the origin algorithm had the problem of large amount of calculation and long matching time. In order to optimize it, a new method based on down sampling and blocking FFT was proposed. Two experiments were designed for comparison. The results show that the new algorithm not only has an accurate matching result and a fine flexibility of the environment, but also can reduce the matching time by 4/5.

Keywords:templatematching;downsampling;partitioningFFT

根據(jù)已知模板圖像，在另外一幅圖中尋找子圖像的過程稱為圖像匹配[1]。圖像匹配是計(jì)算機(jī)視覺中的一個(gè)重要組成部分，在圖像拼接、目標(biāo)檢測與跟蹤、視頻穩(wěn)定、視頻監(jiān)控等領(lǐng)域具有廣泛的應(yīng)用。匹配算法中的重要性能指標(biāo)是結(jié)果的準(zhǔn)確性和算法的速度，基于歸一化相關(guān)系數(shù)的模板匹配是一種常用的算法，結(jié)果準(zhǔn)確，穩(wěn)定性好。但是在當(dāng)前圖像質(zhì)量越來越高，像素點(diǎn)數(shù)越來越多的情況下，算法在匹配速度方面還有待提高。本文據(jù)此提出了基于降采樣和分塊FFT的快速匹配算法。

1算法原理與實(shí)現(xiàn)

1.1算法原理

(1)

從表達(dá)式中可以看出，直接計(jì)算相關(guān)系數(shù)需要大量的乘法和加法，模板圖像和待匹配圖像越大，所需加法和乘法的數(shù)量就越多，而且增長急劇。每到新的一點(diǎn)，相關(guān)值、平方和等參數(shù)需要重新計(jì)算，十分浪費(fèi)。因此，快速算法十分必要。傅里葉變換可以將相關(guān)計(jì)算轉(zhuǎn)化到頻域的相乘，其快速算法能夠大大減少計(jì)算量[3-5]。能量值的計(jì)算可以通過一次計(jì)算模板圖像和待匹配圖像的平方積分圖像來減少計(jì)算量[3,6]。

1.2傅里葉變換

傅里葉變換是由法國數(shù)學(xué)家傅里葉提出的，在許多領(lǐng)域有著非常廣泛的應(yīng)用。大小為M×N的二維數(shù)字圖像f(x,y) 與其傅里葉變換F(u,v)之間的關(guān)系為

快速傅里葉變換是傅里葉變換的快速算法，是由Cooley和Turkey在1965年提出的?？焖俑道锶~變換大大簡化了傅里葉變換的所需的計(jì)算量。其核心是蝶形運(yùn)算單元，其結(jié)構(gòu)圖1所示。

圖1　第級蝶形運(yùn)算單元

f(x,y) °h(x,y)?F*(u,v)H(u,v)

其中，F(xiàn)*(u,v)表示F(u,v)的共軛?？梢岳眠@一關(guān)系簡化計(jì)算。

1.3平方積分圖像

平方積分圖像是原圖像像素值平方的累加圖像，平方積分圖像中每一點(diǎn)的值等于原圖像自左上角開始到該點(diǎn)的矩形框中所有點(diǎn)平方和的相加，即：

平方積分圖像可以由下列公式快速計(jì)算：

c(x,y)=c(x,y-1)+I2(x,y)

II(x,y)=II(x-1,y)+c(x,y)

其中，c(x,y)表示的是待匹配圖像中(x,y)所在列縱坐標(biāo)不大于y的點(diǎn)像素值的平方和。利用平方積分圖像，可以很快計(jì)算待匹配圖像的能量值：

II(x+i,y+j)-II(x+i,y)-II(x,y+j)

快速傅里葉變換和積分圖像快速算法的應(yīng)用，可以在很大程度上減少計(jì)算量，增加計(jì)算速度，但是隨著圖像質(zhì)量越來越高，簡單應(yīng)用快速傅里葉變換和積分圖像快速算法仍不能滿足要求，因此本文提出了降采樣和分塊FFT的優(yōu)化方法。

2算法優(yōu)化

2.1降采樣

現(xiàn)在的成像設(shè)備，如相機(jī)、手機(jī)攝像頭、網(wǎng)絡(luò)攝像頭等都有很高的像素點(diǎn)數(shù)，成像質(zhì)量高，紋理豐富，細(xì)節(jié)清晰，符合人眼視覺的需要。但是對于計(jì)算機(jī)處理卻不一定是必須的。低質(zhì)量、單通道的灰度圖像也能進(jìn)行完成匹配功能。因此，在匹配之前可以對圖像進(jìn)行降采樣的預(yù)處理，在保證匹配正確的基礎(chǔ)上，能夠進(jìn)一步縮小計(jì)算量和存儲(chǔ)空間。

以2倍降采樣為例，通過下列公式對待匹配圖像I(x,y)和模板圖像T(x,y)進(jìn)行降采樣

此時(shí)匹配時(shí)所需的存儲(chǔ)空間是原來的1/4，快速傅里葉變換所需的計(jì)算量是原來的1/5左右。極大的縮短了計(jì)算時(shí)間。降采樣的結(jié)果與準(zhǔn)確結(jié)果之間可能存在偏差，但是根據(jù)第3部分的實(shí)驗(yàn)結(jié)果，產(chǎn)生的偏差在可接受范圍內(nèi)。

2.2分塊傅里葉變換

一般來說，模板圖像是待匹配圖像中的一小部分，兩幅圖像尺寸上有很大的比例關(guān)系。在運(yùn)用快速傅里葉變換進(jìn)行相關(guān)系數(shù)計(jì)算的時(shí)候，需要對模板圖像進(jìn)行大量的補(bǔ)零操作，使其和待匹配圖像的大小一致，這不僅導(dǎo)致了計(jì)算量的浪費(fèi)，而且?guī)砹舜鎯?chǔ)空間的增加。對待匹配圖像進(jìn)行分塊處理，在保證相關(guān)系數(shù)結(jié)果一致的基礎(chǔ)上，不僅能夠減少存儲(chǔ)空間，而且還能夠進(jìn)一步提高計(jì)算速度。

包括待匹配圖像和模板圖像的一次傅里葉變換和共軛相乘結(jié)果的一次傅里葉逆變換。

圖2　計(jì)算量比較

從圖2中可以看出，分塊的計(jì)算量要遠(yuǎn)小于不分塊的情況。上圖只是簡單分成4塊的比較，如果分成多塊，計(jì)算量還會(huì)進(jìn)一步減少。因此，本文算法的流程如下(圖3)。

圖3　算法流程

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

為驗(yàn)證算法的準(zhǔn)確性和速度，本文在Matlab下設(shè)計(jì)了兩個(gè)對比實(shí)驗(yàn),并在主頻2.4GHz,內(nèi)存1G的PC機(jī)上進(jìn)行了實(shí)驗(yàn)。本文選取了不同光照條件下的待匹配圖像與模板圖像進(jìn)行匹配操作，待匹配圖像尺寸為640×480，模板圖像尺寸為68×54，選用圖片如下(圖4)：

實(shí)驗(yàn)1：準(zhǔn)確度檢驗(yàn)實(shí)驗(yàn)，檢驗(yàn)在不同外界條件下本文算法的準(zhǔn)確性。根據(jù)本文算法得到的匹配結(jié)果如下(圖5)：

白框中的區(qū)域即為模板在待匹配圖像中的位置，從圖中可以看出，本文算法匹配的結(jié)果正確，而且非常穩(wěn)定，可以適應(yīng)不同的光照條件。

圖5　匹配結(jié)果

實(shí)驗(yàn)2：匹配時(shí)間比較。本文算法與沒有經(jīng)過降采樣處理和分塊的算法之間的時(shí)間比較見表1。

表1　算法時(shí)間比較

從表1中可以看出，本文算法所用時(shí)間是原始算法的1/5 左右，算法速度有了很大的提高。

4結(jié)論

參考文獻(xiàn)：

[1]岡薩雷斯.數(shù)字圖像處理[M].2版.北京:電子工業(yè)出版社,2010.

[2]GaryBradski,AdrianKaehler.學(xué)習(xí)OpenCV(中文版)[M].于仕琪,劉瑞楨,譯.北京:清華大學(xué)出版社,2009.

[3]殷松峰,王一程,曹良才,等.基于快速傅里葉變換和積分圖的快速相關(guān)匹配[J].光子學(xué)報(bào),2010,39(12):2246-2250.

[4]陳松柏.實(shí)時(shí)的歸一化相關(guān)匹配算法[J].信息與電子工程,2006,4(6):461-463.

[5]楊勇兵,何緒昊,戚其豐,等.一種新型的快速模板匹配算法[J].電子工藝技術(shù),2010,31(3):128-131.

[6]楊喜東.基于頻域分析的圖像匹配定位算法的研究[J].通信電源技術(shù),2012,29(4):20-22,43.

(責(zé)任編輯楊繼森)