金字塔模板匹配算法融合NMSFast以及优化研究

Integration of Pyramid Template Matching Algorithm with NMSFast and Optimization Techniques

摘要: 图像模板匹配是计算机视觉领域的一项重要任务，它在许多应用中都有广泛的应用。然而，传统的模板匹配算法在大规模图像和复杂场景下存在计算量大、效率低的问题。为了解决这些问题，本文提出融合快速非最大抑制(NMSFast)的金字塔模板匹配算法，提高准确度，并通过特征提取、查表优化、OpenMP并行、量化等技术对其优化，从而提高效率。基于Sobel获取图像的梯度信息，并结合阈值和强度条件来筛选候选特征点以达到特征提取。通过查表创建模板特征和对应搜索图像特征之间的关联关系和缩放因子和旋转角度对应的变换矩阵的索引表。将特征数据进行量化，其转换为更简单的浮点数，对角度图像进行8方向量化，结合阈值过滤无效角度值。以上优化能够减少计算量和存储空间的消耗。OpenMP并行技术对金字塔进行并行分层搜索，将单线程变成多线程，可以提高算法的运行速度。实验结果表明，所提出的金字塔模板匹配算法融合NMSFast算法在大规模图像匹配任务中，运算时间提高51%，精度提高1.7%。

Abstract: Template matching in image processing is an important task in the field of computer vision and has wide applications in various domains. However, traditional template matching algorithms suffer from high computational complexity and low efficiency, especially when dealing with large-scale images and complex scenes. To address these issues, this paper proposes a pyramid template matching algorithm that integrates the NMSFast (Non-Maximum Suppression Fast) al-gorithm for improved accuracy. Several optimization techniques, including feature extraction, table lookup optimization, OpenMP parallel programming, and quantization, are employed to enhance the efficiency of the algorithm. The proposed algorithm utilizes the Sobel operator to extract gradient information from images and applies thresholding and intensity conditions to filter candidate feature points during feature extraction. Table lookup is used to establish the correspondence between template features and the corresponding features in the search image, along with indexing tables for scaling factors and rotation angles. Feature data are quantized to simplify representation, converting them into floating-point numbers. The angle image is quantized into 8 directions, and invalid angle values are filtered out using thresholding. These optimizations significantly reduce computational complexity and storage requirements. The OpenMP parallel programming technique is employed to perform parallel hierarchical searches on the pyramid, transforming the algorithm from single-threaded to multi-threaded, thereby improving its runtime performance. Experimental results demonstrate that the proposed pyramid template matching algorithm integrated with NMSFast achieves a 51% reduction in computation time and a 1.7% improvement in accuracy for large-scale image matching tasks.

1. 引言

图像模板匹配是计算机视觉中的一项基础任务，它在目标检测 [1] 、图像识别 [2] 、人脸识别 [3] 等领域具有重要的应用。传统的模板匹配算法通常采用滑动窗口的方式在搜索图像上进行匹配，然后通过比对相似度来判断是否存在匹配 [4] 。然而，随着图像数据的增加和场景的复杂化，传统算法在效率和准确性上面临一定的挑战。因此，对模板匹配算法进行优化和改进是很有必要的。

由于模板匹配是一个大量搜索过程，针对图像的搜索遍历极为耗时 [5] ，针对该问题，汪睿等提出利用形态学骨架提取与像素滑动检索方法确定器械的数量与位置，并将数量与位置作为先验信息预先建立待测物搜索框，再结合模板匹配方法对器械进行分类。朱鸣镝 [6] 等为了提升匹配速度和精度，该算法通过提供特征点的坐标，可以计算出每个特征点的得分值，并将其用于从输入图像中提取模板。基于输入图像和另一幅图像之间的模板匹配，使用暴力匹配算法在模板和匹配区域之间进行特征点匹配。张琬迎 [7] 等为解决非定义手势在手势识别过程中的干扰问题，提出一种改进的手势识别算法，在使用模板匹配的手势识别算法基础上，引入相似度判断对干扰手势进行筛选，以增强手势识别的抗干扰性。以上文献均是通过对算法采取复杂的前处理以精简后续模板匹配过程。

