一种基于多边形广义霍夫变换的图像匹配方法

摘要

本发明公开了一种基于多边形广义霍夫变换的图像匹配方法，该方法包括：(1)离线阶段：(1.1)对模板图像进行边缘提取和多边形拟合；(1.2)利用局部三角特征以及顶点与模板图像参考点的矢量关系，构建R-Table表；(2)在线阶段：(2.1)对目标图像进行边缘提取和多边形拟合；(2.2)对目标图像进行投票，票数最高的位置点作为与模板图像上的参考点对应的匹配点，以确定模板图像的多边形的顶点与目标图像的多边形的顶点的对应关系，同时确定模板图像与目标图像之间发生平移、旋转和缩放的参数。本方法能够在RFID制造装备以及LED制造装备中用于物体的实时定位，并且有很好的鲁棒性和精度。

说明书

技术领域

本发明属于图像处理技术领域，涉及一种基于多边形广义霍夫变换的图像匹配方法。

背景技术

IC封装产品向着集成化、小型化发展，要求IC电子封装设备具有高速度、高精度的定位的能力，从而能快速准确的实现芯片的拾取和放置。基于视觉的定位是一种常见的机器视觉方法，它经常被用来预计经过相似变换的物体的姿态。通常，这些物体在自动化生产设备中用相机来记录下来。它的精度和计算量将直接影响自动化生产设备的效率和性能。由于自动化生产技术的发展，高速视觉定位在高性能机器人和装备中有很大的需求，特别是IC封装和制造业。

广义霍夫变换在发生相似变换的物体检测以及定位上有广泛使用。然而，传统的广义霍夫变换有一个缺点，由于它采用了四维的投票参数空间导致时间复杂度很高，而且对内存的占用量也很大，其鲁棒性差，而且匹配精度也不高。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于多边形广义霍夫变换的图像匹配方法，其是一种对旋转和缩放不变，用于高精度和高速度的特点。

为实现上述目的，按照本发明，提供了一种基于多边形广义霍夫变换的图像匹配方法，其特征在于，该方法包括如下步骤：

(1)离线阶段，该步骤具体包括以下子步骤：

(1.1)对模板图像进行边缘提取，并基于边缘提取结果来执行多边形拟合，并且该模板图像上设有参考点，以用于在目标图像中找到与此参考点对应的匹配点，从而将模板图像与目标图像的对应关系转化为参考点与匹配点的对应关系；

(1.2)针对步骤(1.1)所拟合多边形，提取它的各个顶点及其邻近两顶点之间的局部三角特性，同时提取上述各个顶点与所述模板图像参考点之间的矢量关系，由此共同构建R-Table表也即局部三角矢量关系表；

(2)在线阶段，该步骤具体包括以下步骤：

(2.1)对目标图像同样进行边缘提取，并边缘提取结果来执行多边形拟合；

(2.2)利用目标图像的多边形的每个顶点与其邻近两顶点的局部三角特征，以及步骤(1.2)中构建的R-Table表对目标图像进行投票，票数最高的位置点作为与模板图像上的参考点对应的匹配点，以确定模板图像中的多边形与目标图像中的多边形的对应关系，同时确定模板图像与目标图像之间发生平移、旋转和缩放的参数。

优选地，所述步骤(1.1)具体过程如下：

采用Canny算子对模板图像进行边缘提取和采用优势点删除的多边形拟合算法进行多边形拟合，在模板图像I_T(x,y)中获得N_T个多边形；模板图像的第k个多边形的第i个顶点

其中k＝1,2,...,N_T，i＝1,2,...,是模板图像中第k个多边形的顶点的总个数，和分别是在X轴和Y轴上的坐标。

优选地，所述步骤(1.2)具体过程如下：

(1.2.1)以模板图像的中心，或者模板图像几何轮廓的重心为参考点P_ref，并且P_ref＝(_Tx_r,_Ty_r)，其中_Tx_r和_Ty_r分别是参考点P_ref在X轴和Y轴上的坐标；

表示从顶点到参考点P_ref的矢量，并且

(1.2.2)对于模板图像中的N_T个多边形中的每一个多边形执行以下操作：

获得矢量$L_T^k(i-1)=V_T^k\left(i\right)-V_T^k(i-1),L_T^k(i+1)=V_T^k\left(i\right)-V_T^k(i+1),$其中，和分别是第k个多边形的其中一个顶点和与其相邻的两顶点构成的矢量；

将矢量和中长度较小的矢量记作长度较大的矢量记作

