Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 54 ยท Features and Matching

Feature Matching and Homography

Match ORB and SIFT descriptors with BFMatcher and FLANN, filter with Lowe's ratio test, then fit a homography with RANSAC. Hamming and RANSAC in NumPy.

Once you have keypoints and descriptors for two images (see Corners and Keypoints), the task is to decide which keypoint in image A is the same physical point as which keypoint in image B. That is feature matching. The matches then let you estimate how the second image is related to the first, for example the homography that maps a flat object or a rotated camera view from one picture into the other. This is the engine behind panoramas, augmented reality markers and object recognition.

All cv2 code in this lesson is read-only because opencv-python does not run in the browser. The live examples use NumPy stand-ins that implement the same ideas (Hamming distance, the ratio test, RANSAC and a homography solver), and the text says what is real and what is the stand-in.

The pipeline

From two photos to one transform

Detect Find keypoints in both images.
Describe One compact vector per keypoint.
Match Pair each descriptor with its nearest one.
Filter Drop ambiguous pairs with the ratio test.

A homography is then fitted to the surviving pairs.

1 / 2

Brute-force matching

cv2.BFMatcher compares every descriptor of image A with every descriptor of image B and keeps the closest. The distance has to suit the descriptor: NORM_HAMMING for binary descriptors (ORB, BRIEF, AKAZE, BRISK) and NORM_L2 for float ones (SIFT).

Python
import cv2

