Say we want affine transformation

• How many knowns do we get with one match? mA = n
• n_x = a₀₀*m_x + a₀₁*m_y + a₀₂*1
• n_y = a₁₀*m_x + a₁₁*m_y + a₁₂*1
• Solve M a = b
• M^T M a = M^T b
• a = (M^T M)^-1 M^T b
• Still works if overdetermined
• WHY???

Linear least squares

Want to minimize squared error: || b - M a ||² =

b^Tb - 2a^TM^Tb + a^TM^TMa

This is convex and minimized when gradient = 0. So we take the derivative wrt a and set = 0.

-M^Tb + (M^TM)a = 0

(M^TM)a = M^Tb

a = (M^TM)^-1M^Tb yay!!!!

So how does least squares do?

So how does least squares do?

Error based on squared residual

Very scared of being wrong, even for just one point

Very bad at handling outliers in data

RANSAC: RANdom SAmple Consensus

RANSAC: RANdom SAmple Consensus

• Parameters: data, model, n points to fit model,�k iterations, t threshold, d “good” fit cutoff

bestmodel = None�bestfit = INF�While i < k:� sample = draw n random points from data� Fit model to sample� inliers = data within t of model� if inliers > bestfit:� Fit model to all inliers� bestfit = fit� bestmodel = model� if inliers > d:� return model�return bestmodel

• ​

RANSAC: RANdom SAmple Consensus

• Works well even with extreme noise.

We want projective (homography)

• New matrix equations:

​

​

​

​

• Same procedure, Solve M a = b
• Exact if #rows of M = 8
• Least squares if #rows of M > 8

In practice:

What’s happening?

Very bad for big panoramas!

How do we fix it? Cylinders!

How do we fix it? Cylinders!

Does it work?

Does it work? Yay!

THIS IS AS GOOD AS IT GETS!

• Not so fast…
• Our descriptor has some issues:
• Not invariant to lighting changes!
• Want features invariant to lighting

Histogram of Oriented Gradients (HOG)

Binning from http://aishack.in/tutorials/sift-scale-invariant-feature-transform-features/

• Dalal and Triggs 2005
• Better image descriptor
• Compute gradients
• Bin gradients
• Aggregate blocks (4x4, 16x16 cells)
• Normalize gradient magnitudes
• Not reliant on magnitude, just direction
• Invariant to some lighting changes
• Train SVM to recognize people

​

Histogram of Oriented Gradients (HOG)

​

​

THIS IS AS GOOD AS IT GETS!

• Not so fast…
• Harris and has some issues:
• Corners detection is rotation invariant
• Harris not invariant to scale
• Descriptors are also hard
• Just looking at pixels is not rotation invariant!
• HOG also not rotation invariant

Want features invariant to scaling, rotation, etc.

• Scale Invariant Feature Transform (SIFT)
• Lowe et al. 2004, many images from that paper
• Get scale-invariant response map
• Find keypoints
• Extract rotation-invariant descriptors
• Normalize based on orientation
• Normalize based on lighting

Extract DoG features at multiple scales

Find local-maxima in location and scale

Throw out weak responses and edges

• Estimate gradients
• Similar to before, look at nearby responses
• Not whole image, only a few points! Faster!
• Throw out weak responses
• Find cornery things
• Same deal, structure matrix, use det and trace information

Find main orientation of patches

• Look at weighted histogram of nearby gradients
• Any gradient within 80% of peak gets its own descriptor
• Multiple keypoints per pixel
• Descriptors are normalized based on main orientation

Keypoints are normalized gradient histograms

• Divide into subwindows (2x2, 4x4)
• Bin gradients within subwindow, get histogram
• Normalize to unit length
• Clamp at maximum .2
• Normalize again
• Helps with lighting changes!

SIFT is great!

• Find good keypoints, describe them
• Finding objects, recognition, panoramas, etc.

SIFT is great!

Topics:

• Sparse* Optical Flow (Lucas-Kanade, 1981)
• Dense Optical Flow (Farneback, 2003)

​

​

​

​

*LK can technically be dense.

What is Optical Flow?

What is Optical Flow?

Movement

What is Optical Flow?

Movement

What is Optical Flow?

Movement

What is Optical Flow?

Movement

What is Optical Flow?

Movement

Object

What is Optical Flow?

Movement

Pan

What is Optical Flow?

Movement

Forward

What is Optical Flow?

Movement

Why do we want Optical Flow?

Why do we want Optical Flow?

Motion Estimation

Why do we want Optical Flow?

