KRA：一种双阶段精确圆检测算法

代巍 沈云啸 谢宁 何道聪 马亚东

【摘 要】为解决现有随机Hough变换（RHT）圆检测算法存在的无效积累严重问题，提出一种基于k-means聚类算法和随机Hough变换（RHT）圆检测算法的双阶段圆检测算法（KRA）。所提出的KRA由k-means聚类算法和RHT圆检测算法两部分组成。k-means聚类算法负责对边缘点进行聚类，得到每一类边缘点额范围。在此基础上，RHT圆检测算法对区域内的点进行检测，最终得到圆的参数。实验表明，提出的KRA能检测到所有圆，并且算法的聚类和检测时间只占RHT圆检测时间的25.2%～67.8%，即采样积累减少25.2%～67.8%，从而证明了文章提出的算法在减少无效采样方面的有效性。

【关键词】圆检测;感兴趣区域（ROI）;k均值聚类;随机Hough变换;小范围随机采样

【中图分类号】TP391.41 【文献标识码】A 【文章编号】1674-0688（2021）03-0040-03

圆检测是计算机视觉领域的常见方向，被广泛应用于工程实践项目。Hough变换圆检测 [1]是最基本的检测方法，其原理是把曲线由图像空间中映射到由圆的3个参数构成的参数空间，累加统计参数空间的点，最大累加值的参数即为所求圆的参数。但该算法存在很多不足之处，在参数量、计算量和内存占用方面有很大的改进空间。针对上述不足，Xu L等人 [2]提出使用随机Hough变换做圆检测，该方法在图像空间中随机选取不共线的3个特征点，映射成参数空间中的一个点，是多到一的映射，大大减少了计算量，但是在图像复杂的情形下，由于噪声较多，从而引入大量的无效采样，增加迭代次数，降低检测效率 [3]。随后，有很多改进的算法被提出，周勇亮等人 [4]提出一种有效继承的累计加速算法，每次成功检测圆后不清空参数空间，在随机Hough变换圆检测算法上测试取得很好的速度提升，但是对于单圆和极端情况下加速效果并不明显。Chen等人 [5]在随机Hough变换的基础上进行了改进，使用第4个随机采样点判断是否在候选圆上，随后再验证圆的真伪，提高了圆的检测速度。

除此之外，还有许多学者从不同的角度改进圆检测算法，如在Hough变换的基础上结合梯度信息 [6]，运用圆的几何属性做圆检测 [7]及使用图像的直方图 [8]作为评判依据，这些措施都取得了不错的提升。

文中提到的改进算法是基于随机Hough变换（RHT）圆检测算法进行，虽然大幅提高了算法检测效率，但是仍存在漏检及无效积累等严重问题。为了改善这一问题，本文提出了一种基于k-means聚类算法和随机Hough变换圆检测结合的新的圆检测算法，通过结合两种算法的优点，对采样空间进行约束，大大减少了无效采样并降低了圆的漏检率。

1 传统的随机Hough变换圆检测

在平面直角坐标系中，圆的標准方程如下：

其中，（a，b）为圆心坐标，r为圆的半径，（a，b，r）为圆的3个参数，分别是圆心坐标和半径。随机Hough变换（RHT）圆检测算法需要在边缘点集合中随机采样3个点（x1，y1）、（x2，y2）、（x3，y3），再将随机选取的3个点代入圆的方程中，可以得到如下方程组：

求解以上方程组可求得圆的3个参数（a，b，r），即圆心坐标和圆半径。然后计算边缘上的其他点到圆心的距离d，并与所得参数r进行比较，若满足|d-r|≤δ，δ为设定的误差阈值，则该圆为候选圆。否则，重新采样。随后将其他边缘点执行相同的过程，并统计在预设误差范围内的边缘点的个数，当边缘点个数累积达到设定阈值时，确定该圆为真实圆;否则，重新采样。重复上述步骤，直至所有的真实圆检测完成，或者是重复次数达到最大迭代次数。

2 本文的KR圆检测算法

本文的圆检测算法主要分为两个部分：一是通过k-means聚类算法对边缘点进行聚类，得到每个圆的ROI;二是在每个圆的ROI基础上采用随机Hough变换算法检测圆，从而得到多个圆的圆心和半径。

2.1 边缘点聚类

在工程实践中，工程背景相对复杂，在复杂环境拍摄的图像存在不同程度的噪声，导致检测过程中的计算量剧增。为了缓解上述复杂背景问题，首先对圆所在区域进行提取。通过对原始图像进行一系列预处理，包括灰度化和中值滤波处理，减少了随机噪声对后期处理的影响;对滤波后的图像进行Canny边缘检测，得到二值图像，并收集所有边缘点构造边缘点集;对边缘点的数据采用k-means聚类算法进行聚类，方法描述如下。

（1）在边缘点集中随机选取k个点作为初始聚类的簇心。

（2）分别计算每个样本点到k个簇心的距离（本文取欧式距离），找到离该点最近的簇核心，将它归属到对应的簇。

（3）所有点都归属到簇后，边缘点就被分为k类。之后重新计算每个簇的中心，将其定义为新的簇核心。

（4）反复迭代步骤（2）和（3），直到达到某个中止条件。

2.2 ROI分区独立采样

传统的随机Hough变换（RHT）圆检测算法是在当前所有边缘点中随机采样3个点，但是在多个圆的情况下会有大量无效采样。为缓解以上无效采样问题，本文提出分区采样的方法。通过k-means聚类算法对边缘点进行聚类，每个圆的边缘点都有属于本身的聚类中心，再以此聚类中心点为中心，做一个可以囊括该类所有中心点的正方形，作为该圆的ROI。采样时，只在该类边缘点所在的ROI区域内部采样，大幅度提高采样效率，减少无效采样。具体步骤如下。

