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

吳鵬， 徐洪玲，宋文龍

(東北林業大學 機電工程學院，黑龍江 哈爾濱 150040)

?

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

吳鵬， 徐洪玲，宋文龍

(東北林業大學 機電工程學院，黑龍江 哈爾濱 150040)

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

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

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

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

1 快速歸一化相關算法

1.1 歸一化互相關匹配算法

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

特征點匹配算法，其原理是根據兩幅圖像中特征點鄰域像素灰度值的相似性來匹配的，對于左圖像中的一點，計算其與右圖像中所有特征點的歸一化互相關系數，當得到其中最大值的點就為最佳匹配位置。

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

不去均值：

(1)

去均值：

(2)

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

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

1.2 快速歸一化互相關算法

傳統的歸一化互相關匹配算法進行特征點匹配時，需要對特征點進行遍歷搜索，共需要3mnMN加運算和2mnMN乘運算，計算量非常龐大。因此在本文中通過構建加和表[12]來減少匹配過程中計算量，加快運算速度。

快速NCC匹配算法在計算歸一化互相關系數時，將公式變換為

(3)

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

在本文中，構建的和表法計算圖像均值S1(x，y)，圖像方差S2(x，y)和圖像間的相關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)

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

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的鄰域窗口，提出的和表法計算復雜度從ο(m×n×M×N)顯著降為ο(M×N)，只需要18MN加運算和2MN乘運算。

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

2.1 小波金字塔搜索策略

金字塔結構能夠減少圖像匹配搜索的時間，而小波分解變換具有多分辨率的優點，能夠有效地保留圖像中的大部分信息，實現對圖像的自適應分析。因此本文采用小波金字塔分層結構進行搜索。

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

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

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

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

2.2 本文算法具體步驟

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

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

2)因為低頻分量圖像中集中了原始圖像的大部分能量，所以匹配從頂層金字塔圖像的低頻分量圖像開始，利用改進后的快速NCC算法進行匹配，得到該層的最佳匹配點。

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

4)重復進行3)，隨著分辨率的提高，互相關匹配的搜索范圍被限定在一個比較小的范圍，隨著分辨率的提高，匹配點對的精度逐漸提高。經過匹配得到原始圖像上的最佳匹配點。根據所得到的最終結果，將待匹配的準圖像進行相應處理，完成匹配過程。

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

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

3 實驗結果與分析

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

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

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

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

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

(a) 傳統歸一化算法匹配結果

(b) 采用文獻[9]匹配結果

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

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

傳統NCC算法、文獻[9]匹配算法與本文算法采用時間結果如表1所示。

表1 三種算法耗時

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

4 結論

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

文中針對靜止的圖像進行的匹配，后續可以針對改進的算法對運動目標的匹配測試的準確度和實時性進行進一步研究。

[1]段湘斌.基于灰度圖像的匹配算法改進[D].長沙：中南大學， 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].合肥： 合肥工業大學， 2012.

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

[4]謝維達，周宇恒，寇若嵐.一種改進的快速歸一化互相關算法[J].同濟大學學報：自然科學版， 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].傳感器與微系統， 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]汪華琴.基于特征點匹配的圖像拼接方法研究[D].武漢： 華中師范大學， 2007.

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

[9]孫祖鑫，吳強.一種基于TS201的歸一化互相關快速算法[J].現代電子技術， 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].光電工程， 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]吳強，任琳，張杰，等.快速歸一化互相關算法及DSP優化實現[J].電子測量與儀器學報， 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]劉國權，李守軒.基于小波圖像金字塔的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]阮曉虎，李衛軍，覃鴻，等． 一種基于特征匹配的人臉配準判斷方法[J].智能系統學報， 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].電子學報， 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].南昌： 南昌航空大學， 2012.

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

[19]王佳，孫一權，馮仲科.金字塔分層影像雙向匹配的樹木圖像匹配策略[J].測繪科學， 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.

本文引用格式：

吳鵬， 徐洪玲，宋文龍.結合小波金字塔的快速NCC圖像匹配算法[J]. 哈爾濱工程大學學報， 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.

國家自然科學基金項目(31470714)；哈爾濱市科技創新人才研究專項資金項目(2014RFQXJ127)；黑龍江省博士后科研啟動金項目(LBH-Q14006)；中央高校基本科研業務費專項資金項目(2572014CB14).

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

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

10.11990/jheu.201512022

TP391

A

1006-7043(2017)05-0791-06

網絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1041.026.html