Finding a checkerboard, from adaptive threshold to sub-pixel saddle

cv2.findChessboardCorners finds a checkerboard, or it doesn’t. When it doesn’t, you get nothing: no reason, no partial answer, and no way to ask “did you at least see the left half of the board?” Post 38 opened that box for a plain checkerboard: a corner is a saddle point of intensity, one Hessian eigenvalue test finds every candidate, and four geometric filters clean up the impostors.

This repo doesn’t calibrate against a plain checkerboard, though. It calibrates against a ChArUco board, a checkerboard with a small binary-coded square dropped into every other cell, and the reason is exactly the failure mode above. A plain board is one blob: cover a corner of it, or catch it at a bad angle, and the corner-ordering step (the “find the four extreme corners, walk the edges” trick from post 38) has no way to know which edge it lost. A ChArUco board is dozens of small, independently-readable IDs. Cover half of it and the other half still tells you exactly which squares you’re looking at, because each one says so.

Why ChArUco, in the repo’s own words

The report’s rationale (docs/pngs/report-10.png, §4.2.3) is worth having straight, because it’s easy to reach for “ArUco is fancier” and miss the actual argument:

The calibration technique used follows the method suggested by D. Moreno and G. Taubin. First, a known pattern is generated. The usual choice for this is usually either a checkerboard or a grid of circles. The checkerboard provides easy to identify corners, which can be detected to sub-pixel accuracies. An improvement to the checkerboard pattern is known as a ChArUco board. A ChArUco board is a checkerboard pattern which contains ArUco markers in each white block. ArUco markers are square markers which are easy to uniquely identify in an image. Using them with the checkerboard pattern allows one to identify which corners are present in an image.

Two sub-claims are doing the work there: sub-pixel corners (which a plain checkerboard already gives you, that’s post 38) and knowing which corners you found (which it doesn’t). The second one is the actual improvement, and it’s why a partially-covered ChArUco board still calibrates while a partially-covered checkerboard just fails.

The board

CameraCalibration/BoardInfo.py is short enough to quote whole:

dpmm = 40
A4_shape = 210, 280
A4_shape_margin = A4_shape[0]-10, A4_shape[1] - 20
outshape = A4_shape[0]*dpmm, A4_shape[1]*dpmm
desired_block_size_mm = 20
desired_aurco_size_mm = 14
desired_gap_size_mm = 5

blocksx = A4_shape[0]//desired_block_size_mm
blocksy = A4_shape[1]//desired_block_size_mm

aurcoDict = aruco.getPredefinedDictionary(aruco.DICT_4X4_250)
charucoBoard = aruco.CharucoBoard_create(blocksx, blocksy,
                                         desired_block_size_mm,
                                         desired_aurco_size_mm,
                                         aurcoDict)

210 × 280 mm, not the true A4 297 mm: 280 is 14 × 20, so fourteen whole 20 mm rows fit exactly and there’s 17 mm of margin left over at the bottom rather than a fifteenth half-row. blocksx, blocksy = 10, 14: ten columns, fourteen rows of 20 mm squares, a 14 mm DICT_4X4_250 marker centred in every other one. That’s (10 × 14) / 2 = 70 marker squares and (10 - 1) × (14 - 1) = 117 interior checkerboard corners, both numbers the widget’s live readout counts up to.

DICT_4X4_250 means every marker encodes a 4×4 grid of black/white bits, chosen from OpenCV’s own list of 250 codewords engineered to survive being confused with each other. My dictionary is not that list (see below), but the geometry above is exact: same block count, same square size, same marker size, same sheet. The “print this board” link under the widget renders it at true millimetre scale from these numbers.

Adaptive threshold

Everything downstream depends on turning grey pixels into “ink” or “not ink,” and a single global threshold can’t do that across an unevenly-lit board: the repo’s own photos have a projector-lit wall behind the board and open shadow in front of it, so one edge of the frame can be twice as bright as the other. KinectCameraCalibration.py L26–31 sets OpenCV’s ArUco detector up for exactly this:

detectorParams = aruco.DetectorParameters_create()
detectorParams.adaptiveThreshConstant = 5
detectorParams.adaptiveThreshWinSizeMin = 3
detectorParams.adaptiveThreshWinSizeMax = 50
detectorParams.adaptiveThreshWinSizeStep = 2
detectorParams.minMarkerPerimeterRate = 0.01
detectorParams.maxMarkerPerimeterRate = 8

