面向圆形标志符的两级优化霍夫变换快速检测定位方法

摘要

本发明提供了一种面向圆形标志符的两级优化霍夫变换快速检测定位方法，首先对基准点进行霍夫变换，然后通过一级优化霍夫变换减少图像空间参与平移霍夫变换的点数和参数空间的无效累加，快速确定圆形标志符圆心所在的区域，最终通过二级优化霍夫变换高效控制参数空间累加范围，快速确定圆形标志符的圆心位置。本发明能够准确定位圆形标志符区域，快速精确计算出圆形标志符的圆心坐标，时间开销大大优于平移霍夫变换，具有快速、准确和鲁棒的特点。

说明书

技术领域

本发明涉及一种基于机器视觉的图像检测定位技术，尤其是面向圆形标志符的、 能够满足工业生产实时需求的高精度快速检测定位技术。

背景技术

随着器件封装尺寸的减小和印刷电路板贴片密度的增加，使印刷过程中印刷电路 板和钢网之间的高精度位置校准成为关键环节之一，而高精度位置校准的前提和核心 就是视觉检测系统对印刷电路板和钢网上的定位标志符的几何中心进行高精度检测定 位。目前表面贴装技术中常用的定位标志符有圆形、矩形、三角形和十字形等，其中 圆形是最常见的，因此，快速准确地检测定位圆形标志符的圆心位置具有广泛的实用 价值。

目前常用的圆形标志符圆心检测算法有：基于最小二乘原理的拟合检测算法、基 于边界曲线分组的检测算法、遗传算法、基于存在概率的圆检测算法和霍夫变换及其 改进算法。在这些方法中，霍夫变换以其鲁棒性强，在噪声、缺损、变形等情况下仍 能取得理想结果的特点而在圆形检测方面被广泛应用。但是传统霍夫变换将二维图像 空间中的一个点映射到三维参数空间，运算时间长，占用内存大，在实际工业生产中 难以应用。为了克服上述缺点，目前改进的方法主要有三类：第一类方法主要是将图 像空间圆形边缘上的三点根据圆形性质，按照一定的规则变换到参数空间中的一点， 理论上大大降低了参与变换的点数，降低了时间开销，但是当图像中存在噪声点和多 个圆的情况时，算法检测精度急剧下降。第二类方法的代表思想是梯度累加，即只对 变化后落在梯度方向上的点进行累加求和，算法执行效率高，速度快，但是该算法与 传统霍夫变换相比抗干扰能力大大下降，同时由于算子求出的梯度离散、有限，因而 梯度方向往往并非指向圆心，造成检测精度降低。第三种方法是平移霍夫变换，该方 法综合上述两类方法的改进思路，借助“坐标平移”思想，对图像空间中的某一基准 点进行霍夫变换，通过将基准点在参数空间中的投影集合平移来得到其他需要变换的 点在参数空间的投影集合。这种算法有利于降低时间和空间开销，但是通过平移得到 的坐标点集合和通过计算得到的坐标点集合不可能完全一样，导致算法最终检测误差 的存在。

发明内容

为了克服现有技术的不足，本发明提供一种既能保证圆心检测精度，又能满足印 刷电路板视觉检测中实时性要求的圆形标志符快速检测定位算法，针对现有圆形标志 符圆心检测中的速度和精度相互制约问题，对平移霍夫变换算法进行改进，提出两级 优化霍夫变换算法，能够准确定位圆形标志符区域，快速精确计算出圆形标志符的圆 心坐标，时间开销大大优于平移霍夫变换，具有快速、准确和鲁棒的特点，能够满足 印刷机视觉检测中，对印刷电路板上的圆形标志符实现精确实时检测定位的要求。本 发明同样适用于钢网上圆形标志符的精确实时检测定位。

本发明解决其技术问题所采用的技术方案包括以下步骤：