Motion Estimation

Object Tracking

Why do we want Optical Flow?

Motion Estimation

Object Tracking

Visual Odometry

How do we find the flow in an image?

Feature Matching

Previously: Features!

• Highly descriptive local regions
• Ways to describe those regions
• Useful for:
• Matching
• Recognition
• Detection

Feature Matching

Feature Matching

Feature Matching

SOLVED!

Feature Matching

​

​

Disadvantages:

​

Feature Matching

Disadvantages:

-Sparse!

Feature Matching

Disadvantages:

-Sparse!

-Feature alignment not exact

Feature Matching

Feature Matching

Disadvantages:

-Sparse!

-Feature alignment not exact

-Low accuracy

Feature Matching

Advantages:

Disadvantages:

-Sparse!

-Feature alignment not exact

-Low accuracy

Feature Matching

Advantages:

-Scale/rotation invariant

-*kinda* lighting invariant

-Can handle large movements

Disadvantages:

-Sparse!

-Feature alignment not exact

-Low accuracy

Feature Matching

Advantages:

-Scale/rotation invariant

-*kinda* lighting invariant

-Can handle large movements

Disadvantages:

-Sparse!

-Feature alignment not exact

-Low accuracy

Overall: Doesn’t work very well for Optical Flow

What do we do instead?

An observation...

An observation...

An observation...

An observation...

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

An observation...

f(t)

f(-p)

An observation...

f(t)

f(-p)

SAME!

An observation...

f(t)

f(-p)

Insight: Moving the object to the right is the same as moving the observed pixel to the left

Lucas-Kanade Optical Flow

Can we use this relationship to compute optical flow?

Lucas-Kanade Optical Flow

Can we use this relationship to compute optical flow?

​

B.D. Lucas, T. Kanade, “An Image Registration Technique with an Application to Stereo Vision”, in Proceedings of Image Understanding Workshop, 1981, pp. 121-130.

Lucas-Kanade Optical Flow

Can we use this relationship to compute optical flow?

​

B.D. Lucas, T. Kanade, “An Image Registration Technique with an Application to Stereo Vision”, in Proceedings of Image Understanding Workshop, 1981, pp. 121-130.

You will be implementing the LK optical flow algorithm for the homework

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Observation point

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

The movement @p

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

First image

Second image

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Brightness

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Approximate with a first-order Taylor expansion

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Approximate with a first-order Taylor expansion

What in the doodely is a first-order Taylor expansion?

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

​

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For first-order i=1

≈ a₁x¹ + a₀x⁰

≈ mx + b

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For first-order i=1

≈ a₁x¹ + a₀x⁰

≈ mx + b

x

f(x)

mx + b

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For first-order i=1

≈ a₁x¹ + a₀x⁰

≈ mx + b

x

f(x)

mx + b

Equal at x

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Approximate with a first-order Taylor expansion

m(p - 𝚫p) + b ≈ f(p, t + 𝚫t)

Lucas-Kanade Optical Flow

Assuming the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Approximate with a first-order Taylor expansion

m(p - 𝚫p) + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

Out of space

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Subtract f(p, t) from both sides

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

​

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

​

Plugging mp + b in for f(p, t) cancels out!

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

​

Plugging mp + b in for f(p, t) cancels out!

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

These we know

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

These we know

This is what we want to know

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

These we know

This is what we want to know

What is this?!

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Slope

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Slope = derivative

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Slope = derivative, aka gradient,

We know how to do gradients!

Previously: Image derivatives

• Recall:
• We don’t have an “actual”�Function, must estimate
• Possibility: set h = 2
• What will that look like?

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

m = dp = dx 0

0 dy

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

-dp𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

-dp𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

Let’s drop the vector notation

Lucas-Kanade Optical Flow

mp - m𝚫p + b ≈ f(p, t + 𝚫t)

mp - m𝚫p + b - f(p, t) ≈ f(p, t + 𝚫t) - f(p, t)

Recall f(x, t) = mx + b

-m𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

-dp𝚫p ≈ f(p, t + 𝚫t) - f(p, t)

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

​

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Solve for u,v

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Solve for u,v

1 equation, 2 unknowns

Lucas-Kanade Optical Flow

-dx𝚫x + -dy𝚫y ≈ f((x,y), t + 𝚫t) - f((x,y), t)

Let’s clean up the notation a bit

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Solve for u,v

1 equation, 2 unknowns IMPOSSIBLE!

Lucas-Kanade Optical Flow

Let’s back up

​

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

