Transcript *** 1

Optical Flow
Optical Flow
• Distribution of apparent velocities of
movement of brightness pattern in an image
Optical Flow
• Perspective projection (pinhole camera)
• Instantaneous 2D velocity
Definitions
The optical flow is a velocity field in the image which
transforms one image into the next image in a sequence
[
Horn&Schunck ]
+
frame #1
=
flow field
frame #2
The motion field … is the projection into the image of
three-dimensional motion vectors [ Horn&Schunck ]
4
Ambiguity of optical flow
flow (2)
flow (1): true motion
Frame 1
5
Determining Optical Flow
Berthold K.P. Horn and Brian G. Rhunck
Artificial Intelligence Laboratory, MIT.
Optical Flow
• Optical flow field: Estimate the 2D motion field, which are
the 2D velocities for all visible points
• Two key problems
– Determine what image property to track
– Determine how to track it
Brightness Constancy
I ( x  u, y  v, t  1)  I ( x, y, t )  0
( x  u , y  v, t  1)
( x, y , t )
u
frame t+1
v
frame t
8
Brightness Constancy
• Track points of constant brightness, assuming
that surface radiance is constant over time
I ( x, y, t  1)  I ( x  u1, y  u2 , t )
• Brightness constancy is often violated by Mother
Nature, so the resulting optical flow field is
sometimes a very poor approximation to the 2D
motion field
Optical Flow
• The optical flow cannot be computed at a
point independently of neighboring points
without introducing additional constraints
Brightness Constancy Constraint
• The brightness of a particular point in the pattern is
v
constant
E dx E dy E


0
x dt y dt t
dE
0
dt
u
dx
dt
v
dy
dt
Exu  E y v  Et  0
Et
( Ex , E y )
u
• Cannot determine the flow velocity
Constraint line
(u, v) locally without additional constraints
Brightness Constancy Constraint
• Normal Velocity
• No constraint when the gradient magnitude is
zero
Optical Flow Assumptions:
13
* Slide from Michael Black, CS143 2003
Optical Flow Assumptions:
14
* Slide from Michael Black, CS143 2003
Smoothness Constraint
• Constraint Assumption
– Neighboring points on the objects have similar
velocities and
– The velocity field of the brightness patterns in the
image varies smoothly almost everywhere
– Discontinuities in flow can be expected where one
object occludes another
• Algorithms based on smoothness constraint are
likely to have difficulties with occluding edges
Smoothness Constraint
• Minimize the square of the gradient
magnitude of the optical flow velocity
 u   u 
   
 x   y 
2
2
 v   v 
   
 x   y 
2
2
• Sum of the squares of Laplacians of x- and ycomponents of the flow
2
2

u

u
 2u  2  2
x y
 2v  2v
 v 2  2
x y
2
Estimate the Partial Derivatives
Estimate the Laplacian of Flow Velocities
Minimization
• Minimize the sum of errors in rate of change of
image brightness
• And measure of departure from smoothness
• Total error to be minimized
Minimization
• Good (u,v) occurs at
Difference of Flow from Local Average
Exu  E y v  Et  0
• (u,v) lies in the direction towards
the constraint line along a line
that perpendicular to it
• a^2 plays significant role when Ex,
Ey is small: roughly equal to the
expected noise in the estimate of
Iterative Solution
Optical Flow: 1D Case
Brightness Constancy Assumption:
{
f (t )  I ( x(t ), t )  I ( x(t  dt ), t  dt )
f ( x )
0
t
I  x  I


x t  t  t
Ix
v
Because no change in brightness with time
0
x(t )
It
It
v 
Ix
24
Tracking in the 1D case:
I ( x, t ) I ( x, t  1)
p

v ?
x
25
Tracking in the 1D case:
I ( x, t ) I ( x, t  1)
It
Temporal derivative
p

v
x
Ix
Spatial derivative
I
Ix 
x t
I
It 
t
x p

I
v  t
Ix
Assumptions:
• Brightness constancy
• Small motion
26
Tracking in the 1D case:
Iterating helps refining the velocity vector
I ( x, t ) I ( x, t  1)
Temporal derivative at 2nd iteration
It
p
x
Ix
Can keep the same estimate for spatial derivative


I
v  v previous  t
Ix
Converges in about 5 iterations
27
Algorithm for 1D tracking:
For all pixel of interest p:
 Compute local image derivative at p:
Ix

 Initialize velocity vector:
v 0
 Repeat until convergence:

 Compensate for current velocity vector:
I ' ( x, t  1)  I ( x  v , t  1)
I t  I ' ( p, t  1)  I ( p, t )
 Compute temporal derivative:

 I
 Update velocity vector:
v v t
Ix
Requirements:
 Need access to neighborhood pixels round p to compute
Ix
 Need access to the second image patch, for velocity compensation:
 The pixel data to be accessed in next image depends on current velocity
estimate (bad?)
 Compensation stage requires a bilinear interpolation (because v is not integer)
 The image derivative I needs to be kept in memory throughout the iteration
x
process
28
Iterative Solution
• Very costly to solve these equations simultaneously
• Iterative algorithms, such as Gauss-Seidel method
It is interesting to note that the new estimates at a particular
point do not depend directly on the previous estimate at the
same point
Fill in Uniform Region
• Uniform region: brightness gradient is zero
Exu  E y v  Et  0
• No local information to constrain the vecocity
• Fill in uniform region
– Given the values on region boudnary
– Solve the Laplace equation under Dirichlet
boundary condition
2
min  f with
f

f |  f * |
Tightness of Constraint
• In general, the solution is most accurately
determined in the region where the
brightness is not too small and varies in
direction from point to point
– Constraint information is available in a relative
small neighborhood
Choice of Iterative Scheme
• How to interlace the iterations with the time
step?
– Get stable values before going to next frame
– Only one iteration per time-step gives good initial
guess
• Ability to deal with more images per unit time
• Better estimation in uniform regions because of the
noise in measurements of images will be independent
and tend to cancel out
Experiment
• Very low resolution video,
say, 32*32
• A rotating ball with
smoothly varying
patterns, but no shading
Results I
•
•
•
•
Simple linear translation of the entire pattern
Estimate between two images
Showing the velocity
Few changes occur after 32 iterations when
errors ~ 10%
Results I
1 time step
4 time steps
Results I
16 time steps
64 time steps
Results II
• Only one iteration per time-step
• More rapid
• Few changes after 16 iteration when errors ~
7%
Results II
1 time steps
4 time steps
Results II
16 time steps
64 time steps
Results III
• Simple rotation and contraction of the
brightness pattern
Result III
initial
32 time steps
Result IV
• Rigid body motion
– Laplacian for one of the velocity components
becomes infinite on the occluding bound
– Reasonable results are still obtained with finite
velocities
Results IV
Rotating cylinder
Rotating sphere
Results IV
Exact flow pattern for a rotating cylinder and rotating sphere
Summary
• A method for computing optical flow from a
sequence of images
• Two components of flow velocity
• Additional constraint: smoothness
• Iterative method
Optical Flow Research: Timeline
Horn&Schunck
Lucas&Kanade
more
methods
many
methods
1981
1992
1998
Seminal papers
Benchmark:
Barron et.al.
Benchmark:
Galvin et.al.
now
A slow and not very consistent improvement in results,
but a lot of useful ingredients were developed
46
http://people.csail.mit.edu/celiu/ECCV2008/z`z`