面向边缘特征的实时模板匹配方法

王世勇 乾国康 李迪 张舞杰

（华南理工大学 机械与汽车工程学院，广东 广州 510640）

模板匹配作为机器视觉领域十分重要的研究内容之一，是目标识别、工件定位、对象跟踪等技术的重要环节［1］。其核心理念是利用模板图像像素信息或特征信息，在待处理图像中进行目标搜索，进而确定目标位姿。目前，模板匹配的实现主要有3种技术途径：基于灰度的模板匹配方法利用图像灰度信息进行匹配［2-3］，具有原理简单、容易实现的优势，但是其计算量大、抗干扰性差，使用局限性较大；基于特征的模板匹配方法利用特征点［4］、边缘［5-6］、结构［7］等作为匹配特征，相比于基于灰度的方法有较好的鲁棒性；随着机器学习技术的兴起，深度学习也被用于模板匹配［8-9］。基于深度学习的模板匹配方法能够自动学习图像特征，从而显著减少对图像处理专业知识的要求。但深度学习模型的训练需要大量的标注数据和基于经验的反复调试，因此要求大量的人工作业和人工智能专业知识。

因此，基于特征的模板匹配方法具有鲁棒性和效率两方面的综合优势，仍然是目前最常用的一类模板匹配方法。其中，基于边缘特征的模板匹配方法是其一个重要分支。在边缘特征配准鲁棒性方面，Hinterstoisser 等［10］提出一种结合边缘二维梯度信息与物体内部三维法线信息的特征描述方法，一定程度上增强了模板匹配的鲁棒性。Peng［11］在主导方向模板方法中引入颜色模板，并且采用逻辑回归方法优化匹配分数，增强了无纹理物体检测的鲁棒性。Wu 等［12］将关键边缘点和其邻域内边缘直方图信息相结合，形成更加复杂的描述子，能够在非线性强度变化和噪声情况下保持较高的匹配准确率。吴晓军等［13］利用亚像素边缘位置信息和梯度特征作为模板信息，能够以亚像素精度稳定地定位目标对象。Chan 等［14］提出一种面向边界的矩形描述子，利用物体大小的定向矩形实现具有最小离群值的最佳物体信息封装，能够保证在杂波、遮挡场景下的高检测率。这类方法的共性特点是提出了冗余的模板描述方法，以增加匹配时间为代价提升方法的鲁棒性，难以满足实时场景的模板匹配需求。

为了提升模板匹配效率，Le 等［15］提出了一种GPU 加速方法，利用GPU 高效的并行计算能力提升匹配速度。但是，这种方法需要GPU 硬件支持，有一定的局限性。Tsai等［16］根据边缘梯度方向进行高效的相似度查表计算，能够适当地提升匹配速度，但会造成大量的内存消耗，所以该方法也受限于计算机硬件的性能。王凯等［17］提出了边缘点稀疏、逐层重叠筛选的金字塔匹配策略，以提升匹配效率。利用平均采样稀疏虽然能够减少边缘点数量，但不会降低噪声边缘点的比率，所以削弱了方法的鲁棒性；逐层进行目标重叠筛选虽然能够小幅提升计算速度，但会排除掉部分正确位姿，影响匹配准确性。

综上所述，当前基于边缘特征的模板匹配方法在鲁棒性和实时性两方面难以达到平衡。针对该问题，本文提出一种改进的边缘特征模板匹配方法。首先，在模板创建阶段，提出一种新型边缘稀疏方法，获取最佳边缘点集，减少模板信息冗余；然后，在图像匹配阶段，结合金字塔搜索策略，提出顶层提前筛选方法，以剔除错误位姿、加快后续各层的搜索速度；最后，通过多种工况的对比实验和快速视觉点胶工艺检验所提模板匹配方法的性能。

1 系统框架

如图1所示，基于边缘特征的模板匹配方法包括图像模板创建和图像匹配两个阶段，各阶段又分别包括若干个步骤。

图1 整体技术框架Fig.1 Overall technical framework

