基于Hough变换实现圆的快速检测方法

0 引言

图像处理中对圆进行检测及确定其参数是图像特征检测和模式识别中的一项重要任务，在生物信息识别、产品检测、集成电路板在线质量检测等众多领域中，通常需要对图像中的圆形图案进行检测，以便识别和定位目标。常用的圆检测方法有Hough变换检测圆方法、形状分析法、BP网络分类器方法、基于圆度的计算方法等。目前，Hough变换圆检测（HTCD）方法[1]在噪声、曲线间断，边缘不完整地情况下，仍能够可靠的提取出圆的特征信息，成为常用的圆检测方法，Xu等提出了随机Hough变换圆检测方法（RHT）[2]，该方法在图像空间中随机选取不共线的三个特征点，映射成参数空间中一个点，是多到一的映射，大大减少了计算量，但是在处理带有一定噪声且复杂度较高图像时，由于随机采样的无效点太多，造成了大量的无效累积。Chen等提出随机圆检测方法（RCD）[3]，RCD是针对图像的所有边缘点直接检测，不涉及到空间参数的累积等，提高了计算检测速度，减少了累积内存空间，但是当干扰像素点太多时，需要检测的样本数太多，计算量会大大增加，导致检测速度下降，计算不稳定。Shih-HsuanChiu提出了一种标准Hough变换圆检测的投票方法，减少了计算量和存储空间[4]。W.C.Y. Lam等提出了具有直角特性的点三元组检测方案，方案基于Hough变换将计算空间由三维降到了二维，有一定的抗噪能力，但在二维空间计算复杂度仍然很高[5]。林金龙等提出了用点Hough变换检测圆，根据同一圆上任意两条弦的中垂线相交于圆心的性质，将搜索空间由三维降到一维，降低了计算复杂度和对资源的需求[6]，但检测精度仍然不高。

为了解决上述算法出现检测精度不高，计算复杂，占用内存多，不能满足速度要求的缺陷，本文在Hough变换圆检测的基础上进行改进，提出了一种新的Hough变换圆检测方法（FHCD），该方法首先对原始图像进行预处理，并通过Canny边缘检测方法进行边缘提取，在对提取的边缘进行形状识别，排除非圆，之后利用圆是中心对称图形的几何性质，同时选取圆周上三点，计算出圆心和半径，将搜索空间由三维降到一维，进一步降低了计算复杂度，提高了计算速度，实验表明，该方法同时具有较高的检测精度和抗干扰性。

1 Hough变换圆检测原理

Hough变换最早于1962年由Paul Hough提出，其基本思想是将检测图像的空间域映射到参数空间，用大多数边界点满足的某种参数形式来描述图像中的边缘曲线,通过投票和设置累加器的方法将图像空间中的复杂问题转换成简单的局部峰值检测问题[7]。

Hough变换是目前检测图像圆的主要方法，它实现了图像空间的边缘点映射到参量空间中一个投票过程，空间的峰值点对应检测图像所需要的参数。传统的Hough变换在参量空间中对三个自由参数圆心坐标（a,b）和半径r进行累积，对存储量和计算量要求很高。

Hough变换检测圆的公式：

其中r0为半径,（a0，b0）为圆心坐标。

在参数空间中，半径为r，圆心坐标为（a,b）的圆表达式为：

式(2)表示图像空间的圆对应着参数空间中的一个点，图像空间中的任意一个有效点（xi，yi）在参数空间中对应着一个三维直立圆锥，如图1所示，该点约束了通过该点的一族圆的参数。对于图像空间中的一个圆，它的半径是固定不变的，而圆周上各个点组成的集合在参数空间中表现为半径相等，而圆心坐标不等的各个圆锥的集合。图像空间中圆上的点映射到参数空间中的一族圆锥的交点正好对应于圆的圆心坐标和圆的半径，即是被检测圆的三个参数，实现Hough变换检测圆。

如图2所示，图像空间中4个边缘点（A，B，C，D）映射到参数空间，在圆心坐标（a，b，r）处相交，对应着在点（a，b，r）的累加器投票值为峰值，从图中可以看出，图像空间到参数空间的映射，是一维到三维的映射，这需要大量的存储空间且计算复杂度高，难以实际应用中对实时性要求较高的圆检测。

图1 图像空间点对应参数空间直立圆锥

图2 图像空间圆上点在参数空间中的表示

