Template matching and corner features

Intermediate

Introduction

How does a program find a logo on a web page, a known part on a circuit board, or the same building in two holiday photos? The simplest way is to slide a picture of what you want (a template) over the image and score every position. That works when the object looks exactly the same each time. When the view changes, programs instead match keypoints: distinctive points, mostly corners, that can be found again from another angle. This lesson builds both ideas.

How it works

Template matching with SSD. Place the template's top-left corner at (r, c) and compare it with the window under it:

SSD(r, c) = Σ (window pixel − template pixel)²

A perfect match scores 0, so the best position is the smallest SSD. An H × W image and an h × w template give (H − h + 1) × (W − w + 1) scores, one per position where the template fits.

Normalised cross-correlation. SSD fails if the scene is brighter or darker than the template, because every difference grows. NCC first subtracts each patch's mean, then measures how well the patterns line up, divided by both patches' spread:

NCC = Σ (w − w̄)(t − t̄) / √(Σ (w − w̄)² × Σ (t − t̄)²)

It lies between −1 and 1, where 1 is a perfect match up to brightness and contrast and −1 is an inverted pattern. A flat window has no spread, so its score is defined as 0.

Why corners? Look at a small patch. On a flat area, moving the patch in any direction changes nothing. On an edge, moving along the edge changes nothing, but moving across it does. At a corner, every movement changes the patch. That makes corners easy to locate precisely, and therefore good keypoints.

The Harris detector. Compute gradients Ix and Iy (central differences such as I(x+1) − I(x−1) are enough), then sum over a small window:

Sxx = Σ Ix², Syy = Σ Iy², Sxy = Σ Ix·Iy

These form the structure tensor [[Sxx, Sxy], [Sxy, Syy]]. Its determinant Sxx·Syy − Sxy² is large only when brightness changes strongly in two different directions, while its trace Sxx + Syy measures total change. The Harris response combines them:

R = det − k × trace², with k around 0.04 to 0.06

Corners give large positive R, edges give negative R (the determinant is near 0 but the trace is not), and flat areas give R near 0. Real detectors then keep local maxima of R above a threshold.

Example

img = [
    [5, 5, 5, 5, 5],
    [5, 5, 9, 5, 5],
    [5, 9, 9, 9, 5],
    [5, 5, 9, 5, 2],
    [5, 5, 5, 2, 2],
]
plus = [[5, 9, 5], [9, 9, 9], [5, 9, 5]]


def ssd_map(img, t):
    k = len(t)
    return [[sum([(img[r + i][c + j] - t[i][j]) ** 2 for i in range(k) for j in range(k)]) for c in range(len(img[0]) - k + 1)] for r in range(len(img) - k + 1)]


scores = ssd_map(img, plus)
print("SSD at each position (smaller is better):", scores)
best = min([(v, r, c) for r, row in enumerate(scores) for c, v in enumerate(row)])
print("best match: top-left at row", best[1], "column", best[2], "with SSD", best[0])

corner = [
    "00000000",
    "00000000",
    "00000000",
    "00099999",
    "00099999",
    "00099999",
    "00099999",
    "00099999",
]


def harris(img, r, c, k=0.05):
    g = [(int(img[y][x + 1]) - int(img[y][x - 1]), int(img[y + 1][x]) - int(img[y - 1][x])) for y in range(r - 1, r + 2) for x in range(c - 1, c + 2)]
    sxx = sum([ix * ix for ix, iy in g])
    syy = sum([iy * iy for ix, iy in g])
    sxy = sum([ix * iy for ix, iy in g])
    return sxx * syy - sxy * sxy - k * (sxx + syy) ** 2


for name, (r, c) in [("corner", (3, 3)), ("edge", (3, 5)), ("flat area", (5, 5))]:
    print(f"Harris response at the {name}, row {r}, column {c}: {harris(corner, r, c):.1f}")
Open in compiler

Line by line

  1. The 5 × 5 image contains a plus shape of 9s on a background of 5s, plus some darker 2s in the corner.
  2. ssd_map scores all 3 × 3 positions; position (1, 1) scores 0 because the window is exactly the template.
  3. min over (score, row, column) tuples picks the smallest score, and the first position on ties.
  4. The second image (rows of digits) is 0 except for a bright block from row 3, column 3 to the bottom-right: one corner, two edges and flat areas.
  5. harris collects the central-difference gradients of the 3 × 3 window, sums the structure tensor and returns R.
  6. At the corner both Sxx and Syy are large, so R = 77419.8. On the top edge only Syy is non-zero, so the determinant is 0 and R = −11809.8. Inside the block nothing changes, so R = 0.

Expected result

SSD at each position (smaller is better): [[64, 80, 64], [80, 0, 89], [64, 89, 139]]
best match: top-left at row 1 column 1 with SSD 0
Harris response at the corner, row 3, column 3: 77419.8
Harris response at the edge, row 3, column 5: -11809.8
Harris response at the flat area, row 5, column 5: 0.0

In the real world

Factory cameras use template matching to check that parts sit in the right place. Panoramas, 3-D reconstruction, visual odometry in robots and augmented reality all match keypoints between images. Detectors such as Shi–Tomasi and FAST find corners; descriptors such as SIFT and ORB describe the patch around each one so it can be matched. In OpenCV (shown as text; it does not run on this site):

import cv2
import numpy as np

scores = cv2.matchTemplate(img, template, cv2.TM_CCOEFF_NORMED)    # zero-mean NCC
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(scores)          # locations as (x, y)
R = cv2.cornerHarris(np.float32(grey), 2, 3, 0.04)                 # blockSize, ksize, k
orb = cv2.ORB_create()
keypoints, descriptors = orb.detectAndCompute(grey, None)

Common mistakes

  • Taking the maximum SSD instead of the minimum.
  • Using SSD when lighting changes; use NCC.
  • Expecting template matching to handle rotation or scale changes; it does not, which is why keypoints exist.
  • Keeping every pixel with large R instead of local maxima, giving clusters of "corners".
  • Reading OpenCV locations as (row, column): minMaxLoc returns (x, y).

Best practices

  • Crop the template tightly around the object and match on greyscale images.
  • Prefer NCC scores near 1 and set a minimum score, so "best" does not mean "found" when the object is absent.
  • Blur slightly before computing Harris gradients to reduce noise.
  • For changing viewpoints, use keypoints and descriptors rather than whole templates.

Summary

Template matching slides a template over the image: SSD scores differences (smaller is better) and NCC scores normalised correlation (closer to 1 is better, and robust to brightness changes). Corners are points where brightness changes in two directions. Harris sums gradient products into the structure tensor and computes R = det − k × trace²: positive at corners, negative on edges, near 0 on flat areas.

Quick check

1. Which SSD score means a perfect match?
2. Why does NCC still find a template when the whole image is brighter?
3. What sign does the Harris response have on a straight edge?
4. Why are corners good keypoints?

Key takeaways

  • SSD measures difference directly and is fooled by brightness changes; NCC subtracts means and divides by spread, so it is not.
  • A corner is a point where brightness changes in two directions; an edge changes in only one.
  • Harris compares the two directions through the determinant and trace of the structure tensor.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.