基于梯度信息的随机Hough变换圆轮廓测量技术

1、第 35 卷，增刊红外与激光工程2006 年 10 月vol.35 supplement infrared and laser engineering oct.2006 基于梯度信息的随机hough 变换圆轮廓测量技术*崔继文，谭久彬(哈尔滨工业大学超精密光电仪器工程研究所，黑龙江哈尔滨 150001) 摘要：在图像处理及计算机视觉中，hough 变换是一种应用非常广泛的图像边缘检测技术。分析了 hough变换的基本原理， 指出了传统hough 变换以及随机hough 变换存在的缺陷， 提出了一种基于随机hough 变换、综合利用图像本身灰度信息和梯度信息，并根据图形本身性质搜索边缘点的适用于

2、圆周及圆弧轮廓的边缘检测算法。该算法采用“多对一”映射，显著减少了存储所需的容量；采取并行算法提高了运算速度；采用亚像素细分技术对边缘进行进一步的细化处理，提高了测量精度；最后用弦长加权法对边缘点进行拟合，得到被测参数。依据上述原理研制了高精度、高效率图像采集与处理系统，并在该系统上进行了实验。实验结果表明，对于对比度较差的轮廓，其测量不确定度在0.15 像素以内。关键词： 随机 hough 变换；圆轮廓测量；亚像素细分；弦长加权拟合中图分类号：tp391.41 文献标识码：a 文章编号： 1007-2276(2006) 增 d-0419-06 circle contour measureme

3、nt technique based on randomized hough transform using gradient informationcui ji-wen, tan jiu-bin (institute of ultra-precision optoelectronic instrument engineering harbin institute of technology, harbin 150001, china) abstract: hough transform (ht) is an image edge detection technique which is wi

4、dely used in pattern recognition and computer vision. in this paper the fundamental principle of ht is analyzed and the defect of ht and randomized hough transform (rht) is also indicated. an algorithm based on rht and the information of grayscale and gradient in image is proposed. it also uses the

5、property of the pattern and is mainly used in detection of circle and arc contour measurement. this algorithm can decrease needing memory space of computer by “multi to one” mapping, accelerate the calculation speed by parallel algorithm, improve of edge detection accuracy by subpixel division, obta

6、in the parameters of object by applying least square fitting algorithm. based on the principle, one measurement system with high accuracy and efficiency in image capturing and processing is developed, and some experiments are operated in the system. the result shows that the uncertainty is less than

7、 0.15 pixel for contour low contrast image. key words: randomized hough transform (rht); circle contour measurement; subpixel division; chord weight fitting 收稿日期： 2006-08-18 作者简介： 崔继文 (1974-)，男，山东聊城人，博士，主要从事超精密光电测试技术与数字图像处理方面的研究。420 红外与激光工程：光电信息处理技术第 35 卷0 引言快速而准确地测量圆在计算机视觉领域，特别是在自动化精密测量领域有着广泛的应用前景，

8、hough 变换12是进行圆轮廓测量的有效方法之一。但传统的hough 变换存在如下几个显著的缺陷：计算量大、占用内存大以及要提取的参数受参数空间量化间隔的限制。为了克服上述缺陷，xu 等提出了随机hough 变换34，采用“多对一”的映射，同时采用动态链表结构进行参数累加，大大降低了内存的开销。虽然随机hough 变换具有参数空间大、参数精度高的优点，但在处理复杂图像时仍会造成大量无效累加。hough 变换利用图像边缘梯度方向信息和曲线的连续性进行边缘检测时，可以大大减小计算量，较好地解决无效累加问题。如果图像的边缘梯度精度很高，hough 变换就可以只累加梯度方向的边缘信息；但一般边缘梯度

