基于圆对称性和随机选点改进霍夫变换圆检测算法

张汝祥 陈德林 季江伟 张伟昕

摘  要：为了解决使用传统Hough变换圆检测算法存在计算量大、运行效率低以及检测精度不高等问题，文章提出了一种基于圆对称性和随机选点改进Hough变换圆检测算法。首先，根据圆对称性特点，求解出圆心坐标;然后，将圆心坐标回代入圆方程，求解出半径。为了增强抗噪能力，随机选取圆周上一定数量的边缘点进行求解，统计半径值，选择频数最高的半径值作为最终结果。在MATLAB环境中开展圆检测仿真实验，结果表明，提出的方法可以有效地提高圆检测精度。

关键词：霍夫变换;圆检测;MATLAB

中图分类号：TP391.4 文献标志码：A         文章编号：2095-2945（2019）14-0041-03

Abstract： In order to solve the problems of large computational complexity， low running efficiency and low detection accuracy using the traditional Hough transform circle detection algorithm， an improved Hough transform circle detection algorithm based on circle symmetry and random point selection is proposed in this paper. Firstly， according to the characteristics of circle symmetry， the center coordinates are solved; then， the center coordinates are replaced into the circle equation， and the radius is solved. In order to enhance the anti-noise ability， a certain number of edge points on the circumference are randomly selected to solve， the radius value is counted， and the radius value with the highest frequency is selected as the final result. The simulation experiment of circle detection is carried out in MATLAB environment. the results show that the proposed method can effectively improve the accuracy of circle detection.

Keywords： Hough transform; circle detection; MATLAB

引言

Hough变换是图形检测处理中的方式之一，它通过图像空间与参数空间的点-线的对偶性，从而可以将空间中的检测问题转换成参数空间的检测问题。它可以有效的提取直线、曲线、圆甚至是其他任何形状的边缘。因为机器视觉有效率高、速度快、成本低可重复利用等优点，广泛应用于各个领域。标准Hough变换算法及其优化算法大量被應用于机器视觉中。由于Hough算法的参数空间是三维空间，很多情况下运算数据量大，占据内存多，目前的一些改进算法[1-5]主要是同对Hough变换进行降维处理，但是对于小于8像素的圆很难检测。因此本文用一种改进的单圆检测算法，提高了检测效果的准确率，使操作更加简单化易于实现。

1 标准Hough变换耗时分析

传统的圆检测算法一般是基于Hough变换[6-9]来求解的，所以标准的Hough变换算法中存在运算量大、运算速度慢等缺点，也会被引入到计算。圆的Hough变换中有圆心坐标a、b和半径r，存在3个未知参数，这就意味着需要对圆的所有边缘点进行三重积分，才能够求解出一个标准的圆，Hough计算量大的问题成为制约这种算法发的瓶颈，导致在实际过程中Hough很难被实现和运用起来[10-11]。

在笛卡尔坐标系中，圆的方程是：对参数空间进行量化，得到一个三维累积矩阵，用于记录（a，b，r），当我们在检测图像空间中的圆的时候，先用边缘检测算子，检测出圆的边缘信息，然后再计算边出与边缘上每个点距离是r的所有的点（a1，b1），然后记录下（a1，b1，r）。改变r值的大小然后再重复进行以上计算过程，当计算完所有的边缘点之后，对所有的数据值进行累计排序，累计出数据最多的一组数值就认为对应的是图像空间中圆的圆心。

假设有n个边缘点，本文中提到的图像n通常大于2000，所以总时间t的系数大于10到6次方。这么庞大的计算仅仅是其中的一个环节，它需要大量的运行时间和存储空间，因此需要改进Hough转换以提高效率。传统的Hough变换是根据Hough变换的定义进行的。虽然它有许多明显的缺点，但它经常可以作为改进算法的参考对象。

2 基于圆对称性的改进Hough变换算法

2.1 求取圆心坐标

2.2 求解圆的半径r

2.3 改进Hough算法检测单个圆检测仿真

（1）图像读取与处理。实际中我们拍的照片是彩色的，而在运算中需要的是二值图像。所以我们先通过函数imfinfo（）读取输入的图像，然后再通过函数edge（），将彩色图像转换成我们需要的二值图像。

（2）计算中点值。先用水平直线从左到右进行扫描，记录下扫描后计算出来的中间点坐标。同理，再用铅直线从左到右进行扫描，记录中间值。

（3）数据处理。累积中值，找出现频率最高的数据。可以利用MATLAB中的tabulate（）函数，创建数据表记录中间点，Rx=tabulate（X）;其中X表示计数器。[～，h]=max（Rx（：，2））;找出第二列中的最大值所在行（第二列是频数）。A=Rx（h，1）;找出第一列的频数值（表的第一列为原始数据）。

（4）记录圆心坐标。

（5）在圆周上随机取一定数目点边缘点，代会圆的方程，来求取圆的半径值r，并进行数据记录。

（6）对记录的半径数值进行统计处理，去除极值，然后求去半径的平均值。

（7）可以使用参数法x=r·sinθ+cx;y=r·cosθ+cy;对圆进行打印。

2.4 MATLAB检测成果

3 结论

结合先前的研究知识，提出改进的算法，本算法在一定程度上解决了传统Hough变换存在的计算量大耗时多的缺点。通过MATLAB实验的验证，可以简单快捷的解决单个圆的检测问题，虽然检测条件比较局限，但是可以很高效的对圆进行检测提取，效率和精确度得到了很大的提高，在实际工业生产中有廣泛的应用的价值。

参考文献：

[1]王宪，赵前程，谭建平.应用区域估计的复杂背景多圆快速定位方法[J].中南大学学报（自然科学版），2016，47（07）：2266-2272.

[2]陈珂，吴建平，李金祥，等.一维概率Hough变换的实时鲁棒多圆检测方法[J].计算机辅助设计与图形学学报，2015，27（10）：1832-1841.

[3]蔡佳，黄攀峰，张彬.基于梯度的区域生长和距离直方图的快速圆检测方法[J].光学学报，2015，35（03）：193-202.

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

[5]叶峰，陈灿杰，赖乙宗，等.基于有序Hough变换的快速圆检测算法[J].光学精密工程，2014，22（04）：1105-1111.

[6]Yi W， Marshall S. Circle detection using Fast Finding and Fitting（FFF）algorithm[J]. Geo-Spatial Information Science， 2000，3（1）：74-78.

[7]Ji Yu Shan Yuekang Zhang Zhi Pan Zisheng （China JiLiang University， Hangzhou 310018 China）. An Algorithm for Concentric Circles Detection Based on Least Squares and Cluster Analysis[A].中国电子学会.ICEMI'2005第七届国际电子测量与仪器学术会议论文集[C].中国电子学会，2005：4.

[8]Hanahara K， Hiyane M. A circle-detection algorithm simulating wave propagation[J]. Machine Vision and Applications， 1991，4（2）：97-111.

[9]蒋联源.Fast detection of multi-circle with randomized Houghtransform[J].光电子快报：英文版，2009，5（5）：397-400.

[10]张翼，孙永荣，王艳，等.圆形目标实时检测的改进算法研究[J].计算机与数字工程，2040（3）.

[11]浮红霞，陈西平，毛慧珍，等.一种非Hough变换的快速圆检测算法[J].河南理工大学学报（自然科学版），2010，29（4）.