步骤一、定义图像坐标系为X轴正方向水平向右，Y轴正方向垂直向上，原点位 于左下角；定义霍夫变换后的参数空间坐标系为a轴正方向水平向右，b轴正方向垂 直向上，原点位于左下角；

设图像I_bi为形状质量检测达到合格标准的N行M列圆形标志符二值化图像，I_bi＝f(x, y)，0≤x≤M-1，0≤y≤N-1；对I_bi进行轮廓提取，构造边缘点集 V＝{(x_vi,y_vi)|i＝1,2,…,Q}，式中，Q为边缘点的总个数，由边缘点集可得到圆形标志 符的外接矩形，外接矩形的宽外接矩形的高 H＝Δy_v＝y_{v_max}-y_{v_min}，式中，x_{v_max}，x_{v_min}分别为V中的X坐标的最大值和最小值； y_{v_max}，y_{v_min}分别为V中的Y坐标的最大值和最小值，取W和H中较小者为d_min，较 大者为d_max；

在图像空间中任取I_bi上的一点(x_base，y_base)作为基准点，以内径r_in＝d_min/2，外径 r_out＝d_max/2作为半径r的约束条件对该点进行圆形霍夫变换；规定x_base的取值范围为[r_out, M-r_out]，y_base的取值范围为[r_out,N-r_out]；则基准点经过霍夫变换后在参数空间得到的 变换圆边缘点集合F_base＝{(a,b)|(a-x_base)²+(b-y_base)²＝r,r_in＜r＜r_out}，式中，(a， b)为变换圆的边缘点坐标，记F_base中变换圆边缘点的个数为D；

步骤二、对圆形标志符边缘点集V中的Q个元素，以3个像素为周期进行等间隔 采样，得到边缘采样点集V′＝{(x′_vj,y′_vj)|j＝1,2,…,Q′}，式中，Q′为边缘采样点的个 数，仅边缘采样点参与平移霍夫变换；当采样到点(x′_vj,y′_vj)时，可计算得到该点在X 方向和Y方向相对于(x_base，y_base)的偏移量，点(x′_vj,y′_vj)经过霍夫变换后在参数空间得 到的变换圆边缘点集合F_j＝{(a_j,b_j)|a_j＝a+(x′_vj-x_base),b_j＝b+(y′_vj-y_base)}，式中(a_j， b_j)为变换圆的边缘点坐标；对F_j中处于此范围内的变换圆边缘点进行累加，累加器 累加区域为$x_{v\_\min }+\frac{\sqrt{2}*r_{\mathrm{out}}}{2}<a_j<x_{v\_\max }-\frac{\sqrt{2}*r_{\mathrm{out}}}{2},y_{v\_\min }+\frac{\sqrt{2}*r_{\mathrm{out}}}{2}<b_j<y_{v\_\max }-\frac{\sqrt{2}*r_{\mathrm{out}}}{2},$式中*r_out代表了圆内接矩形的最大边长；对于每一个F_i，以3像素为周期对处于累 加区域范围内的坐标进行采样累加统计，记需要统计的变换圆边缘点个数为D′；

在参数空间建立一个数组累加器A₁(a_j，b_j)，A₁(a_j，b_j)的初始值均为0；当参 数空间中变换圆的边缘点坐标(a_j，b_j)满足F_j的计算时，相应的累加器A₁(a_j，b_j) 的值加1；寻找累加值最大的峰值累加器，峰值累加器所在位置代表了一级优化霍夫 变换的圆心位置(x_cent，y_cent)；

圆形标志符圆心所在区域确定为以(x_cent，y_cent)为中心的7×7像素的小区域， 即x_cent-3≤a_j≤x_cent+3，y_cent-3≤b_j≤y_cent+3；

步骤三、在图像空间中，对圆形标志符的边缘点集V中的元素逐像素进行遍历， 得到参数空间中变换圆边缘点集F_i＝{(a_i,b_i)|a_i＝a+(x_vi-x_base),b_i＝b+(y_vi-y_base)}；对 于每一个F_i，在步骤二确定的7×7区域中对变换圆边缘点进行逐点累加统计；