图像金字塔针对模板匹配过程中横向的大范围搜索转化为纵向多尺度空间中的局部搜索，是目前模板匹配中的主要应用方法之一，Khuram Nawaz Khayam [8] 等通过引入基于局部四模式和空间金字塔匹配的人脸识别模型去解决人脸识别中失调，光照变化，姿态变化，遮挡，表情等问题。逯睿琦 [9] 等在多尺度–显著性特征并行提取算法中，利用空间金字塔模型增强模板匹配方法对于物体不同尺度下的特征提取，有效地提高了匹配精度及效率。刘元琳 [10] 等在灰度模板匹配的经典算法中，采用基于金字塔渐进分辨率匹配算法来提高目标检测跟踪的实时性和精确性。综上所述，在模板匹配中采用金字塔算法可有效提升匹配效率，但上述文献对金字塔搜索之后的结果缺乏筛选，对搜索的量缺乏限制，在匹配的速度和效率方面有很大的提升，针对目前金字塔模板匹配算法存在的不足，提出融合NMSFast减少冗余的匹配结果，降低干扰，保留相似度最高的结果，达到精准度的提高。

结合查表、量化技术降低搜索复杂度，减少无效搜索量，降低搜索复杂度，模板匹配过程为单一线程工作，耗时严重，为此加入OpenMP并行算法、将单线程匹配过程转化为多线程并行匹配 [11] ，进一步提高算法搜索效率。

2. 算法原理

2.1. 传统金字塔模板匹配算法

金字塔模板匹配算法是一种基于多尺度的模板匹配方法，是一种经典的图像匹配算法，它可以在不同尺度下对图像进行匹配，该算法通过构建图像金字塔和逐层匹配的方式来实现。如图1所示，首先构建模板金字塔和图像金字塔，也就是将输入图像按照不同的尺度进行降采样，形成一系列尺度不同的图像，再将模板图像按照与金字塔相同的尺度进行缩放，以便与金字塔中的图像进行匹配。最后从金字塔的顶层开始，逐层对金字塔图像和模板进行匹配。在底层进行重叠筛选。

Figure 1. Traditional pyramid template matching process flowchart

图1. 传统金字塔模板匹配流程图

2.2. NMSFast算法

传统的非最大抑制算法在大规模数据集下存在计算量大、效率低的问题。为了提高算法的速度和效率，本文引入了NMSFast算法进行优化。NMSFast是一种在目标检测和特征匹配中常用的技术，用于抑制冗余的匹配结果。它基于非极大值抑制的思想，在一组候选匹配结果中选择最具代表性的匹配结果，同时剔除与其相似度较高且重叠较大的其他匹配结果 [12] 。

在本次实验中，我将NMSFast封装成模板，以便与后续的调用，减少代码重复率，首先对每个类别的前n个得分检测器计算一个 $c\times n\times n$ 的IoU矩阵X，并对每个类别的框进行降序排列；

其次，通过检查是否有任何得分较高的检测与其IoU大于某个阈值t，从而找到要删除的检测框，因此我将通过矩阵X的下三角和对角设置为0而实现。

$X_{kij}=0\forall k,j,i\ge j$ , (2-1)

在上述三角函数实现后，保留列方向的最大值，来计算每个检测器的最大IoU矩阵K。

$K_{kj}=\underset{i}{\max }\left(X_{kij}\right)\forall k,j$ , (2-2)

最后利用阈值 $t\left(K<t\right)$ 来处理矩阵，对每个检测器保留最优。

在金字塔模板匹配算法中，首先构建图像金字塔，将输入图像按照不同的尺度进行缩放，得到一系列金字塔图像。然后，在每个金字塔层级上进行模板匹配，将模板与金字塔图像进行匹配计算，得到一组匹配结果。在融合NMSFast技术时，对于每个金字塔层级的匹配结果，先进行非最大抑制的处理。具体步骤包括：1) 对于每个匹配结果，计算其与其他匹配结果的相似度或重叠度。2) 根据设定的阈值，筛选出与当前匹配结果相似度较低或重叠度较小的其他匹配结果。3) 保留相似度最高或重叠度最小的匹配结果作为代表性结果，剔除其他匹配结果。

