Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 54 ยท Features and Matching

Corners and Keypoints: Harris, Shi-Tomasi, ORB

Learn what makes a good image feature, then use cornerHarris, goodFeaturesToTrack and ORB in OpenCV. Compute the Harris response yourself with NumPy.

Template matching compares a whole patch pixel by pixel, so it breaks as soon as the object is rotated, scaled or lit differently. Feature detection takes another route: find a few special points that are easy to recognize again, describe the neighborhood of each one with a compact vector, and compare those vectors instead of raw pixels. Those points are called keypoints or interest points.

This lesson is about the first half of that idea: which points make good features and how OpenCV finds them. The second half, describing and matching them, is the next lesson, Feature Matching and Homography.

The cv2 calls in this lesson are shown as read-only code because opencv-python does not run in the browser. The live examples compute the same ideas with NumPy, and each one says what part is a stand-in.

What makes a good feature?

Look at three small windows cut from an image. A window on a flat wall looks the same if you slide it in any direction, so you cannot say where you are. A window on a straight edge looks the same if you slide it along the edge, so you can only locate it across the edge. A window on a corner changes whatever way you slide it, so its position is unambiguous.

Slide a small window around

Flat area Nothing changes in any direction. Useless.
Edge Changes across it, not along it. Ambiguous.
Corner Changes in every direction. Easy to locate.

Good features are the corners and blobs, not the flat areas and plain edges.

1 / 2

The Harris corner detector

Harris turns the window idea into math. For each pixel it looks at the image gradients Ix and Iy (see Gradients, Sobel and Laplacian) inside a small window and builds a 2 by 2 matrix from their sums:

TEXT
M = [ sum(Ix*Ix)   sum(Ix*Iy) ]
    [ sum(Ix*Iy)   sum(Iy*Iy) ]

The two eigenvalues of M describe how strongly the image changes in the two main directions. Both small means flat, one large and one small means an edge, both large means a corner. Harris avoids computing eigenvalues with a score:

TEXT
R = det(M) - k * trace(M)^2        (k is usually 0.04 to 0.06)

R is large and positive at corners, negative at edges and close to zero on flat areas. In OpenCV:

Python
import cv2
import numpy as np

img = cv2.imread("building.png")
gray = np.float32(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY))

# blockSize=2: window size, ksize=3: Sobel aperture, k=0.04
response = cv2.cornerHarris(gray, 2, 3, 0.04)

# Keep only strong responses and mark them in red
img[response > 0.01 * response.max()] = (0, 0, 255)

cornerHarris needs a float32 or uint8 single-channel image and returns a float32 response map the same size as the input, not a list of points. You choose the cutoff yourself, usually a fraction of the maximum, as above.

The next example reproduces the whole computation in NumPy on a synthetic image: a bright square on a dark background. It uses simple central differences instead of Sobel and a plain box window, so the numbers are not identical to OpenCV's, but the structure is the same.

Python Harris response in NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed map shows small clusters of # around the four corners of the square and nothing along the straight sides or inside. The straight sides give a negative R, which is why the minimum is far below zero. A real detector adds one more step, shown below.

Picking the best corners

A threshold on R gives blobs of neighboring pixels around each corner, not single points. Two cleanups fix that: non-maximum suppression (keep a pixel only if it is the largest in its neighborhood) and keeping only the strongest N.

Shi-Tomasi is a small change to Harris that often works better for tracking. Instead of the score R it uses the smaller eigenvalue of M directly, and a pixel is a corner if even its weaker direction changes a lot. OpenCV wraps it, with non-maximum suppression and a minimum distance between points, in one call:

Python
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

corners = cv2.goodFeaturesToTrack(
    gray,
    maxCorners=100,      # keep at most this many
    qualityLevel=0.01,   # relative to the best corner
    minDistance=10,      # pixels between accepted corners
)
# corners has shape (N, 1, 2); each entry is (x, y) as float32
for (x, y) in corners.reshape(-1, 2):
    cv2.circle(img, (int(x), int(y)), 4, (0, 255, 0), -1)

Pass useHarrisDetector=True to make the same function rank by the Harris score instead. Remember the coordinate order: corners come back as (x, y), but indexing an image is img[y, x] (see Images Are NumPy Arrays).

The next TryIt computes the Shi-Tomasi score in closed form (the smaller eigenvalue of a 2 by 2 matrix has a simple formula), then selects points greedily with a minimum distance, which is the same idea as minDistance. It builds on Sxx, Syy and Sxy computed the same way as above.

