Feature Matching (SIFT/ORB) and Image Stitching

Every method so far has worked inside one image. This post is about relating two images: finding the same physical point in both, throwing away the matches that are wrong, and computing the transformation that lines the images up. That single idea underpins panoramas, visual tracking, augmented reality, and 3D reconstruction.

Prerequisites: Edge detection and thresholding for gradients, and math for computer vision for matrix multiplication.

The problem: photographing a long shelf

A warehouse needs a single wide photo of each aisle for inventory checks. An aisle is 12 metres long, so a phone must take five overlapping photos. Those five need to become one image, aligned well enough that a barcode near a seam is still readable.

You cannot just place the photos side by side. The camera moved, rotated slightly, and tilted between shots, so the same shelf edge appears at a different position and angle in each photo. You need to work out, from the images themselves, exactly how each one relates to the next.

graph LR
  A["Photo 1"] --> D["Detect keypoints<br/>+ descriptors"]
  B["Photo 2"] --> D
  D --> E["Match descriptors"]
  E --> F["Lowe's ratio test<br/>drops ~90%"]
  F --> G["RANSAC<br/>drops the rest"]
  G --> H["Homography H"]
  H --> I["Warp + blend"]
  I --> J["Panorama"]

What makes a good keypoint

Pick a random pixel in a photo and try to find the same pixel in the next photo. If it sits on a plain white wall, thousands of pixels look identical and you cannot. If it sits on a straight shelf edge, you can tell which side of the edge you are on but not where along it — you can slide freely in one direction. Only at a corner are you locked in both directions.

That is the whole intuition behind corner detection. Shift a small window by one pixel in every direction and measure how much the patch content changes:

Both SIFT and ORB build on this. They add two things a plain corner detector lacks: a scale, so the same corner is found whether the camera is near or far, and an orientation, so the same corner is found whether the camera is upright or rotated.

SIFT versus ORB

The memory figure is the one people underestimate. Matching 2,000 SIFT keypoints against 2,000 others means comparing 128-dimensional float vectors four million times. ORB compares 256-bit strings, which a CPU does with a single XOR and a population-count instruction.

Hamming distance is just the number of differing bits. Here are two 16-bit slices of ORB descriptors:

Three bits differ out of sixteen, so the Hamming distance is 3. For a real 256-bit descriptor, a distance under about 50 usually means a genuine match and over 80 usually does not.

import cv2

