一种改进的快速归一化互相关算法
第39卷第8期
2011年8月
同济大学学报(自然科学版)
JOURNALOFTONGJIUNIVERSITY(NATURALSCIENCE)
V01.39No.8
Aug.2011
文章编号:0253-374X(2011)08-1233—05IX)Itl0.3969/1。issn.0253.374x.2011.08.025
一种改进的快速归一化互相关算法
谢维达,周宇恒,寇若岚
(同济大学铁道与城市轨道交通研究院,上海201804)
摘要:根据模板和全局最优子图的特点及其相互关系给出2
个判据,对归一化互相关算法进行了改进.首先计算模板自相关值。再利用快速傅里叶变换方法计算互相关矩阵,利用第1个判据大幅缩小可能解的范围,减少匹配时间,然后利用第2个判据生成一个规模更小的候选最优解集合,最后确
基于灰度值的图像匹配方法被广泛应用于多种领域,如医学图像分析[1|、视频处理‘21、交通控制[3]等,其中最常用的一种算法是归一化互相关算法
(normalized
cross
correlation,NCC).NCC算法的主
定全局最优解.实验结果说明,改进的归一化互相关算法能
加快匹配速度,且能有效地提高图像匹配的准确率.关键词:归一化互相关算法;判据;匹配速度;匹配准确率中图分类号:TP
391.9
要优点是对光照强度的线性变化不太敏感,抗干扰性能较好;计算结果有固定的范围[一1,1],容易设置检测阈值.但是,NCC算法没有一个简单的频域表达式,无法利用类似快速傅里叶变换(fastFouriertransform,FFT)的方法得到计算结果.由于是逐像素进行计算,导致NCC算法计算量大,速度慢,只适合对处理速度要求不高的场合.目前已提出许多快速NCC算法,如基于sumtables的快速NCC算法[卜6],基于winner
update
文献标识码:A
AnImprovedFastNormalizedCrossCorrelationAlgorithm
脚Weida,ZttOV懒,KOURuolan
(Institute
of
strategy的快速算
elimination
Railway
andUrban
RailTransit。TongjiUniversity。
法[7。8],连续排除算法(successive
Shanghai201804,China)
algorithm)[91,基于分块理论的boundedpartialcorrelation[10]等.匹配算法不仅需要有效加快匹配
normalized
to
on
Abatract:Someimprovementsweremadefor
cross
correlationhased
twocriterionsaccording
the
速度,还应该关注算法的匹配准确程度.因为在外界干扰的作用下,待匹配图像的某些区域会形成匹配盲区,与模板很容易出现误匹配.因此,验证这些算法性能的实验仿真不能只是选取一些特定的模板,因为并不具备代表性.
基于此问题,本文根据模板和待匹配图像的特点,提出一种新的归一化互相关匹配算法,该算法在加快匹配速度的同时,有效提高模板的识别准确率.1
characteristics0ftemplateandimageandtheinterrelationshipbetween
them.11地auto-correlation
cross
ofthe
template
WaS
calculatedatfirst,andthecorrelation
between
template
and
imageWaSgainedbasedonfastFourier
transform.Then
thefirstcriterionWaSusedtoshrinkthemngeofthepossiblesolutions.whichcouldshortenthematchingtime
and
the
second
criterionwasappliedtogenerating
a
moreminiature
normalizedcrOSS
set,inwhichthesolutionwiththe
maximal
correlationwastheglobaloptimalsolution.Experimentsshowthat
the
normalized
cr∞scorrelationbased
an
Oil
thegiven
归一化互相关匹配算法
设待匹配图像f的像素大小为M×N,模板T
criteriacanspeedthecomputing、^,ith
precision.
enhancedmatching
Keywords:normalizedcrOSScorrelation;criteriont
matching
的像素大小为mX饥从图像J中任意选取一块像素大小为mX竹的子图j州,其左上角在图像j中
speed,matching
precision
收稿日期;2010—04—27
基金项目:“十一五”国家科技支撑计划(2009BAGllB02)
第一作者。谢维达(1947一)。男.教授,工学学士,主要研究方向为车辆牵引控制与检测技术、轨道车辆安全技术、轮轨系统动力学与控制
E-mailltixwd@163.com
通讯作者。周字恒(198l一).男。博士生・主要研究方向为车辆牵引控制与检测技术.E-mailtyuhengzhou(圆QQ.COm
同济大学学报(自然科学版)第39卷
的坐标为(∞,可),可知坐标范围为0≤z≤M—m,0≤拶≤N一视.其中,M,N分别为待匹配图像像素的行数和列数,m,忱分别为模板像素的行数和列数。
子图Ix,Y和模板T的归一化互相关值R(z,可≯
定义为
R(七,可)=
∑∑[j(茁+i,可+J)一k][T(t,歹)一司
√∑∑[J(z+i,Y+歹)~乙]2∑∑[T(i,J)一司2
(1)
式中:(i,歹)为像素在模板中的坐标;I。。。=
丽%E;:。Z伽[I(∞+{,Y+J)]为子图j。,V的像素平
均值;亍2去荟荟T(i,歹)为模板T的像素平均
值.所有的归一化互相关值构成归一化互相关矩阵
R.
定义1在归一化互相关矩阵足中,V0≤z≤
M—m,V0≤y≤N一%,若点(z,可)处的
R(∞,矽)=max{R),则称(z,可)为最优解,对应的子图j州为最优子图.
对于式(1),考虑以下2点:
(1)由于模板T已知,Rr=∑∑[T({.D一亍]2
在整个搜索过程中为一个定值且为正数,不会影响最优解的确定,可不计算,故式(1)的分母部分可写
成
‰(∞,可)=^/∑∑[J(z+{,!,+歹)一k]2(2)
V
‘=0
J=0
(2)令T7(i,歹)=T(i,歹)一T,则式(1)的分子部分可作如下简化:
Jk=
∑∑[f(z+i,Y+J)一7"][T(t,歹)一司=∑∑[J(z+i,Y+J)一了埘]r(i,歹)=
∑∑I(x+i,可+j)r(i,J)一乙∑∑r(i,j)
因为∑∑T7(i,歹)=∑∑[T(i,J)一亍].0,
所以
‰(z,可)=∑∑I(x+i,可4-歹)r(i,歹)
(3)
所以式(1)可以等效为下式:
—m—-1兰兰
∑∑I(x+i,Y+歹)r(z,歹)
R7(∞,可)=_兰兰辈========二=(4)
^/∑∑[J(z+i,Y+歹)一7Ⅵ]2
V
i=0
j=0
将式(4)称为逐像素匹配的归一化互相关算法(pixel-by—pixelNCC).从式(4)可知,匹配中所产生的计算量主要分为两部分:式(2)的计算量为(2mn一1)(M—m+1)(N一视+1)次加法运算及mn(M—m+1)(N一佗+1)次乘法运算及式(3)的为了减小式(3)的计算量,可利用傅里叶变换的R一=F。[F(j)F。(T7)]
(5)
X
N的矩阵.式(5)计算量为心・
l092(朋Ⅳ)+
采用pixel—by—pixelNCC方法匹配所需时间代定义2设模板T在待匹配图像J上的坐标为定义3若最优解与全局最优解不同,称该最优根据全局最优子图的定义,当原始图像为待匹(1)由式(3)可知,以原始图像作为待匹配图像m一1矗一l
计算量为mn(M—m+1)(N一他+1)次加法运算及(m他一1)(M—m+1)(N—n+1)次乘法运算.性质,即图像经过傅里叶变换后,在空域上的互相关运算可以变为频域上的复数乘法运算,即
式中:F(・)为傅里叶变换;F。(・)为F(・)的复共轭;F-1(・)为傅里叶逆变换,且T7应补零拓延成
为像素大小为M[61092(彻V)+2]次加法运算和MN[9
4]次乘法运算.
价巨大[4-10],且通过本文实验可知,在外界干扰的影响下,若模板选取不当,容易出现失配的情况.基于这些问题,本文根据模板和全局最优解的特点及其相互关系,提出一种新的NCC算法,能够有效提高图像匹配准确度,并能提高匹配的速度.
2基于2个判据的归一化互相关算法
2.1全局最优子图的3个特点
(茁o,Yo),则称(zo,Yo)为全局最优解,对应的子图J‰。‰为全局最优子图.
解为局部最优解,对应的最优子图称为局部最优子图.
配图像时,模板就是全局最优子图.基于此,全局最优子图应具有以下3个特点:
时,全局最优子图与模板的互相关值R(‰,Y。)应等
于模板的自相关值Rt=∑∑[T(i,J)一亍]z;当
第8期
谢维达,等:一种改进的快速归一化互相关算法
待匹配图像为加噪图像时,全局最优子图与模板间有一定的误差,有lR(∞o,Yo)一RrI<E。,其中£l为给定的阈值.由此可得第1个判据.
判据1V0≤∞≤M—m,VO≤g≤N一",若lR(∞,g)一RtI<e。成立,则(z,Y)为可能解,否则视为不可能解而抛弃.
由所有的可能解组成一个集合Srmnz.
(2)待匹配图像为原始图像时,全局最优子图的像素平均值J。.。应等于模板的像素平均值T;待
I了
128,模板像素大小选为30×30.实验的硬件配置为Xeon2GHz,4GB内存的DELL服务器,软件使用
MATLAB2008b.
匹配图像为加噪图像时,有—二竺}—;当<e。,其
J¨‰I+ITI
中ez为给定阈值.
(3)待匹配图像为原始图像时,全局最优子图的均方差
一亍I
a狒狒b帆船
圈1测试圈像
Fig.1
Testingimag∞
3.1实验1
GlZo,Vo
2√志蕃蚤瞰‰“一YⅦo㈣]2
一r
在待匹配图像中逐点移动以选取模板,模板数
量为(128—30+1)(128—30+1)=9801.表1的实
应等于模板的均方差
2√去荟孕T“加。]2
厂j—i2广再T—————————一
验结果为每个模板平均需要匹配的子图数量.
衰1可能解的平均数■
Tab.1
Averagequantityofpossiblesolutions
当待匹配图像为加噪图像时.有IaL。.一arl<e。.其中e。为给定阈值.此时可以给出第2个判据如下.
判据2
I了
一亍l
丢生蔫<e2和h.,一O'Tk£3'则(∞,Ⅳ)为
J。I+lTI
“’
V(£,Y)∈S砌,若同时满足
候选最优解,否则视为非最优解而抛弃.
所有候选最优解构成集合S—om,计算该集
合中所有成员的归一化互相关值,其中,全局最优解具有最大的归一化互相关值.
2.2算法流程
本算法基于前述2个判据,称该算法为CNCC,算法流程如下:①读人待匹配图像J和模板T,给定阈值£I,e2和£a;②计算模板的自相关值Rr=
从结果可以看出,不论是pixel—by—pixelNCC或是FNcc,每个模板需要和9801个子图进行匹配,即可能解的平均数量为9801;CNCC在阚值e-的作用下能有效减少可能解的平均数量,且e。越小,可能解的平均数量越少.该实验说明,利用判据1可大幅缩小可能解的范围,而且由于模板已知,所以J对可事先计算好,而互相关矩阵R可通过FFT方法快速箅得,从而有效缩短寻找最优解的时间,提高NCC的匹配速度.
3.2实验2
∑∑Er(i,J)一I]2;③用式(5)得到互相关矩阵
R。;④基于判据1,建立集合SP0sn;⑤基于判据2.确
定集合S一;⑥计算集合Sm∞m中所有成员的归
一化互相关值,取最大值对应的点为全局最优解.
分别在图1a和1b中逐点移动选取模板,图2是在图1上施加高斯噪声(一为噪声的均方差)的图像,作为待匹配图像.实验结果见表2,其中CNCC的3个阈值分别取为:e。=20.00,£:=5.00,e3=0.10.在匹配准确率上,CNCC的表现优于pixel—by—pixelNCC和FNCCI在平均匹配时间上,CNCC与FNCC相差不大.且明显优于pixel—
by-pixelNCC.
3实验
对文中提出的CNCC方法进行验证,分别与pixel—by—pixe[NCC和的FNCC[‘一61进行对比.用于测试的原始图像如图1所示.像素大小都为128×
1236
同济大学学报(自然科学版第39卷
d
口=0.1
e
口=02
fo--03
图2施加噪声的图像
Fig.2
Noisehnages
表2匹配准确率和平均匹配时间
1[铀.2
待匹配图像
Matchingprecisionandaveragematchingtime
算法
塑竖兰1二!!二!!兰!型堕
匹配准确率/%平均匹配时间/ms匹配准确率/%平均匹配时间/ms
坠坚
匹配准确率/%平均匹配时问/ms
3.3实验3
在图1a上逐点移动选取模板,选取图2c作为待匹配图像.测试阔值E-,£2及E。对CNCC方法在
匹配准确率和匹配时间方面的影响的实验结果见表3.
表3舅试阈值对匹配的影响
T址.3
Influeneeofthreethresholdsonmatching
第8期谢维达,等:一种改进的快速归一化互相关算法
表3显示,平均匹配时间随着e,的减小而缩短,匹配准确率随着£,的增大而上升,并在£。达到一定值时稳定;平均匹配时间与£o变化关系不大,匹配准确率随£:的增大而上升,在£:到一定值时稳定;匹配准确率与ss呈抛物线关系,平均匹配时间随es的增大略有增加.
4结论
归一化互相关算法在外界干扰作用的影响下容易产生误匹配.本文根据模板和全局最优子图的特点及其相互关系给出2个判据,对传统的归一化互相关算法进行了改进,提出新的归一化互相关算法CNCC.实验结果说明,CNCC算法能加快运算速度,
且能有效地提高图像匹配的准确率.3个阈值£-,£z
和£。对CNCC匹配性能有着至关重要的影响,如何选取合适的阈值是后续工作的重点.参考文献:
[1]WuQ,Whitman
GJ。Fussell
Ds,eta1.Registration
ofDCEMR
imagesforcomputer-aideddiagnosisofbreast∞ncer[C]//
Fortieth
Asilomar
ConferenceOil
Signal,Systems
and
Computers.Pacific
Grove:IEEE
SignalProcessing
Society.
2006:826—830.
[2]PanWH.、ⅣeiSD,LaiSH.Ahybrid
motion
estimation
approach
based
on
normalizedcrosscorrelation
forvideo
compression[C]//IEEE
InternationalConferenceon
Acoustics.
Speech
and
SignalProcessing.LasVegas:IEEE
Signal
ProcessingSociety.2008:1037—1040.
[3]PaclikP,NovovicovaJ,Duin
RP
W.Buildingclassifiers
using
a
m舶涨[J].IEEE
Road.Sign
trainable
similarity
Transactionson
IntelligentTransportationSystems,2006,7
(3):309.
[4]LewisJ
P.FasttemplatematchingCJ].VisionInterface,1995。
95:120.
[5]T髭i
DM。LinC.Fastnormalized
cr088
correlationfordefect
detection[J].Pattern
Recognition
Letters,2003,24(15)z2625.
[6]HiiAJH.HannC
E,ChaseJG,eta1.Fastnormalized
CROSS
correlation
for
motion
tracking
using
basis
functions[J].
Computer
Methods
and
Programs
inBiomedicine.2006,82
(2):144.
[7]PanWH,w色iS
D,Lai
s
H.Efficient
NCC-based
image
matchingbased
on
novel
hierarchical
bounds[J].Computer
Vision,2008,468.
[8]w色isD,LaisH.FastTemplate
matching
based
on
normalized
cr06s
correlation
withadaptivemultilevelwinnerupdateCJ].
IEEETransactions
on
Image
Processing,2008,17(11):2227.
[9]LiW,salari
E.Successiveelimination
algorithm
formotion
estimation口].IEEETransactions
on
Image
Processing,1995。4
(1):105.
[10]Stefano
LD。Mattoccia
S,Tombari
F.ZNCC-based
template
matching
using
bounded
partial
correlation[J].Pattern
Recognition
Letters,2005,26(14—15):2129.
一种改进的快速归一化互相关算法
作者:作者单位:刊名:英文刊名:年,卷(期):被引用次数:
谢维达, 周宇恒, 寇若岚, XIE Weida, ZHOU Yuheng, KOU Ruolan同济大学铁道与城市轨道交通研究院,上海,201804同济大学学报(自然科学版)
Journal of Tongji University(Natural Science)2011,39(8)8次
参考文献(10条)
1. Wu Q;Whitman G J;Fussell D S Registration of DCE MR images for computer-aided diagnosis of breast cancer 2006
2. Pan W H;Wei S D;Lai S H A hybrid motion estimation approach based on normalized cross correlation for video compression2008
3. PaclikP;Novovicova J;Duin R P W Building Road-Sign classifiers using a trainable similarity measure[外文期刊] 2006(03)4. Lewis J P Fast template matching 1995
5. Tsai D M;Lin C Fast normalized cross correlation for defect detection[外文期刊] 2003(15)
6. Hii A J H;Hann C E;Chase J G Fast normalized cross correlation for motion tracking using basis functions[外文期刊]2006(02)
7. Pan W H;Wei S D;Lai S H Efficient NCC-based image matching based on novel hierarchical bounds 2008(468)
8. Wei S D;Lai S H Fast Template matching based on normalized cross correlation with adaptive multilevel winner update[外文期刊] 2008(11)
9. Li W;Salari E Successive elimination algorithm for motion estimation[外文期刊] 1995(01)
10. Stefano L D;Mattoccia S;Tombafi F ZNCC-based template matching using bounded partial correlation[外文期刊] 2005(14-15)
引证文献(7条)
1. 张鹏雁. 赵耀. 朱振峰 基于商标匹配的视频广告识别[期刊论文]-信号处理 2012(8)
2. 李枫. 刘博 基于尺度空间特征实时手势识别[期刊论文]-佳木斯大学学报(自然科学版) 2013(5)3. 吴强. 侯树艳. 李旭雯 融合图像灰度信息与边缘特征的快速匹配算法[期刊论文]-信号处理 2013(2)
4. 张桂南. 刘志刚. 韩烨. 杨红梅 接触网棒式绝缘子故障检测的快速模糊匹配方法[期刊论文]-铁道学报 2013(5)5. 金守峰. 胡永彪 基于图像的织物速度非接触测量方法[期刊论文]-纺织学报 2013(4)
6. 杨航. 陈建魁. 钟强龙 一种RFID标签天线视觉检测方法与实现[期刊论文]-现代电子技术 2013(20)
7. 柳冠伊. 杨小红. 白明. 魏文军. 张绍英. 李海涛 基于线阵扫描图像的玉米果穗性状检测技术[期刊论文]-农业机械学报 2013(11)
引用本文格式:谢维达. 周宇恒. 寇若岚. XIE Weida. ZHOU Yuheng. KOU Ruolan 一种改进的快速归一化互相关算法[期刊论文]-同济大学学报(自然科学版) 2011(8)