Detecting Checkerboard Targets with OpenCV

Template matching finds a chequered ground target to about a pixel, which at a 2 cm ground sample distance is 2 cm of avoidable error added to every control observation. The target’s own geometry supports far better than that: the centre of a chequer is a saddle point in image intensity, and a saddle point can be located to a fraction of a pixel from the gradients around it, without any assumption about scale, rotation or illumination.

This page finds the target with a coarse search and then refines it to sub-pixel accuracy, which is where the accuracy actually comes from.

Why the corner beats the pattern

A template match slides a picture of the target across the image and reports where the correlation peaks. Three properties limit it. The peak is quantised to whole pixels unless it is interpolated. The template must match the target’s apparent scale, which changes with altitude and terrain. And it must match its rotation, which changes with the aircraft’s heading.

The saddle-point view discards all three assumptions. At the centre of a two-by-two chequer, intensity increases along one diagonal and decreases along the other, so the second-derivative matrix has one positive and one negative eigenvalue — a determinant that is strongly negative. That property is invariant to rotation, to uniform scaling, and to any monotonic change in brightness, which is exactly the set of things that vary between frames.

Why the chequer centre is a saddle point A two-by-two chequer with dark squares on one diagonal and light squares on the other. Two profiles are drawn through its centre. Along the dark-to-dark diagonal, intensity dips to a minimum at the centre. Along the light-to-light diagonal, intensity rises to a maximum at the same point. Because one direction has a minimum and the perpendicular direction has a maximum, the centre is a saddle, and the determinant of the second-derivative matrix is strongly negative there and near zero everywhere else. A note states that this property does not depend on the target's rotation, scale, or overall brightness. the saddle point along the dark diagonal a minimum at the centre along the light diagonal a maximum at the same point invariant to rotation uniform scale brightness and contrast Exactly the three things a template match must be told, and the three that vary most between frames.

Figure 1 — The geometric property the detector exploits. A saddle is defined by the relationship between two directions, which no change of viewpoint or exposure alters.

Minimal reproducible solution

Two stages: a cheap search for candidates using the saddle response, then a sub-pixel refinement on the best one.

import cv2
import numpy as np


def saddle_response(gray: np.ndarray, sigma: float = 2.0) -> np.ndarray:
    """Negative determinant of the Hessian — large at chequer centres.

    Smoothing first sets the scale at which saddles are sought; sigma should
    be roughly a quarter of the expected square size in pixels.
    """
    g = cv2.GaussianBlur(gray.astype(np.float32), (0, 0), sigma)
    gxx = cv2.Sobel(g, cv2.CV_32F, 2, 0, ksize=3)
    gyy = cv2.Sobel(g, cv2.CV_32F, 0, 2, ksize=3)
    gxy = cv2.Sobel(g, cv2.CV_32F, 1, 1, ksize=3)
    det = gxx * gyy - gxy * gxy
    return np.maximum(-det, 0.0)          # saddles have a negative determinant