9、的精度不高，尤其对渐变边缘、灰度对比度较差的图像，其梯度图像边缘较宽，因此hough 变换在利用边缘梯度信息时，不仅对梯度方向为的边缘点进行累加，还要对此点周围的点（设梯度方向为?g）进行累加，才能得到图像边缘点的参数。本文提出了利用图像本身的灰度信息和梯度方向信息，并根据梯度图像的边缘宽度确定边缘搜索点的数目，最大限度地保证了圆周上的信息不丢失，极大地降低了内存的开销，提高了运算速度，缩短了运算时间；然后采用亚像素细分技术对边缘进一步细化，以提高检测精度，最后用弦长加权拟合法得到被测圆弧轮廓的参数。1 hough变换原理1.1 hough变换检测边缘的基本原理hough 变换是利用图像全局特

10、征而将边缘像素连接起来组成区域封闭边界的一种方法。它把图像空间转换到参数空间，在参数空间对点进行描述，达到检测图像边缘的目的。对于直线而言，将所有可能落在直线边界上的点进行统计计算，根据对数据的统计结果确定该点属于该直线的程度；此变换方法同样适用于圆、广义曲线等检测及模式识别等58。用 hough 变换对圆轮廓进行检测，可以得到较好的效果。已知圆的方程为：()()222xaybr-+-=(1) 式中：(),a b为圆的圆心坐标；r为圆的半径。相对应于图像空间中的圆，设在图像平面(x-y 平面 )上有一个待检测的圆，()ii,|1,2,3,.,xyin=为待测圆轮廓上点的集合，而(),x y为集

11、合中的任意一点，则在参数空间坐标系(), ,a b r中圆的方程可表示为：()()222axbyr-+-=(2) 可见， hough 变换是将输入图像中圆边界上的点映射到三维的参数空间的锥面上去，即图像空间中的任意一点对应于参数空间中的一个三维曲面；若这些图像空间中的点位于同一个圆周上，则在参数空间中三维曲面必然交于一点()000,a br，恰好对应图像空间中的圆心和半径。特别地，若图像空间中半径r已知 ,，则相应圆边界上的一个点映射到参数空间的一个圆上9，如图1 所示。 这样由三个参数形成一个三维的累加器。在实际变换中可以用二维累加矩阵来统计圆心，用一维累加矩阵来统计半径。对图像中每一个特征

12、点，都在参数空间映射为该特征点为参数的圆，所有的这些圆都经过参数空间单图 1 参数空间中的点fig.1 points in parameter space增刊崔继文等：基于梯度信息的随机hough 变换圆轮廓测量技术 421 元(), a b，这样将所有的特征点都映射后，参数空间中这些圆的交点单元的累加值是局部极大值，该点的坐标(),a b就是所要检测圆的圆心。 用随机 hough 变换进行圆检测时， 随机选取不在同一直线上的三个边缘点唯一地确定参数空间的一个点，是“多对一”的映射，避免了传统hough 变换“一对多”映射的庞大计算。在实际累加时采用动态链表结构，只对“多对一”的映射所得到的参

13、数进行累加，从而大大降低了内存的开销，使随机hough 变换有参数空间大、参数精度高等优点。1.2 利用梯度信息的hough 变换如果被测圆轮廓上某边缘点的梯度并未由于噪声干扰而变化形成虚假方向，在一定误差内可以认为被测圆轮廓的圆心位于边缘点的梯度方向上。引入梯度方向信息可以把圆轮廓测量的累加矩阵从三维降至二维10。由于通过圆轮廓边缘上一点并沿着该点灰度梯度方向的直线必经过圆轮廓的圆心(忽略一些误差因素)，因此，如果在圆轮廓的边缘上按一定间隔距离取两个点，经过这两点并分别沿它们的梯度方向的两条直线应该交于圆心点 (忽略误差因素)。假设ap、bp分别是圆轮廓边缘上的两点，其梯度方向分别为ad|d

14、pyx、bd|dpyx，两点的坐标分别为()aa,ppxy和()bb,ppxy，则可解出该圆轮廓的圆心坐标()cc,xy为：()()aabbababbaababababccdd|dddd|dddddd|dddddd|ddppppppppppppppppppyyxxyyxxxyyxxyyyyyyxxxxxxyyyxx?-?-?=?-?-?-?-?=?-?(3) 同时由圆心坐标和边缘点的坐标得出半径r的值。这样在参数空间只对参数()cc,xy和r的单元进行累加，两个边缘点只对应参数空间的一次累加，实现了多对一的映射。经过多次映射和累加器的累加，统计累加单元中的计数，计数值最大的单元所对应的参数被认

