MotionestimationDigitalVisualEffectsYung-YuChuangwithslidesbyMichaelBlackandP.AnandanMotionestimationParametricmotion(imagealignment)TrackingOpticalflowParametricmotiondirectmethodforimagestitchingTrackingOpticalflowThreeassumptionsBrightnessconsistencySpatialcoherenceTemporalpersistenceBrightnessconsistencyImagemeasurement(e.g.brightness)inasmallregionremainthesamealthoughtheirlocationmaychange.SpatialcoherenceNeighboringpointsinthescenetypicallybelongtothesamesurfaceandhencetypicallyhavesimilarmotions.Sincetheyalsoprojecttonearbypixelsintheimage,weexpectspatialcoherenceinimageflow.TemporalpersistenceTheimagemotionofasurfacepatchchangesgraduallyovertime.ImageregistrationGoal:registeratemplateimageT(x)andaninputimageI(x),wherex=(x,y)T.(warpIsothatitmatchesT)Imagealignment:I(x)andT(x)aretwoimagesTracking:T(x)isasmallpatcharoundapointpintheimageatt.I(x)istheimageattimet+1.Opticalflow:T(x)andI(x)arepatchesofimagesattandt+1.TfixedIwarpSimpleapproach(fortranslation)MinimizebrightnessdifferenceSimpleSSDalgorithmForeachoffset(u,v)computeE(u,v);Choose(u,v)whichminimizesE(u,v);Problems:NotefficientNosub-pixelaccuracyLucas-KanadealgorithmNewton’smethodRootfindingforf(x)=0MarchxandtestsignsDetermineΔx(small→slow;large→miss)Newton’smethodRootfindingforf(x)=0Newton’smethodRootfindingforf(x)=0Taylor’sexpansion:Newton’smethodRootfindingforf(x)=0x0x1x2Newton’smethodpickupx=x0iteratecompute

updatexbyx+ΔxuntilconvergeFindingrootisusefulforoptimizationbecauseMinimizeg(x)→findrootforf(x)=g’(x)=0Lucas-KanadealgorithmLucas-KanadealgorithmLucas-KanadealgorithmiterateshiftI(x,y)with(u,v)computegradientimageIx,IycomputeerrorimageT(x,y)-I(x,y)computeHessianmatrixsolvethelinearsystem(u,v)=(u,v)+(?u,?v)untilconvergeParametricmodeltranslationaffineOurgoalistofindptominimizeE(p)forallxinT’sdomainParametricmodelminimizewithrespecttominimizeParametricmodelimagegradientJacobianofthewarpwarpedimagetargetimageJacobianmatrixTheJacobianmatrixisthematrixofallfirst-orderpartialderivativesofavector-valuedfunction.JacobianmatrixParametricmodelimagegradientJacobianofthewarpwarpedimagetargetimageJacobianofthewarpForexample,foraffinedxxdyxdxydyydxdyParametricmodel(Approximated)HessianLucas-KanadealgorithmiteratewarpIwithW(x;p)computeerrorimageT(x,y)-I(W(x,p))computegradientimagewithW(x,p)evaluateJacobianat(x;p)computecomputeHessiancomputesolveupdatepbyp+untilconvergeCoarse-to-finestrategyJJwIwarprefine+JJwIwarprefine+JpyramidconstructionJJwIwarprefine+IpyramidconstructionApplicationofimagealignmentDirectvsfeature-basedDirectmethodsuseallinformationandcanbeveryaccurate,buttheydependonthefragile“brightnessconstancy”assumption.Iterativeapproachesrequireinitialization.Notrobusttoilluminationchangeandnoiseimages.Inearlydays,directmethodisbetter.Featurebasedmethodsarenowmorerobustandpotentiallyfaster.Evenbetter,itcanrecognizepanoramawithoutinitialization.TrackingTrackingI(x,y,t)I(x+u,y+v,t+1)(u,v)TrackingopticalflowconstraintequationbrightnessconstancyOpticalflowconstraintequationMultipleconstraintsArea-basedmethodAssumespatialsmoothnessArea-basedmethodAssumespatialsmoothnessArea-basedmethodmustbeinvertibleArea-basedmethodTheeigenvaluestellusaboutthelocalimagestructure.Theyalsotellushowwellwecanestimatetheflowinbothdirections.LinktoHarriscornerdetector.TexturedareaEdgeHomogenousareaKLTtrackingSelectfeaturesbyMonitorfeaturesbymeasuringdissimilarityApertureproblemApertureproblemApertureproblemDemoforapertureproblem/Distortions/Breathing_Square.htm/Ambiguous/Barberpole_Illusion.htmApertureproblemLargerwindowreducesambiguity,buteasilyviolatesspatialsmoothnessassumptionKLTtracking/~stb/klt/KLTtracking/~stb/klt/SIFTtracking(matchingactually)

Frame0Frame10SIFTtracking

Frame0Frame100SIFTtracking

Frame0Frame200KLTvsSIFTtrackingKLThaslargeraccumulatingerror;partlybecauseourKLTimplementationdoesn’thaveaffinetransformation?SIFTissurprisinglyrobustCombinationofSIFTandKLT(example)

/projects/buzzard/smalls/Rotoscoping(MaxFleischer1914)1937TrackingforrotoscopingTrackingforrotoscopingWakinglife(2001)AScannerDarkly(2006)Rotoshop,aproprietarysoftware.Eachminuteofanimationrequired500hoursofwork.OpticalflowSingle-motionassumptionViolatedbyMotiondiscontinuityShadowsTransparencySpecularreflection…MultiplemotionMultiplemotionSimpleproblem:fitalineLeast-squarefitLeast-squarefitRobuststatisticsRecoverthebestfitforthemajorityofthedataDetectandrejectoutliersApproachRobustweightingTruncatedquadraticRobustweightingGeman&McClureRobustestimationFragmentedocclusionRegularizationanddenseopticalflowNeighboringpointsinthescenetypicallybelongtothesamesurfaceandhencetypicallyhavesimilarmotions.Sincetheyalsoprojecttonearbypixelsintheimage,weexpectspatialcoherenceinimageflow.InputimageHorizontalmotionVerticalmotionApplicationofopticalflowvideomatchingInputfortheNPRalgorithmBrushesEdgeclippingGradientSmoothgradientTexturedbrushEdgeclippingTemporalartifactsFrame-by-frameapplicationoftheNPRalgorithmTemporalcoherenceReferencesB.D.LucasandT.Kanade,AnIterativeImageRegistrationTechniquewithanApplicationtoStereoVision,Proceedingsofthe1981DARPAImageUnderstandingWorkshop,1981,pp121-130.Bergen,J.R.andAnandan,P.andHanna,K.J.andHingorani,R.,HierarchicalMod