外文翻译原文-霍夫圆变换方法的比较研究发现

ACOMPARATIVESTUDYOFHOUGHTRANSFORMMETHODSFORCIRCLEFINDINGH.K.Yuen,J.Princen,J.IllingworthandJ.KittlerDepartmentofElectronicsandElectricalEngineeringUniversityofSurrey,Guildford,GU25XH.U.K.TheobjectiveofthispaperistoinvestigateanumberofcircledetectionmethodswhicharebasedonvariationsoftheHoughTransform.Themethodsconsideredin-cludethestandardHoughTransform,theFastHoughTransformofLietal,twospacesavingapproacheswhicharebusedonthosedevisedbyGerigandKleinandatwo-stagemethod.Weexperimentallycomparetheperfor-manceofthemethodsandillustratepropertiessuchasaccuracy,reliability,computationalefficiencyandstor-agerequirements.Inrecentyears,severalmethodsofcirclefindingbasedontheHoughTransform(HT)havebeenproposed1,2aswellassomegeneraltechniquesforfastimplementa-tionoftheHT3,4.Invariablythesemethodsclaimtoimproveefficiency,storageorreliabilitythoughinmostcasesthecomparisonsmadewithothertechniquesaresuperficial.Wefeelthatthisisabouttherighttimetoputanumberofthesealgorithmstogetherandexaminetheirpropertiesinmoredetail.Thestudyisexperi-mentalandweconsiderbothrealandsyntheticimages.OurresultsshowthatmoresophisticatedvariationsoftheHTmethoddonotnecessarilyout-performstraight-forwardapproaches.Thepaperisorganisedasfollows.InthenextsectionweintroducethecirclefindingproblemandthebasicideaunderlyingtheHT.Thisisfollowedbyabriefdescrip-tionofeachofthefiveHTbasedmethodsconsideredinourstudy.Theexperimentalevaluationofeachmethodisthengivenandthefinalsectionpresentstheconclu-sionsofourwork.CIRCLEFINDINGUSINGTHEHTIfacircleintheimageisdescribedas(1)where(a,6)arethecoordinateofthecirclecenterandrisitsradius,thenanarbitraryedgepoint(i,y,)willbetransformedintoarightcircularconeinthe(a,6,r)parameterspace5.Ifalltheimagepointslieonacirclethentheconeswillintersectatasinglepointin(a,6,r)correspondingtotheparametersofthecircle.Kimmeetal6giveprobablythefirstknownapplicationoftheHoughTransformtodetectingcirclesinrealimages.Intheirwork,theyhavemadeuseofthedirectionofthegradientateachedgepoint.Thecentreofacirclemustlieonthenormalattheedgepoint.Asaresultinsteadofincrementingthewholecircularcone,onlysegmentsoftheconeneedbeincremented.Thesizetheregionwhichisincrementeddependsontheaccuracyoftheedgedirectionestimation.AnimportantpartofthecompleteHTprocessispeakdetection.Anextremelyusefultechniquewhichwehavefoundeasesthepeakfindingproblemconsiderablyisthepost-processingmethodproposedbyGerigandKlein1.Itconsistsofaseconddaapasswhichtakeseachedgepointandidentifiesthemaximumvalueintheac-cumulatorarrayoutofallparametervaluesvotedforbythepoint.Theedgepointislabelledwiththislocation.Inallthemethodsconsidered,thistechniqueisusedtodetectthefinalpeaks.Wereferthereaderto7,10fordetails.THESTANDARDHTTheStandardHoughTransform(SHT)inthisstudyfollowsthebasicideaoutlinedintheprevioussection.A3-Daccumulatorarrayisemployedandedgedirec-tioninformationisusedtolimitvotingtoasectionofthecone.Inanidealsituation,thecentreofthecirclemustlieonalineorientednormaltotheedgedirection.Thereforeweonlyhavetomovealongthenormalofev-eryedgepointtofindthepossiblelocationsofcenters.Thedistancebetweeneachedgepointandtheestimatedcenterisacandidateforradiusofthecorrespondingcir-cle.However,inpractice,theedgedirectionisusuallyestimatedinaccurately.Asaresult,thedetectionofthetruelocalmaximumintheaccumulatorarraycouldbedifficultifthissimpleaccumulationstrategyisused.IfthedirectionerrorisknowntobewithinarangeofA(,thenwemaysaythatthecenterofthecircleforthepoint(xinthethreedimensionalHoughspaceconsistsoftwoorthogonalstraightlinespointingoutwardfromthepoint(a:,-,t/j,O).Todeter-minewhetherahypercubehasbeenintersectedbyoneofthesetwolines,wecomparetheperpendiculardis-tancefromthecenterofthehypercubetothelineswiththediagonallengthofthehypercube.Iftheformerisshorter,thehypercubewillreceiveonevote.UnliketheoriginalFHT,thereisnoincrementalupdatingfortheintersectiontest.Inordertoimprovetheefficiencyofthealgorithm,wehavedevelopedaschemetochooseasuitablethresh-oldvalueadaptivelybasedontherangeofradiusbeingsearchedandatthesametime,reducethesearchingrangeofradius10.Theresultspresentedarebasedonthisstrategy.EXPERIMENTALCOMPARISONTherearemanycriteriawhichcanbeconsideredinanycomparisonofalgorithmsbutinourstudythemostim-portantpointsrelatetotheaccuracy,robustness,com-putationalcomplexityandstorage.Theaccuracyismeasuredbycomparingtheabsoluteerrorsofthees-timatedradiiandcentercoordinatestothetruevaluesofcirclesinsyntheticimages.Wepresentatypicalex-ampleusinganimageconsistingof19randomlygener-atedcircles.Totestthedetectioncapabilitiesofeachalgorithm,arealimageconsistingofabout76circlesofvariousradii,countedsubjectively,isexamined.Thenumberofmissingandfalsecirclesarecountedforeachalgorithm.Toestimatecomputationalefficiencyweusethetimetakentoruneachalgorithmonour/iVAX-2computer.Werealisethatasameasureofefficiencythisisnotnecessarilyofgeneralsignificance.Howeverallal-gorithms,excepttheFastHoughTransform,areverysimilarandthereforeatleastinacoarsesensewewouldexpecttheconclusionsregardingefficiencytohold.The170majortimeconsumptionforeachalgorithmoccursfortransformaccumulationandtheimplementationoftheGerigandKleinpost-processing.The2stagemethodalsoexpendsasignificanttimefortheradiushistogramstep.Thestoragerequirementsforeachmethodaredominatedbytheaccumulatorarray(s).NotethatallthealgorithmswerecodedinPASCAL.Figures1and2showtheedgesofthesyntheticandrealimages.TheedgepointsineachimageareidentifiedusingamethodbasedontheCannyedgedetector9followedbybinarythinningoftheresultantthresholdededgemap.TheedgedirectionofthesyntheticimageissmearedbyaUniformdistributednoiseintherange5,5.ThissmearingdoesnotaffecttheperformanceoftheGKHTmethodasedgedirectionisnotused.Fortheothermethods,threedifferenterrorbounds,0,5and10,areassumedforedgedirectionaccuracy.Fig-ure3showsthecorrespondingmeansoftheabsoluteerrorofthethreeparameters.ItisinterestingtonotethattheGKHTmethodachievedazeroerrorforthera-diusparameterwithoutusingthegradient.The21HTmethodisverysensitivetotheassumptionofvalueoftheerrorbound.Itachievesverysmallerrorsfortheparametersattheerrorboundof5.TheresultfortheMFHTattheerrorboundof0isverygoodbuttheresultatthe10isnotavailableduetothelargestor-agerequirement.ThemeansofabsoluteerroroftheSHTmethodaregenerallylargerthanthosefromothermethods.TheresultoftheGHTGisgoodinmostcasesandthemeansremainstableastheassumptionoftheerrorboundincreases.Itisdifficulttochoosethebestmethodbasedonthissingleexample.However,basedontheresultsfromotherexperiments10,the21HTandGHTGmethodsseemtobemoreaccuratethantheothers.Table1showsforthesyntheticimagethenumberofmissingandfalsecirclesfoundbyeachalgorithmatdif-ferentassumededgedirectionerrorbounds.ThebestperformanceinthiscaseisobtainedwiththeGHTGmethodwhichonlymissed2and1circlesattheerrorboundsof0and5respectivelyanddetectedallthe19circlesusingtheerrorboundof10,seefigure4.Wefoundthatusingthe2stagemethod,errorsinthefirststagecausedproblemsinthesecondstagehis-togram.Itcanbeshownthatifthemagnitudeofthecentreerrorisgreaterthanthehistogramcellwidthasinglecirclewillproducetwopeaksintheradialhistogram10.Thepeaksaresymmetricallylocatedaroundthetrueradiusandthedistancebetweenthemdependsonthecentreerror.Thismakesconcentriccir-clesdifficulttodistinguishfromdoublepeaksduetocentreerrors.ThemoststrikingobservationconcerningtheMFHTisthatitexhauststheavailablestorageoftheVAXma-chineinthecaseof10errorboundandthereforetheresultisnotavailable.ThisproblemrelatestothelargenumberofphantompeakswhichtheMFHTinvestigatesbeforediscoveringthecorrectones.Thealgorithmper-formsreasonablywellintermsofefficiency,accuracyandreliabilityusingtheothererrorbounds.Figure5showstheCPUtimeforthealgorithms.Inthiscase,theperformanceofthe21HT,GHTGandSHTareveryclosetoeachother.AsexpectedtheGKHTwhichdoesnotusegradientdirectiontakessignificantlylongerthanGHTG.Thecomparativestudywouldnotbecompletewithoutapplyingthealgorithmstorealimages.Figure6givestherunningtimeofthealgorithmsontherealimageshowninfigure2.Theerrorboundisassumedtobe5fortheMFHTmethod(becauseofstorageproblemmentionedpreviously)and10forthe21HT,GHTGandSHTmethods.Thetimetakenbythealgorithms21HT,GHTGandSHTareveryclosetoeachother.Howeveroncountingthemissingandfalsecircles,asshownintable2,theGHTGout-performsalltheothermethodswithonly3circlesmissingoutof76.Thereare,however,10falsecirclesdetectedbythealgorithm.Allofthemareverysmallcircleswithradius1or2.Thesefalsecirclesarefoundfrombadlydetectededgepointswhichareinfacttruecircleswithverylowgreylevelintheoriginalimage.Figure7showstheresultofcirclefindingusingtheGHTGmethod.Inmostmethods,thestoragerequirementsdependdi-rectlyontheparameterrangesandthequantizationofeachparameteraxis.Wehaveused2562imagesandonlydetectcirclecentreswhichlieinsidetheimage,henceaand6arewithin(0,256).Theradiuswaslim-itedtoliebetween(1,35).Eachaxiswasdividedinto1unitcells.Consideringthestoragerequirementsofeachofthe5algorithms,asshownintable3weseethatthe21HTmethodhasaclearadvantageovertheothers.TheGKHTandGHTGarethesecondbest.Thestor-agerequirementoftheMFHTisratherunpredictable.Itwilldependonthecomplexityoftheimage,choiceofthresholdvalueandtheerrorboundassumption.CONCLUSIONSTheresultsofourstudyindicatethatboththeGKHTandMFHTexperienceseveredifficultiesifappliedtocompleximages.ThemainproblemoftheGKHTistheunreliabilityandlowefficiencyduetothefactthatedgedirectioninformationisnotincorporatedinthemethod.TheMFHTsuffersfromtheunpredictablestorageandcomputationalrequirement,andhasthemostcompli-catedprogrammingstructureincomparisonwiththeothermethods.Nevertheless,bothmethodsmaystillbeusefuliftheyareappliedtosimpleimageswithverylownoise.Ithasbeenshownthattheperformanceofthe21HT,GHTGandSHTareveryclosetoeachother.Themain171drawbackfortheSHTisthelargestoragerequirementforimagesconsistingofcirclesofdifferentsizes.Al-thoughtheGHTGisrestrictedtonon-concentriccir-cles,wehavefound,fromotherexperimentalresults10,thattheGHTGgenerallypeformsbetterthanthe21HTmethodinthesenseofrobustness.Thisisduetothefactthatthe21HTisa2stagemethodandanyerroroccurringinthefirststageofcenterfindingwillcausedifficultiesinthepeakfindingofthesecondradiusfind-ingstage.ACKNOWLEDGEMENTSThisworkwascarriedoutaspartofALVEYcontractMMI/078,acollaborativeprojectinvolvingSurreyUni-versity,Heriot-WattUniversityandComputerRecogni-tionSystemsofWokingham.REFERENCES1.GerigG.andKleinF.FastcontouridentificationthroughefficientHoughTransformandsimplifiedinter-pretationstrategy,8thIJCPR,Paris,pp498-500,1986.2.DaviesE.R.AmodifiedHoughschemeforgeneralcirclelocation,PatternRecognitionLetters,vol7,no.1,pp37-44,1988.3.IllingworthJ.andKittlerJ.TheadaptiveHoughTransform,IEEETrans.PatternAnalysis&MachineIntelligence,vol9,no.5,pp690-697,1987.4.LiH.,LavinM.A.andLeMasterR.J.FastHoughTransform:Ahierarchicalapproach,CVGIP,36,pp139-161,1986.5.DudaR.O.andHartP.E.UseoftheHoughTransformationtodetectlinesandcurvesinpictures,Comm.oftheACM,vol15,no.1,pp11-15,1972.6.KimmeC,BallardD.andSklanskyJ.Findcirclesbyanarrayofaccumulators,Comm.oftheACM,vol18,no.2,pp120-122,1975.7.PrincenJ.,YuenH.K.,IllingworthJ.andKit-tierJ.AcomparativestudyofHoughTransformAl-gorithms:PartI-Linedetectionmethods,DepartmentofElectronicandElectricalEngineering,UniversityofSurrey,U.K.8.IllingworthJ.,KittlerJ.andPrincenJ.ShapedetectionusingtheAdaptiveHoughTransform,inPro-ceedings,NATOAdvancedResearchWorkshoponReal-TimeObjectandEnvironmentMeasurementandClas-sification,Maratea,Italy,September1987,Springer-Verlag,NewYork/Berlin.9.CannyJ.Acomputationalapproachtoedgede-tection,IEEETrans.PatternAnalys