Putting Features to Work: Matching, RANSAC, and Stitching

Matching Descriptors Across Images

This is the payoff guide. Over the last four guides you learned to find repeatable keypoints (corners, blobs across scale) and to summarise the neighbourhood around each one as a descriptor vector — SIFT, HOG, SURF, BRIEF, ORB. But a descriptor sitting alone in one image does nothing. The magic begins when you have two pictures of the same scene and you ask: which keypoint over here is the same physical point as which keypoint over there? Answering that question is called feature matching, and it is the bridge from 'describing one image' to 'reasoning about how two images relate'.

The core idea is beautifully simple: each descriptor is a point in a high-dimensional space, so 'the same physical point' should land at nearly the same place in that space when seen from a slightly different angle. To match a descriptor f from image 1, we find its nearest neighbour among all descriptors of image 2 — the one with the smallest distance. We reuse exactly the distance metrics from Guide 4: for real-valued descriptors like SIFT descriptors (and SURF) we use Euclidean (L2) distance; for binary descriptors like ORB descriptors (and BRIEF) we use Hamming distance — the count of differing bits, which a CPU computes as a single XOR-then-popcount. The metric is not an afterthought; it is dictated by how the descriptor was built.

How do we actually search for nearest neighbours? The honest baseline is brute-force matching: for every descriptor in image 1, compute its distance to every descriptor in image 2 and keep the smallest. If the images have m and n keypoints, that is m × n distance computations — fine for a few thousand features, but it grows quadratically and becomes the bottleneck at scale. So in practice we often use approximate nearest-neighbour structures: a KD-tree (which recursively splits the descriptor space along axes, great for low-to-moderate-dimensional float vectors like SIFT) or LSH, locality-sensitive hashing (which hashes similar binary descriptors into the same buckets — the natural choice for Hamming-space ORB). 'Approximate' means we trade a tiny chance of missing the true nearest neighbour for a large speed-up — usually a great deal.

# Brute-force matching with the RIGHT metric per descriptor type.
# (conceptual; OpenCV's cv2.BFMatcher wraps this efficiently)

def match_brute_force(desc1, desc2, metric):
    matches = []
    for i, f in enumerate(desc1):           # each descriptor in image 1
        best_j, best_d = None, float('inf')
        second_d = float('inf')
        for j, g in enumerate(desc2):       # scan all of image 2
            d = metric(f, g)                # L2 for SIFT/SURF, Hamming for ORB
            if d < best_d:
                second_d = best_d           # demote old best to 2nd best
                best_d, best_j = d, j
            elif d < second_d:
                second_d = d
        # keep BOTH neighbours -- we need them for Lowe's ratio test (next section)
        matches.append((i, best_j, best_d, second_d))
    return matches

Good Matches vs Bad: Lowe's Ratio Test

Here is the uncomfortable truth: nearest-neighbour matching is noisy. Every descriptor in image 1 is guaranteed to find some nearest neighbour in image 2 — even if its true partner isn't in image 2 at all (it was occluded, or fell outside the frame). Worse, real scenes are full of repeated texture: bricks, windows, leaves, fence posts, lettering. A descriptor on one brick looks almost identical to a descriptor on the brick beside it, so the matcher can confidently pair the wrong ones. We need a way to ask not just 'what is the closest match?' but 'is the closest match distinctively close?'

Lowe's ratio test: keep a match only if the best neighbour is clearly better than the second-best.