15、为是被测圆轮廓的圆心和半径。2 本文提出的适用于圆轮廓测量的hough 变换由上面的分析可知，尽可能减少hough 变换的点数、降低参数空间中累加数组的维数是提高hough 变换效率、减少运算时间的关键。本文提出了一种用于圆轮廓测量的hough 变换方法，该方法首先利用圆轮廓图像空间中本身的灰度信息，同时利用图像的梯度信息，并根据圆周的性质按照一定的规律搜索属于圆周上的点，使在保证圆周上信息不丢失的情况下尽量减少变换的点数，减少内存的开销。并用亚像素细分技术处理所得到的边缘图像，以提高测量精度。最后利用弦长加权原理对所得到的点进行拟合，得到被测圆轮廓的参数。文中假设图像在进行处理前已经进行了噪

16、声去除、灰度增强等处理。2.1 图像的边缘提取及对边缘点进行亚像素细分首先运用适当的边缘检测算子对所得到的图像进行边缘锐化处理，得到梯度图像( , )r i j并同时获取梯度方向。为了进一步提高测量精度，对得到的梯度边缘图像进行亚像素细分，使边缘定位精度达到1/201/10 像素。本文采用多项式插值亚像素细分算法实现图像边缘的高精度定位11。此方法利用边缘检测所获得的梯度图像中确定的边缘点两侧的梯度值所提供的信息获得插值函数，插值函数最大值所对应的坐标即是亚像素精度的边缘点坐标。边缘亚像素坐标ee(,)xy可以表示为：422 红外与激光工程：光电信息处理技术第 35 卷ee(1, )(1, )

17、(1, )2( , )(1, )2( ,1)( ,1)( ,1)2 ( , )( ,1)2ijr ijr ijwxxr ijr i jr ijr i jr i jhyyr i jr i jr i j-+=+-+-+=+-+?(4) 式中：(,)ijx y为以像元几何中心位置表示的点( , )i j的边缘点坐标；ee(,)xy为亚像元边缘坐标；( , )r i j为边缘检测得到的梯度图像；w为 ccd 像元水平方向间距；h为 ccd 像元垂直方向间距。2.2 梯度均值阈值分割通过梯度均值的阈值选取方法对梯度图像的目标和背景进行分割，并把分割后的目标和背景进行二值化。其阈值选取步骤如下：（1）计算

18、梯度图像( , )r i j的归一化灰度直方图( )h n；（2）由( )h n计算阈值t。2550( )ntnh n=(5) 梯度均值阈值法可直接利用梯度图像进行计算，减少了算法的复杂性，提高了计算速度。2.3 圆轮廓边缘图像的获取根据三点确定一个圆的原理，不在同一条直线上的三个点必然唯一地确定一个圆，任意取分割后图像上三个目标点，由公式(1)可以得到由此三点确定的圆参数()111,a b r；同时由这三点和公式(3)可以求出被测圆的参数()222,a br。如果两次求得的圆心和半径的差值在容许的误差范围内，对存储此圆心和半径的单元进行累加。如此循环，直到梯度图像上全部目标点变换完毕为止。统

19、计参数累加单元的累加数，出现峰值的累加单元即为被测圆轮廓的圆心和半径。为了尽可能减少被测圆轮廓的信息丢失，经过 hough 变换得到被测圆轮廓的圆心()00,ab和半径0r后，对圆轮廓周围的点进行判断，重新构造函数：() ()()222000,fx yxaybr=-+-(6) 式中：(),f x y表示点(), x y到圆的距离。将圆周目标点代入上式，若得到的(),f x y，其中是容许的误差，则此点为圆轮廓上的点，记录此点的坐标，如此循环，直至全部结束。2.4 弦长加权法圆拟合通 过 上 述 检 测 方 法 可 以 检 测 到 属 于 圆 周 上 的n个 点ii(,) |1,2,.,x yi

