基于梯度的随机Hough快速圆检测方法(海军大连舰艇学院,辽宁大连116018)摘要：针对随机Hough变换(RHT)在复杂图像中检测圆时产生随机采样的大量无效累积，提出了一种改进的RHT用于圆检测，方法利用梯度方向信息来判定是否对采样到的三点进行参数累积，从而较好地解决了无效累积问题。实验表明改进后的算法比原算法计算速度快，占用的内存小，检测性能有较大提高。关键词：随机Hough变换；圆检测；梯度方向信息??中图法分类号：TP391.4文献标识码：A：10013695(2006)08016402??FastCircleDetectionUsingRandomizedHoughTransformBasedonGradient??WANG激an,WANGXiaotong,XUXiaogang,LIBo（DalianNavalAcademy,DalianLiaoning116018，China）Abstract:TosolvetheproblemofalargeamountofuselessaccumulationsyieldedbyrandomsamplingwhenrandomizedHoughtransform(RHT)isusedtodetectcirclesincompleximages,animprovedRHTisproposed.Itusesgradientdirectioninformationtodeterminewhethertheparametershouldbeaccumulatedornot.IncomparisonwiththebasicRHT,theproblemofuselessaccumulationsiswellsolvedandourmethodhashigherspeed,smallerstorageandbetterdetectionperformance.??Keywords:RandomizedHoughTransform(RHT);CircleDetection;GradientDirectioinFormation检测圆在计算机视觉领域有着广泛的应用前景。Hough变换[1]是检测圆的有效方法，其主要优点为：它对于图像中的噪声点不敏感，用其得到的结果可有效地滤除噪声的影响,以提高结果的可信度；该变换便于并行计算，计算机视觉领域的一些问题相当复杂，需要很大的计算量，并行计算是提高计算速度的有效方法。但传统的Hough变换有几个较大的缺陷：①计算量大，每个边缘点映射成参数空间的一个曲面(有时可简化成一条曲线)，是一到多的映射；②占用内存大；③提取的参数受参数空间的量化间隔制约。为了克服上述缺陷，Xu等人[2,3]提出了随机Hough变换(RandomizedHoughTransform,RHT)，在图像空间随机选取不共线的三个点映射成参数空间的一个点，是多到一的映射，从而避免了传统Hough变换一到多映射的庞大计算量。为了降低内存需求，采用动态链表结构，只对多到一映射所得到的参数分配单元进行累积，从而与传统Hough变换相比,降低了内存需求，同时使RHT具有参数空间无限大、参数精度任意高等优点。尽管RHT只对多到一映射所得到的参数分配单元进行累积，但在处理复杂图像时，由于随机采样仍引入大量的无效单元，从而造成了大量无效累积。为此，本文提出一种改进的RHT用于圆检测。1圆检测的RHT用于圆检测的算法描述如下:设D为图像空间的边缘点集,P为参数空间的参数单元集,它是一个动态链表结构。设参数单元的计数值为score,当参数单元pc的score达到指定阈值Nt(它是一个很小的数,如2、3)时,pc(本文用相同的符号表示参数单元和它对应的参数)对应的圆成为候选圆,判断图像空间中落到该候选圆上的点数Mpc,若其大于圆所允许的最小点数Mmin,则确认该候选圆为真实圆,记下该圆并继续进行下一个圆的检测。当检测到的圆已达到规定的数目时,结束检测过程;若事先不知道圆的个数,则可规定检测一个圆过程中所允许随机采样的最大循环次数Kmax,当采样次数已大于Kmax,而参数单元点集P中仍没有参数单元的score达到指定的阈值Nt时,则认为Hough变换已不能检测到更多的圆而结束。算法的具体步骤如下:??2圆检测的改进RHT(RHT+)尽管只对多到一映射所得到的参数分配单元进行累积,但在处理复杂图像时,随机采样仍然会引入大量的无效单元,造成大量无效累积。例如，某图像包含N个大小(圆的大小是由圆上的点数来衡量的)为q的圆,另外还有n个非圆上的点,则随机采样所得三点落在同一圆上的概率为由式(2)可知,当图像中仅有同样大小的圆时,随机采样三点落在同一圆上的概率与圆数目的平方成反比,圆数目越多,三点落在同一圆上的概率就越小,这意味着产生无效累积的概率就越大。对于仅有五个圆的图像,其无效采样的概率为24/252。另外,由式(1)知,非圆上的由式(2)可知,当图像中仅有同样大小的圆时,随机采样三点落在同一圆上的概率将越小,产生无效累积的概率也就越大。??可...