获得和的夹角${\beta }_T^k\left(i\right)=\arccos \left(\frac{L_T^k\left(i_{\min }\right)·L_T^k\left(i_{\max }\right)}{\left|\right|L_T^k\left(i_{\min }\right)\left|\right|·\left|\right|L_T^k\left(i_{\max }\right)\left|\right|}\right),$其是一个对于旋转和缩放不变的局部特征；

获得主索引其中Δβ为的角度步长，Δβ,2Δβ,...,π，f_round(·)表示四舍五入取整函数；

获得二次索引以用于区分具有相同主索引β_index的三角形，其中，表示和的模的比即Δε表示的比率步长，${ϵ}_T^k\left(i\right)\in (0,\Delta ϵ,2\Delta ϵ,...,1);$

获得矢量与的夹角${\alpha }_T^k\left(i_{\min }\right)=\arccos \left(\frac{L_T^k\left(i_{\min }\right)·R_T^k\left(i\right)}{\left|\right|L_T^k\left(i_{\min }\right)\left|\right|·\left|\right|R_T^k\left(i\right)\left|\right|}\right);$

获得矢量与的夹角${\alpha }_T^k\left(i_{\max }\right)=\arccos \left(\frac{L_T^k\left(i_{\max }\right)·R_T^k\left(i\right)}{\left|\right|L_T^k\left(i_{\max }\right)\left|\right|·\left|\right|R_T^k\left(i\right)\left|\right|}\right);$

(1.2.3)利用局部三角特征以及多边形顶点与模板图像中的参考点的矢量关系，将所有与主索引角β_index和二次索引ε_index对应的储存作为R-Table表的内容，则获得 R-Table表。

优选地，所述步骤(2.2)具体过程如下：

(2.2.1)分别建立旋转角度矢量Γ_rot(φ_r)、缩放参数矢量Γ_scale(λ_r)和二维霍夫计数空间HCS_pos(x_r,y_r)；HCS_pos(x_r,y_r)用于确定模板图像I_T(x,y)相对于目标图像I_S(x,y)发生平移、旋转和缩放的参数；其中，x_r和y_r表示二维霍夫计数空间HCS_pos(x_r,y_r)中的点在X轴和Y轴上的坐标，并且二维霍夫计数空间HCS_pos(x_r,y_r)中的点与目标图像中的点一一对应；φ_r表示模板图像相对于目标图像的旋转角度；λ_r表示模板图像和目标图像之间的缩放参数；

在目标图像I_S(x,y)中通过拟合获得N_S个多边形，目标图像I_S(x,y)的第m个多边形的第j个顶点为其中m＝1,2,...,N_S，)，是目标图像中第m个多边形的顶点的总个数，和是在X轴和Y轴上的坐标；

(2.2.2)对于目标图像中中N_S个多边形中的每一个多边形执行以下操作：

获得$L_S^m(j-1)=V_S^m\left(j\right)-V_S^m(j-1),L_S^m(j+1)=V_S^m\left(j\right)-V_S^m(j+1),$其中和分别是目标图像的第m个多边形的其中一个顶点和与其相邻的两顶点构成的矢量；

将矢量和中长度较小的矢量记作长度较大的矢量记作

获得矢量和之间的夹角为

获得和的长度比

利用步骤(1.2)的R-Table表中的得到旋转角度后的矢量$l_S^m\left(j\right)=\left(\begin{array}{cc}cos\left({\alpha }_T^k\right(i_{\max }\left)\right)& sin\left({\alpha }_T^k\right(i_{\max }\left)\right)\\ -sin\left({\alpha }_T^k\right(i_{\max }\left)\right)& cos\left({\alpha }_T^k\right(i_{\max }\left)\right)\end{array}\right)\frac{L_S^m\left(j_{max}\right)}{\left|\right|L_S^m\left(j_{max}\right)\left|\right|};$

另外，通过$\left(\begin{array}{c}{{}_{S}x}_r\\ {{}_{S}y}_r\end{array}\right)={\lambda }_r·\left|\right|R_T^k\left(i\right)\left|\right|·l_S^m\left(j\right)+\left(\begin{array}{c}{{}_{T}x}_r\\ {{}_{T}y}_r\end{array}\right)$得到模板图像中的参考点(_Tx_r,_Ty_r)在二维霍夫计数空间HCS_pos(x_r,y_r)中的位置点，进而通过该位置点，得到目标图像上与参考点(_Tx_r,_Ty_r)对应的投票候选点的坐标(_Sx_r,_Sy_r)；其中，表示从顶点到投票候选点的参考矢量λ_r表示模板图像和目标图像之间的缩放参数，并且

