中南大学

硕士学位论文

图像模板匹配快速算法研究

姓名：刘锦峰

申请学位级别：硕士

专业：计算机应用技术

指导教师：沙莎

20070501摘要

图像匹配问题是图像处理中的一个经典问题，在计算机视觉、模

式识别和医学图像处理等方面有着广泛的应用。

本文在研究现有的主要匹配算法基础上，从匹配相似性度量函数

和模板快速搜索方法两方面进行研究，以提高匹配速度和准确度。研

究主要工作包括：

１、在基于灰度的匹配算法研究中，首先对匹配相似性度量函数

ＮＣＣ进行改进，在差分求和方法的基础上提出差分有序数组方法，

然后，在深入研究图像灰度特征的基础上，提出多值模板方法，即用体现匹配对象主要特征的Ｋ个灰度值替代初始灰度模板的２５６值。最

后，将差分有序数组方法和多值模板方法相结合，通过对Ｋ值模板的

排序和差分，减少ＮＣＣ公式的运算量。同时，提出基于多值模板的

快速粗搜索方法，粗一精搜索相结合，使算法在保持准确度的前提下，

速度较经典匹配算法提高了两个数量级。

２、在基于特征的匹配算法研究中，为解决匹配对象存在一定角度旋转的情况，引入中心区域置信度加大思想。为解决抗任意角度旋

转的快速匹配问题，对已有的具有旋转不变性的基于圆投影匹配方法

进行改进，通过比较模板和子图去均告投影向量是否属于同一灰度级

进行粗匹配，选取若干个候准匹配点，然后在此基础上再进行精匹配。

３、归纳总结基于矩形窗口加权快速算法构造思想和编程技巧，

以进一步提高整个匹配系统的处理速度。

试验结果表明，改进后的匹配算法能很好地满足匹配实际应用中

的实时性问题，且能适应匹配对象受一定噪声点干扰、局部整体光照

变化以及复杂背景干扰等情况。

关键词图像匹配，快速算法，多值模板，差分数组ＡＢＳＴＲＡＣＴ

Ｉｍａｇｅｍａｔｃｈｉｎｇｉｓａｃｌａｓｓｉｃｐｒｏｂｌｅｍｉｎｉｍａｇｅｐｒｏｃｅｓｓｉｎｇ，ａｎｄｉｔｉｓ

ｅｘｔｅｎｓｉｖｅｌｙａｐｐｌｉｅｄｔｏｔｈｅｆｉｅｌｄｏｆｃｏｍｐｕｔｅｒｖｉｓｉｏｎ，ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ，ｍｅｄｉｃａｌｉｍａｇｅｐｒｏｃｅｓｓｉｎｇ，ｅｔｃ．Ｉｎｔｈｉｓｐａｐｅｒ＇ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｍａｔｃｈｉｎｇｓｐｅｅｄａｎｄｒｏｂｕｓｔｎｅｓｓ，ｗｅ

ｄｅｅｐｌｙｓｔｕｄｙｏｎｔｈｅｔｗｏａｓｐｅｃｔｓａｂｏｕｔｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｉｓ

ｍａｔｃｈｉｎｇｓｉｍｉｌａｒｉｔｙｆｕｎｃｔｉｏｎａｎｄｆａｓｔｔｅｍｐｌａｔｅｓｅａｒｃｈｉｎｇｓｔｒａｔｅｇｙ，ｂａｓｅｄ

ｏｎｔｈｅａｎａｌｙｓｉｓｏｆｒｅｌａｔｅｄｗｏｒｋｓ．Ｔｈｅｒｅｓｅａｒｃｈｉｎｃｌｕｄｅｓ：

１）Ｉｎｔｈｅｒｅｓｅａｒｃｈｏｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｉｍａｇｅｇｒａｙｖａｌｕｅ，

ｆｉｒｓｔｌｙ，ｗｅｍａｋｅａｌｌｉｍｐｒｏｖｅｍｅｎｔｏｎｆａｓｔｎｏｒｍａｌｉｚｅｄｃｏｒｒｅｌａｔｉｏｎ，ａｎｄ

