基于Hough变换运用形状角及梯度检测圆

方 菲，耿春明

（北京航空航天大学 机械工程及自动化学院，北京 100191）

0 引言

常见几何图形的识别是机器视觉中非常重要的一项任务，其中圆形的快速准确检测在图像处理中占据着重要地位。常用的检测圆算法［1］主要有Hough变换（CHT）［2］及相应改进算法、环路积分微分法、最小二乘拟合算法和遗传算法等。其中应用最广的是Hough变换及相应改进算法。Hough变换的基本原理［3］是将图像空间中具有某种关系的像素变为参数空间的聚焦点，并通过判断参数空间的各个聚焦点的累积程度来完成这种给定关系的特征曲线检测。Hough变换对图像的噪声不敏感，有较好的鲁棒性，但当参数空间的维数达到或超过3时，这种方法的计算时间和存储空间都会变的很大。圆的参数空间为三维：圆心（a，b）、半径r，因此在实际应用中这种方法不适合用来检测圆。针对上述问题，结合轮廓线的形状角特征及梯度信息，本文提出了一种新的基于Hough变换检测圆的改进算法，最终可以准确并且快速地得到检测结果。

1 相关理论

在图像空间检测圆中，广义Hough变换是通过在全图所有边缘像素点中随机采样来确定候选圆，但因为存在噪声点、非圆形形状的边缘点等各种无效采样，导致大量的候选圆为假圆。本文首先利用形状角这个几何不变量来判断轮廓线是否为圆形，剔除噪声点以及非圆形边缘轮廓点等无效采样点；然后再通过保留下的轮廓线的梯度信息来确定候选圆，利用梯度信息可将检测圆轮廓的累加矩阵从三维转变为二维；此外，确定候选圆后，在对边缘点进行证据积累（Evidence Collecting，EC）时，由于圆必定在其外接正方形之内，因此可不必考虑位于候选圆外接正方形之外的边缘点［4］，以此减少算法的计算量，提高检测圆的速度。

［5］定义形状角Sθ为：

其中：mi为轮廓上每一点与该轮廓质心的连线；gi为轮廓上每一点的法向量；αi为mi和gi的夹角；n为轮廓边缘点的总个数。

圆有如下性质：

性质1：根据圆形的质心就是圆心可知，理想圆的形状角Sθ为0°。

性质2：根据圆的性质——圆的切线垂直于过切点的直径可知，圆心在圆上任意一点的法线上。对于图像上的每一个在圆上的边缘点，加上它的梯度信息（方向信息），就可确定一条直线，圆的圆心就在这条直线上。

性质3：假设已确定候选圆Oij（圆心为（aij，bij）、半径为rij），为检验候选圆是真圆还是假圆而进行证据积累时，可不考虑位于此圆外接正方形之外的边缘像素点，即对于边缘点（xm，ym）（（xm，ym）∈U，其中U是图像空间中所有边缘像素点的集合），当xm＞aij＋rij或xm＜aij－rij或ym＞bij＋rij或ym＜bij－rij时，则不再对（xm，ym）进行证据积累。

2 算法描述

2.1 算法基本思想

为降低噪声影响，首先对给定的原始图像进行预处理，主要是采用中值滤波对图像进行平滑处理；然后采用Canny算子对预处理后的图像进行边缘检测并记录轮廓线的梯度信息，为了不盲目投票，先依据上文所述的性质1对检测出的边缘轮廓线进行初步分类，剔除形状非圆形的边缘轮廓，只保留形状为圆形的轮廓线；接着再利用保留下的轮廓线的梯度信息根据性质2初步确定圆心和半径；最终运用证据积累的方法精确定位圆的位置。

根据式（1）计算图像上所有边缘轮廓的形状角Sθ，当某一段轮廓的形状角满足Sθ≤ε（ε为给定的一个很小的值）时，可以认为该轮廓的形状为圆形，则保留此段边缘。经过该步骤后，可以过滤掉一些形状为非圆形的边缘轮廓，只保留形状为圆形的边缘轮廓，即可过滤复杂背景下的一些干扰物体，从而提高检测速度。

