Fast corners, a binary fingerprint and an orientation: features quick enough for a phone.
Oriented FAST and Rotated BRIEF
Use cases: mobile devices, embedded systems, real-time applications.
FAST keypoint detection: find corners quickly
Harris corner measure: rank them and keep the top N
Scale pyramid: detect at multiple scales
Orientation assignment: the intensity centroid method
Rotated BRIEF: a binary descriptor aligned with that orientation
FAST (Features from Accelerated Segment Test) checks the 16 pixels on a circle around a candidate.
If N consecutive pixels are all brighter than \(p + t\) or all darker than \(p - t\), it is a corner. ORB uses N = 9.
Only simple comparisons, so it is very fast. ORB's improvement: rank the corners with the Harris measure and keep the best.
Problem: BRIEF is not rotation invariant. Solution: compute an orientation, then rotate the BRIEF pattern to match.
Intensity centroid of the patch around the keypoint:
Result: turn the image and θ turns with it, so a descriptor measured relative to θ stays the same: rotation invariance.
BRIEF: Binary Robust Independent Elementary Features.
256 pixel pairs → 256 comparisons → 256 bits (32 bytes). Very fast to compute and to match: XOR and a bit count.
import cv2
# create ORB detector
orb = cv2.ORB_create() # ans:
# detailed parameters
orb = cv2.ORB_create(nfeatures=500, scaleFactor=1.2, nlevels=8, # ans:
edgeThreshold=31, firstLevel=0, WTA_K=2, # ans:
scoreType=cv2.ORB_HARRIS_SCORE, # ans:
patchSize=31, fastThreshold=20) # ans:
# nfeatures: max keypoints to retain
# ans: 500 strongest features
# scaleFactor: pyramid scale factor
# ans: 1.2 means each level is 1/1.2 = 83% of the previous
# nlevels: number of pyramid levels
# ans: 8 levels for multi-scale detection
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
orb = cv2.ORB_create(nfeatures=1000)
# detect keypoints only
keypoints = orb.detect(gray, None) # ans:
# detect and compute descriptors
keypoints, descriptors = orb.detectAndCompute(gray, None) # ans:
# descriptor is binary
print(descriptors.shape) # ans:
# ans: (N, 32): 32 bytes = 256 bits
print(descriptors.dtype) # ans:
# ans: uint8
computing…
Drawn like DRAW_RICH_KEYPOINTS: circle size = pyramid level, line = orientation. Colour = level.
orb = cv2.ORB_create()
kp, des = orb.detectAndCompute(gray, None)
# simple keypoint drawing
img_kp = cv2.drawKeypoints(img, kp, None, color=(0, 255, 0)) # ans:
# rich keypoints (with size and orientation)
img_kp = cv2.drawKeypoints(img, kp, None, # ans:
flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS) # ans:
# ans: circles show scale, lines show orientation
Distance metric: Hamming distance, the count of differing bits. Fast: XOR plus a bit count.
# create ORB matcher (Hamming distance)
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True) # ans:
# detect in two images
orb = cv2.ORB_create()
kp1, des1 = orb.detectAndCompute(gray1, None)
kp2, des2 = orb.detectAndCompute(gray2, None)
# match
matches = bf.match(des1, des2) # ans:
matches = sorted(matches, key=lambda x: x.distance) # ans:
See it run on a real photo in Keypoint Matching.
Choice: ORB for speed, SIFT for accuracy.
Why? The same feature can appear at different sizes, so ORB detects features at several scales. Level k is the image shrunk by \(\text{scaleFactor}^k\).
WTA_K is the number of points compared in each BRIEF test.
WTA_K=2Compare 2 points: one bit per test (the default, 256 bits). Match with NORM_HAMMING.
WTA_K=3Compare 3 points; the test outputs which is brightest (2 bits). More robust.
WTA_K=4Compare 4 points (2 bits). Even more robust. For 3 or 4, match with NORM_HAMMING2.
Trade-off: robustness vs speed.
Answer first, then press → to check.
What does ORB stand for?
Oriented FAST and Rotated BRIEF.
Which detector does ORB use?
The FAST corner detector.
Which descriptor does ORB use?
The BRIEF binary descriptor, rotated.
How many bits in an ORB descriptor?
256 bits (32 bytes).
Which distance metric for ORB?
Hamming distance (count of differing bits).
Why is ORB fast?
A binary descriptor, simple comparisons and fast matching.
How does ORB handle rotation?
It assigns an orientation using the intensity centroid.
What is scaleFactor?
The scale ratio between pyramid levels.
The advantage of binary descriptors?
Fast to compute and to match (XOR + bit count).
The ORB vs SIFT trade-off?
ORB is faster but less accurate; SIFT is slower but more robust.
# create ORB with 2000 features
orb = cv2.ORB_create(nfeatures=2000) # ans:
# detect and compute
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
keypoints, descriptors = orb.detectAndCompute(gray, None) # ans:
# check descriptor shape
print(descriptors.shape) # ans:
# ans: (N, 32)
# create Hamming matcher
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True) # ans:
# match ORB features
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) # ans:
matches = sorted(matches, key=lambda x: x.distance) # ans:
img_matches = cv2.drawMatches(img1, kp1, img2, kp2, matches[:50], None, flags=2) # ans:
# ORB with more pyramid levels
orb = cv2.ORB_create(nlevels=12, scaleFactor=1.2) # ans:
# ans: 12 levels for a wider scale range
# draw rich keypoints
orb = cv2.ORB_create()
kp, des = orb.detectAndCompute(gray, None)
img_kp = cv2.drawKeypoints(img, kp, None, # ans:
flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS) # ans:
# ORB with WTA_K=3
orb = cv2.ORB_create(WTA_K=3) # ans:
# ans: more robust descriptor; match it with NORM_HAMMING2