一种用Hough变换检测圆的快速算法摘要:为了克服传统Hough变换检测圆时耗时巨大的缺陷,给出了一种新的基于Hough变换检测圆的快速算法新算法与传统的方法相比具有以下特点｡:计算量少,提高了检测的速度;保留了传统Hough变换识别率高抗噪性强对不完整边缘具有鲁棒性等所有优点､､;不需要任何特殊的限定条件实验表明｡,新的快速算法可以快速进行目标识别,在实时目标识别系统中具有良好的表现关键词｡:目标识别;霍夫变换;圆的检测;快速算法:TP317文献标志码:A:1001-3695(2007)10-0197-03??0引言??在日常生活和军事应用中,在不同视角下,许多物体以类似圆的形状出现,准确而有效地检测出这些圆形物体在图像中的位置就成为图像分析的一项重要工作在应用中经常采用的一种方法就是｡Hough变换或其改进算法｡Hough变换是PaulHough在1962年提出的一种图像边缘检测技术,它可以检测图像空间中的任意解析曲线[1]｡Hough变换以其对局部缺损的不敏感对随机噪声的鲁棒性以及适于并､行处理等优良特性,备受图像处理模式识别和计算机视觉领域学者的青睐､｡Hough变换的突出优点就是可以将图像中较为困难的全局检测问题转换为参数空间中相对容易解决的局部峰值检测问题然而利用传统的｡Hough变换检测图像中的圆时,所需的计算量非常大检测､速度慢,需要研究新的快速方法到目前为止｡,对Hough快速算法的研究主要集中在四个方面:对解析曲线方程进行变形来减少计算的复杂性[2];利用曲线的某些特殊性质来简化计算[3];通过减少累加器空间的维数来减少运算所需的存储空间[4];利用相位信息来减少计算量[5]但这些算法在实际应用中往往具有较大的局限性或要求的条件比较苛刻｡,不能适应一般情况如对解析曲线方程进行变形来减少计算复杂性的算法需要精确计算出边缘点｡的方向信息;利用曲线的某些特殊性质的算法在某些特殊情况下不能正常识别目标,如圆的边缘提取出来不到3/4圆周时;通过减少累加器空间的维数来减少运算所需的存储空间只是减少运算时所需的存储器空间,并不能减少算法的运算时间;利用相位信息的算法的抗噪性能不如传统算法[1]本文在｡Duda提出的传统Hough变换思想的基础上,结合坐标平移的知识提出了一种新的用Hough变换检测圆的快速算法新算法可以较显著地提高检测速度｡,不需要任何限定条件;新算法需要与传统算法一样大小的累加器空间｡??本文介绍了Hough变换的原理,提出了用Hough变换检测图像中圆的快速算法及计算量的分析｡??1Hough变换原理??Hough变换检测圆的基本思想是将图像空间中的边缘点映射到参数空间中,然后将在参数空间中得到的所有坐标点元素对应的累加值进行累加统计,根据累加值判断圆的大小和圆心所在位置在笛卡尔坐标系下圆的方程为｡??3实验结果与分析??为了验证新算法的可行性和识别效果,分别用Duda提出的传统Hough变换算法[1]和本文所提出的新算法进行了目标识别实验对比系统运行主机为｡PC机,CPU为IntelP4主频､1.8GHz,内存512MBDDR333MHz,标准C++代码源程序｡??3.1合成图像检测实验??合成图像为无噪声图像序列,如图2所示,序列共有47张图,合成图像分辨率为800×600,图像序列中第??N+1张图比第N??张图多一个半径为随机大小的圆在本次试验中｡,圆的半径限定最小为20个像素,最大为40个像素识别结果如图｡3所示第一组比较实验为比较改进后的新算法相对于传｡统算法提高的倍数｡??从图3(a)可以看出,本文提出的新算法与传统Hough算法相比速度有了很大的改善,并且对目标的检测效果也很显著在速度方面｡,第一组实验新算法的平均速度比传统算法的平均速度高6.5倍左右,最高为6.7775在检测效果方面｡,新算法和传统Hough算法的总体检测率均为99.82%,新算法的检测序列中仅有第21､24两帧各有一个圆未检测出来,原始Hough算法同样也未检测出这两帧中的这两个圆,并且传统Hough算法的检测序列中也仅仅是这两个圆未检测出新算法的检测序列中检测出的圆的坐标与圆的真｡实坐标最大相差两个像素以上两点表明改进的快速算法相对于传统｡Hough算法不仅可较高地提高检测速度,而且具有较强的目标识别性｡??3.2实际图像的目标识别??在实际图像中,圆形物体的形状绝大多数情况下并不是标准的圆,而且实际图像中...