20、n=。运用弦长加权法12对这些边缘点进行拟合，得到被测圆轮廓的精确圆心坐标()00,xy。其几何模型如图2 所示。根据圆轮廓上点的性质可知，对轮廓上的两点()ii,x y与()jj,xy，则有：22220000()()()()iijjxxyyxxyy-+-=-+-(7) 对上式展开整理得：2222002()2()jijijjiixx xyyyxyxy-+-=+-(8) 令：22222()2()kjikjikjjiiaxxbyycxyxy?=-?=-?=+-?，并建立误差方程：图 2 弦长加权法几何模型fig.2 model of method with chord length weight

21、增刊崔继文等：基于梯度信息的随机hough 变换圆轮廓测量技术 423 00()kkkkeca xb y=-+(9) 式中：ke为残余误差；(1)/2nn n=-；1kn 。上式用向量表示为：=-ecmxtmin=e e(10) 式中：12neee?=?#e；00 xy?=?x；1122nnababab?=?m#；12nccc?=?c#由于不同的弦长产生不同的误差，采用弦长加权法进行圆拟合。设弦ab的长度为：22()()kijijpxxyy=-+-，其中0kn 由kp组成nn阶权矩阵为12nppp?=?p%按照最小加权二乘法整理得到圆心位置为：t1t()-=xm pmm pc(11) 被测轮廓

22、的半径为：()()220011niiirxxyyn=?=-+-?(12) 3 仪器系统与实验依据上述工作原理，研制了高精度、高效率的图像采集与处理系统，并在该系统上进行了实验。本实验系统由高精度工作台、平行光照明系统、ccd 摄像机、显微物镜、电机以及带有图像采集卡的计算机组成，如图 3 所示。水平电机和工作台由计算机程序控制实现ccd 相机自动调焦，为后续测量提供保证。由传光光纤组成的冷光源照明系统发出照明光，被测物通过返回光经显微物镜成像到ccd 摄像机上； 通过图像采集卡把采集到的图像实时传输到计算机中进行在线实时运算处理，得到被测圆轮廓参数。在实验中，把两个几乎相切的圆弧轮廓作为测量目

23、标，由ccd 拾取的图像如图4 所示。本文提出的算法应用于此目标的测量，测量结果如表1 所示。由测量结果可以得出测量重复性小于0.15 像素。图.3 测试系统实物图图 4 被测目标图像fig.3 experiment system for the method fig.4 image of the object 424 红外与激光工程：光电信息处理技术第 35 卷表1 圆心坐标和半径的测量值(上面的圆弧 ) ( 单位 :像素 ) tab.1 measurement results of the center and radius(upper arc) (unit: pixel) 测量值平均值重

24、复性( ) 测量次数a0b0r0a0b0r0a0b0r01 482.03 -315.85 624.99 2 481.97 -315.91 625.34 3 481.93 -315.64 625.13 4 481.87 -315.78 625.28 5 482.07 -315.82 625.33 481.97 315.80 625.21 0.079 0.101 0.150 4 结论本文提出的基于梯度信息的随机hough 变换方法的圆轮廓测量技术，采用了“多对一”的映射，显著减少了存储所需的空间；通过并行算法，使运算速度和测量效率得到了较大提高；采用亚像素细分技术，提高了测量精度；最后用弦长加权拟

25、合算法得到被测圆轮廓的参数。本测量方法测量精度高，可以用于灰度对比度较差的图像，完全适用于圆轮廓的测量。参考文献：1 hough p v c.method and means of recognizing complex patterns ：us，patent 3069645p.1962. 2 illingw j，kitter j.a survey of the hough transformj.computvision grapics image process，1988，44（1） ：87-116. 3 xu l.a new curve detection method: randomiz

26、ed hough transformj.pattern recognition letters，1990，11（5） ：331-338. 4 xu l.randomized hough transform: basic mechanisms, algorithms, and computational complexitiesj.computer vision graphics image process: image understanding，1993，57（2） ：131-154. 5 orazio t d，guaragnella c，leo m.a new algorithm for ball recognition using circle hough transform and neural classifierj.pattern recognition ，2004，37：3