ｐｒｏｐｏｓｅａｍｅｔｈｏｄｏｆｄｉｆｆｅｒｅｎｔｉａｌｏｒｄｉｎａｌａｒｒａｙｂａｓｅｄｏｎｄｉｆｆｅｒｅｎｔｉａｌａｎｄ

ｒｅｃｕｒｒｅｎｃｅｓｕｍｆｏｒｍｕｌａ．Ｓｅｃｏｎｄｌｙ，Ｋ－ｖａｌｕｅｔｅｍｐｌａｔｅｍｅｔｈｏｄｗｈｉｃｈ

ｒｅｆｌｅｃｔｓｔｈｅｍａｉｎｃｈａｒａｃｔｅｒｏｆｍａｔｃｈｉｎｇｏｂｊｅｃｔｉｎｓｔｅａｄｏｆｏｒｉｇｉｎａｌ２５６一ｖａｌｕｅｔｅｍｐｌａｔｅｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｎ，ｔｈｅｔｗｏｍｅｔｈｏｄｓｍｅｎｔｉｏｎｅｄａｂｏｖｅ

ａｒｅｃｏｍｂｉｎｅｄｗｉｍｔｏｒｅｄｕｃｅｔｈｅｃｏｍｐｕｔａｔｉｏｎｉｎｍａｔｃｈｉｎｇｐｒｏｃｅｓｓｉｎｇ．

Ｔｈｉｒｄｌｙ，ｆａｓｔｃｏａｒｓｅ—ｆｉｎｅｓｅａｒｃｈｉｎｇｍｅｔｈｏｄｂａｓｅｄｏｎｋ－ｖａｌｕｅｔｅｍｐｌａｔｅｉｓ

ａｄｏｐｔｅｄ，ａｎｄｔｈｅｃｏｓｔｔｉｍｅｉｓｉｍｐｒｏｖｅｄｔｗｏｏｒｄｅｒｓｏｆｍａｇｎｉｔｕｄｅｉｎ

ｃｏｎｔｒａｓｔｔｏｔｈｅｃｕｒｒｅｎｔｃｏｒｒｅｌａｔｉｏｎａｌｇｏｒｉｔｈｍｓ．２）Ｉｎｔｈｅｒｅｓｅａｒｃｈｏｎｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｉｍａｇｅｃｈａｒａｃｔｅｒ，

ａｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｆｏｒａｃｅｒｔａｉｎａｎｇｌｅｒｏｔａｔｉｏｎｉｎｖａｒｉａｎｔｉｓｓｔｕｄｉｅｄ，ｂａｓｅｄｏｎｉｎｔｅｒｅｓｔｉｎｇａｒｅａｗｅｉｇｈｔｉｎｇ．Ｍｅａｎｗｈｉｌｅ，ａｎｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ

ｆｏｒａｒｏｔａｔｉｏｎｉｎｖａｒｉａｎｔｔｅｍｐｌａｔｅｍａｔｃｈｉｎｇｍｅｔｈｏｄｂａｓｅｏｎｃｉｒｃｌｅ

ｐｒｏｊｅｃｔｉｏｎｉｓａｌｓｏｒｅｓｅａｒｃｈｅｄ．Ｂｙｆａｓｔｃｏａｒｓｅｍａｔｃｈｉｎｇｂａｓｅｄｏｎｍｅａｎ－ｒｅｓｉｄｕａｌｃｉｒｃｌｅｐｒｏｊｅｃｔｉｏｎ，ｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙｉｓｒｅｄｕｃｅｄａｎｄ

ａｃｃｕｒａｔｅｔｅｍｐｌａｔｅｍａｔｃｈｉｎｇｉｓｐｅｒｆｏｒｍｅｄｏｎｌｙｏｎｔｈｅｍａｔｃｈｉｎｇｃａｎｄｉｄａｔｅｓ．

