HOUGH TRANS.ppt

HOUGHTRANSFORM PresentationbySumitTandonDepartmentofElectricalEngineeringUniversityofTexasatArlingtonCourse EE6358ComputerVision EE6358 ComputerVision 2 Contents IntroductionAdvantagesofHoughtransformHoughTransformforStraightLineDetectionHoughTransformforCircleDetectionRecapandlistofparametersGeneralizedHoughTransformImprovisationofHoughTransformExamplesReferences EE6358 ComputerVision 3 1 Introduction PerformedafterEdgeDetectionItisatechniquetoisolatethecurvesofagivenshape shapesinagivenimageClassicalHoughTransformcanlocateregularcurveslikestraightlines circles parabolas ellipses etc RequiresthatthecurvebespecifiedinsomeparametricformGeneralizedHoughTransformcanbeusedwhereasimpleanalyticdescriptionoffeatureisnotpossible EE6358 ComputerVision 4 2 AdvantagesofHoughTransform TheHoughTransformistolerantofgapsintheedgesItisrelativelyunaffectedbynoiseItisalsounaffectedbyocclusionintheimage EE6358 ComputerVision 5 3 1HoughTransformforStraightLineDetection Astraightlinecanberepresentedasy mx cThisrepresentationfailsincaseofverticallinesAmoreusefulrepresentationinthiscaseisDemo EE6358 ComputerVision 6 3 2HoughTransformforStraightLines AdvantagesofParameterizationValuesof r and q becomeboundedHowtofindintersectionoftheparametriccurvesUseofaccumulatorarrays conceptof Voting ToreducethecomputationalloaduseGradientinformation EE6358 ComputerVision 7 3 3ComputationalLoad Imagesize 512X512MaximumvalueofWitharesolutionof1o maximumvalueofAccumulatorsize Useofdirectionofgradientreducesthecomputationalloadby1 360 EE6358 ComputerVision 8 3 4HoughTransformforStraightLines Algorithm QuantizetheHoughTransformspace identifythemaximumandminimumvaluesofrandqGenerateanaccumulatorarrayA r q setallvaluestozeroForalledgepoints xi yi intheimageUsegradientdirectionforqComputerfromtheequationIncrementA r q byoneForallcellsinA r q SearchforthemaximumvalueofA r q CalculatetheequationofthelineToreducetheeffectofnoisemorethanoneelement elementsinaneighborhood intheaccumulatorarrayareincreased EE6358 ComputerVision 9 3 5LineDetectionbyHoughTransform EE6358 ComputerVision 10 4 1HoughTransformforDetectionofCircles TheparametricequationofthecirclecanbewrittenasTheequationhasthreeparameters a b rThecurveobtainedintheHoughTransformspaceforeachedgepointwillbearightcircularconePointofintersectionoftheconesgivestheparametersa b r EE6358 ComputerVision 11 4 2HoughTransformforCircles GradientateachedgepointisknownWeknowthelineonwhichthecenterwilllieIftheradiusisalsoknownthencenterofthecirclecanbelocated EE6358 ComputerVision 12 4 3DetectionofcirclebyHoughTransform example OriginalImageCirclesdetectedbyCannyEdgeDetector EE6358 ComputerVision 13 4 4DetectionofcirclebyHoughTransform contd HoughTransformoftheedgedetectedimageDetectedCircles EE6358 ComputerVision 14 5 1Recap IndetectinglinesTheparametersrandqwerefoundoutrelativetotheorigin 0 0 IndetectingcirclesTheradiusandcenterwerefoundoutInboththecaseswehaveknowledgeoftheshapeWeaimtofindoutitslocationandorientationintheimageTheideacanbeextendedtoshapeslikeellipses parabolas etc EE6358 ComputerVision 15 5 2Parametersforanalyticcurves EE6358 ComputerVision 16 6 1GeneralizedHoughTransform TheGeneralizedHoughtransformcanbeusedtodetectarbitraryshapesCompletespecificationoftheexactshapeofthetargetobjectisrequiredintheformoftheR TableInformationthatcanbeextractedareLocationSizeOrientationNumberofoccurrencesofthatparticularshape EE6358 ComputerVision 17 6 2CreatingtheR table AlgorithmChooseareferencepointDrawavectorfromthereferencepointtoanedgepointontheboundaryStoretheinformationofthevectoragainstthegradientangleintheR TableTheremaybemorethanoneentryintheR Tablecorrespondingtoagradientvalue EE6358 ComputerVision 18 6 3GeneralizedHoughTransform Algorithm FormanAccumulatorarraytoholdthecandidatelocationsofthereferencepointForeachpointontheedgeComputethegradientdirectionanddeterminetherowoftheR TableitcorrespondstoForeachentryontherowcalculatethecandidatelocationofthereferencepointIncreasetheAccumulatorvalueforthatpointThereferencepointlocationisgivenbythehighestvalueintheaccumulatorarray EE6358 ComputerVision 19 6 4GeneralizedHoughTransform SizeandOrientation ThesizeandorientationoftheshapecanbefoundoutbysimplymanipulatingtheR TableForscalingbyfactorSmultiplytheR TablevectorsbySForrotationbyangleq rotatethevectorsintheR Tablebyangleq EE6358 ComputerVision 20 6 5GeneralizedHoughTransform Advantagesanddisadvantages AdvantagesAmethodforobjectrecognitionRobusttopartialdeformationinshapeToleranttonoiseCandetectmultipleoccurrencesofashapeinthesamepassDisadvantagesLotofmemoryandcomputationisrequired EE6358 ComputerVision 21 7 1ImprovisationoftheHoughtransformfordetectingstraightlinesegments HoughTransformlackstheabilitytodetecttheendpointsoflines localizedinformationislostduringHTPeakpointsintheaccumulatorcanbedifficulttolocateinpresenceofnoisyorparalleledgesEfficiencyofthealgorithmdecreasesifimagebecomestoolargeNewapproachisproposedtoreducetheseproblems EE6358 ComputerVision 22 7 2Spatialdecomposition ThistechniquepreservesthelocalizedinformationDividetheimagerecursivelyintoquad trees eachquad treerepresentingapartoftheimagei e asub imageTheleafnodeswillbevotedforfeaturepointswhichareinthesub imagerepresentedbytheleafnode EE6358 ComputerVision 23 7 2SpatialDecompositionofHoughTransform ParameterspaceisdefinedfromaglobaloriginratherthanalocaloneEachnodecontainsinformationaboutthesub nodesaswellasthenumberoffeaturepointsinthesub imagerepresentedbythenodePruningofsub treesisdoneifthenumberofthefeaturepointsfallsbelowathresholdAnaccumulatorisassignedforeachleafnode EE6358 ComputerVision 24 7 3Somerelationsinvolvedinspatialdecomposition ConsiderthefollowingQ anynon leafnodeF featurepointsinthesub imagerepresentedbythisnodeA parameterspaceofthesub imageThefollowingrelationsholdtrue EE6358 ComputerVision 25 7