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

62 传感器与微系统(TransducerandMicrosystemTechnologies) 2006年第25卷第4期

计算与测试

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

张 霄,彭 维

(郑州解放军信息工程大学测绘学院,河南郑州450052)

摘 要:Hough变换在图像处理中占有重要地位,但本身具有存储空间大、计算时间长的缺点。利用圆的几何特性,针对Hough变换的缺点进行改进,并将其应用到图像中存在多个圆的情况。实验表明:该算法

能较好地减少存储空间,并降低计算时间,同时,能很好地对图像中多个圆进行检测。关键词:图像处理;Hough变换;圆检测

中图分类号:TN219 文献标识码:A 文章编号:1000-9787(2006)04-0062-03

Detectionofcirclebasedonhoughtransform

ZHANGXiao,PENGWei

(SchoolofSurveyingandMapping,ZhengzhouUniversityofInformationEngineeringofPLA,

Zhengzhou450052,China)

Abstract:Houghtransformtakesanimportantpartintheimageprocessing,butithasthedisadvantagesof

massivestoragespaceandlongcalculationaltime.ThedisadvantagesofHoughtransformaremodifiedbyusingthegeometricalcharacteristicofcircleanditisusedintheinstanceofmult-icirclesinoneimage.Theexperimentsshowthatitcanreducestoragespaceandcalculationaltime,andcanwelldetectmult-icirclesinoneimage.Keywords:imageprocess;Houghtransform;circledetection

0 引 言

人工图像和卫星影像中,比如:光学干涉图像和军事驻地图像,大多数物体都是由线或曲线组成的,所以,图像处理中,对线或曲线的识别和定位就显得十分重要。

Hough变换是一种用于区域边界形状描述的方法,经典Hough变换常常被用于直线段、圆和椭圆的检测。其基本思想是将图像的空间域变换到参数空间,用大多数边界点满足的某种参数形式来描述图像中的曲线(区域边界),通过设置累加器进行累加,求得峰值对应的点就是所需要的信息[1]。

圆的Hough变换有一个最大的缺点就是往往要用进行全局的累加运算,所以,运算量很大。多年来,许多学者利用Hough变换针对具体情况进行了扩展。如利用中心点生成圆弧的方法统计一定范围内点的累加值获得圆心和根据最小二乘法原理用圆来逼近轮廓等,虽然能在一定程度上降低运算量,但是,存在通用性不强和不能十分有效降低运算量的缺点,在实际工程应用中,急需找到一种计算迅速、通用性好的算法。

1 圆的Hough变换检测方法

Hough变换可应用于检测图像空间的解析曲线。解析曲线的参数表示的一般形式为

f(x,a)=0,

式中 x为解析曲线上的点(二维矢量);a为参数空间中的点(矢量)。对于圆来说,半径为r,圆心坐标为(a,b)的圆在参数空间中的表示为

(xi-a)2+(yi-b)2=r2.

(1)

此时,点x=[xi,yi]T,a=[a,b,r]T,其参数空间为三维。

从式(1)可以看出:由于圆的Hough变换涉及的维数过高,达到了三维,如果对图像上所有的点都做运算的话,运算量是非常大的,所以,需要从参与运算和降低维数两方面入手,以提高速度[2]。2 算 法

2.1 减少点数

2.1.1 图像平滑

为了防止噪声的干扰,首先,应用二维的高斯滤波对图像进行平滑处理,以消除噪声,原始的图像如图1所示,高斯滤波器的数学模型如下(假设滤波器的中心在坐标原点)

smoothfilter[i,j]=

(

i+j21-#e2R2.

2PR)2

第4期 张 霄等:基于Hough变换的圆形物体的检测

63

2.2 减少运算的维数

2.2.1 累加圆心(a,b)空间

Hough变换的思想是垂直圆周上的点的直线应该交于圆心。因此,如果在每个边缘点往边缘法向方向做直线,那么,就可以在圆心处得到一个累加的亮斑。因此,在(a,b)

空间中做直线,就会得到圆的中心的交点图,(a,b)空间可

图1 原始图像Fig1 Originalimage

以表示为

a=rsinH

b=rcosH

rI(minr,maxr),

2.1.2 图像边缘检测

