基于局部不变几何特征的广义霍夫变换图像匹配方法

摘要

本发明公开了一种基于局部不变几何特征的广义霍夫变换图像匹配方法，用于实现对具有任意旋转角度的目标图像的匹配，其特征在于，该方法包括对模板图像进行预处理的步骤和利用该模板图像的处理结果对目标图像进行匹配的步骤，其中，模板图像处理步骤中包括提取图像各边缘点并建立边缘点匹配特征关系，所述目标图像进行匹配时先提取目标图像的各边缘点，再利用上述建立的边缘点匹配特征关系对提取的图像进行匹配，从而获得匹配位置点和相应的旋转角度，完成目标图像匹配。本发明的方法通过改进传统的广义霍夫变换，建立改进的参考表，能够对任意角度旋转的目标图像进行匹配，具有很高的匹配速度和匹配精度。

说明书

技术领域

本发明属于机器视觉技术领域，更具体地，涉及一种图像匹配方 法。

背景技术

在集成电路（IC）制造业中，高速度、高精度的进行拾取、放置 芯片是影响生产效率的关键操作。而拾取、放置芯片又依赖于高速度、 高精度的对芯片进行定位。随着机器视觉技术的快速发展，其在目标 定位中表现出极佳的优越性，因此机器视觉技术在IC制造业得到非 常广泛应用。应用于芯片定位的机器视觉系统主要由光源，相机，图 像匹配模块组成。调节光源至合适亮度，通过相机采集芯片图像，图 像采集板卡将图像传输至工控机，通过图像匹配算法计算出芯片位置 及旋转角度，将位置及旋转角度传送给电机，电机控制机械手对芯片 进行拾取。现代IC制造工艺要求芯片定位精度达到um甚至nm级别， 速度达到10ms内。在整个机器视觉系统中，图像匹配技术是机器视 觉系统的核心，是实现高速度、高精度芯片定位的关键。在实际的生 产过程中，常常出现模板图像与目标图像存在旋转的情况，由于旋转 的存在，使得图像匹配算法变的更加复杂。

为了能够对任意旋转角度进行匹配，目前广泛采用广义霍夫变换 图像匹配。广义霍夫变换是由霍夫变换发展而来以实现对任意形状进 行定位的算法。因其对噪声、遮挡、光照变化具有较强的鲁棒性，广 义霍夫变换得到国内外学者的广泛研究。然而，当目标存在旋转时， 传统的广义霍夫变换具有巨大的内存需求和很高的计算复杂度，这些 缺点都严重制约其实现高速度、高精度的实现图像匹配。

针对广义霍夫变换存在的缺点，目前出现了一些改进的方法。如 为降低广义霍夫变换的内存需求，Lee等在文献“Generalized Hough  transform in object recognition”（Pattern Recognition,1992.Vol.III. Conference C:Image,Speech and Signal Analysis,Proceedings.,11th  IAPR International Conference on.IEEE,1992:285-289.）中提出将图像 参考点限定到图像的边缘上。虽然Lee的方法可以极大的降低广义霍 夫变换的内存需求，但当目标图像存在遮挡，残缺时，参考点的选择 将极大影响匹配结果，从而降低了算法的鲁棒性。

为降低广义霍夫变换的累加器的大小，并加速匹配过程，Ulrich  M等在文献“Real-time object recognition using a modified  generalized Hough transform”（Pattern Recognition,2003,36(11): 2557-2570.）中提出采用分层的策略来进行匹配。其首先分别对模板 图像和目标图像建立图像金字塔，图像匹配从金字塔顶层开始进行。 由于在金字塔的顶层的分辨率很低，很快可以得到粗略的位置和旋转 角度。在顶层得到粗略的位置和旋转角度后，在下一层的匹配过程中， 位置搜索范围将限制在粗略位置周围，角度搜索范围也限制在粗略旋 转角度周围。基于这种分层策略，匹配结果从粗到精，也提高了匹配 的速度。虽然Ulrich改善了广义霍夫变换的性能，但在其匹配过程中， 采用的特征依旧是边缘点的梯度方向，即其依然是基于传统的广义霍 夫变换。

