一种基于灰度的快速模板匹配方法

郑剑斌，郑力新,2，朱建清

（1.华侨大学工学院，泉州 362021；2.工业智能化技术与系统福建省高校工程研究中心，泉州 362021）

模板匹配;序贯相似性检测;图像金字塔;高斯滤波

0 引言

随着图像处理、模式识别和机器人产业的快速发展，机器视觉技术的应用越来越广泛。传统机器人一般采用“示教”或离线编程来控制机器人的运动，难以适应目前工业生产中的实时性要求与复杂的工作环境。结合视觉技术，使机器人具有更高的智能化程度和更好的环境适应性。

对于大多数二维平面机器人视觉应用，工件需要通过可视化模块进行识别和定位。在图像中定位一个已知目标的最直接的方法是在像素级搜索需要识别控制的目标[1]。二维平面应用中模板匹配是一种计算量较小的有效目标识别算法。模板匹配的思想是比较已知模板和原始图像中相同大小的区域之间的灰度值等信息[2]。将匹配对象称为模板，并将其与搜索图像进行比较，以在未知图像中找到模板的位置，这个过程是图像匹配。模板匹配算法涉及两个关键方面：相似性度量和搜索策略[3]。这两个方面都决定了目标识别的计算匹配时间[4-5]。模板匹配是目标识别、医学成像、工业自动检测、特征跟踪和数字摄影测量等方面最重要的课题之一[6-7]。

经典的模板匹配方法具有机理简单，检测准确率高的特点，被用作一般模型评估和误差估计。传统的像素灰度匹配算法SAD和SSD[8]，时间复杂度较高，光照条件变化影响算法稳定性。归一互相关系数算法[9]通过计算标准差解决了光照变化使得图像中灰度值不相等问题。去均值归一化算法则通过增加算法的计算量[10]，通过计算可能匹配位置的图像与模板之间的均值，得到零均值图像，使得算法具有抗亮度干扰能力，提高了模板匹配的精度。传统的匹配方法影响速度的主要因素是搜索计算和匹配的操作，适当减小位置和相似度计算精度可显著提高模板匹配的速度。这正成为这个领域的一个研究热点。

针对上述问题，本文首先对图像进行处理，提取对象的特征图像，减少匹配干扰。为使待匹配点快速被检测，结合序贯相似性检测算法，通过图像金字塔搜索策略减少待匹配图像与模板上的匹配点来加快匹配速度。通过建立多角度模板来解决匹配中角度偏差较大不匹配或者匹配概率低的问题。

1 序贯相似性检测算法

设参考模板T，其大小为Mt×Nt，搜索图像S，其大小为Ms×Ns，且Mt≤Ms，Nt≤Ns，搜索图像中以(u,v)为左上角坐标，大小Mt×Nt的子图像块为Su,v。序贯相似性检测算法（SSDA）[11][12]则通过定义以累计差值，来停止某一点的匹配计算，进而切换至下一点位置上计算，通过这样的方式可加快匹配的速度。

序贯相似检测算法与传统模板匹配一样，需要度量(Ms-Mt+1)∙(Ns-Nt+1)个像素点，但与其他传统算法不一样的是SSDA通过计算子图像Su,v与模板T对应像素的累计差值，且两者对应像素点对以随机的次序 (mr1,nr2)(r1=1,2,…,Mt;r2=1,2,…,Nt)做比较，加快了累计差值的增加。序贯相似检测算法的非归一化与归一化的匹配差值定义如下：

非归一化：

归一化：

式中：

通过比较e(u,v,mr1,nr2)与一个预定义的固定阈值W或者单调递增的阈值序列W(k)，在子图像的累计差值e(u,v,mr1,nr2)等于或者大于W或W(k)时，结束此次度量计算，记下相应的k值，进行下一个待匹配点子图像差值的计算；当然，如果累计差值e(u,v,mr1,nr2)小于阈值W或W(k)，则继续计算该子图像在(u,v)处的下一个随机点的累计差值，直到e(u,v,mr1,nr2)大于W或W(k)，记下相应的k值。整个度量计算是对不同的待匹配点进行上述计算，最后取最大k值对应的待匹配点位置即为相似点。计算过程中，子图像需要越多的对应点差值才能累加达到W或W(k)的值，则子图像就越趋近于匹配对象。SSDA通过选取合适的阈值，使得误差累计较快的子图像所需测试的像素点远小于模板大小Mt×Nt。所以SSDA匹配速度比传统相关法提高了一个数量级。

2 图像金字塔分层搜索策略

2.1 图像金字塔原理

从相似度量计算的过程中，可知函数的计算复杂度为O(whn)，w和h是图像的宽和高,n是模板中点的数量。虽然在序贯相似性检测的相关性函数中改变了停止标准，算法的处理速度提升了一定常数比例，但不能降低算法的计算复杂度。因此，需要一种快速的搜索策略，通过减少需要检测的位姿数量以及模板中点的数量，来提高算法的速度，满足系统的实时性。一般情况下，图像多次缩小2倍至一个倍数与直接将图像缩小至这一倍数的效果更好。如图1所示，将图像多次缩小2倍，按照分辨率从大到小分层堆放，图像形如金字塔状，所以将这样的数据结构称为图像金字塔[13-16]。

