当前位置：文档之家 › 一种基于随机Hough变换圆检测的改进算法[1]

一种基于随机Hough变换圆检测的改进算法[1]

  • 格式：pdf
  • 大小：347.09 KB
  • 文档页数：3

收稿日期:2007-07-02基金项目:2007年四川省重点技术创新项目计划(07XM020)作者简介:赵桂霞(1981-),女,山东菏泽人,硕士研究生,研究方向为计算机视觉;黄　山,博士,教授,研究方向为模式识别与图像处理。

一种基于随机H ough 变换圆检测的改进算法赵桂霞,黄　山(四川大学电气信息学院,四川成都610065)摘　要:介绍了一种基于随机Hough 变换(RHT )的圆检测的改进算法。

该算法利用梯度方向信息来确定采样的三点是否进行累积,然后再利用确定候选圆范围的方法来缩小所要搜索的像素点的范围。

此方法较好地解决了传统RHT 中由于随机采样而造成的大量无效累积问题,并且改进后的算法使运行速度得到进一步的提高,检测性能也有较大的改善。

该算法分别在加噪和不加噪的人工图像上做了实验,检测性能和处理速度方面都比传统的RHT 有明显的改善和提高。

关键词:随机Hough 变换;圆检测;梯度方向信息;窗口中图分类号:TP301.6 文献标识码:A 文章编号:1673-629X (2008)04-0077-03An Improved R andomized H ough Method of Circle DetectionZHAO Gui 2xia ,HUAN G Shan(School of Electrical Engineering and Information ,Sichuan University ,Chengdu 610065,China )Abstract :Proposes an improved algorithm for detecting circles which is based on randomized Hough transform.It uses gradient direction information to determine whether the parameter should be accumulated or not.And it uses the range of circle to reduce the range of pixels searching.The problem of useless accumulation in traditional RHT is well solved and the improved method has higher speed and better de 2tection performance.Synthetic images with different level noises have been taken to test the detection performance and the speed.And this algorithm has been proved an efficient method.K ey w ords :randomized Hough transform ;circle detection ;gradient direction information ;window0　引　言在复杂图像中快速准确地检测出圆及其参数是计算机视觉和模式识别中一项重要的任务。

Hough 变换[1～3]常常被用于圆形特征的检测。

Hough 变换的优点在于:它对图像的噪声不敏感,能有效地消除噪声的影响;这种变换便于并行计算,计算机视觉领域的一些问题相当复杂,需要很大的计算量,并行计算是提高计算速度的有效方法。

Hough 变换的基本思想是将图像空间中具有一定关系的像元进行聚类,寻找能把这些像元用某一解析形式联系起来的参数空间累积对应点[4,5]。

在参数空间超过2维时,Hough 变换几乎不可能应用于实际,这是由于Hough 变换计算量和占用内存都很大。

为了克服这一缺点,Xu 等[2]提出了随机Hough 变换(Ran 2domized Hough Transform ,RHT )。

由于RHT 采用了随机采样和多对一映射,使得时间和空间的开销都大大减少。

但是在处理复杂图像时,由于随机采样引入大量无效单元,从而造成大量无效累积。

文中提出了一种改进的RHT 用于圆检测。

1　传统的RHT 算法众所周知,半径为r ,圆心坐标为(a ,b )的圆的参数空间的表示为(x -a )2+(y -b )2=r 2(1)利用该方程可以用较简单的累加的方法实现对圆的检测。

此方程包括3个参数(a ,b ,r ),根据Hough 变换的思想,需要建立一个3维累加数组,可以让圆心(a ,b )依次变化计算出r ,即要通过降低维数来减少计算量。

1.1　传统RHT 算法原理用于圆检测的RHT 具体算法:(1)构造边缘点集D ,初始化参数单元集P =NULL ,循环次数K =0;(2)从D 中随机选取3点;(3)由这3点解特征参数p ;第18卷　第4期2008年4月 计算机技术与发展COMPU TER TECHNOLO GY AND DEV ELOPMEN T Vol.18　No.4Apr.　2008(4)在P 中找一个p c ,满足ζp -p c ζΦδ,若找到则转(6);否则转(5);(5)将p 插入P ,其对应计数值为1,转(7);(6)将p c 所对应的计数值加1,若小于指定阈值N t ,转(7);否则转(8);(7)k =k +1;若k >k max ,结束;否则,转(2);(8)p c 为候选圆特征参数,若该参数对应圆上的边缘点数M pc >M min ,转(9);(9)p c 为真实圆参数,将落在参数p c 对应特征上的点从D 中去掉,判断已检测到的圆的数目是否达到规定数目,若是则结束,否则重置P =NULL ,K =0,转(2)。

