三种典型模板匹配算法性能比较

吴成茂， 郭 锐

(西安邮电大学 电子工程学院， 陕西 西安 710121)

三种典型模板匹配算法性能比较

吴成茂， 郭 锐

(西安邮电大学 电子工程学院， 陕西 西安 710121)

为了在图像识别、配准和拼接等具体问题中能够针对不同条件来合理选取适当的匹配算法，详细介绍三种典型模板匹配算法，即基于索引表的图像匹配算法、基于图像相关性的图像匹配算法和序贯相似性检测算法(SequentialSimilarityDetectionAlgorithm，SSDA)，并从实时性、鲁棒性和精确性等角度出发，对其匹配性能进行差异分析。采用分组实验的方法对匹配算法的各项性能指标进行测试和比较，结果表明，三种算法都具有良好的精确性，其中基于索引表的算法和序贯相似性检测算法具有较好的实时性，而基于图像相关性的算法在噪声环境下具有良好的鲁棒性。

模板匹配；性能比较；实时性；鲁棒性；精确性

伴随着计算机科学技术的发展，图像匹配已经成为图像信息处理领域中不可或缺的一项重要技术，其应用已从最早的军事领域逐渐扩大到遥感监测、地理测绘、导航制导[1]、医疗诊断、机器人视觉、图像三维重构[2]以及雷达图像模板跟踪[3]等各项军事及民用领域。将匹配算法应用在高分辨率遥感图像中，有助于更好地获取地理信息，准确实现目标定位与识别等，具有重要的军用和民用价值，然而，实际应用却因为算法的检索策略、鲁棒性的差异以及外界环境的影响等，有时会导致匹配效果不理想。为了提高工作效率，并在噪声环境下获得较为理想的匹配效果，从众多的算法中根据实际情况来选取适当的图像匹配算法是十分必要的。

本文从鲁棒性，实时性和精确性三个方面来分析比较基于图像相关性的算法[4]，基于索引表的算法[5]以及序贯相似性检测算法(Sequential Similarity Detection Algorithm，SSDA)[6-7]三种匹配算法的性能，通过对算法的思想进行理论分析并用Matlab进行实验仿真，根据实验结果对三种算法的性能进行比较和评述，从而服务于今后在实际应用中匹配算法的适当选取。

1 模板匹配算法描述

先介绍三种典型的图像匹配算法，它们是基于索引表的算法，基于图像相关性的算法和序贯相似性检测算法(SSDA)，并对这三种算法的思想和步骤进行详细描述。

1.1 基于索引表的图像匹配算法

给出一幅图像，其矩阵表示如图1所示。

图1 图像矩阵

根据图像矩阵构建图像索引表[4]。先将矩阵中的每个元素，即图像像素的灰度值列举出来, 再依次将灰度值与之相等的元素的坐标放在该灰度值所在的行中。

与原图像相关的索引表如图2所示。构造索引表的时间复杂度为O(n2)，其中n为图像的宽度(或长度)。

图2 图像索引表

模板的图像矩阵如图3所示,而图1所示即为待匹配的图像。

图3 模板图像矩阵

在最差情况下，即需经过最多次的匹配才得到匹配结果，此时的时间复杂度为O(m2)，其中m为模板的宽度(或长度)。

引入边界概念，不仅列举出与模板中像素灰度值完全相等的元素，而且设置一个边界值，将与模板中第一个像素的灰度值相差在边界值范围内的待匹配像素都列举出来。例如，设置边界值为10,列举符合边界条件的待选图像矩阵，如图4所示。

图4 待选图像矩阵

引入惩罚数概念，当已选出待选匹配方案后，待选图像的下一像素的灰度值和模板中相应的像素灰度值相差超过边界值的范围时，惩罚数加1；若未超过边界值，则惩罚数保持不变，然后再与下一个比较，直到遍历模板中的所有元素后，得到惩罚数表，如图5所示。

图5 惩罚数表

在遍历模板中所有元素后，选取惩罚数累加和最小的项。从图5的惩罚数表中容易看出，图4中以点(1,2)为起始点的待选图像是最优解。图6中的深色阴影部分就是待匹配图像中与模板相符的图像。

图6 匹配结果

1.2 基于图像相关性的图像匹配算法

首先考虑一个3×3的参考图像Ir，待匹配的目标图像为It。参考图像矩阵Ir的中心点Ir(x,y)，坐标为(x,y)，如图7所示[3]。

图7 3×3图像矩阵

当评估矩阵中相邻像素的顺序一致性时，需要对每个像素跟与它相邻的其他8个像素间进行计算，即共有72个像素对。为了简化运算，现只考虑水平和垂直方向的像素对，如图7所示，仅有18个像素对。分别定义Ir(x,y)的水平与垂直的左差值为

