Motion & optical flow

Optical flow gives, for every pixel, the distance and direction of its move between two frames. On this page, you derive the constraint equation and see why it is under-determined. You then solve it with Lucas–Kanade and Horn–Schunck. You also learn when to use each method.

What is motion in computer vision?

In vision, motion is the apparent displacement of objects, regions or pixels between consecutive frames of a video. "Apparent" means that we see only how brightness patterns shift in the image. We do not see the real 3-D movement.

The slides give three causes of motion:

Applications: object tracking, video surveillance, autonomous driving, gesture recognition, activity recognition, video compression (motion vectors), robotics and navigation.

Optical flow

Optical flow is the pattern of apparent motion of image pixels between two consecutive frames. Each pixel has a small arrow. The set of all arrows is a motion vector field.

$$\text{flow at pixel }(x,y)=(u,v),\qquad u=\frac{dx}{dt},\; v=\frac{dy}{dt}$$

$u$ = horizontal motion (pixels per frame, positive to the right). $v$ = vertical motion (positive downward, because the image rows count downward).

Slide example. A vertical bar (three 1s) in a 5×5 image moves right by one pixel.

Frame 1:

00000
00100
00100
00100
00000

Frame 2 (object moved right by 1 pixel):

00000
00010
00010
00010
00000

The column index of the bar changes from 3 to 4, so $\Delta x=+1$ and $\Delta y=0$. The motion vector is $(u,v)=(1,0)$. The optical-flow output in the slide is a grid of → arrows. Every pixel on the object has flow $(1,0)$.

Optical flow exists only where the image has structure. The empty 0 background has no information, so a real algorithm cannot give a reliable result there. The slide draws arrows everywhere only for illustration. Optical flow is also not the same as the true motion field (the projection of the real 3-D velocity). A rotating plain sphere has a real motion field but zero optical flow.

Assumptions of optical flow

Motion estimation from two images is ill-posed, so the method makes three assumptions.

  1. Brightness constancy. A moving pixel keeps the same intensity. If a pixel goes from $(x,y,t)$ to $(x+\Delta x,\,y+\Delta y,\,t+\Delta t)$, then $$I(x,y,t)=I(x+\Delta x,\,y+\Delta y,\,t+\Delta t)$$ This assumption fails with lighting changes, shadows and specular highlights.
  2. Small motion. The displacement between frames is small (about one pixel or less), so a first-order Taylor expansion is valid.
  3. Spatial coherence. Neighbouring pixels move in a similar way, because a small neighbourhood belongs to the same object. This lets us pool equations later.

Deriving the optical flow constraint equation

Brightness constancy says the intensity does not change after the move. Expand the moved intensity with a Taylor series, then cancel the terms.

$$I(x+dx,\,y+dy,\,t+dt)\approx I+I_x\,dx+I_y\,dy+I_t\,dt$$

Brightness constancy says the left side is equal to $I(x,y,t)=I$, so the extra terms vanish:

$$I_x\,dx+I_y\,dy+I_t\,dt=0$$

Divide by $dt$ and set $u=dx/dt$ and $v=dy/dt$:

$$\boxed{I_x u+I_y v+I_t=0}\qquad\text{(optical flow constraint equation, OFCE)}$$

$I_x=\partial I/\partial x$ and $I_y=\partial I/\partial y$ are spatial image gradients. They show how fast the brightness changes across the image. $I_t=\partial I/\partial t$ is the temporal derivative. It shows the brightness change at a fixed pixel from frame to frame. You can measure all three. $u,v$ are the unknowns.

The compact vector form is $\nabla I\cdot(u,v)+I_t=0$. The motion along the gradient direction must explain the temporal change.

How to measure the derivatives. $I_x\approx\frac{I(x+1,y)-I(x-1,y)}{2}$, $I_y\approx\frac{I(x,y+1)-I(x,y-1)}{2}$, $I_t\approx I_2(x,y)-I_1(x,y)$. Smooth the image first, because derivatives amplify noise.

1-D sanity check. A brightness ramp moves right by 1 pixel. These are the row in frame 1 (x = 1..5) and in frame 2:

1020304050
010203040

