基于随机Hough变换改进的快速圆检测算法

朱正伟，宋文浩，焦竹青，郭 晓

(常州大学(武进校区) 信息科学与工程学院，江苏 常州 213164)

0 引 言

目前，图像中圆检测的最常用方法是Hough变换[1,2]，但Hough变换通常需要较大的存储空间和计算时间，因而很少在实际应用中使用。

为了提升Hough变换算法的性能有学者提出了随机Hough变换算法，该算法的思想[3]是在边缘图像中随机选取3个点映射成参数空间的一个点，以此计算圆的参数，并对结果进行累积以判断圆的真假。随机Hough变换只对有效参数单元进行累计，大大减轻了内存的负担，节省大量内存空间，避免了Hough变换一到多映射的巨大运算量，但是随机Hough变换对边缘图像的要求很高，如果圆形出现变形，就不能准确检测出结果，且由于随机采样，随机取出的三点在同一圆的概率就很小，导致检测速度较低。为了克服这些缺陷，研究人员提出了一些改进的方法，比如对随机采样进行约束[4,5]、利用采样点的梯度[6-8]或曲率信息[9,10]来判断是否进行累积、利用随机采样共圆的四点来降低无效累积的计算[11,12]、通过在每次成功检测圆后不清空参数空间来减少总采样次数[13]。为了进一步提高随机圆检测速度，本文提出了一种改进的随机Hough变换快速圆检测算法。通过实验对比验证，本文算法相比于传统算法可以明显提高检测速度。

1 随机Hough变换圆检测

由于Hough变换在检测圆时有较大问题，因而本文仅对随机Hough变换算法(RHT)做相关介绍。首先设定待检测图像中圆的期望个数以及采样累积循环次数上限。在每次循环中，随机采样3个不共线的边缘点，计算出对应的圆的参数(a,b,r)，即候选圆的圆心为(a,b)，半径为r；如果图像中的边缘点到圆心的距离近似等于半径，则认为该边缘点为候选圆上的点，统计边缘点在候选圆上的个数；如果候选圆上被验证的边缘点个数超过一定阈值，则认定该候选圆为真圆，并将该圆对应的所有边缘点去除，循环结束。直到检测完所有的圆为止。

设D为图像边缘点集，P为圆参数单元集，k为随机采样循环次数，Kmax为循环采样次数阈值，N为累计验证阈值，Mmin为共圆验证阈值，则RHT算法具体实现步骤如下：

步骤1 构造边缘点集D，初始化圆参数集合P=NULL，初始化循环次数k=0。

步骤2 从集合D中随机选取3个点。

步骤3 由这3点可得到圆参数p，若有解，转步骤4；否则转步骤7。

步骤5 将p插入P，令其对应value值为1，转步骤7。

步骤6 将pc的value值加1，若value

步骤7 令k=k+1， 若k>Kmax，则结束；否则转步骤2。

步骤8pc为候选圆参数，若该圆上统计的点数M>Mmin，转步骤9；否则转步骤10。

步骤9pc为真圆参数，转步骤11。

步骤10pc为假圆参数，从P中去除pc，转步骤2。

步骤11 判断期望圆是否已经检测完，若是则结束；否则，从D中去掉pc上的点，同时令P=NULL，k=0，转步骤2。

算法流程如图1所示。

图1 随机Hough变换算法流程

2 改进的快速随机Hough变换圆检测

改进算法主要分为以下3个部分：①原始图像预处理，即通过对图像灰度化、平滑滤波和边缘细化等处理，消除光照、背景等噪声点，为后期图像处理减少数据量；②候选圆的检测，即通过检测算法计算出候选圆，但不确定真假，需要对其进行验证；③候选圆的验证，即通过证据积累验证候选圆的真假，同时去除被错误拟合的圆，余下的圆就是所找的真圆。

2.1 对原始图像进行预处理

由于实际图像往往比较复杂，可能存在如光照不均匀、目标物体分布不规则、相互之间有遮挡和物体边界模糊等问题。为了避免上述问题对圆检测的影响，先对原图像进行预处理，减少图像中的噪声点，从而有效减少无效累积和计算量，从而提高检测效率。