Let's unpack it symbol by symbol. f is the query descriptor from image 1. NN₁ is its closest descriptor in image 2 and NN₂ is its second-closest (a different keypoint); d(·,·) is the same descriptor distance as before (L2 or Hamming). The test computes the ratio of the best distance to the second-best distance and accepts the match only when that ratio is below a threshold ρ, typically 0.7–0.8. The intuition is the whole point: if f's true partner is in image 2, that partner should stand out — NN₁ should be much closer than NN₂, giving a small ratio (say 0.3). But if f sits on repeated texture, NN₁ and NN₂ are both equally good impostors, so the ratio creeps toward 1.0 — the match is ambiguous and we throw it away. Concrete example: with SIFT distances d(f,NN₁)=120 and d(f,NN₂)=150, the ratio is 0.80, borderline and likely rejected at ρ=0.7; but d(f,NN₁)=120 with d(f,NN₂)=400 gives 0.30 — a crisp, trustworthy match. Lowe found this single threshold eliminates ~90% of false matches while discarding only ~5% of correct ones.

A complementary filter is symmetric (cross-check) matching: a match between keypoint a in image 1 and keypoint b in image 2 is kept only if a's nearest neighbour is b and b's nearest neighbour back in image 1 is a. It demands that the two images agree with each other rather than trusting a one-way vote. The ratio test and cross-check attack the problem from different angles — ratio test measures distinctiveness, cross-check measures mutual agreement — and they are often combined for a cleaner match set.

Homography: Relating Two Views of a Plane

Geometry gives us a powerful filter, but only when the scene cooperates. There are two common situations where a single, exact mapping relates the two images: (1) the scene is a flat plane (a wall, a poster, a tabletop, the ground seen from a drone), or (2) the camera doesn't move but only rotates in place (the classic panorama, where you pivot to sweep the horizon). In both cases the relationship between a point in image 1 and its location in image 2 is captured by a single 3×3 matrix called a homography, written H. Once we know H, we can predict exactly where any point of image 1 should appear in image 2 — and a match that disagrees with that prediction is exposed as an outlier.

To write H cleanly we need homogeneous coordinates — your first meeting with them, so let's go gently. The trick is to represent a 2D point (x, y) by appending a 1, giving the triple (x, y, 1). Why bother? Because projection (the way a 3D world flattens onto a 2D sensor) involves division, and division is awkward to write as a matrix multiply. Homogeneous coordinates absorb that division into a rule: two triples that differ only by an overall scale factor represent the same 2D point. So (2, 4, 2), (1, 2, 1) and (3, 6, 3) are all the very same point (1, 2). Think of it as a 'shadow': a point and a light ray through it cast the same shadow on the image plane no matter how far along the ray you slide — the scale is irrelevant, only the direction matters.

A homography maps homogeneous image-1 points to homogeneous image-2 points, up to an unknown scale s.

Reading the equation: (x, y) is a point in image 1 written homogeneously as (x, y, 1). Multiplying by the 3×3 matrix H produces a 3-vector; that vector is (x', y') — the point's location in image 2 — but scaled by an unknown number s. We recover the real pixel coordinates by dividing through by the third entry: if H·(x,y,1)ᵀ = (u, v, w)ᵀ, then x' = u/w and y' = v/w. That division is exactly the 'scale removed' that s denotes, and it is what makes a homography more than a plain linear map. Now count the unknowns: H has 9 entries, but because the whole equation is up to scale we may fix one entry (commonly h₃₃ = 1), leaving 8 degrees of freedom. Each point correspondence gives us two equations (one for x', one for y'), so 4 correspondences provide 8 equations — exactly enough to solve for the 8 unknowns. That magic number 4 is why the next section samples 4 matches at a time.

RANSAC: Finding Truth Among Outliers

We now have a set of matches, mostly good but salted with surviving outliers, and a geometric model (the homography) they ought to obey. The problem is that ordinary least-squares fitting is a coward: if you feed it all the matches and ask for the best H, even a handful of wild outliers can drag the answer far from the truth, because squared error punishes the fitter for ignoring them. We need a method that can find the model supported by the majority while simply ignoring the liars. That method is RANSAC — RANdom SAmple Consensus. The analogy: imagine asking a noisy crowd a yes/no question where most people are honest but a few lie. You don't average everyone; you look for the largest group that all agree, and trust them.