At $x=3$: $I_x=(40-20)/2=10$. $I_t=I_2-I_1=20-30=-10$. In 1-D, the OFCE is $I_x u+I_t=0$, so $u=-I_t/I_x=-(-10)/10=1$. This is the same as the true motion of 1 pixel to the right.

The 1-pixel-wide bar in the slide is a bad test. The bar is as wide as the motion, so the small-motion (Taylor) assumption fails. For this reason, real systems blur the image or use pyramids.

The aperture problem

The OFCE is one equation with two unknowns $(u,v)$ for each pixel, so $(u,v)$ is not unique. This is the aperture problem.

Look at a long straight edge through a small circular hole (the aperture). You see the edge move perpendicular to itself. You cannot see any sliding along the edge. The true motion can be many things. You get only the component along the gradient (the normal flow).

Through the aperture: edge seems to move perpendicular visible normal flow Solutions of one equation form a line uv Ixu + Iyv = -It every point on the line fits
Left: through a small aperture only motion perpendicular to the edge is visible. Right: in the $(u,v)$ plane one equation gives a whole line of solutions.

Numerical (normal flow). At one pixel, $I_x=2$, $I_y=3$ and $I_t=-6$. The OFCE is $2u+3v=6$.

Many answers work: $(3,0)$, $(0,2)$, $(1.5,1)$. The normal flow is the unique solution with the smallest magnitude. It is along the gradient direction:

$$(u,v)_{\perp}=-\frac{I_t}{\|\nabla I\|^2}\nabla I=\frac{6}{2^2+3^2}(2,3)=\left(\tfrac{12}{13},\tfrac{18}{13}\right)\approx(0.92,\,1.38)$$

Check: $2(0.923)+3(1.385)=6$. Speed $=|I_t|/\|\nabla I\|=6/\sqrt{13}\approx1.66$.

To solve the problem, add more constraints. Lucas–Kanade assumes that a neighbourhood moves together. Horn–Schunck assumes that the flow is smooth.

Sparse versus dense optical flow

Sparse optical flowDense optical flow
Where is motion estimatedOnly at selected feature points (Harris, Shi–Tomasi corners, SIFT keypoints)At every pixel
AdvantagesFast, less memoryComplete motion field
Typical usesTracking, SLAMVideo analysis, human action recognition
Example methodsLucas–Kanade, pyramid LKHorn–Schunck, Farneback, RAFT/FlowNet

Lucas–Kanade method

Lucas–Kanade is one of the most popular optical flow methods. Idea: all neighbouring pixels in a small window (for example 5×5, so $n=25$ pixels) have the same $(u,v)$. Do not use the single equation $I_xu+I_yv=-I_t$. Write one equation for each pixel, then solve the stacked system by least squares.

$$\underbrace{\begin{bmatrix}I_{x1}&I_{y1}\\I_{x2}&I_{y2}\\\vdots&\vdots\\I_{xn}&I_{yn}\end{bmatrix}}_{A\ (n\times2)}\underbrace{\begin{bmatrix}u\\v\end{bmatrix}}_{\mathbf d}=\underbrace{\begin{bmatrix}-I_{t1}\\-I_{t2}\\\vdots\\-I_{tn}\end{bmatrix}}_{\mathbf b}$$ $$A^TA\,\mathbf d=A^T\mathbf b\;\Rightarrow\;\begin{bmatrix}u\\v\end{bmatrix}=\begin{bmatrix}\sum I_x^2&\sum I_xI_y\\\sum I_xI_y&\sum I_y^2\end{bmatrix}^{-1}\begin{bmatrix}-\sum I_xI_t\\-\sum I_yI_t\end{bmatrix}$$

The sums run over the window. There are $n>2$ equations and 2 unknowns, so the system is over-determined. Minimise $\sum(I_xu+I_yv+I_t)^2$. $A^TA$ is the same matrix as in Harris corner detection.

Worked LK solve. A window has four pixels. The table shows their gradients and temporal derivatives (noisy measurements):

pixel$I_x$$I_y$$I_t$$b=-I_t$
110-22
201-11
311-33
421-44

Step 1: $\sum I_x^2=1+0+1+4=6$, $\sum I_y^2=0+1+1+1=3$, $\sum I_xI_y=0+0+1+2=3$.

