Keypoints, descriptors and feature matching for robotics

How does a robot know it is looking at the same corner of a table from two different positions? It finds a few distinctive points in each image, describes each one with a short list of numbers, and pairs up points whose numbers are similar. That is feature matching, and it sits at the start of visual SLAM, visual odometry, object recognition and image stitching.

$$ \text{Image} \;\rightarrow\; \underbrace{\text{Keypoints}}_{\text{where?}} \;\rightarrow\; \underbrace{\text{Descriptors}}_{\text{what does it look like?}} \;\rightarrow\; \underbrace{\text{Matching}}_{\text{which is which?}} \;\rightarrow\; \text{Robot motion} $$

An analogy. In a library, the keypoint is where a book stands on the shelf, the descriptor is its title, author and summary, and matching is finding the book in another library whose description is most similar.

1. Keypoints: where to look

A keypoint is a spot in the image that can be found again reliably, even when the camera moves, rotates or the light changes. Corners and blobs are good keypoints; a plain white wall is not. Each keypoint stores:

• its position \((x, y)\) in the image,
• its scale, the size of the region it covers,
• its orientation, the dominant direction of the image gradient around it,
• its response, how strong the detection is.

Harris: corners from image gradients

The Harris detector looks at how the brightness changes in a small window. With image derivatives \(I_x, I_y\) and a Gaussian window \(w\), it builds the structure tensor

$$ \mathbf{M} = \sum_{x,y} w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} $$

and scores each pixel with

$$ R = \det(\mathbf{M}) - k\,\big(\operatorname{trace}\mathbf{M}\big)^2, \qquad k \approx 0.04 \text{ to } 0.06 $$

FAST: corners by comparing pixels

FAST looks at the 16 pixels on a circle of radius 3 around a pixel \(p\). If at least \(n\) neighbouring pixels on the circle are all brighter than \(I(p) + t\), or all darker than \(I(p) - t\), then \(p\) is a corner. With \(n = 9\) or \(12\) this needs only a few comparisons per pixel, which makes FAST very fast.

Comparing detectors

2. Descriptors: what the point looks like

A descriptor is a vector of numbers that summarises the patch around a keypoint. A good descriptor is distinctive (different patches give different vectors), invariant (the same patch seen differently gives a similar vector), compact and robust to noise.

SIFT: 128 numbers from gradient histograms

Around each keypoint, SIFT computes the gradient magnitude and direction at every pixel of the smoothed image \(L\):

$$ m = \sqrt{\big(L_{x+1,y} - L_{x-1,y}\big)^2 + \big(L_{x,y+1} - L_{x,y-1}\big)^2}, \qquad \theta = \operatorname{atan2}\!\big(L_{x,y+1} - L_{x,y-1},\; L_{x+1,y} - L_{x-1,y}\big) $$

The 16 × 16 region is split into a 4 × 4 grid of cells, and each cell gets an 8-bin histogram of gradient directions:

$$ 4 \times 4 \text{ cells} \times 8 \text{ directions} = 128 \text{ numbers} $$

All directions are measured relative to the keypoint's orientation, which is what makes SIFT rotation invariant.

ORB: 256 yes/no answers

ORB's descriptor (rotated BRIEF) compares the brightness of 256 fixed pairs of pixels \((\mathbf{a}_i, \mathbf{b}_i)\) in the smoothed patch, rotated to the keypoint's orientation. Each comparison gives one bit:

$$ \tau_i = \begin{cases} 1 & \text{if } I(\mathbf{a}_i) < I(\mathbf{b}_i) \\ 0 & \text{otherwise} \end{cases} \qquad \text{descriptor} = \tau_1 \tau_2 \ldots \tau_{256} $$

That is 256 bits, or 32 bytes. Binary descriptors are tiny and can be compared extremely fast.

A toy example

Take this 3 × 3 patch of brightness values:

A simple four-number descriptor could be:

Descriptor: \([\,50.33,\ 1.67,\ 2.33,\ 7.56\,]\). Real descriptors are longer and normalised, but the idea is the same.

3. Matching: which point is which

To match, we compare each descriptor in image 1 with the descriptors in image 2 and pick the closest one, its nearest neighbour.

Measuring distance

For float descriptors such as SIFT, use the Euclidean distance:

$$ d(\mathbf{a}, \mathbf{b}) = \sqrt{\sum_{i=1}^{n} (a_i - b_i)^2} $$

Example: \(\mathbf{a} = [2, 5, 1]\), \(\mathbf{b} = [4, 3, 2]\) gives \(d = \sqrt{4 + 4 + 1} = 3\).

For binary descriptors such as ORB, use the Hamming distance, the number of bits that differ:

$$ d_H(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{n} a_i \oplus b_i $$

Example: 10110101 and 10011101 differ in bits 3 and 5, so \(d_H = 2\). Computers do this with one XOR and a bit count, which is why ORB matching is so fast.

The ratio test

The closest match is not always a correct one. In repetitive scenes (windows, tiles) a point may have several look-alikes. Lowe's ratio test accepts a match only if the best candidate is clearly better than the second best:

$$ \frac{d_1}{d_2} < r, \qquad r \approx 0.7 \text{ to } 0.8 $$

Worked example. Query \(Q = [2.0, 5.0, 1.7]\) and three candidates:

The nearest neighbour is D3, but D1 is almost as close: \(0.300 / 0.332 = 0.90 > 0.75\). The match is ambiguous and rejected. Throwing away a few good matches is much better than keeping wrong ones.

Brute force or approximate search

4. From matches to robot motion

In a visual SLAM front end, matching runs on every camera frame:

$$ \text{New frame} \;\rightarrow\; \text{ORB features} \;\rightarrow\; \text{Match to previous frame or map} \;\rightarrow\; \text{Reject outliers (RANSAC)} \;\rightarrow\; \text{Estimate motion} \;\rightarrow\; \text{Update map} $$

Matching statistics for one frame

Out of 155 features, about 120 survive the ratio test. RANSAC then removes the remaining wrong matches by keeping only those consistent with a single camera motion.

Worked example: how far did the robot move?

Suppose a robot measures three landmarks (in metres, in its own frame) before and after a move. We want the rotation \(\theta\) and translation \(\mathbf{t}\) that map the new view onto the old one:

$$ \mathbf{p}^{(0)}_i = \mathbf{R}(\theta)\,\mathbf{p}^{(1)}_i + \mathbf{t}, \qquad \mathbf{R}(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} $$

Step 1, centroids. \(\bar{\mathbf{p}}^{(0)} = (3.00, 0.17)\) and \(\bar{\mathbf{p}}^{(1)} = (2.47, -0.37)\).

Step 2, centre the points: \(\mathbf{a}_i = \mathbf{p}^{(0)}_i - \bar{\mathbf{p}}^{(0)}\) and \(\mathbf{b}_i = \mathbf{p}^{(1)}_i - \bar{\mathbf{p}}^{(1)}\).

Step 3, rotation. The best 2D rotation in the least-squares sense is

$$ \theta = \operatorname{atan2}\!\Big(\sum_i (b_{i,x} a_{i,y} - b_{i,y} a_{i,x}),\; \sum_i (b_{i,x} a_{i,x} + b_{i,y} a_{i,y})\Big) = \operatorname{atan2}(0.72,\; 4.12) \approx 10^\circ $$

Step 4, translation. \(\mathbf{t} = \bar{\mathbf{p}}^{(0)} - \mathbf{R}(\theta)\,\bar{\mathbf{p}}^{(1)} \approx (0.50,\ 0.10)\) m.

So the robot drove about half a metre forward, slightly to the left, and turned 10° to the left. In 3D the same idea, with an SVD instead of atan2, is the Kabsch / Umeyama method; with a single camera and no depth, OpenCV estimates the essential matrix instead and recovers the rotation and the direction of travel.

5. Code: matching two images with OpenCV

import cv2

def match(img1_path, img2_path, ratio=0.75):
    img1 = cv2.imread(img1_path, cv2.IMREAD_GRAYSCALE)
    img2 = cv2.imread(img2_path, cv2.IMREAD_GRAYSCALE)

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

    matcher = cv2.BFMatcher(cv2.NORM_HAMMING)        # Hamming for binary ORB descriptors
    pairs = matcher.knnMatch(des1, des2, k=2)        # two nearest neighbours each

    good = [m for m, n in (p for p in pairs if len(p) == 2)
            if m.distance < ratio * n.distance]      # Lowe's ratio test

    print(f"{len(kp1)} and {len(kp2)} keypoints, {len(good)} good matches")
    out = cv2.drawMatches(img1, kp1, img2, kp2, good[:50], None,
                          flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)
    cv2.imwrite("matches.png", out)
    return kp1, kp2, good

kp1, kp2, good = match("frame1.png", "frame2.png")

For SIFT, use cv2.SIFT_create() and cv2.BFMatcher(cv2.NORM_L2) instead.

6. Code: camera motion between two frames

With the camera matrix \(\mathbf{K}\) from calibration, the matches give the relative motion directly:

import numpy as np
import cv2

K = np.array([[525.0,   0.0, 319.5],    # fx, 0, cx
              [  0.0, 525.0, 239.5],    # 0, fy, cy
              [  0.0,   0.0,   1.0]])

pts1 = np.float32([kp1[m.queryIdx].pt for m in good])
pts2 = np.float32([kp2[m.trainIdx].pt for m in good])

# RANSAC keeps only matches that agree with one camera motion
E, inliers = cv2.findEssentialMat(pts1, pts2, K, method=cv2.RANSAC,
                                  prob=0.999, threshold=1.0)
n, R, t, _ = cv2.recoverPose(E, pts1, pts2, K, mask=inliers)

angle = np.degrees(np.arccos(np.clip((np.trace(R) - 1) / 2, -1, 1)))
print(f"{n} inliers, rotation {angle:.1f} deg, direction of travel {t.ravel()}")

With one camera, t has length 1: the direction is known but not the distance. A stereo or depth camera, an IMU or a known object size supplies the missing scale.

7. Code: nearest neighbour and ratio test from scratch

import numpy as np

def match_ratio(query, database, ratio=0.75):
    """Return (query index, database index) pairs that pass the ratio test."""
    matches = []
    for i, q in enumerate(query):
        d = np.linalg.norm(database - q, axis=1)   # Euclidean distance to every entry
        best, second = np.argsort(d)[:2]
        if d[best] < ratio * d[second]:
            matches.append((i, int(best)))
    return matches

Q  = np.array([[2.0, 5.0, 1.7]])
DB = np.array([[2.1, 5.3, 1.8], [4.2, 3.1, 2.0], [1.9, 4.8, 1.5]])
print(match_ratio(Q, DB))   # [] : rejected as ambiguous, as in the worked example

Common problems and fixes

Further reading

• OpenCV feature detection tutorials
• Multiple View Geometry, Hartley and Zisserman
• ORB-SLAM3, a complete feature-based SLAM system
• The Visual SLAM guide on this site, which continues where this post ends

Try it yourself

1. Implement the Harris response \(R\) with NumPy and compare it with cv2.cornerHarris.
2. Match two photos of your desk with ORB and with SIFT. Which gives more good matches, and which is faster?
3. Change the ratio threshold from 0.6 to 0.9 and count the wrong matches.
4. Simulate a robot moving in 2D, add noise to the landmark positions and recover its motion with the method from section 4.