自适应连续多级分区和初始阈值估计的快速模板匹配

孙静晶　马占欣　张　鹏　汪鲁才

(1.鹤壁汽车工程职业学院　鹤壁　458030)(2.漯河技师学院　漯河　462000)(3.湖南师范大学　长沙　410081)

自适应连续多级分区和初始阈值估计的快速模板匹配

孙静晶1马占欣2张鹏1汪鲁才3

(1.鹤壁汽车工程职业学院鹤壁458030)(2.漯河技师学院漯河462000)(3.湖南师范大学长沙410081)

摘要论文提出了一种基于归一化互相关测度(NCC)的通过结合自适应连续多级分区和初始阈值估计实现高效搜索的快速模板匹配算法。归一化互相关测度在光照改变时,比采用绝对差之和测度(SAD)要稳定,但是归一化互相关测度的缺陷在于它的计算量非常大。为了解决这一问题,论文根据模板图像中不同模块的梯度值,将模板图像进行逐级分区,通过分区顺序将互相关之和分为不同的层,得到各层互相关的上界,运用柯西-施瓦兹不等式得到上界间的关系,形成自适应连续多级分区淘汰方法。同时,为了进一步加快匹配速度,论文利用初始阈值估计产生一个较大的边界阈值,以淘汰初始搜索时的大量非匹配点,减少搜索点数目。实验结果表明,论文提出的算法在不降低匹配精度的前提下,算法的执行速度比FS算法快将近30倍,比FFT算法快将近2倍,优于EBC算法。

关键词自适应连续多级分区; 归一化互相关; 部分边界相关; 增强边界相关

Class NumberTP391

1引言

模板匹配在目标跟踪,机器视觉和图像编码等图像处理领域具有重要的作用。模板匹配快速算法主要有两类:一类为非穷举搜索算法,它通过减少搜索点的数目来实现快速运算。B. Zitova等提出通过减少搜索范围[1]来节省计算时间,H. Schweitzer等通过分解模板或者图像为多个矩形区域并将每个矩形区域近似为一个多项式[2]来达到快速运算的目的。但这些算法找到的匹配点可能是局部最优点。另一类穷举搜索算法主要通过降低每个搜索点上的计算量来实现快速运算。它的优点在于找到的匹配点是全局最优点。在基于相异性测度的搜索中,C. D. Bei等提出部分失真淘汰算法(PDE)[3],它的思想是如果当前失真测度大于当前最小值时,立刻停止评估。而后,一系列新的算法被提出:W.Li等提出连续淘汰算法(SEA)[4],C.Lee等提出模块和金子塔算法(BSP)[5],X.Q.Gao等提出多级连续淘汰算法(MSEA)[6],C.Wang等提出赢墩领出算法(WUS)[7]。但这些算法是基于SAD测度的,所以对光照的变化都比较敏感。而基于相关性测度的归一化互相关测度在光照变化时比绝对差值和(SAD)和平方差和(SSD)测度更稳定,在目标识别和工业检测等领域应用广泛。J. P. Lewis等通过在频域利用FFT算法来计算相关性[8～9]实现快速运算。S. Mattoccia等提出加强边界相关算法EBC[10],虽然EBC的算法执行速度比FFT快,但EBC算法将模板分为均等的子模块,所以得到的边界仍不足以抑制可观的搜索点。

本文通过对MSEA算法进行扩展,将其应用到NCC测度中,提出了一种基于NCC测度的快速模板匹配算法,算法主要由两部分组成:自适应连续多级分区及初始阈值估计。自适应连续多级分区利用图像的复杂度实现高效的子模块的划分,提供了一个比MSEA更严格的边界,而且可以在较早阶段跳过更多的非匹配点的搜索;初始阈值估计产生一个较大的边界阈值,它有效地抑制了开始阶段搜索点的数目。实验表明,提出的算法不但能实现比FFT、EBC更快的匹配速度,而且能够保证匹配的精度。

2自适应连续多级分区的快速模板匹配算法

设T为一大小为n*n的模板,I为原始图像,大小为M*N。基于NCC的模板匹配通过寻找NCC函数的最大值,将模板T定位到I中,如图1所示。记当前模板在图像中的位置为(x,y),当前候选子图为Ic(x,y)。

