Motion Computing in Image AnalysisRoadmapImportance of Visual MotionApparent MotionOptic Flow ComputationSlide 6Slide 7Aperture ProblemSlide 9Slide 10Slide 11Optic Flow ConstraintLucas-Kanade Optic FlowSlide 14EdgeLow texture regionHigh texture regionImproving the Lucas-Kanade methodIterative Lucas-Kanade methodSlide 20Slide 21Feature Based MethodSlide 23Estimation CriterionEstimation Criterion(contd.)Slide 26Slide 27Slide 28Slide 29Slide 30Block Matching AlgorithmsBlock Matching Algorithms(contd.)Slide 33Slide 34Slide 35ConclusionMotion Computing in Image Analysis- Mani V ThomasCISC 489/689RoadmapOptic Flow ConstraintOptic Flow ComputationGradient Based ApproachFeature Based ApproachEstimation CriterionBlock Matching algorithmsConclusionSome slides and illustrations are from M. Pollefeys and M. ShahImportance of Visual MotionApparent motion of objects on the image plane is a strong cue to understand structure and 3D motionBiological visual systems infer properties of the 3D world via motionTwo sub-problems of motionProblem of correspondence estimationWhich elements of a frame correspond to which elements of the next frameProblem of reconstructionGiven the correspondence and the camera’s intrinsic parameters can we infer 3D motion and/or structureCourtesy: E. Trucco and A. Verri, “Introductory techniques for 3D Computer Vision”Apparent MotionApparent motion of objects on the image planeCaution required!!Consider a perfectly uniform sphere that is rotating but no change in the light directionOptic flow is zeroPerfectly uniform sphere that is stationary but the light is changingOptic flow existsHope – apparent motion is very close to the actual motionCourtesy: E. Trucco and A. Verri, “Introductory techniques for 3D Computer Vision”Optic Flow ComputationTwo strategies for computing motionDifferential MethodsSpatio temporal derivatives for estimation of flow at every positionMulti-scale analysis required if motion not constrained within a small rangeDense flow measurementsMatching MethodsFeature extraction(Image edges, corners)Feature/Block Matching and error minimizationSparse flow measurementsCourtesy: E. Trucco and A. Verri, “Introductory techniques for 3D Computer Vision”Optic Flow ComputationImage Brightness Constancy assumptionLet E be the image intensity as captured by the cameraUsing Taylor series to expand EApparent brightness of moving objects remains constant   ttEyyExxEtyxEttyyxxE  ,,,,0dtdEtEdtdyyEdtdxxE   tEtyyEtxxELtttyxEttyyxxEL ttt 00,,,,Optic Flow ComputationImage Brightness Constancy assumptionApparent brightness of moving objects remains constantThe are the image gradient while the are the components of the motion fieldCourtesy: E. Trucco and A. Verri, “Introductory techniques for 3D Computer Vision”0tEdtdyyEdtdxxE EyExE  , vdtdydtdx , 0tTEE vAperture ProblemWe can measure Terms that can be measuredTerms to be computedNumber of equations - 1The component of the motion field that is orthogonal to the spatial image gradient is not constrained by the image brightness constancy assumptionIntuitivelyThe component of the flow in the gradient direction is determinedThe component of the flow parallel to an edge is unknownCourtesy: E. Trucco and A. Verri, “Introductory techniques for 3D Computer Vision”tEyExE  ,,dtdydtdx ,Different physical motion but same measurable motion within a fixed windowRoadmapOptic Flow ConstraintOptic Flow ComputationGradient Based ApproachFeature Based ApproachEstimation CriterionBlock Matching algorithmsConclusionSome slides and illustrations are from M. Pollefeys and M. ShahOptic Flow ConstraintHow to get more equations for a pixel?Basic idea: impose additional constraintsMost common is to assume that the flow field is smooth locallyOne method: pretend the pixel’s neighbors have the same (u,v)If we use a 5x5 window, that gives us 25 equations per pixel!   0. itiEvuE pp            12512225252125252211bdAEEEvuEEEEEEtttyxyxyxpppppppppLucas-Kanade Optic FlowWe now have more equations than unknownsSolve the least squares problemMinimum least squares solution (in d) is given byFirst proposed by Lucas-Kanade in 1981Summation performed over all the pixels in the windowbAdbdA min12512225   tytxyyxyyxxxTTEEEEvuEEEEEEEEbAdAA1252521222Lucas-Kanade Optic FlowLucas-Kanade Optic flowWhen is the Lucas-Kanade equations solvableATA should be invertible ATA should not be too small (effects of noise)Eigenvalues of ATA, 1 and 2 should not be smallATA should be well conditioned1/2 should not be large (1 = larger eigenvalue)tytxyyxyyxxxEEEEvuEEEEEEEEEdgeGradient is large in magnitudeLarge 1 but small 2Low texture regionGradients has small magnitudeSmall 1 and small 2High texture regionGradients are different with large magnitudesLarge 1 and large 2Improving the Lucas-Kanade methodWhen our assumptions are violatedBrightness constancy is not satisfiedThe motion is not smallA point does not move like its neighborsIterative Lucas-Kanade AlgorithmEstimate velocity at each pixel by solving Lucas-Kanade equationsWarp H towards I using the estimated flow fielduse image warping techniquesRepeat until convergenceIterative Lucas-Kanade methodimage Iimage HGaussian pyramid of image H Gaussian pyramid of image Iimage Iimage Hu=10 pixelsu=5 pixelsu=2.5 pixelsu=1.25 pixelsIterative Lucas-Kanade methodimage Iimage JGaussian pyramid of image H Gaussian pyramid of image Iimage Iimage Hrun iterative L-Krun iterative