其中k max 为规定的检测一个圆过程中所允许采样的最大循环次数。

M min 是圆所必需的最小点数,一般设为2πλ,其中λ为一个固定系数。

P 为参数空间的参数单元集,是一个动态链表结构。

M pc 为图像空间中落到候选圆上的点数。

1.2　传统RHT 无效累积分析当处理的图像中有多个圆存在时,RHT 由于随机采样会引起大量无效累积单元,造成大量的无效累积(见图1)。

假设图像中有几个非圆上的点,有N 个大小相同的圆,且每个圆上有q 个点,则随机采样所得3点落在同一圆上的概率为:p =N C 3q C 3Nq+n=N q (q -1)(q -2)(N q +n )(N q +n -1)(N q +n -2)(2)图1　无效累积说明图理想情况下,假设所有点都在圆上,即n =0时,式(2)可简化为:p =N q (q -1)(q -2)N q (N q -1)(N q -2)≈1N2(3)由式(3)知,当图像中仅有大小相等的圆时,随机采样3点落在同一圆上的概率和圆的总数的平方成反比。

随着圆的数量的增多,产生无效累积的概率也就随之猛增。

2　改进的RHT 算法针对RHT 变换中的无效累积问题,可以首先利用梯度方向信息来确定随机选取3点是否在同一个圆上。

如果在同一个圆上再对其进行参数计算,否则就重新选取3点。

根据圆的性质,如果3点的梯度方向和各自的法线方向在允许的误差范围内时,即认定3点在同一个圆上,计算出圆的参数后再以圆心为中心,以圆的直径为边长的正方形范围内依次取一点,若该点到所解圆心的距离与半径之差在允许的范围内时,说明该点在这一圆上。

利用梯度方向信息可以有效减少动态链表的参数单元集,确定参数后再通过缩小搜索范围来提高RHT 变换的速度和效率。

2.1　梯度的求取在对圆进行检测时,往往只需要得到该圆的边界信息,所以要用到边界检测。

在数字图像处理中,一阶导数可以用来检测图像中的一个点是不是边缘点,而一阶导数是基于各种二维梯度的近似值。

像素点f (x ,y )处的梯度定义为如下的向量:f =[G x ,G y ]r =[9f 9x ,9f9y](4)梯度向量指向坐标(x ,y )处f 的最大变化率方向。

在边缘检测中梯度的大小是一个非常重要的量,且是一个标量,用 F 表示:F =[G 2x +G 2y ]1/2(5)梯度向量的方向也是一个重要的量,令α(x ,y )表示标量 F 在(x ,y )处的方向角,有α(x ,y )=arctan (G yG x)(6)这里,角度是以轴为基准度量的,边缘在(x ,y )处的方向与此点的梯度方向垂直,即此点的梯度方向与此点的法线方向重合。

公式(5)和(6)分别给出了梯度大小和方向的计算公式,两个公式都涉及到G x ,G y 的求取,即图像上每个像素位置的偏导数9f 9y ,9f9x。

一般是通过Roberts 算子、Soble 算子等经典边缘检测算子来求取G x ,G y 。

文中采用计算量比较小的Soble 算子来进行边缘检测。

2.2　加　窗文中采用加窗口的方法来减少运算时间,提高计算速度。

在候选圆周围加一个正方形窗口,即以候选圆的直径加一定的余量为边长,以候选圆的圆心为中心的正方形。

当随机取点的时候先比较此点是否在所加窗口内,如果是,则计算该点到候选圆的距离,若不是,则放弃此点,继续取下面的点进行判断。

此方法可缩小搜索范围,减少计算量的同时提高了计算速度。

2.3　改进的RHT 算法的描述(1)存储所有边缘点d i (x i ,y i )至集合D ,并记录・87・ 计算机技术与发展 第18卷各点的梯度方向,初始化参数单元集P =NULL ;(2)从D 中随机选取3点;(3)计算这3点所确定的圆的参数p (a ,b ,r ),然后判断法线方向与梯度之差是否在允许范围内,若是则转(4);否则转(2);(4)在P 中寻找p c ,满足ζp -p c ζ<δ,δ是允许误差,若找到则转(6),否则转(5);(5)将p 插入P ,令其计数值为1;(6)若a -r <x i <a +r 且b -r <y i <b +r ,则计算d i 到候选圆心的距离,若在允许的误差范围内,则将计数值加1,遍历正方形范围内所有的点;(7)若该参数对应的圆上的点数M pc >M min ,转(8);否则,为虚假圆,把该参数特征从P 中剔除;(8)检测到的为真实圆,判断已检测到的圆是否已达到规定的数目,若是,结束;否则,把圆上的点从边缘点集中去除,重置P =NULL ,转(2)。

