CN101556694B - 一种旋转图像的匹配方法 - Google Patents

Abstract

本发明涉及一种旋转图像的匹配方法，其包括：(1)确定输入角度搜索范围，以中间角度值及搜索范围的首末两个角度为搜索角度，旋转搜索窗口分别进行灰度归一化互相关匹配，获得各自匹配值；(2)将角度间距缩小一倍定为新角度搜索范围，以步骤(1)中取得最大匹配值角度为中心，左右再取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；(3)重新比较步骤(2)中三个角度进行匹配时的匹配值，取最大者为中心，角度间距继续缩小一半，左右取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；(4)重复步骤(3)，直到角度间距达到指定的精度，进行匹配，获得最后的匹配角度、匹配位置及匹配值。本发明匹配时间更短、计算量更小。

Description

一种旋转图像的匹配方法

技术领域

本发明属于图形处理方法，尤其涉及一种旋转图像的匹配方法。

背景技术

随着科学技术的发展，图像匹配已成为图像信息处理领域中一项非常重要的技术。现在约40％的机器视觉应用中需要用到图像匹配技术，所涉及的应用领域从工业检测到导弹的地形匹配、光学和雷达的图像跟踪、工业流水线的自动监控、工业仪表的自动监控、资源分析、气象预报、医疗诊断、交通管理、文字识别以及图像检索等。图像匹配研究涉及到了图像采集、图像预处理、图像分割、特征提取等，并且与计算机视觉、多维信号处理和数值计算方法等紧密结合。它也是其它一些图像分析技术，如立体视觉、运动分析、数据融合等的基础：正因为其应用的广泛性，新的应用和新的要求逐步产生，使得匹配算法的研究逐步走向深入，出现了快速、稳定、鲁棒性好的匹配算法。因此，对现有匹配算法展开分析对于实际工程提高图像处理质量和识别精度具有非常重要的意义。

归一化互相关匹配算法通过计算模板和待匹配图像的灰度归一化互相关系数，即互相关值来确定匹配的程度。互相关法可以克服由于图像采集和系统误差带来的灰度畸变和几何畸变(平移变形和旋转)。

如PCB元件可能存在旋转，为了检测出旋转的角度，需要进行旋转的匹配。最简单的方法就是将在可能的旋转角度范围的所有角度依次代入到层叠二分算法中，求得最大匹配值的角度即实际元件的旋转角度。例如，假设旋转的范围在±15度之间，精确到1度，则将搜索窗口分别旋转-15、-14，直到15的31个角度应用匹配算法，取得最大匹配值的角度即元件的旋转角度。但这种方法随着匹配角度范围的增大，匹配时间也成倍增大，匹配时间太长，不适合应用于实际。

发明内容

针对现有技术存在的问题，本发明提供一种匹配时间更短、计算量更小的图像匹配方法。

为实现上述目的，本发明的技术方案为：一种旋转图像的匹配方法，包括以下步骤：

(1)确定输入角度搜索范围，以中间角度值及搜索范围的首末两个角度为搜索角度，旋转搜索窗口分别进行灰度归一化互相关匹配，获得各自匹配值；

(2)将角度间距缩小一倍定为新的角度搜索范围，以步骤(1)中取得的最大匹配值的角度为中心，左右再取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(3)重新比较步骤(2)中三个角度进行匹配时的匹配值，取最大者为中心，角度间距继续缩小一半，左右取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(4)重复步骤(3)，直到角度间距达到指定的精度，进行匹配，获得的最后的匹配角度、匹配位置及匹配值。

灰度归一化互相关匹配运用层叠二分互相关匹配方法，其包括以下步骤：

(1)将待匹配图像和模板图像在宽度和高度方向均缩小一倍；

(2)重复步骤(1)，直到匹配图像和模板图像达到指定的尺寸，在缩小的图像上使用灰度归一化互相关匹配获得最佳匹配位置(x，y)；

(3)返回到上一级缩小一倍的图像上在(2x-1～2x+1，2y-1～2y+1)范围内的9个搜索位置再进行进一步的匹配，获得新的最佳匹配位置(x，y)；

(4)重复步骤(3)，直到返回到第一级图像，即原图像，进行最后的匹配，获得的最佳匹配位置及匹配值。

上述旋转搜索窗口的方法进行灰度归一化互相关值的计算，首先计算第一个搜索位置的搜索窗口内所有像素的坐标，其它搜索位置的坐标通过第一个搜索位置的坐标平移得到。

旋转搜索窗口的相关值计算公式为：

