Goal

Detect every chessboard corner visible in a grayscale image, assign each corner an integer pattern coordinate, and refine the corner to subpixel accuracy — without requiring the full pattern to be present. Input: a grayscale image $I : \Omega \to \mathbb{R}$. Output: a set of subpixel points $\{(x_k, y_k)\} \subset \Omega$ together with integer pattern coordinates $\{(i_k, j_k)\} \subset \mathbb{Z}^2$. Corner legality is decided topologically on a Delaunay mesh over the candidate set rather than by a response threshold.

Algorithm

Let $I$ denote the grayscale image. For a pixel $p_c$, let $V = \{p_1, p_2, \ldots, p_n\}$ denote its $n$-pixel Bresenham circle neighbourhood, traversed in order around the circumference, with circular indexing $p_0 \equiv p_n$. Let $m = \frac{1}{n}\sum_{i=1}^{n} I(p_i)$ denote the mean intensity over $V$ and $\mathrm{gate}$ a fixed contrast offset. Define the two thresholds

Let $C \subset \Omega$ denote the candidate x-corners surviving non-maximum suppression. Let $B : \Omega \to \{0, 1\}$ denote a binarization of $I$ used to label triangle interiors. Let $T = \operatorname{Del}(C)$ denote the Delaunay triangulation of $C$ — the unique triangulation in which every triangle's circumcircle contains no other point of $C$.

Procedure

flowchart TB
    A["Image I"] --> B["X-corner<br/>N_alt = 4"]
    B --> C["NMS<br/>argmax R"]
    C --> D["Delaunay<br/>T = Del(C)"]
    A --> E["Adaptive<br/>binarize B"]
    E --> F["Triangle<br/>colour c(t)"]
    D --> F
    F --> G["Topological<br/>filter"]
    G --> H["Coord<br/>propagation"]
    H --> I["Hessian<br/>subpixel"]

Implementation

The per-pixel alternation count is the detector's hot kernel. One pass over the ring yields the alternation count, the two one-sided energies for the NMS cost, and the ring mean.

fn x_corner_response(ring: &[u8], gate: u8) -> Option<u32> {
    let n = ring.len();
    let sum: u32 = ring.iter().map(|&v| v as u32).sum();
    let m = (sum / n as u32) as u8;
    let t_lo = m.saturating_sub(gate);
    let t_hi = m.saturating_add(gate);

    let mut alt = 0u32;
    let mut dark_energy = 0u32;
    let mut light_energy = 0u32;
    for i in 0..n {
        let cur = ring[i];
        let prev = ring[(i + n - 1) % n];
        let up   = cur > t_hi && prev < t_lo;
        let down = cur < t_lo && prev > t_hi;
        if up || down { alt += 1; }

        let delta = (cur as i16 - m as i16).unsigned_abs() as u32;
        if cur < t_lo  { dark_energy  += delta; }
        if cur > t_hi  { light_energy += delta; }
    }
    if alt == 4 {
        Some(dark_energy.max(light_energy))
    } else {
        None
    }
}

The caller further enforces $T_\ell < I(p_c) < T_h$ on the centre pixel before admitting the corner; non-maximum suppression then retains the pixel with the largest returned response in a local window.

Remarks

• Complexity: the x-corner scan is linear in image area with a fixed $n$-sample ring; Delaunay triangulation is $O(|C|\log|C|)$; topological filtering runs a bounded number of fixed-point sweeps, each linear in the mesh; coordinate propagation visits each triangle once; subpixel refinement is invoked only at surviving vertices, not image-wide.
• The detection threshold $\mathrm{gate}$ is set empirically to $10$ on a blurred input. The classification is dominated by the alternation count: any remaining false positives are discarded downstream by the topology, so results are weakly sensitive to $\mathrm{gate}$.
• Binarization is integral-image adaptive (Bradley-Roth) — linear time, window-size independent, and tolerant of slow illumination gradients across the pattern.
• The filter requires only that a sufficient subset of the pattern be visible; it does not demand the full grid. Partial occlusion, missing border tiles, and background clutter all reduce to discarded Delaunay triangles.
• Scope: the method emits ordered integer-coordinate corner lists; it does not solve for camera intrinsics or extrinsics. Those are the downstream calibration problem (e.g. Zhang's method).
• Failure modes: steep viewing angles defocus the X-junctions and push Delaunay edges across tile corners simultaneously; both detection and topology degrade at the same time rather than catching each other. Low-contrast images starve $N_\mathrm{alt}$ at the first stage.
• Compared with Shu: see When to choose Shu over Laureano on the Shu page, which hosts the comparison per the older-paper-hosts rule.

References

1. G. T. Laureano, M. S. V. de Paiva, A. S. da Silva. Topological Detection of Chessboard Pattern for Camera Calibration. IPCV (WorldComp), 2013. PDF
2. C. Shu, A. Brunton, M. A. Fiala. A topological approach to finding grids in calibration patterns. Machine Vision and Applications, 2009. DOI: 10.1007/s00138-009-0202-2
3. E. Rosten, T. Drummond. Machine Learning for High-Speed Corner Detection. ECCV, 2006. PDF