Computer Engineering andApplications算机工程与应用 改进的归一互相关法的灰度图像模板匹配方法 陈丽芳。,刘 渊 ,须文波 CHEN Lifang ,LIU Yuan ,XU Wenbo ̄ 1.江南大学数字媒体学院,江苏无锡214122 2.江南大学物联网工程学院,江苏无锡214122 1.School of Digital Medium。Jiangnan University,Wuxi,Jiangsu 2 14122,China 2.School of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China CHEN Lifang,LIU Yuan,XU Wenbo.Improved normalized correlation method of gray image template matching method. Computer Engineering and Applications,2011,47(26):181・183. Abstract:There are many good qualities in the Normalized Correlation(NC)method.For example,there are high accuracy, high adaptable,strong anti-jamming,li ̄le affection of noise and no false match.But the calculation of the method is complex and the amounts of datum in this method are too large.So it cannot be applied in real time systems.This paper proposes a new method to improve searching arihtmetic of NC method.The experiments show the new method is higher accuracy and fast speed than the NC method. Key words:grey level image;template matching;normalized correlation;search method 摘要:在灰度图像的模板匹配方法中,归一化互相关(NC)法具有很高的准确性和适应性,以及抗干扰能力强,受噪声的影响小 和不存在伪匹配等特点,同时对图像灰度值的线性变换具有“免疫性”。但NC方法计算时间长、计算数据量相对较大,所以实时 性较差。提出通过改进搜索方法以提高归一化互相关(NC)法的运算速度 实验仿真结果证明了改进的归一化互相关(NC)法比 传统的NC方法具有精度高、速度快的特点,有一定的适用价值。 关键词:灰度图像;模板匹配;归一化互相关法;搜索方法 DO1:10.37 78/j.issn.1002—8331.2011.26.050 文章编号:1002.8331(2011)26.0181.03 文献标识码:A 中图分类号:TP391 不同传感器或同一传感器在不同时间、不同视点获得的 1以灰度为基础的匹配 图像,由于:拍摄时间、拍摄角度、自然环境的变化,传感器本身 灰度匹配的基本思想:以统计的观点将图像看成是二维 的缺陷,灰度失真、几何畸变和噪声等因素的影响,给图像匹 信号,采用统计相关的方法寻找信号间的相关匹配。利用两 配工作带来一定程度的困难和问题。 个信号的相关函数,评价它们的相似性以确定同名点。 目前图像匹配在飞机辅助导航、远程武器、光学或雷达图 基于灰度的匹配方法是直接利用图像的灰度值度量两幅 像的目标搜索和跟踪、车辆定位、医学图像处理、人脸识别、指 图像之间的相似性,用某种相似陛度量,判定两幅图像中的对 纹验证、气象预报、遥感影像技术、军事目标的检测与识别、交 应关系。灰度信息匹配方法只对图像的灰度进行处理,避免 通管制、安俭系统、环境监控、网络安全等领域都有着广泛应 了主观因素的影响,可以实现完全自动的匹配。 用。随着人们对高质量图像的需求和对海量数据实时性处理 的要求,姐何将不同图像进行匹配就成为了一个急需解决的 2模板匹配的方法 课题,并具有重大的使用价值和现实意义。 模板匹配法确定在被搜索图中是否有同模板一样的尺寸 图像匹配是指通过一定的匹配算法在两幅或多幅图像之 和方向的目标物,并通过一定的算法来找到它以及其在被搜 间识别同名点。在图像处理领域,已提出了相当多的图像匹 索图中的坐标位置,是根据已知模板图,到另一幅图像中搜索 配方法,目前主要有以灰度为基础的匹配和以特征为基础的 相匹配的子图像的过程 。模板就是一幅已知的小图像,通常 匹配。由于基于灰度的图像匹配算法理论已经较为成熟,算 模板越大,匹配速度越陧;模板越小,匹配速度越陕。 法原理简单,易于硬件实现,其对成像畸变适应能力弱的缺 模板匹配法也是一种基于灰度互相关的匹配方法,该算 点,可以通:过图像校正加以克服。而基于特征的图像匹配算 法研究在一幅图像中是否存在某已知模板图像。如图1所示, 法比较复杂,对图像噪声适应能力较差川,本文提出基于灰度 (a)为参考图 , 的大小是N×Ⅳ;(b)为模板图 , 的大小是 的利用归一化互相关法的模板匹配。 x 匹配时将模板图叠放在参考图上平移,模板覆盖下的 基金项日:江苏省科技厅基金项目(No.SBE200800983);江南大学自主科研计划(N0.JUSRP30909)。 作者简介:陈丽芳(1973一),女,硕士,副教授,主研方向:图像处理、计算机应用;刘渊(1967一),男,硕士,教授;须文波(1946一),男,博导。 B‘mail:may7366@163.corn 收稿日期:2011-02.25;修回日期:2011-04—28 Computer Engineering andApplications计算机工程与应用 部分叫做搜索子图 ”,则f√是这块搜索子图的左下角像点 在 图中的坐标,叫做参考点。可以选用不同的相似性度量来 非匹配点上,为了提高运算时间,可以采用隔行隔列甚至更大 的定步长,也可以根据灰度特性采用变步长的方式进行。主 衡量丁和 。之间的相似程度。 Ⅳ 口 N M (a)参考图像 (Ⅳ×Ⅳ) (b)模板图像T(Mx^ 图1模板匹配示意图 3归一化互相关法NC 归一化互相关匹配算法是图像匹配算法中较为经典的匹 配算法。通过计算参考图和模板图之间的互相关度量值来确 定二者的匹配程度,度量值大小反映了参考图和模板图之间 的相似程度。度量值^ (f ,)值越大,则表示搜索子图上的(f ,) 位置和模板越相似。当NC(i,J)等于1的时候,为匹配位置。 当然,常常由于不同传感器或同一传感器在不同时间、不同视 点获得的图像在空间上往往会存在差异、自然环境的变化、传 感器本身的缺陷、图像噪声的影响,因此很难找到^rC值为1的 位置。通常只需要在参考图上找到最大度量值ArC的位置,为 最佳匹配位置。归一化互相关法度量值的计算形式如下: MⅣ ∑∑r(m,n)S , NC(i, = — ——一 (1) 、fm=In=If∑∑ ( , 坍=IH=1∑∑ , ) 其中, , 为模板图像倒数第n行,第m个像素值;S 为 模板覆盖下的部分,称为搜索子图,f、,是搜索子图的左下角像 点在参考图 中的坐标。 4改进传统NC算法的搜索策略 传统的模板匹配的基本算法就是将模板图在搜索图上遍 历所有可能的位置,从中找出相关度最大位置即认为是匹配 位置。由于传统做法需要遍历所有点,当模板图很大的情况 下,显然其计算量是相当大的,要加快运算速度比较有效的方 法是减少搜索位置和每个位置处的计算量,所以提出了变换 模板图和改变搜索步长的方法来加快匹配的速度,并通过实 验验证了该方法的准确性和快速性。 (1)变换模板 变换模板图存在两种情况:一种是参考图和模板图都比 较大的情况,先按照一定的比例同时缩小参考图和模板图,寻 找出大概位置后,从原始参考图中截取参考图的有效性区域, 利用有效性区域和原始模板图进行匹配;另一种是当模板图 比较大的情况下,根据一些明显特性,利用手工比对的方法先 把模板图的特征区域截取出来,利用特征区域模板图和参考 图进行匹配,得到参考图的候选区域,最后再利用原始模板图 和候选区域进行匹配得到所要的结果。 (2)改变搜索步长 传统模板匹配,都是遍历每点,这样会浪费大量的时间在 要有两种情况:对参考图采用隔行隔列,模板图遍历每点的形 式,使参与运算的数据量减少到原来的1/4;对参考图和模板 图都采用隔行隔列,使参与运算的数据量减少到原来的1/ 16。通过实验发现这两种情况都没有影响匹配的准确度,但 运算时间却大大缩短(参见表1)。 5实验仿真 本文利用VC6.0为编程环境,分别实现了传统NC算法和 改进NC算法的匹配。为了验证NC算法的精确性,同时实现 了绝对差搜索法(ABS)算法的匹配,并进行了比较分析。 5.1 改进NC算法和绝对差搜索法算法匹配结果比较 分别在图像质量较差、字母查找、参考图相似部分较多的情 况下,和绝对差搜索法(ASS)算法进行比较。比较结果如下: (1)参考图图像质量较差的情况,例如存在噪声等。实验 参考图如图2所示;模板图如图3所示;ABS算法匹配结果如 图4所示;改进NC算法匹配结果如图5所示。 ■■■ 图2参考图 图3模板图 图4 ABS匹配结果 图5改进NC方法匹配结果 从匹配结果图可以看出,当参考图存在一定噪声的影响, 模板图比较正常的情况下,改进的NC算法可以准确的匹配, 而ABS算法却无法准备匹配。 (2)字母查找的情况。实验参考图如图6所示;模板图如 图7所示;ABS算法匹配结果如图8所示;改进NC算法匹配结 果如图9所示。 b|b |b b燃h 蝴gbl》 b{鞣Kl曲酾g p辨 0触 牌 P 螅p p p I …… ∞拣m … &m 蛐日 帆mm f ¥墒辆fm‰ s觚; , 幽 4 d哪d 臻《{礴张撕秘 d畔 { l 9嗍 Ht柚# 姚nt ≈鹕触g # 0蝴 蝌矗 晦g # ¥ } l1 k 粕) 8l《 酶鼬{#e斡 轴 辩8妇s #科ge 科 g 《 鼢n E雌g,mgg魄g h虹 聃*k姆k嗽确辫 #啊 h 辨 h能h蚰g 锦g *4 { J 鼬 艄 引 £。 q 《g 0m 獬 《 辨 ∞ 端 亦 啦e l南 砧 o蜘 辨《獬 本辩g 蝮 a 蠛 ‘ # 端豳辩捣聃g 一 柱睡 s t碡l 晦鞔鼎 辨照热抽}鹞‘ ¥矬・ #” 娜 獬l姐l螺 W 辅‘ 黔聪≈ l *璐 蚺 £姐 q嚣l 姊u札n %媳 鹊g t… { 辨”n 辩 ang嘲S・ 9 w 科 mO ‘‘矗 图6字母参考图 图7字母模板图 陈丽芳,刘 渊,须文波:改进的归一互相关法的灰度图像模板匹配方法 虹 9 bR ba。b b b g % lc bi? ̄qK¨kn鼬 一 # p王n p∞paag Spi pie 0 飘 F ng ……弹;w}0 9 … gm g ,* mj … …m‘郎t f趣如撕如 融缸g船 颤dcdaIde【电 4 I daⅡd g d髀gmdie《m《u d 曲g- t{ lt 9…Et1Bt tS曝 t1c 9t …g・ M … 五目 9粥n g…E 粥nn 辩 E l Jlak l l {ou鲰 gl媳 趋毒l_c 斡h m&I B・ § g g g郫B gg & h k k km k观g hah£ n b h雕hcn蛔 e , j#】‘ 张Ⅲ 脯J#a+ q q 0 q q 0 q1 酶 & sm 々 S ’ 4珈 驰e 庙 和 雄 毒砒砖 血 g ・ 曲 a du 娃 Ⅱt 鹏 如; 《端s 由唾§^c l {ao 辨 阻 曲 鹣 g H … g IS・ {拜g o舶 哪州 #“#0 s F 乱 啊s{珏 ’… ∞ 蝌H∞5∞‘ g E X 瑚 ye 9 ’ w H gw郸 ・ 图8 ABS算法匹配结果 bba b 脚b拙g ibi ”{bin pi融删辩 g艄 弹 m0【 划 ∞ ma …mm g唧 m¨ 獬 m m 胁 M №kg g t 和dtdmd 如 和 d蚺d lgd黔g de 《 g・ I t拙蛳 nt n ・ I D “。 镍Ⅱ n景* g l" "… } I {la 珥It4 q1 轴% 照lie I 酶1 l lg随 鲥辩 胖 B№g gang§魄 ka k k。 k k眦kln ・ bh hm hlⅡg h# ・ 1 t1擀 端 q m q 螅m 辩mH q q 弧 } { 9 " 哺。 聃蚺 鸡l曲 ;脚破 本 碡 4l镐g t ch碡 鼬}£b cl ∞ A∞g 出 l e I s 珈 目 蛳 ^ni 瑚# 貅 ” 鳞 #∞%# c越蝴 * …辙 } g{#期 yoa y s 抟 H y g— m 研W辨 聃 g删 图9改进NC方法匹配结果 由于字母之间存在相似形状,并且所占面积较小,所以虽 然参考图和模板图的质量一致,但ABS算法还是出现误匹配 的情况,而改进的NC算法仍能准确匹配。 (3)参考图相似部分较多的情况。实验参考图如图10所 示;模板图如图11所示;ABS算法匹配结果如图12所示;改进 Nc算法匹配结果如图13所示。 图10参考图图11模板图图12 ABS算 图13改进NC方 法匹配结果 法匹配结果 从匹配结果可以看出,在相似部分较多的情况下,并且参 考图和模板图的质量情况相同下,ABS算法和NC算法都能准 确的找到匹配结果。 5.2传统NC算法匹配和改进NC算法的比较 (1)精确度的比较 因为模板图越大,匹配时间就越长,所以为了充分展现改 进NC算法的运行时问优势,参考图仍然采用图2所示的图;模 板图则采用如图14所示;传统Nc算法的匹配结果如图15所示; 图14模板图 图15传统NC匹配结果 改进NC方法1(先利用手工比对把特征区域找出,并且采用参 考图隔行隔列搜索方式)的匹配结果如图16所示;方法2(先利 用手工比对把特征区域找出,并且采用参考图和模板图隔行 隔列搜索方式)的匹配结果如图l7所示。从匹配结果图可以 看出,匹配位置基本一致,对于前面提到的字母查找匹配和参 考图相似部分较多情况匹配也进行了比较,传统和改进的NC 算法匹配精度基本相当,因此改进算法之后,匹配的准确度没 有受到影响。 图16改进NC方法1匹配结果图17改进NC方法2匹配结果 (2)运行时间比较 分别在参考图质量良好和质量较差的两种睛况下,统计传 统NC算法和改进NC算法的运行时间。具体数据如表1所示。 表1运行时问表 s 从表1可以看出,改进NC算法在运行时间上具有绝对的 优势,大大缩短了运行时间。 6结论 从仿真实验的结果可以看出,改进的NC算法仍然具有很 高的准确性和适应性,受噪声的影响小、抗干扰能力强以及算 法不存在伪匹配等特点,同时大大地缩短了算法的运行时间, 可以应用在一些实时l生要求比较高的场合。但目前在参考图 和模板图较大的情况下,存在人工比对干预。今后将研究结 合特征匹配的方法进行自动初始匹配,生成参考图的候选区 域,扩大该方法的应用范围。 参考文献: [1]张强.图像匹配算法研究[D].西安:西安电子科技大学,2006. [2]Ding L,Goshtasby A,Satter M.Volume image registration by tem— plate matching[J].Image and Vision Computing,2001,19:821-832. [3]王岩松,阮秋琦.—种基于互相关的图像定位匹配算法研究及应用[J]. 北方交通大学学报,2002,26(2):20.24. [4王红梅,4]张科,李言俊.图像匹配研究进展[J].计算机工程与应用, 2004,40(19):42.44. [5】Zhao Chunjiang,Shi Wenkang,Deng Yong.A new Hausdorff dis— tance for image matching[J].Pattem Recognition Letters,2005, 26:581.586. [6]Chen Jiunhung,Chen Chusong,Chen Yongsheng.Fast algorithm for robust template matching with M—estimators[J].IEEE Trnasac— tions on Signal Processing,2003,5 1(1):230—243. [7]章毓晋.图像处理和分析基础【M].北京:高等教育出版社,2002.