基于环投影和快速动态时间规整的模板匹配算法

Template Matching Algorithm Based on Ring Projection and Fast Dynamic Time Warping

摘要

针对传统方法在旋转、尺度及光照鲁棒性和计算效率上的不足，提出了一种基于改进环投影与快速动态时间规整的模板匹配算法.在特征提取阶段，采用自适应环投影方法，通过动态调整角度步长实现均匀采样，并结合高斯平滑与光照补偿，以提升特征提取的光照鲁棒性和抗噪性.在模板匹配阶段，通过快速动态时间规整算法对齐不同尺度的环投影序列并直接计算尺度因子和匹配距离，结合径向投影计算旋转角度，并使用步长加速法代替逐点遍历以提高搜索效率.在测试图像集上的实验表明，在0.8~1.2尺度范围内的匹配准确率大于97.5%，与传统环投影算法相比，匹配速度提高1.84倍.

Abstract

To address the shortcomings of traditional methods in terms of rotation， scale， illumination robustness， and computational efficiency， a template matching algorithm based on improved ring projection and fast dynamic time warping was proposed. In the feature extraction stage， an adaptive ring projection method was adopted， which achieved uniform sampling by dynamically adjusting the angle step size， and it was combined with Gaussian smoothing and illumination compensation to enhance the illumination robustness and noise resistance of feature extraction. In the template matching stage， the fast dynamic time warping algorithm was used to align ring projection sequences at different scales and directly calculate the scaling factor and matching distance. Radial projection was combined to calculate the rotation angle， and the step acceleration method was used to replace point-by-point traversal to improve search efficiency. Experiments on the test image set show that the matching accuracy within the scale range of 0.8~1.2 is greater than 97.5%， and the matching speed is increased by 1.84 times compared with the traditional ring projection algorithm.

Graphical abstract

关键词

模板匹配 / 环投影 / 快速动态时间规整 / 径向投影 / 步长加速法

Key words

template matching / ring projection / fast dynamic time warping（fast DTW） / radial projection / step acceleration method

模板匹配是一种广泛应用于计算机视觉和图像处理领域的技术，用于在一幅图像中定位和识别特定模式或对象，具有精度高、鲁棒性强、适用性广和原理清晰的优点，在工业检测、遥感和医学影像等领域发挥着重要作用^［1-3］.模板匹配的基本思想是将模板与目标图像进行相似性比较，从而找到最佳匹配位置.模板匹配算法通常采用逐点搜索的方法，比较模板与场景图像中各个位置的子图的相似度，当相似度最大时，该位置即为目标位置^［4］.

最常用的相似性度量包括绝对差值总和（sum of absolute differences，SAD）、平方差和（sum of squared differences，SSD）和归一化互相关（normalized cross-correlation，NCC）^［5］，其中NCC具有更高的鲁棒性^［6］，而零均值归一化互相关（zero-mean normalized cross-correlation，ZNCC）在计算时减去窗口内的均值以克服光照和亮度的变化，使其广泛应用于物体识别和工业检测，但依然存在缺乏旋转不变性的缺陷^［7-8］.Lin^［9］提出了一种基于环投影的匹配方法，环投影将目标的形状信息从二维空间转化为一维的投影特征，以互相关系数作为匹配分数标准，实现旋转不变性和尺度不变性，并可以通过径向投影计算具体的旋转角度^［10］.但基于环投影的模板匹配依然不具有尺度不变性，需要一组不同尺度的模板图像构建模板向量，无法通过单一模板实现多尺度的模板匹配^［11］.基于深度学习的模板匹配通过卷积神经网络提取图像特征，然后结合传统的密集特征相似度评估算法或简单的评估网络来实现模板匹配，如基于Siamese网络与NCC的模板匹配^［12］、质量感知模板匹配^［13］、广义模态不变特征变换^［14］等，这些算法进一步提升了匹配的准确性和鲁棒性，也极大地拓宽了其应用范围，但对硬件平台也有更高的要求.动态时间规整（dynamic time warping，DTW）常用于语音模板的识别和匹配^［15］，可以处理非线性时间形变，如局部拉伸或压缩，适用于长度不同或存在局部时间偏移的序列的对齐，使得通过单一模板计算尺度因子成为可能.但与NCC相比，DTW的时间复杂度更高，在窗口遍历过程中占用过大的计算资源，当序列长度较大时无法满足匹配需求^［16］.快速动态时间规整（fast DTW）结合了区域限制和抽样，加速了DTW的计算^［17］.

