第6讲 特征提取-点、直线 深圳大学 机器视觉及应用 课件

机器视觉及应用李东lidong@Whyextractfeatures?Motivation:panoramastitchingWehavetwoimages–howdowecombinethem?Localfeatures:maincomponentsDetection:IdentifytheinterestpointsDescription:Extractvectorfeaturedescriptorsurroundingeachinterestpoint.Matching:DeterminecorrespondencebetweendescriptorsintwoviewsKristenGraumanCharacteristicsofgoodfeaturesRepeatabilityThesamefeaturecanbefoundinseveralimagesdespitegeometricandphotometrictransformationsSaliencyEachfeatureisdistinctiveCompactnessandefficiencyManyfewerfeaturesthanimagepixelsLocalityAfeatureoccupiesarelativelysmallareaoftheimage;robusttoclutterandocclusionRepeatabilityWewanttodetect(atleastsomeof)thesamepointsinbothimages.Yetwehavetobeabletorunthedetectionprocedureindependentlyperimage.Nochancetofindtruematches!KristenGraumanDistinctivenessWewanttobeabletoreliablydeterminewhichpointgoeswithwhich.Mustprovidesomeinvariancetogeometricandphotometricdifferencesbetweenthetwoviews.?KristenGraumanApplicationsFeaturepointsareusedfor:Imagealignment3DreconstructionMotiontrackingRobotnavigationObjectrecognitionExistingDetectorsAvailableHessian&Harris [Beaudet‘78],[Harris‘88]Laplacian,DoG [Lindeberg‘98],[Lowe1999]Harris-/Hessian-Laplace

[Mikolajczyk&Schmid‘01]Harris-/Hessian-Affine [Mikolajczyk&Schmid‘04]EBRandIBR [Tuytelaars&VanGool‘04]

MSER

[Matas‘02]SalientRegions [Kadir&Brady‘01]Others…Whatpointswouldyouchoose?KristenGrauman“edge”:

nochangealongtheedgedirection“corner”:

significantchangeinalldirections“flat”region:

nochangeinalldirectionsCornerDetection:BasicIdeaWeshouldeasilyrecognizethepointbylookingthroughasmallwindowShiftingawindowinany

directionshouldgivealargechangeinintensitySource:A.EfrosCornerDetection:MathematicsChangeinappearanceofwindoww(x,y)fortheshift[u,v]:I(x,y)E(u,v)E(3,2)w(x,y)CornerDetection:MathematicsChangeinappearanceofwindoww(x,y)fortheshift[u,v]:I(x,y)E(u,v)E(0,0)w(x,y)CornerDetection:MathematicsChangeinappearanceofwindoww(x,y)fortheshift[u,v]:IntensityShiftedintensityWindowfunctionorWindowfunctionw(x,y)=Gaussian1inwindow,0outsideCornerDetection:MathematicsWewanttofindouthowthisfunctionbehavesforsmallshiftsE(u,v)Changeinappearanceofwindoww(x,y)fortheshift[u,v]:CornerDetection:MathematicsCornerDetection:MathematicsThequadraticapproximationsimplifiestowhereMisasecondmomentmatrix

computedfromimagederivatives:M2x2matrixofimagederivatives(averagedinneighborhoodofapoint).Notation:CornersasdistinctiveinterestpointsInterpretingthesecondmomentmatrixThesurfaceE(u,v)islocallyapproximatedbyaquadraticform.Let’strytounderstanditsshape.Ifeitherλiscloseto0,thenthisisnotacorner,solookforlocationswherebotharelarge.InterpretingthesecondmomentmatrixFirst,considertheaxis-alignedcase(gradientsareeitherhorizontalorvertical)Considerahorizontal“slice”ofE(u,v):InterpretingthesecondmomentmatrixThisistheequationofanellipse.Considerahorizontal“slice”ofE(u,v):InterpretingthesecondmomentmatrixThisistheequationofanellipse.TheaxislengthsoftheellipsearedeterminedbytheeigenvaluesandtheorientationisdeterminedbyRdirectionoftheslowestchangedirectionofthefastestchange(max)-1/2(min)-1/2DiagonalizationofM:VisualizationofsecondmomentmatricesVisualizationofsecondmomentmatricesInterpretingtheeigenvaluesClassificationofimagepointsusingeigenvaluesofM:12“Corner”

1and2arelarge,

1~2;

Eincreasesinalldirections1and2aresmall;

Eisalmostconstantinalldirections“Edge”

1>>2“Edge”