Step 2: $\sum I_xb=2+0+3+8=13$, $\sum I_yb=0+1+3+4=8$.

Step 3: Solve $\begin{bmatrix}6&3\\3&3\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix}=\begin{bmatrix}13\\8\end{bmatrix}$. $\det=6\cdot3-3\cdot3=9$.

$$u=\frac{3\cdot13-3\cdot8}{9}=\frac{15}{9}=1.67,\qquad v=\frac{-3\cdot13+6\cdot8}{9}=1$$

The flow is $(u,v)\approx(1.67,\,1)$. Check pixel 4: $2(1.67)+1(1)=4.33\approx4$. The residual is small, as expected with noise.

When does LK work? $A^TA$ must be invertible and well conditioned. Check its eigenvalues $\lambda_1\ge\lambda_2$:

Window contentEigenvaluesResult
Flat regionboth smallno flow information
Edgeone large, one smallaperture problem, only normal flow
Corner / textureboth largereliable $(u,v)$

For this reason, LK is used on corner features (Harris, Shi–Tomasi). This makes it sparse and fast, and it is popular for tracking.

Horn–Schunck method

Idea: the flow field changes smoothly over the whole image. Minimise a global energy that balances data fit and smoothness.

$$E=\iint\Big[(I_xu+I_yv+I_t)^2+\lambda\big(|\nabla u|^2+|\nabla v|^2\big)\Big]\,dx\,dy$$

The first term is the violation of the OFCE (data term). $|\nabla u|^2+|\nabla v|^2$ shows how much the flow changes between neighbours (smoothness term). $\lambda$ controls the smoothness. A large $\lambda$ gives a very smooth flow. A small $\lambda$ trusts the data more.

Characteristics: the flow is dense. Every pixel has a vector, even in flat areas, where the smoothness term copies the flow from the neighbours. The method is more expensive to compute (it is iterative), and it blurs motion boundaries.

Extra practice (one iterative update, textbook form). The minimum of $E$ gives the update $$u^{k+1}=\bar u^k-\frac{I_x(I_x\bar u^k+I_y\bar v^k+I_t)}{\lambda+I_x^2+I_y^2},\qquad v^{k+1}=\bar v^k-\frac{I_y(I_x\bar u^k+I_y\bar v^k+I_t)}{\lambda+I_x^2+I_y^2}$$ where $\bar u,\bar v$ are the average flow of the neighbours. Take $I_x=2$, $I_y=1$, $I_t=-5$ and $\lambda=1$. Start with $\bar u=\bar v=0$.

Residual $=2(0)+1(0)-5=-5$. Denominator $=1+4+1=6$. $u=0-2(-5)/6=1.67$, $v=0-1(-5)/6=0.83$. After the update, the residual is $2(1.67)+0.83-5=-0.83$, which is much smaller. If you repeat the update with new neighbour averages, it converges.

Farneback optical flow

Farneback is a dense algorithm in OpenCV. Idea: approximate the neighbourhood of each pixel with a polynomial (quadratic) expansion in both frames. Find the displacement from the change in the polynomial coefficients. Advantages: dense motion field, good accuracy, real-time capable.

Pyramid optical flow

Problem: basic Lucas–Kanade needs small motion (about 1 pixel). A fast object that moves 16 pixels breaks the Taylor assumption. Solution: build an image pyramid (blur and halve the image again and again) and go from coarse to fine.

Level 3: small image (start here) Level 2 Level 1 Level 0: original image (finish here) flow x2 and refine
Coarse levels turn big motion into small motion; each finer level refines the estimate.

Numerical. The true displacement is 16 pixels, with 4 levels (0 to 3). At level $L$, the displacement is $16/2^L$: level 1 gives 8, level 2 gives 4 and level 3 gives 2 pixels. This is still too big at level 3 for a 1-pixel limit, so use more levels (5 levels give 1 pixel). Procedure:

  1. Estimate the flow at the top level (about 1 pixel).
  2. Upsample the flow by 2. The flow vectors double also.
  3. Warp the next finer image with the flow.
  4. Estimate the small residual flow and add it.
  5. Repeat down to level 0.