（1）模板创建阶段：首先，对模板图像进行自适应下采样，生成图像金字塔；其次，对每层图像进行轮廓分割［18］并创建图像掩膜，结合最大类间方差法和Canny 算子对模板图像进行自适应边缘检测［19］，并且通过边缘稀疏方法筛选出最佳边缘点集；最后，根据最佳边缘点集中边缘点梯度向量生成图像模板信息。

（2）图像匹配阶段：首先，对实时图像进行与模板创建阶段同样的金字塔下采样；其次，在金字塔顶层进行粗搜索并利用顶层提前筛选方法获取潜在目标位姿，同时排除错误目标位姿；接着，从上到下对金字塔进行逐层搜索，以精度递增的方式，进一步排除错误目标位姿，找到满足阈值要求的潜在目标位姿；最后，在底层图像中，利用非极大抑制与曲面拟合得到亚像素级的目标位姿。

2 模板创建

图像模板是图像匹配的基准，在保证模板图像特征质量的前提下减少模板表达的信息量，有助于减小图像匹配的计算量，从而提升匹配速度。图像模板创建包括图像金字塔构建、最佳边缘点提取、模板信息生成等几个主要步骤。特别地，在图像金字塔构建方面，提出了自适应金字塔层数计算方法；在最佳边缘点提取方面，提出了稀疏可控的邻域融合方法；在模板信息生成方面，采用了更加稳健的描述子。这些创新能够有效减少图像模板的信息冗余，为实时模板匹配奠定基础。

2.1 自适应图像金字塔构建

图像金字塔是利用滤波器多次下采样形成的一系列分辨率逐步降低的图像集合。当前，高斯金字塔是最常用的图像金字塔，采用的滤波器是高斯滤波器。为了减少金字塔构建时间，本文采用2 × 2均值滤波器构建图像金字塔。这种方法虽然降低了图像分辨率，但不会显著影响图像质量。同时，根据模板图像大小、模板图像边缘情况，自适应地计算金字塔层数。

式中：m为根据图像大小初步确定的层数；W为模板图像宽度；H为模板图像高度；Round 函数为取整操作；m'为最终确定的金字塔层数；NEP，min为设定的边缘点数量阈值，NEP(j)为初步确定的第j（j=1，2，…，m）层金字塔图像边缘点数量，且令NEP(m+1)=NEP，min。由于每层边缘点数量随着层数的增加而单调减少，因此该方法最终将第m'层作为顶层，而排除掉其后边缘点过少的几层。

2.2 最佳边缘点提取

直接利用边缘检测结果构建图像模板会加大搜索过程的计算量，难以保证方法的实时性。针对这一问题，提出一种边缘稀疏方法。该方法能够保留模板边缘中稳定性较好的边缘点，即对旋转、尺度缩放、亮度变化能够保持较好不变性的边缘点。

首先，对所有边缘点进行置信评分计算：

式中，Ep为边缘点p的置信评分，U(p，R)为边缘点p的半径为R的邻域，Mp为边缘点p的梯度幅值，而Mi为p邻域内其他边缘点的梯度幅值：

式中，ti、ui分别为边缘点在x、y方向的梯度值。式（2）表明相对于邻域内其他点，点p的梯度幅值越大，其置信评分越高。这样，能够保证强边缘获得较高的置信评分。

其次，定义边缘点集EPall和最佳边缘点集EPbest。初始时，EPall包含所有边缘点，EPbest为空。

然后，根据置信评分对EPall中的边缘点进行排序，将置信评分最高的边缘点转移到EPbest中，并将其邻域中所有其他边缘点从EPall中删除。

接着，对EPall中剩余的边缘点重复进行上述的排序、转移和删除操作，直到EPall为空。这样，EPbest就汇集了所有最佳边缘点。

另外，为使最佳边缘点数量可调，为所提边缘稀疏方法定义一种稀疏因子γ：

利用边缘稀疏方法能够提取边缘中适量的关键点，组成最佳边缘点集，这些点分布在模板图像的重要边缘上。与边缘点集相比，最佳边缘点集在较少的边缘点数量情况下，仍然能够保留边缘轮廓结构信息。