(1)

其中,ψ(x,y)为原始图中候选子图和模板之间的互相关值,‖IC(x,y)‖和‖T‖分别代表原始图中候选子图和模板图的自相关值。

图1　模板匹配图

IMssn(x,y)=IIss(x+n-1,y+n-1)

+IIss(x-1,y-1)-IIss(x+n-1,y-1)

-IIss(x-1,y+n-1)

(2)

TMssa(x,y)=ITss(x+a-1,y+a-1)

+ITss(x-1,y-1)-ITss(x+a-1,y-1)

-ITss(x-1,y+a-1)

(3)

对于NCC中的自相关ψ(x,y)的计算,本文采用自适应多级连续分区算法实现快速运算。如图2所示,将模板图像进行自适应连续多级分区,根据分区顺序计算各层的上界,进行初始阈值估计后,采取多级连续淘汰获得最优匹配区域。

2.1自适应连续多级分区策略

图2　自适应连续多级分区和初始阈值估计的快速模板匹配算法框图

2.1.1柯西-施瓦兹不等式的推广

通过柯西-施瓦兹不等式,文献[10]中已经证明:

如果a,b∈Rp,A={1,2,…,p},则存在r∈{1,2,…,p}

A1∪A2…Ar=S

Ai∩Aj=∅,∀i≠j,(i,j∈{1,2,…,r})

则下面的不等式成立:

(4)

2.1.2自适应多级连续分区策略

图3　自适应多级连续分区策略

2.2利用分区策略计算上界

本文将每个子模块信息用模块的起点坐标,模块大小,模块梯度幅度和,模块分层层数以及模板起始位置来标记。

1) 取得各层模块的标记

设模板图像标记为(x,y,n,sg,r,p),即模板的起点坐标为(x,y),模板的大小为n*n,模板的梯度幅度和为sg,模板分层的层数r,模板存放的起始位置p。

Repeat:

(1)从所有的模块标记信息中选择具有最大梯度幅度和的模块设它的标记为(x1,y1,n1,sg1,r,p1)。

(2)将标记信息中层数信息为r的不具有最大梯度幅度和的所有模块的标记信息中的层数信息加一。

(3)将所选的具有最大梯度和的模块分为四个子模块,分别计算它们的梯度幅度和。

(4)检查四个子模块,如果子模块的梯度幅度和大于一个给定阈值T,将模块存入起始位置分别为

p1,p1+(n1/2*n1/2),p1+2*(n1/2)*(n1/2),p1+3*(n1/2)*(n1/2)的存储区域。为简便起见,这里将存储区域的起始位置分别标注为p11,p,p13,p14。

本文中T设置为0,以得到和全搜索(FS)NCC一样的精度,找到全局最优点。如果T设置得大些,可进一步提高算法的运算时间,但匹配精度下降。

(5)将四个子模块分别标记为

(x1,y1,n1/2,sg11,r+1,p11),(x1+n1/2,y1,n1/2,sg12,r+1,p12),(x1,y1+n1/2,n1/2,sg13,r+1,p13),(x1+n1/2,y1+n1/2,n1/2,sg14,r+1,p14)。

Until:所有子模块的梯度幅度和均小于阈值。

2) 计算NCC上界

第r层互相关的上界

(5)

在计算βr(x,y)时,先查找模块标记信息中层数信息为r的所有模块标记。通过标记信息中的(x,y,n)即起点坐标,模块大小,利用式(2)和式(3)完成上界的计算。

λ0≥λ1≥…λr≥…λmaxL≥NCC

(6)

其中NCC为归一化互相关值。如果阈值T设置为0,则λmaxL=NCC。

2.3初始阈值估计

利用阈值NCCmax淘汰搜索点的模板匹配方法,通常设置一个可能出现的最小值,例如0,给NCCmax,这个值随后被计算得到的当前的NCCmax替代。这是一种降低计算量的有效方法。然而,最匹配点的坐标通常不知道,如果最优点在起始搜索点附近,那么快速搜索到目标;相反,如果最优点远离起始点搜索,则需要较多的计算时间。如果我们在搜索开始之前估计一个较大的阈值,和在正确匹配点处NCCmax的值相同或者近似,那么更多的搜索点可以在搜索过程中淘汰,计算量将大大降低。当然,利用估计阈值进行穷举搜索一般都能找到全局最优匹配的点,而不会陷入局部最优点。本文获取初始阈值的方法如图4所示。其中原始图大小为M*N,模板大小为n*n。

