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

【摘 要】为解决现有随机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变换圆检测算法上测试取得很好的速度提升，但是对于单圆和极端情况下加速效果并不明显。……