結(jié)合小波金字塔的快速NCC圖像匹配算法

吳鵬， 徐洪玲，宋文龍

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040)

?

結(jié)合小波金字塔的快速NCC圖像匹配算法

吳鵬， 徐洪玲，宋文龍

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040)

針對傳統(tǒng)的歸一化互相關(guān)算法(NCC)計(jì)算量龐大、運(yùn)算速度慢、正確率較低等問題，本文提出一種基于小波金字塔搜索策略的快速NCC圖像匹配算法。該算法在歸一化互相關(guān)算法的基礎(chǔ)上，采用和表法分別計(jì)算圖像均值、圖像方差和圖像間的互相關(guān)來降低運(yùn)算的復(fù)雜度，減少算法的計(jì)算量；同時在選擇特征點(diǎn)匹配搜索策略時，構(gòu)造圖像小波金字塔結(jié)構(gòu)，利用分層匹配來提高圖像匹配的效率。與其他算法進(jìn)行對比，結(jié)果表明該算法獲得的匹配點(diǎn)連線效果更好，所用的時間也量化，證明該算法不僅能提高匹配速度，還能改善匹配精度。

圖像匹配；特征點(diǎn)；歸一化互相關(guān)匹配算法；匹配策略；小波金字塔；和表法；匹配速度；匹配精度

圖像匹配是計(jì)算機(jī)視覺和模式識別中一項(xiàng)重要而廣泛的應(yīng)用，利用相關(guān)的匹配算法在兩幅或者多福圖像之間識別同一特征點(diǎn)。隨著圖像匹配技術(shù)的逐步發(fā)展，國內(nèi)外的學(xué)者都對其進(jìn)行了深入的研究，并提出了許多圖像匹配算法[1-2]。經(jīng)典的匹配算法有：歸一化互相關(guān)(normalized cross-correlation， NCC)匹配算法、差的絕對值和(sum of absolute difference， SAD)相關(guān)算法、差的平方和(sum of square differences， SSD)相關(guān)算法等。其中NCC算法在現(xiàn)有相關(guān)匹配算法中應(yīng)用最為廣泛，具有較好的魯棒性，對光照強(qiáng)度的線性變化不太敏感，抗白噪聲干擾能力強(qiáng)，但其缺點(diǎn)是計(jì)算量大、匹配速度慢、錯誤匹配較多，并不符合系統(tǒng)實(shí)時性的要求[3-5]。

因此如何降低計(jì)算的復(fù)雜度，減少運(yùn)算過程中的計(jì)算量，提高匹配精度，已成為現(xiàn)在研究的難點(diǎn)和熱點(diǎn)問題。Lewis提出用兩個加和表的方法來來簡化NCC分母的計(jì)算量，但沒有改變分子的運(yùn)算復(fù)雜度[6]；Tsai等通過改進(jìn)了NCC的定義，構(gòu)造三個和表法來同時簡化分子和分母的計(jì)算量，但匹配精度并不高[7]；汪華琴針對歸一化互相關(guān)算法精度不高，采用分層匹配來提高搜索匹配的效率，但計(jì)算仍很復(fù)雜[8]。孫祖鑫等采用遞推與多模板思想構(gòu)建歸一化互相關(guān)快速算法，但匹配率并不是很理想[9]。針對以上問題，本文首先對傳統(tǒng)的歸一化互相關(guān)算法進(jìn)行改進(jìn)，減少計(jì)算量，同時在搜索策略上利用小波金字塔分層匹配的思想，分辨率由低到高，匹配由粗到細(xì)，提出一種基于小波金字塔搜索策略的快速NCC圖像匹配算法。

1 快速歸一化相關(guān)算法

1.1 歸一化互相關(guān)匹配算法

歸一化互相關(guān)算法(NCC)是一種常用的圖像

特征點(diǎn)匹配算法，其原理是根據(jù)兩幅圖像中特征點(diǎn)鄰域像素灰度值的相似性來匹配的，對于左圖像中的一點(diǎn)，計(jì)算其與右圖像中所有特征點(diǎn)的歸一化互相關(guān)系數(shù)，當(dāng)?shù)玫狡渲凶畲笾档狞c(diǎn)就為最佳匹配位置。

