Keypoints that survive zooming, turning and relighting, and the 128 numbers that describe each one.
SIFT: Scale-Invariant Feature Transform (David Lowe, 1999).
Detects features at multiple scales.
Assigns an orientation to each keypoint.
Robust to lighting changes.
Copes with partial occlusion.
Patent expired in 2020: now free to use commercially (cv2.SIFT_create is in the main OpenCV package).
Original → Blur → Downsample → Blur → Downsample …
DoG (Difference of Gaussians) approximates the Laplacian:
$$\text{DoG} = G(k\sigma) - G(\sigma)$$
σ grows by k = 21/3 per level. Each DoG is the difference of its two neighbours above, scaled up so you can see it: grey is 0, bright and dark are blobs at that scale.
DoG at the scale above
this scale
DoG at the scale below
A pixel is a candidate keypoint if it is larger (or smaller) than all 26 neighbours: 8 in its own DoG image and 9 in each neighbouring scale.
computing…
DoG extrema over 3 octaves, low contrast and edge responses rejected, dominant orientation from a 36-bin gradient histogram. Circle radius = scale.
import cv2
# create SIFT with default parameters
sift = cv2.SIFT_create() # ans:
# custom parameters
sift = cv2.SIFT_create(nfeatures=500, nOctaveLayers=3, # ans:
contrastThreshold=0.04, edgeThreshold=10, sigma=1.6) # ans:
# nfeatures: max features to retain (0 = all)
# ans: keeps the 500 best features
# nOctaveLayers: layers per octave
# ans: more layers = more scales, slower
# contrastThreshold: filter low-contrast
# ans: higher = fewer, stronger features
# edgeThreshold: filter edge responses
# ans: higher = more edge-like features accepted
# sigma: initial gaussian blur
# ans: 1.6 is the standard value
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
sift = cv2.SIFT_create()
# detect keypoints only
keypoints = sift.detect(gray, None) # ans:
# detect and compute descriptors
keypoints, descriptors = sift.detectAndCompute(gray, None) # ans:
# keypoint properties
kp = keypoints[0] # ans:
x, y = kp.pt # ans:
# ans: position
size = kp.size # ans:
# ans: scale
angle = kp.angle # ans:
# ans: orientation (degrees)
response = kp.response # ans:
# ans: strength of the detector response
A 128-dimensional vector built from gradients around the keypoint:
Normalization makes it illumination invariant. Matching: L2 (Euclidean) distance.
SURF: Speeded-Up Robust Features (Herbert Bay, 2006).
Uses integral images.
Close to SIFT's matching quality.
The extended descriptor has 128.
Caveat: still patented; it needs opencv-contrib (built with the non-free modules).
# requires opencv-contrib-python
# create SURF detector
surf = cv2.xfeatures2d.SURF_create() # ans:
# set Hessian threshold
surf.setHessianThreshold(400) # ans:
# ans: lower = more features, weaker ones
# detect and compute
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
keypoints, descriptors = surf.detectAndCompute(gray, None) # ans:
# use extended descriptor (128-dim instead of 64)
surf.setExtended(True) # ans:
# ans: 128 dimensions for more distinctiveness
Both: scale and rotation invariant, with robust descriptors.
# detect SIFT in two images
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(gray1, None)
kp2, des2 = sift.detectAndCompute(gray2, None)
# brute-force matcher with L2 norm
bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True) # ans:
matches = bf.match(des1, des2) # ans:
matches = sorted(matches, key=lambda x: x.distance) # ans:
# draw matches
img_matches = cv2.drawMatches(img1, kp1, img2, kp2, matches[:30], None, flags=2) # ans:
Problem: ambiguous matches, when several descriptors look alike.
Solution: compare the best match with the second-best match.
0.75 is the standard threshold: lower it for stricter matching, raise it for looser.
See it filter real matches in Keypoint Matching.
if distance(1st) < 0.75 * distance(2nd):
accept match
else:
reject # ambiguous
# BFMatcher with kNN (k=2)
bf = cv2.BFMatcher(cv2.NORM_L2)
matches = bf.knnMatch(des1, des2, k=2) # ans:
# ans: returns the 2 best matches for each descriptor
# apply ratio test
good_matches = []
for m, n in matches: # ans:
if m.distance < 0.75 * n.distance: # ans:
good_matches.append(m) # ans:
# draw good matches
img_matches = cv2.drawMatches(img1, kp1, img2, kp2, good_matches, None, flags=2)
Answer first, then press → to check.
What does SIFT stand for?
Scale-Invariant Feature Transform.
How many dimensions in a SIFT descriptor?
128.
What is DoG?
Difference of Gaussians; it approximates the Laplacian.
Why multiple scales in SIFT?
Features appear at different sizes across images.
The main advantage of SURF over SIFT?
3 to 5× faster, using integral images.
What is Lowe's ratio test?
Compare the best match with the second best; reject if the ratio is above 0.75.
Why the ratio test?
It filters ambiguous matches (several similar descriptors).
The SIFT descriptor's grid structure?
4×4 cells with an 8-bin histogram each = 128 values.
Which distance metric for SIFT?
L2 (Euclidean) distance.
Is SIFT rotation invariant?
Yes: it assigns an orientation to each keypoint.
# create SIFT with 1000 features
sift = cv2.SIFT_create(nfeatures=1000) # ans:
# detect and compute SIFT
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
keypoints, descriptors = sift.detectAndCompute(gray, None) # ans:
# get first keypoint properties
kp = keypoints[0] # ans:
x, y = kp.pt # ans:
size = kp.size # ans:
angle = kp.angle # ans:
# match SIFT features
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(gray1, None)
kp2, des2 = sift.detectAndCompute(gray2, None)
bf = cv2.BFMatcher(cv2.NORM_L2, crossCheck=True) # ans:
matches = bf.match(des1, des2) # ans:
matches = sorted(matches, key=lambda x: x.distance) # ans:
# apply ratio test
bf = cv2.BFMatcher(cv2.NORM_L2)
matches = bf.knnMatch(des1, des2, k=2) # ans:
good = [m for m, n in matches if m.distance < 0.75 * n.distance] # ans:
# SIFT with higher contrast threshold
sift = cv2.SIFT_create(contrastThreshold=0.08) # ans:
# ans: fewer features, higher quality
# draw SIFT keypoints with rich info
sift = cv2.SIFT_create()
kp, des = sift.detectAndCompute(gray, None)
img_kp = cv2.drawKeypoints(img, kp, None, # ans:
flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS) # ans:
# ans: shows size and orientation
# stricter ratio test
bf = cv2.BFMatcher(cv2.NORM_L2)
matches = bf.knnMatch(des1, des2, k=2)
good = [m for m, n in matches if m.distance < 0.6 * n.distance] # ans:
# ans: 0.6 is stricter than 0.75: fewer but better matches