
Lecture 10
Computer Science Department, Colorado School of Mines
By the end of this lecture, you should be able to:
| 1. Image Filtering | \(\displaystyle y[m,n]=\sum_{k,l} h[k,l]\,I[m+k,n+l]\) |
| 2. Optical Flow | \(\displaystyle I(x,y,t)=I(x+\Delta x,\ y+\Delta y,\ t+\Delta t)\) |
| 3. Camera Geometry | \(\displaystyle \mathbf{x}=\mathbf{K}\begin{bmatrix}\mathbf{R}&\mathbf{t}\end{bmatrix}\mathbf{X} \qquad \mathbf{x}^{T}\mathbf{F}\mathbf{x}'=0\) |
| 4. Machine Learning | \(\displaystyle \underset{\mathcal{S}}{\operatorname{arg\,min}}\sum_{i=1}^{k}\sum_{\mathbf{x}\in S_i}\left\lVert\mathbf{x}-\boldsymbol{\mu}_i\right\rVert^{2} \qquad y=\varphi\!\left(\mathbf{w}^{T}\mathbf{x}+b\right)\) |
Optical flow describes the apparent motion of image points between video frames.
A point at \((x,y)\) moves to \((x+u,y+v)\), giving a displacement vector \((u,v)\).

Note: Image coordinates increase to the right and downward.

Only a subset of the dense field’s arrows is displayed for readability.
Optical flow is often displayed using arrows or colors.

jason@heqingele.com; pexels
Rainer Hessmer
Liu & Sun, CVPR 2011; TPAMI 2014
Google Pixel 6: Face Unblur
Can we estimate optical flow by detecting SIFT features and matching them between frames?
Can we estimate motion directly from changes in image intensity, without detecting and matching keypoints?
What stays the same as a point moves between frames?

Rearrange brightness constancy and apply a first-order Taylor expansion:
\[ \begin{aligned} 0 &= I(x+u,y+v,t+1) - I(x,y,t)\\[2pt] &\approx I(x,y,t) + I_x u + I_y v + I_t - I(x,y,t)\\[2pt] &= I_x u + I_y v + I_t\\[2pt] &= \nabla I \cdot [u,\ v]^T + I_t \end{aligned} \]
Optical Flow Equation
\[ I_x u + I_y v + I_t = 0 \]
When is this approximation bad? When \(u\) or \(v\) is large compared with how smoothly the image varies.
What do static image gradients have to do with motion?


Pixel values: black = 0, white = 1. Derivatives use forward differences.
\[I_x = 1,\qquad I_y = 0,\qquad I_t = 1\]
\[I_x u + I_y v + I_t = 0\] \[\Rightarrow\; 1\,u + 0\,v + 1 = 0\]
If Lucas–Kanade window sees only a straight edge, many different motions look the same:
Given \(I_x, I_y, I_t\), can we uniquely recover \((u,v)\) from the optical flow equation \(I_x u + I_y v + I_t = 0\)?

\[ \underbrace{\begin{bmatrix} I_x(p_1) & I_y(p_1)\\ \vdots & \vdots\\ I_x(p_{25}) & I_y(p_{25}) \end{bmatrix}}_{A\ (25\times2)} \underbrace{\begin{bmatrix} u\\ v \end{bmatrix}}_{\mathbf d\ (2\times1)} = \underbrace{-\begin{bmatrix} I_t(p_1)\\ \vdots\\ I_t(p_{25}) \end{bmatrix}}_{\mathbf b\ (25\times1)} \]
B. Lucas and T. Kanade, “An iterative image registration technique with an application to stereo vision,” IJCAI, 1981.

Frame 2 is a synthetic shift of image by \((u,v)=(0.6,-0.4)\) px.
Least squares:
\[ A^TA\,\mathbf d = A^T\mathbf b \quad\Rightarrow\quad \mathbf d = (A^TA)^{-1}A^T\mathbf b \]
Summing over the pixels in the window:
\[ \underbrace{\begin{bmatrix} \sum I_xI_x & \sum I_xI_y\\ \sum I_xI_y & \sum I_yI_y \end{bmatrix}}_{A^TA} \begin{bmatrix} u\\ v \end{bmatrix} = \underbrace{-\begin{bmatrix} \sum I_xI_t\\ \sum I_yI_t \end{bmatrix}}_{A^T\mathbf b} \]

The \(v\) axis points down, as in image coordinates.

Orange dots: estimates from 40 frame pairs with independent noise. Green star: known shift. At the edge, \(u\) is accurate but \(v\) is not.
Lucas–Kanade (one window)
Simplified implementation:
def lucas_kanade_window(frame1, frame2, x, y, half_size=2, min_eigenvalue=100):
gradient_x, gradient_y = image_gradients(frame1)
temporal_change = frame2 - frame1
window = np.s_[y-half_size:y+half_size+1, x-half_size:x+half_size+1]
Ix, Iy, It = gradient_x[window], gradient_y[window], temporal_change[window]
ATA = np.array([[np.sum(Ix*Ix), np.sum(Ix*Iy)],
[np.sum(Ix*Iy), np.sum(Iy*Iy)]])
ATb = -np.array([np.sum(Ix*It), np.sum(Iy*It)])
if np.linalg.eigvalsh(ATA)[0] < min_eigenvalue:
return None
return np.linalg.solve(ATA, ATb)
Synthetic horizontal shifts of the street image; median estimate over the most textured \(5\times5\) windows.

Coarse-to-Fine Lucas–Kanade
Warping uses the current flow estimate \((u_0,v_0)\) to resample frame 2, pulling each pixel back by the motion already found: \[ I_2^{\text{warped}}(x,y) = I_2(x+u_0,\ y+v_0) \]

Same synthetic shifts as before. At the coarsest of 3 levels, an 8 px shift becomes 2 px.
qualityLevel: keep points whose smaller eigenvalue is at least 1% of the strongest one.minDistance: minimum spacing between points (pixels).blockSize: window size used to form \(A^TA\).J. Shi and C. Tomasi, “Good Features to Track,” CVPR, 1994.
OpenCV: Shi–Tomasi Corner Detector.

winSize: the Lucas–Kanade window at each pyramid level.maxLevel: number of pyramid levels above the original (0 = no pyramid).status: 1 if the point was tracked; keep only those.displacement: \((u,v)\) for each retained point.[:, 0] gives an \((N,2)\) array of coordinates.
Frames 100 → 101, zoomed to the walkers. Arrows are drawn 5× longer than the displacement; yellow points moved ≤ 1 px.
import cv2
import numpy as np
GREEN, RED = (0, 255, 0), (0, 0, 255) # OpenCV colors are BGR
def track_points(gray1, gray2, points):
# Lucas-Kanade from gray1 to gray2, then back to gray1.
next_points, status, error = cv2.calcOpticalFlowPyrLK(
gray1, gray2, points, None, winSize=(15, 15), maxLevel=3)
back_points, back_status, _ = cv2.calcOpticalFlowPyrLK(
gray2, gray1, next_points, None, winSize=(15, 15), maxLevel=3)
# Keep points found in both directions that came back within 1 px.
returned = np.linalg.norm(points - back_points, axis=1) < 1
tracked = (status.ravel() == 1) & (back_status.ravel() == 1) & returned
return next_points, tracked
video = cv2.VideoCapture("vtest.avi")
tracks = [] # one track per point: its list of (x, y) positions
gray1 = None
frame_count = 0
while True:
ok, frame = video.read()
if not ok: # end of the video
break
gray2 = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
# Move each track's latest point to gray2; keep its last 10 positions.
if gray1 is not None and tracks:
points = np.float32([track[-1] for track in tracks])
next_points, tracked = track_points(gray1, gray2, points)
tracks = [(track + [point])[-10:] for track, point, keep
in zip(tracks, next_points, tracked) if keep]
# Every 10 frames, add new points at least 10 px from those already tracked.
if frame_count % 10 == 0:
mask = np.full(gray2.shape, 255, np.uint8)
for track in tracks:
cv2.circle(mask, np.int32(track[-1]), 10, 0, -1)
corners = cv2.goodFeaturesToTrack(gray2, maxCorners=300, qualityLevel=0.01,
minDistance=10, blockSize=7, mask=mask)
tracks += [[point] for point in corners[:, 0]]
# Draw tails (green) and current positions (red).
for track in tracks:
cv2.polylines(frame, [np.int32(track)], False, GREEN, 2, cv2.LINE_AA)
cv2.circle(frame, np.int32(track[-1]), 2, RED, -1, cv2.LINE_AA)
cv2.imshow("Lucas-Kanade tracking", frame)
if cv2.waitKey(100) == 27: # 100 ms per frame (10 fps); Esc quits
break
gray1 = gray2
frame_count += 1
video.release()
cv2.destroyAllWindows()
flow has shape (height, width, 2): flow[y, x] \(=(u,v)\) at every pixel.pyr_scale: scale factor between pyramid levels.levels: total number of levels, including the original image.winsize: averaging window; larger is smoother and more robust to noise, but blurs motion boundaries.iterations: refinements per pyramid level.poly_n, poly_sigma: neighborhood size and smoothing for the polynomial fit.
Hue: direction; saturation: magnitude, saturating at 5 px. White means no motion.
ULTRAFAST, FAST, MEDIUM) trade accuracy for speed.
Hue: direction; saturation: magnitude, saturating at 5 px. White means no motion.
import cv2
import numpy as np
def flow_to_bgr(flow, max_flow=5):
# Hue: direction. Saturation: magnitude. White: no motion.
magnitude, angle = cv2.cartToPolar(
flow[..., 0], flow[..., 1], angleInDegrees=True)
hsv = np.zeros(flow.shape[:2] + (3,), np.uint8)
hsv[..., 0] = angle / 2
hsv[..., 1] = np.clip(255 * magnitude / max_flow, 0, 255)
hsv[..., 2] = 255
return cv2.cvtColor(hsv, cv2.COLOR_HSV2BGR)
video = cv2.VideoCapture("vtest.avi")
dis = cv2.DISOpticalFlow_create(cv2.DISOPTICAL_FLOW_PRESET_MEDIUM)
_, previous = video.read()
gray1 = cv2.cvtColor(previous, cv2.COLOR_BGR2GRAY)
while True:
ok, current = video.read()
if not ok:
break
gray2 = cv2.cvtColor(current, cv2.COLOR_BGR2GRAY)
farneback = cv2.calcOpticalFlowFarneback(
gray1, gray2, None, pyr_scale=0.5, levels=3, winsize=15,
iterations=3, poly_n=5, poly_sigma=1.2, flags=0)
dis_flow = dis.calc(gray1, gray2, None)
# Forward flow is defined at pixels in the previous frame.
cv2.imshow("Video", previous)
cv2.imshow("Farneback", flow_to_bgr(farneback))
cv2.imshow("DIS", flow_to_bgr(dis_flow))
previous, gray1 = current, gray2
if cv2.waitKey(100) == 27: # Esc quits.
break
video.release()
cv2.destroyAllWindows()
| Method | Function | Output | Module |
|---|---|---|---|
| Pyramidal Lucas–Kanade | cv2.calcOpticalFlowPyrLK |
Sparse | main |
| Farnebäck | cv2.calcOpticalFlowFarneback |
Dense | main |
| DIS | cv2.DISOpticalFlow_create |
Dense | main |
| Dual TV-L1 | cv2.optflow.DualTVL1OpticalFlow_create |
Dense | contrib |
| DeepFlow | cv2.optflow.createOptFlow_DeepFlow |
Dense | contrib |
| Sparse-to-dense | cv2.optflow.calcOpticalFlowSparseToDense |
Dense | contrib |
| Robust local flow (RLOF) | cv2.optflow.calcOpticalFlowSparseRLOF, cv2.optflow.calcOpticalFlowDenseRLOF |
Both | contrib |
contrib methods require OpenCV built with the contrib modules.When Is Motion Reliable?
Flat regions provide little motion information; a straight edge reveals only motion normal to the edge. Corners and texture help resolve both components, but lighting changes, occlusion, and large motion can still cause errors.
Computer Vision; Colorado School of Mines | Kaveh Fathian