3　实验结果实验是在内存为512MHz 的P4的计算机上进行的,所处理的图片是合成的圆图像(见图2、图4),其检验结果分别见图3、图5。

实现语言为VC ++。

图2　原图像 图3　图2的检测结果表1　计算速度对比传统RHT 算法(ms )改进算法(ms )图2362215图4827466图4　带噪声图像 图5　图4的检测结果4　结　语文中的改进RHT 算法和传统的RHT 算法由表的速度对比中可以看出,改进的RHT 算法在计算速度上有一定的优势。

合集下载

基于随机Hough变换的圆检测改进算法

基于随机Hough变换的圆检测改进算法

维普资讯
卿 ■ 僵息技术 ．僵息亿 Ｉ ｂ
基 于 随机 Ｈ ｕｈ变 换 的 圆检 测 改进 算 法 ｏｇ
Ａ ｍｐｏ ｅ ｔｏ ｆＣ ｒｌ ｅｅ ｔ ｎ Ｂ ｓｄ ｏ ａ ｄ ｍｉ ｄＨｏ ｇ ｒｎ ｆｒ ｎ Ｉ ｒｖ ｄ Ｍｅｈ ｄｏ ｉ ｅＤ ｔｃ ｏ ａｅ ｎ Ｒ ｎ ｏ ｚ ｕ ｈＴ ａ ｓ ｍ ｃ ｉ ｅ ｏ
转 （ ）否则转（ ） ６， ５；
（ ） Ｐ插入 Ｐ， ５将 令其对应 的累加器值 为 ｌ转到 （） ， ７；
（） Ｐ 对 应 的累加 器值 ｔ ｌ若小 于 阈值 ， 转 ６将 加 ， 则
（ ）否则转 （） ７， ８；
（） ７ Ｋ＝Ｋ＋ｌ若 Ｋ＞ ，
数 ＞Ｊ ， ｌ 则转 （） ｆ ９；
误差。
随机 Ｈ ∞小 变换
圆 检测
最 小 点 集
Ａｂ ｔａ ｔ Ｔｆ ａ ｅ ｎｒ ｄ ｃ ｓ ａｌｉ ｒ ｖ ｄ ｍｅｈ ｄ ｏ ｉ ｌ ｄ ｔｃｉｎ ｗ ｉｈ ｉ ｂ ｓｄ ｏ ａ ｄ ｍ ｚｄ Ｉ ｗ ｈ ｓｒ ｃ ｉｓ ｐ ｐ ｒ ｉｔ ｕ ｅ ｌ ｍｐ ｏ ｅ ｔｏ ｆｃｒ ｅ ｅｅ ｔ ｈｃ ｓ ａ ｅ ｎ Ｒ ｎ ｏ ｉ － ｏ ｃ ｏ ｅ Ｉ ｏ
１ 引言
图像中圆的检测是机器视觉 中一项重要任务 。Ｈ ｕｈ ｏｇ 变 换“ 是 目前应 用最 广的特征 检测方 法 ， 常常被用 于直线 、 圆 和椭圆等特征的检 测。其基本 思想 是将原 图像 变换 到参数 空间 ， 大多数边 界点 满足的某 种参数形式来描 述图像 中的 用 曲线 ， 过设 置累加 器进 行 累积 ， 得峰 值对 应的 点就是 所 通 求 需要 的信息 。在参数空 间不超过二维 的情 况下 ， 这种变换 有 较理想的效果 ， 当参 数空 间超过 二维时 ， 种变 换几乎 不 但 这 可能应用于实 际， 这是因为传统 的 Ｈ ｕｈ变换计算 量 和 占用 ｏ ｇ 内存很大 。为 了解决这一 问题 ， 出现 了许多 改进 的 ｒ ｕ 变 ｔｇ ｏｈ 换方法 ， 随机 ｒ ｎ ｌ ￣变换 ｏ ｇ 。 就是其中之一。 随机 ｎ ｗｈ变换 法采用 了随机采 样 和多对 一 映射 ， 即 ｏ， （
基于Hough变换的圆形物体的检测

基于Hough变换的圆形物体的检测