def find_target(gray: np.ndarray, search_centre: tuple[int, int],
                radius_px: int = 100, square_px: float = 24.0) -> tuple[float, float]:
    """Locate a chequer centre near a predicted position, to sub-pixel accuracy."""
    cx, cy = search_centre
    x0, y0 = max(0, cx - radius_px), max(0, cy - radius_px)
    x1 = min(gray.shape[1], cx + radius_px)
    y1 = min(gray.shape[0], cy + radius_px)
    patch = gray[y0:y1, x0:x1]
    if patch.size == 0:
        raise ValueError("search window falls outside the image")

    resp = saddle_response(patch, sigma=square_px / 4.0)
    _, peak, _, loc = cv2.minMaxLoc(resp)
    if peak <= 0:
        raise ValueError("no saddle response in the search window")

    # Sub-pixel refinement: cornerSubPix solves for the point where the
    # gradient is orthogonal to every edge vector in its neighbourhood, which
    # for a chequer is the saddle to a fraction of a pixel.
    corner = np.array([[loc]], dtype=np.float32)
    win = max(5, int(square_px // 2) | 1)
    cv2.cornerSubPix(
        patch, corner, (win, win), (-1, -1),
        (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 40, 0.001),
    )
    return float(corner[0, 0, 0] + x0), float(corner[0, 0, 1] + y0)

cornerSubPix is the part that produces the accuracy. It refines by requiring the image gradient at every pixel in a window to be perpendicular to the vector from the candidate to that pixel — a condition satisfied exactly at a saddle and only there — and converges to roughly a twentieth of a pixel on a well-exposed target.

The sigma and window sizes both derive from the target’s apparent square size in pixels, which follows from the physical target size and the ground sample distance. Deriving them rather than fixing them is what makes the detector work at two altitudes without retuning.

Edge-case matrix

Condition Effect on the response Handling
Target rotated None — saddle is rotation-invariant Works unchanged
Altitude changed Square size in pixels changes Derive sigma from the GSD
Partial shadow across the target Response weakens, position holds Usually still converges
Target partly occluded Saddle destroyed if the centre is covered Reject; use another frame
Motion blur Response falls with the square of blur Reject the frame, not the target
Specular glare on one square Contrast inverted locally Reject; the saddle sign flips
Repeating pattern nearby Multiple candidate peaks The search window resolves it
Target at the frame edge Refinement window truncated Reject; refinement is unreliable

The repeating-pattern row is why the search window matters as much as the detector. Paving, roof tiles and farm buildings all produce saddle responses, and a whole-frame search finds dozens. Restricting the search to a window predicted from the flight log — the approach described in how to auto-tag GCPs in drone images — reduces the problem to picking the strongest peak in a region where only one target exists.

Verify the fix worked

Sub-pixel accuracy is a claim, and it is testable by consistency: the same physical target observed in several frames should triangulate to a single ground point.

import numpy as np


def assert_subpixel_consistency(observations: list[tuple[float, float]],
                                projections: list, tol_px: float = 0.3) -> None:
    """Observations of one target must agree after projection to the ground.

    Reprojects the triangulated position back into each frame and requires the
    departure from the measured pixel to be small — which is only achievable
    if the measurements were sub-pixel to begin with.
    """
    ground = _triangulate(observations, projections)
    errs = []
    for (u, v), P in zip(observations, projections):
        uh, vh = P(ground)
        errs.append(float(np.hypot(uh - u, vh - v)))
    worst = max(errs)
    assert worst <= tol_px, (
        f"worst reprojection {worst:.2f} px across {len(errs)} observations — "
        "the detections are not sub-pixel, or one of them is on a different "
        "feature entirely")

A tolerance of 0.3 px is achievable with saddle refinement and not achievable with an unrefined template match, so this assertion also serves as a regression test on the detector itself: if someone replaces the refinement with a simpler peak pick, the test fails.

Detection accuracy converted into ground error A bar comparison of three detection methods at a two centimetre ground sample distance. A whole-pixel template peak gives roughly one pixel of error, which is two centimetres on the ground. A parabolic interpolation of the correlation peak gives about a third of a pixel, or six millimetres. A saddle-point refinement gives about a twentieth of a pixel, or one millimetre. A note observes that the third is well below the accuracy of the control survey itself, so the detector stops being the limiting term. whole-pixel peak parabolic interpolation saddle refinement ≈ 20 mm ≈ 6 mm ≈ 1 mm typical control survey accuracy — 10 mm Only the third method puts the detector below the control survey's own uncertainty. Above that line the detector is the limiting term, and improving the survey buys nothing.

Figure 2 — What sub-pixel refinement is worth at survey resolutions. The gain is not marginal: it moves the detector from being the dominant error term to being negligible.

When to escalate

  • The response is strong and the refinement moves the point by several pixels. The refinement window is larger than the target’s squares, so it is being pulled by structure outside the chequer. Derive the window from the square size rather than fixing it.
  • Detections are consistent within a frame and inconsistent between frames. The targets were physically moved between flights, or two similar targets exist near each other. Compare the triangulated positions against the surveyed coordinates before assuming a detector fault.
  • The target is visible to a human and produces no saddle response. Almost always blur or a very oblique view. Both destroy the second-derivative structure, and neither is recoverable by tuning; use a different frame, which is what having several observations per point is for.

One practical note on the targets themselves. A matte finish matters more than the colour contrast: a glossy painted board produces specular glare that inverts the local contrast at exactly the moment the sun is behind the aircraft, which is when most of the frames covering that target are taken. Unpainted concrete pavers or a matte vinyl print outlast painted plywood in both weather and detection reliability, and the difference shows up as the fraction of frames in which a given target is found at all.

← Automating GCP Detection with Python

Sizing the target from the planned ground sample distance A relationship between physical target size and flight altitude for three ground sample distances. The requirement is that each chequer square spans at least six pixels, so at a two centimetre ground sample distance a square must be at least twelve centimetres and a four-square target at least twenty-four centimetres across. At four centimetres per pixel the target must be at least forty-eight centimetres, and at eight centimetres per pixel nearly a metre. A note observes that a target sized for one altitude becomes undetectable if the flight is raised, which is a planning decision rather than a processing one. 1 cm/px 2 cm/px 4 cm/px 8 cm/px ground sample distance minimum target size 12 cm 24 cm 48 cm 96 cm Six pixels per square is the working minimum; a target sized for 2 cm/px stops working if the flight is raised to 4.

Figure 3 — The target size is a flight-planning decision made weeks before processing. No refinement recovers a chequer whose squares are three pixels across.