Goal

Recover a correspondence between a detected corner graph and a checkerboard model graph when the pattern is partially occluded, leaves the field of view, or contains spurious edges from background clutter. Input: a candidate graph $G_d = (V_d, E_d)$ of detected saddle-point corners with edges between grid-neighbour corners, and a checkerboard model graph $G_m = (V_m, E_m)$ of known dimensions. Output: a partial, non-injective, non-surjective mapping $M : V_d \to V_m$ covering as many $V_d$ vertices as possible while tolerating missing and extra vertices and edges.

Algorithm

Let $G_d = (V_d, E_d)$ denote the candidate graph delivered by an upstream corner-graph builder, and $G_m = (V_m, E_m)$ the checkerboard model graph. Let $N = |V_d|$ and $N_m = |V_m|$. Let $w$ denote the subpixel-refinement window size of the upstream refiner, which doubles as the lower bound on corner-to-corner distance. Let $\mathrm{BFS}_k(v)$ denote the BFS neighbourhood of $v$ out to depth $k$ in $G_d$. For a candidate $v \in V_d$, let $D_a(v)$ denote the BFS distance from an anchor vertex $a$.

Procedure

Implementation

The binary-search driver is the algorithmic core — it treats VF2 as a black-box exact-match engine and converges $N_i$ by halving.

type VertexId = u32;
type Mapping = Vec<(VertexId, VertexId)>;

fn ocpad_match(
    g_d: &Graph, g_m: &Graph,
    anchor: VertexId, order: &[VertexId],
    vf2: &dyn Fn(&Graph, &Graph) -> Option<Mapping>,
) -> Option<Mapping> {
    let n = order.len();
    let mut n_prev = n;
    let mut n_i = n;
    let mut best: Option<Mapping> = None;

    for i in 1.. {
        let g_i = g_d.induce(&order[..n_i]);
        let step = ((n as f64) * 2f64.powi(-(i as i32))).round() as isize;
        match vf2(&g_i, g_m) {
            Some(m) => {
                best = Some(m);
                n_prev = n_i;
                n_i = (n_i as isize + step).clamp(0, n as isize) as usize;
            }
            None => {
                n_i = (n_i as isize - step).clamp(0, n as isize) as usize;
            }
        }
        if n_i >= n_prev && best.is_some() { break; }
        if step == 0 { break; }
    }
    best
}

Region growing runs after this converges: for each unassigned neighbour of a matched vertex, the caller extends $G_i$ by one vertex and re-runs VF2, committing the extension only on a valid mapping.

Remarks

• The algorithm consumes a corner graph and produces only a mapping; it does not detect corners, refine subpixel locations, or estimate intrinsics. Those stages live in the upstream detector and the downstream calibration solver.
• Runtime is dominated by the inner VF2 calls. Because the checkerboard graph is strongly connected, the binary search usually converges in a number of iterations logarithmic in $N$; on fragmented inputs it degenerates to linear region-growing.
• The $50\%$ vertex threshold and the spatial-consistency check are pre-filters that reject garbage before VF2 runs. They do not help a valid partial pattern — they cheapen the rejection of wrong candidates.
• The quad filter excises every triangle and isolated edge, which removes most background clutter before matching. A spurious diagonal inside an otherwise valid quad is tolerated downstream by the error-tolerant driver.
• Failure modes: candidates with fewer than half the model vertices are dropped at step 1; genuine patterns with ambiguous anchor placement (no clear quad-density maximum, e.g. a uniform fragment) yield slower, less reliable matches; multiple disconnected components of the candidate graph are resolved by keeping only the largest, which drops real corners on the smaller side.
• VF2 can be swapped for any exact subgraph-isomorphism routine; the binary-search driver and the region-growing step are independent of the matcher.
• Compared with GP enhancement (Hillen 2023): OCPAD is combinatorial — it matches the detected corner graph against the model graph by exact subgraph isomorphism and requires no training. The GP method is regression — it learns the board-to-pixel map from a partial allocated set and predicts missing corners by interpolation/extrapolation, requiring at least a partial board fragment as training data but extending naturally beyond the image border. The two are complementary: OCPAD recovers a partial visible subgraph; GP enhancement fills in occluded or out-of-frame corners with smooth refinement.

References

1. P. Fürsattel, S. Dotenco, S. Placht, M. Balda, A. Maier, C. Riess. OCPAD — Occluded Checkerboard Pattern Detector. IEEE WACV, 2016. DOI: 10.1109/WACV.2016.7477565
2. S. Placht, P. Fürsattel, E. A. Mengue, H. Hofmann, C. Schaller, M. Balda, E. Angelopoulou. ROCHADE: Robust Checkerboard Advanced Detection for Camera Calibration. ECCV, 2014. DOI: 10.1007/978-3-319-10593-2_50
3. L. P. Cordella, P. Foggia, C. Sansone, M. Vento. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE TPAMI, 2004. DOI: 10.1109/TPAMI.2004.75