改进的Hough变换圆检测算法

尚璐，李锐，宋信玉

（重庆大学光电技术及系统教育部重点实验室，重庆400030）

快速而准确地检测出圆及其参数是计算机视觉和模式识别中的一项重要研究内容，在机器视觉自动测量系统、智能检测等领域有着广泛的应用前景。标准Hough变换[1]（Standard Hough Transform，SHT）检测圆是一种最传统的检测算法。它的最大优点是：对噪声不敏感，检测后可有效去噪；而且在圆变形，甚至部分区域丢失的情况下仍然可以得到比较理想的结果。

Hough变换的基本思想是将图像空间中具有一定关系的像元进行聚类，寻找能把这些像元用某一解析形式联系起来的参数空间累积对应点。但由于圆有3个自由参数，需在三维参数空间中进行累积，使得这种做法因计算量和内存需求量过大而不合实际。为了克服这些缺点，XU[2-3]等提出了随机Hough变换（Randomized Hough Transform，RHT），在图像空间随机地选取非共线的三个点映射成参数空间的一个点，是“多对一”的映射。当用RHT处理简单图像时，它表现出相当优异的性能，但在处理复杂图像时，由于随机采样引入大量的无效采样和累积，使算法的性能下降。为此，很多学者提出了改进的RHT算法。如：利用圆内接直角三角形长边过圆心的性质[4]，对圆参数进行求解；以随机采样到的2个图像点及在此两点的中垂线上搜索第3个图像点来确定候选圆[5]；利用圆边缘上各点梯度所在的直线过圆心的特点，对选取的任意三点进行约束[6]。它们都有效的减少了“多对一”映射的计算量，同时使用动态链表结构降低了参量分配空间，但随着圆和噪声的增多，随机采样的无效累积增多，性能将大大降低。……