Matching Images
The same point in two photos.
Your phone makes a panorama by finding the same points in overlapping photos, and joining them together. Augmented reality pins objects to the real world in the same way. It all begins with matching.
- Phones stitch panoramas
- AR pins objects to the world
- It all begins with matching
Matching across views
For each keypoint in the first photo, we look for the closest descriptor in the second. Then lines connect the matching points. Most are correct. A few are wrong, since some patches just look alike. We've got to filter those out.
Matching with a ratio test
We create a rotated and shrunken copy of the photo. We find ORB features in both. For each point, we look up its two best matches. Lowe's ratio test keeps a match only if the best is clearly better than the second best. If they're nearly equal, it's ambiguous, so we drop it. Run it. Lines connect the same points, even with the image rotated and smaller. That was impossible with template matching.
import cv2
import matplotlib.pyplot as plt
from skimage import data
a = cv2.cvtColor(data.astronaut(), cv2.COLOR_RGB2GRAY)
h, w = a.shape
M = cv2.getRotationMatrix2D((w / 2, h / 2), 20, 0.8)
b = cv2.warpAffine(a, M, (w, h))
orb = cv2.ORB_create(800)
p1, d1 = orb.detectAndCompute(a, None)
p2, d2 = orb.detectAndCompute(b, None)
pairs = cv2.BFMatcher(cv2.NORM_HAMMING).knnMatch(d1, d2, k=2)
good = [m for m, n in pairs if m.distance < 0.75 * n.distance]
out = cv2.drawMatches(a, p1, b, p2, good[:40], None, flags=2)
plt.figure(figsize=(9, 4.5)); plt.imshow(out); plt.axis("off")
plt.tight_layout(); plt.savefig("matches.png", dpi=110)
print("All matches:", len(pairs), " good:", len(good))All matches: 800 good: 405
Fitting a transform with RANSAC
A few bad matches can ruin any calculation. RANSAC solves this beautifully. Pick a few random matches, fit a model, and count how many others agree. Repeat many times, and keep the best. Bad matches simply get outvoted. Here, we warp an image with a known transform, then ask it to find the transform from matches alone. Run it. The numbers it found are very close to the truth. RANSAC is everywhere in vision and robotics.
import cv2
import numpy as np
from skimage import data
a = cv2.cvtColor(data.astronaut(), cv2.COLOR_RGB2GRAY)
h, w = a.shape
true = np.array([[0.9, 0.1, 30], [-0.1, 0.9, 50], [0.0001, 0.0002, 1]])
b = cv2.warpPerspective(a, true, (w, h))
orb = cv2.ORB_create(1500)
p1, d1 = orb.detectAndCompute(a, None)
p2, d2 = orb.detectAndCompute(b, None)
good = [m for m, n in cv2.BFMatcher(cv2.NORM_HAMMING).knnMatch(d1, d2, k=2)
if m.distance < 0.75 * n.distance]
src = np.float32([p1[m.queryIdx].pt for m in good])
dst = np.float32([p2[m.trainIdx].pt for m in good])
H, mask = cv2.findHomography(src, dst, cv2.RANSAC, 4.0)
print("Matches used:", len(good), " agreed:", int(mask.sum()))
print("True: ", (true / true[2, 2])[0].round(2))
print("Found:", H[0].round(2))Matches used: 642 agreed: 626 True: [ 0.9 0.1 30. ] Found: [ 0.9 0.1 29.99]
Summary
Match features, filter with the ratio test, and fit with RANSAC. Next, we leave the flat image, and enter the three dimensional world. How does a camera turn a real scene into pixels?
Key takeaways- Ratio test removes ambiguous matches
- RANSAC ignores bad matches
- That's how panoramas are made