外文翻译原文-利用Hough变换检测图像的直线和曲线

GraphicsandW.NewmanImageProcessingEditorUseoftheHoughTransformationToDetectLinesandCurvesinPicturesRichardO.DudaandPeterE.HartStanfordResearchInstitute,MenloPark,CaliforniaHoughhasproposedaninterestingandcomputationallyefficientprocedurefordetectinglinesinpictures.Thispaperpointsoutthattheuseofangle-radiusratherthanslope-interceptparameterssimplifiesthecomputationfurther.Italsoshowshowthemethodcanbeusedformoregeneralcurvefitting,andgivesalternativeinterpretationsthatexplainthesourceofitsefficiency.KeyWordsandPhrases:pictureprocessing,patternrecognition,linedetection,curvedetection,colinearpoints,point-linetransformation,HoughtransformationCRCategories:3.63Copyright(1972,AssociationforComputingMachinery,Inc.Generalpermissiontorepublish,butnotforprofit,allorpartofthismaterialisgranted,providedthatreferenceismadetothispublication,toitsdateofissue,andtothefactthatreprintingprivilegesweregrantedbypermissionoftheAssociationforCornputingMachinery.ThisworkwassupportedbytheAdvancedResearchProjectsAgencyandtheNationalAeronauticsandSpaceAdministrationunderContractNAS12-2221.111.IntroductionArecurringproblemincomputerpictureprocessingisthedetectionofstraightlinesindigitizedimages.Inthesimplestcase,thepicturecontainsanumberofdis-crete,blackfigurepointslyingonawhitebackground.Theproblemistodetectthepresenceofgroupsofco-linearoralmostcolinearfigurepoints.Itisclearthatheproblemcanbesolvedtoanydesireddegreeofac-curacybytestingthelinesformedbyallpairsofpoints.However,thecomputationrequiredfornpointsisap-proximatelyproportionalton2,andmaybeprohibitiveforlargen.Rosenfeld1hasdescribedaningeniousmethodduetoHough2forreplacingtheoriginalproblemoffind-ingcolinearpointsbyamathematicallyequivalentprob-lemoffindingconcurrentlines.Thismethodinvolvestransformingeachofthefigurepointsintoastraightlineinaparameterspace.Theparameterspaceisdefinedbytheparametricrepresentationusedtodescribelinesinthepictureplane.Houghchosetousethefamiliarslope-interceptparameters,andthushisparameterspacewasthetwo-dimensionalslope-interceptplane.Unfortunately,boththeslopeandtheinterceptareun-bounded,whichcomplicatestheapplicationofthetech-nique.Inthisnotewesuggestanalternativeparameteri-zationthateliminatesthisproblem.Wealsogivetwoal-ternativeinterpretationsofHoughsmethod,oneofwhichrevealsplainlythesourceofitsefficiency.Finally,weshowhowthemethodcanbeextendedtofindmoregeneralclassesofcurvesinpictures.2.FundamentalsThesetofallstraightlinesinthepictureplanecon-stitutesatwo-parameterfamily.Ifwefixaparameteriza-CommunicationsJanuary1972ofVolume15theACMNumber1tionforthefamily,thenanarbitrarystraightlinecanberepresentedbyasinglepointintheparameterspace.Forreasonsthatbecomeobvious,weprefertheso-callednormalparameterization.AsillustratedioFigure1,thisparameterizationspecifiesastraightlinebytheangle0ofitsnormalanditsalgebraicdistancepfromtheorigin.TheequationofalinecorrespondingtothisgeometryisxcosO+ysinO=p.Ifwerestrict0totheinterval0,-,thenthenormalparametersforalineareunique.Withthisrestriction,everylineinthex-yplanecorrespondstoauniquepointinthe0-oplane.Supposenow,thatwehavesomeset(xa,ya),.,(x,y,)ofnfigurepointsandwewanttofindasetofstraightlinesthatfitthem.Wetransformthepoints(x,y)intothesinusoidalcurvesinthe0-pplanede-finedbyo=xcos0+ysin0.(1)Itiseasytoshowthatthecurvescorrespondingtoco-linearfigurepointshaveacommonpointofintersec-tion.Thispointinthe0-pplane,say(00,o0),definesthelinepassingthroughthecolinearpoints.Thustheprob-lemofdetectingcolinearpointscanbeconvertedtotheproblemoffindingconcurrentcurves.Adualpropertyofthepoint-to-curvetransforma-tioncanalsobeestablished.Supposewehaveaset(01,oi),.,(Ok,Ok)ofpointsinthe0-oplane,alllyingonthecurveo=XoCOSO+yosinO.Thenrtiseasytoshowthatallthesepointscorrespondtolinesinthex-yplanepassingthroughthepoint(x0,y0).Wecansummarizetheseinterestingpropertiesofthepoint-to-curvetransformationasfollows:Property1.Apointinthepictureplanecorrespondstoasinusoidalcurveintheparameterplane.Property2.Apointintheparameterplanecorre-spondstoastraightlineinthepictureplane.Property3.Pointslyingonthesamestraightlineinthepictureplanecorrespondtocurvesthroughacom-monpointintheparameterplane.Property4.Pointslyingonthesamecurveintheparameterplanecorrespondtolinesthroughthesamepointinthepictureplane.InSection3weapplytheseresultstotheproblemofdetectingcolinearpointsinthepictureplaneandshowhowsignificantcomputationaleconomiescanberealizedincertainsituations.3.ApplicationsandAlternativeInterpretationsSupposewemapallofthepointsinthepictureplaneintotheircorrespondingcurvesintheparameterplane.Ingeneral,thesencurveswillintersectinn(n-1)/2pointscorrespondingtothelinesbetweenallpairsofFig.1.Thenormalparametersforaline.Fig.2.Projectionofcolinearpointsontoaline.X(x2.Y212CommunicationsoftheACMJanuary1972Volume15Number1figurepoints.Exactlycolinearsubsetsoffigurepointscanbefound,atleastinprinciple,byfindingcoincidentpointsofintersectionintheparameterplane.Unfor-tunately,thisapproachisessentiallyexhaustive,andthecomputationrequiredgrowsquadraticallywiththenum-berofpicturepoints.Whenitisnotnecessarytodeterminethelinesex-actly,thecomputationalburdencanbereducedcon-siderably.FollowingHoughsbasicproposal,wespecifytheacceptableerrorin0andpandquantizetheO-pplaneintoaquadruledgrid.Thisquantizationcanbeconfinedtotheregion0_07r,-R_p_R,whereRisthesizeoftheretina,sincepointsoutsidethisrectanglecorrespondtolinesinthepictureplanethatdonotcrosstheretina.Thequantizedregionistreatedasatwo-dimensionalarrayofaccumulators.Foreachpoint(x,y)inthepictureplane,thecor-respondingcurvegivenby(l)isenteredinthearraybyincrementingthecountineachcellalongthecurve.Thus,agivencellinthetwo-dimensionalaccumulatoreventuallyrecordsthetotalnumberofcurvespassingthroughit.Afterallfigurepointshavebeentreated,thearrayisinspectedtofindcellshavinghighcounts.Ifthecountinagivencell(0i,pi)isk,thenpreciselykfigurepointslie(towithinquantizationerror)alongthelinewhosenormalparametersare(0;,pj).Analternativeinterpretationofthepoint-curvetrans-formationcanbeobtainedbyrecognizingthatthepcomputedby(1)locatestheprojectionofthepoint(x,y)ontoalinethroughtheoriginwithslopeangle0.Thus,ifanumberoffigurepointslieclosetosomeline1,theirprojectionsontothelinenormaltoIarenearlycoincident(seeFigure2).AgivencolumnintheO-paccumulatorarrayisjustahistogramfortheseprojections,soahighcountinagivencellclearlycorrespondstoanearlycolinearsubsetoffigurepoints.AvariationofthisapproachwasusedbyGriffith3tofindlonglinesinapicture.Letusinvestigatehowthecomputationrequiredbytheaccumulatorimplementationvarieswiththenumberoffigurepoints.Tobemorespecificaboutthequantiza-tion,supposethatwerestrictourattentiontodvaluesof0uniformlyspacedintheinterval0,7r).Supposefurtherthatthepaxisintheinterval-R,Risquantizedintocells.Foreachfigurepoint(x,y),weuse(1)tocomputetheddifferentvaluesofpcorrespondingtothedlpossiblevaluesoftheindependentvariable0.Sincetherearenfigurepoints,weneedtocarryoutthiscomputationndtimes.Whenthesecomputationsarecomplete,thedld.2cellsofthetwo-dimensionalaccumulatorareinspectedtofindhighcounts.Thusthecomputationrequiredgrowslinearlywiththenumberoffigurepoints.Clearly,whennislargecomparedtodl,thisapproachispreferabletoanexhaustivepro-cedurethatrequiresconsideringthelinesbetweenalln(n-1)/2pairsoffigurepoints.Anotheralternativeinterpretationexposesthesourceofthisefficiency.ConsideragainProperty4inSection132:PointslyingonthesamecurveintheO-pplanecor-respondtolinesthroughthesamepointinthepictureplane.Whenthecurvecorrespondingtofigurepoint(x,yi)isaddedtotheaccumulator,wearereallycomputingandrecordingtheparametersofthed:linesinthepictureplanepassingthrough(x,y),andbecause0isquantized,theseareallthelinesintheplanepassingthrough(xl,yi).Shouldagivenparam-eterpaireverrecurasaresultofcomputingthedllinesthroughsomeotherfigurepoint,therecurrencewillbereflectedinanincreasedcountintheappro-priateaccumulatorcell.Roughlyspeaking,then,foreachfigurepointthequantizedtransformmethodcon-sidersonlythesetofalldlinesthroughthatpoint,whereasmoreexhaustivemethodsconsiderall(n-1)linesbetweenthegivenpointandallotherfigurepoints.4.ExampleThefollowingexampleillustratessomeofthefeaturesofthetransformapproach.Figure3(a)showsatelevi-sionmonitorviewofabox,andFigure3(b)showsadigitizedversionofthatview.Asimpledifferencingoperationlocatessignificantintensitychangesandpro-ducesthebinarypictureshowninFigure3(c).This120X120picturecontainsmanynearlycolinearfigurepointsthatcanbefitwellbyafewstraightlines.Sampling0atd=9twenty-degreeincrementsin0and,quantizingpintod2=86two-elementcells,weobtainthetwo-dimensionalaccumulatorarrayshowninTableI.Ifthearrayentryat(00,p0)isk0,thenk0figurepointslieonparallellinesforwhich0=00,andpliesbetweenp0andp0d-2.Whenmanypointsarenearlycolinear,theentryforthelinethatfitsthembestislarge.ThelargestentryinTableIoccursat(0,-5)andcorrespondstothemiddleverticaledgeofthebox.Theninecircledentriescorrespondtolocallymaximumvaluesthatexceedthearbitrarythresholdof35.ThecorrespondingninegroupsofnearlycolinearfigurepointsareshowninFigure3(d).Inthisexample,ithappensthateverygroupcorrespondstosomephys-icallymeaningfullineinthepicture.However,twosignificantlinesonthetopoftheboxwerenotfound-one,becauseitcontainedveryfewpoints,andtheother,becauseitfellbetweenthelinesat0=80and0=100.The20angularquantizationintervalwaschosentokeeptheaccumulatorarraysmall.Clearly,wewerefortunatetohavefoundasmanylinesaswedid,andasmallerquantizationintervalwouldhavetobeusedinpractice.Afewremarksconcerningsomelimitationsofthetransformapproachareinorder.First,theresultsaresensitivetothequantizationofboth0andp.Finerquantizationgivesbetterresolution,butincreasesthecomputationtimeandexposestheproblemofclusteringentriescorrespondingtonearlycolinearpoints.Second,CommunicationsJanuary1972ofVolume15theACMNumber1thetechniquefindscolinearpointswithoutregardtocontiguity.Thusthepositionofabest-fitlinecanbedistortedbythepresenceofunrelatedfigurepointsinanotherpartofthepicture.Arelatedproblemisthatofmeaninglessgroupsofcolinearpointsbeingdetected.Inourexample,afalselinewouldbedetectedifthethresholdwerereducedfrom35to24,thevalueneededtodetectthetopleft-handedgeofthebox.Thetransformapproachdoessuccessfullyfindgroupsofcolinearornearlycolinearfigurepoints.Ifthemini-mumsizeofasignificantgroupisknown,allsuchgroupscanbedetected.Ifadditionalpropertiessuchascon-tiguityareknown,theycanbeusedtorejectmeaning-lessresults.Ingeneral,thetransformapproachshouldbeviewedprimarilyasacomputationallyefficientwayofaccomplishingaconceptuallysimplestepinsceneanalysis.Fig.3Anillustrativeexample.lI(a)Monitor5.ExtensionsandConclusionsThetransformmethodcanbegeneralizedandspe-cializedinseveralways.Wenoteimmediatelythatanyparametrizationofthefamilyofstraightlinescanbeused.Aswehavementioned,Houghusedtheslope-interceptparameterization.However,thisparameteriza-tionhasthedisadvantageofbeingsensitivetothechoiceofcoordinateaxesinthepictureplane.Ifseveralfigurepointslieonanearlyverticalline,forexample,boththeslopeandtheinterceptmaybearbitrarilylarge.Thustheentiretwo-dimensionalparameterplanemustbeconsidered.AsRosenfeld1haspointedout,onecoulddotheentireproblemtwice,interchangingthex-andy-axes,butthiswouldintroduceadditionalcomplica-tions.Thenormalparametrizationavoidsthesedis-advantages,fundamentallyforthesamereasonsthatmakeitusefulinintegralgeometry:Itallowsustoplaceaninvariantmeasureonthesetofallstraightlines.Animportantspecialuseofthetransformmethodistodetecttheoccurrenceoffigurepointslyingonastraightlineandpossessingsomespecifiedproperty.Forexample,supposewewanttofindwhetherasig-nificantnumberoffigurepointslieonalinethroughthepoint(x0,y0)inthepictureplane.AswehaveseenfromProperty4,thenormalcoordinatesofanysuchlinemustlieon(or,inpracticeatleastnear)thecurven=x0cos0+y0sin0.Hence,thetransformprocesscanbecarriedoutintheusualway,butattentioncanberestrictedtotheregionofthe0-pplanenearthiscurve.Ifwefindacellwithcountknearthiscurve,thenweareassuredthatkfigurepointslieonalinepassing(nearly)throughthepoint(x0,y0).Similarly,supposeweareinterestedonlyinlineshavingagivendirection,say00.Again,wecarryouttheprocessintheusualway,butrestrictourattentiontoasubsetofthe0-pplaneinthevicinityof0=00.Itisclearthatthegeneraltransformapproachcanbe(b)Digitized(c)Gradientii,(d)Lines14CommunicationsoftheACMJanuary1972Volume15Number1TableI.AccumulatorArrayforFigure3(c)0-0:20:40:60:80zoo:120:140:160:8528312814479265772842756627343371211423691412435673214234651111246352246113959411191812574331012310155595454511125366410119145149420211108495621031113847844421310104547143116843418215I1210841917211525187839820211322111173712172217910910(314171738879635333716222110599313511212323811910291318182320141399277161230202079625718123219278782381211201751167217171223811151110199141216771467179121216691612715813131171016141013109151171016136!2111314(10161313119101016148914212271082212Q671221511121511236111414313151581871116151101417117891012oo0=20=40:60:80:100=120140:160-85-83-81-7931-77i3-75-73-712-692-67-6512-6312-615-5972l1-576212-550I06ll4-5316131218416t15II151665()1523I1549321811-471016i12214162195-45717111116184216-438121410131712176-4l671411141471912-3971098128112023-3777148179121824-3589178107102323-33612158129112226-3159199811161815-2991012989181815-2771210869181919-25510887722914-236I19961119129-21715971010161011-191381691117910-177179157I1161413-15615101781310149-131015915917111312-11101310781791115-97148782381215-791512782171312(131597141012155-3261414681291118-1101318988111215extendedtocurvesotherthanstraightlines.Forex-ample,supposewewantamethodtodetectcircularconfigurationsoffigurepoints.Wecanchooseapara-metricrepresentationforthefamilyofallcircles(withinaretina)andtransformeac