M6-T2 — Feature Detection and Tracking

Learning objectives

After this lesson, you should be able to:

• Compare detect-and-match with optical-flow tracking: cost, accuracy and failure modes.
• Apply the ratio test and the forward-backward check and say what each rejects.
• Solve the Lucas-Kanade equation for a small displacement and state its assumptions.
• Compute how many RANSAC iterations a given inlier ratio requires.

The problem and the intuition

Imagine a photo album of a trip taken every second. To work out how you moved between two photos you pick a few landmarks (a church tower, a tree) and find them in both. There are two ways. You can write a description of each landmark and search the next photo for the closest description (match). Or, since the next photo was taken only a second later, you can look near where the landmark was and follow it (track). Matching can find a point after a long gap or a big motion; tracking is quicker and more precise for small motion, and does not need descriptors.

Both produce some wrong pairs: a repeated window, a leaf that moved, a reflection. Wrong pairs are far more damaging than noisy ones, because a least-squares estimator treats a gross error as data. Rejecting them (ratio test, back-check, geometric verification) is part of the front end, not an afterthought.

Correspondence quality decides visual SLAM quality. A hundred correct matches beat a thousand with ten percent wrong ones, unless the wrong ones are removed.

The algorithms: matching, tracking, verification

Problem. Given images I₁ and I₂ of a static scene from nearby viewpoints, produce a set of pixel pairs (p₁, p₂) that observe the same 3D point, with as few wrong pairs as possible.

Assumptions. Brightness constancy (a point has the same intensity in both images), small motion between frames for tracking, a mostly static scene, and enough texture. The geometric verification assumes a rigid scene viewed by one camera.

Detect and match

1. Detect and describe. Run a detector (FAST, Shi-Tomasi, ORB) in each image, with a grid so that points are spread out, and compute a descriptor for each (M6-T1).
2. Nearest neighbour. For each descriptor in image 1, find the closest descriptor in image 2 by Hamming (binary) or Euclidean (float) distance. Brute force costs O(n₁n₂); approximate search or a restriction to a window around a predicted position makes it faster.
3. Ratio test (Lowe, 2004). Accept the match only if d₁ / d₂ < ρ (typically 0.7 to 0.8), where d₁ and d₂ are the distances to the best and second-best candidates. A true match is much closer than any other; a point on a repeated texture has several nearly-equal candidates and fails the test.
4. Cross-check. Optionally require that the match is mutual: the best match of the match is the original.

Optical-flow tracking (Lucas-Kanade)

Brightness constancy says I(p + d, t+1) = I(p, t). Linearise for small d: I_x d_x + I_y d_y = −I_t. One equation, two unknowns, so Lucas and Kanade (1981) assume the displacement is the same over a window W and solve the least-squares problem:

G is the same structure tensor as the Harris matrix: the tracker is solvable exactly where the feature is a good corner (both eigenvalues large). Large motion violates the linearisation, so the standard remedy is a pyramid (Bouguet, 2001): track coarsely at low resolution, then refine at each finer level, iterating the step several times per level.

Rejecting wrong correspondences

• Forward-backward check. Track from image 1 to 2 and back to 1; keep the point if it returns within about 1 px of its start.
• Status and error. Drop points that leave the image, whose window residual is large, or whose G has a small eigenvalue.
• Geometric verification with RANSAC (Fischler and Bolles, 1981). Repeatedly draw the minimal sample needed for a model (5 points for the essential matrix, 8 for the fundamental, M6-T3), fit it, and count the pairs consistent with it. Keep the model with most inliers and discard the rest. The number of iterations N needed to draw at least one all-inlier sample with probability p when the inlier ratio is w and the sample size is s is N = log(1 − p) / log(1 − w^s).

d

displacement of a feature between two images (pixels).

G

structure tensor over the window; the tracker is well-posed where its smaller eigenvalue is large.

ρ

ratio-test threshold on the best-to-second-best distance.

w, s, p

inlier ratio, RANSAC sample size, desired success probability.

Strengths, limitations, failure modes

A worked example: ratio test, one Lucas-Kanade step, RANSAC iterations