(1)

(2)

Ir(x,y)的水平与垂直的中心差值为

(3)

(4)

φ(x,y)=

(5)

在实际应用中，将上述的方法扩展到一个大小为M×N的区域中，然后逐点计算区域中的每一个元素的φ(x,y)。为了不重复运算，对于每一个像素，仅需计算其水平方向的左差值与中心差值，以及垂直方向的左差值与中心差值，即将之前的18次运算缩减为4次运算。由此，在大小为M×N的区域中，从点(x1,y1)开始的参考图像和与其相对应的从位置点(x2,y2)开始的目标图像，二者的匹配函数为四个相关量的和,即

(6)

其中

(d∈{v,h},s∈{l,c})。

(7)

最后采用归一化步骤，将Φ(x1,y1,x2,y2)除以其各项的范数，得

ΦN(x1,y1,x2,y2)=

(8)

其中

‖R(x1,y1)‖=

(9)

‖T(x2,y2)‖=

(10)

(11)

1.3 序贯相似性检测算法

序贯相似性检测算法[7]是对传统模板匹配算法的改进。设待匹配图像S大小为N×N，匹配的模板T大小为M×M，Si,j为模板覆盖下的搜索子图，其中(1

定义绝对误差

ε(i,j,mk,nk)=|Si,j(mk,nk)-

(12)

(13)

(14)

选取一个固定阈值Tk。在搜索子图Si,j中随机抽取像素点，计算其与T中所对应点的误差值ε，再把该点的差值跟其它点对的差值累加，经R次累加后，误差超过阈值Tk时，停止并记录累加的次数R，在这里将SSDA的检测曲面定义为

I(i,j)=

(15)

若计算不超过Tk，则继续计算(i,j)处的下一个随机点的误差值，直至超过了阈值Tk，记录下次数。

当I(i,j)取到最大值时，将其坐标(i,j)作为匹配点，即最终匹配结果。在该点上需很多次累加才能使得总误差超过选定的阈值。

2 算法性能及复杂性分析

根据三种算法各自的特点，分别分析它们的性能和复杂性。

2.1 索引表算法分析

基于索引表的图像匹配算法的性能从很大程度上来说，是取决于对边界值(相当于阈值)的选取。当边界值选取较大时，匹配时抗噪性得到提高，但会额外增加计算量；而当边界值取得过小时，虽然提高了匹配速度，但若图像中存在噪声干扰，就可能得不到匹配结果或者得到错误的最优值。因此，根据待匹配图像的大小、纹理复杂程度等情况并通过调试来选取适当的边界值，会增强算法对应用环境的适应能力，提高算法的鲁棒性。

若模板大小为m×m，在最糟糕的情况下，即需经过最多次匹配，遍历模板中的所有元素才能得到匹配结果，此时算法的时间复杂度为O(m2)。由于本算法中的惩罚数的计数步骤均为加法运算，运算量较小，所以具有较高的运行效率。

2.2 相关性算法分析

基于相关性的图像匹配算法在传统的基于绝对差和(SAD)以及基于平方差和(SSD)的算法基础上，结合了归一化互相关方法(NCC)和零均值归一化互相关方法(ZNCC)的思想，利用其相对抗噪能力强的特点，降低了外界因素对匹配的影响，提高了算法的抗噪性。在不同的光照及噪声条件下，基于相关性的算法，表现出良好的鲁棒性和精确性；ZNCC的匹配效果要逊色于相关性算法；而传统的NCC和SSD在光照变化较大的情况中，效果十分不理想。现已有学者提出了基于NCC的加权算法(WNCC)[12]，其对二值化阈值的敏感性较小，具有一定抗噪性，但其计算量较大，每一次循环运算都需要执行数次累加、求平方以及求平方差运算等，因此运行效率较低。

2.3 序贯相似性检测算法分析

SSDA算法是对传统匹配策略的改进，通过随机选取像素和设定阈值来快速的丢弃不匹配的点，减少计算量从而提高效率，算法简单也容易实现。然而传统SSDA算法并不具备较强的抗噪能力，为提高其鲁棒性，可采用如下方法对噪声进行预处理：计算每个待匹配区域中第k点的误差ε(i,j,mk,nk)，与定义的阈值Tk进行比较，若大于Tk，则认为误差由噪声引起，丢弃该结果，不加入误差总和中，并对该噪声点计数，若待匹配区域内噪声点个数大于定义的阈值，停止运算并记录次数；若第k点误差小于Tk，认为误差并非由噪声引起，仍使用传统SSDA算法。这种改进方法通过设置阈值进行预处理，以此提高SSDA的鲁棒性。

此外，尽管SSDA算法通过随机选取像素点减小了运算量，但由于阈值Tk选定后，仍需对误差ε进行累加直至超过Tk。为减少运算量，可利用序列代替原先的固定阈值，并采用隔点采样及粗匹配结合精确匹配等方法[12]降低运算量，进一步提高原算法的运算效率。

3 仿真测试与分析

实验选用的计算机配置为Intel Core(TM)2 Duo CPU E7300 2.66GHz，2.98GB内存，Windows XP系统，实验使用的编译工具为Matlab 7.0.1。选取三组图像，即标准Lena图像、指纹图像和遥感图像，进行试验仿真，以比较各算法的性能，即匹配准确度、匹配运算的实时性和鲁棒性。

观察匹配点的位置，对于Lena图像和指纹图像，若匹配误差在2个像素内，则视为匹配成功；对于遥感图像，若匹配误差在5个像素内，视为成功。记下匹配点位置，经过20次匹配计算平均成功率。至于匹配运算的实时性，主要指图像匹配耗时，在实验中也通过20次运算取平均值。关于鲁棒性的试验，是对原图像和模板图像都加上在Matlab参数中均值为0，方差分别取0.01，0.05和0.1的高斯噪声来进行匹配，如果此时匹配误差仍在3个像素内，则视为对上述噪声具有较好的鲁棒性。

标准Lena图像如图8所示，待搜索图像大小为256×256,目标图像大小为40×40。

图8 Lena图像

指纹图像如图9所示，待搜索图像大小为129×199,目标图像大小为25×25。

图9 指纹图像

遥感图像如图10所示，待搜索图像大小为1 000×1 000,目标图像大小为200×200。

图10 遥感图像

实验1 当图像中不存在噪声的情况下，对于三组图像，分别采用前述的三种算法进行匹配。考虑准确率，匹配所耗时间和匹配位置(代码初次运行结果的位置)三个方面。对于索引表算法，边界值选为20；对于SSDA算法，阈值选为40。实验所得数据对比结果如表1,表2和表3所示。

表1 针对无噪Lena图像的各算法性能比较

表2 针对无噪指纹图像的各算法性能比较

表3 针对无噪遥感图像的各算法性能比较

实验1的结果如图11所示。

图11 无噪声匹配结果

从实验1的图表中可以看出，当图像中不存在噪声时，针对Lena图像，指纹图像和遥感图像三组图像，文中的三种算法都具有较高的匹配精度。其中索引表算法耗时最短，其次为SSDA算法，相关性算法耗时最久。

实验2 给原图像分别加上方差为0.01，0.05和0.1的高斯噪声后，再用前述三种算法进行匹配。实验所得数据对比结果如表4至表12所示。

表4 针对含噪(σ2=0.01)Lena图像的各算法性能比较

表5 针对含噪(σ2=0.01)指纹图像的各算法性能比较

表6 针对含噪(σ2=0.01)遥感图像的各算法性能比较

表7 针对含噪(σ2=0.05)Lena图像的各算法性能比较

表8 针对含噪(σ2=0.05)指纹图像的各算法性能比较

表9 针对含噪(σ2=0.05)遥感图像的各算法性能比较

表10 针对含噪(σ2=0.1)Lena图像的各算法性能比较

表11 针对含噪(σ2=0.1)指纹图像的各算法性能比较

表12 针对含噪(σ2=0.1)遥感图像的各算法性能比较

实验2的具体结果如图12所示。

图12 含高斯噪声匹配结果

从实验2的图表中可以看出，当存在方差为0.01的高斯噪声时，对图像匹配精度几乎没有影响。当存在方差为0.05的高斯噪声时，基于索引表的算法和SSDA算法的匹配精度明显下降，而基于图像相关性的算法则具有良好的鲁棒性。当存在方差为0.1的高斯噪声时，基于索引表的算法和SSDA算法的匹配精度较差，而基于图像相关性的算法则仍然具有较高的匹配精度。另外，综合三组图像实验结果来看，噪声存在与否对于图像匹配的实时性影响不大。

4 结 语

基于索引表的算法具有良好的实时性，在较小的噪声环境下具有一定的鲁棒性。在加入噪声的情形下，将该算法的边界值适当放大，取到50，此时对于方差为0.1的高斯噪声仍具有较好的鲁棒性；然而当高斯噪声增至方差0.1以上后，鲁棒性则较差。若边界值选取过大，将增加匹配所耗时间，此时若在较强噪声影响下，匹配效果也不理想。为了提高该算法的匹配效果，应根据待匹配图像的特点选取合适的边界值。

基于图像相关性的算法具有十分良好的鲁棒性和精确性，在高斯噪声环境下仍然具有很高的匹配精度。但其缺点是实时性较差，对于较大的图像，例如遥感图像，匹配所耗时间太久。

SSDA具有较好的实时性和精度，在低噪声环境下也具有一定的鲁棒性。在不同场合要求下，对SSDA进行改进[13-14]。例如使用序列代替固定阈值[6]的自适应匹配算法等方法，提高了原算法的鲁棒性和计算效率，增大了算法的使用范围。

综上所述，在无噪声以及低噪声的环境下，可采用基于索引表的算法和SSDA算法，具有良好的实时性；在较强的噪声环境下，可采用基于图像相关性的算法，具有良好的鲁棒性。根据实际情况的要求来选用合适的算法，能够大大地提高图像匹配工作的效率，更好地发挥图像匹配在图像处理领域中的作用。在下一步的研究工作中，可以结合几种算法各自的优点，进一步对算法的性能进行改进，开发一种新的高性能快速鲁棒性算法，使其精度，速度和抗噪性等方面都能满足多数应用的要求。

[1] 李壮.异源图像匹配关键技术研究[D].长沙:国防科技大学,2011:1-135.

[2] 施陈博.快速图像配准和高精度立体匹配算法研究[D].北京:清华大学,2011:1-138.

[3] 刘兴淼,王仕成,赵静.基于图像多尺度熵的红外图像匹配跟踪算法[J].控制与决策,2011,26(5):768-772.

[4] Tombari F, Di Stefano L, Mattoccia S. A robust measure for visual correspondence[C]//Proceeding of 14th International Conference on Image Analysis and Processing. Italy Modena: ICIAP, 2007:376-381.

[5] Shin Bong Gun, Park So-Youn, Lee Ju Jang. Fast and Robust Template Matching Algorithm in Noisy Image[C]//International Conference on Control, Automation and Systems. Korea Seoul: ICCAS,2007:6-9.

[6] 刘晓光,陈曦,陈政伟,等.基于图像灰度的SSDA匹配算法[J].航空计算技术,2010,40(1):54-57.

[7] 王立新,刘彤宇,李阳.SSDA图像匹配算法的研究及实现[J].光电技术应用,2005,20(3):53-55.

[8] Crow F. Summed-area tables for texture mapping[J].Computer Graphics,1984,18(3):207-212.

[9] McDonnel M. Box-filtering techniques[J].Computer Graphics and Image Processing,1981,17(1):65-70.

[10] Rosenfeld A, Vanderburg G. Coarse-fine template matching[J]. IEEE Transactions on Systems, Man and Cybernetics,1977,7(2):104-107.

[11] Di Stefano L, Mattoccia S, Tombari F. Zncc-based template matching using bounded partial correlation[J]. Pattern Recognition Letters, 2005,26(14):2129-2134.

[12] 王刚.数字图像中模板抽取及匹配方法的研究与应用[D].济南:山东师范大学,2013:1-47.

[13] 吴培景,陈光梦.一种改进的SSDA图像匹配算法[J].计算机工程与应用,2005,41(33):76-78.

[14] Shao Xigao, Wu Kun, Duan Xiangbin. An Improved Algorithm for Gray Image Matching[J]. Journal of Information and Computational Science, 2013,10(7):1947-1957.

[责任编辑:王辉]

Comparison and research on three typical template matching algorithms

WU Chengmao, GUO Rui

(School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to reasonably select an appropriate algorithm for different conditions in particular problems such as image recognition, registration and mosaicking, three typical template matching algorithms, i.e. index table algorithm; an algorithm based on visual correspondence; and sequential similarity detection algorithm (SSDA), are explained in details in this paper. Differences analysis of matching performance of these algorithms is processed on their robustness, speed and precision. Experimental simulations data under different circumstances show that all three algorithms perform perfectly in precision, the index table algorithm and SSDA perform better in speed and the algorithm based on visual correspondence performs well on robustness in noise circumstance.

template matching, performance comparison, speed, robustness, precision

10.13682/j.issn.2095-6533.2014.03.004

2013-11-29

国家自然科学基金重点资助项目(90607008)；国家自然科学基金资助项目(61073106)；陕西省教育厅专项基金资助项目(2013JK1129)

吴成茂(1968-)，男，高级工程师，从事图像处理研究。E-mail:wuchengmao123@sohu.com郭锐(1988-)，男，硕士研究生，研究方向为图像信息处理。E-mail:304352014@qq.com

TP

A

2095-6533(2014)03-0015-07