基于随机采样的随机Hough变换快速圆检测算法*

李建森，项 偲

(黄山学院 信息工程学院，安徽 黄山245041)

目标检测是计算机视觉领域中的核心问题之一，自提出以来逐渐成为计算机视觉领域的研究热点。圆形是构成物体的基本形状之一，具有圆形形状的物体存在于各种工农业生产中，如工业制造中的圆形零件检测、农业生产中的果实定位、人脸识别中的瞳孔检测等，对圆形目标进行检测具有重大现实意义以及应用价值。

Hough变换是圆形检测的常用方法[1-4]，其原理是把图像中的曲线检测问题变成参数空间中的峰值问题，对参数空间中的点进行累加统计，其中累加最大值的参数就是所求圆的参数。Hough变换方法具有可靠性和精度高等优点，但其缺点同样明显，所需存储空间要求大，计算时间长，这使Hough变换很难应用在实际检测中。为解决Hough变换所需存储空间大和计算量大的问题，提出了各种改进方案，随机Hough变换(Randomized Hough Transform，RHT)是针对Hough变换最常用的一种改进算法[5-8]。该算法随机选取图像空间中不在一条直线上的三点，将这三点映射成参数空间中的一点，从而解决了Hough变换一到多映射产生巨大运算量的问题。但对复杂背景图像而言，随机采样仍然会导致大量的无效采样以及无效积累，这会大大降低计算效率[9-10]。

为了进一步提高圆检测速度，本文提出了一种基于随机采样的随机Hough变换快速检测算法。该算法主要从减少随机采样点和利用圆的几何特性两方面来对随机Hough变换进行改进。通过实验验证，本文算法提高了检测效率，在实际生产中有广泛的应用价值。

1 随机Hough变换

随机Hough变换采用随机采样不共线的三个点的方式，计算出对应的圆参数，并且采用多对一的映射方式，判断候选圆存在的条件是积累次数大于阈值，然后通过证据积累去验证候选圆的真实性。

在随机采样过程中，随机选取三个边缘点，设A、B、C这三个点的坐标分别为(x1，y1)，(x2，y2)，(x3，y3)，代入圆方程，由式(1)可得到候选圆的参数(a，b，r)。

其中i=1，2，3。对此圆构成的点进行统计，当统计后的总数达到一定数量后，即认为此候选圆为真圆，否则为假圆。

2 改进算法

在原有随机Hough变换基础上，主要从减少随机采样点和利用圆几何特性来对随机Hough变换进行改进。

2.1 通过随机采样两点和圆几何特性求取圆心坐标和半径

传统RHT算法检测圆时是通过随机采样三个点来确定候选圆的，而这三点位于同一个圆上的概率为

N表示某图像有N个圆，q表示每个圆上有q个点，m表示还有m个非圆上点。

当随机采样的点数越少时，可知位于同一圆上的概率越高，因此减少随机采样的点数可以更容易找到圆，即可通过降低随机采样的点数来减小无效采样率。

在边缘图像上随机采样两点(x1，y1)和(x2，y2)，假设这两点均在候选圆上，根据圆的几何特性可知，在这两点形成的线段的垂直线上一定有圆上的第三点(x3，y3)，如图1所示。

图1 确定侯选圆

由这三点确定候选圆参数(a，b，r)，(a，b)是候选圆的圆心，r是半径。

2.2 通过统计候选圆上的点数判断是否真圆

传统方法为统计候选圆上点的数量。对于图像中的边缘点，求它们到圆心的距离d，如果d近似等于半径r，即|d－r|＜ε(ε为实际计算时留的一些小余量)，则认为该边缘点在圆上。由于图像中所有的边缘点都要计算其到圆心的距离，大大降低了检测速度，故本文对其进行了改进[11]。

由图2可知，候选圆上的点仅可能位于该候选圆的外切正方形与内接正方形之间的区域中(图2中的阴影部分)，不在该区域内的点肯定不在候选圆上，不再计算它们到圆心的距离，而通过减少计算边缘点到圆心距离的次数的方式减少计算量，从而大幅缩减验证耗时。

图2 候选圆上的点所在位置(阴影部分)

候选圆的圆心坐标为(a，b)，半径为r，如果边缘点的坐标(x，y)满足式(3)则认为点(x，y)为候选圆上的点。

令真实圆的阈值Mmin=λ×2πr(其中λ为比例系数，r为候选圆半径)。在验证点到圆心的距离时，若尚未验证的点数为t，当前有效计数为M1，那么只要出现t+M1＜Mmin，便可确定当前候选圆为假圆，不需再对剩余点集进行计算；若当前已经有M1＞Mmin，则可确定当前候选圆为真实圆，也不需再对剩余点集进行计算。这样也减少了很多的距离计算，节省了时间。

3 实验与结果

为了测试本文算法的性能，分别对合成图像和实际图像进行了大量实验。

首先对图像进行预处理，消除图像中的噪声以及增强图像的边缘。然后对预处理后的图像进行边缘检测。本文采用的边缘检测算子为Canny算子，因为与其他边缘检测算子相比，Canny边缘检测算子具有高的检测率和定位精度。最后用随机Hough变换算法和本文算法对边缘图像进行圆检测，再分析数据对比结果。

实验共分为3组。图3为原图像，图4为原图像经过预处理后得到的边缘图像，图5为边缘图像经过本文算法处理后的结果图。

图3 原图像

图4 边缘图像

图5 本文算法结果

从图5中可以看出，场景1和场景2中的圆形目标均能较好地检测出来，但对于场景3这类圆形目标重叠或残缺的场景，均存在一定的漏检和错检，这也是以后我们将要继续研究的方向。

由于算法采样的随机性，每一次运行的时间均不一样。为准确对比算法效率，故对测试图像做50次运算，取其平均值作为算法运行时间。

表1是对图3中的三个场景，用随机Hough变换算法和本文算法检测图像所耗费的时间对比结果。由实验结果可知，本文算法耗费时间明显比随机Hough变换算法耗费时间少，即本文算法在检测速度上有显著提高。

表1 两种算法所耗费的时间

4 结束语

本文提出了一种基于随机采样的随机Hough变换圆形快速检测算法，从减少随机采样点和利用圆几何特性来对随机Hough变换进行改进，在检测速度上有显著性提高。但现实中的场景通常都是复杂的，存在如图像质量一般、光照不均匀、残缺等问题，这使得圆形目标在实际生产检测中具有较大的难度，因此对复杂背景下的圆形检测问题有必要进一步研究，并根据实际应用做出相应的改进。