获得模板图像和目标图像之间的旋转参数

(2.2.3)利用HCS_pos(_Sx_r+τ_x,_Sy_r+τ_y)＝HCS_pos(_Sx_r+τ_x,_Sy_r+τ_y)+W_pos(τ_x,τ_y)进行投票，其中W_pos(τ_x,τ_y)是投票候选点对应的位置权重，其采用了一个高斯核，并且其中，τ_x和τ_y为设定的长方形区域的长度和宽度，投票候选点位于长方形区域的中心；投票候选点的周边面积为τ_x×τ_y的长方形区域内的点会在二维霍夫计数空间HCS_pos(x_r,y_r)中被投票，投票候选点中得到票数最高的点即为与模板图像上的参考点对应的匹配点，匹配点的坐标为通过${\Gamma }_{scale}\left(f_{round}\right(\frac{{\lambda }_r}{\Delta \lambda }\left)\right)={\Gamma }_{scale}\left(f_{round}\right(\frac{{\lambda }_r}{\Delta \lambda }\left)\right)+W_{scale}$以及分别对φ_r和λ_r进行投票，分别得到票数最高的值，即为匹配点的旋转角度和缩放参数最后得到匹配点的平移、旋转和缩放参数其中，Δλ和Δφ分别是设定的投票候选点的缩放和旋转的投票步长，W_scale和W_rot分别是设定的投票候选点的缩放权重和旋转权重。

优选地，所述步骤(2.2.3)在缩放参数下通过最小平方拟合法来获得位置参数和旋转角度，具体过程如下：

模板图像和目标图像的相似度在的3×3×3的三维空间邻 域中计算，通过最小二乘法来获得二次曲线的参数进行拟合，其中二次曲线的表达式为f(x,y,φ)＝a₀+a₁x+a₂y+a₃φ+a₄x²+a₅xy+a₆xφ+a₇y²+a₈yφ+a₉φ²，得到邻域中f(x,y,φ)的最大值，进而在缩放参数λ_r下得到拟合后的坐标和旋转角度

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：利用物体轮廓信息和梯度方向的统计信息，可快速进行角度定位，提高了匹配速度，匹配准确度高，能够在RFID制造装备以及LED制造装备中用于物体的实时定位，并且有很好的鲁棒性和精度。

附图说明

图1(a)～图1(d)是本发明的多边形广义霍夫变换算法的离线过程，其中图1(a)为模板图像，图1(b)为边缘提取后的图像，图1(c)为多边形拟合后的图像，图1(d)为局部三角特征关系图；

图2(a)～图2(d)是本发明的多边形广义霍夫变换算法的在线过程，其中图2(a)为模板图像，图2(b)为边缘提取后的图像，图2(c)为多边形拟合后的图像，图2(d)为点投票过程及局部三角特征关系图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

本发明提出了一种缩放旋转不变性的多边形广义霍夫变换算法，是一种对旋转和缩放不变，用于高精度和高速度的目标定位算法。

在本实施例中，图像可以表示为行列方向的二维数组，每个数组元素的值代表该点的像素灰度值，以图像左上角为图像坐标的原点，垂直向下 方向为Y正方向，同时也为行数标号递增方向，代表了图像的高度方向，水平向右方向为X正方向，同时也为列数标号递增方向，代表了图像的宽度方向。

本发明的匹配方法分为离线过程和在线过程。以下对本发明提出的匹配方法作详细说明。具体步骤如下：

(1)离线阶段，该步骤具体包括以下子步骤：

(1.1)对模板图像进行边缘提取，并基于边缘提取结果来执行多边形拟合，并且该模板图像上设有参考点，以用于在目标图像中找到与此参考点对应的匹配点，从而将模板图像与目标图像的对应关系转化为参考点与匹配点的对应关系；

(1.2)针对步骤(1.1)所拟合多边形，提取它的各个顶点及其邻近两顶点之间的局部三角特性，同时提取上述各个顶点与所述模板图像参考点之间的矢量关系，由此共同构建R-Table表也即局部三角矢量关系表；

步骤(1.1)对模板图像进行边缘提取和多边形拟合的具体过程如下：

采用Canny算子对模板图像进行边缘提取和采用优势点删除的多边形拟合算法进行多边形拟合，在模板图像I_T(x,y)中获得N_T个多边形；模板图像的第k个多边形的第i个顶点