$R(i,j)=\frac{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}(C(x^{\′}+i,y^{\′}+j)-\stackrel{\‾}{C}(i,j))(P(x,y)-\stackrel{\‾}{P})}{\sqrt{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(C(x^{\′}+i,y^{\′}+j)-\stackrel{\‾}{C}(i,j))}^2\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(P(x,y)-\stackrel{\‾}{P})}^2}}$

使用的旋转搜索窗口图像坐标系为原点在左上角，向右为x轴正方向，向下为y轴正方向，假设搜索窗口的尺寸为w*h像素大小，搜索窗口顺时针旋转θ时得到第一个搜索位置搜索窗口坐标，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}{x}^{\′}=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}+(h-1)*\sin \mathrm{\θ}\\ y^{\′}=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}\end{array}\right.$

搜索窗口逆时针旋转θ时的第一个搜索位置搜索窗口坐标，为使坐标值非负，再向上平移(w-1)*sinθ得到，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}{x}^{\′}=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}\\ y^{\′}=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}-(w-1)*\sin \mathrm{\θ}\end{array}\right..$

匹配过程中互相关值的计算采用增量方法进行计算，先计算出第一个搜索位置的灰度平均值，搜索窗口向右移动一个位置，新位置的灰度平均值的计算只需要在上一个平均值的基础上参考刚移入的一列和移出的一列，同理搜索窗口向下移动时，只需要参考刚移入的一行和刚移出的一行。

匹配过程中互相关值的计算采用增量方法进行计算，先计算出第一个搜索位置的灰度平均值，对于搜索窗口旋转的情况，当旋转角度为顺时针旋转时，向右移动一个像素时，最上一行和最右一列都新移入的，同时移出了最下一行及最左一列，新位置的灰度平均值的计算只需要在上一个平均值的基础上参考新移入的最上一行和最右一列；当旋转角度为逆时针旋转，向右移动一个像素时，只需参考新移入了最下一行和最右一列。

本发明相对于现有技术的优势：

本发明通过旋转搜索窗口的方法进行灰度归一化互相关值的计算，并结合运用层叠二分互相关匹配方法，大大减小了匹配的时间。

附图说明

图1是搜索角度和匹配值的关系曲线；

图2是层叠二分互相关匹配算法示意图；

图3是搜索窗口顺时针旋转时的坐标系变换示意图；

图4增量法计算搜索窗口平均灰度值示意图。

具体实施方式

本发明提供了一种图像匹配方法，如图3所示，其包括以下步骤：

(1)确定输入角度搜索范围，以中间角度值及搜索范围的首末两个角度为搜索角度，旋转搜索窗口分别进行灰度归一化互相关匹配，获得各自匹配值；

(2)将角度间距缩小一倍定为新的角度搜索范围，以步骤(1)中取得的最大匹配值的角度为中心，左右再取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(3)重新比较步骤(2)中三个角度进行匹配时的匹配值，取最大者为中心，角度间距继续缩小一半，左右取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(4)重复步骤(3)，直到角度间距达到指定的精度，进行匹配，获得的最后的匹配角度、匹配位置及匹配值。

灰度归一化互相关匹配运用层叠二分互相关匹配方法，如图2所示，其包括以下步骤：

(1)将待匹配图像和模板图像在宽度和高度方向均缩小一倍；

(2)重复步骤(1)，直到匹配图像和模板图像达到指定的尺寸，在缩小的图像上使用灰度归一化互相关匹配获得最佳匹配位置(x，y)；

(3)返回到上一级缩小一倍的图像上在(2x-1～2x+1，2y-1～2y+1)范围内的9个搜索位置再进行进一步的匹配，获得新的最佳匹配位置(x，y)；

(4)重复步骤(3)，直到返回到第一级图像，即原图像，进行最后的匹配，获得的最佳匹配位置及匹配值。

上述旋转搜索窗口的方法进行灰度归一化互相关值的计算，首先计算第一个搜索位置的搜索窗口内所有像素的坐标，其它搜索位置的坐标通过第一个搜索位置的坐标平移得到。

旋转搜索窗口的相关值计算公式为：

$R(i,j)=\frac{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}(C(x^{\′}+i,y^{\′}+j)-\stackrel{\‾}{C}(i,j))(P(x,y)-\stackrel{\‾}{P})}{\sqrt{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(C(x^{\′}+i,y^{\′}+j)-\stackrel{\‾}{C}(i,j))}^2\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(P(x,y)-\stackrel{\‾}{P})}^2}}$

使用的旋转搜索窗口图像坐标系为原点在左上角，向右为x轴正方向，向下为y轴正方向，假设搜索窗口的尺寸为w*h像素大小，搜索窗口顺时针旋转θ时得到第一个搜索位置搜索窗口坐标，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}{x}^{\′}=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}+(h-1)*\sin \mathrm{\θ}\\ y^{\′}=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}\end{array}\right.$

