checkerboard_calibrate/chessboard/
contour.rs

1// Copyright (C) The Strand-Braid Authors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Suzuki–Abe border following — a port of OpenCV's `findContours`
5//! (`RETR_LIST`, `CHAIN_APPROX_NONE`).
6//!
7//! Reference: S. Suzuki and K. Abe, "Topological structural analysis of
8//! digitized binary images by border following", CVGIP 30(1), 1985. OpenCV's
9//! `findContours` implements the same algorithm, so the set of border pixels
10//! produced here matches OpenCV exactly. Ordering within a contour is an
11//! implementation detail and is not required to match.
12//!
13//! Input is a binary image (0 = background, non-zero = foreground). Output is
14//! the list of borders; each border is a closed sequence of `(x, y)` pixels,
15//! flagged as an outer or hole border.
16
17/// A traced border.
18#[derive(Clone, Debug)]
19pub struct Contour {
20    /// Border pixels as `(x, y)` = `(col, row)`, in trace order.
21    pub points: Vec<(i32, i32)>,
22    /// Whether this is a hole border (background enclosed by foreground) as
23    /// opposed to an outer border.
24    pub is_hole: bool,
25}
26
27/// Clockwise 8-neighborhood offsets `(d_row, d_col)`, index 0 = East.
28const NEI: [(i32, i32); 8] = [
29    (0, 1),
30    (1, 1),
31    (1, 0),
32    (1, -1),
33    (0, -1),
34    (-1, -1),
35    (-1, 0),
36    (-1, 1),
37];
38
39fn dir_index(dr: i32, dc: i32) -> usize {
40    NEI.iter().position(|&(r, c)| r == dr && c == dc).unwrap()
41}
42
43#[inline]
44fn get(img: &[i32], w: i32, h: i32, r: i32, c: i32) -> i32 {
45    if r < 0 || c < 0 || r >= h || c >= w {
46        0
47    } else {
48        img[(r * w + c) as usize]
49    }
50}
51
52/// Find all borders in a binary image.
53pub fn find_contours(bin: &[u8], width: usize, height: usize) -> Vec<Contour> {
54    assert_eq!(bin.len(), width * height, "bin length must be width*height");
55    let (w, h) = (width as i32, height as i32);
56    let mut img: Vec<i32> = bin.iter().map(|&v| (v != 0) as i32).collect();
57
58    let mut contours = Vec::new();
59    // Border counter; 1 is the implicit image frame. The full Suzuki-Abe
60    // hierarchy (parent links via the last-seen border number) is not
61    // reconstructed here — the quad detector only needs the borders and their
62    // outer/hole type.
63    let mut nbd = 1i32;
64
65    for i in 0..h {
66        for j in 0..w {
67            let fij = img[(i * w + j) as usize];
68            if fij == 0 {
69                continue;
70            }
71
72            let from;
73            let is_hole;
74            if fij == 1 && get(&img, w, h, i, j - 1) == 0 {
75                // Outer border start: foreground pixel with background to the left.
76                nbd += 1;
77                from = (i, j - 1);
78                is_hole = false;
79            } else if fij >= 1 && get(&img, w, h, i, j + 1) == 0 {
80                // Hole border start: pixel with background to the right.
81                nbd += 1;
82                from = (i, j + 1);
83                is_hole = true;
84            } else {
85                continue;
86            }
87
88            let mut points = Vec::new();
89            border_follow(&mut img, w, h, (i, j), from, nbd, &mut points);
90            contours.push(Contour { points, is_hole });
91        }
92    }
93    contours
94}
95
96/// Trace one border starting at `start`, coming from background pixel `from`,
97/// labeling visited pixels with `nbd`.
98fn border_follow(
99    img: &mut [i32],
100    w: i32,
101    h: i32,
102    start: (i32, i32),
103    from: (i32, i32),
104    nbd: i32,
105    points: &mut Vec<(i32, i32)>,
106) {
107    let (i, j) = start;
108    let idx = |r: i32, c: i32| (r * w + c) as usize;
109
110    // 3.1: clockwise from `from`, find the first foreground neighbor.
111    let from_dir = dir_index(from.0 - i, from.1 - j);
112    let mut found = None;
113    for k in 0..8 {
114        let d = (from_dir + k) & 7;
115        let (r, c) = (i + NEI[d].0, j + NEI[d].1);
116        if get(img, w, h, r, c) != 0 {
117            found = Some((r, c));
118            break;
119        }
120    }
121    let (i1, j1) = match found {
122        // Isolated pixel: a single-point border.
123        None => {
124            img[idx(i, j)] = -nbd;
125            points.push((j, i));
126            return;
127        }
128        Some(p) => p,
129    };
130
131    let (mut i2, mut j2) = (i1, j1);
132    let (mut i3, mut j3) = (i, j);
133    loop {
134        // 3.3: counterclockwise around (i3,j3) starting one step CCW from (i2,j2).
135        let d2 = dir_index(i2 - i3, j2 - j3);
136        let mut examined_east_zero = false;
137        let mut p4 = None;
138        for k in 1..=8 {
139            let d = (d2 + 8 - k) & 7;
140            let (r, c) = (i3 + NEI[d].0, j3 + NEI[d].1);
141            let val = get(img, w, h, r, c);
142            if d == 0 && val == 0 {
143                // The east neighbor was examined and is background.
144                examined_east_zero = true;
145            }
146            if val != 0 {
147                p4 = Some((r, c));
148                break;
149            }
150        }
151        let (i4, j4) = p4.expect("border closes on itself");
152
153        // 3.4: label the current pixel.
154        if examined_east_zero {
155            img[idx(i3, j3)] = -nbd;
156        } else if img[idx(i3, j3)] == 1 {
157            img[idx(i3, j3)] = nbd;
158        }
159        points.push((j3, i3));
160
161        // 3.5: stop when we return to the start along the first edge.
162        if (i4, j4) == (i, j) && (i3, j3) == (i1, j1) {
163            break;
164        }
165        (i2, j2) = (i3, j3);
166        (i3, j3) = (i4, j4);
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173    use std::collections::BTreeSet;
174
175    fn img(rows: &[&str]) -> (Vec<u8>, usize, usize) {
176        let h = rows.len();
177        let w = rows[0].len();
178        let mut data = vec![0u8; w * h];
179        for (r, row) in rows.iter().enumerate() {
180            for (c, ch) in row.chars().enumerate() {
181                data[r * w + c] = if ch == '#' { 255 } else { 0 };
182            }
183        }
184        (data, w, h)
185    }
186
187    fn pointset(c: &Contour) -> BTreeSet<(i32, i32)> {
188        c.points.iter().copied().collect()
189    }
190
191    #[test]
192    fn single_pixel() {
193        let (data, w, h) = img(&[".....", ".....", "..#..", ".....", "....."]);
194        let cs = find_contours(&data, w, h);
195        assert_eq!(cs.len(), 1);
196        assert_eq!(cs[0].points, vec![(2, 2)]);
197        assert!(!cs[0].is_hole);
198    }
199
200    #[test]
201    fn solid_square_outer_border() {
202        let (data, w, h) = img(&[".....", ".###.", ".###.", ".###.", "....."]);
203        let cs = find_contours(&data, w, h);
204        assert_eq!(cs.len(), 1);
205        assert!(!cs[0].is_hole);
206        // The border is the 8 perimeter pixels (the center is interior).
207        let expected: BTreeSet<(i32, i32)> = [
208            (1, 1),
209            (2, 1),
210            (3, 1),
211            (1, 2),
212            (3, 2),
213            (1, 3),
214            (2, 3),
215            (3, 3),
216        ]
217        .into_iter()
218        .collect();
219        assert_eq!(pointset(&cs[0]), expected);
220    }
221
222    #[test]
223    fn ring_has_outer_and_hole_borders() {
224        // 5x5 solid block with a single-pixel hole in the middle.
225        let (data, w, h) = img(&[
226            ".......", ".#####.", ".#####.", ".##.##.", ".#####.", ".#####.", ".......",
227        ]);
228        let cs = find_contours(&data, w, h);
229        assert_eq!(cs.len(), 2, "expected one outer and one hole border");
230        assert!(!cs[0].is_hole, "first found border should be outer");
231        assert!(cs[1].is_hole, "second should be the hole border");
232        // Outer border = the 16 perimeter pixels of the 5x5 block.
233        assert_eq!(
234            cs[0].points.iter().copied().collect::<BTreeSet<_>>().len(),
235            16
236        );
237        // Hole border surrounds the missing pixel at (3,3): its 8 neighbors.
238        let hole = pointset(&cs[1]);
239        assert!(hole.contains(&(2, 3)) && hole.contains(&(4, 3)));
240        assert!(!hole.contains(&(3, 3)));
241    }
242
243    #[test]
244    fn two_separate_squares() {
245        let (data, w, h) = img(&[".......", ".##.##.", ".##.##.", "......."]);
246        let cs = find_contours(&data, w, h);
247        assert_eq!(cs.len(), 2);
248        assert!(cs.iter().all(|c| !c.is_hole));
249    }
250}
checkerboard_calibrate/chessboard/contour.rs

checkerboard_calibrate/chessboard/
contour.rs