1. Sample: randomly pick the minimal set of matches needed to fit the model — for a homography that is exactly 4 correspondences (from Section 3's count).
2. Fit: solve for a candidate homography H from just those 4 matches.
3. Score: apply H to every other match's image-1 point, measure the reprojection error (distance between where H predicts the point lands and where its matched point actually is), and count how many matches fall within a small threshold. Those agreeing matches are the inliers; the count is the consensus score.
4. Keep the best: remember the H that earned the most inliers so far.
5. Repeat: run steps 1–4 many times so a random all-good sample is virtually certain to occur at least once.
6. Refit: take the inliers of the winning model and re-estimate H from all of them with least squares — now safe, because the outliers are gone.

How many random samples RANSAC needs to succeed with probability p.

This formula tells you how many iterations N to run, and it is wonderfully intuitive once unpacked. w is the inlier fraction — the proportion of your matches that are actually correct (say 0.5 means half are good). s is the sample size drawn each round (s = 4 for a homography). p is the target probability that RANSAC succeeds, i.e. that at least one of the N samples is purely inliers (commonly p = 0.99). Build it up step by step: the chance that one randomly drawn match is an inlier is w, so the chance that all s of them are inliers — an all-good sample — is wˢ (each draw independent, approximately). Therefore the chance a sample is contaminated (at least one outlier) is 1 − wˢ, and the chance that all N samples are contaminated is (1 − wˢ)ᴺ. We want that failure probability to be at most 1 − p, set (1 − wˢ)ᴺ = 1 − p, take logs, and solve for N — giving the formula above. Plug in numbers: with w = 0.5, s = 4, p = 0.99, we get wˢ = 0.0625, so N = log(0.01)/log(0.9375) ≈ 71 iterations. Drop the inlier fraction to w = 0.3 and N jumps to about 567 — vividly showing how the cost explodes as outliers grow. The deep lesson: RANSAC's effort depends on how dirty the data is, not on how many matches you have.

Image Stitching: Building a Panorama

Now the 'aha' moment that ties the whole track together. When you sweep your phone across a landscape and it fuses the shots into one wide panorama, every concept from these five guides is quietly at work. Stitching is the canonical end-to-end application: it needs repeatable keypoints, distinctive descriptors, careful matching, robust geometry, and image warping — exactly the ladder you've climbed. Let's trace the full pipeline and label each rung with the guide that taught it.

1. Detect keypoints in both photos — corners and blobs that survive scale and viewpoint changes (Guides 1–2).
2. Describe each keypoint with an invariant descriptor — SIFT/HOG, or fast binary SURF/BRIEF/ORB (Guides 3–4).
3. Match descriptors across the two images by nearest neighbour, then clean the set with Lowe's ratio test and cross-check (this guide, Sections 1–2).
4. Estimate the homography H between the two views with RANSAC, which simultaneously discards the surviving outliers (this guide, Sections 3–4).
5. Warp one image into the other's coordinate frame by applying H to every pixel, so overlapping content lines up exactly.
6. Blend the overlap to hide the seam and even out exposure, producing one seamless wide image.

Step 5, warping, is where the homography earns its keep. Conceptually we choose one image as the canvas and, for each output pixel, use H (or its inverse) to look up which source pixel maps there, interpolating between neighbours for sub-pixel accuracy. Because H was fit only to inliers, the planar/rotational geometry holds and the second image slots cleanly onto the first — straight lines stay straight, the wall stays flat. This is the moment the abstract 3×3 matrix becomes a visibly correct overlay.

But a perfect geometric warp still shows an ugly seam, because the two photos were taken with slightly different exposure and white balance — one side is brighter, and the join is visible as a hard edge. Blending fixes this. The simplest is feathering: in the overlap region, take a weighted average of the two images where the weight ramps smoothly from one to the other, so the transition is gradual instead of abrupt. More sophisticated is multi-band blending, which blends low spatial frequencies (broad brightness) over a wide region while blending high frequencies (fine texture and edges) over a narrow one — this hides exposure differences without smearing detail. The result is the seamless panorama your phone hands back in a second.

Bag of Visual Words: From Matching to Recognition

Geometry is one great use of descriptors, but there is a second, equally important one: recognition and retrieval — answering 'what is in this image?' or 'find me all images like this one' across a database of millions. Pairwise matching is far too slow for that; comparing a query against a million images by matching every descriptor would take forever. The trick, borrowed straight from text search, is bag of visual words (BoVW). In text, a document's bag-of-words is just a count of how often each vocabulary word appears, ignoring order — 'the cat sat' and 'sat the cat' get the same histogram. BoVW does the identical thing for images, with descriptors playing the role of words.

First we build a visual vocabulary. We collect a huge pile of descriptors (say SIFT descriptors) from many training images and cluster them with k-means into k groups — perhaps k = 1,000 or 100,000. Each cluster centre becomes a 'visual word': a representative patch-appearance like 'a corner of this orientation' or 'a dark blob on light'. Crucially, descriptors that are slightly different but visually similar (the same corner under slightly different lighting) get rounded to the same word, which is exactly the robustness we want. The vocabulary is built once, offline.

Vector quantization: snap each descriptor to its nearest vocabulary word.

This little equation is vector quantization — turning a continuous descriptor into a discrete word label. Reading it: d is one descriptor extracted from the image; c_k is the centre of the k-th cluster (the k-th visual word); ‖d − c_k‖ is the Euclidean distance from the descriptor to that centre; and argmin over k picks the index k that makes the distance smallest. In plain words: assign each descriptor to whichever visual word it most resembles. Do this for all of an image's descriptors and you can tally them into a histogram h, a vector of length k where h[k] counts how many descriptors landed in word k (then normalise so image size doesn't matter). That histogram is the image's whole-image signature — a fixed-length vector you can feed to a classifier or compare to other images by simple vector distance. The text analogy is exact: just as you'd describe a document by 'mentions "economy" 12 times, "goal" 0 times', you describe an image by 'visual word 47 appears 9 times, word 88 appears 3 times'.