常见的生物措施。在茄子种植中，可以根据当地的实际情况、自然环境，选择抗病虫害的茄子种子，避免出现病虫害；在病虫害的预防中，可以先使用化学药水浸泡种子，使种子能够抗病虫害；在选择茄子种子时要选择种粒饱满、质量高、无病虫害的种子。

由式（4）初步解出圆心坐标（xo，yo），由此坐标与轮廓上任一个边缘点可初步求出半径r，这时该圆形的位置已大致确定。下一步利用证据积累的方法精确定位此圆形轮廓的位置。在初步解出的圆心坐标与半径的基础上，分别给定一个圆心和半径的变化范围to和tr，使得圆心坐标和半径分别在［xo－to，xo＋to］，［yo－to，yo＋to］，［r－tr，r＋tr］范围内变换。采用证据积累法累计出在每一种情况确定的圆上有多少点是位于边缘轮廓上的，找出具有最多边缘点的圆，此时求得的圆的位置便是精确定位的。在进行证据积累时，根据性质3可知，只需验证位于圆外接正方形内的边缘点即可，不必遍历全图的所有边缘点，这样可提高检测速度。

2.2 算法步骤

具体算法流程如图1所示。

图1 算法流程图

算法中主要有3个步骤：利用形状角分类轮廓边缘线、采用保留下的轮廓边缘线初步确定圆心和半径、精确定位圆位置。前两个步骤的程序实现过程主要依据算法原理中的公式进行，第三个步骤的程序实现主要过程如下：

循环所有情况，iNumOfCircle表示为在每一种情况下既在圆上又位于边缘轮廓上的元素个数。记录当iNumOfCircle值最大时的半径及圆心位置，此时求得的圆即是最终确定的圆位置。

3 实验

本文中的算法在Windows XP操作系统、Microsoft Visual C＋＋6.0平台上实现，实验中所采用的图像大小为480×640、灰度为256，实验图像及其检测结果如图2、图3所示。

图2 实验图像1及其检测结果

图3 实验图像2及其检测结果

图2的检测时间为42ms，图3的检测时间为57 ms。从检测结果图像（将检测到的圆在图中用白线沿边缘圈出）可以看出，本文提出的算法能较准确地找到圆的位置；从检测算法所耗费的时间可以看出，此算法能较快速地得到检测结果。

通过对实际应用中图像的测试，证明此算法具有较好准确性、快速性及鲁棒性。

4 结语

广义的Hough变换有计算时间长或存储空间大等问题，为解决这些问题，一些基于Hough变换的改进方法常利用导数信息或梯度信息，但当背景复杂或受噪声干扰影响较大时，导数或梯度信息会十分敏感，所以仅仅利用导数或梯度信息可能会导致误检或漏检。所以在本文提出的这种计算方法中，不仅结合梯度信息，也结合了形状角这一几何不变量特征。因为形状角只与轮廓的形状有关，所以对噪声或复杂背景的敏感度较小。这样在解决了时间和空间复杂度高问题的同时，也保证了算法对干扰噪声或复杂背景的敏感程度，也就是说本文介绍的结合轮廓线形状角及梯度信息的Hough变换检测圆的改进算法不仅提高了圆检测速度，也具有较好的鲁棒性。

［1］王敏，李启堂，丁书斌.单参数Hough变换实现圆检测方法的研究［J］.机械设计与制造，2007（7）：61－63.

［2］Illingworth J， Kittler J. A survey of the Hough transform［J］.Computer Vision Graphics and Image Process，1988，44（1）：87－116.

［3］赵小川，何灏，缪远诚.MATLAB数字图像处理实战［M］.北京：机械工业出版社，2013.

［4］陈爱军，李金宗，李东东.一种改进的随机圆检测算法［J］.光电工程，2006，33（12）：91－95.

［5］秦开怀，王海颍，郑辑涛.一种基于Hough变换的圆和矩形的快速检测方法［J］.中国图像图形学报，2010，15（1）：109－115.

［6］崔继文，谭久彬.基于梯度信息的随机 Hough变换圆轮廓测量技术［J］.红外与激光工程，2006，35（增刊1）：419－424.

［7］陈星.一种基于梯度Hough变换的同心圆检测新方法［J］.技术纵横，2011（7）：86－89.