Tsai等在文献“An improved generalized Hough transform for the  recognition of overlapping objects”（Image and Vision computing, 1997,15(12):877-888.）中提出使用最小二乘来进行圆拟合来计算边 缘点的曲率半径，并以此为特征。虽然边缘处的曲率半径是旋转不变 的，但用最小二乘圆拟合来计算边缘点的曲率半径，不仅会增加每个 边缘点处的计算量，而且匹配结果依赖于曲率半径的估计精度。特别 是，当模板图像和目标图像的边缘主要是直线时，此算法就会失效。

Aguado等在文献“Invariant characterization of the Hough  transform for pose estimation of arbitrary shapes”（Pattern Recognition, 2002,35(5):1083-1097）中提出以两个边缘点处的切线夹角为特征来 改进广义霍夫变换。对于任意边缘点，将边缘点的梯度方向向量逆时 针旋转固定角度，沿着由边缘点和梯度方向向量旋转后的方向定义的 直线上找到第二个边缘点。然而当梯度算子存在小误差时，或在目标 图像上存在多目标时，第二个边缘点将会找错，这将严重影响算法的 精度。

发明内容

针对传统广义霍夫变换存在的缺陷，本发明旨在提供一种高精度、 高速度，并且能够对任意旋转角度的目标进行匹配的基于局部不变几 何特征的广义霍夫变换图像匹配方法，可以实现对具有任意旋转角度 图像的精确匹配。

实现本发明目的所采用的具体技术方案如下。

一种图像匹配方法，用于实现对具有任意旋转角度的目标图像的 匹配，其特征在于，该方法包括对模板图像进行预处理的步骤和利用 该模板图像的处理结果对目标图像进行匹配的步骤，其中，

所述模板图像处理步骤中包括提取图像各边缘点并建立边缘点 匹配特征关系，所述目标图像进行匹配时先提取目标图像的各边缘点， 再利用上述建立的边缘点匹配特征关系对提取的图像进行边缘点匹 配，从而获得匹配位置点和相应的旋转角度，完成目标图像匹配。

作为本发明的进一步优选，所述图像匹配特征关系包括位置匹配 关系和旋转角度匹配关系，其中：

所述位置匹配关系指图像边缘点到边缘点中心的距离以及边缘 点的梯度方向与边缘点到边缘点中心连线的夹角，其与两边缘点的梯 度方向夹角所形成的第一对应关系；所述旋转角度匹配关系指边缘点 的梯度方向与边缘点到边缘点中心连线的夹角与边缘点的梯度角之 间形成的第二对应关系。

作为本发明的进一步优选，所述第一对应关系通过一索引表表示， 其中，两边缘点的梯度方向夹角散列后作为索引值，该梯度方向夹角 所对应的边缘点到边缘点中心的距离，以及边缘点的梯度方向与边缘 点到边缘点中心连线的夹角两者组合作为索引内容，从而建立彼此对 应的索引表。

作为本发明的进一步优选，所述两边缘点的梯度方向夹角通过如 下散列函数进行散列：其中0<S_β≤1，β_i为两边缘点的 梯度方向夹角，β为散列后的索引值，其中floor()表示对结果进行向 下取整。

作为本发明的进一步优选，所述第二对应关系通过一索引表表示， 其中，边缘点的梯度方向与边缘点到边缘点中心连线的夹角散列后作 为索引值，对应的边缘点的梯度角为索引内容，从而建立彼此对应的 索引表。

作为本发明的进一步优选，所述边缘点的梯度方向与边缘点到边 缘点中心连线的夹角通过如下散列函数进行散列：其中 为边缘点的梯度方向与边缘点到边缘点中心点连线的夹角， 为散列后的索引值，floor()表示对结果进行向下取整。

作为本发明的进一步优选，所述目标图像的匹配中，根据目标图 像的各边缘点的梯度方向夹角利用所述第一对应关系获得图像的匹 配位置，根据目标图像的边缘点的梯度方向与边缘点到边缘点中心点 连线的夹角获得图像的旋转角度。

作为本发明的进一步优选，所述匹配位置为各边缘点对应的可能 匹配位置(x_io,y_io)中出现最多次数的匹配位置点，所述旋转角度为边缘 点中可能旋转角度φ_in中出现最多次数的旋转角度。

