一种基于中点画圆算法的改进Hough变换检测圆方法

朱晓林， 高诚辉， 何炳蔚， 黄敏纯， 陈 杰

（1. 福州大学机械工程及自动化学院，福建 福州 350108，2. 福建省制造业数字化设计工程研究中心，福建 福州 350002）

一种基于中点画圆算法的改进Hough变换检测圆方法

朱晓林1,2， 高诚辉1,2， 何炳蔚1,2， 黄敏纯1， 陈 杰1

（1. 福州大学机械工程及自动化学院，福建 福州 350108，2. 福建省制造业数字化设计工程研究中心，福建 福州 350002）

为了对机械零件图像中的圆形几何特征进行视觉检测，将中点画圆算法与Hough变换相结合，提出一种基于中点画圆算法的 Hough变换检测圆的新方法，并对中点画圆算法中的浮点运算等方面进行了改进。给出了该新方法的具体实施步骤和检测结果，表明了该方法的可行性。最后，通过对比实验验证了该方法的有效性。

工程图学；中点画圆算法；Hough变换；圆检测；累加器投票

直线、圆（圆弧）及椭圆等平面曲线是构成机械零件图像的主要元素。在机械零件二维几何特征检测工作中，首先要进行机械零件图像的边缘检测，在获取图像边缘离散点信息后，再进行直线、圆（圆弧）、椭圆或其它平面曲线等几何特征的检测。其中，圆形特征检测无疑是机械零件二维几何特征检测的重要内容。

Hough变换是目前应用较为广泛的圆检测方法，该方法最大特点是可靠性高，在噪声、变形、甚至部分区域丢失的状态下仍能取得理想的结果[1]，但直接采用Hough变换检测圆，存在需要频繁地进行开平方或三角运算等缺陷，计算量比较大。目前，Hough变换已发展出几种改进方法，如随机Hough变换、梯度Hough变换等，但仍存在会产生大量无效累积、数字化量化误差大等问题[2-6]。

中点画圆算法是一种高效的画圆算法，但目前只用于画圆方面的研究，尚未见到用于Hough变换检测圆的研究。本文将中点画圆算法与Hough变换相结合，提出一种基于中点画圆算法的改进Hough变换检测圆的新方法。该新方法具有运算速度快，占用内存小，检测结果准确等特点，可用于对自动生产线上被加工机械零件的圆形几何特征进行实时在线检测，确保零件的加工质量。

1 标准Hough变换检测圆方法

标准Hough变换检测圆的基本原理是[7]：设半径为r0，圆心坐标为(a0, b0)的圆的表达式为

对于原图像中的每一点(xi, yi)，在参数空间中对应一个三维直立圆锥，其表达式为

其中 a、b、r为参数空间中的3个变量。对于图像空间中的半径为r0，圆心坐标为(a0, b0)的圆上的点集，在参数空间中对应一簇三维圆锥面，它们交于一点(a0, b0, r0)，如图1所示。

图1 标准Hough变换检测圆方法

在参数空间中，由公式（2）可推导出

对给定的 r0，由公式（3）可确定出一组(ai0,bi0)值，将(ai0, bi0)值投票到r0层的累加器上；对给定的 r1，由公式（3）又可确定出另一组(ai1, bi1)值，将(ai1, bi1)值投票到r1层的累加器上；依此类推，可得到三维累加阵列(aij, bij, rj)。通过三维累加计算，得到最大累加值对应的坐标(a0, b0, r0)，即得到被检测圆的3个参数，实现标准Hough变换检测圆。

由于采用标准 Hough变换检测圆需要频繁地进行开平方运算，其计算量相当大，占用的存储空间也非常大。因此，在实时在线检测中用标准Hough变换检测圆几乎是不可能的。

2 中点画圆算法