​

Lucas-Kanade Optical Flow

Let’s back up

​

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

What does this mean?

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

Brightness/x-pixel

Brightness/y-pixel

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

u

v

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

u

v

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

u

v

Underspecified: Lots of u and v solve this equation.

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

u

v

Idea: What if we assume neighbors move together? I.e., they have the same u,v.

Lucas-Kanade Optical Flow

dx*u + dy*v = I_t[x,y] - I_t+𝚫t[x,y]

dx

dy

u

v

Lucas-Kanade Optical Flow

dx₁*u + dy₁*v = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

dx₂*u + dy₂*v = I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

dx₉*u + dy₉*v = I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

​

9 equations, 2 unknowns

Lucas-Kanade Optical Flow

dx₁*u + dy₁*v = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

dx₂*u + dy₂*v = I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

dx₉*u + dy₉*v = I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

​

9 equations, 2 unknowns

OVERSPECIFIED!

Lucas-Kanade Optical Flow

​

​

​

S𝚫p = T

T = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

Lucas-Kanade Optical Flow

​

​

​

S𝚫p = T

||S𝚫p - T||² = 0

𝚫p = (S^TS)^-1S^TT

T = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

Least-squares solution

Lucas-Kanade Optical Flow

​

​

​

S𝚫p = T

||S𝚫p - T||² = 0

𝚫p = (S^TS)^-1S^TT

T = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

What if this isn’t invertible?

Lucas-Kanade Optical Flow

​

​

​

S𝚫p = T

||S𝚫p - T||² = 0

𝚫p = (S^TS)^-1S^TT

T = I_t[x₁,y₁] - I_t+𝚫t[x₁,y₁]

I_t[x₂,y₂] - I_t+𝚫t[x₂,y₂]

...

I_t[x₉,y₉] - I_t+𝚫t[x₉,y₉]

What if this isn’t invertible?

E.G., no structure around (x,y)

Lucas-Kanade Optical Flow

Testing for invertibility: 𝚫p = (S^TS)^-1S^TT

​

Lucas-Kanade Optical Flow

Testing for invertibility: 𝚫p = (S^TS)^-1S^TT

S^TS is symmetric so it can be decomposed as

S^TS = U U^T

𝛌₁ 0

0 𝛌₂

Lucas-Kanade Optical Flow

Testing for invertibility: 𝚫p = (S^TS)^-1S^TT

S^TS is symmetric so it can be decomposed as

S^TS = U U^T

det(S^TS - 𝛌I) = 0

​

𝛌₁ 0

0 𝛌₂

Lucas-Kanade Optical Flow

Testing for invertibility: 𝚫p = (S^TS)^-1S^TT

S^TS is symmetric so it can be decomposed as

S^TS = U U^T

det(S^TS - 𝛌I) = 0

= 0

𝛌₁ 0

0 𝛌₂

𝚺_i (dx_i)² - 𝛌 𝚺_i (dx_i)(dy_i)

𝚺_i (dx_i)(dy_i) 𝚺_i (dy_i)² - 𝛌

Lucas-Kanade Optical Flow

Testing for invertibility: 𝚫p = (S^TS)^-1S^TT

S^TS is symmetric so it can be decomposed as

S^TS = U U^T

det(S^TS - 𝛌I) = 0

= 0

If either 𝛌₁ or 𝛌₂ are ≤0, S is not invertible and there is no solution!

𝛌₁ 0

0 𝛌₂

𝚺_i (dx_i)² - 𝛌 𝚺_i (dx_i)(dy_i)

𝚺_i (dx_i)(dy_i) 𝚺_i (dy_i)² - 𝛌

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Bad

No gradient

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Bad

No gradient

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Bad

No gradient

Slightly better

Can’t detect vertical motion

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Bad

No gradient

Slightly better

Can’t detect vertical motion

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

​

Bad

No gradient

Slightly better

Can’t detect vertical motion

Best

Vertical and horizontal motion

Lucas-Kanade Optical Flow

How to pick (x,y)? What makes a good feature?

CORNERS!

​

Lucas-Kanade Optical Flow

Demo

Lucas-Kanade Optical Flow

When does LK fail?

​

Lucas-Kanade Optical Flow

When does LK fail?

-Lighting changes

-Large movement

-Specularities

-No good features

-Aperture Problem

​

Lucas-Kanade Optical Flow

When does LK fail?

-Lighting changes

-Large movement

-Specularities

-No good features

-Aperture Problem

​

Lucas-Kanade Optical Flow

