基于圆投影与径向投影的模板匹配算法

Template Matching Algorithm Based on Circular Projection and Radial Projection

摘要: 针对传统的基于相关性的模板匹配算法计算量大和不具有旋转不变性的问题，提出一种基于圆投影与径向投影的快速模板匹配算法。首先采用跳跃式步长和高斯金字塔策略快速获得圆投影向量，接着使用NCC相似性度量方法进行粗匹配；然后再进行精匹配，得到模板图像在待测图像中的准确位置；最后利用径向投影得到模板与待匹配图像之间旋转的角度。实验结果表明：基于圆投影与径向投影的模板匹配算法不仅可以解决旋转不变性的问题，还可以准确获得模板与待匹配图像之间的旋转角度，匹配速度也较快。

Abstract: Aiming at the problems of a large amount of computation and no rotation invariance of the traditional template matching algorithm based on correlation, a fast template matching algorithm based on circular projection and radial projection is proposed. Firstly, the circular projection vector is quickly obtained by using jump step size and Gaussian pyramid strategy, and then the NCC similarity measurement method is used for rough matching; then, the accurate position of the template image in the image to be measured is obtained by fine matching; Finally, the rotation angle between the template and the image to be matched is obtained by radial projection. The experimental results show that the template matching algorithm based on circular projection and radial projection can not only solve the problem of rotation invariance, but also accurately obtain the rotation angle between the template and the image to be matched, and the matching speed is also fast.

1. 引言

模板匹配是一种常见的图像处理算法，其基本思想是在待匹配图像中找到与模板图像相似度最大的子图。模板匹配技术在图像分割、目标识别、工业定位、产品分类等领域中被广泛应用。模板匹配按照匹配的特征可以分为两大类：基于图像灰度特征和基于图像几何特征的模板匹配 [1]。基于图像几何特征的模板匹配算法通常是提取图像的角点、边缘、面积、梯度、曲率等信息，进行相似性判断。这类算法受光照变化的影响较小，而且可以解决模板图像与待测图像之间的旋转和缩放问题，但是算法复杂性较大，通常耗时也大 [1] [2]。基于图像灰度特征的模板匹配是利用统计学相关性算法计算模板图像与待测图像灰度信息的相似性。常见的相似性度量方法有：MAD算法、SAD算法、SSD算法、NCC算法、SSDA算法 [3]。这类方法的优点是原理简单，容易实现，匹配速度也相对较快，在图像受到的干扰性不强时，得到的结果很准确。但是这类方法对光照变化和噪声比较敏感，而且当待匹配图像与模板图像存在一定角度时，匹配准确率会随着角度的变大而降低，当角度过大的时候会完全失效 [4]。如何解决基于灰度特征的模板匹配算法的旋转不变性一直是一个热点问题。

之前，解决基于灰度特征的模板匹配的旋转不变性问题的做法是在360度范围内，以一定角度增量旋转模板后再计算搜索区域同模板之间的相似性。显然，这种处理方式的运算量很大，很难用于实时检测系统中 [5]。目前，比较有效的办法是利用圆各向同性的特点，进行圆投影匹配。近些年，不少研究学者在圆投影的基础上进行了大量研究。薛骏、程俊等人针对传统模板匹配方法不适用于元件标志的旋转情况，提出基于圆投影与矢量和的旋转不变量检测方案，利用圆周投影图像灰度特征向量来进行匹配，该方案可以解决图像旋转匹配的问题 [6]。王珏和孙小惟提出了一种基于圆投影及直方图不变特征的图像匹配方法，他们利用圆投影方法进行预处理，采用圆形模板对待匹配图像进行快速搜索，最后用直方图不变矩作为图像特征量进行匹配。该方法有效解决了目标图像和匹配图像之间存在的较大旋转问题 [7]。徐亦斌、王敬东等人利用圆的各向同性和投影特征提出了圆投影匹配算法，通过对圆投影向量进行重构，进行改进。改进后的圆投影匹配算法对灰度变化、噪声、光照以及对比度变化等具有更好的鲁棒性 [8]。贾晓芬、赵佰亭等人针对现有的圆投影匹配方法在实际应用中计算量高、速度慢的缺点，提出了一种新的图像匹配算法．该算法基于序贯相似检测原理，采用由粗到精的匹配策略，实现了较高的匹配精度和匹配速度 [9]。王培容、陈鸿雁等人将圆投影和Zernike矩相结合实现了快速且具有旋转不变性的模板匹配 [10]。谢志江、吕波等人将圆投影，图像梯度幅值和图像梯度角度相结合实现了任意角度旋转的情况下的匹配 [11]。上述基于圆投影的模板匹配算法只是实现了旋转不变性，而没有得到模板与待匹配图像之间准确的旋转角度。针对这一问题，曹田、李勃等人基于混合圆投影向量，结合塔式分解和角度直方图估计，不仅可以识别出模板在待匹配图像中的准确位置，还可以通过角度估计策略得到模板的旋转角度 [12]。张俊凯把圆投影把图像Hu距和Zernike距相结合，作为相似度匹配信息，进行区域定位，并使用Zernike相位相关信息迭代的方法估计旋转角度。但是这两种方法的计算过程比较复杂，计算速度较慢，不能用于实时检测系统中。为了解决传统模板匹配在图像旋转的情况下，匹配准确率低和现有基于圆投影匹配算法速度慢和难以输出旋转角度的问题，提出一种基于圆投影与径向投影的快速模板匹配算法。

