Slide 1: Image Motion
Slide 2: The Information from Image Motion • 3D motion between observer and scene + structure of the scene – Wallach O’Connell (1953): Kinetic depth effect – http://www.biols.susx.ac.uk/home/George_Mather/Motion/KDE .HTML – Motion parallax: two static points close by in the image with different image motion; the larger translational motion corresponds to the point closer by (smaller depth) • Recognition – Johansson (1975): Light bulbs on joints – http://www.biols.susx.ac.uk/home/George_Mather/Motion/inde x.html
Slide 3: Examples of Motion Fields I (a) (b) (a) Motion field of a pilot looking straight ahead while approaching a fixed point on a landing strip. (b) Pilot is looking to the right in level flight.
Slide 4: Examples of Motion Fields II (a) (b) (c) (d) (a) Translation perpendicular to a surface. (b) Rotation about axis perpendicular to image plane. (c) Translation parallel to a surface at a constant distance. (d) Translation parallel to an obstacle in front of a more distant background.
Slide 5: Optical flow
Slide 6: Assuming that illumination does not change: • Image changes are due to the RELATIVE MOTION between the scene and the camera. • There are 3 possibilities: – Camera still, moving scene – Moving camera, still scene – Moving camera, moving scene
Slide 7: Motion Analysis Problems • Correspondence Problem – Track corresponding elements across frames • Reconstruction Problem – Given a number of corresponding elements, and camera parameters, what can we say about the 3D motion and structure of the observed scene? • Segmentation Problem – What are the regions of the image plane which correspond to different moving objects?
Slide 8: Motion Field (MF) • The MF assigns a velocity vector to each pixel in the image. • These velocities are INDUCED by the RELATIVE MOTION btw the camera and the 3D scene • The MF can be thought as the projection of the 3D velocities on the image plane.
Slide 9: Motion Field and Optical Flow Field • Motion field: projection of 3D motion vectors on image plane Object point P0 has velocity v 0 , induces v i in image dri dt r r r0 related to ri by i  0 f r0  z 0 ˆ v0  v1  dr0 dt • • Optical flow field: apparent motion of brightness patterns We equate motion field with optical flow field
Slide 10: 2 Cases Where this Assumption Clearly is not Valid (a) A smooth sphere is rotating under constant illumination. Thus the optical flow field is zero, but the motion field is not. (b) A fixed sphere is illuminated by a moving source—the shading of the image changes. Thus the motion field is zero, but the optical flow field is not. (a) (b)
Slide 11: What is Meant by Apparent Motion of Brightness Pattern? The apparent motion of brightness patterns is an awkward concept. It is not easy to decide which point P' on a contour C' of constant brightness in the second image corresponds to a particular point P on the corresponding contour C in the first image.
Slide 12: The aperture problem
Slide 13: Aperture Problem (a) (b) (a) Line feature observed through a small aperture at time t. (b) At time t+t the feature has moved to a new position. It is not possible to determine exactly where each point has moved. From local image measurements only the flow component perpendicular to the line feature can be computed. Normal flow: Component of flow perpendicular to line feature.
Slide 14: Brightness Constancy Equation • Let P be a moving point in 3D: – At time t, P has coords (X(t),Y(t),Z(t)) – Let p=(x(t),y(t)) be the coords. of its image at time t. – Let E(x(t),y(t),t) be the brightness at p at time t. • Brightness Constancy Assumption: – As P moves over time, E(x(t),y(t),t) remains constant.
Slide 15: Brightness Constraint Equation Let E  x, y, t  be the irradiance and u  x, y  , v x, y  the components of optical flow. E  x  ut , y  vt , t  t   E  x, y, t  Taylor expansion E E E  y  t  e  E  x, y , t  x y t dividing by t and taking limit t  0 E  x , y , t   x E dx E dy E   0 x dt y dt t which is the expansion of the total derivative dE 0 dt short: E x u  E y v  Et  0
Slide 16: Brightness Constancy Equation Taking derivative wrt time:
Slide 17: Brightness Constancy Equation Let (Frame spatial gradient) (optical flow) and (derivative across frames)
Slide 18: Brightness Constancy Equation Becomes: vy rE -Et/|r E| vx The OF is CONSTRAINED to be on a line !
Slide 19: Interpretation Values of (u, v) satisfying the constraint equation lie on a straight line in velocity space. A local measurement only provides this constraint line (aperture problem). Normal flow u n E x , E y    u , v    Et Let n  E E E  x y x T T , Ey   E E E E  u n   u  nn   2 x t , 2 y t 2  E E E E  y x y x T
Slide 20: Optical flow equation Barber Pole illusion http://www.sandlotscience.com/Ambiguous/barberpole.htm
Slide 21: Solving the aperture problem • 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!
Slide 22: Constant flow • Prob: we have more equations than unknowns • Solution: solve least squares problem – minimum least squares solution given by solution (in d) of: – The summations are over all pixels in the K x K window
Slide 23: Taking a closer look at (ATA) This is the same matrix we used for corner detection!
Slide 24: Taking a closer look at (ATA) The matrix for corner detection: is singular (not invertible) when det(ATA) = 0 But det(ATA) =  i = 0 -> one or both e.v. are 0 One e.v. = 0 -> no corner, just an edge Two e.v. = 0 -> no corner, homogeneous region Aperture Problem !
Slide 25: Edge – large gradients, all the same – large1, small 2
Slide 26: Low texture region – gradients have small magnitude – small1, small 2
Slide 27: High textured region – gradients are different, large magnitudes – large1, large 2
Slide 28: An improvement … • NOTE: – The assumption of constant OF is more likely to be wrong as we move away from the point of interest (the center point of Q) Use weights to control the influence of the points: the farther from p, the less weight
Slide 29: Solving for v with weights: • Let W be a diagonal matrix with weights • Multiply both sides of Av = b by W: WAv=Wb • Multiply both sides of WAv = Wb by (WA)T: AT WWA v = AT WWb • AT W2A is square (2x2): • (ATW2A)-1 exists if det(ATW2A)  0 • Assuming that (ATW2A)-1 does exists: (AT W2A)-1 (AT W2A) v = (AT W2A)-1 AT W2b v = (AT W2A)-1 AT W2b
Slide 30: Observation • This is a two image problem BUT – Can measure sensitivity by just looking at one of the images! – This tells us which pixels are easy to track, which are hard • very useful later on when we do feature tracking...
Slide 31: Revisiting the small motion assumption • Is this motion small enough? – Probably not—it’s much larger than one pixel (2nd order terms dominate) – How might we solve this problem?
Slide 32: Iterative Refinement • Iterative Lukas-Kanade Algorithm 1. Estimate velocity at each pixel by solving Lucas-Kanade equations 2. Warp H towards I using the estimated flow field - use image warping techniques 3. Repeat until convergence
Slide 33: Reduce the resolution!
Slide 34: Coarse-to-fine optical flow estimation u=1.25 pixels u=2.5 pixels u=5 pixels image H Gaussian pyramid of image H u=10 pixels image I Gaussian pyramid of image I
Slide 35: Coarse-to-fine optical flow estimation run iterative L-K warp & upsample run iterative L-K . . . image J H Gaussian pyramid of image H image I Gaussian pyramid of image I
Slide 36: Optical flow result
Slide 37: Additional Constraints • Additional constraints are necessary to estimate optical flow, for example, constraints on size of derivatives, or parametric models of the velocity field. • Horn and Schunck (1981): global smoothness term es  ec   u D D 2 x  u y  v x  v y dx dy : departure from smoothness 2 2  2 2    E u  E v  E  x y t T dx dy : error in optical flow constraint equation Let A   Ax , Ay  denote the gradient of A  E  u  Et  2    u 2 2  v 2 2 dx dy  min  • This approach is called regularization. • Solve by means of calculus of variation.
Slide 38: Discrete implementation leads to iterative equations Geometric interpretation u , v denotes local averages of u and v u n 1 v n 1 Ex 1 2 2  Ex  E y   E x u n  E y v n  Et  E n v  y 1 2 2  Ex  E y  u n E u  x n  E y v n  Et  In the iterative scheme for estimating the optical flow, the new value  u , v  at a point is the average of the values of the neighbors  u , v  , minus an adjustment in the direction toward the constraint line.
Slide 39: Other Differential Techniques • Lucas Kanade (1984): Weighted least-squares (LS) fit to a constant model of u in a small neighborhood ; Denote A   E  x1  , , E  x n   , W  diag  W  x1  , , W  x n   , T T x  W 2  x   E  x, t   u  Et  x, t    min 2 b    E t  x1  ,  , E t  x n   u   AT W 2 A AT W 2 b 1 T •  • Nagel (1983,87): Oriented smoothness constraint; smoothness is not imposed across edges 2 2 2 2 2  E T u  Et     u x E y  u y E x    v x E y  v y E x    u 2  v 2 E 2  2   2 2  Uras et al. (1988): Use constraints on second-order derivatives dE  x, t  0 dt  E xx  x, t   E  x, t   xy E xy  x, t   u   Etx  x, t    v    E  x, t     E yy  x, t     ty 
Slide 40: Classification of Optical Flow Techniques • Gradient-based methods • Frequency-domain methods • Correlation methods
Slide 41: 3 Computational Stages 1. Prefiltering or smoothing with low-pass/band-pass filters to enhance signal-tonoise ratio 2. Extraction of basic measurements (e.g., spatiotemporal derivatives, spatiotemporal frequencies, local correlation surfaces) 3. Integration of these measurements, to produce 2D image flow using smoothness assumptions
Slide 42: Energy-based Methods • Adelson Berger (1985), Watson Ahumada (1985), Heeger (1988): Fourier transform of a translating 2D pattern: F E  wx , wy , wt   F E  wx , wy ,0  wx u  wy v  wt  • All the energy lies on a plane through the origin in frequency space Local energy is extracted using velocity-tuned filters (for example, Gabor-energy filters) Motion is found by fitting the best plane in frequency space Fleet Jepson (1990): Phase-based Technique – Assumption that phase is preserved (as opposed to amplitude) – Velocity tuned band pass filters have complex-valued outputs R  x , t , w     x , t , w  e i  x , t , w  with  the amplitude and  the phase d  0 or  x u   y v  t  0 dt
Slide 43: Correlation-based Methods Anandan (1987), Singh (1990) 1. Find displacement (dx, dy) which maximizes cross correlation CC  dx, dy   j n in  W  i, j   E  i, j   E  i  dx, j  dy  1 2 n n or minimizes sum of squared differences (SSD) SSD dx, dy   j  n i  n  W  i, j    E  i, j   E  i  dx, j  dy   1 2 n n 2 2. Smooth the correlation outputs
Slide 44: A Pattern of Hajime Ouchi
Slide 45: Bias in Flow Estimation Symmetric noise in spatial and temporal derivatives Notation: A=A-A', where A is the estimate, A' the actual value and A the error  E xi   E xi  u   E y i   E y i  v  E t i   E t i in matrix form  E  E  u  b T 1 expected value of u E  u   u' n s  E 'T E ' u' 2 1 LS solution u   E E  E T b n number of measurements  s standard deviation of spatial noise • Underestimation in length • Bias in direction: more underestimation in direction of fewer measurements
Slide 46: Epipolar Constraint for Discrete Motions C '-C, m  C , m'C ' coplanar, or t , m and Rm ' coplanar  t  m  T  Rm'  0 epipolar constraint   t   m  T  Rm'  0 m T Em'  0, E   t   R  m1  0 Def : m2    m3    m3    m2   t  m   t  m  m3 0 m1 m2   m1   0 
Slide 47:  x Consider a line ax  by  c  0 or  a, b, c   y   0,  1   T T or m T l  0 with l   a, b, c  and m   x, y,1 . If a line goes through t wo points m1 and m 2 , then m1 l  0 and m 2 l  0 or l  m1  m 2 .  lm ' and lm are the correspond ing epipolar lines. T T lm '  e  Rm '  t  Rm'  Em' lm '  Em Epipolar constraint : m T Em'  0 or m T lm '  0, lm '  Em': points lie on their corresponding epipolar lines. The epipole lies on all epipolar lines eT Em '  0 m' , or e T E  0. e1  E32 E21  E22 E31 e2  E31 E12  E11 E32 e3  E 22 E11  E 21 E12
Slide 48: Sources: • Horn (1986) • J. L. Barron, D. J. Fleet, S. S. Beauchemin (1994). Systems and Experiment. Performance of Optical Flow Techniques. IJCV 12(1):43–77. Available at http://www.cs.queesu.ca/home/fleet/ research/Projects/flowCompare.html • http://www.cfar.umd.edu/~fer/postscript/ouchipapernew.ps.gz (paper on Ouchi illusion) • http://www.cfar.umd.edu./ftp/TRs/CVL-Reports-1999/TR4080fermueller.ps.gz (paper on statistical bias) • http://www.cis.upenn.edu/~beau/home.html http://www.isi.uu.nl/people/michael/of.html (code for optical flow estimation techniques)