针对现有模板匹配方法的不足，本文提出了一种基于自适应改进环投影和快速动态时间规整的模板匹配算法.该算法克服了传统环投影算法无法通过单一模板计算尺度的缺陷，无需样本训练，同时不需要对待测图像逐像素遍历，能通过单一模板实现高效精确的尺度不变模板匹配.

1 改进的模板匹配算法

1.1 改进环投影特征提取

环投影变换通常用于图像处理中的旋转不变性特征提取.其基本思想是将二维图像转换到极坐标系，在不同半径的环上进行投影，生成一维的特征向量^［18］，如图1所示.

定义M×N的模板图像为T(x,y)，其图像中心为(x_{\mathrm{0}},y_{\mathrm{0}})，以图像中心为坐标原点的极坐标(r,\theta )的欧氏坐标为

\left.\begin{array}{c}x=x_{\mathrm{0}}+r\mathrm{c}\mathrm{o}\mathrm{s}\theta ,\\ y=y_{\mathrm{0}}+r\mathrm{s}\mathrm{i}\mathrm{n}\theta .\end{array}\right\}(1)

式中：r表示环的半径，r=\sqrt[]{(x-x_{\mathrm{0}}{)}^{\mathrm{2}}+(y-y_{\mathrm{0}}{)}^{\mathrm{2}}},r\in [\mathrm{0},R];\theta表示极坐标系下该点的极角，\theta \in [\mathrm{0,2}\mathrm{\pi }]，最大内切圆半径R=\mathrm{m}\mathrm{i}\mathrm{n}(M,N)/\mathrm{2}.半径为r的环的投影值P_{\mathrm{t}}(r)和图像的环投影向量{\mathit{P}}_{\mathrm{t}}为

\left.\begin{array}{c}{P}_{\mathrm{t}}(r)=\frac{\mathrm{1}}{s(r)}{\displaystyle \sum _{\theta =\mathrm{0}}^{\mathrm{2}\mathrm{\pi }}}(T(r,\theta )-T_{\mathrm{m}\mathrm{i}\mathrm{n}}(r,\theta )),\\ {\mathit{P}}_{\mathrm{t}}=\left[P_t(\mathrm{1}),P_t(\mathrm{2}),P_t(\mathrm{3}),\dots ,P_t(R)\right].\end{array}\right\}(2)

式中：T(r,\theta )表示极坐标点的像素值；T_{\mathrm{m}\mathrm{i}\mathrm{n}}(r,\theta )表示落在半径为r的环上像素的最小像素值；s（r）为当前环上所取像素总数.

当光照强度均匀变化时，像素值的变化可表示为

I(x,y)=k{I}_{\mathrm{0}}(x,y)+t.(3)

式中：I(x,y)和I_{\mathrm{0}}(x,y)分别为光照改变后的像素灰度和原像素灰度；k和t为常数.当图像的全局光照强度发生改变时，对于加性分量t，每个环的投影值为

P_{{\mathrm{t}}_{\mathrm{1}}}(r)=\frac{\mathrm{1}}{s(r)}{\displaystyle \sum _{\theta =\mathrm{0}}^{\mathrm{2}\pi }}[T(r,\theta )+t-T_{min}(r,\theta )-t]=P_{\mathrm{t}}(r). (4)

可得加性分量并不改变投影值.对于其中的乘性分量k，P_{\mathrm{t}}(r)\propto k，环投影幅值与k成正比.式（2）中减去T_{\mathrm{m}\mathrm{i}\mathrm{n}}(r,\theta )以去除光照变化中的加性分量，提高环投影特征向量对光照的鲁棒性，同时将环投影向量的起始点移动到坐标原点，便于后续进行匹配.

由于数字图像中像素点的离散性质，在计算图像环投影特征向量时需要按照一定的半径步长∆r和角度步长∆θ对像素点进行采样.为确保对图像特征的均匀采集，半径步长一般取固定值，本文取为1像素.在传统环投影中，往往取角度步长为固定值，在不同半径的环上的采样点数相同，即s（r）为固定值，这将导致在r较小的环上采样过于密集，降低了计算效率，而在r较大的环上采样过于稀疏，造成特征信息的丢失，降低了计算精度，如图2a所示.对此，根据半径的变化对∆θ进行调整，设半径为r的环上的采样点数为