Python Shi-Tomasi score and minimum distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see points clustered at the corners of both rectangles, each one separated from the others by at least the minimum distance. Raising min_distance thins them out; lowering quality admits weaker candidates.

ORB: keypoints with descriptors

Harris and Shi-Tomasi find corners but do not describe them, and a corner of a 10 pixel square looks like a corner of a 100 pixel square only to a human. They are also not scale invariant: zoom in and a corner turns into a gentle curve.

ORB (Oriented FAST and Rotated BRIEF) is OpenCV's free, fast, general-purpose answer. It does four things:

  1. Detects corners with the FAST test (compare a pixel with a ring of 16 neighbors) on several scales of an image pyramid, so it finds the same feature at different sizes.
  2. Ranks them with a Harris score and keeps the best.
  3. Measures an orientation for each keypoint, so the descriptor can be rotated to a canonical direction.
  4. Builds a 256-bit binary descriptor (rotated BRIEF) by comparing pairs of pixel intensities around the keypoint.
Python
orb = cv2.ORB_create(nfeatures=500)
keypoints, descriptors = orb.detectAndCompute(gray, None)

print(len(keypoints), descriptors.shape)   # for example: 500 (500, 32)

# Each keypoint knows where it is, how big and which way it points
kp = keypoints[0]
print(kp.pt, kp.size, kp.angle, kp.response)

vis = cv2.drawKeypoints(img, keypoints, None, color=(0, 255, 0),
                        flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

descriptors is a uint8 array with one row of 32 bytes (256 bits) per keypoint. If the image has too little texture, descriptors is None, so check before using it. The second argument of detectAndCompute is an optional mask limiting where keypoints may appear.

The next stand-in does the "compare pairs of pixels" step of a BRIEF-style descriptor on a tiny patch, using a fixed random pattern, and shows why the result survives a brightness change. This is the idea of ORB's descriptor but not its exact sampling pattern or rotation step.

Python A binary descriptor from pixel comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Adding a constant to every pixel never changes a < comparison, so the brighter patch gives distance 0. An inverted patch flips almost every comparison. An unrelated patch differs in about half of the bits, which is what chance looks like. The next lesson uses exactly this Hamming distance to match keypoints.

SIFT and friends

SIFT (Scale-Invariant Feature Transform) detects blobs across scales and describes them with a 128-number float vector built from gradient histograms. It is slower than ORB but more distinctive, and it handles scale and rotation well. Its patent expired in 2020, and since OpenCV 4.4 it ships in the main module:

Python
sift = cv2.SIFT_create()
keypoints, descriptors = sift.detectAndCompute(gray, None)
print(descriptors.dtype, descriptors.shape)   # float32 (N, 128)

On older versions you needed the opencv-contrib-python package (see Installing OpenCV). Other detectors exist, such as AKAZE, BRISK and FAST on its own, but ORB (fast, free, binary) and SIFT (accurate, float) cover most needs. Float descriptors like SIFT's are compared with L2 distance and binary ones like ORB's with Hamming distance.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why are corners better features than straight edges?

    On a straight edge you can slide along the edge without any change, so the position along it is ambiguous. A corner pins the position down in both directions.
  2. 2. What does cv2.cornerHarris return?

    cornerHarris returns a response image. You choose a cutoff, typically a fraction of its maximum, and extract points from it.
  3. 3. What is different about cv2.goodFeaturesToTrack compared with a plain threshold on a Harris map?

    goodFeaturesToTrack returns a clean list of the best, well-spaced points (by default ranked with the Shi-Tomasi score), so you do not clean up blobs yourself.
  4. 4. What kind of descriptor does ORB produce, and how are two of them compared?

    ORB stores 32 bytes (256 bits) per keypoint. Counting the differing bits (Hamming distance) is very fast.
  5. 5. Which statement about SIFT in current OpenCV is correct?

    cv2.SIFT_create() is part of the main module since OpenCV 4.4 and produces float32 descriptors of length 128.

Summary

  • Good features are corners and blobs: places where the image changes in every direction.
  • Harris scores each pixel with R = det(M) - k * trace(M)^2; cornerHarris returns the map and you threshold it.
  • Shi-Tomasi uses the smaller eigenvalue, and goodFeaturesToTrack adds non-maximum suppression and a minimum distance.
  • ORB detects FAST corners on an image pyramid, adds orientation and a 256-bit binary descriptor.
  • SIFT gives 128-float descriptors, is more distinctive but slower, and is in the main module since OpenCV 4.4.
  • Detecting points is only half the job: you also need descriptors and a way to compare them.

Next: Feature Matching and Homography