搜索窗口逆时针旋转θ时的第一个搜索位置搜索窗口坐标，为使坐标值非负，再向上平移(w-1)*sinθ得到，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}{x}^{\′}=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}\\ y^{\′}=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}-(w-1)*\sin \mathrm{\θ}\end{array}\right..$

由于模板图像是不变的，因此模板图像的平均灰度值P只需要计算一次，也只需要计算一次；其余部分每移动一个搜索位置都需要重新计算，但其中的搜索框窗口的图像的灰度平均值C(i，j)可以用增量法进行计算，减少计算时间。由于搜索过程是从左到右或从上到下一个一个像素移动搜索窗口的，因此可以这样简化计算搜索窗口图像的灰度平均值：先计算出第一个搜索位置的灰度平均值，搜索窗口向右移动一个位置，新位置的灰度平均值的计算只需要在上一个平均值的基础上考虑刚移入的一列和移出的一列，同理搜索窗口向下移动时，只需要考虑刚移入的一行和刚移出的一行。对于搜索窗口旋转的情况，当旋转角度为正时(顺时针旋转)，向右移动一个像素时，最上一行和最右一列都新移入的，同时移出了最下一行及最左一列；当旋转角度为负时(逆时针旋转)，向右移动一个像素时，新移入了最下一行和最右一列，同时移出了最上一行及最左一列，如图4所示。

例如，假设上一个搜索位置的平均值为C_pre，那么计算新移入的像素灰度之和为G_in，刚移出的像素灰度之和为G_out，搜索窗口的大小为m*n像素，则新位置搜索窗口的灰度平均值为：

${\stackrel{\‾}{C}}_{\mathrm{cur}}={\stackrel{\‾}{C}}_{\mathrm{pre}}+\frac{G_{\mathrm{in}}-G_{\mathrm{out}}}{m*n}.$

假设匹配对象实际旋转了6度，在待匹配图像中的位置为(30，31)，角度精度为1度，角度搜索范围为±12，则使用本发明进行匹配的实施方法如下：

(1)图1是各个搜索角度对应的最大互相关值，实际图像旋转了6度，搜索角度越接近6度互相关值越大。根据这一特性，本发明进行角度匹配的过程为：首先分别以-12、0和12度三个角度进行匹配，结果在0度时的匹配值最大；再以0为中心间距缩小一半，得到-6度和6度两个角度，分别以这两个角度进行匹配，并将得到的匹配值和0度时的匹配值比较，结果在6度时的匹配值最大；再以6度为中心，间距继续缩小一半，得到3度和9度，并分别以这两个角度进行匹配，将匹配值和6度时的匹配值比较，结果仍然在6度时的匹配值最大；如此不断进行下去最后是以6度为中心，间距为0.75，得到5.25度和6.75，比较三个角度的匹配值，最后在6度时的匹配值最大，此时三个角度的间距小于要求的1度精度，停止继续下去，匹配过程结束。角度匹配计算过程为0，-12，12，-6，6，3，9，4.5，7.5，5.25，6.75。最后的匹配结果为6度。

(2)在角度匹配过程中，每个角度的匹配值使用层叠二分互相关匹配求得，并同时返回最佳匹配位置，以0度的匹配过程为例进行说明，如图2所示。将待匹配图像和模板图像称为第一级图像，对一级图像进行连续两次缩小一半的操作，获得第二级和第三级图像，第三级图像的尺寸已经很小，对其使用传统灰度互相关匹配算法在整个搜索范围查找最佳匹配位置，假设是在位置(7，8)。然后返回到上一级图像，即第二级图像，则只需要在包括位置(2*7，2*8)在内及其周围的九个搜索位置进行进一步的精匹配，这九个位置为(13，15)，(14，15)，(15，15)，(13，16)，(14，16)，(15，16)，(13，17)，(14，17)，(15，17)。假设在位置(15，15)找到最大互相关值，则继续返回到上一级图像即第一级图像进行最后的精确匹配查找，同理也只需要在包括(2*15，2*15)在内及其周围的九个搜索位置进行查找，这九个位置为(29，29)，(30，29)，(31，29)，(29，30)，(30，30)，(31，30)，(29，31)，(30，31)，(31，31)。最后在(30，31)求得最大互相关值，这个位置即匹配位置，对应的互相关值即0度时的匹配值。

(3)第一个搜索位置的搜索窗口内的图像像素坐标和互相关值的计算根据式(5)、式(7)和式(8)计算，即通过旋转搜索窗口的方式进行计算，如图3所示。