s(r)=\mathrm{2}\mathrm{\pi }r/\omega .(5)

式中：ω为固定常数，为便于计算可取\mathrm{\pi }或2\mathrm{\pi }，角度步长Δθ=ω/r，即半径越大Δθ越小，s（r）越大，使得采样点在图像上均匀分布，提高特征提取精度和计算效率，如图2b所示.

圆环在旋转时形状不变，尽管旋转后相同半径的环上的采样点可能不同，但旋转只改变角度分量，环上像素的统计值不会因角度变化而改变.因此环投影具有旋转不变性，在模板匹配中无需预存多角度模板，可通过单一模板匹配任意旋转角度的目标.

当目标图像发生缩放时，对应的环投影半径放大或缩小，环投影向量的一维轮廓也按缩放比例呈现拉伸或压缩，特征向量的长度变化，但走势基本保持不变.

将原始图像分别进行旋转90°，增强光照（k=1.75）以及图像放大1.15倍，其环投影向量如图3所示.旋转几乎不改变环投影向量曲线，而图像的缩放只改变序列的长度，光照变化只改变环投影向量的幅值，环投影向量的趋势皆保持基本不变.

1.2 快速动态时间规整

动态时间规整（DTW）是一种用于衡量时间序列相似性的算法.DTW通过动态规划的方法，计算两个序列之间的距离矩阵，找到最佳对齐路径并将两序列对齐，使得对齐后的总距离最小.即使两个序列在时间轴上有不同程度的拉伸或压缩，也能准确计算它们的相似性，如图4所示.图中i，j分别表示序列 x 和序列 y 中的位置索引，矩阵网格中的各点表示序列 x 中的第i点与序列 y 中的第j点相匹配.当图像发生缩放时，模板图像和目标子图像的环投影序列的长度将按比例拉伸或压缩，而DTW尤其适用于处理不同长度或存在时间偏移的序列，可以解决匹配中的尺度变化问题.

然而，传统DTW具有平方时间复杂度，为O（n²）（n表示时间），这使其在处理大规模时间序列数据时效率较低，在模板匹配的遍历过程中将占用过大的计算资源.fast DTW结合抽样和约束，通过多级分辨率显著降低计算成本，通常能达到或趋近线性时间复杂度O（n）^［19］.fast DTW主要步骤如下：

1） 将序列粗化，通过多次抽样逐级降低原序列分辨率，每次长度减半，得到1/8—1/4—1/2—1/1分辨率的序列；

2） 使用DTW在最低分辨率下找到最佳规整路径，并将该路径投影到更高分辨率，作为高分辨率下最佳路径的初始猜想；

3） 对低分辨率下得到的路径进行局部调整，得到更高分辨率下的路径.为增加找到最佳路径的可能性，需要在投影路径的邻域中寻找最佳的规整路径，其中邻域的大小由半径参数控制，对于离散的图像数据，半径参数设为1.

fast DTW的多分辨率粗化如图5所示.

fast DTW将两个序列对齐并返回两序列的距离，这将作为模板匹配的直接依据.同时能够得到两序列的距离矩阵和规整后的对齐路径，对齐后的序列长度相等，回溯路径，记录匹配点对.设P_{\mathrm{1}}(i)表示模板序列中第i个点的位置索引，P_{\mathrm{2}}(i)表示待测序列中与P_{\mathrm{1}}(i)匹配的第i个点的位置索引，对于每组点对，局部尺度因子K_i=P_{\mathrm{2}}(i)/P_{\mathrm{1}}(i).由于当两序列尺度相差过大或相关性过低时都会造成K_i 过高或过低，同时当尺度相差过大时DTW难以将序列准确对齐，故只保留合理范围内的K_i\in [\mathrm{0.7,1.3}].改进环投影序列的起始点相同，而由于两序列初始长度不同，模板图像与相同大小的子图像的环投影序列末端差异过大，保留K_i序列中间1/5到4/5部分的值以提高尺度因子计算的准确性.设K_i 序列长度为l，则平均尺度因子为