中点画圆算法的基本思想是[8]：确定起始点P，根据中点M构造函数判别式，计算出下一像素点 P1（如图 2(a)所示）；依次每步单位间隔取样，顺时针确定出最佳逼近于该圆弧的像素序列（如图 2(b)所示）；考虑到圆的对称性，只需计算 1/8圆弧的数据（如图 2(c)所示），从而大大减少运算量。

图2 中点画圆算法

3 基于中点画圆算法的改进Hough变换检测圆方法

将中点画圆算法与 Hough变换检测圆方法相结合，提出一种基于中点画圆算法的改进Hough变换检测圆方法，其基本思想如下：设待测圆的半径为r0，对于实时在线检测获得的机械零件图像每一个边缘点(xi, yi)（如图3(a)所示），以(xi, yi)为圆心、r0为半径，在Hough变换参数空间的累加器阵列中，采用中点画圆算法对相应的累加器进行投票（如图 3(b)所示），然后检测各累加器的累加值，当某个累加器的值达到检测阈值时（如图 3(c)所示），即可确定出机械零件图像上的一个以(ai, bi)为圆心，r0为半径的圆。

图3 基于中点画圆算法的改进Hough变换检测圆方法

对于给定的半径R，在参数空间的累加器阵列中，设当前累加器为P(xp, yp)（如图3(b)所示），为判别下一累加器为 P1还是P2，构造判别函数F(x, y)= x2+ y2- R2。对于参数空间中的圆上的点，F(x, y)= 0；对于圆外的点，F(x, y)> 0；而对于圆内的点，F(x, y)< 0。

假设M是P1和P2的中点，即M =(xp+ 1, yp-0.5)。构造M的判别式

若d1< 0，M在圆内，说明P1距离圆弧更近，应取 P1为下一累加器。再下一个累加器的判别式为

因此，在已知1P后，即可根据dΔ方便地确定出下一个累加器。

若10d≥ ，M在圆外（或圆上），说明2P距离圆弧更近，应取2P为下一个累加器。再下一个累加器的判别式为令右下方向的增量因此，在已知2P后，即可根据 d′Δ 方便地确定出下一个累加器。

对比公式（3）～公式（5）可以看出：公式（3）要进行开平方运算，其运算量大，而公式（4）、公式（5）只需进行简单的加减运算，运算量小，运算速度快。

为了进一步提高检测速度和准确性，使该方法能更好地适用于机械零件圆形几何特征的实时在线检测，对检测圆的方法做以下改进。

如图2(b)所示，要生成第二个8分圆，按顺时针方向，起始点为(0,)R，判别式d的初始值为

因在计算判别式d的过程中会出现大量浮点运算，存在运算量大、计算结果精度低等缺点。为了克服浮点运算方法的不足之处，本文提出采用整数运算代替浮点运算，即将判别式d的初始值放大 4倍改为 5-4R，则下一个累加器的判别式增量dΔ变为8xp+12或8(xp-yp)+20，从而进一步提高检测速度和精度。

4 具体实施步骤

基于中点画圆算法的改进 Hough变换检测圆方法的具体实施步骤如下：

（1） 经验知识设定

根据待检测机械零件图像的实际情况和经验知识，预先分段指定待测圆的半径范围，进行经验知识设定。

（2） 分段检测阈值生成

根据实际情况，分段设置调节系数，自适应生成各段的检测阈值[9]。

（3） 基于中点画圆算法对累加器进行投票

采用中点画圆算法对 Hough变换参数空间中相应的累加器进行投票，然后统计各累加器的累加值。

（4） 检测出圆的几何参数

比较累加值与检测阈值，确定出被测圆，然后得到圆心坐标、圆的半径等几何参数。

检测圆新方法的检测结果如图4所示。

图4 检测圆新方法的检测结果

5 对比实验