图4　初始阈值估计算法流程图

2.4利用自适应连续多级分区进行连续多级淘汰

在获得初始估计阈值后,便可进行连续多级淘汰,如图5所示,获取最优匹配位置。其中原始图大小为M*N,模板大小为n*n。

图5　连续多级淘汰方法流程图

3实验结果

为验证所提出算法的有效性,本文将提出的算法和全搜索算法(FS),相关率Cr=50%的BPC算法,基于SAD的WUS算法,FFT算法,以及EBC算法进行了比较。实验在intel P4 2.1G CPU,2G内存的个人电脑上进行,采用C语言及Matlab编程。本文采用256*256的lena图,如图6(a)所示,以及加入σ=16的随机高斯噪声之后的lena图作为原始图,如图6(b)所示。采用从原始图中选取的大小分别为64*64,128*128的子图,如图7中,模板1及模板3所示,以及它们提高50%亮度之后的图作为模板图,如图7中,模板2及模板4所示。

表1展示了采用256*256的lena图作为原始图,选取不同的模板图的匹配结果。从表中可以看出,本文提出的算法在采用模板2,4时仍能保证匹配的精度,即不受光照变化的影响。而算法的执行时间比FS快了近30倍,比FFT算法快了近2倍,比EBC算法也要快。而WUS(SAD)算法虽然匹配速度较快,但在模板图象的亮度变化时,匹配位置出错。

表2展示了在256*256的lena图上叠加σ=16的随机高斯噪声之后的lena图作为原始图,选取不同的模板图像的匹配结果,从表中可以看出,提出的算法在原始图受噪声污染时,仍能保证匹配位置的正确性,而且匹配速度几乎不受噪声影响。

图6　原始图

图7　模板图

算法原始图类型T(1)T(2)T(3)T(4)全局搜索算法(FS)a3271314350314925(BPC)a1501142525162347WUS(SAD)a43*11772*165FFTa116139213232EBCa8691143161提出的算法a62799497

其中,T(i)(1≤i≤4)表示选择第i个模板后,各个算法的执行时间,单位为ms。

表2　对图1(b),采用不同模板后,

其中,T(i)(1≤i≤4)表示选择第i个模板后,各个算法的执行时间,单位为ms.

4结语

本文提出了一种基于NCC测度的非常高效的模板匹配算法。将自适应连续多级分区方法结合初始阈值估计实现高效计算。自适应连续多级分区利用图像的复杂度实现高效的子模块的划分,提供了一个比MSEA更严格的边界。而且可以在较早阶段跳过更多的非匹配点的搜索;初始阈值估计产生了一个较大的边界阈值,它有效的抑制了开始阶段搜索点的数目。实验结果表明,提出的算法比FS快近30倍,比FFT快近2倍,优于EBC算法;而且在光照变化和随机噪声的影响下,仍能保证匹配的精度。

参 考 文 献

[1] B. Zitova, J. Flusser. Image registration methods: a survey[J]. Image Vis. Comput,2003,21(11):977-1000.

[2] H. Schweitzer, J. W. Bell, F. Wu. Very fast template matching[C]//Proc. Eur. Conf. Computer Vision,2002:358-372.

[3] C. D. Bei, R. M. Gray. An improvement of the minimum distortion encoding algorithm for vector quantization[J]. IEEE Trans. Commun.,1985,COM-33(10):1132-1133.

[4] 赵鹏,白振兴,范文同.基于主成分分析的快速图像匹配研究[J].电子技术应用,2010(4):132-134.

ZHAO Peng. white rejuvenation; model; fast image matching based on principal component analysis[J]. Electronic Technology Application,2010(4):132-134.

[5] 温兆麟,陈新,郑德涛.用快速归一化互相关进行缺陷检测[J].广州航海高等专科学校学报,2006(2):29-31.

WEN Zhaolin, CHEN Xin, ZHENG Detao. Defect detection using fast normalized cross correlation[J]. Journal of Guangzhou Maritime College,2006(2):29-31.