2.3 模板信息的生成

模板信息通常是由模板图像全部边缘描述子构成［20］，本文以最佳边缘点梯度信息作为描述子构建模板信息。为了保证模板具有不变性，选择模板图像中心作为参考点，并以边缘点相对于参考点的位置偏移Li(xi，yi)和梯度向量Gi(Ti，Ui)作为描述子，如图2 所示。整合全部边缘描述子，形成模板信息：

图2 模板信息描述子示例Fig.2 Illustration of template information descriptors

式中，IMinfo 表示图像模板信息，n为最佳边缘点集中边缘点数量，(xi，yi，Ti，Ui)为最佳边缘点集中第i个边缘点对应的描述子，其中(xi，yi)为边缘点相对于参考点的位置偏移，而Ti、Ui为边缘点在x、y方向的归一化梯度值：

通常，归一化有利于提升模板的鲁棒性。

3 图像匹配

图像匹配是一个动态过程，需要交替地进行目标搜索和相似性度量，最终筛选出与模板图像相似的对象作为目标对象。对目标图像进行遍历搜索是一个直观但低效的过程。为了提升搜索效率，采用金字塔搜索策略，特别是在金字塔搜索的过程中提出一种顶层提前筛选方法，从而可以提前排除错误位姿，显著缩短搜索时间。在相似性度量方面，引入边缘梯度阈值限制，能够排除目标图像中不满足梯度幅值要求的边缘点，实现滤噪操作，提升鲁棒性。

3.1 相似性度量

相似性度量是模板匹配的重要技术之一，目标图像中某一局部区域和模板图像之间的相似性得分越高，表明该区域越可能包含目标对象［21］。在图像模板制作阶段，创建单一角度模板信息，以避免多角度模板信息的过大内存开销。相应地，在模板匹配阶段，为了保证模板旋转不变性和尺度不变性，需要对单一角度模板信息进行相似变换：

式中，θ为旋转角度，f为尺度因子，为相似变换后的描述子。

匹配过程中，在目标图像中的某个搜索位置P=(xp，yp)计算目标图像与模板图像的相似度：

式中：MP'为边缘点P'的梯度幅值；Mmin为梯度幅值阈值；P'(+xp，+yp)为目标图像中与模板图像第i个边缘点对应的点；VP'、WP'分别为P'处归一化梯度向量在x、y方向上的分量；si为目标图像与模板图像中单个对应点对的相似性得分。当目标图像中边缘点梯度幅值大于阈值Mmin时才计算点对的相似性得分，否则点对的相似性得分为0，这种阈值限制能够避免目标图像中噪声边缘点对相似度的干扰。

模板图像在目标图像某位置处的相似性得分S定义为所有点对相似性得分的算术平均值：

然而，对于部分遮挡的目标图像，遮挡区域出现的随机梯度会降低相似性得分。根据遮挡比例α（可由用户设定或由自适应方法确定），取k个相似性得分最高的边缘点对计算总体相似性得分：

综上，利用梯度阈值限制目标图像中梯度较小的噪声边缘，能够提升模板匹配稳定性。对于存在遮挡的匹配场景，在对所有描述子进行相似度计算后，根据遮挡比例和相似得分分布情况排除得分较低的区域，从而显著降低错误配准率。

3.2 金字塔搜索策略

图像金字塔搜索是一种由粗到精的搜索策略，即先在顶层低分辨率图像中进行遍历搜索，获取潜在目标平面位姿，然后逐层缩小搜索范围并增加搜索精度，从而能够在保证搜索精度的同时提升搜索效率［22］。在逐层搜索过程中，下层只需要对上层潜在平面目标位姿映射的邻域进行搜索，搜索区域由下式确定：

式中，（x，y，θ）为搜索区域，ηx、ηy、ηθ为上层潜在目标位姿，dEp表示扩展搜索范围，

式中，j为金字塔层数，取值范围通常为1 -7。这种加速搜索策略在越靠近顶层时搜索范围越大，越靠近底层时搜索范围越小，使得匹配方法不会过早陷入局部最优解。