人工图像 和卫星影像 中， 比如 ： 光学 干涉 图像 和军事驻
地图像 ， 大多数物体都是由线或曲线组成的， 以， 所 图像处
理 中， 对线或 曲线 的识 别和定位就显得 十分重要 。 Ｈ ｕｈ变换是一种 用于 区域边 界形 状 描述 的方 法 ， ｏｇ 经 典 Ｈ ｕｈ变换常 常被 用于 直线段 、 和椭 圆的检测 。其基 ｏｇ 圆 本思想是将图像的空 问域变 换 到参 数空 间 ， 大多数边 界 用 点满足的某种参数形式来 描述 图像 中的 曲线 （ 区域 边界 ） ，
的点 （ 量 ） 矢 。对 于圆来说 ， 半径 为 ｒ 圆心坐标 为 （ ， ） ， ａ ｂ 的 圆在 参数空间中的表示为
（ 一 ＋（ ） ） Ｙ 一６ ：ｒ ． （） １
此时 ， ＝［ ，Ｉ ， ，，］ 其参 数 空间 为三 点 Ｙ］ ａ＝［ ｂｒ ，
维。
运算量是非常大的， 所以， 需要从参与运算和降低维数两方
面人手 ， 以提高速 度 。
２ 算 法
全局的累加运算， 所以， 运算量很大。多年来， 许多学者利
用 Ｈ ｕｈ ｏｇ 变换针对具体情 况进行了扩展 。如利用 中心点生 成圆弧的方法统计一定范 围内点的累加值获得圆心和根据
最ｔ －乘法原理用圆来逼近轮廓等 ， ｂ－ 虽然能在一定程度上
通过设置累加器进行 累加 ， 求得 峰值对应 的点 就是所需 要
的信 息… 。 圆的 Ｈｏｇ ｕ ｈ变换有一个最 大的 以看 出 ： １可 由于 圆的 Ｈ ｕ ｈ变换 涉 及的 维数 ｏｇ 过高， 达到 了三维 ， 如果 对 图像上 所有 的点都 做运算 的话 ，
张 霄 ，彭 维
（ 郑州解放军信息工程大学 测 绘学院 。 河南 郑州 ４ ０ ５ ） ５ ０ ２
hough变换圆拟合

hough变换圆拟合

hough变换圆拟合
Hough变换圆拟合（Hough transform circle fitting）是一种用于从图像中检测圆的技术。

它是从Hough变换（Hough transform）算法演变而来的。

Hough变换圆拟合算法使用梯度信息来检测圆，并且它能够检测出各种大小、位置和形状的圆。

算法步骤如下：
1. 首先对图像进行预处理，如灰度化、边缘检测等。

2. 选择一组圆心候选点，可以采用图像中的各种特征点，例如边缘点、角点、中心点等。

3. 对于每个候选点，设定一个半径范围，然后在这个半径范围内搜索圆。

4. 对于每个搜索到的圆，计算出它的梯度值。

如果梯度值大于设定的阈值，则将这个圆作为候选圆。

5. 重复步骤3和步骤4，直到所有的候选点都被搜索完毕。

6. 统计所有候选圆的得票数，并根据得票数高低进行排序。

7. 选取得票数最高的圆作为最终检测结果。

Hough变换圆拟合算法的优点是可以检测出各种大小、位置和形状的圆，它的缺点是计算量大，需要较长的运行时间。

基于Hough变换的椭圆检测改进算法

基于Hough变换的椭圆检测改进算法

基于Hough变换的椭圆检测改进算法陆路;梁光明;丁建文【摘要】An improved algorithm based on Hough transform is proposed for detection of multi ellipses in image with com-plicated background to cope with the problems of inaccurate position of the ellipse center and overmuch pseudo ellipse. The ac-curacy of the ellipse detection is improved through the developed calculation of parameter space and Hough transform. The true ellipse is distinguished from the pseudo candidate ellipses by using the parameter equation. The experimental results show that the detection method can detect multiple ellipses in the complex environment quickly and accurately,and has strong anti-inter-ference ability.%在背景复杂的图像中,针对多椭圆检测时椭圆中心定位不准、虚假椭圆过多的缺点,提出一种基于Hough变换的改进算法.该算法对参数空间和Hough变换计算的改进提高了椭圆检测的准确度,并利用参数方程判断候选椭圆的真假.实验结果表明,该检测方法具有较强地抗干扰能力,能够在复杂的环境中准确快速地检测出多个椭圆.【期刊名称】《现代电子技术》【年(卷),期】2015(038)016【总页数】3页(P92-94)【关键词】Hough变换;椭圆检测;参数方程;检测方法【作者】陆路;梁光明;丁建文【作者单位】湘潭大学信息工程学院,湖南湘潭 411105;国防科学技术大学电子科学与工程学院,湖南长沙 410075;爱威科技股份有限公司研发中心,湖南长沙410013【正文语种】中文【中图分类】TN911-34;TP391.41椭圆一般性方程为：设椭圆中心为（x0，y0），则椭圆方程变为：式（1）有5个自由参数，文献[8]中CMHT算法采用2步检测法：第1步利用弦中点的几何特性投票统计得到关于椭圆中心的2个参数x0，y0；第2步结合椭圆方程式（2）计算出另外3个参数。