在参数空间建立一个数组累加器A₂(a_i，b_i)，A₂(a_i，b_i)的初始值均为0；当参 数空间中变换圆的边缘点坐标(a_i，b_i)满足式F_i的计算时，相应的累加器A₂(a_i，b_i) 的值加1；寻找累加值最大的峰值累加器，峰值累加器所在位置即为二级优化霍夫变 换得到的精确圆心位置(x_center，y_center)。

本发明的有益效果是：实现了圆形标志符圆心的快速精确检测定位。通过基准点 的霍夫变换确定参数空间的平移基准；通过一级优化霍夫变换减少了图像空间参与平 移霍夫变换的圆形标志符边缘点数量，同时减少了参数空间的无效累加，快速计算出 圆形标志符圆心所在的区域；通过二级优化霍夫变换在高效控制参数空间累加范围的 前提下，提高求解圆形标志符圆心位置的精度。算法通过逐步控制参数空间计算量， 大大减低了时间开销，同时保证了精确定位，可广泛应用于对精度和速度要求很高的 机器视觉检测领域。

附图说明

图1是平移霍夫变换原理示意图；

图2是实例3的示意图，显示在圆形标志符图像形状质量合格的前提下，图像边缘 存在凸出或者凹陷的情况；

图3是本发明实现方法流程图；

图中，1-基准点，2–圆形标志符边缘上任意一点，3-圆形标志符边缘上任意 一点，4-圆形标志符边缘上任意一点，5-圆形标志符圆心，6-峰值累加器位置，7 -基准点1霍夫变换后在参数空间的图像，8-标记点2霍夫变换后在参数空间的图像， 9-标记点3霍夫变换后在参数空间的图像，10-标记点4霍夫变换后在参数空间的图 像，11-图像空间的XOY坐标系，12-参数空间的aob坐标系。

具体实施方式

下面结合附图和实施例对本发明进一步说明，本发明包括但不仅限于下述实施例。

本发明的技术方案为：对通过形状质量检测达到合格标准的圆形标志符二值化图 像，首先对图像空间的基准点进行霍夫变换，以确定参数空间的平移基准；一级霍夫 变换通过减少图像空间参与平移霍夫变换的点数和减少参数空间的无效累加，快速确 定圆形标志符圆心所在的区域，二级霍夫变换在此区域内进一步高效控制参数空间的 累加范围，快速精确定位圆心位置，由此通过两级优化霍夫变换方法，加速实现圆形 标志符圆心由粗到精的检测定位。

霍夫变换检测圆的基本原理：霍夫变换利用图像空间和参数空间的点线对偶性， 把图像空间中的曲线检测问题转换到参数空间的峰值统计问题。对于圆形而言，图像 空间中圆边缘上的一个点，通过霍夫变换对应参数空间的一个圆，则图像空间中所有 边缘上的点在参数空间对应的圆簇相交于一点，该点即为图像空间中圆的圆心。对于 平移霍夫变换而言，只对图像空间某个基准点进行霍夫变换，图像空间中圆形边缘上 的点在参数空间的霍夫变换结果，通过基准点在参数空间的图像平移得到，从而避免 了逐点做霍夫变换带来的时间消耗。本发明在平移霍夫变换的基础上，提出两级优化 霍夫变换算法，进一步减少计算量，实现由粗到精地快速精确检测。

本发明包括以下几个步骤：

步骤一、对基准点进行霍夫变换。

定义图像坐标系为：X轴正方向水平向右，Y轴正方向垂直向上，原点位于左下 角。定义霍夫变换后的参数空间坐标系为：a轴正方向水平向右，b轴正方向垂直向上， 原点位于左下角。