对原图像进行预处理的步骤：①对原始图像进行灰度化和平滑滤波操作，图像的滤波处理可以去除一些噪声同时又可以保留图像的边缘信息，有利于图像的进一步处理；②对图像进行二值化，二值化处理可以大幅减少图像中数据量，同时能凸显出感兴趣的物体轮廓；③对二值图像进行边缘检测，边缘检测算子选择Canny算子,Canny算子相比于其它算子能更好地保留物体边缘；④对边缘图像进行细化处理，将边缘细化到最低限度且相连没有断点的线，该步同样可以减少数据量，提高检测效率。

2.2 候选圆的检测

尽管传统RHT是只对多到一映射所得的参数分配单元进行判断和累积，但在处理复杂图像时，大量噪声点会干扰随机采样操作，使圆上的点被成功采样到的概率变小，引入大量无效采样，易导致无效判断和无效累积从而影响算法效率。

本文获取候选圆的方式为首先在边缘图像上随机采样一点p1(x1,y1)(如图2所示)，再在以p1为中心N×N的方形窗口内，找到p1所在的连通域，并对连通域内的点进行最小二乘法圆拟合以得到候选圆。

图2 以p1为中心的N×N的窗口

最小二乘法(least squares analysis)通常用于曲线拟合，它是一种经典的优化手段。最小二乘法原理是采用最简的方法求得一些绝对不可知的真值，且令误差平方之和为最小。

对于从p1点连通域得到的点集 {(xi,yi)，i=1,2,…,m， 其中m为点集中点的数量}，设理想圆pc的圆心为(a,b)，半径为r，则点距候选圆圆心的代数距离方程为

d=(x-a)2+(y-b)2-r

(1)

式中： (x,y)∈{(xi,yi),i=1,2,…,m}。

令候选圆半径的取值范围为[Rmin,Rmax]，如果理想圆的半径r满足Rmin

2.3 候选圆的验证

通过2.2节的方法可以得到图像中的候选圆，但候选圆的真假不能确定，可能存在一些被错误拟合的圆，因此需要对其进行验证，去除假圆。

验证候选圆的真假，需要统计候选圆上的点数。本文算法规定如果边缘点位于该圆内切正方形和外接正方形之间的部分区域，则判断该点为候选圆上的点。这样通过简单的数值比较即可筛选出符合的像素点，相对通过计算两点间距离的验证方式可以明显减少计算量从而大幅缩减验证耗时。具体采样区域如图3中阴影部分所示。

图3 候选圆内切外接正方形

由图3知，候选圆的圆心坐标为(a,b)，半径为r，要验证的边缘点坐标(x,y)若满足式(2)

(2)

则视点(x,y)为候选圆上的点，统计该候选圆上的边缘点的数量M。令验证候选圆为真圆的阈值Mmin=λ*2πr(其中λ为比例系数，r为候选圆半径)，若M>Mmin，则确认当前候选圆为真圆，否则为假圆。

2.4 算法的总体流程实现

本文算法描述如下：

步骤1 将边缘图像中的所有边缘点存储至集合D，初始循环次数k=0，令最大循环次数为Kmax；

步骤2 从D中随机选取一个点d1；

步骤3 在以点d1为中心的N×N的窗口内，找到d1所在的连通域，并对此连通域内点进行圆拟合，得到理想圆pc(a,b,r)，若半径r满足Rmin

步骤4 对候选圆pc进行证据积累，若pc的有效计数大于阈值Mmin，则转步骤6；否则，转步骤5；

步骤5k=k+1，若k>Kmax，则结束；否则，转步骤2；

步骤6pc为真圆，判断理想圆是否已经检测完。若是，则结束；否则，转步骤2。

算法流程如图4所示。

图4 改进算法的流程实现

3 实验验证及分析

