Lecture 08 — Descriptors, Matching & RANSAC

Lecture 8

Dr. Muhammad Kazim

Department of Intelligent Systems, University of Lahore

Today’s Agenda

Part 1 — Descriptors & Matching

SIFT, SURF, ORB, BRIEF
Ratio test & cross-check
Brute-force vs FLANN matching
Hamming distance & why binary descriptors suit embedded targets

Part 2 — Geometry & RANSAC

2D transform families
Homography by the DLT
Robust fitting: RANSAC / MSAC
Alignment, panorama stitching & blending

This is also Midterm week — a revision checklist appears near the end of this deck.

From Keypoints to Identity

Last lecture found where the interesting points are (corners, blobs). A descriptor answers a different question: given a keypoint in image A, which keypoint in image B is the same physical point? A descriptor turns a small patch around a keypoint into a vector that is:

similar for the same physical point seen from different views/lighting,
different for unrelated points — distinctive enough to avoid false matches.

SIFT Descriptor

Scale-Invariant Feature Transform (Lowe, 1999/2004) builds on the DoG detector (Lecture 7) and adds:

Orientation assignment: build a histogram of local gradient directions around the keypoint; the dominant peak becomes the keypoint’s reference orientation — this is what makes SIFT rotation-invariant (all later sampling is done relative to this orientation).
Descriptor construction: sample a 16×16 patch (at the keypoint’s scale), split into 4×4 sub-blocks, compute an 8-bin gradient-orientation histogram per sub-block → \(4\times4\times8 = 128\)-dimensional float vector, normalised to unit length (and clipped to reduce sensitivity to illumination).

Distinctive and robust, but 128 floats/keypoint is expensive to store, compute, and match — historically patent-encumbered (patent expired 2020), which pushed the field toward faster, free alternatives.

SURF (Speeded-Up Robust Features)

Bay et al. (2006) re-engineered SIFT for speed:

Uses Haar-wavelet responses and integral images (Lecture 4) so box-filter approximations of the Gaussian/Laplacian can be computed in \(O(1)\) time regardless of filter size.
64-D (or 128-D “extended”) descriptor — roughly half the size of SIFT, several times faster to compute.
Also patent-encumbered historically and, like SIFT, largely superseded in embedded pipelines by binary descriptors.

ORB (Oriented FAST and Rotated BRIEF)

Rublee et al. (2011) — the practical default for this course’s embedded targets:

Detector: FAST (Lecture 7), augmented with a Harris-based corner score to keep only the strongest \(N\) keypoints, plus an intensity-centroid orientation estimate for rotation invariance.
Descriptor: BRIEF (below), but with the sampling pattern rotated to the keypoint’s orientation — “steered BRIEF” — which is what gives ORB rotation invariance that plain BRIEF lacks.
Free, open, an order of magnitude faster than SIFT/SURF, and a 32-byte (256-bit) binary descriptor — ideal for the Pi 5.

orb = cv2.ORB_create(nfeatures=1000)
kp, des = orb.detectAndCompute(gray, None)

BRIEF: Binary Descriptors

Binary Robust Independent Elementary Features (Calonder et al., 2010): instead of a float histogram, sample \(n_d\) (e.g. 256) pairs of pixels \((p_i, q_i)\) around the keypoint from a fixed, precomputed random (or learned) pattern, and set one bit per pair:

\[ \tau(p,q) = \begin{cases} 1 & \text{if } I(p) < I(q) \\ 0 & \text{otherwise} \end{cases} \qquad \Rightarrow \qquad \mathbf{d} = \big(\tau_1,\tau_2,\ldots,\tau_{n_d}\big) \in \{0,1\}^{n_d} \]

Result: a compact 128–512-bit string per keypoint, computed with a handful of comparisons — no gradients, no trigonometry.
Not inherently rotation- or scale-invariant on its own — ORB adds both.

Descriptor Family Comparison

Descriptor	Type	Size	Distance metric	Speed
SIFT	Float histogram	128 × 32-bit	Euclidean (\(L_2\))	Slow
SURF	Float, Haar-based	64/128 × 32-bit	Euclidean	Medium
BRIEF	Binary	128–512 bit	Hamming	Very fast
ORB	Binary (steered BRIEF)	256 bit	Hamming	Very fast

Matching Strategies

Brute-force: compare every descriptor in image A against every descriptor in image B, keep the closest (and optionally the 2nd closest, for the ratio test).

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)   # ORB / BRIEF
matches = sorted(bf.match(des_a, des_b), key=lambda m: m.distance)

Cross-check: a match \((a_i, b_j)\) is kept only if \(b_j\) is \(a_i\)’s nearest neighbour and \(a_i\) is \(b_j\)’s nearest neighbour — a cheap, effective mutual-consistency filter (set via crossCheck=True, mutually exclusive with the ratio test below).

Lowe’s Ratio Test

A wrong match is often still the “best” match available — the real signal is whether the best match is much better than the second-best. For each descriptor, find its two nearest neighbours \(d_1 \le d_2\) and keep the match only if:

\[ \frac{d_1}{d_2} < \tau, \qquad \tau \approx 0.7\text{–}0.8 \]

bf = cv2.BFMatcher(cv2.NORM_HAMMING)
knn = bf.knnMatch(des_a, des_b, k=2)
good = [m for m, n in knn if m.distance < 0.75 * n.distance]

This single line removes the large majority of false matches in a typical scene and is the standard pre-filter before RANSAC.

FLANN — Approximate Nearest-Neighbour Matching

Brute-force matching is \(O(N \cdot M)\) — fine for a few hundred keypoints, too slow for thousands. FLANN (Fast Library for Approximate Nearest Neighbors) builds an index for sub-linear approximate search:

Float descriptors (SIFT/SURF): randomised KD-trees over the vector space.
Binary descriptors (ORB/BRIEF): Locality-Sensitive Hashing (LSH) — KD-trees don’t work well on Hamming space.

index_params = dict(algorithm=6, table_number=6, key_size=12, multi_probe_level=1)  # LSH for ORB
flann = cv2.FlannBasedMatcher(index_params, dict(checks=50))
knn = flann.knnMatch(des_a, des_b, k=2)

Rule of thumb: brute-force for < ~1000 keypoints (simpler, exact); FLANN once matching cost starts to dominate your frame budget.

Why Binary Descriptors Suit Embedded Targets

Hamming distance between two binary strings is just XOR followed by a population count — both are single, cheap CPU instructions (POPCNT on x86, similarly cheap on ARM/NEON), versus dozens of floating-point multiply-adds for a Euclidean distance over 128 floats.

32 bytes (ORB) vs 512 bytes (SIFT, 128 × 4-byte floats) per keypoint — 16× less memory traffic.
No floating-point unit dependency — friendly to low-power microcontroller-class cores too.
This is exactly why the course’s default embedded feature pipeline (Lab 7, Lab 8) is FAST/ORB + Hamming matching, reserving SIFT for offline, accuracy-critical work.

From Matches to Geometry

A set of point correspondences is not yet useful — we need the transform that explains them, so we can warp, align, or measure.

2D Transform Families

Transform	DoF	Preserves	Matrix form
Translation	2	Orientation, shape, size	\(\begin{bmatrix}1&0&t_x\\0&1&t_y\end{bmatrix}\)
Rigid (Euclidean)	3	Shape, size (+ rotation)	\(\begin{bmatrix}R&t\end{bmatrix}\), \(R^TR=I\)
Similarity	4	Shape, angles	Rigid + uniform scale \(s\)
Affine	6	Parallel lines	Any \(2\times3\)
Projective (homography)	8	Straight lines only	Any invertible \(3\times3\) (up to scale)

Each family is a special case of the next — more degrees of freedom means it can fit more complex distortion, but needs more (non-degenerate) correspondences and is more sensitive to noise/outliers.

Homography

A homography \(H\) maps points on one plane to their image on another (or the same plane seen from a different camera pose) in homogeneous coordinates:

\[ \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} \sim H \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad H = \begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{bmatrix} \]

8 DoF (defined up to scale — 9 entries, 1 constraint).
Exact for: (a) a planar scene viewed from any two cameras, or (b) any scene viewed by a camera that only rotates about its optical centre (the panorama case).
Each point correspondence gives 2 linear equations in the unknown \(h_{ij}\) ⇒ need \(\ge 4\) correspondences (in general position).

Direct Linear Transform (DLT)