顶层遍历搜索过程中需要设定尺度步长，通常尺度步长越小则搜索时间越长，合适的步长能够在避免目标遗漏的情况下保证最佳的搜索速度，因此尺度步长需要根据实际场景设定。

在进行图像金字塔搜索时，角度步长越小，角度分辨率就越高，但过小的角度步长会增加搜索时间，所以需要确定合适的角度步长。其中，最底层的角度步长a1为

式中，(xl，yl)为最佳边缘点集中距离参考点(xc，yc)最远的边缘点。随着金字塔层数的升高，图像分辨率逐渐降低，所以可以在上层搜索中采用较大的角度步长aj：

为了不丢失目标，随着金字塔层数的升高，需要放松对相似性得分的要求。如果底层相似性得分阈值为Smin1，那么各层相似性得分阈值Sminj为

金字塔底层搜索后只能得到像素级精度目标位姿，为了获取更高精度的目标位姿，可以将目标位置周围3 × 3 邻域进行曲面拟合［23］，并将拟合曲面的顶点作为最终亚像素精度目标位置。

3.3 金字塔顶层提前筛选

在对金字塔顶层图像进行遍历搜索后，可能得到多个潜在目标位姿，而通常只有一部分为正确的目标位姿。传统的金字塔搜索方法不对顶层潜在目标位姿进行筛选，而是将全部的潜在目标位姿作为后续搜索的对象，因此增加了无效搜索时间。为了尽早排除顶层搜索结果中的错误目标位姿，本文提出一种顶层提前筛选方法。

顶层遍历过程中，当所得位姿满足最小相似性得分Smin1时，计算其与其他潜在目标位姿的归一化曼哈顿距离D：

式中，(x1，y1，θ1)、(x2，y2，θ2)分别为待判定的目标位姿和合法的潜在目标位姿，ϕ为搜索角度范围。如果该位姿与其他合法位姿的曼哈顿距离均大于设定的阈值Dmin，则直接将该位姿认定为合法的潜在目标位姿；如果该位姿与部分合法位姿的曼哈顿距离小于设定的阈值Dmin，则重新评估这些位置相近的位姿，然后保留相似性得分最高的一个，同时排除这些邻近位姿中的其他位姿。

顶层提前筛选方法不仅考虑了潜在目标位姿的重叠率，还将角度差作为判断依据，能够在顶层中提前排除错误位姿，并且不会错误地排除位置接近、角度不接近的潜在目标位姿。图3展示了顶层提前筛选方法的实施效果。在顶层搜索过后得到5 个目标位姿，且各位姿的相似性得分均大于设定值。位姿A、B、C的位置、角度均接近，所以仅相似性得分最大的位姿B 得以保留。位姿D 和E 的相似性得分虽然小于位姿B，但是位姿D 与位姿B 角度偏差较大，而位姿E 与位姿B 距离较远，所以这两个位姿也得以保留。

图3 顶层提前筛选示例Fig.3 A top-level pre-screening example

所提算法搜索效率的提升主要体现在最佳边缘提取与顶层提前筛选两方面。为了进行时间复杂度分析，假设：①在最佳边缘提取过程中保留了β1(0 ＜β1＜1)倍的边缘点，在顶层提前筛选过程中保留了β2(0 ＜β2＜1)倍的潜在目标；②其他过程对时间复杂度的影响较小，在此不考虑其影响；③令传统方法在顶层遍历搜索时耗时Ttop，在其他层逐层精确搜索耗时Tother。

基于上述假设，传统的基于金字塔的模板匹配算法时间复杂度为Ttop+Tother，所提算法时间复杂度为β1Ttop+β1β2Tother，且有：

所以，所提算法的搜索速度比传统金字塔模板匹配方法快。

4 实验结果与分析

4.1 实验条件