设图像I_bi为形状质量检测达到合格标准的N行M列圆形标志符二值化图像，I_bi＝f(x, y)，0≤x≤M-1，0≤y≤N-1。对I_bi进行轮廓提取，构造边缘点集V：

V＝{(x_vi,y_vi)|i＝1,2,…,Q}   (1)

式中，Q为边缘点的总个数。由边缘点集可得到圆形标志符的外接矩形：

W＝Δx_v＝x_{v_max}-x_{v_min}，H＝Δy_v＝y_{v_max}-y_{v_min}   (2)

式中，W为外接矩形的宽，H为外接矩形的高；x_{v_max}，x_{v_min}分别为V中的X坐标的 最大值和最小值；y_{v_max}，y_{v_min}分别为V中的Y坐标的最大值和最小值，取W和H中 较小者为d_min，较大者为d_max。

在图像空间中任取I_bi上的一点(x_base，y_base)作为基准点，基准点可以看做是圆形边 缘上的一点，以内径r_in＝d_min/2，外径r_out＝d_max/2作为半径r的约束条件对该点进行圆形 霍夫变换。同时为了使变换后在参数空间中得到完整圆形，规定x_base的取值范围为[r_out, M-r_out]，y_base的取值范围为[r_out,N-r_out]。则基准点经过霍夫变换后在参数空间得到的 变换圆边缘点集合表示为F_base：

F_base＝{(a,b)|(a-x_base)²+(b-y_base)²＝r,r_in＜r＜r_out}   (3)

式中，(a，b)为变换圆的边缘点坐标，记F_base中变换圆边缘点的个数为D。

步骤二、一级优化霍夫变换减少图像空间参与平移霍夫变换的点数和参数空间的 无效累加，快速确定圆形标志符圆心所在的区域。

在图像空间中，为了减少计算量，提高计算速度，对圆形标志符边缘点集V中的 Q个元素，以3个像素为周期进行等间隔采样，得到边缘采样点集V′：

V′＝{(x′_vj,y′_vj)|j＝1,2,…,Q′}   (4)

式中，Q′为边缘采样点的个数，仅边缘采样点参与平移霍夫变换。当采样到点(x′_vj,y′_vj) 时，可计算得到该点在X方向和Y方向相对于(x_base，y_base)的偏移量，根据霍夫变换和 坐标平移原理可知，点(x′_vj,y′_vj)经过霍夫变换后在参数空间得到的变换圆边缘点集合 F_j相对于F_base具有相同的位置偏移量，因此得到F_j如下：

F_j＝{(a_j,b_j)|a_j＝a+(x′_vj-x_base),b_j＝b+(y′_vj-y_base)}   (5)

式中(a_j，b_j)为变换圆的边缘点坐标。考虑到圆心只可能处于圆内接矩形范围内，因 此只对F_j中处于此范围内的变换圆边缘点进行累加。根据霍夫变换检测圆的原理可知， 图像空间和参数空间均为二维空间，且数据集范围相同，参数空间中需要累加的范围 与图像空间中圆内接矩形范围相同，因此累加器累加区域为：

$x_{v\_\min }+\frac{\sqrt{2}*r_{\mathrm{out}}}{2}<a_j<x_{v\_\max }-\frac{\sqrt{2}*r_{\mathrm{out}}}{2}---\left(\text{6}\right)$

$y_{v\_\min }+\frac{\sqrt{2}*r_{\mathrm{out}}}{2}<b_j<y_{v\_\max }-\frac{\sqrt{2}*r_{\mathrm{out}}}{2}---\left(\text{7}\right)$

式中*r_out代表了圆内接矩形的最大边长。为了加快累加速度，对于每一个F_i，以3 像素为周期对处于累加区域范围内的坐标进行采样累加统计，记需要统计的变换圆边 缘点个数为D′。