K={\displaystyle \sum _{i=⌊l/\mathrm{5}⌋}^{⌊\mathrm{4}l/\mathrm{5}⌋}}{K}_i/(⌊\mathrm{4}l/\mathrm{5}⌋-⌊l/\mathrm{5}⌋-\left.\mathrm{1}\right).(6)

式中，K为目标序列相对于模板序列的平均尺度因子.环投影向量间的尺度比即为半径比，即匹配的子图像与模板图像的缩放比为K.

当图像的背景过于复杂时，其环投影向量的一维轮廓往往存在大量连续的尖锐锯齿；同时原始图像中的噪声、光照不均以及局部区域过高的对比度都可能会导致环投影的一维轮廓出现局部剧烈波动，对fast DTW的匹配造成影响，尤其是在子图像与模板图像尺度不一致的情况下.为提高匹配的鲁棒性，需要对环投影的轮廓曲线进行高斯平滑.高斯滤波通过加权平均邻域像素值，平滑一维轮廓的高频噪声，保留主要趋势，达到抑制噪声干扰的效果，如图6所示.取标准差\sigma =\mathrm{1}，核范围为［-3，3］，则滤波窗口大小为n_{\mathrm{G}}=\mathrm{7}.高斯核函数为

G(x)=\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{x^{\mathrm{2}}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right).(7)

设原序列为 P₀（x），则滤波后的序列为

{\mathit{P}}_{\mathrm{1}}(x)={\mathit{P}}_{\mathrm{0}}(x)\otimes G(x)/{\displaystyle \sum _{x=\mathrm{1}}^n}G(x).(8)

图7a为原始模板图像，图7b为其旋转90°，放大1.15倍并增强亮度（k=1.75）后所得，以进行对比.计算两图像的环投影向量并进行高斯平滑，得到一维轮廓曲线如图7c所示.使用fast DTW进行匹配，匹配结果及对齐后的序列如图7d所示.经计算得到尺度因子为1.146.

1.3 径向投影

环投影是对圆周上所有像素点的平均灰度值进行计算，忽略了像素点在圆周上的具体位置信息，且由于角度信息被平均化，环投影无法反映图像在不同角度上的具体特征变化.因此基于环投影的模板匹配虽然可以找到模板图像旋转后的位置，但无法得到旋转的角度.

径向投影算法常用于模板匹配中的旋转角度计算，通过将二维旋转问题转换为一维信号的平移问题来实现，是一种快速而可靠的方法^［20］.算法的核心思想是将图像转换到极坐标系，并沿径向积分，生成一维投影序列.当图像旋转时，极坐标系下的角度轴会发生平移，通过比较投影序列的平移量即可确定旋转角度，如图9所示.设模板图像为T(x,y)，图像中心为(x_{\mathrm{0}},y_{\mathrm{0}})，图像最大内切圆半径为R，则图像的径向投影为

\left.\begin{array}{c}{P}_{\mathrm{r}}(\delta )={\displaystyle \sum _{r=\mathrm{0}}^R}T(r,\delta )/n_{\mathrm{r}},\delta \in \left[\mathrm{0,2}\mathrm{\pi }\right],\\ {\mathit{P}}_{\mathrm{r}}=\left[P_r(\mathrm{1}),P_r(\mathrm{2}),P_r(\mathrm{3}),\dots ,P_r(\mathrm{360})\right].\end{array}\right\}(9)

其中：\delta为极坐标中的角度；n_r为径向上的采样点数，取角度步长\mathrm{\Delta }\delta =1°，则图像的径向投影向量维数为360.

为降低噪声、局部光照以及局部过高对比度对径向投影匹配的影响，对径向投影轮廓曲线进行高斯平滑，同式（7），式（8）.

使用环投影和fast DTW匹配待测图像中目标子图像的中心坐标，在匹配过程中待测子图像窗口大小和模板图像相同.由于尺度变化，子图像最大半径为R_p=R×K，由fast DTW计算得出.图9a为原始图像，图9b由原图像逆时针旋转90°，放大1.2倍并提高亮度（k=1.75）后得到，图9c，图9d分别为其径向投影.

