数字视频特效处理lec06-feature特征分析

FeaturesDigitalVisualEffectsYung-YuChuangwithslidesbyTrevorDarrell

CordeliaSchmid,DavidLowe,DaryaFrolova,DenisSimakov,RobertCollinsandJiwonKimOutlineFeaturesHarriscornerdetectorSIFTExtensionsApplicationsFeaturesFeaturesAlsoknownasinterestingpoints,salientpointsorkeypoints.Pointsthatyoucaneasilypointouttheircorrespondencesinmultipleimagesusingonlylocalinformation.?DesiredpropertiesforfeaturesDistinctive:asinglefeaturecanbecorrectlymatchedwithhighprobability.Invariant:invarianttoscale,rotation,affine,illuminationandnoiseforrobustmatchingacrossasubstantialrangeofaffinedistortion,viewpointchangeandsoon.Thatis,itisrepeatable.ApplicationsObjectorscenerecognitionStructurefrommotionStereoMotiontracking…ComponentsFeaturedetectionlocateswheretheyareFeaturedescriptiondescribeswhattheyareFeaturematchingdecideswhethertwoarethesameoneHarriscornerdetectorMoraveccornerdetector(1980)WeshouldeasilyrecognizethepointbylookingthroughasmallwindowShiftingawindowinany

directionshouldgivealargechangeinintensityMoraveccornerdetectorflatMoraveccornerdetectorflatMoraveccornerdetectorflatedgeMoraveccornerdetectorflatedgecornerisolatedpointMoraveccornerdetectorChangeofintensityfortheshift[u,v]:windowfunctionFourshifts:(u,v)=(1,0),(1,1),(0,1),(-1,1)Lookforlocalmaximainmin{E}intensityshiftedintensityProblemsofMoravecdetectorNoisyresponseduetoabinarywindowfunctionOnlyasetofshiftsatevery45degreeisconsideredOnlyminimumofEistakenintoaccountHarriscornerdetector(1988)solvestheseproblems.HarriscornerdetectorNoisyresponseduetoabinarywindowfunctionUseaGaussianfunction

HarriscornerdetectorOnlyasetofshiftsatevery45degreeisconsideredConsiderallsmallshiftsbyTaylor’sexpansionHarriscornerdetectorOnlyasetofshiftsatevery45degreeisconsideredConsiderallsmallshiftsbyTaylor’sexpansionHarriscornerdetectorEquivalently,forsmallshifts[u,v]wehaveabilinearapproximation:,whereMisa22matrixcomputedfromimagederivatives:Harriscornerdetector(matrixform)HarriscornerdetectorOnlyminimumofEistakenintoaccountAnewcornermeasurementbyinvestigatingtheshapeoftheerrorfunctionrepresentsaquadraticfunction;Thus,wecananalyzeE’sshapebylookingatthepropertyofMHarriscornerdetectorHigh-levelidea:whatshapeoftheerrorfunctionwillwepreferforfeatures?flatedgecornerQuadraticformsQuadraticform(homogeneouspolynomialofdegreetwo)ofnvariablesxiExamples=SymmetricmatricesQuadraticformscanberepresentedbyarealsymmetricmatrixAwhereEigenvaluesofsymmetricmatricesBradOsgoodEigenvectorsofsymmetricmatricesEigenvectorsofsymmetricmatricesHarriscornerdetectorIntensitychangeinshiftingwindow:eigenvalueanalysis

1,

2–eigenvaluesofMdirectionoftheslowestchangedirectionofthefastestchange(

max)-1/2(

min)-1/2EllipseE(u,v)=constVisualizequadraticfunctionsVisualizequadraticfunctionsVisualizequadraticfunctionsVisualizequadraticfunctionsHarriscornerdetector

1

2Corner

1and

2arelarge,

1~

2;

Eincreasesinalldirections

1and

2aresmall;

Eisalmostconstantinalldirectionsedge

1>>

2edge

2>>

1flatClassificationofimagepointsusingeigenvaluesofM:HarriscornerdetectorMeasureofcornerresponse:(k–empiricalconstant,k=0.04-0.06)Onlyforreference,youdonotneedthemtocomputeRHarriscornerdetectorAnotherviewAnotherviewAnotherviewSummaryofHarrisdetectorComputexandyderivativesofimageComputeproductsofderivativesateverypixelComputethesumsoftheproductsofderivativesateachpixelSummaryofHarrisdetectorDefinethematrixateachpixelComputetheresponseofthedetectorateachpixelThresholdonvalueofR;computenonmaxsuppression.Harriscornerdetector(input)CornerresponseRThresholdonRLocalmaximumofRHarriscornerdetectorHarrisdetector:summaryAverageintensitychangeindirection[u,v]canbeexpressedasabilinearform:

DescribeapointintermsofeigenvaluesofM:

measureofcornerresponse

Agood(corner)pointshouldhavealargeintensitychangeinalldirections,i.e.RshouldbelargepositiveNowweknowwherefeaturesareBut,howtomatchthem?Whatisthedescriptorforafeature?Thesimplestsolutionistheintensitiesofitsspatialneighbors.Thismightnotberobusttobrightnesschangeorsmallshift/rotation.()123456789123456789Harrisdetector:somepropertiesPartialinvariancetoaffineintensitychange

Onlyderivativesareused=>invariancetointensityshiftI

I

+

b

Intensityscale:I

a

IRx

(imagecoordinate)thresholdRx

(imagecoordinate)HarrisDetector:SomePropertiesRotationinvarianceEllipserotatesbutitsshape(i.e.eigenvalues)remainsthesameCornerresponseRisinvarianttoimagerotationHarrisDetectorisrotationinvariantRepeatabilityrate:#correspondences

#possiblecorrespondencesHarrisDetector:SomePropertiesBut:notinvarianttoimagescale!AllpointswillbeclassifiedasedgesCorner!Harrisdetector:somepropertiesQualityofHarrisdetectorfordifferentscalechangesRepeatabilityrate:#correspondences

#possiblecorrespondencesScaleinvariantdetectionConsiderregions(e.g.circles)ofdifferentsizesaroundapointRegionsofcorrespondingsizeswilllookthesameinbothimagesScaleinvariantdetectionTheproblem:howdowechoosecorrespondingcirclesindependentlyineachimage?ApertureproblemSIFT

(ScaleInvariantFeatureTransform)SIFTSIFTisancarefullydesignedprocedurewithempiricallydeterminedparametersfortheinvariantanddistinctivefeatures.SIFTstages:Scale-spaceextremadetectionKeypointlocalizationOrientationassignmentKeypointdescriptor()localdescriptordetectordescriptorA500x500imagegivesabout2000features1.Detectionofscale-spaceextremaForscaleinvariance,searchforstablefeaturesacrossallpossiblescalesusingacontinuousfunctionofscale,scalespace.SIFTusesDoGfilterforscalespacebecauseitisefficientandasstableasscale-normalizedLaplacianofGaussian.DoGfilteringConvolutionwithavariable-scaleGaussianDifference-of-Gaussian(DoG)filterConvolutionwiththeDoGfilterScalespace

doublesforthenextoctaveK=2(1/s)Dividingintooctaveisforefficiencyonly.Detectionofscale-spaceextremaKeypointlocalizationXisselectedifitislargerorsmallerthanall26neighborsDecidescalesamplingfrequencyItisimpossibletosamplethewholespace,tradeoffefficiencywithcompleteness.Decidethebestsamplingfrequencybyexperimentingon32realimagesubjecttosynthetictransformations.(rotation,scaling,affinestretch,brightnessandcontrastchange,addingnoise…)DecidescalesamplingfrequencyDecidescalesamplingfrequencys=3isthebest,forlargers,toomanyunstablefeaturesfordetector,repeatabilityfordescriptor,distinctivenessPre-smoothing=1.6,plusadoubleexpansionScaleinvariance2.AccuratekeypointlocalizationRejectpointswithlowcontrast(flat)andpoorlylocalizedalonganedge(edge)Fita3Dquadraticfunctionforsub-pixelmaxima1650-1+12.AccuratekeypointlocalizationRejectpointswithlowcontrast(flat)andpoorlylocalizedalonganedge(edge)Fita3Dquadraticfunctionforsub-pixelmaxima1650-1+12.AccuratekeypointlocalizationTaylorseriesofseveralvariablesTwovariablesAccuratekeypointlocalizationTaylorexpansioninamatrixform,xisavector,fmapsxtoascalarHessianmatrix(oftensymmetric)gradient2Dillustration2Dexample-17-1-17777-9-9DerivationofmatrixformDerivationofmatrixformDerivationofmatrixformDerivationofmatrixformDerivationofmatrixformAccuratekeypointlocalizationxisa3-vectorChangesamplepointifoffsetislargerthan0.5Throwoutlowcontrast(<0.03)AccuratekeypointlocalizationThrowoutlowcontrastEliminatingedgeresponsesr=10LetKeepthepointswithHessianmatrixatkeypointlocationMaximainDRemovelowcontrastandedgesKeypointdetector233x89832extrema729aftercon-trastfiltering536aftercur-vaturefiltering3.OrientationassignmentByassigningaconsistentorientation,thekeypointdescriptorcanbeorientationinvariant.Forakeypoint,ListheGaussian-smoothedimagewiththeclosestscale,orientationhistogram(36bins)(Lx,Ly)mθOrientationassignmentOrientationassignmentOrientationassignmentOrientationassignmentσ=1.5*scaleofthekeypointOrientationassignmentOrientationassignmentOrientationassignmentaccuratepeakpositionisdeterminedbyfittingOrientationassignment36-binorientationhistogramover360°,weightedbymand1.5*scalefalloffPeakistheorientationLocalpeakwithin80%createsmultipleorientationsAbout15%hasmultipleorientationsandtheycontributealottostabilitySIFTdescriptor4.LocalimagedescriptorThresholdedimagegradientsaresampledover16x16arrayoflocationsinscalespaceCreatearrayoforientationhistograms(w.r.t.keyorientation)8orientationsx4x4histogramarray=128dimensionsNormalized,clipvalueslargerthan0.2,renormalizeσ=0.5*widthWhy4x4x8?SensitivitytoaffinechangeFeaturematchingforafeaturex,hefoundtheclosestfeaturex1

