4/20/2021
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
MOTION AND OPTICAL FLOW
‘-
Many slides adapted from S. Seitz, R. Szeliski, M. Pollefeys, K. Grauman and others…
1
4/20/2021
Video
• A video is a sequence of frames captured over time
• Now our image data is a function of space (x, y) and time (t)
‘-
Motion Application
• Background subtraction
• A static camera is observing a scene
• Goal: separate the static background from the moving foreground
‘-
2
4/20/2021
Background subtraction • Form an initial background estimate
• For each frame:
• Update estimate using a moving average
• Subtract the background estimate from the frame
‘-
• Use median filtering to “clean up” the results
• Challenges?
• Periodic Motion • Camera motion • Shadows
• Label as foreground each pixel where the magnitude of the difference is greater than some threshold
Exercise
Can you come up with others?
Motion Application • Shot Boundary Detection
• Commercial video is usually composed of shots or sequences showing the same objects or scene
• Goal: segment video into shots for summarization and browsing ‘-
(each shot can be represented by a single keyframe in a user
interface)
• Difference from background subtraction: the camera is not necessarily stationary
3
4/20/2021
Shot Boundary Detection • For each frame
• Compute the distance between the current frame and the previous one
‐ Pixel-by-pixel differences
‐ Differences of color histograms ‐ Block comparison
‘-
• If the distance is greater than some threshold, classify the frame as a shot boundary
• Challenges?
• Content shift (slow or fast)
Exercise
Can you come up with others?
Motion Application • Motion segmentation
• Segment the video into multiple coherently moving objects ‘-
4
4/20/2021
Motion and perceptual organization • Sometimes, motion is the only cue
‘-
Gestalt psychology (Max Wertheimer, 1880-1943)
Motion and perceptual organization • Sometimes, motion is the only cue
‘-
5
4/20/2021
Motion and perceptual organization • Sometimes, motion is the only cue
‘-
Motion and perceptual organization • Sometimes, motion is the only cue
‘-
6
4/20/2021
Motion and perceptual organization
• Even “impoverished” motion data can evoke a strong percept
‘-
Motion and perceptual organization
• Even “impoverished” motion data can evoke a strong percept
‘-
7
4/20/2021
Motion estimation: Optical flow
Optic flow is the apparent motion of objects or surfaces
‘-
We will start by estimating motion of each pixel separately Then will consider motion of entire image
Problem definition: optical flow
‘-
How to estimate pixel motion from image I(x,y,t) to I(x,y,t+1) • Solve pixel correspondence problem
– given a pixel in I(x,y,t), look for nearby pixels of the same color in I(x,y,t+1)
Key assumptions
• color constancy: a point in I(x,y,t) looks the same in I(x,y,t+1)
– For grayscale images, this is brightness constancy • small motion: points do not move very far
This is called the optical flow problem
I(x, y,t) I(x, y,t 1)
8
4/20/2021
Optical flow constraints (grayscale images)
‘-
• brightness constancy constraint (equation)
I ( x , y , t ) I ( x u , y v , t 1)
• small motion: (u and v are less than 1 pixel, or smooth)
Taylor series expansion of I: I I
I (x u, y v) I (x, y) x u y v [higher order terms]
I(x,y)I uI v x y
I(x, y,t) I(x, y,t 1) • Let’s look at these constraints more closely
Optical flow equation
• Combining these two equations
0 I(xu,yv,t1)I(x,y,t)
I ( x , y , t 1) I x u I y v I ( x , y , t ) ‘-
(Short hand: 𝐼
Exercise
Pause Video and Work the Math!
for t or t+1)
9
4/20/2021
Optical flow equation
• Combining these two equations
0 I(xu,yv,t1)I(x,y,t)
(Shorthand:𝐼 fort ort+1)
Exercise
Pause Video and Work the Math!
I(x,y,t1)IxuIyvI(x,y,t) ‘-
[I(x,y,t1)I(x,y,t)]I uI v xy
It IxuIyv It Iu,v
Optical flow equation • Combining these two equations
0 I(xu,yv,t1)I(x,y,t)
I ( x , y , t 1) I x u I y v I ( x , y , t )
IxuIyv ‘-
IxuIyv It Iu,v
In the limit as u and v go to zero, this becomes exact
0It Iu,v
(Short hand: 𝐼
for t or t+1)
[ I ( x , y , t 1) I ( x , y , t ) ]
Exercise
Pause Video and Work the Math!
It
Brightness constancy constraint equation
Ix uIy vIt 0
10
4/20/2021
How does this make sense?
• What do the static image gradients have to do with motion
estimation?
Brightness constancy constraint equation
Ix uIy vIt 0
‘-
The brightness constancy constraint
Can we use this equation to recover image motion (u,v) at each pixel?
0It Iu,v or IxuIyvIt 0 • How many equations and unknowns per pixel?
‘-
The component of the motion perpendicular to the gradient (i.e., parallel to the edge) cannot be measured
•One equation (this is a scalar equation!), two unknowns (u,v)
If (u, v) satisfies the equation, so does (u+u’, v+v’ ) if
T Iu’ v’ 0
gradient
(u’,v’)
(u,v)
(u+u’,v+v’) edge
11
4/20/2021
Aperture problem
‘-
‘-
12
4/20/2021
‘-
The barber pole illusion
‘-
http://en.wikipedia.org/wiki/Barberpole_illusion
13
4/20/2021
The barber pole illusion
‘-
http://en.wikipedia.org/wiki/Barberpole_illusion
Solving the ambiguity…
• How to get more equations for a pixel?
• Spatial coherence constraint
• Assume the pixel’s neighbors have the same (u,v) • If we use a 5×5 window, that gives us 25 equations per pixel
‘-
B. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 674–679, 1981.
14
4/20/2021
Solving the ambiguity… • Least squares problem:
‘-
Matching patches across images • Overconstrained linear system
‘-
The summations are over all pixels in the K x K window
Least squares solution for d given by
15
4/20/2021
Conditions for solvability
Optimal (u, v) satisfies Lucas-Kanade equation
‘-
When is this solvable? I.e., what are good points to track?
• ATA should be invertible
• ATA should not be too small due to noise
– eigenvalues 1 and 2 of ATA should not be too small
• ATA should be well-conditioned
– 1/ 2 should not be too large ( 1 = larger eigenvalue) Does this remind you of anything?
Criteria for Harris corner detector
Low texture region
‘-
– gradients have small magnitude – small 1, small 2
16
4/20/2021
Edge
‘-
– large gradients, all the same – large 1, small 2
High textured region
‘-
– gradients are different, large magnitudes – large 1, large 2
17
4/20/2021
The aperture problem resolved
‘-
Actual motion
The aperture problem resolved
‘-
Perceived motion
18
4/20/2021
Errors in Lucas-Kanade
• A point does not move like its neighbors
• Motion segmentation
• Brightness constancy does not hold
‘-
• The motion is large (larger than a pixel)
1. Not-linear: Iterative refinement
2. Local minima: coarse-to-fine estimation
• Do exhaustive neighborhood search with normalized correlation – tracking features – maybe SIFT – more later….
Revisiting the small motion assumption
• Is this motion small enough?
• Probably not—it’s much larger than one pixel • How might we solve this problem?
‘-
19
4/20/2021
Coarse-to-fine optical flow estimation
u=1.25 pixels u=2.5 pixels
‘-
u=5 pixels
image1
Gaussian pyramid of image 1
u=10 pixels image 2
Gaussian pyramid of image 2
run iterative L-K
warp & upsample
run iterative L-K
. . .
‘-
image I2
Gaussian pyramid of image 2
image J1
Gaussian pyramid of image 1
20
4/20/2021
Optical Flow Results
‘-
* From Khurram Hassan-Shafique CAP5415 Computer Vision 2003
‘-
* From Khurram Hassan-Shafique CAP5415 Computer Vision 2003
21
4/20/2021
Deep optical flow, 2015
Synthetic Training data
‘-
Fischer et al. 2015. https://arxiv.org/abs/1504.06852
Deep optical flow, 2015
Results on Sintel
‘-
Fischer et al. 2015. https://arxiv.org/abs/1504.06852
22