360°的投影在首尾（0°与360°）处存在不连续边界.为利用一维窗口滑动对模板图像与待测子图像的径向投影进行匹配，需将模板图像的径向投影角度拓展至720°，即

{\mathit{P}}_{\mathrm{r}}=\left[P_r(\mathrm{1}),P_r(\mathrm{2}),\dots ,P_r(\mathrm{360}),P_r(\mathrm{1}),\dots ,P_r(\mathrm{360})\right].(10)

投影向量首尾相连形成闭环，可通过单次滑动匹配覆盖所有可能的旋转角度（0°~359°），确保任意旋转角度的匹配均落在连续区间内.以互相关函数值作为匹配分数，其计算公式为

{\rho }_{\mathit{x},\mathit{y}}=\frac{\mathrm{c}\mathrm{o}\mathrm{v}(\mathit{x},\mathit{y})}{\sqrt[]{D(\mathit{x})} \sqrt[]{D(\mathit{y})}}.(11)

式中：\mathrm{c}\mathrm{o}\mathrm{v}(\mathit{x},\mathit{y})表示序列 x 和 y 的协方差；D(\mathit{x})和D(\mathit{y})分别为序列\mathit{x}和\mathit{y}的方差.互相关函数值最高处所对应角度即为旋转角度，如图10所示.计算得旋转角度为90°，与实际值相符.

1.4 匹配流程

1.4.1 主要步骤

基于改进环投影和快速时间规整的模板匹配目的在于使用单一模板确定待测图像中目标对象的位置、旋转角度和尺度因子.为了提高计算效率，本文采用一系列加速策略.匹配过程如下：

1） 预处理，去除图像中的噪声.由于环投影需要在环上进行采样计算环的统计值，噪声点会对计算造成干扰，破坏图像特征的提取，需要使用均值滤波去除图像噪声点.

2） 环投影特征提取.使用改进的环投影算法提取模板图像的环投影特征向量，并对所得特征向量进行高斯平滑.

3） 粗匹配.当待测图像较大时，使用高斯金字塔方法对待测图像和模板图像进行降采样处理，将图像映射到低分辨率.在水平和垂直方向以步长\lambda遍历待测图像，计算待测子图像的环投影向量，并用fast DTW计算匹配距离.若当前点距离小于阈值，则设其为初始猜测；否则完成遍历后将得到的距离最小的点作为初始猜测.对于M×N的模板图像，步长\lambda的经验取值范围为［3，0.1 min（M，N）］.

4） 以初始猜测为起点，使用步长加速法对其邻域进行搜索，找到其邻域内环投影与模板环投影DTW距离最小的点，该点即为最佳匹配点，并通过DTW路径的回溯计算其尺度因子.

5） 亚像素调整.可使用双线性插值法对已获得的整数匹配点进行局部亚像素调整.

1.4.2 步长加速法

在匹配中，待测子图像与模板图像的环投影间的距离在理想匹配点达到最小值.一般而言，在一定区域内，模板环投影与待测环投影的距离会随着待测点与理想匹配点距离的增加而增大，用等值线图表示以理想匹配点为中心的区域内各点所对应的匹配距离，理想匹配点位于最内圈，越向外圈匹配距离越大，如图11所示.

步长加速法是一种无导数优化算法，通过交替执行探测搜索和模式移动逐步逼近最优解，用于寻找多变量函数的局部极小值^［21］.

以x_{\mathrm{0}}作为探测搜索的出发点，作为参考点，用a表示，即a=x_{\mathrm{0}}，在其周围搜索数值更小的点b使，即I型探测.从b出发沿模式方向(b—a)做模式移动，得到新参考点a^{\mathrm{*}}=\mathrm{2}b-a，并从新参考点再次进行探测（II型探测），若探测所得新基点的值f(b^{\mathrm{*}})>f(b)，则模式移动作废，以前基点b作为新的初始参考点重新进行探测.交替进行的探测搜索和模式移动将使迭代点逐渐向极小点靠近.步长加速法流程如图12所示.

以粗匹配点作为初始参考点进行补偿加速搜索，得到理想的最佳匹配点，步长加速法搜索路径如图13所示.其中矩形为参考点，圆形为基点，实线为模式移动路径.设待测图像大小为W×L，模板图像大小为M×N，采用逐点遍历时需进行（W-M+1）×（L-N+1）次匹配计算，而当图像较大时采用步长加速法所需的计算次数将接近逐点遍历的\mathrm{1}/{\lambda }^{\mathrm{2}}.