設(shè)W1和W2分別是圖像I1和圖像I2的兩個大小相同的匹配窗口，圖像大小為M×N，匹配窗口大小為m×n，u1和u2是匹配窗口內(nèi)像素灰度的均值。歸一化相關(guān)系數(shù)的定義形式通常有去均值和不去均值兩種[10-11]：

不去均值：

(1)

去均值：

(2)

式中： (x，y)∈M×N；r(x，y)的取值范圍為 -1～1，值越大表示相關(guān)程度越高。

雖然去均值的歸一化互相關(guān)圖像匹配算法的計(jì)算量比較大，但是它對于灰度和較小的幾何畸變存在不變性，同時具有很強(qiáng)的抗噪聲干擾的能力，因此本文選用去均值的歸一化互相關(guān)匹配算法。在本文中，對兩幅同樣大小的圖像，使用Harris算法進(jìn)行特征點(diǎn)檢測，傳統(tǒng)的歸一化互相關(guān)方法行進(jìn)特征點(diǎn)匹配，但匹配結(jié)果精度不高，且所用時間長。本文在現(xiàn)有算法的基礎(chǔ)上，針對NCC算法，通過構(gòu)建3個加和表的方法，減少分子分母計(jì)算量，并引入圖像小波金字塔分層結(jié)構(gòu)，提高搜索匹配的效率。

1.2 快速歸一化互相關(guān)算法

傳統(tǒng)的歸一化互相關(guān)匹配算法進(jìn)行特征點(diǎn)匹配時，需要對特征點(diǎn)進(jìn)行遍歷搜索，共需要3mnMN加運(yùn)算和2mnMN乘運(yùn)算，計(jì)算量非常龐大。因此在本文中通過構(gòu)建加和表[12]來減少匹配過程中計(jì)算量，加快運(yùn)算速度。

快速NCC匹配算法在計(jì)算歸一化互相關(guān)系數(shù)時，將公式變換為

(3)

從式(3)可以看出來，方程的歸一化互相關(guān)操作涉及源圖像W(x，y)和模板圖像T(x，y)的平均值，平方以及W和T之間的互相關(guān)的計(jì)算。

在本文中，構(gòu)建的和表法計(jì)算圖像均值S1(x，y)，圖像方差S2(x，y)和圖像間的相關(guān)S3(x，y)為[13]

S1(x，y)=W(x，y)+S1(x-1，y)+

S1(x，y-1)-S1(x-1，y-1)

(4)

S2(x，y)=W(x，y)2+S2(x-1，y)+

S2(x，y-1)-S2(x-1，y-1)

(5)

S3(x，y)=W(x，y)×T(x，y)+S3(x-1，y)+

S3(x，y-1)-S3(x-1，y-1)

(6)

當(dāng)x，y<0時，S1(x，y)=S2(x，y)=0。則W在x，y位置上與模板同樣大小的區(qū)域的累積和與平方和為

S1(x-1，y-1)

(7)

1)-S2(x-1，y+n-1)-S2(x+m-

1，y-1)+S2(x-1，y-1)

(8)

m-1，y+n-1)-S3(x-1，y+n-1)-

S3(x+m-1，y-1)+S3(x-1，y-1)

(9)

(10)

對于大小為M×N的兩個比較圖像和大小為m×n的鄰域窗口，提出的和表法計(jì)算復(fù)雜度從ο(m×n×M×N)顯著降為ο(M×N)，只需要18MN加運(yùn)算和2MN乘運(yùn)算。

2 基于小波金字塔的圖像匹配算法

2.1 小波金字塔搜索策略

金字塔結(jié)構(gòu)能夠減少圖像匹配搜索的時間，而小波分解變換具有多分辨率的優(yōu)點(diǎn)，能夠有效地保留圖像中的大部分信息，實(shí)現(xiàn)對圖像的自適應(yīng)分析。因此本文采用小波金字塔分層結(jié)構(gòu)進(jìn)行搜索。