OpenCV actually re-thresholds several times, walking the window size from 3 up to 50 in steps of 2 and pooling candidates across all of them, so a marker that’s the wrong size for one window still gets caught by another. My Rust (board::adaptive_threshold, wasm/crates/calib-wasm/src/board.rs) thresholds once, at a single window the widget’s slider controls: a deliberate simplification, so a reader can see what one window buys you before imagining the multi-pass version.

The threshold itself is the standard “mean minus a constant”: for every pixel, compare it to the average of its own window × window neighbourhood, marked as foreground (probable ink) if it’s more than C darker than that local average. Computing that mean naively is O(window²) per pixel; a running-sum integral image makes it O(1) per pixel regardless of window size, so the slider stays interactive at any setting:

let mut integral = vec![0.0f64; (w + 1) * (h + 1)];
// ... prefix sums, one pass ...
let mean = box_sum(x0, y0, x1, y1) / area;
out[y * w + x] = if px < mean - c as f64 { 255 } else { 0 };

Drag the window slider small and the board’s own printed line-work starts thresholding against itself (every dark pixel judged only against its immediate, equally-dark neighbours); drag it large and a real shadow gradient across the frame stops being local enough to cancel out. The “threshold” stage in the widget below shows exactly this trade-off live.

Suzuki–Abe contour tracing

A binary image full of board::find_contours’s “foreground” pixels doesn’t tell you where any shape is: you still have to walk each blob’s boundary and turn it into an ordered list of points. The obvious way is a flood fill per blob; the way OpenCV’s findContours actually works, and the way board::find_contours reimplements, is one raster scan that finds every border, including the borders of holes inside a region, without ever re-visiting a pixel twice.

The trick is a marking scheme. Scanning left-to-right, top-to-bottom, a foreground pixel with a background pixel immediately to its left starts a new outer border; a foreground pixel with a background pixel immediately to its right starts a new hole border. Either way, the border gets a fresh id (NBD, “newly found border”) and is traced with an 8-connected walk: from the current border pixel, search its neighbours counter-clockwise, starting just past the direction you arrived from, for the next foreground pixel. Each pixel visited gets written with ±NBD: positive if it’s a real interior point of the region, negative if its immediate east neighbour is background (meaning a later raster-scan visit to it must not mistake it for the start of yet another border). That marking is the entire reason one pass suffices: by the time the scan reaches a pixel again, its value already says whether it’s already spoken for.

// 3.3: counter-clockwise search from just past the direction to (prev_x, prev_y).
let from_dir = dir_index(prev_x - cur_x, prev_y - cur_y);
for k in 1..=8 {
    let d = ((from_dir as i32 - k as i32).rem_euclid(8)) as usize;
    // ... first nonzero neighbour wins ...
}
// 3.4: the *fixed* east neighbour decides the sign, not the one the search found.
if get(&f, cur_x + 1, cur_y) == 0 { f[idx] = -nbd; }

I don’t track the parent/hierarchy half of the paper (which border is a hole inside which outer border): the quad search below only needs the shapes, not their nesting, so this is a real but intentional subset of the full algorithm.

From contour to quad candidate

A raw contour is a dense pixel chain: one point per boundary pixel, so a few hundred points for a modest marker. OpenCV’s detectMarkers reduces each one with approxPolyDP (Douglas-Peucker) and keeps the ones that land on exactly four points within a shape tolerance. board::hull_to_quad does something related but simpler: take the contour’s convex hull, then repeatedly drop whichever hull vertex costs the least triangle area (Visvalingam–Whyatt decimation) until four vertices remain.

fn hull_to_quad(hull: &[Pt]) -> Option<[Pt; 4]> {
    let mut poly = hull.to_vec();
    while poly.len() > 4 {
        // drop the vertex whose removal changes the polygon's area least
    }
    Some([poly[0], poly[1], poly[2], poly[3]])
}

Candidates are then kept if their perimeter falls inside [min_perimeter_rate, max_perimeter_rate] × max(width, height): the same gate minMarkerPerimeterRate / maxMarkerPerimeterRate set above, and the widget’s two perimeter-rate sliders.