３）Ａｄｅｓｉｇｎｉｄｅａｆｏｒｆａｓｔａｌｇｏｒｉｔｈｍｏｆｉｍａｇｅｒｅｃｔａｎｇｌｅｗｉｎｄｏｗ

ｗｅｉｇｈｉｎｇｐｒｏｃｅｓｓｉｎｇａｎｄｐｒｏｇｒａｍｍｉｎｇｓｋｉｌｌｉｓｃｏｎｃｌｕｄｅｄ，ｉｎｏｒｄｅｒｔｏｆｕｒｔｈｅｒｉｍｐｒｏｖｅｐｒｏｃｅｓｓｉｎｇｓｐｅｅｄｏｆｔｈｅｗｈｏｌｅｍａｔｃｈｉｎｇｓｙｓｔｅｍ．

Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｄｅｖｅｌｏｐｅｄａｌｇｏｒｉｔｈｍｉｓｒｏｂｕｓｔａｎｄｆａｓｔｕｎｄｅｒｔｈｅｃｏｎｄｉｔｉｏｎｏｆｕｎ—ｌｉｎｅａｒｃｈａｎｇｉｎｇｏｆｌｏｃａｌｌｉｇｈｔｉｎｇ，ｎｏｉｓｅ，

ＩＩｔａｒｇｅｔｍａｔｃｈｉｎｇｏｆｉｒｒｅｇｕｌａｒｓｈａｐｅａｎｄｅｖｅｎｍａｔｃｈｉｎｇｉｎｃｏｍｐｌｅｘ

ｂａｃｋｇｒｏｕｎｄａｎｄｒｏｔａｔｉｏｎｉｎｖａｒｉａｎｃｅ．

ＫＥＹＷＯＲＤＳｉｍａｇｅｍａｔｃｈｉｎｇ，ｆａｓｔａｌｇｏｒｉｔｈｍ，Ｋ—ｖａｌｕｅｔｅｍｐｌａｔｅ，

ｄｉｆｆｅｒｅｎｔｉａｌａｒｒａｙ

１１１原创性声明

本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得

的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不

包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单

位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均

已在论文中作了明确的说明。

作者签名：掣镪嗡日期：≥唧年ｒ月，阳

关于学位论文使用授权说明

本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学

位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内

容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省

有关部门规定送交学位论文。

作者躲斗叶导师始卫卜瞧呷ｆ＂ａ硕士学位论文第一章绪论

１．１课题研究背景及意义第一章绪论

图像匹配问题是计算机视觉、图像处理领域中的基本问题，有两种对应的问

题模型；一是两幅（或者多幅１来自不同传感器、不同视角或不同时间的图像需找

出对应关系，经过匹配步骤可得出两幅图像的差别所在，为下一步处理作基础；

二是根据已知的图像模式在另一幅图像中搜索类似模板的目标。图像匹配技术是

数字图像处理领域的一项重要研究，已在计算机视觉、虚拟现实场景、航空航天

遥感测量、医学影像分析、光学和雷达跟踪、景物制导等领域有着重要的应用价

值。

图像匹配的应用领域”ｌ概括起来主要有以下几个方面：

ｌ、计算机视觉和模式识秀ｊｔ２１。包括图像分割、物体识别、形状重建、运动

跟踪和特征识别。

２、医学图像分析１３’４Ｊ。包括医学成像信息诊断，生物医学信号处理等。

３、遥感信息处理１５】。包括特定目标的定位和识别等。

图像匹配方法［６１大致可分为三类：第一类是基于灰度的图像匹配算法；第二

类是基于特征的图像匹配算法；第三类是基于对图像理解和解释的匹配方法１７Ｊ。

基于对图像理解和解释的匹配方法是把计算机中的模型同外在世界中的物

体和现象建立起相对应的关系，这种方法涉及到计算机视觉、人工智能、模式识

别等许多领域，即可用知识和规则来描述匹配对象，利用知识和规则实质上是给

匹配对象赋予了一种解释。但是这种方法在实现时，为减少计算量而使结构与点

