Find the same points in two images, then throw away the matches that lie.
Matching finds corresponding features between images.
Panoramas
Find an object in a scene
Stereo vision
Follow objects
Align images
Compare each descriptor in set 1 with all in set 2 and keep the closest. Simple, exact, slow for large sets.
Fast Library for Approximate Nearest Neighbors. Tree-based search (KD-tree, LSH): much faster, slightly less accurate.
Press → to search with each. The pink star is the query descriptor.
L1 (Manhattan): \(\sum_i |d_1[i] - d_2[i]|\)
L2 (Euclidean): \(\sqrt{\sum_i (d_1[i] - d_2[i])^2}\)
Hamming: the number of differing bits.
Hamming2: for ORB with WTA_K = 3 or 4, where bits come in pairs.
count the 1s → distance = 0
Lower distance = better match. XOR and a bit count is all a binary match costs.
import cv2
# BF matcher for ORB (binary)
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True) # ans:
# BF matcher for SIFT (float)
bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True) # ans:
# crossCheck: mutual best match
# ans: ensures A's best match is B AND B's best match is A
# match descriptors
matches = bf.match(des1, des2) # ans:
# returns DMatch objects
# ans: each has .distance, .queryIdx, .trainIdx
matches = bf.match(des1, des2)
m = matches[0] # ans:
# properties
distance = m.distance # ans:
# ans: lower is better
queryIdx = m.queryIdx # ans:
# ans: index in des1
trainIdx = m.trainIdx # ans:
# ans: index in des2
# sort by distance
matches = sorted(matches, key=lambda x: x.distance) # ans:
# ans: best matches first (lowest distance)
# simple match drawing
orb = cv2.ORB_create()
kp1, des1 = orb.detectAndCompute(gray1, None)
kp2, des2 = orb.detectAndCompute(gray2, None)
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = bf.match(des1, des2)
matches = sorted(matches, key=lambda x: x.distance)
# draw top 30 matches
img_matches = cv2.drawMatches(img1, kp1, img2, kp2, matches[:30], None, flags=2) # ans:
# ans: flags=2 means cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS
computing…
ORB written in JavaScript, running on the photo (left) and a rotated, scaled, re-lit copy (right).
k-nearest neighbours returns the k best matches for each descriptor. Its purpose: enabling Lowe's ratio test.
# kNN with k=2 (2 best matches)
bf = cv2.BFMatcher(cv2.NORM_HAMMING)
matches = bf.knnMatch(des1, des2, k=2) # ans:
# ans: returns a list of lists: [[best, 2nd_best], ...]
# each descriptor gets 2 matches
for matches_for_one in matches: # ans:
m, n = matches_for_one # ans:
# ans: best and 2nd best
No crossCheck here: it only works with k=1.
Purpose: filter ambiguous matches. Accept a match only if the best is much closer than the second best.
The amber mark is 0.75 × 2nd best: the best match must end before it. Typical thresholds: 0.7 to 0.8.
bf = cv2.BFMatcher(cv2.NORM_HAMMING)
matches = bf.knnMatch(des1, des2, k=2)
# apply ratio test
good_matches = []
for m, n in matches: # ans:
if m.distance < 0.75 * n.distance: # ans:
good_matches.append(m) # ans:
# ans: keeps only distinctive matches
# FLANN parameters for SIFT (KD-tree)
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) # ans:
# trees: number of KD-trees
# ans: more trees = better accuracy, slower
# checks: number of leaf nodes to search
# ans: higher = better accuracy, slower
# match
matches = flann.knnMatch(des1, des2, k=2) # ans:
# FLANN parameters for ORB (LSH)
FLANN_INDEX_LSH = 6
index_params = dict(algorithm=FLANN_INDEX_LSH, table_number=6,
key_size=12, multi_probe_level=1)
search_params = dict(checks=50)
flann = cv2.FlannBasedMatcher(index_params, search_params) # ans:
# descriptor type?
# ans: LSH hashes the binary uint8 descriptors as they are
# ans: (only a KD-tree index needs np.float32(des))
# match
matches = flann.knnMatch(des1, des2, k=2)
Homography: a 3×3 perspective transformation matrix mapping points in one image to the other.
RANSAC (random sample consensus) iteratively fits the transformation to random samples and keeps the one most points agree with. Those points are the inliers; the rest are outliers.
Use case: filter geometric outliers after matching. Here RANSAC fits a line (2 points per sample); a homography needs 4.
# need at least 4 matches
# extract matched point coordinates
src_pts = np.float32([kp1[m.queryIdx].pt for m in good_matches]).reshape(-1, 1, 2)
dst_pts = np.float32([kp2[m.trainIdx].pt for m in good_matches]).reshape(-1, 1, 2)
# find homography with RANSAC
M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 5.0) # ans:
# M: 3x3 transformation matrix
# ans: mask: inliers (1) vs outliers (0)
# filter matches using mask
inliers = [m for m, msk in zip(good_matches, mask.ravel()) if msk == 1] # ans:
5.0 is the reprojection threshold in pixels: a match further than that from where M sends it is an outlier.
Answer first, then press → to check.
What is keypoint matching?
Finding corresponding features between images.
Which distance for binary descriptors?
Hamming distance.
What is crossCheck in BFMatcher?
It keeps only mutual best matches (bidirectional).
What is the ratio test?
Compare the best and second-best match; reject if they are similar.
A typical ratio test threshold?
0.75 (or the 0.7 to 0.8 range).
BF vs FLANN?
BF is exact but slow; FLANN is approximate but fast.
What is kNN matching?
Finding the k nearest neighbours for each descriptor.
Why k=2 for the ratio test?
We need the second-best match to compare with the best.
What is RANSAC?
Random sampling to find inliers and filter outliers.
What is a homography?
A 3×3 perspective transformation matrix.
# BF matcher for ORB
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True) # ans:
matches = bf.match(des1, des2) # ans:
matches = sorted(matches, key=lambda x: x.distance) # ans:
# kNN matching
bf = cv2.BFMatcher(cv2.NORM_HAMMING)
matches = bf.knnMatch(des1, des2, k=2) # ans:
# ratio test
good = []
for m, n in matches: # ans:
if m.distance < 0.75 * n.distance: # ans:
good.append(m) # ans:
# FLANN for SIFT
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) # ans:
matches = flann.knnMatch(des1, des2, k=2) # ans:
# FLANN for ORB
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, search_params) # ans:
matches = flann.knnMatch(des1, des2, k=2) # ans:
# complete matching pipeline
orb = cv2.ORB_create()
kp1, des1 = orb.detectAndCompute(gray1, None)
kp2, des2 = orb.detectAndCompute(gray2, None)
bf = cv2.BFMatcher(cv2.NORM_HAMMING)
matches = bf.knnMatch(des1, des2, k=2)
good = [m for m, n in matches if m.distance < 0.75 * n.distance] # ans:
img_matches = cv2.drawMatches(img1, kp1, img2, kp2, good, None, flags=2) # ans:
# homography filtering
good_matches = [] # from ratio test
src_pts = np.float32([kp1[m.queryIdx].pt for m in good_matches]).reshape(-1, 1, 2)
dst_pts = np.float32([kp2[m.trainIdx].pt for m in good_matches]).reshape(-1, 1, 2)
M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 5.0) # ans:
inliers = [m for m, msk in zip(good_matches, mask.ravel()) if msk == 1] # ans:
print(f"Inliers: {len(inliers)}/{len(good_matches)}") # ans: