09-Optical Flow.pptx

COMPUTER VISION – OPTICAL FLOW Prof. Mohsen Ebrahimi Moghaddam Computer Engineering Department Shahid Beheshti University OPTICAL FLOW Where did each pixel in image 1 go to in image 2 OPTICAL FLOW Pierre Kornprobst's Demo INTRODUCTION  Given a video sequence with camera/obje...

COMPUTER VISION – OPTICAL FLOW Prof. Mohsen Ebrahimi Moghaddam Computer Engineering Department Shahid Beheshti University OPTICAL FLOW Where did each pixel in image 1 go to in image 2 OPTICAL FLOW Pierre Kornprobst's Demo INTRODUCTION  Given a video sequence with camera/objects moving we can better understand the scene if we find the motions of the camera/objects. SCENE INTERPRETATION  How is the camera moving?  How many moving objects are there?  Which directions are they moving in?  How fast are they moving?  Can we recognize their type of motion (e.g. walking, running, etc.)? APPLICATIONS  Recover camera ego-motion. Result by MobilEye (www.mobileye.com) APPLICATIONS  Motion segmentation Result by: L.Zelnik-Manor, M.Machline, M.Irani “Multi-body Segmentation: Revisiting Motion Consistency” To appear, IJCV  APPLICATIONS  Structure from Motion Input Reconstructed shape Result by: L. Zhang, B. Curless, A. Hertzmann, S.M. Seitz “Shape and motion under varying illumination: Unifying structure from motion, photometric stereo, and multi-view stereo” ICCV’03 EXAMPLES OF MOTION FIELDS Forward Rotation Horizontal Closer motion translation objects appear to move faster!! MOTION FIELD & OPTICAL FLOW FIELD  Motion Field = Real world 3D motion  Optical Flow Field = Projection of the motion field onto the 2d image CCD 3D motion vector 2D optical flow vector  u  u, v   WHEN DOES IT BREAK? The screen is Homogeneous Fixed sphere. Non-rigid stationary yet objects generate Changing light texture motion displays motion zero optical source. flow. THE OPTICAL FLOW FIELD Still, in many cases it does work….  Goal:  Find for each pixel a velocity vector u  u, v  which says:  How quickly is the pixel moving across the image  In which direction it is moving METHODS FOR DETERMINING OPTICAL FLOW Phase correlation methods Block-based methods Differential methods, such as: Lucas–Kanade method Horn–Schunck method Buxton–Buxton method Black–Jepson method HOW DO WE ACTUALLY DO THAT? ESTIMATING OPTICAL FLOW  Assume the image intensity I is constant Time = t Time = t+dt  x, y   x  dx, y  dy  I  x, y, t   I  x  dx, y  dy, t  dt   BRIGHTNESS CONSTANCY EQUATION I  x, y, t  I  x  dx, y  dy, t  dt  First order Taylor Expansion I I I I  x, y, t   dx  dy  dt x y t Simplify notations: I x dx  I y dy  I t dt 0 Divide by dt and denote: dx dy u v dt dt Problem I: One equation, I xu  I y v  I t two unknowns PROBLEM II: “THE APERTURE PROBLEM”  Forpoints on a line of fixed intensity we can only recover the normal flow Time t Time t+dt ? Where did the blue point move to? We need additional constraints PROBLEM II: “THE APERTURE PROBLEM” Actual motion PROBLEM II: “THE APERTURE PROBLEM” Perceived motion USE LOCAL INFORMATION Sometimes enlarging the aperture can help  LOCAL SMOOTHNESS LUCAS KANADE (1984)  u I xu  I y v  I t Ix I y     I t  v Assume constant (u,v) in small neighborhood  I x1 I y1   I t1   I I   u    I   x 2 y 2   v   t2        Problem: Overconstrained linear system  Solution: Least-squares method Au b LEAST-SQUARES METHOD (EXAMPLE) As a result of an experiment, four (x,y) data points were obtained, (1,6), (2,5), (3,7), and (4,10). It is desired to find a line that fits "best" these four points. In other words, we would like to find the numbers and that approximately solve the overconstrained linear system: LEAST-SQUARES METHOD (EXAMPLE) The least squares approach to solving this problem is to try to make as small as possible the sum of squares of "errors" between the right- and left-hand sides of these equations, that is, to find the minimum of the function: The minimum is determined by calculating the partial derivatives of S(, ) with respect to and and setting them to zero. LEAST-SQUARES METHOD (GENERAL PROBLEM) Consider an overconstrained system: of m linear equations in n unknown coefficients, m>n. This can be written in matrix form as: LEAST-SQUARES METHOD (GENERAL PROBLEM) Such a system usually has no solution, so the goal is instead to find the coefficients β which fit the equations "best, Define: Then: LEAST-SQUARES METHOD (GENERAL PROBLEM) S is minimized when its gradient vector is zero.  LEAST-SQUARES METHOD (GENERAL PROBLEM) The normal equations are written in matrix notation as: The solution of the normal equations yields the vector LUCAS KANADE (1984)  2 Goal: Minimize Au  b Method: Least-Squares  Au b  T T A A u A b 2x2 2x1 2x1  T 1 T  uA A A b  HOW DOES LUCAS-KANADE BEHAVE?  T 1 T  uA A A b   2 T  Ix  IxI y  A A  2    I x I y  I y  We want this matrix to be invertible. i.e., no zero eigenvalues HOW DOES LUCAS-KANADE BEHAVE? Edge  T  A Abecomes singular  I y , I x   I , I    I x2   IxI y    I y  2    0   x y I  0   IxI y  y  x  I  Iy  I  is eigenvecto r with eigenvalue 0  x  HOW DOES LUCAS-KANADE BEHAVE? Homogeneous  T  A A 0 0 eigenvalues  I x , I y  0  HOW DOES LUCAS-KANADE BEHAVE?  Textured regions  two high eigenvalues  I x , I y  0 HOW DOES LUCAS-KANADE BEHAVE? Edge  T  A Abecomes singular Homogeneous regions  low gradients T A A 0 High texture  OTHER BREAK-DOWNS  Brightness constancy is not satisfied Correlation based methods  A point does not move like its neighbors  what is the ideal window size? Horn-Schunck method  The motion is not small (Taylor expansion doesn’t hold) Use multi-scale estimation  MULTI-SCALE FLOW ESTIMATION u=1.25 pixels u=2.5 pixels u=5 pixels u=10 pixels image Itt-1 imageimage It+1 I Gaussian pyramid of image It Gaussian pyramid of image It+1  MULTI-SCALE FLOW ESTIMATION run Lucas-Kanade warp & upsample run Lucas-Kanade... image Itt-1 image IIt+1 image Gaussian pyramid of image It Gaussian pyramid of image It+1 EXAMPLES: MOTION BASED SEGMENTATION Input Segmentation result Result by: L.Zelnik-Manor, M.Machline, M.Irani “Multi-body Segmentation: Revisiting Motion Consistency” To appear, IJCV  AFFINE MOTION For panning camera or planar surfaces: u  p1  p2 x  p3 y v  p4  p5 x  p6 y I x ( p1  p2 x  p3 y )  I y ( p4  p5 x  p6 y )  I t  Ix Ixx Ix y Iy Iyx I y y  p  I t Only 6 parameters to solve for Better results That’s all for today