其思想是[14-15]：首先用L表示低通濾波器，H表示高通濾波器，分別對圖像的行列進(jìn)行卷積，然后進(jìn)行2取1的亞抽樣，則離散小波變換可將原圖像分解成4個子帶，即LL1，LH1，HL1，HH1。其中LL1反應(yīng)圖像的低頻成分，是由水平和垂直兩個方向的低通濾波器獲得的子帶，LH1則反應(yīng)圖像的水平邊緣細(xì)節(jié)，是由水平方向低通濾波器和垂直方向的高通濾波器獲得的子帶，類似地，HL1為水平方向高頻和垂直方向低頻獲得的子帶，HH1則是由水平方向高頻和垂直方向高頻獲得的子帶。其次將分辨率設(shè)為原圖的1/2，對低頻分量LL1進(jìn)行再一步分解，又能夠獲得LL2、LH2、HL2和HH2共4個子帶。按照這個過程反復(fù)，能夠?qū)崿F(xiàn)圖像的多級分解。則小波變換三級分解如圖1所示。

考慮到對圖像原有信息的保護(hù)以及算法的穩(wěn)定性，分層的層數(shù)一般選擇3～5層。在本文中，選用3層金字塔分層的結(jié)構(gòu)進(jìn)行匹配。其原理是[16]：利用小波變換的理論對原始圖像進(jìn)行逐級分解，得到一個尺寸規(guī)模由小到大、分辨率從低到高的金字塔分層結(jié)構(gòu)；匹配從小波分解的最低分辨率即金字塔頂層開始，利用匹配算法首先確定兩幅圖像上粗匹配的大致位置(x1，y1)和(x2，y2)，然后根據(jù)子帶樹型關(guān)系，在下一層映射位置中的中心點(diǎn)(2x1，2y1)和(2x2，2y2)鄰域內(nèi)找到精確匹配點(diǎn)，最終在金字塔底層圖像上得到滿足匹配精度要求的特征點(diǎn)。

圖1 小波三級分解示意圖Fig.1 The wavelet three decomposition diagram

在本文中，鄰域的選取影響匹配的準(zhǔn)確度，鄰域選擇過小時，包含信息少，鄰域選擇過大時，包含特征點(diǎn)多，都易造成誤匹配，因此本文選擇7×7的鄰域進(jìn)行匹配，小波金字塔搜索示意圖如圖2所示[17]。

2.2 本文算法具體步驟

采用小波金字塔搜索策略，每一層的結(jié)果都是以前一層搜索結(jié)果作為約束，與直接用原圖像進(jìn)行匹配相比，縮小了搜索的范圍，因此減少運(yùn)算中的計(jì)算量，并且提高了匹配的準(zhǔn)確度。該算法的具體步驟如下[18-19]：

1)對左右兩幅圖像用小波變換進(jìn)行2層分解，構(gòu)成三層圖像金字塔。在本文中，采用參數(shù)設(shè)置相同的Harris特征點(diǎn)檢測算法對每層金字塔圖像進(jìn)行特征點(diǎn)提取，獲得圖像的特征點(diǎn)金字塔。

2)因?yàn)榈皖l分量圖像中集中了原始圖像的大部分能量，所以匹配從頂層金字塔圖像的低頻分量圖像開始，利用改進(jìn)后的快速NCC算法進(jìn)行匹配，得到該層的最佳匹配點(diǎn)。

3)將上層的匹配點(diǎn)作為下層圖像匹配的中心點(diǎn)，在左右兩幅圖像的中心點(diǎn)的鄰域內(nèi)重新搜索進(jìn)行歸一化互相關(guān)匹配計(jì)算，得到本層的最佳匹配點(diǎn)。

4)重復(fù)進(jìn)行3)，隨著分辨率的提高，互相關(guān)匹配的搜索范圍被限定在一個比較小的范圍，隨著分辨率的提高，匹配點(diǎn)對的精度逐漸提高。經(jīng)過匹配得到原始圖像上的最佳匹配點(diǎn)。根據(jù)所得到的最終結(jié)果，將待匹配的準(zhǔn)圖像進(jìn)行相應(yīng)處理，完成匹配過程。