Per-quad homography, and bit sampling

Post 38’s report flags this module as directly reusable: a marker candidate is a quadrilateral, a marker’s own bit grid is a canonical square, and mapping one onto the other is exactly Zhang’s normalised DLT from post 41 (zhang::homography, wasm/crates/calib-wasm/src/zhang.rs). So that’s what board::sample_and_decode calls, unmodified: the canonical 0..6 × 0..6 module square (a 4×4 code plus one module of black border each side) as world, the candidate’s four ordered corners as image.

let world = vec![[0.0, 0.0], [n, 0.0], [n, n], [0.0, n]];   // n = 6 modules
let (h_mat, _cond) = homography(&world, &image, true, Solver::Jacobi)?;

With that homography, sampling is just projecting each of the 36 module centres through it and bilinearly reading the grey image there: no separate perspective-correction warp, because the homography is the perspective correction, evaluated only where it’s needed. A quick Otsu threshold over the 36 samples splits them into black/white; every one of the 24 border modules must come out black or the candidate is rejected outright (a real marker’s border is solid by construction; almost nothing else that survived the quad filter has one); the inner 4×4 becomes a 16-bit code.

A dictionary that is honestly not DICT_4X4_250

The generation is greedy: draw a random 16-bit pattern, keep it only if every one of its four 90°-rotations is at Hamming distance ≥ 4 from every rotation of every code already accepted.

pub const MIN_DISTANCE: u32 = 4;

Four isn’t an arbitrary round number: it’s the smallest distance that makes correction provable rather than merely usual. By the triangle inequality, a word within distance 1 of code $A$ and also within distance 1 of a different code $B$ would put $A$ and $B$ within distance 2 of each other, contradicting a minimum distance of 4. So with MIN_DISTANCE = 4: a single flipped bit is always correctable to the right code (nothing else is close enough to be confused with it), and a double flip is always caught rather than silently decoded wrong: the corrupted word sits at distance 2 from its true code, and by the same inequality at distance $\geq 4 - 2 = 2$ from every other code, so it can never land inside anyone’s radius-1 acceptance ball. decode accepts distance ≤ 1 and rejects everything else:

best.filter(|&(_, _, d)| d <= 1)

hamming_correction_fixes_one_bit_and_rejects_two in board.rs checks exactly that pair of guarantees, not just “usually works.” Decode itself tries all four rotations of the sampled code against the dictionary’s stored canonical orientation, so a marker read upside-down or on its side still resolves to the right id: rotation in the result says how many quarter-turns it took, which is also how the marker’s four corners get assigned consistently to “its” corner of the checkerboard square around it.

Interior corners: local, not global

The last step is the actual payoff for occlusion tolerance, so it’s worth being precise about the design choice. A tempting shortcut is: fit one homography for the whole board from every detected marker corner, then project every interior checkerboard corner through it. That would work, and would also mean a single distant, badly-decoded marker corner can drag every corner’s estimate off, and a board only half in frame gets no corners at all until enough markers are visible to make the global fit stable.

board::interpolate_corners does the local thing instead, closer to what interpolateCornersCharuco actually promises: every decoded marker proposes only the four checkerboard corners of its own 20 mm square, by extrapolating its own already-fit per-marker homography a little past the 14 mm footprint it was measured on:

let margin_mod = margin / module_mm;              // (20 - 14) / 2 mm, in module units
let local_corners = [(-margin_mod, -margin_mod), (n + margin_mod, -margin_mod), ...];

An interior corner shared by up to four neighbouring squares gets an average of however many of those squares’ markers actually decoded: one proposal is enough to place it, and a corner nowhere near any decoded marker is honestly reported as not found, rather than guessed at from the far side of the board. Every proposal then gets pulled onto the nearest strong saddle response within a few pixels, reusing image::Hessian from post 38 exactly as it’s used there:

let resp = hess.lambda1[idx].min(-hess.lambda2[idx]);
if resp > best.2 { best = (x, y, resp); }

This mirrors what OpenCV’s own corner interpolation does, refining a geometric estimate onto the image’s actual local structure, without reusing its code, and it’s the piece that makes “cover half the board” a story the widget can actually show rather than just claim.

