模板匹配的一種快速算法

【信息科學與控制工程】

模板匹配的一種快速算法

戴憲策，劉昌錦

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

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

關鍵詞：模板匹配；降采樣；分塊FFT

收稿日期：2014-07-10

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

doi:10.11809/scbgxb2015.01.031

中圖分類號：TP391.4

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

本文引用格式：戴憲策，劉昌錦.模板匹配的一種快速算法[J].四川兵工學報，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]。圖像匹配是計算機視覺中的一個重要組成部分，在圖像拼接、目標檢測與跟蹤、視頻穩(wěn)定、視頻監(jiān)控等領域具有廣泛的應用。匹配算法中的重要性能指標是結果的準確性和算法的速度，基于歸一化相關系數(shù)的模板匹配是一種常用的算法，結果準確，穩(wěn)定性好。但是在當前圖像質(zhì)量越來越高，像素點數(shù)越來越多的情況下，算法在匹配速度方面還有待提高。本文據(jù)此提出了基于降采樣和分塊FFT的快速匹配算法。

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

1.1算法原理

(1)

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

1.2傅里葉變換

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

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

圖1　第級蝶形運算單元

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

其中，F(xiàn)*(u,v)表示F(u,v)的共軛。可以利用這一關系簡化計算。

1.3平方積分圖像

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

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

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)所在列縱坐標不大于y的點像素值的平方和。利用平方積分圖像，可以很快計算待匹配圖像的能量值：

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

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

2算法優(yōu)化

2.1降采樣

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

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

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

2.2分塊傅里葉變換

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

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

圖2　計算量比較

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

圖3　算法流程

3實驗驗證

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

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

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

圖5　匹配結果

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

表1　算法時間比較

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

4結論

參考文獻：

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

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

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

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

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

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

(責任編輯楊繼森)