图1 图像金字塔

图像金字塔思想是先在最上层低分辨率的图像中，利用相关测度算法进行初步搜索匹配，将得到的度量计算的结果回溯到分辨率比其高的下一层图像中，在下一层中选取匹配结果得到的相似点的一个邻域，这层中则在该邻域中进行搜索，以此一层层回溯，最后则可以得到最高分辨率图像中的一个小范围邻域，再进行相似度量函数的精确匹配。

构建金字塔的速度是非常重要的，通常为了不考虑频率响应问题，采用2×2的均值滤波器来平滑图像。为了避免图像压缩后的折叠失真，在采样前可对图像进行低通滤波来去除高于采样频率的空间频率。所以在构建图像金字塔的过程中本文使用高斯函数滤波器来实现平滑[17]。

2.2 分层搜索策略

图像金字塔算法首先要对被搜索图像和模板图像进行采样，根据搜索对象的大小以及分层后最上层图像的可辨识度，确定搜索过程中需要划分的金字塔层数。如图2所示为图像金字塔分层策略。

实验中为了避免分层使得图像产生锯齿以及保证整个匹配的稳定性，采用的分层策略是将金字塔低一层的图像中某个邻域块中的像素取平均值，或者是用给定的函数模板进行加权拟合，得到的像素值作为上一层金字塔图像的像素点。

图2 金字塔分层策略

图像分层后，则进行由粗到精的匹配[18-20]。在得到了一个k层的金字塔图像后，在Sk和Tk中通过遍历的方式，使用预定的序贯相似性度量检测算法计算各层中点的累计差值，并设定好阈值来确定一系列的回溯点(xk,yk)，回溯到搜索图像Sk-1和模板图像Tk-1中的邻域δ(xk,yk)，在得到的邻域中，再进行相似度检测，重新得到一定数量的相似点邻域(xk-1,yk-1)，直到计算至出金字塔最低层，分辨率最高图像中的最佳匹配点。由于目标物体通过分层变换后，在高层金字塔的图像中灰度值的变化细节不那么明显。为了保证所有可能的匹配位置，保证匹配的准确性，在图像金字塔中层数越高，应该使用越宽松的阈值进行序贯相似性度量检测。

3 旋转处理

传统的灰度模板匹配相似度度量的方法中，待匹配图像与模板之间只允许小角度的旋转，即限定了模板与待匹配图像的方向。这使得传统的模板匹配方法不能匹配对象或者匹配概率低，不适用于待匹配图像与模板之间具有较大角度偏差的情况。

实验中选取待匹配图像中一区域，对该区域图像进行角度旋转，取一定角度偏差的图像进行创建模板，得到多角度的模板，如图3所示。

图3 多角度模板图像

4 实验验证

4.1 图像处理

实验中，首先是对待匹配图像进行数字图像处理，如图4为图像处理前后的待匹配图像。

4.2 创建模板

图4 待匹配图像预处理

实验中，首先在获取的待匹配原图像（图4（a））中选取模板区域来创建模板，记录模板的中心坐标位置和模板旋转的角度信息，如图5所示。

图5 创建模板图像

在选取的模板图像基础上，对其进行旋转处理得到不同角度的模板图像，在0～360°之间，实验中每2.6°创建一个模板。

4.3 模板匹配

利用创建好的模板，结合图像金字塔分层搜索策略，根据相似度测量方法对图像预处理后的图像进行匹配计算。对匹配的感兴趣区域记录其中心位置坐标信息以及当前匹配区域相对于上一匹配区域的旋转角度。每一个匹配区域匹配结果如图6所示。最终模板匹配完成后的图像如图7所示。在整个匹配的过程中，执行不到0.2s，满足系统实时性的要求。

图6 模板匹配过程

4.4 坐标转换

在模板图像中通过鼠标示教出一些位置坐标，如图8所示。

图7 模板匹配结果

图8 示教位置

表2 各匹配图像位置的图像坐标

获取并记录模板中位置的图像坐标系下位置信息，如表1所示。

表1 模板示教位置图像坐标

通过模板匹配获取的各器件图像的中心坐标和旋转角度，可计算出各个器件中示教位置在图像坐标系下的位置信息，其中匹配器件1为模板图像，匹配器件2与3分别图7中另外两个匹配器件图像。实验中计算的各器件的位置信息如表2所示。

5 结语

本文利用序贯相似性检测算法作为匹配的相似性测度，结合图像金字塔分层搜索策略，大大提高了模板匹配速度，且通过建立多角度模板来解决基于灰度模板匹配对角度偏差较大图像不匹配或匹配概率低的问题。实验中整个匹配计算过程在0.2s内完成，满足工业应用中实时性的要求，利用匹配得到的中心坐标与角度信息，计算了图像各区域匹配后相关坐标、角度信息，验证了匹配精确度，证明了方法的可行性。