在参数空间建立一个数组累加器A₁(a_j，b_j)，A₁(a_j，b_j)的初始值均为0。当参 数空间中变换圆的边缘点坐标(a_j，b_j)满足式(5)时，相应的累加器A₁(a_j，b_j)的 值加1。寻找累加值最大的峰值累加器，峰值累加器所在位置代表了一级优化霍夫变 换的圆心位置(x_cent，y_cent)。

由于在一级优化平移霍夫变换时，在参数空间中对于F_j中的元素是以3像素为周 期进行采样累加统计，因此(x_cent，y_cent)代表了3个像素误差范围内的圆心位置，故 圆形标志符圆心所在区域可以确定为以(x_cent，y_cent)为中心的7×7像素的小区域， 即：

x_cent-3≤a_j≤x_cent+3，y_cent-3≤b_j≤y_cent+3   (8)

步骤三、二级优化霍夫变换高效控制参数空间累加范围，快速确定圆形标志符的 圆心位置。

由于步骤二已经计算得到了圆形标志符圆心位置所在区域，为了提高精度至单像 素级，在图像空间中，对圆形标志符的边缘点集V中的元素逐像素进行遍历，采用与 步骤二相同的方法得到参数空间中变换圆边缘点集F_i：

F_i＝{(a_i,b_i)|a_i＝a+(x_vi-x_base),b_i＝b+(y_vi-y_base)}   (9)

式中(a_i，b_i)为变换圆的边缘点坐标。对于每一个F_i，在步骤二确定的7×7区域中 对变换圆边缘点进行逐点累加统计。

在参数空间建立一个数组累加器A₂(a_i，b_i)，A₂(a_i，b_i)的初始值均为0。当参 数空间中变换圆的边缘点坐标(a_i，b_i)满足式(9)时，相应的累加器A₂(a_i，b_i)的 值加1。寻找累加值最大的峰值累加器，峰值累加器所在位置即为二级优化霍夫变换 得到的精确圆心位置(x_center，y_center)。

至此，通过以上三个步骤，逐步由粗及精地计算出印刷电路板上圆形标志符的圆 心坐标(x_center，y_center)。

算法时间开销分析：

本发明提出的两级优化霍夫变换算法，在一级优化霍夫变换时，在图像空间中对 圆形标志符的边缘点集(x_vi，y_vi)以3个像素为周期进行等间隔采样，参与霍夫变换 的点数Q′与原始平移霍夫变换的Q个像素点相比，为Q'＜Q/2；在参数空间中，对 于每一个变换圆边缘点再次以3个像素为周期采样，并且只统计落在圆内接矩形内的 D'个像素点，与原始平移霍夫变换的D个像素点相比，D'＜D/12，因此大大减少了 计算量。二级优化霍夫变换中，在圆心(x_cent，y_cent)的7×7像素区域内的累加计算， 运算量极小，可忽略不计。因而本发明在达到精确检测定位的同时，高效减少了算法 的时间开销。

以下实例采用仿真实验检验。制作含有已知精确圆心位置的标准圆形标志符图像， 分辨率为1280像素*960像素，并人工加入噪声后作为仿真图。以经过图像质量检测 达到合格标准的仿真图的二值化图像作为输入源，在windows XP操作系统、AMD  Athlo(tm)II X2250 Processor、3.01G主频、2G内存的硬件配置条件下，实例1～3均取 得了良好的检测结果。

实例1：

仿真实验所用标准圆形标志符的圆心坐标为(300，200)，半径R＝100，单位为像 素。

对仿真图的二值化图像进行轮廓提取，构造边缘点集V，得到x_{v_max}＝400，x_{v_min}＝ 200，y_{v_max}＝300，y_{v_min}＝100；计算外接矩形的宽W＝200，高H＝200，及内径r_in＝100， 外径r_out＝100。