Aperture Problem

Lucas-Kanade Optical Flow

Aperture Problem

Line moving up and to the right

Lucas-Kanade Optical Flow

Aperture Problem

Line moving up and to the right

Lucas-Kanade Optical Flow

Aperture Problem

Line moving up and to the right

Line moving only to the right

Lucas-Kanade Optical Flow

Aperture Problem - Barber pole illusion

Lucas-Kanade Optical Flow

Aperture Problem - Barber pole illusion

Lucas-Kanade Optical Flow

Aperture Problem - Barber pole illusion

Actual movement to the right

Lucas-Kanade Optical Flow

Aperture Problem - Barber pole illusion

Apparent movement to the up and right

Homework 3

Implement Lucas-Kanade.

Come up with some *minor* way to improve it and test it.

​

Improving on LK: Iterative LK

dx₁*u + dy₁*v = I_t[x,y] - I_t+𝚫t[x,y]

Improving on LK: Iterative LK

dx₁*u + dy₁*v = I_t[x,y] - I_t+𝚫t[x,y]

​

dx₂*u + dy₂*v = I_t[x,y] - I_t+𝚫t[x + dx₁,y + dy₁]

Propagate dx₁, dy₁ forward and re-estimate

Improving on LK: Iterative LK

dx₁*u + dy₁*v = I_t[x,y] - I_t+𝚫t[x,y]

​

dx₂*u + dy₂*v = I_t[x,y] - I_t+𝚫t[x + dx₁,y + dy₁]

​

...

dx_n*u + dy_n*v = I_t[x,y] - I_t+𝚫t[x + dx_n-1,y + dy_n-1]

Propagate dx₁, dy₁ forward and re-estimate

Propagate dx₂, dy₂ forward and re-estimate

Improving on LK: Image Pyramids

Improving on LK: Image Pyramids

Image 1

Image 2

Improving on LK: Image Pyramids

Image 1

Image 2

Improving on LK: Image Pyramids

Image 1

Image 2

Run LK

Run LK

Run LK

Upsample

Upsample

Optical Flow

Optical Flow

Sparse vs Dense

Optical Flow

Sparse vs Dense

Compute flow only for specific features

Compute flow for all pixels

Optical Flow

Sparse vs Dense

Compute flow only for specific features

Compute flow for all pixels

Lucas-Kanade is technically a dense algorithm, but in practice only works on good feature points, i.e., it’s sparse.

Optical Flow

Is there a way to do dense optical flow?

Farnebäck Optical Flow

Farnebäck, Gunnar. "Two-frame motion estimation based on polynomial expansion." Scandinavian conference on Image analysis. Springer, Berlin, Heidelberg, 2003.

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

In LK we approximate this with a first-order Taylor Expansion

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For first-order i=1

≈ a₁x¹ + a₀x⁰

≈ mx + b

x

f(x)

mx + b

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For second-order i=2

≈ a₁x² + a₁x¹ + a₀x⁰

≈ ax² + bx + c

x

f(x)

ax² + bx + c

Quick & Dirty: Taylor Expansion

Approximate complex function with n^th-order polynomial

f(x) ≈ 𝚺_i a_ixⁱ

For second-order i=2

≈ a₁x² + a₁x¹ + a₀x⁰

≈ ax² + bx + c

≈ x^TAx + bx + c

x

f(x)

ax² + bx + c

Vector notation

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

Poly parameters from first image

Poly parameters from second image

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

A_t = A_t+𝚫t

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

A_t = A_t+𝚫t

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

A_t = A_t+𝚫t

b_t+𝚫t = b_t - 2A_t𝚫p

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

A_t = A_t+𝚫t

b_t+𝚫t = b_t - 2A_t𝚫p

Farnebäck Optical Flow

Recall: We assumed the object moves by 𝚫p over 𝚫t

f(p - 𝚫p, t) = f(p, t + 𝚫t)

Instead, let’s approximate with a second-order Taylor Expansion

(p-𝚫p)^TA_t(p-𝚫p) + b_t(p-𝚫p) + c_t = p^TA_t+𝚫tp + b_t+𝚫tp + c_t+𝚫t

p^TA_tp + (b_t - 2A_t𝚫p)^Tp + 𝚫p^TA_t𝚫p - b_t𝚫p + c_t = p^TA_t+𝚫tp + pb_t+𝚫t + c_t+𝚫t

A_t = A_t+𝚫t

b_t+𝚫t = b_t - 2A_t𝚫p