2. 圆投影模板匹配算法

获取圆投影向量：以矩形模板的中心为模板的圆心，以矩形模板的最大内接圆半径为圆形模板的半径，设为R，如图1所示。以圆形模板的圆心为坐标系原点，建立直角坐标系。定义图像的圆投影向量为P(R)如公式(1)所示：

$P\left(R\right)=\left[p\left(0\right),\cdots ,p\left(r\right),\cdots ,p\left(R\right)\right]$ (1)

其中p(r)是半径为r的圆上所有像素的灰度平均值如式(2)所示：

$p\left(r\right)={\displaystyle \underset{0}{\overset{2\pi }{\sum }}T\left(r\ast \cos \theta ,r\ast \sin \theta \right)/N\left(r\right)}\left(0<r<R\right)$ (2)

其中 $T\left(r\ast \cos \theta ,r\ast \sin \theta \right)$ 是角度为 $\theta$ 半径为r处像素的灰度值， $N\left(r\right)$ 为半径为r的圆上的像素个数，求灰度平均值的目的是为了降低噪声的影响。

Figure 1. Schematic diagram of circular formwork

图1. 圆形模板示意图

设待匹配图像S的大小为M * N，圆形模板图像T的大小为R * R， $S_{\left(i,j\right)}$ 为模板图像在待匹配图像中子图的位置 $\left(0<i<M-R,0<j<N-R\right)$，如图2所示。用P_T(R)表示模板的圆投影向量。 $P_{S\left(i,j\right)}\left(R\right)$ 表示子图 $S_{\left(i,j\right)}$ 的圆投影向量。利用NCC作为相似性的度量，其计算公式如式(3)所示：

$\rho \left(i,j\right)=\frac{{\displaystyle {\sum }_{r=0}^R\left(\left[p_T\left(r\right)-{\bar{p}}_T\right]\times \left[p_{S\left(i,j\right)}\left(r\right)-{\bar{p}}_{S\left(i,j\right)}\right]\right)}}{\sqrt{{\displaystyle {\sum }_{r=0}^R{\left[p_T\left(r\right)-{\bar{p}}_T\right]}^2}}\times \sqrt{{\displaystyle {\sum }_{r=0}^R{\left[p_{S\left(i,j\right)}\left(r\right)-{\bar{p}}_{S\left(i,j\right)}\right]}^2}}}$ (3)