andthesecondclosestfeaturex2.Ifthedistanceratioofd(x,x1)andd(x,x1)issmallerthan0.8,thenitisacceptedasamatch.SIFTflowMaximainDRemovelowcontrastRemoveedgesSIFTdescriptorEstimatedrotationComputedaffinetransformationfromrotatedimagetooriginalimage:0.7060-0.7052128.42300.70570.7100-128.9491001.0000Actualtransformationfromrotatedimagetooriginalimage:0.7071-0.7071128.69340.70710.7071-128.6934001.0000SIFTextensionsPCAPCA-SIFTOnlychangestep4Pre-computeaneigen-spaceforlocalgradientpatchesofsize41x412x39x39=3042elementsOnlykeep20componentsAmorecompactdescriptorGLOH(Gradientlocation-orientationhistogram)17locationbins16orientationbinsAnalyzethe17x16=272-deigen-space,keep128componentsSIFTisstillconsideredthebest.SIFTMulti-ScaleOrientedPatchesSimplerthanSIFT.Designedforimagematching.[Brown,Szeliski,Winder,CVPR’2005]FeaturedetectorMulti-scaleHarriscornersOrientationfromblurredgradientGeometricallyinvarianttorotationFeaturedescriptorBias/gainnormalizedsamplingoflocalpatch(8x8)PhotometricallyinvarianttoaffinechangesinintensityMulti-ScaleHarriscornerdetectorImagestitchingismostlyconcernedwithmatchingimagesthathavethesamescale,sosub-octavepyramidmightnotbenecessary.Multi-ScaleHarriscornerdetectorsmootherversionofgradients

Cornerdetectionfunction:Picklocalmaximaof3x3andlargerthan10KeypointdetectionfunctionExperimentsshowroughlythesameperformance.Non-maximalsuppressionRestrictthemaximalnumberofinterestpoints,butalsowantthemspatiallywelldistributedOnlyretainmaximumsinaneighborhoodofradiusr.Sortthembystrength,decreasingrfrominfinityuntilthenumberofkeypoints(500)issatisfied.Non-maximalsuppressionSub-pixelrefinementOrientationassignmentOrientation=blurredgradientDescriptorVectorRotationInvariantFrameScale-spaceposition(x,y,s)+orientation(

)MSOPdescriptorvector8x8orientedpatchsampledat5xscale.SeeTRfordetails.Sampledfromwithspacing=58pixels40pixelsMSOPdescriptorvector8x8orientedpatchsampledat5xscale.SeeTRfordetails.Bias/gainnormalisation:I’=(I–

)/

Wavelettransform8pixels40pixelsDetectionsatmultiplescalesSummaryMulti-scaleHarriscornerdetectorSub-pixelrefinementOrientationassignmentbygradientsBlurredintensitypatchasdescriptorFeaturematchingExhaustivesearchforeachfeatureinoneimage,lookatalltheotherfeaturesintheotherimage(s)Hashingcomputeashortdescriptorfromeachfeaturevector,orhashlongerdescriptors(randomly)Nearestneighbortechniquesk-treesandtheirvariants(BestBinFirst)Wavelet-basedhashingComputeashort(3-vector)descriptorfroman8x8patchusingaHaar“wavelet”Quantizeeachvalueinto10(overlapping)bins(103totalentries)[Brown,Szeliski,Winder,CVPR’2005]Nearestneighbortechniquesk-Dtree

andBestBin

First

(BBF)IndexingWithoutInvariantsin3DObjectRecognition,BeisandLowe,PAMI’99ApplicationsReco