通过应用NMSFast技术，可以减少冗余的匹配结果，并保留最具代表性的匹配结果，从而提高算法的准确性和效率。

3. 优化过程

3.1. 特征提取和存储

基于图像的梯度信息，通过计算梯度方向和幅值，并结合阈值和强度条件来筛选候选特征点 [13] ，根据输入的角度图像(angle)、量化角度图像(quantized_angle)和梯度幅值图像(mag)，生成本地角度图像(local_angle)。本地角度图像将原始角度图像的方向信息进行量化，将角度划分为四个主要方向(0度、45度、90度、135度)。遍历梯度幅值图像的像素，并根据本地角度图像的值，判断当前像素是否为候选特征点。候选特征点的选择条件包括：当前梯度幅值大于其相邻像素的幅值，并且大于预设的强度阈值。在满足条件的情况下，将候选特征点的位置、得分和量化角度值保存到候选列表中。根据指定的特征点数量(num_features)，从候选列表中选择一组离散的特征点作为最终的特征模板。选择的过程通过对候选列表进行排序，并按照一定的间隔距离选择特征点，以保证特征点的分布离散均匀。最后，根据选择的特征点构建特征模板(Template)，包括模板的形状信息、金字塔级别和特征点信息。如果成功选择了特征点，则模板被标记为有效(is_valid = 1)，否则标记为无效(is_valid = 0)，实现了一种基于梯度信息的特征提取算法，用于从图像中提取具有一定分布和强度条件的特征点，进而构建特征模板。具体的特征选择策略可以根据需求进行调整和扩展。

3.2. 查表优化技术

查表是一种常用的优化技术，可用于加速图像金字塔模板匹配算法。它能通过预先计算和存储查找表，以避免重复计算和减少运算量 [14] 。

在金字塔模板匹配算法，创建一个索引表来存储每个金字塔级别上的模板特征和对应搜索图像特征之间的关联关系。这个索引表可以加速匹配过程中的金字塔层级间的匹配操作，从而避免重复计算和搜索。在模板需要进行缩放和旋转变换，预先计算并存储一些常见的缩放因子和旋转角度对应的变换矩阵。这样，可以通过查表获取所需的变换参数，而不需要实时计算变换矩阵或重新采样图像。

在最后金字塔底层重叠筛选过程，采取阈值功能，预先计算并存储不同阈值下的判定结果。通过查表，可以快速获取给定阈值下的匹配结果，而不需要再次进行判断或计算。

通过使用查表优化技术，可以大大减少重复计算和提高算法的执行效率。然而，建立和更新查表需要一定的计算和存储成本，并且需要根据具体应用场景和算法要求进行合理的设计和管理，如图2所示，索引表的建立。

Figure 2. Feature index table

图2. 特征索引表

3.3. 量化优化技术

量化是图像金字塔模板匹配算法中的一种优化技术，可以帮助提高匹配过程的效率和减少存储空间的占用。通过Sobel滤波器计算图像的边缘梯度，然后计算边缘角度和边缘幅值。最后，根据指定的量化方式将角度进行量化，得到量化后的角度图像。

在特征提取阶段，将特征数据进行量化，将其转换为更简单和紧凑的表示形式。使用较低的位深度表示特征向量中的浮点数，从而减少内存占用和计算复杂度 [15] 。

$Q\left(r\right)=Int\left(r/S\right)-Z$ , (3-1)

Q是量化算子，r是输入实值，Z是整数零点，S是实值缩放因子,总的来说就将实数值转换为浮点值，并将其映射到较低的精度范围。

对于角度信息，将其量化为离散的角度值，对角度图像进行8方向量化，通过计算每个像素周围的角度值的直方图，选取出现次数最多的角度作为该像素的量化后的角度值。仅当周围像素中出现次数最多的角度值的次数超过预设阈值时，才接受该量化结果。否则，将该像素的角度值标记为无效。从而降低存储和计算成本 [16] 。