Results

On a clean, straight-on render of the widget’s own printed board (its own dictionary, so this is the fair test of whether the pipeline is correct), every setting I tried (threshold window 15–31 px, C 4–10) reads all of it:

The two bundled real photographs tell a different, more interesting story. They’re genuine 1200-DPI-then-photographed-then-scanned-into-a-PDF images of the repo’s actual board, and that board was printed with OpenCV’s real DICT_4X4_250, not this widget’s dictionary. At the widget’s default settings (23 px window, C = 7):

The widget

Five stages, live: greyscale, the adaptive threshold, every raw Suzuki–Abe contour, the quads that survived the perimeter filter (accent-coloured if they went on to decode), and one decoded marker’s unwarped 6×6 module grid. The default “detected” view overlays every decoded marker’s id on its quad and a cross on every interior corner it could place.

With JavaScript on, this becomes a live ChArUco detector: two bundled real photos, a file picker, and a camera button. Step through greyscale, adaptive threshold, candidate contours, surviving quads and an individual marker’s bit grid, with window-size and perimeter-rate sliders live. The detection downloads as JSON, and a “print this board” link serves the exact geometry above as an A4 PDF.

Things worth trying:

• Print the board and photograph it. It’s the only way to see the “N / 70” readout move past one or two: the bundled historical photos are printed in a dictionary this widget doesn’t know.
• Watch the “quads” stage on a real photo. Hundreds of candidates, almost none of them anywhere near a real marker: table grain, mug lettering, cardboard texture all produce quad-shaped hulls that the perimeter filter alone can’t rule out. Decode is doing real work rejecting them.
• Push the threshold window very small or very large on sample-board-2.webp, where the statue’s shadow crosses part of the board. A window too small starts thresholding the board’s own print against itself; too large stops separating the shadow from the fully-lit squares next to it.
• Cover part of the printed board with a hand before photographing it, then load that photo. Markers elsewhere on the board still decode, and the corners nearest your hand are the only ones reported missing: that’s the entire pitch for a ChArUco board over a plain one, made concrete.

Camera note

getUserMedia only exists in a secure context: https://, or localhost. Reviewed over plain HTTP to a LAN address, navigator.mediaDevices is undefined and the widget says so honestly rather than pretending the camera button just isn’t there. Upload, drag-drop and paste all work regardless.

Output format, for the next post

Post 61 takes a pile of (board point, image point) pairs and fits a camera matrix from them: it needs this post’s output, not this post’s pixels. Post 38 already ships checkerboard-corners/v1: a flat, always-fully-populated row-major array of [x, y] pairs, because the Liu detector either finds the whole board or refuses outright. A ChArUco board can genuinely succeed partially, so this post’s format, finding-a-checkerboard/v1, keeps the same row-major interior-grid shape but allows null where occlusion or a failed decode left a corner unplaced:

{
  "format": "finding-a-checkerboard/v1",
  "board": { "colsBlocks": 10, "rowsBlocks": 14, "squareMm": 20, "markerMm": 14 },
  "markers": [{ "id": 0, "rotation": 0, "corners": [[x, y], [x, y], [x, y], [x, y]] }],
  "corners": {
    "rows": 13, "cols": 9,
    "order": "row-major; corner k is column k % cols, row floor(k / cols); null if unplaced",
    "points": [[x, y], null, "…"]
  }
}

corners.points is the part a calibration solver actually wants: same row-major convention as checkerboard-corners/v1, just with holes it has to be prepared to skip. markers is kept alongside it for anyone who wants the raw marker reads (ids, rotation, quad corners) rather than only the interpolated grid.

What this doesn’t do

• No multi-window adaptive threshold. OpenCV pools candidates across a whole ladder of window sizes (3 to 50, step 2); this thresholds once, at whatever the slider says.
• No true 30 fps live decode. The camera button freezes one frame and runs the detector on the still, the same choice post 38’s widget makes: a single-threaded WASM contour tracer over a full camera frame every animation frame is a real cost this post didn’t spend the budget to hide.
• No lens distortion, no extrinsics. Same limits post 38 already flagged for the plain-checkerboard detector: this post only finds and identifies corners; post 61 is where a camera matrix comes from them.