2 改进的Hough变换圆检测方法

Hough变换需要将图像空间转换成3个参量空间，参量空间较大，而往往为了提高精度，量化值又较小，投票阶段箱格数会很多，使得Hough变换圆检测占用内存空间和计算量特别多，运算速度慢[8]，为此对Hough变换进行了改进，该方法在圆周上同时选取三点，以过圆心的直线x=a0，y=b0为对称轴对图像上的三点进行对称选取，选取的三点对应于参量a-b-r空间中一点，运用Hough变换对该点进行累加计数，计数最大值对应的参数坐标即圆心坐标和半径的值，由此将搜索空间由三维降到了一维，降低了计算复杂度，提高了计算速度和精确性。

2.1 圆的识别

摄像机在获取图像的过程中，拍摄的目标图片中往往含有其他背景图像，因此将获取的彩色图像转换成灰度图后，运用Otsu图像分割技术将Mark点图像从背景图像中精确地分割出来，阈值分割后运用Canny边缘检测器对图像进行边缘提取，得到一幅包含边缘信息的图像。

为了避免无效投票，减少无效累积，边缘检测后对图像进行圆形识别，图3中点A1，A2，A3，A4为圆周上互不重合的四点，坐标值分别为（x1，y1），（x2，y2），（x3，y3），（x4，y4）由圆的性质可知，若四点在圆周上，则必满足弦A1A2和弦A3A4在弦A2A3的异侧。

构造函数：

将（x1，y1）、（x4，y4）代入上式：

若f（x1，y1）. f（x4，y4）＞0，则弦MN和弦PQ一定在弦NP的同侧；

若f（x1，y1）. f（x4，y4）＜0，则弦MN和弦PQ一定在弦NP的异侧；

若f（x1，y1）. f（x4，y4）=0，则弦MN或弦PQ一定与弦NP共线。

对于f（x1，y1）. f（x4，y4）＞0的图形可以初步认为是圆，由此就可以在检测过程中，排除明显不可能为圆的轮廓，从而提高后续Hough变换检测圆的效率。

图3 圆性质图

2.2 圆参数确定

图像上每一点的灰度值，如式(4)所示：

p（m,n）表示第m行第n列的像素点坐标值。定义图像中任意一点关于过圆心的直线x=a0，y=b0对称的点组集合为|P|={（A1，B1，C1），（A2，B2，C2），…，（An，Bn，Cn）}，在图4中圆上选取Ai，Bi，Ci三点，（Ai，Bi，Ci）∈|P|，Ai，Bi，Ci坐标分别为（mi，ni）、（qi，ni）、（mi，zi），点Ai与点Bi关于圆心横坐标x=a0对称，点Ai与Ci关于圆心纵坐标y=b0对称，Ai，Bi，Ci三点构成一个以直径为斜边的直角三角形。

由于图像二值化处理过程中图像边缘存在一定的偏移和误差，因此存在对称点为非边缘点的情况，对此采用对称点上下左右偏移一个像素来处理。

设：

当f（mi，ni）×f（qi，ni）=1时Ai（mi，ni）与Bi（qi，ni）是关于圆心横坐标x=a0的对称点，当f（mi，ni）×f（mi，zi）=1时Ai（mi，ni）与Ci（mi，zi）是关于圆心纵坐标y=b_0的对称点。

利用圆是中心对称的几何性质可以求出：

圆上的任意不共线三点Ai，Bi，Ci，对应于参量空间中一个点（ai，bi，ri），参量空间中的点用向量表示图像中圆（ai，bi，ri）上的点组（Ai，Bi，Ci）对应参量空间中向量在图像中选取N个点组，得到包括N个向量的向量组，在参量空间中运用Hough变换圆检测对向量值进行累加计数，累计阵列中出现次数最多的向量值就是图像中圆的参数。

图4 获取圆心和半径

2.3 复杂度分析

假设图像有N个待分析点，则共有个点组，从图像空间到参数空间进行投票时，对应于在参数空间中进行了次投票，复杂度函数为：f（N）=O（N3）。

在改进的算法中，同样假定图像中有N个待分析点，点Ai选定后，由于圆是中心对称图形的几何性质，水平对称点Bi，垂直对称点Ci也被定下来，点（Ai，Bi，Ci）能够达到遍历所有有效边缘，共有N个点组，对应于参量空间中进行了N次投票，复杂度函数为f（N）=O（N）。O（N3）远大于O（N），从而显著减少了计算时间，提高了计算速度，达到精确检测的目标。