The Classical Pipeline in the Deep-Learning Era

Let's close the track with a clear-eyed map of where everything you've learned stands today. The classical pipeline is a clean five-stage assembly line: detect keypoints → describe them → match descriptors → geometrically verify with RANSAC → recognise or retrieve with bag-of-visual-words. You now understand every box and every arrow. The fair question is: in an era when deep networks dominate so much of vision, does this still matter? The answer is a confident yes — but you should know exactly where and why.

Classical, hand-crafted features still dominate several arenas. In visual SLAM (robots and AR headsets tracking their pose live) and structure-from-motion (reconstructing 3D scenes from photo collections), the geometry-first pipeline of keypoints + matching + RANSAC is the workhorse — it is fast, well-understood, and needs no training data for a new environment. On phones and drones, the on-device efficiency of ORB descriptors (binary, Hamming-matchable in microseconds) is hard to beat. And in low-data or interpretability-critical settings — medical, scientific, or safety domains where you must explain why two images matched — a transparent descriptor distance beats an opaque neural embedding you cannot audit.

Where do learned methods now lead? When you have abundant data and can afford training, neural detectors and descriptors win on raw matching accuracy, especially under hard appearance changes — day-to-night, seasons, big viewpoint swings. Systems like SuperPoint (a CNN that jointly learns keypoints and descriptors) and SuperGlue (a graph neural network that matches them by reasoning about all candidates jointly, far smarter than independent nearest-neighbour + ratio test) set the state of the art on hard benchmarks. They don't discard the classical structure — they learn better instances of the same boxes. SuperPoint is still a detector-plus-descriptor; SuperGlue is still a matcher; both still feed RANSAC and homographies downstream.