(4)匹配过程下一个搜索位置搜索窗口内的图像像素坐标根据第一个搜索窗口的坐标平移得到，搜索窗口内的灰度平均值根据式(9)使用增量法计算，以最大限度减少计算互相关值的计算时间，如图4所示。

Claims (4)

1.一种旋转图像的匹配方法，其特征在于包括以下步骤：

(1)确定输入角度搜索范围，以中间角度值及搜索范围的首末两个角度为搜索角度，旋转搜索窗口分别进行灰度归一化互相关匹配，获得各自匹配值；

(2)将角度间距缩小一半定为新的角度搜索范围，以步骤(1)中取得的最大匹配值的角度为中心，左右再取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(3)重新比较步骤(2)中三个角度进行匹配时的匹配值，取最大者为中心，角度间距继续缩小一半，左右取两个角度，旋转搜索窗口进行灰度归一化互相关匹配；

(4)重复步骤(3)，直到角度间距达到指定的精度，获得最后的匹配角度、匹配位置及匹配值，匹配过程结束；

上述旋转搜索窗口进行灰度归一化互相关匹配中，进行灰度归一化互相关值的计算，首先计算第一个搜索位置的搜索窗口内所有像素的坐标，其它搜索位置的坐标通过第一个搜索位置的坐标平移得到；

旋转搜索窗口进行灰度归一化互相关匹配中进行灰度归一化互相关值的计算公式为：

$R(i,j)=\frac{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}(C(x\′+i,y\′+j)-\stackrel{\‾}{C}(i,j))(P(x,y)-\stackrel{\‾}{P})}{\sqrt{\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(C(x\′+i,y\′+j)-\stackrel{\‾}{C}(i,j))}^2\underset{x}{\mathrm{\Σ}}\underset{y}{\mathrm{\Σ}}{(P(x,y)-\stackrel{\‾}{P})}^2}}$

为搜索框窗口的图像的灰度平均值，

为模板图像的平均灰度值；

使用的旋转搜索窗口图像坐标系为原点在左上角，向右为x轴正方向，向下为y轴正方向，假设搜索窗口的尺寸为w*h像素大小，搜索窗口顺时针旋转θ时得到第一个搜索位置搜索窗口坐标，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}x\′=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}+(h-1)*\sin \mathrm{\θ}\\ y\′=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}\end{array}\right.$

搜索窗口逆时针旋转θ时的第一个搜索位置搜索窗口坐标，为使坐标值非负，再向上平移(w-1)*sinθ得到，搜索窗口顺时针旋转θ时的坐标变换公式为：

$\left\{\begin{array}{c}x\′=x*\cos \mathrm{\θ}-y*\sin \mathrm{\θ}\\ y\′=x*\sin \mathrm{\θ}+y*\cos \mathrm{\θ}-(w-1)*\sin \mathrm{\θ}\end{array}\right..$

2.根据权利要求1所述的旋转图像的匹配方法，其特征在于：灰度归一化互相关匹配运用层叠二分互相关匹配方法，其包括以下步骤：

(2.1)将待匹配图像和模板图像在宽度和高度方向均缩小一半，将待匹配图像和模板图像称为第一级图像；

(2.2)重复步骤(2.1)，直到待匹配图像和模板图像达到指定的尺寸，在缩小的图像上使用灰度归一化互相关匹配获得最佳匹配位置(x，y)；

(2.3)返回到上一级缩小一半的图像上在(2x-1～2x+1，2y-1～2y+1)范围内的9个搜索位置再进行进一步的匹配，获得新的最佳匹配位置(x，y)；

(2.4)重复步骤(2.3)，直到返回到第一级图像，进行最后的匹配，获得最后的最佳匹配位置及匹配值。

3.根据权得要求2所述的旋转图像的匹配方法，其特征在于：匹配过程中互相关值的计算采用增量方法进行计算，先计算出第一个搜索位置的灰度平均值，搜索窗口向右移动一个位置，新位置的灰度平均值的计算只需要在上一个平均值的基础上参考刚移入的一列和移出的一列，同理搜索窗口向下移动时，只需要参考刚移入的一行和刚移出的一行。

4.根据权得要求2所述的旋转图像的匹配方法，其特征在于：匹配过程中互相关值的计算采用增量方法进行计算，先计算出第一个搜索位置的灰度平均值，对于搜索窗口旋转的情况，当旋转角度为顺时针旋转时，向右移动一个像素时，新移入最上一行和最右一列，同时移出了最下一行及最左一列，新位置的灰度平均值的计算只需要在上一个平均值的基础上参考新移入的最上一行和最右一列；当旋转角度为逆时针旋转，向右移动一个像素时，只需参考新移入了最下一行和最右一列。

Images