2.4 算法流程

本文的算法流程如图5所示：先对图像进行预处理以消除摄像头在获取图像时所产生的噪声，阈值分割后运用Canny算子进行边缘检测，获取图像边缘信息，然后通过计算f(x,y)来对轮廓进行圆形识别，最后运用新的Hough变换圆检测方法获取圆参数。

图5 算法流程图

3 实验结果和分析

为验证本文算法的检测结果，采用PCB Mark图片对改进后Hough变换圆检测方法与SHT和RHT算法进行对比实验，主要针对圆检测准确度和速度进行考察。实验采用的计算机为Intel 3.6GHz Core i7-7700，8G内存，软件环境为MATLAB2014a。

3.1 速度和精确性测试

图6 新Hough变换检测过程图

测试图片为PCB Mark图，本文的测试程序将检测到的圆用蓝色线画出，原始图像在PCB中运用3D显示功能生成，对原始图像进行平滑处理，生成与实际情况尽可能相符的标准图像，如图6(a)所示，实验重复100次。图6(b)是边缘检测图，图6(c)是最终的检测结果图。

表1列出了不同方法的检测结果，检测结果表明，三种检测方法都能检测出圆，检测误差在一个像素以内，执行时间约为26ms，显示了新Hough变换圆检测方法具有检测精度高，计算速度快的特性。

表1 速度和精确性性测试结果

3.2 鲁棒性测试

在工业检测环境下，由于光线照射不均匀，其他影像干扰等因素的影响，存在各种噪声，因此模拟实际工作环境，给检测图像加上不同强度的椒盐噪声，比较不同圆检测方法所花时间，进行鲁棒性测试。

图7(a)Mark图像噪声强度为10%，图7(b)是边缘检测图，图7(c)是算法在噪声影响下的圆检测结果图。表2为不同噪声图像的检测数据，从中可以看出本文算法检测的精度和速度优于标准Hough变换。

图7 噪声Mark图像的圆检测

4 结论

提出了一种改进的Hough变换圆检测方法，该方法运用阈值分割技术将测试目标与背景分离，对检测图形进行Canny边缘检测后，对检测图像进行形状识别，之后运用新Hough变换识别圆的参数，得到检测结果。运用PCB Mark图片和PCB Mark噪声图进行实验，实验结果表明本文方法与标准Hough变换圆检测方法（SHT）和随机Hough变换圆检测方法（RHT）相比，降低了计算复杂度，提高了处理速度，同时降低了对存储空间的需求，且该方法保留了标准Hough变换检测精度高、抗噪能力强的优点，图像中存在干扰因素时，计算速度优势明显，具有较强的抗干扰能力和检查精度，可以满足机器视觉，模式识别等领域检测的要求。

表2 不同噪声条件下三种圆检测方法速度和精度比较

参考文献：

[1]Smereka M, Duleba I. Circular object detection using a modified Hough transform[J].International Journal of Applied Mathematics and Computer Science,2008,18(1):85.

[2]Xu L,Oja E.Randomized Hough transform (RHT):basic mechanisms,algorithms, and computational complexities[J].CVGIP: Image understanding,1993,57(2):131-154.

[3]Chen T C,Chung K L.An efficient randomized algorithm for detecting circles[J].Computer Vision and Image Understanding,2001,83(2):172-191.

[4]Lam W C Y,Yuen S Y. Efficient technique for circle detection using hypothesis filtering and Hough transform[J].IEEEProceedings-Vision,Image and Signal Processing,1996,143(5):292-300.

[5]Che0w JJ.An effective voting method for circle detection[J].Pattern recognition letters,2005,26(2):121-133.

[6]林金龙,石青云.用点Hough变换实现圆检测的方法[J].计算机工程,2003,29(11):17-18.

[7]周勇亮,金燕,何萍,等.随机Hough变换圆检测累计加速算法[J].计算机辅助设计与图形学学报,2014,26(4):574-580.

[8]Wang J, Zhu Q, Wang W, et al. Straight line extraction algorithm by Hough transform combining edge grouping[J].Journal of Remote Sensing,2014,1:186-192.

[9]何东海,郑海鹰,马晓玲.GIS中城市平面地图的模糊矢量化算法及实现[J].测绘学院学报,2001,(03):213-216.