（1）以聚类算法得到的k个点作为中心，分别以该类中距离中心点最远的点到该中心的距离为半边长，得到该类边缘的区域边框，即该圆的ROI。

（2）在圆对应的ROI区域内分别随机采样3个边缘点，并确保3点不共线。

（3）将采样得到的边缘点代入公式（5）、公式（6）、公式（7）计算圆的参数。

其中，（a，b，r）分别为圆的横纵坐标及圆心。

2.3 真圆的判定

通过统计位于候选圆上的边缘点数目，对候选圆进行判断，即如果边缘点位于该候选圆的圆心距离等于半径，则认为边缘点在候选圆上，否则，边缘点不在候选圆上。

考虑到数字化误差，应留有一个小余量，判断边缘点是否在候选圆上应满足公式（8）。

其中，（xe，ye）是边缘点坐标，（a，b）为候选圆圆心坐标。

将统计的位于候选圆上的边缘点数目与判定为真圆的相关阈值进行对比，从而确定候选圆的真假性，若候选圆上的边缘点数目大于等于判定阈值，则候选圆为真圆，否则，候选圆不是真圆。即

Ne≥NT 候選圆为真圆other   候选圆为假圆 （9）

其中，Ne为统计得到的在候选圆上的边缘点，NT为设定的数量阈值。

3 试验验证与结果分析

为了验证本文算法的检测效果，我们采用多幅合成图像进行测试，并与RHT圆检测算法在检测时间和检测精确度上进行比较。实验目的是通过圆检测算法实现在对图像中圆的精确检测，实验所用计算机处理器为Intel（R）Core（TM）i5-4210M CPU @2.6 GHz，8 GB RAM，运行环境为Python 3.6。

3.1 圆的ROI区域获取

对原图像1（a）进行灰度化和Canny边缘检测，得到如图1（b）所示的边缘图像，采用k-means聚类算法对所有的边缘点进行聚类处理，从而得出k个聚类中心，在此基础上按照ROI分区独立采样方法获得圆的ROI（如图2所示）。

3.2 试验结果对比

首先利用圆的ROI区域获取方法获取圆的ROI，在每个圆的ROI内分区独立采样，然后分别采用随机Hough变换圆检测算法对每个ROI进行圆检测，使用的图像如图3所示，本文对图像的检测效果如图4所示，算法各环节耗时见表1，与传统的随机Hough变换圆检测算法对比，检测时间见表2，算法运行时间与圆个数的关系如图5所示。

本文算法与RHT算法在不同个数的合成标准圆的图像上（如图3所示）进行比较，从试验结果可知，本文提出的KRA在总的检测时间上比RHT略高（如图5所示），经过实验对比分析KRA算法的各个关键环节（见表1），其中前处理耗时最长，在4张测试图像中占比分别为77.69%、69.50%、64.46%和56.27%。纵向比较前处理时间占比可以发现，随着圆个数的增加，处理时间增加幅度很小的同时，在整个算法的占比不断减小。从图5可以看出，KRA的主要部分即聚类和圆检测时间一直低于直接RHT算法的检测时间，可以得知，KRA缩小了随机采样的像素空间，成功地缓解了RHT圆检测无效积累严重的问题。

3.3 算法性能分析

通过以上实验结果和实验数据表明，本文提出的方法在多个圆同时存在的情况下具有优势。通过对圆的ROI提取，很好地解决了由于边缘点数量大带来的无效采样剧增的问题;ROI分区采样是完全随机采样和约束采样的一种折中方法，既能将所有的边缘点分区，又能在ROI内实现局部随机采样，大大减少无效采样积累，提高圆检测速度。

4 结语

本文提出的多圆检测算法结合了k-means和随机Hough变换圆检测算法的优点，既能将所有边缘点进行ROI分区，又能在ROI内随机采样，提高了采样的有效性。试验结果证明，本文提出的方法在速度上比传统的随机Hough变换圆检测算法更有优势，尤其是在圆个数较多的情况下优势非常明显。但是本文算法仍然存在不足，在使用k-means聚类算法对边缘点进行聚类时需要指定k值的大小，即圆的个数，从而一定程度上限制了算法的适应性。因此，后续还需要对算法进行改进和研究。

参 考 文 献

[1]Smereka M，Duleba I.Circular object detection us-ing a modified Hough transform[J].International Journal of Applied Mathe matics and Computer Sc-ience，2008，18（1）：85.

[2]XU L，OJA E，KULTANEN P.A new curve detec-tion method：randomized Hough transform（RHT）[J].Pattern Recognition Letters，1990，11（5）：331-338.

[3]何奎.基于图像处理技术的圆环零件检测方法研究 [D].大连：大连理工大学，2017.

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

[5]Chen The-Chuan，Chung Kuo-Lian.An efficient ra-ndomized algorithm for detecting circles[J].Comp-uter Vision and Image Understanding，2001，83（2）：172-191.

[6]Kimme C，Ballard D，Sklansky J.Finding circles by an array of accumulator[J].Commun.ACM，1975，18（2）：120-122.

[7]Huang YH，Chuang KL，Yang WN，Chiu SH.Effi-cient symmetry-based screening strategy to speed up randomized circle-detection[J].Pattern Recog-nition Letters，2012，33（16）：2071-2076.

[8]Yuan B，Liu M.Power histogram for circle detect-ion on images[J].Pattern Recognition，2015，48（10）：3268-3280.