img1 = cv2.imread("book.png", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("desk.png", cv2.IMREAD_GRAYSCALE)

orb = cv2.ORB_create(nfeatures=1000)
kp1, des1 = orb.detectAndCompute(img1, None)
kp2, des2 = orb.detectAndCompute(img2, None)

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = bf.match(des1, des2)
matches = sorted(matches, key=lambda m: m.distance)

# Each DMatch: queryIdx (index in des1), trainIdx (index in des2), distance
print(matches[0].queryIdx, matches[0].trainIdx, matches[0].distance)

vis = cv2.drawMatches(img1, kp1, img2, kp2, matches[:30], None,
                      flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

With crossCheck=True a pair is kept only if each descriptor is the other's best match, which removes many wrong pairs but cannot use the ratio test below. Note the argument order: the first descriptor set is the query, the second is the train set.

A Hamming distance counts the differing bits between two binary descriptors. With 256-bit ORB descriptors the distance runs from 0 (identical) to 256, and about 128 is what unrelated descriptors give. The next example is a pure NumPy stand-in for BFMatcher with NORM_HAMMING. It builds fake 256-bit descriptors, makes "image B" a noisy copy in a shuffled order, and recovers the pairing.

Python Brute-force Hamming matching

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The true pairs sit at a small distance (the 5% of flipped bits), while unrelated pairs land around 128. That gap is what makes binary descriptors practical.

Lowe's ratio test

The nearest descriptor is not always the right one. Repetitive textures, such as window grids or brick walls, produce several almost equally good candidates, and any of them may be wrong. David Lowe's ratio test keeps a match only if the best candidate is clearly better than the second best:

TEXT
keep if  distance(best) < ratio * distance(second best)      ratio is about 0.7 to 0.8

You need the two nearest neighbors per query, so use knnMatch with k=2 (and no crossCheck):

Python
bf = cv2.BFMatcher(cv2.NORM_HAMMING)
pairs = bf.knnMatch(des1, des2, k=2)

good = []
for pair in pairs:
    if len(pair) == 2:                 # sometimes fewer than 2 neighbors exist
        best, second = pair
        if best.distance < 0.75 * second.distance:
            good.append(best)

The check len(pair) == 2 matters in real code: a query can come back with fewer than two neighbors, and unpacking would then raise an error.

The next example applies the ratio test to descriptors where some points have an ambiguous twin. Points with a near-duplicate in the other image are rejected, which is exactly the point of the test.

Python The ratio test removes ambiguous matches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The repetitive queries have two nearly equal candidates, so their ratio is close to 1 and they are dropped. The distinctive ones have a second best near 128 and a best near 10, so they pass easily. A lower ratio keeps fewer but more reliable matches.

Drawing matches

To see what matched, use cv2.drawMatches for the output of match (a flat list of matches) and cv2.drawMatchesKnn for the output of knnMatch (a list of lists, one list of candidates per descriptor). Both draw the two images side by side and connect matching keypoints with lines.

Python
# flat list from bf.match(...)
vis = cv2.drawMatches(img1, kp1, img2, kp2, matches[:30], None,
                      flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

# list of lists from knnMatch(...), after the ratio test keep pairs that pass
good = [[m] for m, n in knn if m.distance < 0.75 * n.distance]
vis = cv2.drawMatchesKnn(img1, kp1, img2, kp2, good, None,
                         matchColor=(0, 255, 0), singlePointColor=(255, 0, 0),
                         flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

matchColor colors the lines and the matched points, singlePointColor colors keypoints that found no match, and matchesMask (a list of 0/1 per match) draws only the selected ones, for example only the inliers that RANSAC kept. The flag NOT_DRAW_SINGLE_POINTS hides unmatched keypoints, which makes a busy picture readable. Remember drawMatchesKnn expects the nested list; passing a flat list is the usual error.

ORB: advantages and limits

ORB (Oriented FAST and Rotated BRIEF) detects corners with FAST, assigns each an orientation, and describes it with a rotated BRIEF 256-bit binary string. Advantages: very fast, free of patents, tiny binary descriptors that are compared with cheap bit operations (NORM_HAMMING), invariant to rotation and reasonably robust to noise. Limitations: weaker under large scale changes and strong lighting changes than SIFT, and it finds fewer, less distinctive features in blurry or textureless images. Typical applications are 3D reconstruction, SLAM, panoramas, object recognition and tracking, where speed matters more than the last bit of accuracy.

FLANN for large descriptor sets

Brute force is exact but compares every pair, which is slow when each image has tens of thousands of descriptors. FLANN (Fast Library for Approximate Nearest Neighbors) builds an index and returns approximate neighbors much faster. You must tell it which index to use, depending on the descriptor type:

Python
# For SIFT (float descriptors): KD-trees
FLANN_INDEX_KDTREE = 1
index_params = dict(algorithm=FLANN_INDEX_KDTREE, trees=5)
search_params = dict(checks=50)
flann = cv2.FlannBasedMatcher(index_params, search_params)
pairs = flann.knnMatch(des1, des2, k=2)       # des must be float32

# For ORB (binary descriptors): locality sensitive hashing
FLANN_INDEX_LSH = 6
index_params = dict(algorithm=FLANN_INDEX_LSH,
                    table_number=6, key_size=12, multi_probe_level=1)
flann = cv2.FlannBasedMatcher(index_params, dict(checks=50))

Two classic traps: FLANN with the KD-tree index needs float32 descriptors (ORB's uint8 ones will fail or give nonsense), and for small sets BFMatcher is often just as fast and always exact. Start with BFMatcher; switch only when profiling says so.

From matches to a homography

A homography is a 3 by 3 matrix H that maps points of one plane view to another, including perspective (see Perspective Transforms and Document Scanning). With at least four point pairs you can solve for it, but real matches contain wrong ones (outliers), and a single bad pair ruins a least-squares fit.

RANSAC (random sample consensus) solves that. It repeats: pick 4 random matches, compute H from just them, count how many other matches agree with this H (their reprojection error is below a threshold), and finally keep the H with the most agreeing matches, the inliers. OpenCV does it in one call:

Python
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, inlier_mask = cv2.findHomography(src, dst, cv2.RANSAC, 5.0)
# 5.0 = max reprojection error in pixels for a match to count as an inlier

print(H)                      # 3x3 float64, or None if it failed
print(int(inlier_mask.sum()), "inliers of", len(good))

h, w = img1.shape
corners = np.float32([[0, 0], [w, 0], [w, h], [0, h]]).reshape(-1, 1, 2)
outline = cv2.perspectiveTransform(corners, H)     # where image 1 lands in image 2

findHomography returns None when there are fewer than 4 good pairs or no consistent solution, so check for that. It also needs H to make sense: a plane or a camera that only rotates. For a general 3D scene with a moving camera, a homography fits only the dominant plane.

To stay honest about how this works, the next example is a small homography solver (the direct linear transform, with np.linalg.svd) plus a RANSAC loop in pure NumPy. It generates matches from a known homography, corrupts 30% of them, and shows RANSAC recovering the transform. It is a teaching stand-in, not OpenCV's optimized implementation.

Python Homography and RANSAC in NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The plain least-squares fit is pulled far off by the outliers, while RANSAC picks a model supported by the good matches and refits only on those. That robustness is the reason cv2.findHomography takes cv2.RANSAC as its method.

Stitching and what comes next

With H in hand, stitching two photos is a warp: use cv2.warpPerspective(img1, H, (width, height)) to put image 1 into image 2's frame on a larger canvas, then blend the overlap. The panorama project builds the full pipeline. Related uses of the same tools: locating a book cover in a cluttered scene by projecting its outline, aligning two scans of the same page, or stabilizing video by matching consecutive frames.

A few habits make matching reliable:

  • Match on grayscale images; color is not used by ORB or SIFT.
  • Use the right norm for the descriptor type, and keep float32 for FLANN KD-trees.
  • Always apply the ratio test (0.7 to 0.8) when using knnMatch.
  • Require a minimum number of inliers (for example 10) before trusting H.
  • Visualize with cv2.drawMatches while developing: wrong matches are obvious to the eye.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which norm should BFMatcher use for ORB descriptors?

    ORB descriptors are binary, so the number of differing bits (Hamming distance) is the right and fastest measure. L2 is for float descriptors such as SIFT.
  2. 2. What does Lowe's ratio test do?

    If the best and second-best candidates are about equally close, the match is ambiguous. Requiring best < ratio * second removes those.
  3. 3. Why is a plain least-squares homography fit a poor choice on raw matches?

    A few wrong pairs can dominate a least-squares fit. RANSAC fits on random minimal samples and keeps the model with the most inliers.
  4. 4. You call FlannBasedMatcher with the KD-tree index on ORB descriptors and it fails. What is the most likely reason?

    Use the LSH index for binary descriptors, or the KD-tree index with float32 descriptors such as SIFT's.
  5. 5. What does cv2.findHomography return when it cannot find a consistent transform?

    With too few or inconsistent matches the returned H is None. Check it, and check the inlier count, before using the transform.

Summary

  • Matching pairs each query descriptor with its nearest train descriptor: Hamming distance for binary descriptors, L2 for float ones.
  • BFMatcher is exact; FLANN is approximate and faster on large sets, and KD-trees need float32.
  • The ratio test (best < 0.75 * second) with knnMatch(k=2) discards ambiguous matches.
  • cv2.findHomography(src, dst, cv2.RANSAC, 5.0) finds a 3 by 3 transform and an inlier mask, or None.
  • A homography describes a plane or a rotating camera; check the inlier count before trusting it.
  • RANSAC and Hamming matching are simple enough to write in NumPy, which is what the live examples did.

Next: Reading and Writing Video