Advantages: it handles large displacement and is more robust.

Comparison of the major methods

MethodSparse / denseSpeedLarge motionAccuracy
Lucas–KanadeSparseHighModerateGood
Pyramid Lucas–KanadeSparseHighGoodBetter
Horn–SchunckDenseLowModerateGood
FarnebackDenseMediumGoodVery good
Deep learning (RAFT, FlowNet)DenseHigh (on GPU)ExcellentExcellent

Lucas–Kanade versus Horn–Schunck

Lucas–KanadeHorn–Schunck
Extra assumptionConstant flow inside a local windowSmooth flow over the whole image
ScopeLocalGlobal
SolverLeast squares, 2×2 systemIterative energy minimisation
OutputSparse (reliable only at corners)Dense
Cost, noiseFast, robust to noiseExpensive, more sensitive

Quick self-test

1. State the three assumptions of optical flow.

Brightness constancy: a moving pixel keeps its intensity. Small motion: the Taylor expansion holds. Spatial coherence: neighbouring pixels move together.

2. Derive the optical flow constraint equation.

Start from $I(x,y,t)=I(x+dx,y+dy,t+dt)$. Expand the right side to first order with a Taylor series: $I+I_xdx+I_ydy+I_tdt$. Cancel $I$ to get $I_xdx+I_ydy+I_tdt=0$. Divide by $dt$ and set $u=dx/dt$ and $v=dy/dt$ to get $I_xu+I_yv+I_t=0$.

3. What is the aperture problem and how is it resolved?

The aperture problem is that each pixel has one equation and two unknowns $(u,v)$. The flow is not unique. Only the component along the gradient (normal flow) is observable. To resolve it, add constraints. Lucas–Kanade pools many pixels in a window (least squares). Horn–Schunck adds a global smoothness term.

4. A pixel has $I_x=4$, $I_y=0$, $I_t=-8$. What is the flow?

$4u+0\cdot v-8=0\Rightarrow u=2$. Here $I_y=0$ means a vertical edge, and the normal flow is purely horizontal. $v$ is undetermined (aperture problem), so $(u,v)=(2,?)$. The normal flow is $(2,0)$.

5. Solve LK for the window: $(I_x,I_y,I_t)=(1,0,-1)$, $(0,1,-2)$, $(1,1,-3)$.

$\sum I_x^2=2$, $\sum I_y^2=2$, $\sum I_xI_y=1$; $\sum I_xb=1+3=4$, $\sum I_yb=2+3=5$ (with $b=-I_t=1,2,3$). Solve $\begin{bmatrix}2&1\\1&2\end{bmatrix}\mathbf d=\begin{bmatrix}4\\5\end{bmatrix}$: $\det=3$, $u=(2\cdot4-1\cdot5)/3=1$, $v=(2\cdot5-1\cdot4)/3=2$. The flow is $(1,2)$. It fits all three equations exactly.

6. Why is Lucas–Kanade fast but sparse, while Horn–Schunck is dense but slow?

LK solves a small 2×2 system for each window. It is reliable only where $A^TA$ is well conditioned (corners), so it is applied at features. Horn–Schunck minimises a global energy iteratively over every pixel. The smoothness term propagates the flow into textureless regions. The result is dense but expensive.

7. How does the pyramid approach handle large motion?

Each pyramid level halves the resolution, so a displacement $d$ becomes $d/2^L$ at level $L$. Estimate the flow at the coarsest level, where the motion is small. Upsample it (times 2) to the next level as an initial guess, then refine it. Continue in this way down to the original image.

8. Differentiate sparse and dense optical flow with examples.

Sparse flow is only at selected feature points (Harris, Shi–Tomasi, SIFT). It is fast, uses low memory and is used in tracking and SLAM, for example Lucas–Kanade. Dense flow is at every pixel. It gives a complete motion field and is used in video analysis and action recognition, for example Horn–Schunck, Farneback and RAFT.

9. In Horn–Schunck what does $\lambda$ do?

It weights the smoothness term. A large $\lambda$ gives smoother flow, but it blurs motion boundaries and ignores the data. A small $\lambda$ follows the brightness-constancy data closely, but the flow is noisier.