作为本发明的进一步优选，所述可能的匹配位置(x_io,y_io)通过如下 公式得到：

${\overrightarrow{r}}_i=(r_{\mathrm{ix}},r_{\mathrm{iy}})$

$x_{\mathrm{io}}=x_i+\frac{d_n{r}_{\mathrm{ix}}}{\overrightarrow{\left|r_i\right|}}$

$y_{\mathrm{io}}=y_i+\frac{d_n{r}_{\mathrm{iy}}}{\overrightarrow{\left|r_i\right|}}$

其中，P_i为任一边缘点，G_ix和G_iy分别是P_i在x方向和y方向上的 梯度，(x_i,y_i)为P_i的坐标，为P_i到可能的匹配位置的方向向量， d_n为模板图像中梯度方向夹角所对应的第一个边缘点到边缘点中心 的距离，为模板图像中第一个边缘点的梯度方向与边缘点到边缘点 中心连线的夹角，为P_i与第二边缘点P_j夹角β_i对应索引值的索 引内容，n＝1,2,3,…。由于在图像不同边缘点处存在相等的夹角β_i，所 以通常对于一个索引值有多个索引内容。

作为本发明的进一步优选，所述可能旋转角度φ_in通过如下公式确 定：φ_in＝θ_i-θ_n，其中，θ_i为目标图像边缘点P_i的梯度角，θ_n为模板图 像边缘点的梯度角，θ_n为对应索引值的索引内容，n＝1,2,3,…，为 边缘点P_i的梯度方向与边缘点到匹配位置点连线的夹角。由于在图像 不同边缘点处存在相等的夹角所以通常对于一个索引值有多个索 引内容。

本发明中，可以将该方法归纳为两个阶段：离线阶段和在线阶段。 在离线阶段，对模板图像进行预处理，包括：A1).对模板图像提取边 缘；A2).以局部不变几何特征建立MR-Table，用以求匹配位置；A3). 建立AR-Table，用以求目标旋转角度。在在线阶段，根据离线阶段 所建立的MR-Table和AR-Table，对目标图像进行匹配，包括：B1). 初始化二维累加器用以累计可能匹配位置处的投票数，初始化一维累 加器用以累计可能的旋转角度；B2).对目标图像提取边缘；B3).对于 目标图像边缘上的每个边缘点，计算局部不变几何特征，并以此索引 在A2)中建立的MR-Table，对可能的匹配位置投票，累加器在相应的 位置加一；B4).根据累加器求得匹配位置；B5)根据在A3)中建立的 AR-Table和B4）求得的匹配位置，对可能的旋转角度投票，对应的 累加器在相应的角度加一；B6)根据累加器求得旋转角度；B7).采用 最小二乘拟合将匹配精度提高到亚像素级别。

同时，为加快匹配速度，基于分层策略的图像金字塔也被应用于 此方法中。

总体而言，本发明的方法相对于现有技术，具体如下技术效果：

（1）本发明中通过在局部区域寻找两个边缘点，以两个边缘点 的梯度方向夹角为几何特征，此夹角是旋转不变的，从而使得累加器 从三维变成二维，降低了内存需求。

（2）本发明中采用的几何特征是局部的，使得当图像存在遮挡 时，即使有部分边缘是缺失的，此方法依然能够有较好的适应性。因 此，本方法对遮挡图像具有较好的鲁棒性。

（3）本发明通过改进传统的广义霍夫变换，建立改进的参考表 (MR-Table)，通过运用MR-Table来投票目标位置。由于在MR-Table 中使用的索引是旋转不变的，能够对任意角度旋转的目标图像具有较 好的适应性。因此无需像传统广义霍夫变换遍历所有可能的旋转角度 来求得索引，因此极大的减少了运算时间，同时通过采用采用分层策 略，进一步提高了匹配的速度。得到像素级位置后，本发明采用三元 二次多项式对匹配位置邻域进行亚像素拟合，从而将匹配精度提高至 亚像素级别。

附图说明

图1为本发明实施例的方法的离线阶段模板图像建立索引表 MR-Table和AR-Table示意图。