式中 ${\bar{p}}_T=\frac{{\displaystyle {\sum }_{r=0}^R{p}_T\left(r\right)}}{R+1}$, ${\bar{p}}_{S\left(i,j\right)}=\frac{{\displaystyle {\sum }_{r=0}^R{p}_{S\left(i,j\right)}\left(r\right)}}{R+1}$。当 $\rho$ 最大时的i和j的位置即为最佳匹配位置。虽然圆投影算法将图像二维向量转化为一维向量后，再进行相似性计算，数据量得到了减少，加快了匹配速度，但是在求圆投影向量时需要计算所有半径下的灰度平均值，造成匹配速度下降，难以满足工业上的实时性要求。当图像旋转的时候，由于图像的圆投影向量不会随着旋转角度的变化而变化，所以利用图像的圆投影向量进行匹配具有旋转不变性。但是圆投影匹配算法只能获得模板在待匹配图像中的位置，而无法获得模板与待匹配图像之间的旋转角度。

Figure 2. Circular projection matching analysis

图2. 圆投影匹配分析图

3. 快速匹配策略

为了快速准确的匹配到模板图像，采用由粗到精的匹配策略。金字塔下采样是一种常见的减少数据量的方法。下采样是把图像的尺寸缩减一半，行和列同时缩减一半。如果直接隔行隔列删除，原图中的边缘会变成锯齿状，造成严重失真。为了使下采样获得的图像看起来自然，必须提前进行平滑，所以选用高斯金字塔下采样方法。在粗匹配过程中首先将模板图像和待匹配图像都进行金字塔下采样，模板图像下采样图像如图3所示。

Figure 3. Template and its down sampled image

图3. 模板及其下采样图像

为了进一步提高匹配效率，将圆投影向量的半径步长和角度步长都扩大，如图4所示。通过高斯金字塔下采样和跳跃式步长这两种方法来加速粗匹配速度。在粗匹配获得的匹配位置附近进行精匹配：将圆投影向量的半径步长和角度步长都缩小，然后用模板原图在待匹配原图上进行匹配，得到精匹配位置。

Figure 4. Schematic diagram of radius step and angle step

图4. 半径步长和角度步长示意图

4. 径向投影模板匹配算法

圆投影匹配算法通过粗匹配到精匹配过程得到的匹配结果，只获取到模板在待匹配图像上的位置，没有得到模板与待匹配图像之间的旋转角度。为了获得模板与待匹配图像之间的旋转角度，采用径向投影匹配算法。

$M\left(2\pi \right)=\left[m\left(0\right),\cdots ,m\left(\theta \right),\cdots ,m\left(2\pi \right)\right]$ (4)

其中 $m\left(\theta \right)$ 是角度为 $\theta$ 的所有半径下像素的灰度线性加权平均值如式(5)所示：

$m\left(\theta \right)={\displaystyle \underset{i=1}{\overset{R}{\sum }}{w}_i\ast T\left(i\ast \cos \theta ,i\ast \sin \theta \right)}\left(0<\theta <2\pi \right))$ (5)

因为越靠近圆心，像素越密集，为了提高抗干扰能力，采用线性权重系数来提高鲁棒性，距离圆心越近的像素灰度的权重系数越小，则权重系数如公式(6)所示：

$w_i=\frac{i}{{\displaystyle {\sum }_{i=0}^{R}i}}$ (6)

设模板的径向投影向量为 $M_T\left(2\pi \right)$，精匹配得到的匹配位置的径向投影向量为 $M_S\left(2\pi \right)$，设角度为 $\alpha$ 时的径向投影为 $M_{S\left(\alpha \right)}\left(2\pi \right)=\left[m\left(\alpha \right),m\left(\alpha +1\right),\cdots ,m\left(2\pi \right),m\left(0\right),\cdots ,m\left(\alpha -1\right)\right]$，然后利用NCC作为相似性度量，其计算公式如式(7)所示：

$\rho \left(\alpha \right)=\frac{{\displaystyle {\sum }_{\theta =0}^{2\pi }\left(\left[m_T\left(\theta \right)-{\bar{m}}_T\right]\times \left[m_{S\left(\alpha \right)}\left(\theta \right)-{\bar{m}}_{S\left(\alpha \right)}\right]\right)}}{\sqrt{{\displaystyle {\sum }_{\theta =0}^{2\pi }{\left[m_T\left(\theta \right)-{\bar{m}}_T\right]}^2}}\times \sqrt{{\displaystyle {\sum }_{\theta =0}^{2\pi }{\left[m_{S\left(\alpha \right)}\left(2\pi \right)-{\bar{m}}_{S\left(\alpha \right)}\right]}^2}}}$ (7)

