结合多阶段优化的圆检测算法*

蒋联源 王智文 李春贵 孔凡福 邓向姣

(1．南京航空航天大学自动化学院，南京，210016；2．广西科技大学计算机科学与通信工程学院，柳州，545006；3．柳州市广播电视台，柳州，545006)

引 言

圆的检测是计算机视觉、模式识别中的一个重要研究内容[1-3]。由于圆检测能应用于许多工业应用中的圆形目标定位，因此最近几十年从数字图像中检测出圆已得到研究人员的广泛关注。众所周知，Hough变换是圆检测的常用方法，主要优点表现为：能较好地适用于具有噪声的图像中，以及容易实现并行计算。由于Hough变换用于圆检测时所需的计算时间和存储空间过大，许多改进的Hough变换被提出[4]。其中Xu等[5,6]提出的随机Hough变换(Randomized Hough transform, RHT)是对Hough变换的重大改进。该方法首先从边缘点集中随机选取3点，通过这3点确定一个圆参数；判断这个圆参数是否与链表中某个参数单元的值近似相等，如果均不近似相等则新建该圆参数单元并插入到链表中的适当位置，否则将该参数单元的计数加1；若计数不小于事先规定的阈值nt则找到了一个候选圆，然后通过证据积累进一步判断该候选圆是否为真圆。与Hough变换相比，RHT具有存储空间需求小、快速、无限的参数空间和任意高的检测精度的优点。尽管对于简单图像的检测，RHT有着非常高的检测效率，但是对于较为复杂的图像，RHT的效率也会受到很大影响，因为在图像中的随机采样导致了采样有效率的明显偏低。因此研究人员相继提出一些RHT的改进与扩展算法[7-11]。如黎自强等[7]在寻找用于计算候选圆的圆参数的3个点时，先随机采样2点，然后在这2点的中垂线上寻找第3点，以提高采样有效率；……