图2为本发明实施例的方法的在线阶段目标图像根据索引表 MR-Table和AR-Table投票出位置和旋转角度示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合 附图，对本发明进行进一步详细说明。此处说明若涉及到具体实例时 仅仅用以解释本发明，并不限定本发明。

本实施例中的基于局部不变几何特征的广义霍夫变换图像匹配 方法分为离线阶段和在线阶段两个部分。

在离线阶段，首先对模板进行预处理。具体步骤如下：

A1).对模板图像进行边缘提取，得到模板图像的边缘点 P_i(i＝1,2,3.N.，)其中N为模板图像边缘点的个数，并根据得到的边缘 点获得模板图像边缘点中心P_r。

对图像进行边缘提取有多种成熟的方法，本实施例中优选采用 Canny算子，但并不限于此方法。

根据提取出的图像边缘即可以得到边缘点中心，即所有边缘点的 中心点，具体是将所有边缘点的坐标累加除以边缘点个数得到的坐标 即为中心坐标。

A2).对于模板图像边缘上的每个边缘点P_i（第一个边缘点），在 其局部范围（也可以称为邻域）的边界上找到另外一个边缘点P_j（第 二个边缘点），求得两个边缘点的梯度方向夹角β_i，此夹角本发明中 称为旋转不变的局部几何特征，再以此夹角计算出索引，并根据计算 出的索引建立改进的参考表（MR-Table,Modified Reference Table）。

本实施例中具体方法为沿着第一个边缘点P_i的梯度方向，以固定 半径为模的向量逆时针旋转，与模板边缘的第一个交点为第二个边缘 点P_j（见附图1）。求得两个边缘点的梯度方向夹角β_i，此夹角是旋 转不变的局部几何特征。半径的选择可以根据实际需要具体确定。

由于β_i的范围0～180，将夹角范围以步长为S_β(0<S_β≤1)离散化， 对应的索引值范围0～M_β,（其中floor()表示对结果进 行向下取整)，则以为索引（即将β_i以散列函数本实施例 中优选为进行散列，得到的散列值作为索引值），以P_i的梯 度方向与的夹角和长度为被索引内容，建立 MR-Table(见表1)。由于在图像不同边缘点处存在相等的夹角β_i，所 以通常对于一个索引有多个索引内容。

表1.MR-Table

A3).对于模板图像上的任意边缘点P_i，计算出P_i的梯度方向与 的夹角通过计算出索引，以P_i的梯度角θ_i为被索引内容建立 角度参考表（AR-Table，Angle Reference Table）(见表2)。

由于角度的范围0～180，将此范围以步长为离散化，对 应的索引值范围0～M,（floor()表示对结果进行向下取 整),则以为索引（即将以散列函数本实施例中优选为 进行散列，得到的散列值作为索引值），以P_i的梯度角θ_i为 被索引内容，建立AR-Table(见表2)。由于在图像不同边缘点处存在 相等的夹角所以通常对于一个索引有多个索引内容。

表2.AR-Table

在在线阶段，开始在目标图像上进行目标定位。

B1).初始化一个二维累加器Acc_loc，用以累计可能的匹配位置的 投票数，其大小为目标图像大小，即所有可能的匹配位置。同时，初 始化一个一维累加器Acc_rot，用以累计可能的旋转角度的投票数， 其大小为360，即目标所有可能的旋转角度。

B2).对目标图像运用Canny算子进行边缘提取。

B3).得到目标边缘图像后，对于目标边缘图像的每个边缘点的局 部找到第二个边缘点，计算两个边缘点的梯度夹角，计算出索引后， 根据在离线阶段建立的MR-Table中索引对应的索引内容计算可能的 匹配位置。

具体方法为对于目标边缘图像上的每个边缘点P_i，在以其为中心 的圆上找第二个边缘点P_j（具体方法见A2）），计算处的梯度方向 夹角β_i。以索引在离线阶段建立的MR-Table对应的索引 内容按以下方程计算可能的匹配位置(x_io,y_io)（见附 图2）：

${\overrightarrow{r}}_i=(r_{\mathrm{ix}},r_{\mathrm{iy}})$

$x_{\mathrm{io}}=x_i+\frac{d_n{r}_{\mathrm{ix}}}{\overrightarrow{\left|r_i\right|}}$