$Q=\frac{R}{S}+Z$ , (3-2)

$S=\frac{R_{\max }-R_{\min }}{Q_{\max }-Q_{\min }}$ , (3-3)

$Z=Q_{\max }-\frac{R_{\max }}{S}$ , (3-4)

R：真实浮点值；Q：量化后的定点值；Z：表示0浮点值对应的量化定点值；S：定点量化后可表示最小刻度。

对于模板和搜索图像的强度信息，进行适当的量化处理。将像素强度值离散化为几个固定的级别，以减少存储空间和计算复杂度，由于采取的与角度量化同样的方法，再次不做过多陈述。

在匹配过程中，使用预先计算的量化索引表来加速匹配的计算。这些索引表可以包含模板和搜索图像的量化特征表示和相关信息，以避免重复计算和减少存储开销。使用位运算来进行特征的比较和匹配操作，以提高计算效率和减少内存访问次数 [17] 。使用位掩码和位逻辑运算来快速计算特征的相似度或匹配度。

总的来说，量化对图像金字塔模板匹配算法的优化可以减少存储开销、加快计算速度，并且在一定程度上保持匹配的准确性。但需要权衡量化的精度和性能之间的平衡，并根据具体应用场景进行调整和优化。

3.4. OMP并行优化技术

OpenMP并行编程应用于图像金字塔模板匹配算法中，以提高匹配过程的效率，通过使用OpenMP的并行循环指令#pragma omp parallel for，将对多个模板的特征提取、匹配和非最大抑制进行并行化处理。这样可以同时利用多个处理器核心来加速计算，提高匹配的速度 [18] 。在并行化循环时，对共享数据的访问和同步。使用OpenMP的数据共享指令#pragma omp shared来声明共享各层数据以及查找表，以确保多个线程之间正确地访问共享数据。同时，使用OpenMP的同步指令如#pragma omp barrier和#pragma omp critical来实现图像分层搜索同步操作，保证数据一致性和正确性。在图像金字塔模板匹配算法，金字塔的层级和尺度都会影响匹配的粒度 [19] 。可以根据实际情况和硬件资源，在并行化时调整金字塔的层级和尺度，以实现更好的负载平衡和并行效率，在此次实验中，硬件资源充足，顾未采取此方法。总的来说，OpenMP并行编程有效地提高图像金字塔模板匹配算法的计算速度，充分利用多核处理器的并行能力。但在使用OpenMP并行化时，需要注意数据共享、同步和负载平衡等问题，以确保正确性和性能的提升。

在后续处理中，还可以使用OpenMP的任务指令#pragma omp task来将一些耗时较大的子任务交给不同的线程执行，以实现负载均衡。由于本次的实验为出现线程之间的工作量未超出硬件资源，顾未采用此方法。

4. 实验结果分析

所有实验均opencv4.00的开源库，visual studio2017编译器，均采用C++语言程序编写，对模板图像进行多角度旋转后进行特征提取，旋转角度范围为0˚~360˚，旋转角度步长为1˚，缩放范围为0.9~1.1，缩放步长为0.1模板个数为((360 − 0)/1)*((1.1 − 0.9)/0.1) = 360*20 = 7200个模板，即模板存储这7200个模板特征。将相似度阈值和金字塔层数分别定为0.5和7层，为确保算法的容忍度，将选取遮挡、残缺和旋转的图像，结果括号中第一个数字表示旋转角度，第二个数字表示缩放大小，最终目标对象被准确标注于图3中，实验计算机配置为Intel(R) Core(TM) i5-3470 CPU。

Figure 3. Target matching results

图3. 目标匹配结果

4.1. 融合NMSFast结果分析

如表1所示，分别选定传统的图像金字塔模板匹配算法和融合NMSFast的图像金字塔模板匹配算法，对比算法改进后的运行时间及各目标匹配得分可知，算法节约时间是0.0580秒左右，而相对于准确度，对残缺和遮挡的图像则提升较为明显，则对旋转的图像无变化，因此融合NMSFast之后的图像金字塔模板匹配算法无论是在速度还是准确度上都有很大的提升。