为验证算法的有效性，用MATLAB程序完成了大量的图片圆检测实验。限于篇幅，只选取当中的几幅图片做说明。本文运行软件版本为MATLAB R2014a，微机硬件配置为Intel(R) Pentium(R) CPU P6200 @2.13 GHz，4 G RAM，比例系数λ取[0.6,0.9]。下面就多个算法的预处理、耗时、准确性3个方面做比较分析。

3.1 预处理方法比较

对原始图像进行预处理，可以显著减少图像中无关噪声的影响。传统预处理方法一般是对原始图像直接进行边缘检测，本文改进方法是按照2.1节描述的方法对图像进行预处理得到边缘图像。预处理结果如图5所示，其中(a)、(d)为原图像，(b)、(e)为对应原图采用传统预处理方法得到的边缘图像，(c)、(f)为对应原图采用本文改进后的预处理方法得到的边缘图像。

图5 预处理方法对比

采用传统预处理方法和本文提出的改进方法分别对图5中的(a)和(d)图像进行处理，表1为采用两种方法处理后图像中剩余边缘点数的统计结果。从表中数据可以看出传统边缘方法和本文边缘方法得到的结果有较大差异。前者得到的结果中含有大量的噪声点，而本文改进的方法明显减少了噪声点数量，有利于下一步的图像处理。

表1 两种预处理方法结果

3.2 算法耗时分析

为验证本文算法的加速效果，对RHT算法、文献[13]的RHT_A算法和本文算法进行2组实验比较。在实验中，由于3种算法都是基于随机采样机制的，因而算法每次运行时间不固定，对此本文对每种算法均分别测试50次，取其耗时的平均值作为检测时间。

实验1为合成图像对比实验。为测试算法的性能，在图6(a)的合成图上增加不同程度的随机噪声点，噪声比分别为50%和100%。图6中，(a)为一幅大小为256×256的合成图像，(b)为噪声比为50%的图像，(c)为噪声比为100%的图像。

图6 合成图像实验

表2所示为3种算法对不同噪声比图像进行圆检测所耗费时间的平均值，从中可以看出，当噪声比相同时，本文算法比RHT算法和RHT_A算法耗时少，说明了本文算法的加速效果。

实验2为实际图像对比实验，图7中的(a)和(b)两幅图片来自文献[5]和文献[13]，表3为对(a)、(b)两幅实际图像分别使用3种算法所耗费的时间。从中可以看出，本文算法针对不同噪声比图像的检测耗费时间均明显比RHT算法和RHT_A算法耗费时间少。由此可见本文算法具有较快的圆检测速度，具有较好的检测效率。

表2 3种算法对不同噪声比图像圆检测的耗时

图7 实际图像

算法图7(a)图7(b)RHT算法/s3.1673.437RHT_A算法/s1.4161.252本文算法/s0.4160.547

3.3 算法准确性分析

为了验证本文算法的准确性，分别使用RHT算法、RHT_A算法和本文算法对图7中的实际图像(b)进行检测。其检测结果如图8所示(其中白色圆为检测出的圆)。

图8 3种算法检测结果

仔细观察图8，可以发现在检测精度上，3种算法检测效果相当。对于图7(b)，考虑到原图像中部分圆形物体不能完整显示，故设定图像中可识别的完整圆数目为25个。下面分别对3种算法就圆总数、正确检测数目、错误检测数目、漏检数目4个方面进行统计，详见表4。

表4 实际图片实验数据

从表4中数据可以看出，3种算法均可以检测出25个圆中的22个，而本文算法和RHT_A算法没有错检和漏检，因此在检测准确性上，本文算法和RHT_A算法相当并且优于RHT算法。

4 结束语

文本就随机Hough变换算法进行了改进，算法的优点在于在预处理环节增加降噪和边缘化的处理，显著减少了数据量；同时采用圆拟合的方式确定候选圆，提高了拟合候选圆的正确性；最后在验证真圆环节通过缩小限定累积取值区域，大大降低了计算量。通过对模拟图像和实际图像的实验结果对比，本文算法运行时间明显小于随机Hough变换算法且具有较好的准确性。另外，本文算法还具有抗噪声能力强等优点，在实际图像检测中性能表现良好，对各个领域的圆识别具有较好的应用价值。