1. Ratio test. A feature has a best match at Hamming distance 28 and a second best at 52. Ratio 28 / 52 = 0.54 < 0.8: accept. Another has 40 and 46, ratio 0.87 > 0.8: reject, because two candidates are almost equally good (probably a repeated pattern).
2. One Lucas-Kanade step. Over a window, suppose G = [[40, 10], [10, 30]] and e = (20, 5). det G = 40 × 30 − 10 × 10 = 1100, G⁻¹ = (1/1100) [[30, −10], [−10, 40]]. Then d = (1/1100) (30 × 20 − 10 × 5, −10 × 20 + 40 × 5) = (550, 0) / 1100 = (0.5, 0) px. The feature moved half a pixel to the right. If G were [[40, 0], [0, 0.1]] (an edge), the second equation would have e/G enormous and the vertical displacement would be unreliable: the aperture problem.
3. Forward-backward error. Track the point 0.5 px forward and it returns 0.45 px back: the error is 0.05 px, accept. A point that jumps onto a neighbouring leaf and returns 6 px from its start is rejected.
4. RANSAC iterations. To estimate the essential matrix (s = 5) with probability p = 0.99 of at least one clean sample: with 50% inliers, N = ln 0.01 / ln(1 − 0.5⁵) = 4.605 / 0.0317 = 145 iterations. With 70% inliers, only 25. With the 8-point algorithm (s = 8) and 50% inliers it is 1177. That is why the 5-point solver is preferred and why the quality of the front end (the inlier ratio) directly sets the cost.
5. Track loss. A robot turns quickly: the image moves 80 px between frames. A 21 × 21 window with one pyramid level cannot follow it, but with three levels the coarsest level sees only 10 px of motion and recovers. Add motion blur, and the gradients inside the window vanish; G becomes small and the tracker returns noise. This is the failure that the first lab reproduces.

Engineering implications and limitations

Engineering implications

• Use a pyramid and a prior. Initialise the tracker from an IMU or constant-velocity prediction so that the search is short (M6-T6).
• Replenish features. Tracks die. Keep a minimum count (for example 150) and detect new points in cells without any, so that coverage is maintained.
• Always verify geometrically. RANSAC on an essential or fundamental matrix, or a PnP-based check against the map, before any match reaches the estimator.
• Tune the ratio test to the scene. Textured outdoor scenes tolerate 0.8; repetitive indoor scenes need 0.6–0.7.
• Watch exposure and blur. Log the number of tracked features per frame; a sudden drop is the first sign of a lighting change or fast motion.
• Constrain the search. Projecting map points with the predicted pose and searching only a small window around the prediction is faster and avoids many wrong matches (ORB-SLAM does this; M6-T5).

Limits

Brightness constancy is false for specular surfaces, automatic exposure changes and shadows. Short-baseline tracking accumulates drift along long tracks. Matching cannot distinguish a true repeat from an aliased one without extra evidence. A learned front end (SuperPoint with SuperGlue or LightGlue) is more robust but needs a GPU and its failures are harder to predict.

Common misconceptions

Engineering takeaways

1. Correspondences come from matching descriptors or tracking with optical flow; both need outlier rejection.
2. The ratio test rejects ambiguous matches; the forward-backward check rejects unstable tracks; RANSAC enforces the geometry.
3. Lucas-Kanade solves G d = e over a window and is well-posed exactly where the window contains a corner.
4. RANSAC cost grows steeply as the inlier ratio falls and as the sample size grows.
5. Blur, textureless regions, repeated texture and brightness change are the main sources of failed correspondences.

References and further reading

Primary papers and authoritative documentation.

• Lucas, B. D. and Kanade, T. (1981). An iterative image registration technique with an application to stereo vision. IJCAI.
• Bouguet, J.-Y. (2001). Pyramidal implementation of the affine Lucas Kanade feature tracker: description of the algorithm. Intel Corporation.
• Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2).
• Fischler, M. A. and Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM 24(6).
• Shi, J. and Tomasi, C. (1994). Good features to track. IEEE CVPR.
• Baker, S. and Matthews, I. (2004). Lucas-Kanade 20 years on: A unifying framework. International Journal of Computer Vision 56(3).

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

With reliable correspondences in two images, the next lesson recovers the camera motion between them: epipolar geometry, the essential matrix, PnP, and the scale ambiguity that monocular visual odometry cannot escape.

Related content

Nothing below is required to finish this lesson.

• Before
  M6-T1: Camera Models and Image Features

  Write the pinhole projection with intrinsics and distortion and describe corners, descriptors and what makes a feature good.

• Lab
  M6-L1: Diagnose Feature-Tracking Failure

  Tracked features vanish or drift: diagnose blur, low texture and bad thresholds and repair the tracker.