论文部分内容阅读
摘 要：图像处理发展迅速，许多智能算法涌现，其检测识别精度不断提高，但是这些算法的性能大量依赖样本的训练，在某些特定场合，如敌对目标的识别，样本稀缺，无法适用于智能算法。模板匹配算法发展最早，虽然对目标姿态、光照环境较为敏感，但需要样本少，其结果的可靠性是其他智能算法无法比拟的，在一些特定场合应用效果较好，本文主要介绍模板匹配算法的种类及发展。
把实时图像当作一个模板图像（Template image），在参考图像中设定一个和模板图像大小相同的窗口，滑动窗口，比较窗口中图像和模板图像的差别，差别最小处为最佳匹配点。
一、绝对平衡搜索（ABS）算法
ABS算法对参考图像进行绝对平衡搜索，搜索窗口扫过参考图像中的每一个像素点，将窗口图像和模板图像之间的像素点做比较，把它们之间的差别大小作为相关性衡量标准，差别最小的那个窗口的图像区域即为匹配区域，比较方法有以下几种：
其中为模板图像，扫描过程中的窗口图像，取MAD或者SSD最小处的，作模板图像在参考图像中的最佳匹配点。但是，这种方法在图像的灰度值发生线性变化时（灰度值加一个常数或者乘以一个常数），就失效了，两种误差都不能对匹配点做出正确衡量。这种方法只能用于模板图像严格地为参考图像的一部分的情况。
二、归一化互相关度量算法
构造归一化互相关函数（NCD）：
若将模板大小的区域作为向量描述，上述公式描述的为两个向量夹角的余弦值，夹角越小，说明参考图与实时图之间的方向越接近。最大时的为最佳匹配位置。这种方法实际上消除了一部分关照变换的影响（对比度不变性，每个灰度值都乘以一个常数因子），对于很小的旋转和缩放也有一定的容忍度。但对于图像亮度变化（灰度值加减一个常数）、较大的旋转和缩放就失效了，而且该方法计算量太大。
三、幅度排序相关算法
首先把模板图像中的像素点按照灰度值的大小进行排序;然后根据像素点个数进行二进制编码（个数为奇数时中间一个像素点不进行编码）;最后根据二进制位数形成阵列图。下面以大小的模板图为例进行说明：
首先，对图1（a）所示的模板图像进行幅度排序，结果见图1（b）中的第二列。
然后，对排序后的像素点进行二进制编码，如图1（b）第三列所示。
最后，对图1（b）所示的二进制序列，从高到低（1，2，3）分别抽取各个位上的数值。
量化后的模板图像阵列图和窗口图像的積相关函数为（二进制1代表正，0为负）：
这是第一步的粗匹配，上式可以简单的表示为像素点灰度值大的位置和小的位置相减，当为匹配点时，窗口图像也有相同的性质。设定一个阈值，当进行第一次粗匹配搜索时，记录所有的点为第一次检测点;在第一次检测点上，计算第二个阵列图与窗口图像的积相关函数值：
表示了更精细的相关值，同样设定一个阈值，记录所有的点为第二次检测点;依次类推，直到二进制序列的最后一位：
在阈值为时检测到的像素点即为匹配点，如果不唯一，则取最大的点为匹配点。上述中有，每一步的检测更加精细，检测点也更加稀少。
四、序列相似性检测算法
这种算法最大的特征点是能够较快的丢弃不匹配点，提高匹配速度，是一种快速的模板匹配算法。它来自于平均绝对误差（MAD），但并不计算所有的误差和，其基本原理如下：
a.定义SSDA计算时的绝对误差：
其中：分别为参考图像中的搜索窗口和模板图像的平均值。
b.设定阈值为Th;在搜索窗口中随机选取像素点，计算其绝对误差;不停的随机选取像素点并累加其绝对误差（可以提前生成伪随机序列以节省时间），当绝对误差和超过设定阈值Th后，停止选取，记录累计次数。
c.滑动图像窗口，比较所有的，最大处为匹配点。
如果绝对误差和在随机选取的次数较小时就超过了阈值，说明其和模板图像差别较大，不是匹配点;若果绝对误差和随着选取次数的增长而呈线性均匀增长，并增长缓慢（累计次数较大），说明其为匹配点或近似匹配点。由此可以看出，相比较MAD，SSDA在参考图像非匹配点上随机选取几个像素值计算后就很快跳过了，每个窗口处的计算次数要大大减少。
为了进一步提高速度，可以把匹配搜索分成两步来进行，第一步搜索窗口间隔个像素点进行一次序列相似性检测，找出匹配位置，而后在的区域内按照SSDA进行精确匹配，找出最佳匹配位置，的选取不能过大，否则容易跳过匹配位置;同时累计误差阈值采用自适应值，阈值随着累计次数的增长而增长，这样能更快的丢弃非匹配点（随机选取次数降低），进一步降低时间消耗。
以上为四种常见的模板匹配算法，分别从灰度值差值、向量角度、统计排序等来衡量实时图与模板图的相似性，模板匹配的发展更加能够适应环境的变化，例如光照、角度、缩放等变换，这些变化在实际应用中是不可避免的，因为图像中包含了大量的信息，其有效模式及有意义的像素排列组合是及其少数的，所以利用统计的方法进行匹配，在原理上可以避免由于光照、角度和尺度的变换。
把实时图像当作一个模板图像（Template image），在参考图像中设定一个和模板图像大小相同的窗口，滑动窗口，比较窗口中图像和模板图像的差别，差别最小处为最佳匹配点。
一、绝对平衡搜索（ABS）算法
ABS算法对参考图像进行绝对平衡搜索，搜索窗口扫过参考图像中的每一个像素点，将窗口图像和模板图像之间的像素点做比较，把它们之间的差别大小作为相关性衡量标准，差别最小的那个窗口的图像区域即为匹配区域，比较方法有以下几种：
其中为模板图像，扫描过程中的窗口图像，取MAD或者SSD最小处的，作模板图像在参考图像中的最佳匹配点。但是，这种方法在图像的灰度值发生线性变化时（灰度值加一个常数或者乘以一个常数），就失效了，两种误差都不能对匹配点做出正确衡量。这种方法只能用于模板图像严格地为参考图像的一部分的情况。
二、归一化互相关度量算法
构造归一化互相关函数（NCD）：
若将模板大小的区域作为向量描述，上述公式描述的为两个向量夹角的余弦值，夹角越小，说明参考图与实时图之间的方向越接近。最大时的为最佳匹配位置。这种方法实际上消除了一部分关照变换的影响（对比度不变性，每个灰度值都乘以一个常数因子），对于很小的旋转和缩放也有一定的容忍度。但对于图像亮度变化（灰度值加减一个常数）、较大的旋转和缩放就失效了，而且该方法计算量太大。
三、幅度排序相关算法
首先把模板图像中的像素点按照灰度值的大小进行排序;然后根据像素点个数进行二进制编码（个数为奇数时中间一个像素点不进行编码）;最后根据二进制位数形成阵列图。下面以大小的模板图为例进行说明：
首先，对图1（a）所示的模板图像进行幅度排序，结果见图1（b）中的第二列。
然后，对排序后的像素点进行二进制编码，如图1（b）第三列所示。
最后，对图1（b）所示的二进制序列，从高到低（1，2，3）分别抽取各个位上的数值。
量化后的模板图像阵列图和窗口图像的積相关函数为（二进制1代表正，0为负）：
这是第一步的粗匹配，上式可以简单的表示为像素点灰度值大的位置和小的位置相减，当为匹配点时，窗口图像也有相同的性质。设定一个阈值，当进行第一次粗匹配搜索时，记录所有的点为第一次检测点;在第一次检测点上，计算第二个阵列图与窗口图像的积相关函数值：
表示了更精细的相关值，同样设定一个阈值，记录所有的点为第二次检测点;依次类推，直到二进制序列的最后一位：
在阈值为时检测到的像素点即为匹配点，如果不唯一，则取最大的点为匹配点。上述中有，每一步的检测更加精细，检测点也更加稀少。
四、序列相似性检测算法
这种算法最大的特征点是能够较快的丢弃不匹配点，提高匹配速度，是一种快速的模板匹配算法。它来自于平均绝对误差（MAD），但并不计算所有的误差和，其基本原理如下：
a.定义SSDA计算时的绝对误差：
其中：分别为参考图像中的搜索窗口和模板图像的平均值。
b.设定阈值为Th;在搜索窗口中随机选取像素点，计算其绝对误差;不停的随机选取像素点并累加其绝对误差（可以提前生成伪随机序列以节省时间），当绝对误差和超过设定阈值Th后，停止选取，记录累计次数。
c.滑动图像窗口，比较所有的，最大处为匹配点。
如果绝对误差和在随机选取的次数较小时就超过了阈值，说明其和模板图像差别较大，不是匹配点;若果绝对误差和随着选取次数的增长而呈线性均匀增长，并增长缓慢（累计次数较大），说明其为匹配点或近似匹配点。由此可以看出，相比较MAD，SSDA在参考图像非匹配点上随机选取几个像素值计算后就很快跳过了，每个窗口处的计算次数要大大减少。
为了进一步提高速度，可以把匹配搜索分成两步来进行，第一步搜索窗口间隔个像素点进行一次序列相似性检测，找出匹配位置，而后在的区域内按照SSDA进行精确匹配，找出最佳匹配位置，的选取不能过大，否则容易跳过匹配位置;同时累计误差阈值采用自适应值，阈值随着累计次数的增长而增长，这样能更快的丢弃非匹配点（随机选取次数降低），进一步降低时间消耗。
以上为四种常见的模板匹配算法，分别从灰度值差值、向量角度、统计排序等来衡量实时图与模板图的相似性，模板匹配的发展更加能够适应环境的变化，例如光照、角度、缩放等变换，这些变化在实际应用中是不可避免的，因为图像中包含了大量的信息，其有效模式及有意义的像素排列组合是及其少数的，所以利用统计的方法进行匹配，在原理上可以避免由于光照、角度和尺度的变换。