本文算法的框架圖為圖3。

圖2 小波金字塔搜索示意圖Fig.2 Schematic diagram of the wavelet pyramid search

3 實(shí)驗(yàn)結(jié)果與分析

為了便于分析，采用本文算法對兩組圖像進(jìn)行匹配，并與傳統(tǒng)NCC算法和文獻(xiàn)[9]匹配算法進(jìn)行比較。對于A組圖像進(jìn)行詳細(xì)的分析，實(shí)驗(yàn)采用的左右兩幅原始圖像大小都為320×400，經(jīng)小波金字塔分層處理后，中層圖像大小為160×200，頂層為80×100，在金字塔分層搜索過程中，歸一化互相關(guān)鄰域大小統(tǒng)一設(shè)置為7×7。采用傳統(tǒng)NCC算法對兩幅圖像進(jìn)行匹配，結(jié)果如圖4(a)所示；采用文獻(xiàn)[9]匹配算法獲得的結(jié)果圖如圖4(b)所示,采用本文算法得到的原始圖像的匹配點(diǎn)連線如圖4(c)所示。對于B組圖像，大小為224×344，采用傳統(tǒng)NCC算法，文獻(xiàn)[9]算法和本文算法進(jìn)行匹配，結(jié)果圖如圖5(a)、5(b)、5(c)所示。

圖3 本文算法框架圖Fig.3 The frame diagram of algorithm in this paper

(a) 傳統(tǒng)歸一化算法匹配連線圖

(b) 文獻(xiàn)[9]匹配連線圖

(c)本文算法匹配連線圖圖4 A組圖像采用不同算法的匹配結(jié)果Fig.4 The matching results of different algorithms for A group of images

(a) 傳統(tǒng)歸一化算法匹配結(jié)果

(b) 采用文獻(xiàn)[9]匹配結(jié)果

(c)采用本文算法匹配結(jié)果圖5 B組圖像采用不同算法的匹配結(jié)果Fig.5 The matching results of different algorithms for B group of images

由實(shí)驗(yàn)結(jié)果對比圖可以看出，傳統(tǒng)的NCC算法特征點(diǎn)過多，匹配不精確，而文獻(xiàn)[9]匹配算法雖然能減少特征點(diǎn)的數(shù)目，但誤匹配率仍然很高。本文算法采用由粗到精的匹配模式，隨著分辨率的提高，匹配點(diǎn)對的精度逐漸提高，從而產(chǎn)生更多匹配對，誤匹配連線較少，提高了匹配精度。

傳統(tǒng)NCC算法、文獻(xiàn)[9]匹配算法與本文算法采用時間結(jié)果如表1所示。

表1 三種算法耗時

從表1可以看出，本文的算法雖然增加了圖像特征點(diǎn)檢測的時間，由于采用小波金字塔分層搜索策略，縮小搜索范圍，以前一層匹配的結(jié)果作為下一層匹配的約束，在上層匹配點(diǎn)的鄰域內(nèi)搜索匹配，不用遍歷整幅圖像，大大地減少了匹配的時間。

4 結(jié)論

本文通過構(gòu)造三個加和表的方法較少計(jì)算過程中乘法的計(jì)算量，降低運(yùn)算的復(fù)雜度，同時采用小波三級分解獲得的圖像金字塔，根據(jù)由粗到精的匹配模式，使得特征點(diǎn)定位更加精確。對于A、B兩組不同的實(shí)驗(yàn)圖像，與采用傳統(tǒng)的算法和文獻(xiàn)[9]算法相比，該算法雖然在進(jìn)行圖像特征點(diǎn)檢測階段增加了1.28 s和1.43 s，但是在特征點(diǎn)匹配階段也大大縮短了時間，因此總體時間上分別減少了3.5 s、0.47 s和3.52 s、0.3 s；同時該算法獲得的誤匹配較少，匹配連線效果更好，具有實(shí)際應(yīng)用價值。

