checkerboard_calibrate/chessboard/
link.rs

1// Copyright (C) The Strand-Braid Authors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Linking quads into a board graph — stage 3 of `findChessboardCorners`.
5//!
6//! Adjacent chessboard squares touch at their corners, so the detected quads
7//! form a graph: two quads are neighbors when one corner of each nearly
8//! coincides. This mirrors OpenCV's `findQuadNeighbors` (corner matching) and
9//! `findConnectedQuads` (grouping into connected components), which together
10//! isolate the candidate board(s) from spurious quads.
11//!
12//! On a checkerboard the black squares meet only at corners and exactly two
13//! squares meet at any shared corner, so each quad corner links to at most one
14//! neighbor. Corner matching is therefore done as a global nearest-pair greedy
15//! matching under a distance threshold proportional to the quads' edge lengths;
16//! this is order-independent and yields the same board graph as OpenCV for a
17//! clean board. (End-to-end parity with OpenCV is verified later against the
18//! detection golden, since the intermediate graph is not exposed by OpenCV.)
19
20use super::quad::Quad;
21
22/// A quad participating in the board graph.
23#[derive(Clone, Debug)]
24pub struct LinkedQuad {
25    /// Corner positions `(x, y)`. A linked pair of corners is snapped to their
26    /// shared midpoint, as OpenCV merges coincident corners.
27    pub corners: [(f32, f32); 4],
28    /// For each corner, the index of the neighboring quad sharing it (if any).
29    pub neighbors: [Option<usize>; 4],
30    /// Minimum squared edge length of the quad (the neighbor-distance scale).
31    pub edge_len: f32,
32}
33
34/// Fraction of the (squared) edge length within which two corners are treated
35/// as the same shared corner. Shared corners of adjacent squares are
36/// near-coincident, while the next-closest corners are about a full edge away
37/// (squared distance ~= `edge_len`), so any value well below 1 separates them;
38/// 0.25 (a linear gap up to half an edge) is generous but safe.
39const LINK_THRESH_SCALE: f32 = 0.25;
40
41fn dist2(a: (f32, f32), b: (f32, f32)) -> f32 {
42    let dx = a.0 - b.0;
43    let dy = a.1 - b.1;
44    dx * dx + dy * dy
45}
46
47fn min_edge_len2(corners: &[(f32, f32); 4]) -> f32 {
48    let mut m = f32::MAX;
49    for i in 0..4 {
50        m = m.min(dist2(corners[i], corners[(i + 1) % 4]));
51    }
52    m
53}
54
55/// Build [`LinkedQuad`]s from detected quads and link neighboring corners.
56///
57/// Two corners are eligible to link when their squared distance is within
58/// [`LINK_THRESH_SCALE`] of the smaller of the two quads' edge-length scales.
59/// Among all eligible corner pairs, the closest are matched first; each corner
60/// links at most once.
61pub fn link_quads(quads: &[Quad]) -> Vec<LinkedQuad> {
62    let mut linked: Vec<LinkedQuad> = quads
63        .iter()
64        .map(|q| {
65            let corners = [
66                (q.corners[0].0 as f32, q.corners[0].1 as f32),
67                (q.corners[1].0 as f32, q.corners[1].1 as f32),
68                (q.corners[2].0 as f32, q.corners[2].1 as f32),
69                (q.corners[3].0 as f32, q.corners[3].1 as f32),
70            ];
71            LinkedQuad {
72                corners,
73                neighbors: [None; 4],
74                edge_len: min_edge_len2(&corners),
75            }
76        })
77        .collect();
78
79    // Collect all eligible corner pairs (i,ci)-(j,cj) with i < j.
80    struct Cand {
81        d: f32,
82        i: usize,
83        ci: usize,
84        j: usize,
85        cj: usize,
86    }
87    let mut cands = Vec::new();
88    let n = linked.len();
89    for i in 0..n {
90        for j in (i + 1)..n {
91            let thr = linked[i].edge_len.min(linked[j].edge_len) * LINK_THRESH_SCALE;
92            for ci in 0..4 {
93                for cj in 0..4 {
94                    let d = dist2(linked[i].corners[ci], linked[j].corners[cj]);
95                    if d <= thr {
96                        cands.push(Cand { d, i, ci, j, cj });
97                    }
98                }
99            }
100        }
101    }
102    cands.sort_by(|a, b| a.d.partial_cmp(&b.d).unwrap());
103
104    for c in cands {
105        if linked[c.i].neighbors[c.ci].is_none() && linked[c.j].neighbors[c.cj].is_none() {
106            // Snap both corners to their shared midpoint.
107            let a = linked[c.i].corners[c.ci];
108            let b = linked[c.j].corners[c.cj];
109            let mid = ((a.0 + b.0) * 0.5, (a.1 + b.1) * 0.5);
110            linked[c.i].corners[c.ci] = mid;
111            linked[c.j].corners[c.cj] = mid;
112            linked[c.i].neighbors[c.ci] = Some(c.j);
113            linked[c.j].neighbors[c.cj] = Some(c.i);
114        }
115    }
116
117    linked
118}
119
120/// Group quads into connected components following the neighbor links.
121/// Returns each component as a list of quad indices.
122pub fn connected_components(quads: &[LinkedQuad]) -> Vec<Vec<usize>> {
123    let n = quads.len();
124    let mut group = vec![usize::MAX; n];
125    let mut groups = Vec::new();
126
127    for start in 0..n {
128        if group[start] != usize::MAX {
129            continue;
130        }
131        let gid = groups.len();
132        let mut members = Vec::new();
133        let mut stack = vec![start];
134        group[start] = gid;
135        while let Some(q) = stack.pop() {
136            members.push(q);
137            for nb in quads[q].neighbors.into_iter().flatten() {
138                if group[nb] == usize::MAX {
139                    group[nb] = gid;
140                    stack.push(nb);
141                }
142            }
143        }
144        members.sort_unstable();
145        groups.push(members);
146    }
147    groups
148}
149
150#[cfg(test)]
151mod tests {
152    use super::*;
153
154    /// An axis-aligned square quad with given top-left corner and side.
155    fn square(x: i32, y: i32, side: i32) -> Quad {
156        Quad {
157            corners: [(x, y), (x + side, y), (x + side, y + side), (x, y + side)],
158        }
159    }
160
161    fn neighbor_count(q: &LinkedQuad) -> usize {
162        q.neighbors.iter().filter(|n| n.is_some()).count()
163    }
164
165    #[test]
166    fn two_quads_sharing_a_corner_link() {
167        // Q1's top-left corner coincides with Q0's bottom-right corner.
168        let quads = [square(0, 0, 20), square(20, 20, 20)];
169        let linked = link_quads(&quads);
170        assert_eq!(neighbor_count(&linked[0]), 1);
171        assert_eq!(neighbor_count(&linked[1]), 1);
172        let comps = connected_components(&linked);
173        assert_eq!(comps, vec![vec![0, 1]]);
174    }
175
176    #[test]
177    fn diagonal_chain_of_three() {
178        let quads = [square(0, 0, 20), square(20, 20, 20), square(40, 40, 20)];
179        let linked = link_quads(&quads);
180        // The middle quad touches both ends.
181        assert_eq!(neighbor_count(&linked[1]), 2);
182        assert_eq!(neighbor_count(&linked[0]), 1);
183        assert_eq!(neighbor_count(&linked[2]), 1);
184        assert_eq!(connected_components(&linked), vec![vec![0, 1, 2]]);
185    }
186
187    #[test]
188    fn separated_quads_are_distinct_components() {
189        let quads = [square(0, 0, 20), square(500, 500, 20)];
190        let linked = link_quads(&quads);
191        assert_eq!(neighbor_count(&linked[0]), 0);
192        assert_eq!(neighbor_count(&linked[1]), 0);
193        assert_eq!(connected_components(&linked), vec![vec![0], vec![1]]);
194    }
195
196    #[test]
197    fn linked_corner_snaps_to_midpoint() {
198        // Corners a pixel apart still link and snap to the midpoint.
199        let q0 = square(0, 0, 20);
200        let q1 = Quad {
201            corners: [(21, 21), (41, 21), (41, 41), (21, 41)],
202        };
203        let linked = link_quads(&[q0, q1]);
204        // Q0 corner 2 is (20,20); Q1 corner 0 is (21,21); midpoint (20.5,20.5).
205        assert_eq!(linked[0].corners[2], (20.5, 20.5));
206        assert_eq!(linked[1].corners[0], (20.5, 20.5));
207    }
208}
checkerboard_calibrate/chessboard/link.rs

checkerboard_calibrate/chessboard/
link.rs
