基于中点画圆算法的hong变换检测圆的新方法

基于中点画圆算法的hong变换检测圆的新方法

直线、圆（圆）、圆等平面曲线是机械零件图像的主要元素。在机械零件二维几何特征检测工作中,首先要进行机械零件图像的边缘检测,在获取图像边缘离散点信息后,再进行直线、圆(圆弧)、椭圆或其它平面曲线等几何特征的检测。其中,圆形特征检测无疑是机械零件二维几何特征检测的重要内容。Hough变换是目前应用较为广泛的圆检测方法,该方法最大特点是可靠性高,在噪声、变形、甚至部分区域丢失的状态下仍能取得理想的结果,但直接采用Hough变换检测圆,存在需要频繁地进行开平方或三角运算等缺陷,计算量比较大。目前,Hough变换已发展出几种改进方法,如随机Hough变换、梯度Hough变换等,但仍存在会产生大量无效累积、数字化量化误差大等问题。中点画圆算法是一种高效的画圆算法,但目前只用于画圆方面的研究,尚未见到用于Hough变换检测圆的研究。本文将中点画圆算法与Hough变换相结合,提出一种基于中点画圆算法的改进Hough变换检测圆的新方法。该新方法具有运算速度快,占用内存小,检测结果准确等特点,可用于对自动生产线上被加工机械零件的圆形几何特征进行实时在线检测,确保零件的加工质量。1标准hock变换检测圆的计算标准Hough变换检测圆的基本原理是:设半径为r0,圆心坐标为(a0,b0)的圆的表达式为对于原图像中的每一点(xi,yi),在参数空间中对应一个三维直立圆锥,其表达式为其中a、b、r为参数空间中的3个变量。对于图像空间中的半径为r0,圆心坐标为(a0,b0)的圆上的点集,在参数空间中对应一簇三维圆锥面,它们交于一点(a0,b0,r0),如图1所示。在参数空间中,由公式(2)可推导出对给定的r0,由公式(3)可确定出一组(ai0,bi0)值,将(ai0,bi0)值投票到r0层的累加器上;对给定的r1,由公式(3)又可确定出另一组(ai1,bi1)值,将(ai1,bi1)值投票到r1层的累加器上;依此类推,可得到三维累加阵列(aij,bij,rj)。通过三维累加计算,得到最大累加值对应的坐标(a0,b0,r0),即得到被检测圆的3个参数,实现标准Hough变换检测圆。由于采用标准Hough变换检测圆需要频繁地进行开平方运算,其计算量相当大,占用的存储空间也非常大。因此,在实时在线检测中用标准Hough变换检测圆几乎是不可能的。2像素点位置的确定中点画圆算法的基本思想是:确定起始点P,根据中点M构造函数判别式,计算出下一像素点P1(如图2(a)所示);依次每步单位间隔取样,顺时针确定出最佳逼近于该圆弧的像素序列(如图2(b)所示);考虑到圆的对称性,只需计算1/8圆弧的数据(如图2(c)所示),从而大大减少运算量。3基于约束的运动方程法将中点画圆算法与Hough变换检测圆方法相结合,提出一种基于中点画圆算法的改进Hough变换检测圆方法,其基本思想如下:设待测圆的半径为r0,对于实时在线检测获得的机械零件图像每一个边缘点(xi,yi)(如图3(a)所示),以(xi,yi)为圆心、r0为半径,在Hough变换参数空间的累加器阵列中,采用中点画圆算法对相应的累加器进行投票(如图3(b)所示),然后检测各累加器的累加值,当某个累加器的值达到检测阈值时(如图3(c)所示),即可确定出机械零件图像上的一个以(ai,bi)为圆心,r0为半径的圆。对于给定的半径R,在参数空间的累加器阵列中,设当前累加器为P(xp,yp)(如图3(b)所示),为判别下一累加器为P1还是P2,构造判别函数F(x,y)=x2+y2-R2。对于参数空间中的圆上的点,F(x,y)=0;对于圆外的点,F(x,y)>0;而对于圆内的点,F(x,y)<0。假设M是P1和P2的中点,即M=(xp+1,yp-0.5)。构造M的判别式若d1<0,M在圆内,说明P1距离圆弧更近,应取P1为下一累加器。再下一个累加器的判别式为令正右方向的增量因此,在已知P1后,即可根据Δd方便地确定出下一个累加器。若d1≥0,M在圆外(或圆上),说明2P距离圆弧更近,应取P2为下一个累加器。再下一个累加器的判别式为令右下方向的增量因此,在已知P2后,即可根据Δd′方便地确定出下一个累加器。对比公式(3)~公式(5)可以看出:公式(3)要进行开平方运算,其运算量大,而公式(4)、公式(5)只需进行简单的加减运算,运算量小,运算速度快。为了进一步提高检测速度和准确性,使该方法能更好地适用于机械零件圆形几何特征的实时在线检测,对检测圆的方法做以下改进。如图2(b)所示,要生成第二个8分圆,按顺时针方向,起始点为(0,R),判别式d的初始值为因在计算判别式d的过程中会出现大量浮点运算,存在运算量大、计算结果精度低等缺点。为了克服浮点运算方法的不足之处,本文提出采用整数运算代替浮点运算,即将判别式d的初始值放大4倍改为5-4R,则下一个累加器的判别式增量Δd变为8xp+12或8(xp-yp)+20,从而进一步提高检测速度和精度。4检测阈值生成基于中点画圆算法的改进Hough变换检测圆方法的具体实施步骤如下:(1)经验知识设定根据待检测机械零件图像的实际情况和经验知识,预先分段指定待测圆的半径范围,进行经验知识设定。(2)分段检测阈值生成根据实际情况,分段设置调节系数,自适应生成各段的检测阈值。(3)基于中点画圆算法对累加器进行投票采用中点画圆算法对Hough变换参数空间中相应的累加器进行投票,然后统计各累加器的累加值。(4)检测出圆的几何参数比较累加值与检测阈值,确定出被测圆,然后得到圆心坐标、圆的半径等几何参数。检测圆新方法的检测结果如图4所示。5圆形几何参数的生成在相同检测阈值的情况下,分别采用本文提出的检测圆的新方法、标准Hough变换检测圆和随机Hough变换检测圆这三种方法,在给定的半径范围内,对图5中的圆形特征进行检测,获取圆的几何参数,并求得各自的平均运算时间。图5中的圆形几何特征的原始值分别为:圆心坐标(65,150)、(60,65)及(121,97),对应半径19、33及47pixels。对比实验采用的计算机配置为:Pentium®4CPU2.80GHz,2GB内存,NVIDIAGeForce4MX440图形加速卡,64MB显存。其对比实验结果如表1所示。通过上述实验可以看出,检测圆的新方法能有效地检测出目标圆,检测结果准确,其检测速度要比标准Hough变换检测圆快一个数量级,也比随机Hough变换检测圆略胜一筹。6基于中点画圆算法的检测圆新方法针对标准Hough变换计算复杂、运算量大,随机Hough变换会造成参数单元的大量无效累积等缺点,将中点画圆算法与Hough变换相结合,提出了一种基于中点