文中針對靜止的圖像進(jìn)行的匹配，后續(xù)可以針對改進(jìn)的算法對運(yùn)動目標(biāo)的匹配測試的準(zhǔn)確度和實(shí)時性進(jìn)行進(jìn)一步研究。

[1]段湘斌.基于灰度圖像的匹配算法改進(jìn)[D].長沙：中南大學(xué)， 2012.

DUAN Xiangbin. The improve image matching algorithm based on the gray image[D]. Changsha: Central South University， 2012.

[2]STOLLNITZ E J，DEROSE T D，SALESIN D H. Wavelets for computer graphics: A Primer， part1.IEEE computer graphics and application， 1995， 15(3): 76-84.

[3]賀曉佳.灰度圖像快速匹配算法研究[D].合肥： 合肥工業(yè)大學(xué)， 2012.

HE Xiaojia. Research on fast gray image matching algorithm[D]. Hefei: HeFei University of Technology， 2012.

[4]謝維達(dá)，周宇恒，寇若嵐.一種改進(jìn)的快速歸一化互相關(guān)算法[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版， 2011， 39(8): 1233-1237.

XIE Weida，ZHOU Yuheng，KOU Ruolan. An improved fast normalized cross correlation algorithm[J]. Journal of Tongji University：Natural Science， 2011， 39(8): 1233-1237.

[5]孫卜郊，周東華.基于NCC快速匹配算法[J].傳感器與微系統(tǒng)， 2013， 40(1)： 118-125.

SUN Bujiao，ZHOU Donghua. Fast matching method based on NCC[J]. Transducer and microsystem technologies， 2013， 40(1)： 118-125.

[6]LEWIS J P. Fast normalized cross correlation [C]∥Proceeding of Vision Interface. Quebec, Canda， 1995: 120-123.

[7]TSAI D M，LIN C T．Fast normalized cross correlation for defect detection[J].Pattern recognition letters， 2003， 24： 2625-2631.

[8]汪華琴.基于特征點(diǎn)匹配的圖像拼接方法研究[D].武漢： 華中師范大學(xué)， 2007.

WANG Huaqin. The research of image mosaic method based on feature points matching [D]. Wuhan: Huazhong Normal University， 2007.

[9]孫祖鑫，吳強(qiáng).一種基于TS201的歸一化互相關(guān)快速算法[J].現(xiàn)代電子技術(shù)， 2010 (10)： 125-127.

SUN Zuxin，WU Qiang. TS201 based fast algorithm of normalized cross-correlation[J]. Modern electronics technique， 2010(10)： 125-127.

[10]WEI Shoude， LAI Shanghong. Fast template matching based on normalized cross correlation with adaptive multilevel winner update[J].IEEE transactions on image processing， 2008， 17(11): 2227-2235.

[11]程紅，劉文劍，孫文邦.一種改進(jìn)的快速歸一化積相關(guān)圖像匹配算法[J].光電工程， 2013， 40(1)： 118-125.

CHENG Hong，CHEN Wenjian，SUN Wenbang. An improved fast normalized cross correlation algorithm for image matching[J]. Opto-electronic engineering， 2013， 40(1): 118-125.

[12]吳強(qiáng)，任琳，張杰，等.快速歸一化互相關(guān)算法及DSP優(yōu)化實(shí)現(xiàn)[J].電子測量與儀器學(xué)報(bào)， 2011， 25(6)： 495-499.

WU Qiang， REN Lin， ZHANG Jie， et al. Fast algorithm of normalized cross correlation and optimized implementation on DSP[J]. Journal of electronic measurement and instrument， 2011， 25 (6): 495-499.

[13]HII A J H，HANN C E，CHASE J G， et al. Fast normalized cross correlation for motion tracking using basis functions[J].Computer methods and programs in biomedicine， 2006， 82(2)： 144-156.

[14]朱程輝，何勇，王金玲.基于小波金字塔的快速圖像匹配算法[J].圖像處理， 2010， 26(04)： 127-129.

ZHU Chenghui， HE Yong， WANG Jinling. A fast stereo matching algorithm based on wavelet pyramid[J].Image processing， 2010， 26(04)： 127-129.

[15]劉國權(quán)，李守軒.基于小波圖像金字塔的SSDA快速模板匹配算法[J].科技廣場， 2007， 11： 134-137.

LIU Guoquan， LI Shouxuan. A fast images matching algorithm of SSDA based on wavelet pyramid [J]. Technology square， 2007， 11： 134-136.

[16]阮曉虎，李衛(wèi)軍，覃鴻，等． 一種基于特征匹配的人臉配準(zhǔn)判斷方法[J].智能系統(tǒng)學(xué)報(bào)， 2015， 10(1) : 12-19.

RUAN Xiaohu， LI Weijun， TAN Hong, et al. An assessment method for face alignment based on feature matching [J]. CAAI transactions on intelligent system， 2015， 10(1): 12-19.

[17]任三孩，常文革，劉向君.一種基于小波變換和變尺度圓模板融合的景象匹配算法[J].電子學(xué)報(bào)， 2011， 39(9)： 2200-2203.

REN Sanhai， CHANG Wenge， LIU Xiangjun. A scene matching method based on wavelet transform and multi-scale circular template fusion[J].Journal of electronics， 2011， 39(9)： 2200-2203.

[18]張玉.人臉圖像的小波特征提取與匹配[D].南昌： 南昌航空大學(xué)， 2012.

ZHANG Yu. Feature extraction and matching of the face image based on wave[D].Nanchang: Nanchang Hangkong University， 2012.

[19]王佳，孫一權(quán)，馮仲科.金字塔分層影像雙向匹配的樹木圖像匹配策略[J].測繪科學(xué)， 2014， 39(6)： 94-98.

WANG Jia， SUN Yiquan， FENG Zhongke. The trees image matching strategy of pyramid hierarchical image bilateral matching[J].Science of surveying and mapping， 2014， 39(6)： 94-98.

本文引用格式：

吳鵬， 徐洪玲，宋文龍.結(jié)合小波金字塔的快速NCC圖像匹配算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2017， 38(5)： 791-796.

WU Peng，XU Hongling，SONG Wenlong.A fast NCC image matching algorithm based on wavelet pyramid search strategy[J]. Journal of Harbin Engineering University， 2017， 38(5)： 791-796.

A fast NCC image matching algorithm based on wavelet pyramid search strategy

WU Peng， XU Hongling， SONG Wenlong

(College of Mechanical and Electronic Engineering， Northeast Forestry University， Harbin 150040， China)

To remove the defects of the traditional normalized cross correlation (NCC) algorithm， such as significant computation， slow computation speed， and low accuracy， a fast NCC image-matching algorithm based on the wavelet pyramid search strategy was proposed. The algorithm was based on the traditional NCC algorithm， which used the sum-table scheme to calculate the image mean， variance， and the correlation between the images， to reduce the amount of calculation， and the computational complexity. At the same time， the structure of the image pyramid was constructed in selecting the feature point matching search strategy， and the hierarchical matching was applied to improve the efficiency of image matching. Compared with other algorithms， the results show that the effect of linking matching points in the algorithm is better， and it consumes less time. Therefore， it is verified that the algorithm can not only increase the matching speed， but also improve the matching accuracy.

image matching; feature points; normalized cross correlation; matching strategy; wavelet pyramid; sum-table scheme; matching speed; matching accuracy

2015-12-07.

日期：2017-04-26.

國家自然科學(xué)基金項(xiàng)目(31470714)；哈爾濱市科技創(chuàng)新人才研究專項(xiàng)資金項(xiàng)目(2014RFQXJ127)；黑龍江省博士后科研啟動金項(xiàng)目(LBH-Q14006)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2572014CB14).

吳鵬(1980-)，男，副教授，博士； 徐洪玲(1991-)，女，研究生; 宋文龍(1973-)，男，教授，博士生導(dǎo)師.

宋文龍，E-mail:wlsong139@163.com.

10.11990/jheu.201512022

TP391

A

1006-7043(2017)05-0791-06

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1041.026.html