1.4.3 双线性插值

图像中心点坐标以及旋转和尺度变化后的像素坐标往往并非整数点，而非整数坐标无法直接应用于图像数据.一些应用场景需要将精度提高到亚像素级，同时在多分辨率匹配时由低分辨率向高分辨率的映射可能会造成误差累积.双线性插值是一种在二维空间中基于相邻4个已知点的像素值估计非整数坐标点像素值的方法，广泛应用于模板匹配中的亚像素优化、几何变换处理及多尺度分析^［19］.

双线性插值分为x和y方向上的两次插值.设距离非整数点P最近的4个整数点Q_{\mathrm{11}}(x_{\mathrm{1}},y_{\mathrm{1}})，Q_{\mathrm{12}}(x_{\mathrm{1}},y_{\mathrm{2}})，Q_{\mathrm{21}}(x_{\mathrm{2}},y_{\mathrm{1}})，Q_{\mathrm{22}}(x_{\mathrm{2}},y_{\mathrm{2}})，水平插值点为R_{\mathrm{1}}(x,y_{\mathrm{1}})，R_{\mathrm{2}}(x,y_{\mathrm{2}})，如图14所示.R₁和R₂的像素值分别为

\left.\begin{array}{c}f(R_{\mathrm{1}})=\frac{x_{\mathrm{2}}-x}{x_{\mathrm{2}}-x_{\mathrm{1}}}f(Q_{\mathrm{11}})+\frac{x-x_{\mathrm{1}}}{x_{\mathrm{2}}-x_{\mathrm{1}}}f(Q_{\mathrm{21}}),\\ f(R_{\mathrm{2}})=\frac{x_{\mathrm{2}}-x}{x_{\mathrm{2}}-x_{\mathrm{1}}}f(Q_{\mathrm{12}})+\frac{x-x_{\mathrm{1}}}{x_{\mathrm{2}}-x_{\mathrm{1}}}f(Q_{\mathrm{22}}).\end{array}\right\}(12)

在y方向上进行第二次插值，得到点P的像素值为

f(P)=\frac{y_{\mathrm{2}}-y}{y_{\mathrm{2}}-y_{\mathrm{1}}}f(R_{\mathrm{1}})+\frac{y-y_{\mathrm{1}}}{y_{\mathrm{2}}-y_{\mathrm{1}}}f(R_{\mathrm{2}}).(13)

初步匹配后，通过插值整数匹配点周围的匹配得分，将探测步长缩小为0.1像素进行搜索，优化最佳匹配位置，提升精度至亚像素级.

1.4.4 矩形模板匹配

环投影实际是基于圆形模板提取图像特征，其提取范围是模板的内切圆，对于正方形模板，环投影能提取超过78%的图像信息，只忽略了顶点附近的少量边缘部分.而对于长宽比较大的矩形模板，中心环投影在匹配时会造成模板信息的大范围丢失.对此，可将矩形模板沿长轴划分为多个子区域，每个子区域进行独立环投影，如图15所示.

设矩形模板长边为l_{\mathrm{1}}，短边为w_{\mathrm{1}}，将矩形分为H个圆形区域，将矩形模板变成H个圆模板的匹配.其中H=⌈l_{\mathrm{1}}/w_{\mathrm{1}}⌉.

2 实验结果与分析

本文实验采用Ryzen 7 6800H处理器，实验环境为MATLAB R2023a，采用遥感图像数据集和汽车零部件图像对算法进行测试.选取单一模板，以0.05的尺度步长对待测图像进行0.7~1.3范围的缩放，并改变图像的旋转角度和亮度，以验证算法的匹配准确率、旋转不变性、尺度不变性以及匹配效率，并将本文方法与ZNCC，FFT以及传统环投影算法等进行对比，如图16所示.为保证环投影的采样点数满足滤波条件以及fast DTW在多分辨率下对齐的有效性，模板和待测子图像的最大内切圆半径不小于32像素，即\mathrm{m}\mathrm{i}\mathrm{n}(M,N)\ge \mathrm{32}.设实际匹配坐标、尺度因子和旋转角度分别为x_{\mathrm{0}}，s_{\mathrm{0}}和a_{\mathrm{0}}，计算匹配坐标、尺度因子和旋转角度分别为x_{\mathrm{t}}，s_{\mathrm{t}}和a_{\mathrm{t}}，当满足\sqrt[]{(x_{\mathrm{t}}-x_{\mathrm{0}}{)}^{\mathrm{2}}}\le \mathrm{10}，\left|s_{\mathrm{t}}-s_{\mathrm{0}}\right|\le \mathrm{0.1}且\left|a_{\mathrm{t}}-a_{\mathrm{0}}\right|\le \mathrm{5}°时认为匹配准确.本文方法在不同尺度因子下的准确率如图17所示.