之间的关系描述常常是不完全的，并且它们缺乏一种有效地衡量点集之间是否相

同的手段，所以这种方法目前还没有取得突破性的进展。

基于灰度的图像匹配算法，这类方法直接利用图像的次度信息进行匹配，通

过象素对之间某种相似性度量【３ｌ（如最小均方差、归一化积相关、ＳＳＤＡ等）的全

局最优化实现匹配，不需进行图像分割和图像特征提取，因而可以避免由这些预

处理所造成的精度损失。这一类方法因其原理简单，并且数学统计模型以及收敛

速度、定位精度、误差估计等均已有很成熟的研究成果。这类匹配方法需要解决

的问题是：匹配速度比较慢，对灰度信息变化、光照变化、噪声非常敏感，没有

充分利用灰度统计特性，对每一点的灰度信息依赖较大，不适应于匹配对象存在

旋转和缩放情况下的匹配问题。

基于特征的图像匹配算法一般不直接依赖于象素值，通常需要经过较复杂的硕士学位论文第一章绪论

图像处理以提取特征，通常在图像和变换后的图像中提取对比例、缩放、旋转、

灰度变换具有不变性的特征【９一Ｏｌ。这种方法的优点在于：（１）充分利用了图像灰

度特性和相关特性，（２）有效地消除由于背景或光照引起的误匹配，（３）对图像的

各种非本质变化（如旋转、缩放和光照强度变化等）不敏感，对含有一定噪声和

轻微扭曲的图像都可以匹配。而该方法也存在一定缺点：算法非常复杂，一般涉及大量的几何与图像形态学计算，计算量大，计算时间较长而难以达到实时性要

求，且没有一般模型可遵循，需要针对不同应用场合选择各自合适的特征。

图像匹配过程【１９】主要考虑三个因素：匹配的数据类型、相似性度量函数和搜

索策略。这三个因素是决定匹配准确度、实时性和鲁棒性的重要因素，每一个因

素都值得深入研究。

匹配的数据类型。主要可分为两种：基于灰度匹配的数据类型和基于特征匹

配的数据类型。目前，基于灰度匹配的数据类型通常直接利用图像象素值，通常

需对图像作一些基本处理，如平滑滤波、边缘提取、归一化、二值化等。基于特

征匹配的数据类型主要是图像的一些特征，如图像的不变矩特征（重心、质心等），

投影特征，方向码，图像的边缘、轮廓和纹理等。

相似性度量函数用来计算决定图像是否被正确匹配上，通常，匹配算法的抗

干扰能力是由提取的匹配特征和相似性度量函数共同决定，一般的相似性度量必

须考虑归一化。

搜索策略同样也是匹配过程中的一个重要环节。由于很多匹配算法均伴随着

庞大的计算量，常规的线性顺序搜索方法实际上无法在实时应用上实现，因此，

有效的搜索策略成为一个不容忽视的问题。在小的搜索空间内线性顺序搜索即足

以满足要求，但是当搜索空间比较大时，搜索方法的好坏直接影响着匹配的速度．

对于图像匹配技术的分类和比较评判通常比较困难，因为每一个匹配技术通

常针对某一个具体的应用而设计的，而对于那些特定的应用问题来说，并没有哪

一个技术是必须和唯一的。

随着科学技术的发展，图像匹配技术在近代信息处理领域中的应用范围越来

越广泛，而图像数据量庞大这一显著特点，严重制约了图像匹配技术的实时应用。

图像匹配的准确性和实时性是现今在具体应用上存在的一对矛盾体，如何在保持

匹配准确性的同时，提高其匹配速度是现阶段急需解决的问题，也是目前对匹配

算法的研究重点。在序列目标图像分析、跟踪、识别，工业实时检测等实际应用

中，一般是上述模板匹配的第二种情况，即根据已知的图像模式在另一幅图像中

搜索类似模板的目标，不仅需考虑实际环境的光照变化，任何非规则的匹配对象

以及不受复杂背景的干扰，而且需尽可能提高匹配速度，满足实时性要求。