其中k＝1,2,...,N_T，是模板图像中第k个多边形的顶点的总个数，和分别是在X轴和Y轴上的坐标。

步骤(1.2)构建局部三角矢量关系表R-Table表的具体过程如下：

利用模板图像中的所有多边形顶点建立缩放和旋转不变的局部特征，同一个边缘曲线上三个相邻的多边形顶点可以被当做一个局部三角形的三个顶点。因此，第k个几何多边形的三角形的集合被用来作为模板图像经过相似变换后的局部不变特征，如图1所示，这个局部三角不变特征避免了使用梯度方向作为索引，具有更好的鲁棒性。

以模板图像的中心，或者模板图像几何轮廓的重心为参考点P_ref，并且P_ref＝(_Tx_r,_Ty_r)，其中_Tx_r和_Ty_r分别是参考点P_ref在X轴和Y轴上的坐标；表示从顶点到参考点P_ref的矢量，并且

对于模板图像中的N_T个多边形中的每一个多边形执行以下操作：获得矢量$L_T^k(i-1)=V_T^k\left(i\right)-V_T^k(i-1),L_T^k(i+1)=V_T^k\left(i\right)-V_T^k(i+1),$其中，分别是第k个多边形的其中一个顶点和与其相邻的两顶点构成的矢量；将矢量和中长度较小的矢量记作长度较大的矢量记作获得和的夹角其是一个对于旋转和缩放不变的局部特征；获得主索引其中Δβ为的角度步长，Δβ,2Δβ,...,π，f_round(·)表示四舍五入取整函数；获得二次索引以用于区分具有相同主索引β_index的三角形，其中，表示和的模的比即Δε表示的比率步长，获得矢量与的夹角获得矢量与的夹角${\alpha }_T^k\left(i_{\max }\right)=\arccos \left(\frac{L_T^k\left(i_{\max }\right)·R_T^k\left(i\right)}{\left|\right|L_T^k\left(i_{\max }\right)\left|\right|·\left|\right|R_T^k\left(i\right)\left|\right|}\right);$

利用局部三角特征以及多边形顶点与模板图像中的参考点的矢量关系，将所有与主索引角β_index和二次索引ε_index对应的储存作为R-Table表的内容，则获得R-Table表，见表1所示。

表1R-Table表

(2)在线阶段，该步骤具体包括以下步骤：

(2.1)对目标图像同样进行边缘提取，并边缘提取结果来执行多边形拟合；

(2.2)利用目标图像的多边形的每个顶点与其邻近两顶点的局部三角特征，以及步骤(1.2)中构建的R-Table表对目标图像进行投票，票数最高的位置点作为与模板图像上的参考点对应的匹配点，以确定模板图像中的多边形与目标图像中的多边形的对应关系，同时确定模板图像与目标图像之间发生平移、旋转和缩放的参数。

分别建立旋转角度矢量Γ_rot(φ_r)、缩放参数矢量Γ_scale(λ_r)和二维霍夫计数空间HCS_pos(x_r,y_r)；HCS_pos(x_r,y_r)用于确定模板图像I_T(x,y)相对于目标图像I_S(x,y)发生平移、旋转和缩放的参数；其中，x_r和y_r表示二维霍夫计数空间HCS_pos(x_r,y_r)中的点在X轴和Y轴上的坐标，并且二维霍夫计数空间HCS_pos(x_r,y_r)中的点与目标图像中的点一一对应；φ_r表示模板图像相对于目 标图像的旋转角度；λ_r表示模板图像和目标图像之间的缩放参数。

如图2所示，在目标图像I_S(x,y)中通过拟合获得N_S个多边形，目标图像I_S(x,y)的第m个多边形的第j个顶点为其中m＝1,2,...,N_S，是目标图像中第m个多边形的顶点的总个数，和是在X轴和Y轴上的坐标。

对于目标图像中中N_S个多边形中的每一个多边形执行以下操作：获得$L_S^m(j-1)=V_S^m\left(j\right)-V_S^m(j-1),L_S^m(j+1)=V_S^m\left(j\right)-V_S^m(j+1),$其中和分别是目标图像的第m个多边形的其中一个顶点和与其相邻的两顶点构成的矢量；将矢量中长度较小的矢量记作长度较大的矢量记作获得矢量和之间的夹角为获得和的长度比${ϵ}_S^m\left(j\right)=\frac{\left|\right|L_S^m\left(j_{min}\right)\left|\right|}{\left|\right|L_S^m\left(j_{\max }\right)\left|\right|};$