[6] 蔡新建,鲜勇,张大巧.基于多线程的巡航导弹景象匹配技术研究[J].弹箭与制导学报,2010(2):32-34.

CAI Xinjian, XIAN Yong, ZHANG Daqiao. The research on the technique of multi thread based cruise missile scene matching[J].

[7] 黄真宝,陈阳.图像匹配中NCC算法的一种快速实现方法[J].信息化研究,2011(2):48-52.

HUANG Zhenbao, CHEN Yang. NCC algorithm[J]. Information Research,2011(2):48-52.

[8] 孔凡芝,王以忠,李君兰,等.引线键合匹配定位算法研究[J].微计算机信息,2008(30):232-233.

KONG Fanzhi, WANG Yizhong, LI Junlan, et al. Lead bonding matching localization algorithm research[J]. Micro Computer Information,2008(30):232-233.

[9] 孙卜郊,周东华.基于NCC的快速匹配算法[J].传感器与微系统,2007(9):104-106.

SUN Bujiao, ZHOU Donghua. Fast matching algorithm based on NCC[J]. Sensor,2007(9):104-106.

[10] 杨兵,于秋则,刘永才,等.基于新的加权互相关的图像匹配[J].弹箭与制导学报,2008(4):199-202.

in the autumn, YANG Bing, LIU Yongcai, et al. New image correlation matching based on weighted[J]. Missiles and Guidance Journal,2008(4):199-202.

[11] 郭伟,赵亦工,谢振华.一种改进的红外图像归一化互相关匹配算法[J].光子学报,2009(1):189-193.

GUO Wei, ZHAO Yigong, XIE Zhenhua. One kind of improved infrared image normalized mutual correlation matching algorithm[J].:189-193

[12] 范新南,朱佳媛.基于小波变换的快速图像匹配算法与实现[J].计算机工程与设计,2009(20):4674-4676.

FAN Xinnan, ZHU Jiayuan. fast image matching algorithm based on wavelet transform and[J]. Computer Engineering and Design,2009(20):4674-4676.

[13] 孙祖鑫,吴强.一种基于TS201的归一化互相关快速算法[J].现代电子技术,2010(10):125-127.

SUN Zuxin, WU Qiang. A fast algorithm for normalized cross correlation based on TS201[J]. Modern Electronic Technology,2010(10):125-127.

Adaptive Continuous Multistage Partition and the Initial Threshold Estimation Fast Template Matching

SUN JingjingMA ZhanxinZHANG PengWANG Lucai

(1. Hebi Automotive Engineering Vocational College Teachers of Department of Electronics, Hebi458030)(2. Luohe Institute of Technician Director, Luohe462000)(3. Hunan Nomal University, Changsha410081)

AbstractIn this paper, a fast template matching algorithm based on normalized mutual correlation measure(NCC) is proposed to achieve efficient search by combining adaptive continuous multilevel partitioning and initial threshold estimation. The normalized cross correlation measure is stable in the light of the change of illumination, but the defect of the normalized cross correlation measure is that it is very large. In order to solve this problem, this paper divides the template image into different layers according to the gradient values of different modules in the template image, and gets the upper bound of the correlation between the different layers. The upper bound is obtained by using the Schwartz Cauchy inequality. At the same time, in order to further speed up the matching speed, this paper uses the initial threshold estimation to generate a large number of non matching points, and reduce the number of search points. The experimental results show that the proposed algorithm is faster than the algorithm without reducing the matching accuracy. The algorithm is nearly 30 times faster than the FS algorithm. It is nearly 2 times faster than the FFT algorithm. It is better than the EBC algorithm.

Key Wordsadaptive continuous multilevel partitioning, normalized cross correlation, partial boundary correlation, enhanced boundary correlation

收稿日期:2015年12月1日,修回日期:2016年1月7日

作者简介:孙静晶,女,助教,研究方向:电子技术教育。马占欣,男,高级实习指导教师,研究方向:自动化专业。张鹏,男,硕士研究生,研究方向:汽车维修。汪鲁才,男,博士,教授,硕士生导师,研究方向:图像处理与模式识别。

中图分类号TP391

DOI:10.3969/j.issn.1672-9722.2016.06.014