ZNCC方法对图像进行归一化处理，对图像的亮度和对比度变化有较强的鲁棒性，将模板图像和待测子图像进行直接对比，无需特征提取和复杂预处理，但不具备旋转不变性和尺度不变性，只对平移模板和纹理受旋转影响小的圆模板有效；FFT方法利用频域相关性实现快速匹配，有最低的时间复杂度，但同样不具备旋转不变性和尺度不变性，且对光照的鲁棒性较差，依赖于图像的预处理；传统环投影方法将二维图像投影为一维特征，具有天然的旋转不变性，同时特征的降维简化了匹配计算，但不具备尺度不变性，需要依据不同尺度因子生成多个模板来完成多尺度匹配；本文方法通过光照补偿和自适应采样提高了光照鲁棒性，减少了特征丢失，通过fast DTW对齐环投影并计算匹配度和尺度因子，具有尺度不变性，无需多模板，在0.8~1.2尺度范围内平均准确率为97.5%（如图17所示）.本文方法的匹配位置、旋转角度和尺度因子的平均误差如表1所示.

对于不同使用环境下的不同背景复杂度，可对粗匹配步长λ进行调整，如图18a~图18b所示，其模板区域大小均为300像素×300像素，设置尺度因子K=1.1，不同粗匹配步长λ下的位置误差如图18c所示.图18a为工业机床下的汽车轮毂图像，该使用环境下的背景复杂度较低，可采用较大步长，如λ=30，即0.1 min（M，N）；图18b为遥感图像，该使用环境下的背景复杂度较高，存在大量与匹配区域相似度较高的区域，应采用较小粗匹配步长，如λ∈［3，10］，以免步长加速法搜索落入局部极小值点，从而维持匹配的准确性和鲁棒性.

各方法的平均运行时间如表2所示.

设模板图像大小为m_t×m_t，待测图像大小为n_t×n_t，本文算法的时间复杂度约为O（m_t²n_t⁴/λ²）.FFT方法通过频域加速有最快的运行速度，其时间复杂度约为O（m_t²lbm_t），但鲁棒性也是最低的；ZNCC方法由于算法较简单运行时间较快，其时间复杂度约为O（m_t²n_t²）；传统环投影速度较慢，特征提取和逐像素遍历消耗大量时间，其时间复杂度约为O（m_t²n_t⁴）；本文方法有更高的特征提取效率，采用步长加速法优化了遍历方式，实际速度较传统环投影提高约1.84倍.

3 结 论

1） 在特征提取阶段，通过动态调整角度步长实现自适应采样，结合高斯平滑与光照补偿策略，显著提升了特征的抗噪性与光照不变性.

2） 采用快速动态时间规整对齐不同长度的环投影序列并计算尺度因子，实现单模板多尺度匹配.

3） 利用径向投影的一维平移特性快速精准计算旋转角度.实验结果表明，其平均旋转角度误差小于0.8°，尺度因子误差低于0.05，具有实际应用价值.

参考文献

[1] Yang X Y. Motion target tracking algorithm based on improved multi-correlation template matching［C］//2025 IEEE International Conference on Computation， Big-Data and Engineering （ICCBE）. Penang， 2025： 741-746.

[2] Lv C H， Wang W， Quan D， et al. Fourier domain adaptive multi-modal remote sensing image template matching based on Siamese network［C］//IGARSS 2024—2024 IEEE International Geoscience and Remote Sensing Symposium. Athens， 2024： 7325-7329.