利用步骤(1.2)的R-Table表；由于表中对应同一主索引角β_index和二次索引ε_index储存是一组以上的值，不同组值分别进行下述计算得到旋转角度后的矢量$l_S^m\left(j\right)=\left(\begin{array}{cc}cos\left({\alpha }_T^k\right(i_{\max }\left)\right)& sin\left({\alpha }_T^k\right(i_{\max }\left)\right)\\ -sin\left({\alpha }_T^k\right(i_{\max }\left)\right)& cos\left({\alpha }_T^k\right(i_{\max }\left)\right)\end{array}\right)\frac{L_S^m\left(j_{max}\right)}{\left|\right|L_S^m\left(j_{max}\right)\left|\right|},$则也是一组以上的值，这会使后续的多边形的每个顶点在进行投票时，会产生一组以上的投票候选点。

另外，通过$\left(\begin{array}{c}{{}_{S}x}_r\\ {{}_{S}y}_r\end{array}\right)={\lambda }_r·\left|\right|R_T^k\left(i\right)\left|\right|·l_S^m\left(j\right)+\left(\begin{array}{c}{{}_{T}x}_r\\ {{}_{T}y}_r\end{array}\right)$得到模板图像中的参考点(_Tx_r,_Ty_r)在二维霍夫计数空间HCS_pos(x_r,y_r)中的位置点，进而通过该位置点，得到目标图像上与参考点(_Tx_r,_Ty_r)对应的投票候选点的坐标(_Sx_r,_Sy_r)；其中，表示从顶点到投票候选点的参考矢量λ_r表示模板图像和目标图像之间的缩放参数，并且获得 模板图像和目标图像之间的旋转参数

由于每一个多边形顶点通过上述计算，可获得一组以上的投票候选参数

(_Sx_r,_Sy_r,λ_r,φ_r)。利用HCS_pos(_Sx_r+τ_x,_Sy_r+τ_y)＝HCS_pos(_Sx_r+τ_x,_Sy_r+τ_y)+W_pos(τ_x,τ_y)进行投票，其中W_pos(τ_x,τ_y)是投票候选点对应的位置权重，其采用了一个高斯核，并且其中，τ_x和τ_y为设定的长方形区域的长度和宽度，投票候选点位于长方形区域的中心；投票候选点的周边面积为τ_x×τ_y的长方形区域内的点会在二维霍夫计数空间HCS_pos(x_r,y_r)中被投票，投票候选点中得到票数最高的点即为与模板图像上的参考点对应的匹配点，匹配点的坐标为通过${\Gamma }_{scale}\left(f_{round}\right(\frac{{\lambda }_r}{\Delta \lambda }\left)\right)={\Gamma }_{scale}\left(f_{round}\right(\frac{{\lambda }_r}{\Delta \lambda }\left)\right)+W_{scale}$以及分别对φ_r和λ_r进行投票，分别得到票数最高的值，即为匹配点的旋转角度和缩放参数最后得到匹配点的平移、旋转和缩放参数其中，Δλ和Δφ分别是设定的投票候选点的缩放和旋转的投票步长，W_scale和W_rot分别是设定的投票候选点的缩放权重和旋转权重，此处每个投票候选点W_scaleandW_rot都设置为1。

为了找到更精确的亚像素坐标位置和旋转缩放参数，先在特定缩放参数下，通过最小平方拟合法来获得高精度的位置和旋转参数。模板图像和目标图像的相似度在的3×3×3的三维空间邻域中计算，通过最小二乘法来获得二次曲线的参数进行拟合，其中二次曲线的表达式为f(x,y,φ)＝a₀+a₁x+a₂y+a₃φ+a₄x²+a₅xy+a₆xφ+a₇y²+a₈yφ+a₉φ²，得到邻域中f(x,y,φ)的最大值，进而在缩放参数λ_r下得到拟合后的坐标和旋转角度

通过本发明所提出的方法，为了寻找发生了旋转和缩放的目标的位置，提出了一个对于高速视觉定位的基于局部几何三角特征的多边形广义霍夫变换算法，提出的多边形广义霍夫变换算法采用从边缘中提取的局部三角特征作为R-Table表的索引，然而传统的广义霍夫变换算法采用梯度方向作为R-Table表的索引。这样相对于广义霍夫变换的四维空间，多边形广义霍夫变换的参数空间只有两个维度。多边形-广义霍夫变换是具有旋转和缩放不变的所以计算时间要远小于广义霍夫变换算法，对于实际中高速视觉定位能够适用。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。