Table 1. Performance of the integrated NMSFast algorithm

表1. 融合NMSFast算法性能

4.2. 查表、量化优化结果分析

如表2所示，将对融合NMSFast的图像金字塔模板匹配算法和通过对融合NMSFast的图像金字塔模板匹配算法进行查表、量化，对比算法改进后的运行时间及各目标匹配得分可知算法节约时间是0.0170秒左右，而相对于准确度，则基本没有变化，这是因为查表和量化主要是在减少重复计算、减少存储开销、加快计算速度。

Table 2. Results of table lookup and quantization optimization

表2. 查表、量化优化结果

4.3. OpenMP并行优化结果分析

OpenMP并行编程不单单对金字塔图层进行并行匹配搜索，同时还对查表、量化的优化进行并行运算，通过制造不同数量集样本验对查表、量化优化过的融合NMSFast的图像金字塔模板匹配算法进行OpenMP并行优化验证，对比改进前和改进后的运行时间，由于是充分利用多核处理器的并行能力，将多个任务交予读个线程同时处理，则只会影响处理速度而不会改变准度确，在此将不会比对目标得分，结果如图4所示，模板数量分别为1000、2000、3000、4000，并行前和并行后运行时间减少28%左右，并且数量越大，运行整体消耗时间减少越明显。

Figure 4. Time consumption before and after OpenMP parallelization improvement

图4. OpenMP并行改进前后时间消耗

4.4. 算法总体改进效果分析

根据上述结果分析比对，在保证算法正确匹配目标的基础上，采用查表、量化和OpenMP并行编程对融合NMSFast的金字塔模板匹配算法进行优化，相对于传统金字塔模板匹配算法，从图3的目标匹配看出，总体匹配时间减少51%左右，准确度提高1.7%左右。韩硕等 [20] 通过基于双模板搜索方式和位置约束系数r改进传统模板匹配算法，在时间上提升28%，闫河等 [21] 提出一种高斯金字塔变换与新粒子群优化算法结合的PCBA模板匹配算法时间上提升30%。如表3所示，本实验对模板匹配算法的改进，时间上的提升更加明显，对工业化生产具有重大意义。

Table 3. Overall performance comparison of the algorithms

表3. 算法总体性能对比

5. 结论

本文提出了一种金字塔模板匹配算法，并融合了NMSFast算法进行优化。通过特征提取、查表优化、OpenMP并行编程和量化等优化措施，大大提高了金字塔模板匹配算法的运行时间和精度。实验结果表明，优化后的算法在大规模、高精度的图像匹配任务中具有较高的性能。与传统的模板匹配算法相比，优化后的算法在计算时间和存储空间消耗方面都有显著改善。引入NMSFast算法的优化进一步提高了算法的速度和效率。查表优化、OpenMP并行编程和量化等技术的应用也对算法的优化起到了积极的作用。

未来的研究方向可以进一步探索以下几个方面。首先，可以进一步优化特征提取过程，提高特征提取的准确性和效率。其次，可以探索更多的优化方法和技术，如深度学习、图像压缩等，来进一步提高算法的性能。此外，可以将算法应用于更广泛的领域，如目标跟踪、视频分析等。最后，可以考虑将算法与其他相关算法进行结合，形成更加强大和全面的图像处理和分析系统。

总之，本文所提出的金字塔模板匹配算法融合NMSFast算法的优化研究对于提高图像模板匹配算法的效率和准确性具有重要意义。通过优化特征提取、引入快速非最大抑制算法、查表优化、OpenMP并行编程和量化等技术，可以显著提升算法的性能。这对于计算机视觉和图像处理领域的研究和应用具有重要的指导意义。随着技术的不断进步和发展，相信金字塔模板匹配算法在实际应用中将发挥越来越重要的作用。

基金项目

国家自然科学基金联合基金重点支持项目(No. U1836205)；贵州大学培育项目《嵌入式系统中可信计算的硬件安全机制研究》，(黔科合平台人才[2017]5788-60)。

NOTES

^*通讯作者。