1 of 50

Lecture 9: Motion estimation

1

Most slides from S. Lazebnik, which are based on other slides from S. Seitz, R. Szeliski, M. Pollefeys

2 of 50

Announcements

  • Please note the Piazza post is to clarify that you do not need to email me for extensions unless there is an extreme circumstance where you need support

​

  • No homework due this week - next week panoramas due

​

  • Proposal info out this week for the project

2

3 of 50

Corners

https://web.eecs.umich.edu/~justincj/slides/eecs442/winter2020/442_WI2020_lecture09.pdf

​

Slides 43-61 for eigenvalue intuition, through 71 for Harris Detection

4 of 50

Motion

5 of 50

Motion is a powerful perceptual cue

5

Yuwen Xiong, Mengye Ren, Wenyuan Zeng, Raquel Urtasun. Self-Supervised Representation Learning from Flow Equivariance. arXiv 2021.

[Yang et al., “Self-supervised Video Object Segmentation by Motion Grouping”, 2021]

6 of 50

Motion is a powerful perceptual cue

6

G. Johansson, “Visual Perception of Biological Motion and a Model For Its Analysis", Perception and Psychophysics 14, 201-211, 1973.

Source: S. Lazebnik

7 of 50

Optical flow

7

Source: S. Lazebnik

  • Optical flow is the apparent motion of brightness patterns in the image
    • Can be caused by camera motion, object motion, or changes of lighting in the scene

8 of 50

Estimating optical flow

  • Given two consecutive frames, estimate the motion field u(x,y) and v(x,y) between them

8

  • How can we estimate it? Some assumptions:
    • Brightness constancy: projection of the same point looks the same in every frame
    • Small motion: points do not move very far
    • Spatial coherence: points move like their neighbors

I(x,y,t–1)

I(x,y,t)

Source: S. Lazebnik

9 of 50

The brightness constancy constraint

Simple loss function [Lucas & Kanade 1981]. Find flow that minimizes:

I(x,y,t–1)

I(x,y,t)

Source: S. Lazebnik

10 of 50

The brightness constancy constraint

Brightness Constancy Equation:

10

Linearizing the right side using Taylor expansion:

I(x,y,t–1)

I(x,y,t)

Therefore:

Source: S. Lazebnik

Derivative in y direction

Derivative in time:

11 of 50

The brightness constancy constraint

  • How many equations and unknowns per pixel?
    • One equation, two unknowns

11

  • Under-constrained. Let’s rewrite it:
  • The component of the flow perpendicular to the image gradient (i.e., parallel to the edge) is unknown!

edge

(u,v)

(u’,v’)

gradient

(u+u’,v+v’)

If (u, v) satisfies the equation, �so does (u+u’, v+v’) if

Source: S. Lazebnik

12 of 50

The aperture problem

12

Perceived motion

Source: S. Lazebnik

13 of 50

The aperture problem

13

Actual motion

Source: S. Lazebnik

14 of 50

The barber pole illusion

14

Source: S. Lazebnik

15 of 50

The barber pole illusion

15

Source: S. Lazebnik

16 of 50

Solving the aperture problem

  • How to get more equations for a pixel?
  • Spatial coherence constraint: assume the pixel’s neighbors have the same (u,v)
    • E.g., if we use a 5x5 window, that gives us 25 equations per pixel

16

…

…

…

[Lucas & Kanade 1981]

Source: S. Lazebnik

17 of 50

Lucas-Kanade flow

17

When is this system solvable?

[Lucas & Kanade 1981]

Least squares problem:

…

…

…

Source: S. Lazebnik

18 of 50

Lucas-Kanade optical flow

18

(summations are over all pixels in the window)

  • Solution given by

M = ATA is the

“second moment” matrix

(also Gauss-Newton approximation to Hessian)

[Lucas & Kanade 1981]

…

…

…

Source: S. Lazebnik

19 of 50

Analyzing the second moment matrix

19

λ1

λ2

“Corner”�λ1 and λ2 are large,� λ1 ~ λ2

λ1 and λ2 are small

“Edge” �λ1 >> λ2

“Edge” �λ2 >> λ1

“Flat” region

  • Estimation of optical flow is well-conditioned precisely for regions with high “cornerness”:

Eigenvalues

of M

Source: S. Lazebnik

20 of 50

Conditions for solvability

20

Source: S. Lazebnik

Bad case: single, straight edge

21 of 50

Conditions for solvability

21

Source: S. Lazebnik

Good case

22 of 50

Lucas-Kanade flow example

22

Input frames

Output

Source: S. Lazebnik

23 of 50

Fixing the errors in Lucas-Kanade

  • The motion is large (larger than a pixel)
    • Iterative refinement
    • Multi-resolution (coarse-to-fine) estimation�
  • Local ambiguity
    • Smooth using graphical model refinement

23

Source: S. Lazebnik

24 of 50

Large motions

24

Source: Khurram Hassan-Shafique CAP5415 Computer Vision 2003

25 of 50

Idea #1: iterative estimation

Initialize flow: u0(x, y) = v0(x, y) = 0

For each iteration i:

              • Linearize around current solution. Find an update for problem:���by solving linear least squares problem for each pixel:
              • Apply updates: and

Goal: minimize matching error

Iterative algorithm:

where the window width/height is 2N+1

26 of 50

Idea #2: Multi-scale estimation

26

Source: Khurram Hassan-Shafique CAP5415 Computer Vision 2003

27 of 50

Idea #2: Multi-scale estimation

​

For each iteration i:

              • Linearize around current solution. Find an update for problem:���by solving linear least squares problem for each pixel:
              • Apply updates: and

Solve:

Initialize flow: u0(x, y) = v0(x, y) = 0

For each scale s of Gaussian pyramid:

Initialize flow from previous (coarser) scale

              • Extra trick for smoother flow: apply median filter to ui+1 and vi+1

2x scale

2x flow magnitude

28 of 50

Example

28

Flow visualization

Coarse-to-fine LK with median filtering

Coarse-to-fine LK

Input two frames

Source: Ce Liu

29 of 50

Smoothness assumption

Solve:

1

Goal: minimize matching error + smoothness [Horn and Schunck 1981]

where p and p’ are neighboring pixels

match cost

smoothness

    • Can solve using gradient descent or nonlinear least squares

30 of 50

Smoothness assumption

30

Flow visualization

Coarse-to-fine LK

Input two frames

Horn-Schunck

Source: Ce Liu

31 of 50

Warping

31

Warp image 1 to image 2

 

 

 

32 of 50

Flow with warping

 

Solve:

Initialize flow: u0(x, y) = v0(x, y) = 0

For each scale s:

Initialize flow from previous (coarser) scale

33 of 50

Simple application: slow motion

Solve:

1

    • Flow used in lots of familiar places!
      • E.g., video compression, denoising, action recognition, …�
    • One application: use flow to estimate where pixel will be between frames�
    • Synthesize intermediate frames

(x, y) at time t-1

(x + u, y + v) at time t

34 of 50

35 of 50

Structure from motion with flow

[Teed and Deng, 2021]

Use optical flow to find correspondences between frames.

Also called “passive structure from motion”�

36 of 50

Passive Structure From Motion

The camera stay still but the scene moves

​

The same equations can estimate camera movement and depth!

Camera 1

Camera 2

Camera 3

R1,t1

R2,t2

R3,t3

X1

X4

X3

X2

X5

X6

X7

p1,1

p1,2

p1,3

37 of 50

Application: motion magnification.

enlarge tiny motions, making them easier to perceive [Liu et al., 2005].

Daniel Geng

Zhaoying Pan

[Pan*, Geng*, Owens, “Self-Supervised Motion Magnification by Backpropagating Through Optical Flow”, NeurIPS 2023]

38 of 50

Motion magnification model

Input frames

[Geng, Pan, Owens, “Self-supervised Lagrangian Motion Magnification”, In Submission]

Magnified 2nd frame

U-Net

39 of 50

Magnification loss

Optical flow

Flow field

40 of 50

Magnification loss

Optical flow

Flow field

41 of 50

1

Motion magnification loss

42 of 50

magnification factor

1

Motion magnification loss

Backprop through the optical flow during training!

43 of 50

1

Motion magnification loss

44 of 50

1

Motion magnification loss

45 of 50

1

Motion magnification loss

1

46 of 50

Next lecture: machine learning

46

47 of 50

Coarse-to-fine refinement

  • Lucas-Kanade is a greedy algorithm that converges to local minimum
  • Initialization is crucial: if initialized with zero, then the underlying motion must be small
  • If underlying transform is significant, then coarse-to-fine is a must

47

Smooth & down-sampling

 

 

 

 

 

48 of 50

Feature tracking

48

C. Tomasi and T. Kanade. Shape and motion from image streams under orthography: �A factorization method. IJCV, 9(2):137-154, November 1992.

49 of 50

Feature tracking

49

  • Like in SIFT feature matching, only track distinctive regions
  • Small motion assumption: search only in small window

50 of 50

Tracking example

50

J. Shi and C. Tomasi. Good Features to Track. CVPR 1994.