c_t+𝚫t = 𝚫p^TA_t𝚫p - b_t𝚫p + c_t

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

​

A, b, and c can be solved pointwise using least squares over a small neighborhood like before

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

​

A, b, and c can be solved pointwise using least squares over a small neighborhood like before

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

​

A, b, and c can be solved pointwise using least squares over a small neighborhood like before

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

​

A, b, and c can be solved pointwise using least squares over a small neighborhood like before

SAS^T + bS^T + c = T

||SAS^T + bS^T + c - T||² = 0

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

​

A, b, and c can be solved pointwise using least squares over a small neighborhood like before

SAS^T + bS^T + c = T

||SAS^T + bS^T + c - T||² = 0

Quadratic Regression

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

Solve for 𝚫p

𝚫p = -½(A_t)^-1(b_t+𝚫t - b_t)

Same problem as before:

What if it’s not invertible?

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A_t𝚫p = -½(b_t+𝚫t - b_t)

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A_t𝚫p = -½(b_t+𝚫t - b_t)

A_t = A_t+𝚫t

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A_t𝚫p = -½(b_t+𝚫t - b_t)

A_t = A_t+𝚫t

A_t ≠ A_t+𝚫t

In reality not equal

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A_t𝚫p = -½(b_t+𝚫t - b_t)

A_t = A_t+𝚫t

A_t ≠ A_t+𝚫t

In reality not equal

A = ½(A_t + A_t+𝚫t)

Average together

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = -½(b_t+𝚫t - b_t)

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = -½(b_t+𝚫t - b_t)

𝚫b = -½(b_t+𝚫t - b_t)

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = 𝚫b

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = 𝚫b

Assume neighbors move together (just like LK)

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = 𝚫b

Assume neighbors move together (just like LK)

A_i𝚫p = 𝚫b_i

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = 𝚫b

Assume neighbors move together (just like LK)

A_i𝚫p = 𝚫b_i

Apply least squares

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

Farnebäck Optical Flow

b_t+𝚫t = b_t - 2A_t𝚫p

​

Let’s try a different approach:

A𝚫p = 𝚫b

Assume neighbors move together (just like LK)

A_i𝚫p = 𝚫b_i

Apply least squares

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

Gaussian weight (so we care more about the center of the neighborhood than the edges)

Farnebäck Optical Flow

Still assuming 𝚫p is constant over the neighborhood, but not really true…

​

Farnebäck Optical Flow

Still assuming 𝚫p is constant over the neighborhood, but not really true…

​

Relax and assume instead 𝚫p is an affine function in the neighborhood.

​

Farnebäck Optical Flow

Still assuming 𝚫p is constant over the neighborhood, but not really true…

​

Relax and assume instead 𝚫p is an affine function in the neighborhood.

​

𝚫p =

​

​

a₁ + a₂x + a₃y + a₇x² + a₈xy

a₄ + a₅x + a₆y + a₇xy + a₈y²

Farnebäck Optical Flow

Still assuming 𝚫p is constant over the neighborhood, but not really true…

​

Relax and assume instead 𝚫p is an affine function in the neighborhood.

​

𝚫p =

𝚫p = Sd

​

a₁ + a₂x + a₃y + a₇x² + a₈xy

a₄ + a₅x + a₆y + a₇xy + a₈y²

S =

1 x y 0 0 0 x² xy

0 0 0 1 x y xy y²

d =

a₁

a₂

a₃

a₄

a₅

a₆

a₇

a₈

Farnebäck Optical Flow

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

​

Farnebäck Optical Flow

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

​

​

𝚺_i w_i||A_iSd - 𝚫b_i||²

​

Plug in Sd for 𝚫p.

Farnebäck Optical Flow

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

​

​

𝚺_i w_i||A_iSd - 𝚫b_i||²

​

​

​

d = 𝚺_iw_i(S_i)^T(A_i)^TS_i 𝚺_iw_i(S_i)^T(A_i)^T𝚫b_i

Plug in Sd for 𝚫p.

Least squares solve for d

^-1

Farnebäck Optical Flow

𝚺_i w_i||A_i𝚫p - 𝚫b_i||²

​

​

𝚺_i w_i||A_iSd - 𝚫b_i||²

​

​

​

d = 𝚺_iw_i(S_i)^T(A_i)^TS_i 𝚺_iw_i(S_i)^T(A_i)^T𝚫b_i

Plug in Sd for 𝚫p.

Least squares solve for d

^-1

Same inverse problem, but in practice less of an issue

Farnebäck Optical Flow

Demo