Rewriting \(x' \times Hx = 0\) (cross product with the correspondence, to eliminate the unknown scale) gives, per correspondence, 2 rows of a linear system \(A\mathbf{h}=0\) in the 9 unknown entries of \(H\) (stacked as a vector \(\mathbf{h}\)):

\[ A\mathbf{h} = 0, \qquad \mathbf{h} = \arg\min_{\lVert \mathbf{h}\rVert=1} \lVert A\mathbf{h} \rVert^2 \]

With exactly 4 correspondences: solve directly. With more (the usual case): the least-squares solution is the eigenvector of \(A^TA\) with the smallest eigenvalue — obtained via SVD.
Good practice: normalise point coordinates (translate centroid to origin, scale to average distance \(\sqrt2\) from origin) before solving — the Hartley normalisation — or the DLT is numerically poorly conditioned.

RANSAC: Robust Fitting

Feature matching (even after the ratio test) still leaves outliers — wrong correspondences that a plain least-squares fit would be badly skewed by. RANSAC (RANdom SAmple Consensus, Fischler & Bolles, 1981):

Randomly sample the minimal set of correspondences needed (4 for a homography).
Fit the model (DLT) to just that sample.
Count inliers: correspondences whose reprojection error under this model is below a threshold \(\varepsilon\).
Keep the model with the most inliers seen so far.
Repeat for \(N\) iterations; finally, re-fit the model with all inliers of the best model (least squares) for the final answer.

How Many RANSAC Iterations?

Given an assumed inlier ratio \(w\) and a desired success probability \(p\) (e.g. 0.99), and a minimal sample size \(s\) (4 for homography):

\[ N = \frac{\log(1-p)}{\log(1-w^{s})} \]

Example: \(w=0.5\), \(s=4\), \(p=0.99\) ⇒ \(N \approx 72\) iterations — cheap.
Lower inlier ratio or larger minimal sample ⇒ iterations grow fast — this is exactly why binary descriptors + a good ratio-test pre-filter (raising \(w\)) make RANSAC converge faster on an embedded target.
MSAC/MLESAC (variants): instead of a hard inlier/outlier count, use a robust cost that down-weights (rather than discards) points near the threshold — a small, usually-worthwhile accuracy gain over vanilla RANSAC. cv2.findHomography(..., method=cv2.RANSAC) in OpenCV actually implements a close relative of MSAC by default.

src = np.float32([kp_a[m.queryIdx].pt for m in good])
dst = np.float32([kp_b[m.trainIdx].pt for m in good])
H, mask = cv2.findHomography(src, dst, cv2.RANSAC, ransacReprojThreshold=3.0)

Alignment & Panorama Stitching

The classical stitching pipeline, end to end:

1. detect + describe keypoints in each image      (ORB/SIFT)
2. match descriptors, filter with ratio test       (BFMatcher/FLANN)
3. estimate homography with RANSAC                 (findHomography)
4. warp one image into the other's frame           (warpPerspective)
5. blend the overlap region                        (feather / multi-band)

warped = cv2.warpPerspective(img_a, H, (out_w, out_h))
canvas[0:img_b.shape[0], 0:img_b.shape[1]] = img_b   # then blend the overlap

OpenCV also ships a ready-made cv2.Stitcher_create() that runs this whole pipeline (plus bundle adjustment and seam finding) across many images — useful for production, but understanding the manual steps is what Lab 8 is for.

Blending the Seam

A naive overwrite at the overlap boundary produces a visible seam from exposure/parallax differences. Two standard fixes:

Feathering (alpha blending): weight each image by its distance from the seam, blend linearly in the overlap band — cheap, removes hard edges, but not exposure differences.
Multi-band blending (Burt & Adelson): blend low frequencies over a wide band and high frequencies over a narrow band (via Laplacian pyramids, Lecture 5) — removes both the seam and exposure mismatch, at higher compute cost.

Practitioner Notes

Always run the ratio test (or cross-check) before RANSAC — RANSAC is robust to outliers, not immune to being overwhelmed by mostly-wrong input.
Check the RANSAC inlier mask (mask from findHomography) — a homography fit from < ~20 inliers is usually not trustworthy for a production pipeline.
Homography assumes a planar scene or pure camera rotation — stitching a scene with real 3-D parallax (nearby objects at different depths) will show visible ghosting no matter how good the matching is.
For calibration and undistortion (this week’s lab also covers this), remember: they correct the lens, independent of scene content — do them once per camera/lens combination and reuse the saved intrinsics.

Midterm Coverage — Revision Checklist

The in-class Midterm Exam (20 marks) covers everything through this week:

Introduction & Image Formation I — the vision pipeline, optics, projection.
Image Formation II & Digital Fundamentals — sensors, sampling, quantisation, colour spaces.
Point Operations & Thresholding — LUTs, histogram equalisation, Otsu/adaptive thresholds.
Spatial Filtering I & II — convolution, smoothing, sharpening, gradients.
Frequency Domain & Pyramids — DFT, frequency filters, sampling theorem, pyramids.
Restoration & Morphology — noise models, Wiener filtering, erosion/dilation/opening/closing.
Edges/Contours & Local Features — Canny, Hough, moments, Harris/Shi–Tomasi/FAST.
Descriptors, Matching & RANSAC — SIFT/ORB/BRIEF, homography, robust fitting.

Bring: derivations you can reproduce (Canny steps, structure tensor, DLT setup, RANSAC iteration formula), and be ready to reason about why each method exists, not just its formula.

This Week’s Lab

Lab 8 — Geometry.

Estimate a homography with RANSAC between two overlapping photos.
Stitch a panorama from your own images.
Calibrate the Pi camera from a chessboard and undistort a frame.
Deliverable: a stitched panorama + a saved camera-intrinsics file.

Key Takeaways

A descriptor turns a keypoint’s neighbourhood into a comparable vector; SIFT/SURF are float and accurate, ORB/BRIEF are binary and fast.
Hamming distance on binary descriptors is a hardware-cheap XOR + popcount — the reason ORB is the default for embedded pipelines.
The ratio test and cross-check remove most false matches before geometric fitting is even attempted.
A homography has 8 DoF and is exact for planar scenes or pure rotation; the DLT solves for it linearly from ≥4 correspondences.
RANSAC finds a model that is consistent with the largest inlier set, making geometric estimation robust to the outliers that inevitably survive matching.