在相同检测阈值的情况下，分别采用本文提出的检测圆的新方法、标准Hough变换检测圆和随机Hough变换检测圆这三种方法，在给定的半径范围内，对图5中的圆形特征进行检测，获取圆的几何参数，并求得各自的平均运算时间。图5中的圆形几何特征的原始值分别为：圆心坐标(65, 150)、(60, 65)及(121, 97)，对应半径 19、33及 47pixels。对比实验采用的计算机配置为：Pentium® 4 CPU 2.80GHz，2GB内存，NVIDIA GeForce 4 MX 440图形加速卡，64MB显存。其对比实验结果如表1所示。

表1 三种检测圆方法的对比实验结果

图5 对比实验的原始图像

通过上述实验可以看出，检测圆的新方法能有效地检测出目标圆，检测结果准确，其检测速度要比标准Hough变换检测圆快一个数量级，也比随机Hough变换检测圆略胜一筹。

6 结 束 语

针对标准Hough变换计算复杂、运算量大，随机 Hough变换会造成参数单元的大量无效累积等缺点，将中点画圆算法与 Hough变换相结合，提出了一种基于中点画圆算法改进的Hough变换检测圆新方法，并避免了浮点运算。通过实验表明，本文提出的检测圆的新方法具有运算速度快，占用内存小，检测结果准确等特点，适合于被加工机械零件的实时在线检测。由于该方法在初始化设置时还需人工干预，影响了其自动化检测水平，今后还需在提高通用性、智能化等方面进行进一步研究。

[1]朱桂英, 张瑞林. 基于Hough变换的圆检测方法[J].计算机工程与设计, 2008, 29(6)：1462-1464.

[2]XU L, OJA E, Kultanen P. Randomized hough transform (RTH)：basic mechanisms, algorithms, and computational complexities [J]. Computer Vision Graphics Image Process：Image Understanding, 1993,57(2)：131-154.

[3]蒋联源, 苏 勤, 祝英俊. 快速随机Hough变换多圆检测算法[J]. 计算机工程与应用, 2009, 45(17)：163-166.

[4]赵桂霞, 黄 山. 一种基于随机Hough变换圆检测的改进算法[J]. 计算机技术与发展, 2008, 18(4)：77-79.

[5]瞿 钧, 甘 岚. 梯度Hough变换在圆检测中的应用[J]. 华东交通大学学报, 2007, 24(1)：101-104.

[6]冯新岗, 周 诠. 数字图像中基于多尺度几何分析的圆检测算法[J]. 中国图象图形学报, 2009, 14(5)：957-960.

[7]HOUGH P V C．A method and means of recognizing complex patterns [P]. U.S. ：3069645, 1962-12-18.

[8]孙家广, 刘 强, 陆 薇, 等. 计算机图形学(第3版)[M]. 北京：清华大学出版社, 1999. 167-173.

[9]朱晓林. 机械零件二维几何特征检测技术研究及系统开发[D]. 福州：福州大学, 2009.

An Improved Method of Hough Transform Circle Detection Based on the Midpoint Circle-Producing Algorithm

ZHU Xiao-lin1,2, GAO Cheng-hui1,2, HE Bing-wei1,2, HUANG Min-chun1, CHEN Jie1
( 1. College of Mechanical Engineering and Automation, Fuzhou University, Fuzhou Fujian 350108, China;2. Fujian Provincial Research Center of Digital Design for Manufacturing, Fuzhou Fujian 350002, China)

To conduct vision detection to the circle’s geometric feature of the machine parts’images, a new circle detection method is put forward by joining the midpoint circle-producing algorithm and Hough transform, which improves the floating calculating of the midpoint circle-producing algorithm and other. The detailed implementation steps are given and the detection results show that the new method is feasible. Finally, the experimental comparison indicates that the proposed method is effective.

engineering graphics; midpoint circle-producing algorithm; Hough transform;circle detection, accumulator voting

TH 164

A

1003-0158(2010)06-0029-05

2010-04-01

国家自然科学基金资助项目（50605007）；福州市科技计划资助项目（2009-G-115）；福州大学资助项目（2009-8）

朱晓林（1976-），男，福建福州人，高级程序员，实验师，硕士，主要研究方向为机器视觉。