Definition

Topological grid recovery is a class of post-detection verification strategies for chessboard corner detectors. The pipeline runs in two phases: a cheap, permissive corner detector first emits candidate locations, then a graph is built over the candidates and only those that participate in a valid chessboard topology survive. The defining property: false positives are pruned by structural rules — counts of same-colour neighbours, alternating-colour cycles, valid quad orderings — rather than by tightening the per-pixel response threshold. This decouples sensitivity (the detector's recall) from specificity (the topology filter's precision), which is the key idea common to four of the chessboard X-corner pipelines in the atlas.

Mathematical Description

The shared shape

Let $C \subset \mathbb{Z}^2$ be the set of candidate corner pixels emitted by a per-pixel detector (Harris, ChESS, Hessian saddle, FAST-derived). Build a proximity graph $G = (C, E)$ over the candidates — typically one of:

• Delaunay triangulation $\mathrm{Del}(C)$ — the unique triangulation in which no triangle's circumcircle contains another candidate. Used by shu2009 and laureano2013.
• $k$-nearest-neighbour graph — each vertex linked to its $k$ closest neighbours. PuzzleBoard uses $k = 9$.
• Subgraph search target — a regular $r \times c$ chessboard graph $G^*$ that the detected graph $G$ must contain. Used by OCPAD via the VF2 subgraph-isomorphism algorithm.

A topology filter $\mathcal{F}: G \to G'$ removes vertices and edges that violate the expected chessboard structure. The filter is applied to fixed point: orphan vertices are discarded, and the surviving subgraph carries the integer pattern coordinates.

Variants — what "topology" means in each method

Each of the four methods picks a different graph model and a different filter:

Detection–verification decoupling

The four methods share an architectural pattern, even though their graphs and filters differ. In each:

1. The per-pixel detector is configured permissively — high recall, accepting many false positives. ChESS in Laureano; Harris-on-the-Bresenham-ring in Shu; Hessian saddle in PuzzleBoard and OCPAD's underlying detector.
2. The topology filter handles specificity. The filter's parameters are typically robust thresholds (count of same-colour neighbours, $k$ in $k$-NN, distance ratios in VF2's matching condition) — far less sensitive to per-image contrast than the detector's threshold would be.

This decoupling is what makes these pipelines competitive on degraded inputs (motion blur, low contrast, partial occlusion) where pure response-threshold detectors collapse.

Comparison summary

Numerical Concerns

Delaunay degeneracy at small angles. The Delaunay triangulation is well-defined only when no four candidates are co-circular and no three are collinear. Under heavy projective distortion or very densely packed corners (low-resolution boards), near-degenerate configurations occur and the resulting triangulation is unstable — a small perturbation flips edges. Shu reports that the topology filter remains effective up to $\sim 60°$ Delaunay-rotation invariance (Fig. 4) but no theoretical bound exists; this is an open problem in the chessboard-detection literature.

Same-colour-neighbour boundary. Both Shu and Laureano use a "same-colour neighbour" predicate that depends on a binarisation of the image. At pattern boundaries, the binarisation can label an external square inconsistently. A small inset margin $\delta$ (Shu: 5 px) excludes pixels within $\delta$ of the candidate edge from the colour test.

Subgraph isomorphism complexity. VF2 is worst-case exponential; OCPAD bounds the search via depth-3 BFS anchor-selection (the most-connected node serves as the search root). For pattern sizes up to $\sim 10 \times 7$ on commodity hardware, end-to-end OCPAD runs in single-digit milliseconds (§4 of paper). Larger patterns or denser candidate sets push the cost; alternative subgraph algorithms (RI, LAD) are valid drop-ins.

Iterative filter convergence. Triangle-level (Laureano) and quad-level (Shu) filters are applied iteratively: removing one orphan vertex can promote its neighbour to an orphan in the next iteration. Convergence is monotone (the candidate set only shrinks) and terminates in at most $|C|$ iterations; in practice 3–5 iterations suffice on full boards.

Anchor-vertex sensitivity. OCPAD's subgraph search starts from a single anchor candidate (the highest-degree node within a depth-3 BFS). If the anchor is itself a false positive, the search returns nothing — but the cost of trying an alternative anchor is small and OCPAD does so on failure.

Cross-correlation decoding window. PuzzleBoard's absolute-position recovery requires a sub-window of the 501×501 grid aligned with the detected MSF; the cross-correlation operates on $167 \times 333$ and $333 \times 167$ binary de-Bruijn maps. For a too-small detected window (fewer than $\sim 5 \times 5$ corners), the correlation peak is ambiguous and absolute decoding fails — though local detection still succeeds.

Where it appears

The four methods listed above are the atlas instances; ChESS itself does not include topological recovery (it's a pure per-pixel detector), which is one reason it is often paired with one of the topology filters as a downstream verifier in larger pipelines. The Hillen 2023 GP-enhancement (forthcoming page once the index is updated) is a non-topological alternative — it predicts missing corners via Gaussian-process regression rather than verifying via graph rules. The two approaches are complementary: topology filters reject false positives via structure; GP enhancement extrapolates true positives via smoothness.

References

1. C. Shu et al. Topological Grid Finding (2009). Quad-level Delaunay topology filter.
2. C. Laureano, V. Murino. Chessboard Detection via X-Corners and Topology (2013). Triangle-level Delaunay filter; Chen-Zhang Hessian subpixel refinement at surviving vertices.
3. P. Fürsattel et al. OCPAD: Occluded Checkerboard Pattern Detection (2016). Subgraph-isomorphism filter via VF2.
4. P. Stelldinger, N. Lanwer. PuzzleBoard: A New Camera Calibration Pattern with Position Encoding. DAGM-GCPR 2024. (MSF on 9-NN; cross-correlation against de-Bruijn map.)
5. L. Cordella et al. A (sub)graph isomorphism algorithm for matching large graphs. IEEE TPAMI 26(10)
   –1372, 2004. (VF2 algorithm used by OCPAD.)