JournalofZhejiangUniversity(EngineeringScience)
浙 江 大 学 学 报(工学版)
Vol.42No.8Aug.2008
DOI:10.3785/j.issn.10082973X.2008.08.015
基于最小二乘法的改进的随机椭圆检测算法
陈海峰1,雷 华1,孔燕波2,周柳云2,冯华君1
(1.浙江大学现代光学仪器国家重点实验室,浙江杭州310027;2.宁波华光精密仪器有限公司,浙江宁波315153)摘 要:为了提高数字图像中椭圆检测的效率和准确性,提出了一个基于最小二乘法的改进的随机椭圆检测算法.该算法随机选取图像中的3个边缘点,在以这3个点为中心的窗口内,从边缘点中拟合出可能椭圆,并通过随机选取的第4个边缘点来确认可能椭圆.利用直接最小二乘法椭圆拟合的特性,引入可能椭圆边缘点收集和椭圆重新拟合的迭代过程来提取最终的椭圆参数.通过对含有不同噪声的仿真图片和包括残缺椭圆的实际图片的实验表明,新算法的改进是有效的.与原算法相比,新算法降低了对参数的依赖性,提高了检测的速度、稳定性和准确性,同时保留了原算法的抗噪声能力.关键词:椭圆检测;随机检测;最小二乘法
中图分类号:TP391 文献标识码:A 文章编号:10082973X(2008)0821360205
Animprovedrandomizedalgorithmfordetectingellipses
basedonleastsquareapproach
CHENHai2feng1,LEIHua1,KONGYan2bo2,ZHOULiu2yun2,FENGHua2jun1
(1.StateKeyLaboratoryofModernOpticalInstrumentation,ZhejiangUniversity,Hangzhou310027,China;
2.HuaguangPrecisionInstrumentCo.Ltd.,Ningbo315153,China)
Abstract:Animprovedrandomizedellipsedetectionalgorithmbasedonleastsquareapproachwasproposedtoenhancetheefficiencyandaccuracyofellipsedetectionindigitalimages.Thisalgorithmrandomlyse2lectsthreeedgepointsintheimage,andthenusesleastsquareapproachtofitalltheedgepointsinthreewindows,whicharedefinedbythethreeedgepoints.Theforthedgepointisrandomlyselectedtojudgewhetherapossibleellipseexistsintheimage.Utilizingthecharacteristicofdirectleastsquarefittingofellipse,aniterationprocessofedgepointcollectingandellipserefittingofpossibleellipsewasintroducedtoextractthefinalellipse.sparameters.Artificialimageswithdifferentlevelsofnoiseandnatureimagescontainingincompleteellipseswereemployedtotestthisalgorithm.Experimentalresultsshowthattheimprovementsarenotable.Comparedwiththeoriginalalgorithm,theproposedalgorithmreducesthede2pendenceonargumentsofdetectionalgorithm,andenhancesthespeed,stabilityandaccuracyofellipsede2tection,whilepreservestheanti2noiseabilityoftheoriginalalgorithm.Keywords:ellipsedetection;randomizeddetection;leastsquareapproach 椭圆检测在模式识别领域一直是研究的热点.在过去的20多年中,人们提出了很多椭圆检测算
法.例如:基于Hough变换及其改进算法的椭圆检测算法、最小二乘拟合算法、基于随机抽样一致性
收稿日期:2007205218.浙江大学学报(工学版)网址:www.journals.zju.edu.cn/eng
基金项目:宁波市科技计划资助项目(2006B100027).
作者简介:陈海峰(1982-),男,浙江台州人,硕士生,从事数字图像处理工作.E2mail:optical.dlz@gmail.com
通讯联系人:冯华君,男,教授,博导.E2mail:fenghj@zju.edu.cn
第8期
陈海峰,等:基于最小二乘法的改进的随机椭圆检测算法
1361
(randomsampleconsensus,RANSAC)思想的算法、遗传算法以及结合椭圆几何特性的算法.这些算法大致可以分为投票(类聚)和最优化2大类.Hough变换、RANSAC算法都是采用映射的方法,将样本点映射到参数空间,采用累加器或者类聚的方法来检测椭圆.这类算法具有很好的健壮性,能够一次检测多个椭圆,但是需要复杂的运算和大量的存储空间.最优化方法包括最小二乘拟合算法、遗传算法以及其他最优化椭圆拟合方法.这类方法的主要特点在于准确性高,但是通常需要预先进行分割数.np表示集合V中边缘点的数量,当其与图片中边缘点总数的比值小于Tem时,终止椭圆检测算法.在可能椭圆上选中的任意两点之间的距离必须大于阈值Ta.Td表示所选的第4点到可能椭圆边界的距离的阈值.Tr为椭圆残缺率阈值.
2)当f=Tf或者np 近年来,人们对椭圆检测的研究大多在数据点收集、椭圆真伪的验证和各类方法相互结合的方向上展开.Cheng等人[1]提出的受限随机Hough变换(restrictedrandomizedHoughtransform,RRHT),限制了点选取的范围,有效缩短了算法运行的时间,提高了算法的效率.Qiao等人[2]推荐的基于圆弧的椭圆验证方法极大地减少了虚假椭圆的输出.Li等人[324] 提出的随机椭圆检测(randomizedellipsede2tection,RED)方法,巧妙地结合了最小二乘法和随机Hough变换的优点,实现了基于随机Hough变换并利用最小二乘法进行椭圆拟合的检测方法,该方法不需要占用大量的存储空间,另外对噪声不敏感,能够快速检测多个椭圆. 本文首先分析了RED算法,针对基于直接最小二乘法的椭圆拟合的特点,引入了一个可能椭圆边缘点收集和椭圆重新拟合的迭代过程,提出了一种基于最小二乘法的改进的随机椭圆检测算法,解决了原算法中存在的问题.通过对具有不同噪声的仿真图片和实际图片的实验,验证了算法改进的有效性. 1 RED算法 1.1 RED算法介绍 RED方法首先随机选取3个边缘点,并分别以这3个边缘点为中心,定义具有相同大小的窗口,利用最小二乘法把这3个窗口中的所有边缘点拟合成一个假设存在的椭圆.然后在图像中随机选取第4个边缘点,判断这个点是否在假设的椭圆上.如果是,则椭圆存在的可能性较大,接着引入证据收集过程来验证椭圆是否真实存在.算法步骤如下. 1)将所有边缘点pi=(ui,vi)加入集合V中.初始化失败,计数器f=0.令Tf、Tem、Ta、Td、Tr分别为给定的5个阈值.Tf表示能够容忍的最大失败次 点之间的距离都大于Ta,同时第4个点到可能椭圆边界的距离不能超过Td.否则,将pi(i=1,2,3,4)返回到V中,f=f+1,跳转到步骤2). 4)假设Eijk是可能的一个椭圆.设计数器n=0.对于V中的点pm,检查它到椭圆Eijk边界的距离是否小于阈值Td.如果是,则n=n+1,并将pm从V中去除.在遍历V中所有点之后,得到ne=n,即为满足阈值Td的边缘点的个数. 5)如果ne\\Tr#Cijk,其中Cijk是可能椭圆Eijk 的周长,则跳转到步骤6).在其他情况下,认为这个可能的椭圆不是一个真实的椭圆,将步骤4)中的ne个边缘点返回到V中,f=f+1,跳转到步骤2).6)可能存在的椭圆Eijk被证实是真实存在的一个椭圆.将f重置,跳转到步骤2).1.2 RED算法中存在的问题 RED算法使用直接最小二乘法椭圆拟合(di2rectleastsquaresfittingofellipse)算法来求解可能椭圆的参数.Halir等人[5]指出由于该拟合算法是基于代数距离而非几何距离的,因而当拟合含有噪声的椭圆弧时,得到的椭圆通常偏小.当拟合图像中的椭圆数据点时,由于算法本身就有这种倾向,若选取的3个窗口中心点之间的距离较近,加上图像光栅化的影响(图像中椭圆的边缘点相对于理想的边缘点而言噪声总是存在的),拟合出来的椭圆和真实的椭圆差别很大.Li等人的算法只能依靠在提取可能椭圆时,随机选取的3点之间保持适当的距离,和在椭圆确认过程中使用较大的值来解决这个拟合算法带来的问题.但是这种处理方法在实际处理过程中存在较为明显的缺陷. 1)算法的效率严重地依赖于参数Ta,不合适的Ta不仅增加了算法中证据收集的计算量,还会浪费很多有效采样次数.而且合适的Ta值会随着被检测椭圆的大小发生变化,因此当处理包含大小差异较大的椭圆图形的图片时,Ta的值难以确定. 2)当Ta取不到合适的值,Tr又无法选取较大 1362 浙 江 大 学 学 报(工学版) 使用可能椭圆Eijk求解自适应阈值Td: 第42卷 的数值时(也就是处理包含大小差别较大的残缺椭圆的图像),采用直接椭圆拟合算法得到的偏小的可能椭圆,会因为较小的Tr值而被算法确认为真椭圆,从而产生误检.由于在检测到一个椭圆后,算法会将在这个椭圆上的边缘点去除,这种误检就可能导致一个真实存在的椭圆被分割成数个椭圆弧,继而引发更多的误检,使得算法的检测效率很低. 3)算法只考虑了当选取的点之间距离较近时会拟合出虚假的椭圆,没有排除当距离过大时算法会从不同椭圆弧中拟合出虚假椭圆的情况.后一种情Td=|au2A+buAvA+vc2A+duA+evA+1|,uA=u0+(A+ddiff)#cosU,vA=v0+(A+ddiff)#sinU. 式中:u0、v0为椭圆的中心点坐标,ddiff为点到椭圆边界的最大距离,A、U分别为椭圆的长轴长度和椭圆的偏转角度. 在迭代过程中,需要考虑在边缘二值图像中噪声的影响.过量的噪声将会延长迭代收敛的过程,因此况会当Tr较小时,被算法确认为真椭圆,降低算法检测的效率. 2 改进的RED算法 2.1 改进的椭圆提取过程 在RED算法的实际拟合过程中,用来拟合的边缘点始终位于最后拟合出来的椭圆的边界上.假设这些边缘点位于一个真实的椭圆上,那么可以选择适当的代数距离来收集距离拟合出的可能椭圆边界一定范围内的边缘点: D=|au2+buv+cv2+du+ev+1|. 然后通过重新收集和重新拟合的迭代过程来找出这个真实的椭圆.通过此过程,无须事先找出最适合的Ta,只要将选取的3个点之间的距离控制在一定的范围即可. 在新的提取过程中,求取适当的代数距离阈值非常关键.一般来说,如果一个点位于椭圆上,那么理想的D值应该为零.实际上,由于图像是光栅化的,边缘上的点几乎不可能准确地落在椭圆的边界上.图1显示了一系列椭圆的D值的最大值和平均值.这些椭圆的长轴、短轴、中心位置都是一致的,惟一不同的就是椭圆长轴和X轴的夹角. 从图1中不难看出,在实际情况下,光栅化后椭圆的D值大小随H发生很大的变化.因此,本算法 图1 D2H曲线Fig.1 D2Hcurves 在执行之前需要将这些噪声点从边缘图像中去除.本文采用黎自强等人 [6] 提出的去除孤立和半连续噪声 点的方法.这两类噪声点的定义如下:在图像空间中,若Pi(ui,vi)的8个相邻点都不是图像点,则称P为孤立噪声点.若Pi(ui,vi)的4@4邻域满足:1)边界点都不是图像点;2)除了Pi(ui,vi),在其相邻点中还有1~3个图像点,则称P为半连续噪声点. 2.2 改进算法的具体步骤 改进的RED算法只须在原有算法的步骤5)和6)中插入新的椭圆提取过程.具体流程如下. 1)初始化T=0;设置最大迭代次数Tt和最小变化率Tn,用于算法的终止;将ne的值赋给nold. 2)用收集来的位于可能椭圆边界附近的边缘点组成的可能椭圆边界点集合Ve来重新拟合可能椭圆Eijk;T=T+1. 3)根据可能椭圆Eijk求解Td的大小;遍历集合V中的边缘点,寻找D[Td的边缘点,更新ne和可能椭圆边界点集合Ve,并将ne赋给nnew;如果|nnew-nold|/nold>Tn并且T 在一台Celeron2.0GHz的计算机上利用Matlab6.5对改进的RED算法进行了仿真图片和实际图片的实验.主要分析算法改进前后检测的时间、准确率[7]和抗噪声的能力.对于每一副图片,取100次检测的结果作为样本.选用的参数在各个实验中分别给出.在下面的图表中用Orig表示原RED算法,Mod表示改进的RED算法. 实验1 分别用原RED算法和改进的RED算法对3幅640@480的仿真图片进行检测,如图2(a)所示.其中图片1含有3个不同方向的完整椭 圆;图片2含有3个不同方向的重叠的椭圆;图片3含有3个不同方向的部分重叠的椭圆弧,并且这些 第8期 陈海峰,等:基于最小二乘法的改进的随机椭圆检测算法 表1 实验选用的各个参数Tab.1 Argumentsusedinexperiment1实验 Tf Ta Orig Mod Tr Tem0.10.3(图片4)0.1(图片5) 1363 ddiff55 实验1、25000实验3 5000 3030~3600.53030~1200.5 图2(b)、(c)列出了原RED算法和改进的RED算法的检测结果.检测到的椭圆用粗线重绘,加号表示椭圆中心点位置.表3进一步给出了2个算法比较的结果,包括算法检测的最短时间tmin、最长时间tmax、平均时间tavg、标准时间tstd和准确率pacc.在本文设定的实验例子中,原RED算法无法继续使用Ta、Tr的限制来解决拟合算法带来的问题,导致整个椭圆算法运行时间较长,稳定性不佳,有较多误检的情况影响其他真实存在椭圆的检测.改进的RED算法很好地解决了拟合算法带来的问题,无论在准确性、稳定性上,还是在检测速度上都超越了原RED算法. 实验2 检测改进的RED算法抗椒盐噪声的能力.选用实验1中使用的仿真图片,在实验中加入的椒盐噪声的数量为Nnoise,从边缘点数量的1倍逐渐增加到6倍.为保证对照的有效性,原RED算法处理的图片同样经过了前面提到的剔除2类噪声的处理.算法的参数和实验1相同.结果如图3和4所示.可以看出,改进的RED算法在3倍噪声以内时表现非常出色,在超过这个范围之后,算法的准确性和消耗的时间都有所恶化,但是依然好于原RED算法. 图2 改进的RED算法与原RED算法的检测结果(仿 真图片) Fig.2 DetectionresultsofimprovedREDalgorithm andoriginalREDalgorithm(artificialimage) 实验3 选用实际的图片对改进的RED算法进行测试,原RED算法作为对照.图片大小均为640@480,图片4包含多个大小、方向各异,残缺度不同的椭圆,图片5包含多个偏心率接近零的椭圆,如图5(a)所示.实验中选用绝对误差模板(absolutediffer2encemask,ADM)算法作为边缘检测算子.同样选取Tr=0.5,Ta=30,Tem值则按照实际情况做了调整,具体参数见表1.实验结果如表2与图5所示. [8] 图片中包含的3个椭圆的大小差别较大.根据文献[4],实验选取Tr=0.5,在原RED算法中根据符合图片中最小残缺椭圆的检测要求,选取Ta=30,算法的具体参数如表1所示. 表2 改进的RED算法与原RED算法的性能比较 Tab.2 PerformancecomparisonofimprovedREDalgorithmandoriginalREDalgorithm 图片12345 tmin/sOrigMod0.0790.0810.0846.23510.93 0.0460.0590.0581.2970.559 tmax/sOrigMod32.5524.8531.2857.4766.06 0.6101.1131.66714.703.537 tavg/sOrigMod9.5778.9006.44427.1335.42 0.2080.2670.3809.7551.575 tstd/sOrig8.9006.8397.2879.82011.88 Mod0.1280.1720.2592.1160.641 pacc/%OrigMod74.0053.3363.3347.4753.40 100.0100.099.6790.0089.69 1364 浙 江 大 学 学 报(工学版) 第42卷 方法进行了改进.新方法在确认一个可能椭圆之后,使用自适应的Td阈值搜索边缘图片中距离可能椭圆边界一定范围内的点,并拟合出一个新的可能椭圆.通过重复上述搜索和重新拟合过程,准确地找到了图片中的椭圆.对仿真图片和实际图片的实验表明,改进算法有效解决了原方法存在的问题.使得算法对参数Ta、Tr的依赖程度大大下降,改善了算法对不同情况的适应性.新算法在提高检测的速度、稳定性和准确性的同时,保留了原算法抗噪声的能力. 4 结 语 本文对原有的基于最小二乘法的随机椭圆检测 参考文献(References): [1]CHENGZi2guo,LIUYun2cai.Efficienttechniquefor ellipsedetectionusingrestrictedrandomizedHoughtransform[C]MProceedingsoftheInternationalConfer2enceonInformationTechnology:CodingandComputing.LasVegas:IEEE,2004,2:7142718. [2]QIAOYu,ONGSH.Arc2basedevaluationanddetec2 tionofellipse[J].PatternRecognition,2007,40(7):199022003. [3]LILiang2fu,FENGZu2ren,HEKai2liang.Arandom2 izedalgorithmfordetectingmultipleellipsesbasedonleastsquareapproach[J].Opto2electronicsReview, 2005,13(1):61267. [4]李良福,冯祖仁,贺凯良.一种基于随机Hough变化的 椭圆检测算法研究[J].模式识别与人工智能,2005,18(4):4592464. LILiang2fu,FENGZu2ren,HEKai2liang. Anim2 provedalgorithmforellipsesdetectionbasedonrandom2izedHoughtransform[J].PatternRecognitionandArti2ficialIntelligence,2005,18(4):4592464. [5]HALIRR,FLUSSERJ.Numericallystabledirectleast squaresfittingofellipses[C]MProceedingsofthe6thInternationalConferenceinCentralEuropeonComputerGraphicsandVisualization.Plzen:UniversityofWestBohemia,1998:1252132. [6]黎自强,腾弘飞.广义Hough变换:多圆的快速随机检 测[J].计算机辅助设计与图形学学报,2006,18(1):27233. LIZi2qiang,TENGHong2fei.GeneralizedHoughtrans2form:fastrandomizedmulti2circledetection[J].Com2puterAidedDesignandComputerGraphics,2006,18(1):27233. [7]MCLAUGHLIMRA.RandomizedHoughtransform: improvedellipsedetectionwithcomparison[J].PatternRecognitionLetters,1998,19(3):2992305. [8]ZHANGSi2cheng,LIUZhi2qiang.Arobust,real2time ellipsedetector[J].PatternRecognition,2005,38(2):2732287. 因篇幅问题不能全部显示，请点此查看更多更全内容