应用sobel算子进行边缘检测,分别对图像应用垂直和水平的soble检测算子[3]。

对整个图像做水平和垂直的边缘检测运算后,取它们的模作为整个图像的边缘,图像边缘如图2所示。

|$f|=sobel[i,j]

==

(sobelvert[i,j]+(sobelhorize[i,j])A(i?a,j?b)←A(i?a,j?b)+E(i,j).

minr,maxr是要考虑的半径的范围(可以预设),A是(a,b)空间的数组,E(i,j)是Sobel边缘提取后的边缘的强度(经过二值化后取0或1),整个的示意图如图4所示。

+

.

边缘的法向方向角H为H[i,j]=tan-1

9f

[i,j]

sobelvert[i,j]=tan-1.

sobel,j]horize[i[i,j]图4 在a,b空间中需要累加的部分

Fig4 Calculatinglinesegmentsperpendiculartoedgedrawn 经过上述的变换后,to就be可以形成累加的亮点了,其中,

因为角度

H和H+P有相同的方向,文中的所有的角度H[i,j]都被归一化到(-P/2,P/2)范围。

最亮的部分就是圆的中心位置,但是,在实际的图像中,由于光线、噪声等因素往往亮斑比较暗和分散,特别是当圆形的物体由于拍摄角度的影响变成了椭圆或其他失真的图像(如图像边缘有毛刺等)时。因此,有必要对离散的亮斑进行聚合,可以选用一个17@17(大小根据实际的亮斑的分散情况)

的墨西哥小帽滤波器,对图像进行聚合,通过选取最亮的一个点或多个点,就可以确定具体的一个或多个圆

图2 边缘提取Fig2 Edgedetecting

心的位置,如图5所示。

2.1.3 图像的边缘细化

经过sobel算子边缘提取后的边缘往往边缘较厚,并且,噪声的影响非常大,

在图像上表现为很突出的亮点。为减少运算量和去除噪声的干扰,还需要对边缘做增强处理,这里是通过一个墨西哥小帽滤波器[4]对边缘图像增强,并采用非极大值抑制的方法选取边缘图像中的最大值作为边缘,处理后的图像结果如图3所示。

图5 累加后得到的圆心Fig5 Centerafteraccumulation

2.2.2 在半径r空间中累加

在定义圆心后,求圆的半径就容易了(因为只是在一维的空间中累加),在(minr,maxr)范围内,在边缘图像中(经过二值化后),在点P的图像边缘强度E(P)累加为

图3 边缘增强Fig3 Egdeimproving

R(r),即

R(r)=

PleE

E(P).

64 传感器与微系统 第25卷

考虑到实际的噪声和环境的影响,为了得到更好的效果,采用2个增强的措施。第一个改进的地方是:对于大的圆,同在二维圆心累加情况类似,累加的结果可能会占优些,所以,可以通过除以半径的方法来改进;另外一个改进的方法是:由于实际的图像获取时的变形(比如圆形的形状变成了稍椭的形状),希望能把这种变形考虑到里面,在做累加的时候,考虑尽可能多的累加点,所以,设置了一个容错角度E,在实际累加边缘方向角度为

在得到了半径空间的累加值后,对它阈值化,阈值选择的不同会提取不同的半径,如果只选择一个最大的阈值,那么,圆的最理想的半径被确定,如果选择一组阈值范围,那么,就可以确定一组同心的圆环。实际中,根据具体的情况来确定。

2.2.3 对圆心和半径进行亚像素精确的微调

在确定圆心和半径的整个过程中,一些不精确的情况会发生。所以,可以进一步的细化到亚像素的精度。在这里,选用插值的方法来细分,首先,在确定了(a,b,r)空间后,可以在它邻域做一像素下的微调,微调的步长(

为了进行像素细分,一个确定亚像素灰度(这里,被二值化为了0和1)最简单的方法是双二次灰度插值,如果要确定位置在(x,y)的灰度值(i[x[i+1,j[y[j+1),其中,i,j是在(x,y)附近整点像素的灰度值。如图6所示,在(x,y)的灰度值为

3 结束语

本文的算法仍保留着Hough变换的优点,对图像中的噪声不敏感。传统的标准Hough变换使用奔腾四2.0G计算,768@576图像的速度通常在10s左右。通过实验,本文的算法计算速度在1s以下,较传统的提高了1个数量级。同时,本文的算法在目标比较清晰、图像不太残缺的情况下,具有较好的结果。由于算法的局限性,对于有较大残缺的圆弧就无能为力了。这就限制了算法的使用范围,需要在今后的工作中解决。参考文献:

[1] 郑南宁.计算机视觉与模式识别[M].北京:国防工业出版

社,1998.154-159.

[2] 朱淼良.计算机视觉[M].杭州:浙江大学出版社,1999.112-118,151-155.

[3] GonzalezRC.数字图像处理[M].北京:电子工业出版社,

2003.467-470.

[4] GonzalezRC.数字图像处理[M].北京:电子工业出版社,

2003.298-304.

图6 像素插值图Fig6 Diagramofinsertvalue

I(x,y)=(1-(x-i))#I(i,j)+(x-i)#I(i+1,j)#(1-(y-j))+

(1-(x-i))#I(x,j+1)+

(x-i)#I(i+1,j+1)#(y-j)

.

作者简介:

张 霄(1980-),男,河南平顶山人,研究方向为GIS中的图像处理。

(上接第61页)5 结束语

本文提出了在雷管卡口工序过程中的一种自动闭锁装置,并对该装置中选用的红外线光电传感器进行了实验测试和数据分析,得出在雷管卡口工序中使用红外线发射接收管是非常理想的传感器。实际运行表明:具有运行稳定可靠、低功耗等优点,彻底地解决了雷管卡口工序中存在的安全隐患。并为今后实现雷管卡口全自动化生产线打下良参考文献:

[1] 常健生,石要武,常 瑞.检测与转换技术[M].北京:机械工

业出版社,2004.1-30.

[2] 黄继昌,徐巧鱼,张海贵,等.传感器工作原理及应用实

例[M].北京:人民邮电出版社,1998.160.

[3] 何希才.传感器及其应用电路[M].北京:电子工业出版社,

2001,(3):90-120.

作者简介:

沙宝银(1979-),男,辽宁葫芦岛人,硕士研究生,研究方向为

62 传感器与微系统(TransducerandMicrosystemTechnologies) 2006年第25卷第4期

计算与测试

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

张 霄,彭 维

(郑州解放军信息工程大学测绘学院,河南郑州450052)

摘 要:Hough变换在图像处理中占有重要地位,但本身具有存储空间大、计算时间长的缺点。利用圆的几何特性,针对Hough变换的缺点进行改进,并将其应用到图像中存在多个圆的情况。实验表明:该算法

能较好地减少存储空间,并降低计算时间,同时,能很好地对图像中多个圆进行检测。关键词:图像处理;Hough变换;圆检测

中图分类号:TN219 文献标识码:A 文章编号:1000-9787(2006)04-0062-03

Detectionofcirclebasedonhoughtransform

ZHANGXiao,PENGWei

(SchoolofSurveyingandMapping,ZhengzhouUniversityofInformationEngineeringofPLA,

Zhengzhou450052,China)

Abstract:Houghtransformtakesanimportantpartintheimageprocessing,butithasthedisadvantagesof

massivestoragespaceandlongcalculationaltime.ThedisadvantagesofHoughtransformaremodifiedbyusingthegeometricalcharacteristicofcircleanditisusedintheinstanceofmult-icirclesinoneimage.Theexperimentsshowthatitcanreducestoragespaceandcalculationaltime,andcanwelldetectmult-icirclesinoneimage.Keywords:imageprocess;Houghtransform;circledetection

0 引 言

人工图像和卫星影像中,比如:光学干涉图像和军事驻地图像,大多数物体都是由线或曲线组成的,所以,图像处理中,对线或曲线的识别和定位就显得十分重要。

Hough变换是一种用于区域边界形状描述的方法,经典Hough变换常常被用于直线段、圆和椭圆的检测。其基本思想是将图像的空间域变换到参数空间,用大多数边界点满足的某种参数形式来描述图像中的曲线(区域边界),通过设置累加器进行累加,求得峰值对应的点就是所需要的信息[1]。

圆的Hough变换有一个最大的缺点就是往往要用进行全局的累加运算,所以,运算量很大。多年来,许多学者利用Hough变换针对具体情况进行了扩展。如利用中心点生成圆弧的方法统计一定范围内点的累加值获得圆心和根据最小二乘法原理用圆来逼近轮廓等,虽然能在一定程度上降低运算量,但是,存在通用性不强和不能十分有效降低运算量的缺点,在实际工程应用中,急需找到一种计算迅速、通用性好的算法。

1 圆的Hough变换检测方法

Hough变换可应用于检测图像空间的解析曲线。解析曲线的参数表示的一般形式为

f(x,a)=0,

式中 x为解析曲线上的点(二维矢量);a为参数空间中的点(矢量)。对于圆来说,半径为r,圆心坐标为(a,b)的圆在参数空间中的表示为

(xi-a)2+(yi-b)2=r2.

(1)

此时,点x=[xi,yi]T,a=[a,b,r]T,其参数空间为三维。

从式(1)可以看出:由于圆的Hough变换涉及的维数过高,达到了三维,如果对图像上所有的点都做运算的话,运算量是非常大的,所以,需要从参与运算和降低维数两方面入手,以提高速度[2]。2 算 法

2.1 减少点数

2.1.1 图像平滑

为了防止噪声的干扰,首先,应用二维的高斯滤波对图像进行平滑处理,以消除噪声,原始的图像如图1所示,高斯滤波器的数学模型如下(假设滤波器的中心在坐标原点)

smoothfilter[i,j]=

(

i+j21-#e2R2.

2PR)2

第4期 张 霄等:基于Hough变换的圆形物体的检测

63

2.2 减少运算的维数

2.2.1 累加圆心(a,b)空间

Hough变换的思想是垂直圆周上的点的直线应该交于圆心。因此,如果在每个边缘点往边缘法向方向做直线,那么,就可以在圆心处得到一个累加的亮斑。因此,在(a,b)

空间中做直线,就会得到圆的中心的交点图,(a,b)空间可

图1 原始图像Fig1 Originalimage

以表示为

a=rsinH

b=rcosH

rI(minr,maxr),

2.1.2 图像边缘检测

应用sobel算子进行边缘检测,分别对图像应用垂直和水平的soble检测算子[3]。

对整个图像做水平和垂直的边缘检测运算后,取它们的模作为整个图像的边缘,图像边缘如图2所示。

|$f|=sobel[i,j]

==

(sobelvert[i,j]+(sobelhorize[i,j])A(i?a,j?b)←A(i?a,j?b)+E(i,j).

minr,maxr是要考虑的半径的范围(可以预设),A是(a,b)空间的数组,E(i,j)是Sobel边缘提取后的边缘的强度(经过二值化后取0或1),整个的示意图如图4所示。

+

.

边缘的法向方向角H为H[i,j]=tan-1

9f

[i,j]

sobelvert[i,j]=tan-1.

sobel,j]horize[i[i,j]图4 在a,b空间中需要累加的部分

Fig4 Calculatinglinesegmentsperpendiculartoedgedrawn 经过上述的变换后,to就be可以形成累加的亮点了,其中,

因为角度

H和H+P有相同的方向,文中的所有的角度H[i,j]都被归一化到(-P/2,P/2)范围。

最亮的部分就是圆的中心位置,但是,在实际的图像中,由于光线、噪声等因素往往亮斑比较暗和分散,特别是当圆形的物体由于拍摄角度的影响变成了椭圆或其他失真的图像(如图像边缘有毛刺等)时。因此,有必要对离散的亮斑进行聚合,可以选用一个17@17(大小根据实际的亮斑的分散情况)

的墨西哥小帽滤波器,对图像进行聚合,通过选取最亮的一个点或多个点,就可以确定具体的一个或多个圆

图2 边缘提取Fig2 Edgedetecting

心的位置,如图5所示。

2.1.3 图像的边缘细化

经过sobel算子边缘提取后的边缘往往边缘较厚,并且,噪声的影响非常大,

在图像上表现为很突出的亮点。为减少运算量和去除噪声的干扰,还需要对边缘做增强处理,这里是通过一个墨西哥小帽滤波器[4]对边缘图像增强,并采用非极大值抑制的方法选取边缘图像中的最大值作为边缘,处理后的图像结果如图3所示。

图5 累加后得到的圆心Fig5 Centerafteraccumulation

2.2.2 在半径r空间中累加

在定义圆心后,求圆的半径就容易了(因为只是在一维的空间中累加),在(minr,maxr)范围内,在边缘图像中(经过二值化后),在点P的图像边缘强度E(P)累加为

图3 边缘增强Fig3 Egdeimproving

R(r),即

R(r)=

PleE

E(P).

64 传感器与微系统 第25卷

考虑到实际的噪声和环境的影响,为了得到更好的效果,采用2个增强的措施。第一个改进的地方是:对于大的圆,同在二维圆心累加情况类似,累加的结果可能会占优些,所以,可以通过除以半径的方法来改进;另外一个改进的方法是:由于实际的图像获取时的变形(比如圆形的形状变成了稍椭的形状),希望能把这种变形考虑到里面,在做累加的时候,考虑尽可能多的累加点,所以,设置了一个容错角度E,在实际累加边缘方向角度为

在得到了半径空间的累加值后,对它阈值化,阈值选择的不同会提取不同的半径,如果只选择一个最大的阈值,那么,圆的最理想的半径被确定,如果选择一组阈值范围,那么,就可以确定一组同心的圆环。实际中,根据具体的情况来确定。

2.2.3 对圆心和半径进行亚像素精确的微调

在确定圆心和半径的整个过程中,一些不精确的情况会发生。所以,可以进一步的细化到亚像素的精度。在这里,选用插值的方法来细分,首先,在确定了(a,b,r)空间后,可以在它邻域做一像素下的微调,微调的步长(

为了进行像素细分,一个确定亚像素灰度(这里,被二值化为了0和1)最简单的方法是双二次灰度插值,如果要确定位置在(x,y)的灰度值(i[x[i+1,j[y[j+1),其中,i,j是在(x,y)附近整点像素的灰度值。如图6所示,在(x,y)的灰度值为

3 结束语

本文的算法仍保留着Hough变换的优点,对图像中的噪声不敏感。传统的标准Hough变换使用奔腾四2.0G计算,768@576图像的速度通常在10s左右。通过实验,本文的算法计算速度在1s以下,较传统的提高了1个数量级。同时,本文的算法在目标比较清晰、图像不太残缺的情况下,具有较好的结果。由于算法的局限性,对于有较大残缺的圆弧就无能为力了。这就限制了算法的使用范围,需要在今后的工作中解决。参考文献:

[1] 郑南宁.计算机视觉与模式识别[M].北京:国防工业出版

社,1998.154-159.

[2] 朱淼良.计算机视觉[M].杭州:浙江大学出版社,1999.112-118,151-155.

[3] GonzalezRC.数字图像处理[M].北京:电子工业出版社,

2003.467-470.

[4] GonzalezRC.数字图像处理[M].北京:电子工业出版社,

2003.298-304.

图6 像素插值图Fig6 Diagramofinsertvalue

I(x,y)=(1-(x-i))#I(i,j)+(x-i)#I(i+1,j)#(1-(y-j))+

(1-(x-i))#I(x,j+1)+

(x-i)#I(i+1,j+1)#(y-j)

.

作者简介:

张 霄(1980-),男,河南平顶山人,研究方向为GIS中的图像处理。

(上接第61页)5 结束语

本文提出了在雷管卡口工序过程中的一种自动闭锁装置,并对该装置中选用的红外线光电传感器进行了实验测试和数据分析,得出在雷管卡口工序中使用红外线发射接收管是非常理想的传感器。实际运行表明:具有运行稳定可靠、低功耗等优点,彻底地解决了雷管卡口工序中存在的安全隐患。并为今后实现雷管卡口全自动化生产线打下良参考文献:

[1] 常健生,石要武,常 瑞.检测与转换技术[M].北京:机械工

业出版社,2004.1-30.

[2] 黄继昌,徐巧鱼,张海贵,等.传感器工作原理及应用实

例[M].北京:人民邮电出版社,1998.160.

[3] 何希才.传感器及其应用电路[M].北京:电子工业出版社,

2001,(3):90-120.

作者简介:

沙宝银(1979-),男,辽宁葫芦岛人,硕士研究生,研究方向为