[3] Yang J S， Zheng Y B， Xu W Y， et al. An accurate and robust multimodal template matching method based on center-point localization in remote sensing imagery［J］. Remote Sensing， 2024， 16（15）： 2831.

[4] Mei L C， Wang C Y， Wang H Y， et al. Fast template matching in multi-modal image under pixel distribution mapping［J］. Infrared Physics & Technology， 2022， 127： 104454.

[5] Almira J M， Phelippeau H， Martinez-Sanchez A. Fast normalized cross-correlation for template matching with rotations［J］. Journal of Applied Mathematics and Computing， 2024， 70（5）： 4937-4969.

[6] Hu M Q， Sun B， Kang X D， et al. Multiscale structural feature transform for multi-modal image matching［J］. Information Fusion， 2023， 95： 341-354.

[7] Mattoccia S， Tombari F， Di Stefano L. Reliable rejection of mismatching candidates for efficient ZNCC template matching［C］//2008 15th IEEE International Conference on Image Processing. San Diego， 2008： 849-852.

[8] Shen Y P， Li S X， Song Y， et al. Ordering pixels for fast ZNCC template matching［C］//2013 IEEE International Conference of IEEE Region 10 （TENCON 2013）. Xi’an， 2014： 1-5.

[9] Lin Y H. New method for subpixel image matching with rotation invariance by combining the parametric template method and the ring projection transform process［J］. Optical Engineering， 2006， 45（6）： 067202.

[10] Lee W C， Chen C H. A fast template matching method with rotation invariance by combining the circular projection transform process and bounded partial correlation［J］. IEEE Signal Processing Letters， 2012， 19（11）： 737-740.

[11] Qi X W， Miao L G. A template matching method for multi-scale and rotated images using ring projection vector conversion［C］//2018 IEEE 3rd International Conference on Image， Vision and Computing （ICIVC）. Chongqing， 2018： 45-49.

[12] Buniatyan D， Macrina T， Ih D， et al. Deep learning improves template matching by normalized cross correlation［EB/OL］. （2017-05-24） ［2025-04-15］.

[13] Yang J S， Zheng Y B， Xu W Y， et al. An accurate and robust multimodal template matching method based on center-point localization in remote sensing imagery［J］. Remote Sensing， 2024， 16（15）： 2831.

[14] Fan Z L， Pi Y D， Wang M， et al. GLS-MIFT： a modality invariant feature transform with global-to-local searching［J］. Information Fusion， 2024， 105： 102252.

[15] Alkhafaji M J A. QATM-KCNN： improving template matching performance based on integration of CNNs and with QATM by Kalman filtering［J］. Journal of Information Systems Engineering and Management， 2025， 10（25s）： 93-104.

[16] Hwang Y. Fast constrained sparse dynamic time warping［J］. Applied and Computational Engineering， 2025， 120（1）： 50-58.

[17] Cai Q L， Chen L Y， Shao J， et al. AdaPDTW： an efficient abstract-adaptive piecewise dynamic time warping for time series classification［J］. IEEE Access， 2025， 13： 84188-84201.

[18] Wang Y L， Liu W， Li F， et al. A fast template matching method based on improved ring projection transformation and local dynamic time warping［J］. Optik， 2020， 216： 164954.

[19] Cui L F， Zhang Q Z， Shi Y， et al. A method for satellite time series anomaly detection based on fast-DTW and improved-KNN［J］. Chinese Journal of Aeronautics， 2023， 36（2）： 149-159.

[20] 刘岩松， 苗立刚， 刘译彭. 基于环投影特征的汽车轮毂定位与识别［J］. 机床与液压， 2020， 48（14）： 73-77.

[21] Liu Yan-song， Miao Li-gang， Liu Yi-peng. Positioning and identification of automobile wheel hub based on ring projection feature［J］. Machine Tool & Hydraulics， 2020， 48（14）： 73-77.

[22] 程江涵， 夏江南， 李毅， 等. 基于FPGA的遥感图像高分辨系统设计［J］. 遥测遥控， 2025， 46（2）： 109-115.

[23] Cheng Jiang-han， Xia Jiang-nan， Li Yi， et al. Design of high-resolution remote sensing image system based on FPGA［J］. Journal of Telemetry， Tracking and Command， 2025， 46（2）： 109-115.