式中 ${\bar{m}}_T=\frac{{\displaystyle {\sum }_{\theta =0}^{2\pi }{m}_T\left(\theta \right)}}{2\pi +1}$, ${\bar{P}}_{S\left(i,j\right)}=\frac{{\displaystyle {\sum }_{\theta =0}^{2\pi }{m}_{S\left(\alpha \right)}\left(\theta \right)}}{2\pi +1}$。当 $\rho \left(\alpha \right)$ 最大时的 $\alpha$ 的位置即为最佳匹配角度。

5. 实验与总结

实验平台为Windows10操作系统、i7处理器的电脑，编程软件为Visual Studio 2017。图5是模板图，将不同位置拍摄的10张照片每隔10度旋转一次，旋转6次，共获得70张待匹配图片，图6是待匹配图像中的一张。其中传统匹配模板的像素大小为122 * 102，本文匹配模板为半径为50像素的圆形模板，待匹配图像的像素大小是5472 * 3468。

Figure 5. Formwork

图5. 模板图

Figure 6. Diagram to be matched

图6. 待匹配图

5.1. 匹配准确性

传统模板匹配方法和本文模板匹配方法在不同角度下匹配的平均得分如表1所示，匹配结果如图7和图8所示。由表1和图7和图8可以看出：当旋转角度大于20˚时，传统模板匹配算法的匹配得分低于了0.8，而且匹配结果完全是错误的，但是本文的模板匹配算法，即使旋转角度为60˚的时候，匹配得分还在0.99以上，而且匹配准确结果准确。

Table 1. Matching scores under different angles

表1. 不同角度下的匹配得分

Figure 7. Matching results of traditional template matching algorithm at 0˚~60˚

图7. 传统模板匹配算法在0˚~60˚时的匹配结果

Figure 8. Matching results of template matching algorithm in this paper at 0˚~60˚

图8. 本文模板匹配算法在0˚~60˚时的匹配结果

5.2. 匹配速度

传统模板匹配方法、未加入匹配策略的本文模板匹配方法和采用由粗到精的策略的本文模板匹配方法的匹配平均时间如表2所示。通过表2可以看出：未加入匹配策略的本文模板匹配算法只比传统的模板匹配算法快了一点，但是采用由粗到精的匹配策略后，匹配速度快了3倍左右。

Table 2. Average matching time of different methods

表2. 不同方法匹配平均时间

5.3. 匹配角度

径向投影向量的搜索步长分别为10˚、1˚、和0.1˚时的角度匹配准确率、匹配得分和匹配速度如表3所示。由表3可以看出：搜索步长为10˚和1˚的时候，角度匹配准确率为100%，但是搜索步长为0.1˚时，匹配准确率只有85%了，这说明本文基于径向投影的匹配算法的精度为高于0.1˚；随着搜索步长的减少，角度匹配得分在逐渐增加，但是匹配速度在逐渐降低。

Table 3. Matching results when radial projection vector search steps are different angles

表3. 径向投影向量搜索步长为不同角度时匹配结果

6. 总结

本文针对传统模板匹配速度慢和不具有旋转不变性的问题，提出了一种基于圆投影与径向投影的模板匹配算法。实验结果表明：本文方法不仅解决了旋转不变性的问题，还准确地获得了模板图像与待匹配图像之间的旋转角度，而且采用的高斯金字塔和跳跃式步长策略可以大大提高检测效率。

致谢

首先，我要感谢我的导师。他一丝不苟的学术探索精神激励着我在学习和生活上遇到挫折时要敢于直面困难，他以深厚的科研经验教导着我如何正确解读文献，如何学习总结，在积累中逐步提升自己的学术水平。在论文题目的确立和论文的修改方面，他给了我很多宝贵的建议。

感谢各位师兄弟们在学期间对我的照顾，遇到学习的难题时你们细心地为我解答，很幸运研究生阶段有你们的相伴。

最后的最后，感谢评审论文的专家们，感谢你们为本文提出的宝贵建议。

基金项目

湖南省教育厅重点资助项目(19A170)。

NOTES

^*通讯作者。