$y_{\mathrm{io}}=y_i+\frac{d_n{r}_{\mathrm{iy}}}{\overrightarrow{\left|r_i\right|}}$

其中G_ix，G_iy分别是P_i在x方向和y方向上的梯度。(x_i,y_i)为P_i的坐 标。

在(x_io,y_io)处投票一次，在该点处得到一票，即二维累加器Acc_loc 在(x_io,y_io)累加一次：Acc_loc(x_io,y_io)=Acc_loc(x_io,y_io)+1。

B4).当目标图像中的所有边缘点都经过B3)中的处理后，求得 Acc_loc取得最大值的坐标(x_o,y_o)即为匹配位置P_o。

B5).在B4)中得到匹配位置后，对目标边缘图像上的每个边缘点 P_i，计算边缘点梯度方向与的夹角，计算出对应索引，根据在离 线建立的AR-Table中索引相应的索引内容计算可能的旋转角度。

具体方法为对于目标图像边缘上的每个边缘点P_i，计算P_i的梯度 方向与的夹角以来索引AR-Table中对应的索引内 容θ_n(n＝1,2,3...),可能的旋转角度为：

φ_in＝θ_i-θ_n,(n＝1,2,3...)

其中，θ_i为P_i的梯度角。则在φ_in投一票，一维累加器Acc_rot在φ_in累加一次：

Acc_rot(φ_in)=Acc_rot(φ_in)+1

B6).当目标图像中的所有边缘点都经过B5)中的处理后，求得 Acc_rot取得最大值的角度φ_o即为旋转角度。

B7).在B4)和B6)得到的匹配位置和旋转角度的3×3×3邻域，通过 最小二乘拟合三元二次多项式，将匹配结果精确到亚像素级别。

为提高图像匹配速度，分层策略也可用到本匹配方法中来。设模 板图像尺寸为mw×mh，目标图像尺寸为w×h。

在离线阶段，为模板图像建立m层模板图像金字塔，各层模板 金字塔图像尺寸为mw(i)×mh(i)。

其中i＝1,2,...,m,mw(i)=2mw(i+1),mh(i)=2mh(i+1),mw(1)=mw,mh(1)=mh。

对于每一层金字塔图像，分别根据步骤A1)～A2)建立MR-Table(i)， 其中i＝1,2,...,m，并在底层（即第1层）金字塔图像上根据步骤A3) 建立AR-Table。

在在线阶段，为目标图像也建立m层目标图像金字塔，各层目 标金字塔图像尺寸为w(i)×h(i),

其中i＝1,2,...,m,w(i)=2w(i+1),h(i)=2h(i+1),w(1)=w,h(1)=h。

匹配从顶层（即第m层）目标金字塔图像开始，由于第m层目 标金字塔图像的分辨率低，累加器的尺寸小，边缘点数少，搜索范围 小，通过步骤B1)～B4)，很快可以得到在m层的粗略匹配位置(x_m,y_m)。 在m-1层，以(2x_m,2y_m)为中心，在S_m-1×S_m-1的范围内通过步骤B1)～B4) 进行匹配。

其中$S_{m-1}=\sqrt{\mathrm{mw}(m-1)·\mathrm{mw}(m-1)+\mathrm{mh}(m-1)·\mathrm{mh}(m-1)}.$

S_m-1×S_m-1将远小于w(m-1)×h(m-1)。经过图像金字塔的分层策略， 从第m层开始匹配，一直到第1层，整个过程图像匹配位置是从粗 到精的，并且采用分层策略可以减少匹配的搜索范围，从而减少计算 量，加快匹配过程。当匹配进行到第1层时，将得到最精确的位置， 然后，通过步骤B5)～B6)得到匹配旋转角度。

本发明的基于局部不变的几何特征的改进广义霍夫变换图像匹 配方法中，由于采用的特征（每个边缘点和其邻域的另一个边缘点梯 度方向的夹角）是旋转不变的，因此将参数空间从3维降到2维，不 仅降低了内存需求，而且加快了匹配速度。本方法采用分层策略进行 进一步的加速，并且采用最小二乘拟合将匹配结果更加精确。因此， 本发明的方法匹配精度高、速度快，并且可以对任意旋转角度进行匹 配。

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