为了验证所提模板匹配方法的鲁棒性与实时性，本文构建了5组工况不同的图像数据集：①数据集1 是一组在不同光照情况下拍摄的瓶盖图像，共有324张，分辨率为652 × 494；②数据集2是一组包含了不同位姿的半导体芯片图像，共720 张，分辨率为646 × 492；③数据集3是一组包含不同图标缺陷的瓶盖图像，共有324张，分辨率为1 280 ×1 024；④数据集4是一组数量和位置不同的气管接头图像，共有648张，分辨率为1 920 × 1 080；⑤数据集5 是一组存在不同程度遮挡的夹紧装置图像，共有720张，分辨率为1 280 × 1 024。

所有实验都是在同一台64 位Win10 系统的个人计算机上进行的，其CPU 为2.60 GHz 11th Gen Intel（R）Core（TM），并配有16 GB 内存；软件开发平台为Visual Studio 2019，所用编程语言为C++。

所提模板匹配方法参数设置为：边缘点数量阈值EPNmin为10，旋转角度θ范围为-180°～180°，角度步长由式（13）和（14）确定，尺度因子f为0.8～1.2，尺度步长为0.1，梯度阈值Mmin为20，底层相似性得分阈值Smin1为0.6，曼哈顿距离阈值Dmin为1。对于数据集5，遮挡比例α为0.5。

以平均匹配时间和准确率（正确识别的目标个数占目标总数的比例）作为评价指标，进行两部分实验：首先，通过实验分析本文提出的边缘稀疏方法与顶层提前筛选方法对方法鲁棒性和实时性的优化效果；其次，与RPVC［2］、LGSC［7］、NCC［3］、CCAS［11］4种模板匹配方法进行对比实验。

4.2 优化效果分析

本文提出的边缘稀疏方法能够获取最佳边缘点集，而最佳边缘点集的元素数量可由稀疏因子控制。不同稀疏因子下最佳边缘点集如图4所示，其中白色轮廓为图像边缘，红色点为最佳边缘点集的元素。可见，稀疏因子越大，最佳边缘点分布越稀疏。

图4 不同稀疏因子下的最佳边缘点集Fig.4 The best edge points under different sparse factors

为了验证边缘稀疏方法对匹配方法的优化效果，选取芯片图像（数据集2）作为测试对象，所用模板图像分辨率为255×132，测试结果如图5所示。结果表明，随着稀疏因子的增大，平均匹配时间缩短，匹配准确率也逐渐降低；但是平均匹配时间减少的幅度越来越小，而匹配准确率下降的幅度却越来越大。在实验条件下，稀疏因子γ=0.4时，平均匹配时间和准确率能够实现较好的平衡，即能够在较高的匹配准确率情况下大幅缩短匹配时间。本例中，匹配速度相比无边缘稀疏提升了70%，并且匹配准确率保持在98%以上。

图5 不同稀疏因子下的方法性能Fig.5 Algorithm performance under different sparse factors

为了测试顶层提前筛选方法对所提模板匹配方法的优化效果。稀疏因子γ=0.4的条件下，在5组数据集中进行有顶层提前筛选和无顶层提前筛选的性能对比，测试结果如图6所示。结果表明，与不进行顶层筛选相比，进行顶层筛选能够提升20%～45%的匹配速度，同时不会明显影响匹配准确率。

图6 有无顶层提前筛选的性能对比Fig.6 Comparison performance of algorithms with pre-screening and without pre-screening

由此可见，本文方法中提出的边缘稀疏方法与顶层提前筛选方法能够使得所提模板匹配方法在保证鲁棒性的同时提升搜索效率。

4.3 模板匹配效果对比

图7 展示了所提模板匹配方法在稀疏因子γ=0.4，且有顶层提前筛选情况下，在5 个数据集上的部分特征匹配结果。其中，每一行第1张图像为模板图像，其余图像为具有代表性的模板匹配结果。所提模板匹配方法在前4个数据集中均能实现97%以上的识别准确率，在第5个数据集中能实现90%以上的识别准确率。由于这5个数据集代表了5 种典型工况：光照变化、旋转变化、图像缺陷、多对象匹配、相互遮挡，所以测试结果表明所提模板匹配方法具有良好的鲁棒性，即在非均匀光照、遮挡、噪声等情况下，均能识别出正确的位姿。