img1 = cv2.imread("shelf_01.jpg", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("shelf_02.jpg", cv2.IMREAD_GRAYSCALE)

# ORB: fast, binary descriptors
orb = cv2.ORB_create(nfeatures=3000)
kp1, des1 = orb.detectAndCompute(img1, None)
kp2, des2 = orb.detectAndCompute(img2, None)
print(f"{len(kp1)} and {len(kp2)} keypoints")

# SIFT: slower, more accurate
sift = cv2.SIFT_create()
kps, dess = sift.detectAndCompute(img1, None)
print(f"SIFT descriptor shape: {dess.shape}")   # (N, 128)

Matching, and why raw matches are mostly wrong

For each descriptor in image 1, find the closest descriptor in image 2. Simple, and mostly wrong. A shelf has dozens of near-identical bracket corners, and the closest descriptor is often a different bracket.

David Lowe’s fix is one line and removes most of the damage. For each keypoint, find the two nearest neighbours and compare their distances:

$\text{ratio} = \frac{d_1}{d_2}$

If the best match is much closer than the second best, the match is distinctive and probably right. If both are about equally close, the feature is ambiguous and you should discard it rather than guess.

Work through match 3: the nearest descriptor is at distance 42 and the second nearest at 51. The ratio is $42/51 = 0.82$, above the 0.75 threshold, so this keypoint looks almost as similar to two different places. Drop it.

Match 5 has a ratio of $18/74 = 0.24$. Its best match is four times closer than its runner-up. That is a confident match.

The shape of that plot is the argument for the ratio test. Correct matches spread across low ratios; wrong matches pile up near 1.0 because a random descriptor is roughly equidistant from everything. One threshold cuts cleanly between the two populations.

bf = cv2.BFMatcher(cv2.NORM_HAMMING)          # NORM_L2 for SIFT
knn = bf.knnMatch(des1, des2, k=2)

good = [m for m, n in knn if m.distance < 0.75 * n.distance]
print(f"{len(knn)} raw -> {len(good)} after ratio test")

RANSAC: ignoring the matches that are still wrong

After the ratio test roughly 15% of matches are still wrong. Fitting a transformation to all of them gives a result pulled badly off by the outliers, because least squares gives every point a vote weighted by its error squared.

The loop:

1. Pick 4 matches at random (4 is the minimum needed for a homography).
2. Compute the transformation from just those 4.
3. Apply it to every other match and measure the error.
4. Count how many fall within a threshold — these are the inliers.
5. Repeat, then keep the model with the most inliers and refit using all of them.

How many iterations do you need?

There is a formula, and it explains why RANSAC is practical:

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

where $p$ is the confidence you want, $w$ is the fraction of matches that are inliers, and $s$ is the sample size.

With $p = 0.99$, $w = 0.5$, $s = 4$:

$w^s = 0.5^4 = 0.0625$ $N = \frac{\log(0.01)}{\log(1 - 0.0625)} = \frac{-4.605}{-0.0645} = 71.4 \rightarrow 72 \text{ iterations}$

72 iterations to be 99% sure of finding a clean sample, even when half the matches are garbage. Now try a much worse case, $w = 0.3$:

$0.3^4 = 0.0081, \qquad N = \frac{-4.605}{\log(0.9919)} = \frac{-4.605}{-0.008133} = 566$

The cost grows steeply as the inlier fraction falls. That is precisely why the ratio test matters: pushing $w$ from 0.3 to 0.5 cuts the work by a factor of eight, and the ratio test is one line of code.

Homography: the transformation itself

A homography A 3x3 matrix that maps points from one image plane to another. It is exact when the scene is flat, or when the camera only rotates about its own centre. takes a point $(x, y)$ and produces $(u, v)$:

$\begin{bmatrix} u' \\ v' \\ w' \end{bmatrix} = \begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad u = \frac{u'}{w'}, \quad v = \frac{v'}{w'}$

That final division by $w'$ is what makes it a perspective transform rather than an affine one. It is why parallel shelf edges converge in a tilted photo.

Work one point through. Suppose RANSAC returns:

$H = \begin{bmatrix} 1.20 & 0.10 & 30 \\ 0.05 & 1.10 & -20 \\ 0.0002 & 0.0001 & 1 \end{bmatrix}$

Apply it to the keypoint at $(200, 150)$:

$u' = 1.20(200) + 0.10(150) + 30 = 240 + 15 + 30 = 285$ $v' = 0.05(200) + 1.10(150) - 20 = 10 + 165 - 20 = 155$ $w' = 0.0002(200) + 0.0001(150) + 1 = 0.04 + 0.015 + 1 = 1.055$

Divide:

$u = \frac{285}{1.055} = 270.1, \qquad v = \frac{155}{1.055} = 146.9$

So the point at $(200, 150)$ in image 1 should appear at $(270.1, 146.9)$ in image 2.

Reprojection error decides inliers

The matching step said this keypoint appears at $(272, 145)$ in image 2. The homography predicted $(270.1, 146.9)$. The reprojection error The distance in pixels between where a model predicts a point should land and where it was actually measured. is:

$e = \sqrt{(272 - 270.1)^2 + (145 - 146.9)^2} = \sqrt{1.9^2 + 1.9^2} = \sqrt{7.22} = 2.69 \text{ px}$

With a threshold of 3.0 pixels, 2.69 is under it, so this match is an inlier and votes for this homography.

Notice how separated the outlier is. Wrong matches are not slightly off, they are completely off, which is why a threshold anywhere from 2 to 5 pixels gives the same answer.

import numpy as np

src = np.float32([kp1[m.queryIdx].pt for m in good]).reshape(-1, 1, 2)
dst = np.float32([kp2[m.trainIdx].pt for m in good]).reshape(-1, 1, 2)

H, mask = cv2.findHomography(src, dst, cv2.RANSAC,
                             ransacReprojThreshold=3.0,
                             maxIters=2000, confidence=0.995)

inliers = int(mask.sum())
print(f"{inliers} / {len(good)} inliers ({inliers/len(good):.0%})")

The inlier count is your health check. Below about 15 inliers, do not trust the homography at all. Between 15 and 30 it is usable but fragile. Above 50 with a ratio over 60%, the alignment is solid.

Stitching the panorama

graph TD
  A["5 overlapping photos"] --> B["ORB on each"]
  B --> C["Match consecutive pairs"]
  C --> D["Ratio test per pair"]
  D --> E["RANSAC homography per pair"]
  E --> F{"Inliers > 30<br/>for every pair?"}
  F -->|"no"| G["Retake that pair<br/>with more overlap"]
  F -->|"yes"| H["Chain homographies<br/>to a common frame"]
  H --> I["Warp all into the canvas"]
  I --> J["Blend seams"]
  J --> K["Crop to the largest rectangle"]

Two homographies chain by multiplication. If $H_{12}$ maps photo 1 to photo 2 and $H_{23}$ maps photo 2 to photo 3, then photo 1 maps to photo 3 by:

$H_{13} = H_{23} \cdot H_{12}$

Order matters — matrices do not commute. This chaining is also where error accumulates: five photos means four chained homographies, and a half-pixel error in each compounds along the chain. Real panorama software runs a global refinement (bundle adjustment) at the end to spread that error evenly rather than letting it pile up at one end.

stitcher = cv2.Stitcher_create(cv2.Stitcher_PANORAMA)
status, pano = stitcher.stitch([img1, img2, img3, img4, img5])

codes = {
    cv2.Stitcher_OK: "ok",
    cv2.Stitcher_ERR_NEED_MORE_IMGS: "not enough overlap between photos",
    cv2.Stitcher_ERR_HOMOGRAPHY_EST_FAIL: "could not align — too few good matches",
    cv2.Stitcher_ERR_CAMERA_PARAMS_ADJUST_FAIL: "inconsistent geometry across the set",
}
print(codes[status])

For a straightforward panorama, use cv2.Stitcher. Build the pipeline by hand when you need control over which pairs are matched, when you want to blend seams your own way, or when you are debugging a failure and need to see the inlier counts.

When feature matching fails

That last row is a genuine limit rather than a tuning problem. A homography is exact only when the scene is flat, or when the camera rotates about its own centre without moving. Walk sideways past a shelf with objects at different depths and no single 3×3 matrix can align both the near and far objects at once. The near items shift more than the far ones — that is parallax The apparent shift of nearby objects relative to distant ones when the camera moves sideways. It carries depth information, and it is exactly what a homography cannot represent. .

Practice task

Photograph a bookshelf in four overlapping shots, sweeping left to right.

1. Detect ORB keypoints in each. Record how many are found per image.
2. Match consecutive pairs raw, without the ratio test. Draw the matches and count the obviously wrong lines.
3. Apply the ratio test at 0.75. Draw again and count how many survived.
4. Run findHomography with RANSAC and record the inlier count per pair.
5. Repeat steps 3–4 at ratio thresholds 0.6, 0.7, 0.8, and 0.9. Plot inlier count and inlier ratio against threshold.
6. Warp image 2 into image 1’s frame and look at the seam.
7. Now photograph a blank wall the same way and repeat. Note where it breaks.

Step 7 is the one to actually do. Watching the pipeline fail on a blank wall — and seeing findHomography still cheerfully return a matrix — teaches more about why the inlier count matters than any amount of reading.

Summary

Keypoints must be corners, because only a corner is unambiguous when you shift the window in both directions. Each keypoint carries a descriptor: 128 floats for SIFT, 256 bits for ORB, which is 16× smaller and roughly 30× faster to compare using Hamming distance — you counted 3 differing bits between two 16-bit slices by hand.

Raw matches are mostly wrong. Lowe’s ratio test compares each match’s nearest neighbour to its runner-up and discards anything above 0.75; you worked through eight matches and kept four. That single step matters enormously to RANSAC’s cost: at an inlier fraction of 0.5 you need 72 iterations, but at 0.3 you need 566.

RANSAC fits a homography from 4 random matches and counts how many agree. You applied a homography to the point $(200, 150)$ and got $(270.1, 146.9)$ after dividing by $w' = 1.055$, then measured a reprojection error of 2.69 pixels against the observed $(272, 145)$ — an inlier at a 3-pixel threshold. Always check the inlier count, because findHomography returns a matrix whether or not it means anything.

What comes next

Before moving on, one contrast worth holding onto. SIFT and ORB find specific points — a corner on this particular building — and match them between views of the same scene. They answer “is this the same thing I saw before?”. HOG, covered in HOG, HOF and MBH descriptors, describes a whole region by its overall shape and answers “is this the kind of thing I am looking for?”. One is about instance identity, the other about category. That distinction — the recognition ladder from post 1 — decides which descriptor you reach for.

RANSAC gave you the relationship between two views, but not in real units — the homography is in pixels, and the pixels depend on the lens. Camera calibration and perspective correction works out the camera’s internal parameters so you can remove lens distortion and start measuring in millimetres. After that, epipolar geometry and stereo vision handles the case a homography cannot: a camera that translates through a scene with real depth.