Feature Detection and Matching

To track motion or build maps, a robot needs to find the same physical points in two images. It first detects distinctive points, such as corners, then describes the patch around each one, then matches descriptions between images. Corners work because they look different from every nearby spot.

Second view rotation Second view shift Corner threshold Use the ratio test Ratio test limit

Corners

The Harris detector looks at how the image gradients $I_x, I_y$ vary in a small window. If brightness changes strongly in two directions, the point is a corner:

$$M = \sum_{\text{window}} \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} \qquad R = \det M - k\,(\operatorname{tr} M)^2$$

Matching

Each corner is described by its normalized patch. For each corner in the left image, find the closest patch on the right. The ratio test, from Lowe's SIFT paper, keeps a match only if the best match is clearly better than the second best: $d_1 / d_2 < 0.8$.

What to notice

With a small rotation most matches are right. Rotate more and simple patch matching fails, since the patches no longer look alike, so wrong matches appear. Real descriptors like ORB and SIFT measure each corner's orientation and rotate the patch first, which makes them rotation invariant. The ratio test throws out ambiguous matches, so fewer wrong ones survive, and later steps like RANSAC remove the rest.