哈尔滨工程大学学报
Journal o! Harbin Engineering University
Vol.38 No.5
May 2017
结合小波金字塔的快速
NCC图像匹配算法
吴鹏，徐洪玲，宋文龙
(东北林业大学机电工程学院，黑龙江哈尔滨150040)
摘要
:针对传统的归一化互相关算法（NCC)计算量庞大、运算速度慢、正确率较低等问题，本文提出一种基于小
波金字塔搜索策略的快速NCC图像匹配算法。该算法在归一化互相关算法的基础上，采用和表法分别计算图像
均值、图像方差和图像间的互相关来降低运算的复杂度，减少算法的计算量；同时在选择特征点匹配搜索策略时，
构造图像小波金字塔结构，利用分层匹配来提高图像匹配的效率。与其他算法进行对比，结果表明该算法获得的 匹配点连线效果更好，所用的时间也量化，证明该算法不仅能提高匹配速度，还能改善匹配精度。关键词：图像匹配；特征点；归一化互相关匹配算法；匹配策略；小波金字塔;和表法；匹配速度；匹配精度
DOI：10. 11990/jheu.201512022网络出版地址：http://www.cnki.net/kcms/detail/23. 1390.u.20170426. 1041. 026.html 中图分类号:TP391文献标志码:A文章编号：1006-7043(2017)05-0791-06
A fast NCC image matching algorithm based
on wavelet pyramid search strategy
(College of Mechanical and Electronic Engineering，Northeast Forestry University，Harbin 150040，China)
Abstract ：To remove the defects o! 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 o! image matching. Compared with other algorithms，the results show that the effect o! 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.
Keywords：image matching； feature points; normalized cross correlation； matching strategy; wavelet pyramid; sum-table scheme; matching speed; matching accuracy
WU Peng，XU Hongling，SONG Wenlong
图像匹配是计算机视觉和模式识别中一项重要 而广泛的应用,利用相关的匹配算法在两幅或者多 福图像之间识别同一特征点。随着图像匹配技术的 逐步发展，国内外的学者都对其进行了深人的研究， 并提出了许多图像匹配算法[|-2]。经典的匹配算法 有：归一'化互相关（normalized cross-correlation，
收稿日期：2015-12-07. 网络出版日期：2017-04-26.基金项目：国家自然科学基金项目（31470714);哈尔滨市科技创新人
NCC)匹配算法、差的绝对值和（sum of absolute difference，SAD )相关算法、差的平方和（sum of square differences, SSD)相关算法等。其中 NCC 算
法在现有相关匹配算法中应用最为广泛，具有较好 的鲁棒性，对光照强度的线性变化不太敏感，抗白噪
声干扰能力强，但其缺点是计算量大、匹配速度慢、 错误匹配较多，并不符合系统实时性的要求[3-5]。因此如何降低计算的复杂度，减少运算过程中的 计算量，提高匹配精度，已成为现在研究的难点和热 点问题。Lewis提出用两个加和表的方法来来简化
NCC分母的计算量，但没有改变分子的运算复杂
才研究专项资金项目（2014RFQXJ127);黑龙江省博士后
科研启动金项目（LBH-Q14006);中央高校基本科研业务 费专项资金项目（2572014CB14).
作者简介:吴鹏（ 1980-),男，副教授,博士；
徐洪玲（1991-),女，研究生；宋文龙（ 1973-),男，教授，博士生导师.
通信作者：宋文龙，E-mail:wlsong139@ 163.com.
度[6]；Tsai等通过改进了 NCC的定义，构造三个和表 法来同时简化分子和分母的计算量，但匹配精度并不
•792,哈尔滨工程大学学报第38卷
高[7];汪华琴针对归一化互相关算法精度不高,采用分 层匹配来提高搜索匹配的效率，但计算仍很复杂[8]。 孙祖鑫等采用递推与多模板思想构建归一化互相关快 速算法，但匹配率并不是很理想[9]。针对以上问题，本 文首先对传统的归一化互相关算法进行改进,减少计 算量，同时在搜索策略上利用小波金字塔分层匹配的 思想，分辨率由低到高，匹配由粗到细,提出一种基于 小波金字塔搜索策略的快速NCC图像匹配算法。11. 1
快速归一化相关算法
归一化互相关匹配算法归一化互相关算法（NCC)是一种常用的图像
特征点匹配算法，其原理是根据两幅图像中特征点 邻域像素灰度值的相似性来匹配的，对于左图像中 的一点，计算其与右图像中所有特征点的归一化互
相关系数，当得到其中最大值的点就为最佳匹配 位置。
设％和％分别是图像/,和图像&的两个大小 相同的匹配窗口，图像大小为M x W，匹配窗口大小 为m X ra，M,和《2是匹配窗口内像素灰度的均值。 归一化相关系数的定义形式通常有去均值和不去均 值两种[IQ-II]:
不去均值：
X『I(* + Q +■/)『2(* + Q +■/)
卜〇 y = o
丨~~—=—I — I I —IXX ^i + +)2 XX ^2 + +厂Uj)= m
X
n
(xl，yi
, m
n
(I)
(xi，yD'去均值：
r(x，y)X X( ^i( + ， +) — UI)( ^2( + ， i=0 =0m— I n— I m—I n— I
j
xiyjXiy+j) — «2)
(2)
X X (^i( + ， +) — ui)2
Xiyi
X X (^2( + ， + ) — ^2)-
Xiyj
式中：（X，y) e M\" x W;r(x，y)的取值范围为-1 ~ 1，值越大表示相关程度越高。
虽然去均值的归一化互相关图像匹配算法的计 算量比较大，但是它对于灰度和较小的几何畸变存 在不变性，同时具有很强的抗噪声干扰的能力，因此 本文选用去均值的归一化互相关匹配算法。在本文 中，对两幅同样大小的图像，使用Harris算法进行特
和表的方法,减少分子分母计算量，并引人图像小波金字塔分层结构，提高搜索匹配的效率。
1.2快速归一化互相关算法
传统的归一化互相关匹配算法进行特征点匹配 时，需要对特征点进行遍历搜索,共需要3mnMW加 运算和2mnMW乘运算，计算量非常庞大。因此在 本文中通过构建加和表[12]来减少匹配过程中计算 量，加快运算速度。
快速NCC匹配算法在计算归一化互相关系数
征点检测，传统的归一化互相关方法行进特征点匹 配，但匹配结果精度不高,且所用时间长。本文在现有算法的基础上，针对NCC算法，通过构建3个加 时,将公式变换为
m—I n— I
^2(x + +) — X X ^i(X + +j)r( X，y)l，yi，yj
X
mnuiu2(3)
X
1 m-I n- I
X
『I (x + 心 +■/)—
2
2,mnu X
X『2 (x + i，y +；)2 —
mnu^其中，ui = — X X『i(X + + ) ； u2 = = 〇 = 〇1 m- I n- I—X X『2(X +)。mn = 0 = 0
从式（3)可以看出来，方程的归一化互相关操 作涉及源图像『(x，y)和模板图像r(x，y)的平均
mnij
i，yJ
为[13]
S|( ，)=『(，) + i( - 1，y) +
xy
ij
j
xySX
S|(x，y - 1) - S|(X - 1，y - 1)
S2(x，y - 1) - S2(x - 1，y - 1)
(4)
S2(x，r)=『（x，r)2 + S2(x - 1，r) +
⑶
S3(x，y)=『(x，y) x (x，y) + S3(x - 1，y) +
S3(x，y - 1) - S3(x - 1，y - 1) (6)当 x，y < 0 时,S,(x，y) = S2(x，y) = 0。则『在
x，y位置上与模板同样大小的区域的累积和与平方
值，平方以及『和:T之间的互相关的计算。
在本文中，构建的和表法计算图像均值S|(X， ；T)，图像方差S2(x，y)和图像间的相关S3(x，y)
T
第5期
吴鹏，等:结合小波金字塔的快速NCC图像匹配算法
• 793 •
和为
- 1 - 1II =0 =0
mnij
I I
x+i，j+y) = 1( + - 1，j + n- 1)-S1(x - 1，j + n- 1) -S1(x+m - 1，j- 1) + S1(x - 1，r - 1)
Sxm
i=0 j=0
W(x + i，y +j) x T(x + i，y + j) = S3(x +
m - 1，j + n- 1) -S3(x - 1，j + n- 1)-S 3( x + m- 1，j- 1) +S 3( x - 1，y- 1)
(7)
m - 1 n - 1
II ^ (x+i，j+y)2 = 2( - 1 + -i = 0 = 0
1) - S2(x - 1，j + n - 1) - S2(x + m -
(9)
将式（7 )〜（9 )代人式（3 )，令5w2 =
m - 1 n - 1
n • 22 得，II W2(x + i，y +i)2-m •
i=0 y=0
j
Sx+m，yn
u
1，r- 1) +S2( x- 1，r- 1)
厂(x，y)=
(8)
,S3( x + m_1，y + n_1 ) _S3( x_1，y + n_1 ) _)(S 1( x + m _1 ，y + n _1 ) _ S 1( x _1 ，y + n _1 ) _ ^ _
T
、S3( x+m_ 1，J\"— 1 ) +S3( x_ 1，J\"— 1 ) 、S 1( x + m _1，y _1)+ S 1( x _1，y _1) 0J
,S3( x + m_1，y + n_1) _S3( x_1，y + n_1) _、
VS 3( x + m _1，y _1) + S 3( x _1，y _1)
y
(10)
对于大小为M x W的两个比较图像和大小为
m x n的邻域窗口，提出的和表法计算复杂度从 o(m XnxMxW)显著降为〇(MxW)，只需要18MW
的大致位置（x!，yj和(x2，y2)，然后根据子带树型 关系，在下一层映射位置中的中心点UxiJyJ和 (2x2,2y2)邻域内找到精确匹配点，最终在金字塔 底层图像上得到满足匹配精度要求的特征点。
ll3hl3hl3hh3lh2
hh2
加运算和2MW乘运算。2
基于小波金字塔的图像匹配算法
2.1小波金字塔搜索策略
金字塔结构能够减少图像匹配搜索的时间，而 小波分解变换具有多分辨率的优点，能够有效地保 留图像中的大部分信息，实现对图像的自适应分析。 因此本文采用小波金字塔分层结构进行搜索。
其思想是[14_15]:首先用L表示低通滤波器，H 表示高通滤波器，分别对图像的行列进行卷积，然后 进行2取1的亚抽样，则离散小波变换可将原图像 分解成4个子带，即LL1，LH1，HL1，HH1。其中LL1 反应图像的低频成分，是由水平和垂直两个方向的 低通滤波器获得的子带，L4则反应图像的水平边 缘细节，是由水平方向低通滤波器和垂直方向的高 通滤波器获得的子带，类似地，HL1为水平方向高频 和垂直方向低频获得的子带，HH1则是由水平方向 高频和垂直方向高频获得的子带。其次将分辨率设 为原图的1/2,对低频分量LL1进行再一步分解，又 能够获得LL2、HL2和HH2共4个子带。按照 这个过程反复，能够实现图像的多级分解。则小波 变换三级分解如图1所示。
考虑到对图像原有信息的保护以及算法的稳定 性，分层的层数一般选择3〜5层。在本文中，选用3 层金字塔分层的结构进行匹配。其原理是[16]:利用 小波变换的理论对原始图像进行逐级分解，得到一 个尺寸规模由小到大、分辨率从低到高的金字塔分 层结构;匹配从小波分解的最低分辨率即金字塔顶 层开始，利用匹配算法首先确定两幅图像上粗匹配
LHimi
,图1小波三级分解示意图
Fig.l The wavelet three decomposition diagram在本文中，邻域的选取影响匹配的准确度，邻域 选择过小时，包含信息少，邻域选择过大时，包含特 征点多，都易造成误匹配，因此本文选择7x7的邻 域进行匹配，小波金字塔搜索示意图如图2所示[17]。
2. 2本文算法具体步骤
采用小波金字塔搜索策略，每一层的结果都是 以前一层搜索结果作为约束，与直接用原图像进行 匹配相比，缩小了搜索的范围，因此减少运算中的计
算量，并且提高了匹配的准确度。该算法的具体步 骤如下[18_19]:
1) 对左右两幅图像用小波变换进行2层分构成三层图像金字塔。在本文中，采用参数设置相 同的Harris特征点检测算法对每层金字塔图像进行 特征点提取，获得图像的特征点金字塔。
2) 因为低频分量图像中集中了原始图像的大
• 794 •哈尔滨工程大学学报第38卷
部分能量，所以匹配从顶层金字塔图像的低频分量 图像开始，利用改进后的快速NCC算法进行匹配， 采用传统NCC算法，文献[9]算法和本文算法进
行匹配，结果图如图5(a)、5(b)、5(c)所示。
得到该层的最佳匹配点。
3) 将上层的匹配点作为下层图像匹配的中心 点，在左右两幅图像的中心点的邻域内重新搜索 进行归一化互相关匹配计算，得到本层的最佳匹 配点。4)
重复进行3)，随着分辨率的提高，互相关匹
配的搜索范围被限定在一个比较小的范围，随着分
辨率的提高，匹配点对的精度逐渐提高。经过匹配 得到原始图像上的最佳匹配点。根据所得到的最终 结果，将待匹配的准图像进行相应处理，完成匹配 过程。
本文算法的框架图为图3。
3实验结果与分析
为了便于分析，采用本文算法对两组图像进
行匹配，并与传统NCC算法和文献[9]匹配算法 进行比较。对于A组图像进行详细的分析，实验 采用的左右两幅原始图像大小都为320x400,经小 波金字塔分层处理后，中层图像大小为160x200, 顶层为80x100,在金字塔分层搜索过程中，归一化 互相关邻域大小统一设置为7x7。采用传统NCC 算法对两幅图像进行匹配，结果如图4(a)所示;采 用文献[9]匹配算法获得的结果图如图4(b)所 示，采用本文算法得到的原始图像的匹配点连线 如图4(c)所示。对于B组图像，大小为224x344,
图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
第5期
吴鹏，等:结合小波金字塔的快速NCC图像匹配算法
• 795 •
特征点检测的时间，由于采用小波金字塔分层搜索 策略，缩小搜索范围，以前一层匹配的结果作为下一
层匹配的约束，在上层匹配点的邻域内搜索匹配，不 用遍历整幅图像，大大地减少了匹配的时间。4
结论
(a)传统归一化算法匹配结果
本文通过构造三个加和表的方法较少计算过程 中乘法的计算量，降低运算的复杂度，同时采用小波 三级分解获得的图像金字塔，根据由粗到精的匹配 模式，使得特征点定位更加精确。对于A、B两组不 同的实验图像，与采用传统的算法和文献[9]算法 相比，该算法虽然在进行图像特征点检测阶段增加 了 1. 28 s和1. 43 s，但是在特征点匹配阶段也大大 缩短了时间，因此总体时间上分别减少了 3.5 s、 0. 47 s和3. 52 s、0. 3 s;同时该算法获得的误匹配较 少，匹配连线效果更好，具有实际应用价值。文中针对静止的图像进行的匹配，后续可以针 对改进的算法对运动目标的匹配测试的准确度和实 时性进行进一步研究。
参考文献：
(c)采用本文算法匹配结果
图5 B组图像采用不同算法的匹配结果 Fig.5 The matching results of different algorithms for
B group of images
由实验结果对比图可以看出，传统的NCC 算法特征点过多，匹配不精确，而文献[9 ]匹配算法 虽然能减少特征点的数目，但误匹配率仍然很高。 本文算法采用由粗到精的匹配模式，随着分辨率的
提高，匹配点对的精度逐渐提高，从而产生更多匹配 对，误匹配连线较少，提高了匹配精度。
传统NCC算法、文献[9]匹配算法与本文算法 米用时间结果如表1所示。
表1三种算法耗时
Table 1 Time consumption of the three algorithms
特征点检
图像
原
匹配算法
测阶段的时间/s
特征点匹配阶段的时间/s
总耗时/s
A组
图像
NCC算法
文献[9]算法
文献[9]算法
B组
图像
本文算法原 NCC 算法本文算法
1.451.452.731.631.633.069.266.234.4810.747.525.7910.717.687.2112.379. 158.85
从表1可以看出，本文的算法虽然增加了图像
[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，DER0SE 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，ZH0U Yuheng，K0U 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
•796-哈尔滨工程大学学报第38卷
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 multiscale 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 wTave[ 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.
WL Peng，XL Hongling，SONG Wenlong.A fast NCC image matching algorithm based on wavelet pyramid search strategy[J]. Journal of Harbin Engineering Lniversity，2017，38(5)： 791-796.
因篇幅问题不能全部显示，请点此查看更多更全内容