在图像空间中任取I_bi上任选一基准点(400，200)做霍夫变换，得到参数空间中的 变换圆边缘点集合F_base。一级优化霍夫变换：对圆形标志符边缘点集V中的元素，以 3个像素为周期进行等间隔采样，采样点相对于基准点做平移霍夫变换，在参数空间 得到的变换圆边缘点(a_j，b_j)的集合F_j；在270.711<a_j<329.289，170.711<b_j<229.289 的区域内累加统计，得到一级优化霍夫变换的圆心位置(300，199)。二级优化霍夫变 换：对圆形标志符的边缘点集V中的元素逐像素遍历，得到参数空间中变换圆边缘点 (a_i，b_i)的集合F_i，对F_i中满足297≤a_i≤303，196≤b_i≤202的边缘点进行累加统计， 得到二级优化霍夫变换的圆心位置(300，200)。与标准圆形标志符的圆心坐标值比较， 误差为(0，0)，时间开销为187毫秒，与原始平移霍夫变换384毫秒的时间比较，节 约了197毫秒。

实例2：

仿真实验所用标准圆形标志符的圆心坐标为(600，500)，半径R＝300，单位为像 素。

对仿真图的二值化图像进行轮廓提取，构造边缘点集V，得到x_{v_max}＝900，x_{v_min}＝ 300，y_{v_max}＝800，y_{v_min}＝200；计算外接矩形的宽W＝600，高H＝600，及内径r_in＝300， 外径r_out＝300。

在图像空间中任取I_bi上任选一基准点(900，500)做霍夫变换，得到参数空间中的 变换圆边缘点集合F_base。一级优化霍夫变换：对圆形标志符边缘点集V中的元素，以 3个像素为周期进行等间隔采样，采样点相对于基准点做平移霍夫变换，在参数空间 得到的变换圆边缘点(a_j，b_j)的集合F_j；在512.132<a_j<687.868，412.132<b_j<587.868 的区域内累加统计，得到一级优化霍夫变换的圆心位置(600，500)。二级优化霍夫变 换：对圆形标志符的边缘点集V中的元素逐像素遍历，得到参数空间中变换圆边缘点 (a_i，b_i)的集合F_i，对F_i中满足597≤a_i≤603，497≤b_i≤503的边缘点进行累加统 计，得到二级优化霍夫变换的圆心位置(600，500)。与标准圆形标志符的圆心坐标值 比较，误差为(0，0)，时间开销为203毫秒，与原始平移霍夫变换1.08秒的时间比 较，节约了877毫秒。

实例3：

仿真实验所用标准圆形标志符的圆心坐标为(600，500)，半径R＝300，单位为像 素，同时仿真图中的圆形标志符图像在形状质量合格的前提下，边缘可能存在的凸出 或者凹陷的情况，如图2所示。

对仿真图的二值化图像进行轮廓提取，构造边缘点集V，得到x_{v_max}＝900，x_{v_min}＝ 300，y_{v_max}＝800，y_{v_min}＝195；计算外接矩形的宽W＝600，高H＝605，及内径r_in＝300， 外径r_out＝302.5。

在图像空间中任取I_bi上任选一基准点(900，500)做霍夫变换，得到参数空间中的 变换圆边缘点集合F_base。一级优化霍夫变换：对圆形标志符边缘点集V中的元素，以 3个像素为周期进行等间隔采样，采样点相对于基准点做平移霍夫变换，在参数空间 得到的变换圆边缘点(a_j，b_j)的集合F_j；在513.546<a_j<686.454，408.546<b_j<586.454 的区域内累加统计，得到一级优化霍夫变换的圆心位置(602，500)。二级优化霍夫变 换：对圆形标志符的边缘点集V中的元素逐像素遍历，得到参数空间中变换圆边缘点 (a_i，b_i)的集合F_i，对F_i中满足599≤a_i≤605，497≤b_i≤503的边缘点进行累加统 计，得到二级优化霍夫变换的圆心位置(601，500)。与标准圆形标志符的圆心坐标值 比较，误差为(1，0)，时间开销为205毫秒，与原始平移霍夫变换956毫秒的时间比 较，节约了751毫秒。