图7 所提模板匹配方法在5种数据集中的部分匹配结果Fig.7 Matching examples of the proposed algorithm for five datasets

为了进一步地评估所提模板匹配方法的性能，在5个图像数据集上与RPVC、LGSC、NCC、CCAS 4种方法进行了对比实验。平均匹配时间和准确率情况分别如表1、表2 所示，其中最佳结果如粗体字所示。表1 结果表明，所提模板匹配方法在匹配速度方面具有显著的优势，不仅在全部数据集上匹配用时最短，而且在5 个数据集上的平均用时分别为RPVC、LGSC、NCC、CCAS的17.12%、0.47%、0.53%、23.27%。表2表明所提模板匹配方法在多个数据集（数据集1、数据集3、数据集4）上取得了最佳的匹配准确率。在数据集2 和数据集5 上，所提模板匹配方法的准确率也能达到最佳结果的98.06%（98.06/100.00）和98.10%（90.87/92.63）。因此，所提模板匹配方法能够有效平衡匹配速度和匹配准确率，具有优良的综合性能。

表1 5种数据集下5种方法的平均匹配时间Table 1 Average matching time of five algorithms for five datasets ms

表2 5种数据集下5种方法的准确率对比Table 2 Comparison of accuracy of five algorithms for five datasets%

5 应用实例

点胶是一种将流体涂覆、点滴到工件表面的生产工艺，能够起到粘贴、灌封、绝缘、固定、表面光滑等作用。将所提模板匹配方法应用到点胶机上，利用图像匹配代替模具进行工件定位，能够在工件随机分布的情况下进行快速点胶作业，实现了一种新型自由平面位姿快速视觉点胶工艺，如图8所示。

图8 点胶机实物图Fig.8 A glue dispenser

所用视觉点胶装置主要由三轴点胶机、工业相机、相机镜头、环形光源和工业PC 组成。其中，点胶机是一种三轴台式点胶机；工业相机型号为MV-SUA134GA-T，具有1 280 × 1 024 的分辨率；相机镜头型号为C-125-1620-5M；环形光源为KM-2RND704A90；工业PC 具有3.40 GHz Intel（R）Core（TM）i7-4770 的CPU、8 GB 内存和64 位Ubuntu18.04系统。

所提模板匹配方法在实时点胶作业过程中的部分典型工况下的工件定位效果如图9所示。在实时点胶场景中，所提模板匹配方法准确率可达98.10%（207/211），仅在工件缺陷过大的情况下会丢失目标，每个工件的平均匹配时间为20.59 ms，定位精度为0.02 mm，能够满足点胶行业实时稳定定位需求。

图9 所提模板匹配方法在点胶机中的实时定位效果Fig.9 Real-time positioning effect of the proposed template matching method with glue dispenser

6 结论

本文提出了一种面向边缘特征的改进模板匹配方法，以提升方法的实时性，并且保证鲁棒性。在图像模板创建方面，提出了一种边缘稀疏方法，该方法能够从边缘点中筛选出关键点，并且点数可控，从而在保留高质量的边缘信息的同时减少边缘点数量，能够显著降低模板匹配的计算开销。在图像匹配方面，为了进一步提升方法的速度，在金字塔搜索中提出了一种顶层提前筛选方法，采用归一化曼哈顿距离作为限制条件在顶层结果中提前排除错误的目标位姿。构建了5 种工况不同的数据集，对所提出方法进行了对比验证，并成功将所提模板匹配方法应用于自由平面位姿下的快速视觉点胶工艺中。实验结果表明，所提模板匹配方法在显著提升匹配速度的同时能够保证高的匹配准确率，并且能够有效克服光照、旋转、缺陷、多目标、遮挡等干扰因素，同时满足视觉场景中对图像匹配的鲁棒性和实时性要求。但是，所提模板匹配方法着重于解决刚性目标匹配问题，对于非刚性目标匹配，需要重点建立新型的相似性度量方法。