2>>1“Flat”regionCornerresponsefunctionα:constant(0.04to0.06)“Corner”

R>0“Edge”

R<0“Edge”

R<0“Flat”region|R|smallHarriscornerdetectorComputeMmatrixforeachimagewindowtogettheircornernessscores.Findpointswhosesurroundingwindowgavelargecornerresponse(f>threshold)Takethepointsoflocalmaxima,i.e.,performnon-maximumsuppressionC.HarrisandM.Stephens.“ACombinedCornerandEdgeDetector.”Proceedingsofthe4thAlveyVisionConference:pages147—151,1988.

HarrisDetector:StepsHarrisDetector:StepsComputecornerresponseRHarrisDetector:StepsFindpointswithlargecornerresponse:R>thresholdHarrisDetector:StepsTakeonlythepointsoflocalmaximaofRHarrisDetector:StepsInvarianceandcovarianceWewantcornerlocationstobeinvarianttophotometrictransformationsandcovarianttogeometrictransformationsInvariance:imageistransformedandcornerlocationsdonotchangeCovariance:ifwehavetwotransformedversionsofthesameimage,featuresshouldbedetectedincorrespondinglocationsAffineintensitychange

Onlyderivativesareused=>Intensityscaling:

Ia

IRx

(imagecoordinate)thresholdRx

(imagecoordinate)PartiallyinvarianttoaffineintensitychangeIa

I+binvariancetointensityshiftII

+

bImagetranslationDerivativesandwindowfunctionareshift-invariantCornerlocationiscovariantw.r.t.translationImagerotationSecondmomentellipserotatesbutitsshape(i.e.eigenvalues)remainsthesameCornerlocationiscovariantw.r.t.rotationScalingAllpointswillbeclassifiedasedgesCornerCornerlocationisnotcovarianttoscaling!FindingstraightlinesOnesolution:trymanypossiblelinesandseehowmanypointseachlinepassesthroughHoughtransformprovidesafastwaytodothisOutlineofHoughTransformCreateagridofparametervaluesEachpointvotesforasetofparameters,incrementingthosevaluesingridFindmaximumorlocalmaximaingridFindinglinesusingHoughtransformUsingm,bparameterizationUsingr,thetaparameterizationUsingorientedgradientsPracticalconsiderationsBinsizeSmoothingFindingmultiplelinesFindinglinesegmentsHoughtransformGeneraloutline:DiscretizeparameterspaceintobinsForeachfeaturepointintheimage,putavoteineverybinintheparameterspacethatcouldhavegeneratedthispointFindbinsthathavethemostvotesP.V.C.Hough,MachineAnalysisofBubbleChamberPictures,Proc.Int.Conf.HighEnergyAcceleratorsandInstrumentation,1959ImagespaceHoughparameterspaceParameterspacerepresentationAlineintheimagecorrespondstoapointinHoughspaceImagespaceHoughparameterspaceParameterspacerepresentationWhatdoesapoint(x0,y0)intheimagespacemaptointheHoughspace?ImagespaceHoughparameterspaceParameterspacerepresentationWhatdoesapoint(x0,y0)intheimagespacemaptointheHoughspace?Answer:thesolutionsofb=–x0m+y0ThisisalineinHoughspaceImagespaceHoughparameterspaceParameterspacerepresentationWhereisthelinethatcontainsboth(x0,y0)and(x1,y1)?ImagespaceHoughparameterspace(x0,y0)(x1,y1)b=–x1m+y1ParameterspacerepresentationWhereisthelinethatcontainsboth(x0,y0)and(x1,y1)?Itistheintersectionofthelinesb=–x0m+y0andb=–x1m+y1

ImagespaceHoughparameterspace(x0,y0)(x1,y1)b=–x1m+y1Problemswiththe(m,b)space:UnboundedparameterdomainVerticallinesrequireinfinitemParameterspacerepresentationProblemswiththe(m,b)space:UnboundedparameterdomainVerticallinesrequireinfinitemAlternative:polarrepresentationParameterspacerepresentationEachpointwilladdasinusoidinthe(,)parameterspace

AlgorithmoutlineInitializeaccumulatorHtoallzerosForeachedgepoint(x,y)intheimage

Forθ=0to180

ρ=xcosθ+ysinθ

H(θ,ρ)=H(θ,ρ)+1

endFindthevalue(s)of(θ,ρ)whereH(θ,ρ)isalocalmaximumThedetectedlineintheimageisgivenby

ρ=xcosθ+ysinθρθfeaturesvotesBasicillustrationSquareCircleOthershapesSeverallinesAmoreco