imageproc/
contours.rs

1//! Functions for finding border contours within binary images.
2
3use crate::point::Point;
4use image::GrayImage;
5use num::{cast, Num, NumCast};
6use std::collections::VecDeque;
7
8/// Whether a border of a foreground region borders an enclosing background region or a contained background region.
9#[derive(Debug, Copy, Clone, PartialEq, Eq)]
10pub enum BorderType {
11    /// A border between a foreground region and the backround region enclosing it.
12    /// All points in the border lie within the foreground region.
13    Outer,
14    /// A border between a foreground region and a background region contained within it.
15    /// All points in the border lie within the foreground region.
16    Hole,
17}
18
19/// A border of an 8-connected foreground region.
20#[derive(Debug)]
21pub struct Contour<T> {
22    /// The points in the border.
23    pub points: Vec<Point<T>>,
24    /// Whether this is an outer border or a hole border.
25    pub border_type: BorderType,
26    /// Calls to `find_contours` and `find_contours_with_threshold` return a `Vec` of all borders
27    /// in an image. This field provides the index for the parent of the current border in that `Vec`.
28    pub parent: Option<usize>,
29}
30
31impl<T> Contour<T> {
32    /// Construct a contour.
33    pub fn new(points: Vec<Point<T>>, border_type: BorderType, parent: Option<usize>) -> Self {
34        Contour {
35            points,
36            border_type,
37            parent,
38        }
39    }
40}
41
42/// Finds all borders of foreground regions in an image. All non-zero pixels are
43/// treated as belonging to the foreground.
44///
45/// Based on the algorithm proposed by Suzuki and Abe: Topological Structural
46/// Analysis of Digitized Binary Images by Border Following.
47pub fn find_contours<T>(image: &GrayImage) -> Vec<Contour<T>>
48where
49    T: Num + NumCast + Copy + PartialEq + Eq,
50{
51    find_contours_with_threshold(image, 0)
52}
53
54/// Finds all borders of foreground regions in an image. All pixels with intensity strictly greater
55/// than `threshold` are treated as belonging to the foreground.
56///
57/// Based on the algorithm proposed by Suzuki and Abe: Topological Structural
58/// Analysis of Digitized Binary Images by Border Following.
59pub fn find_contours_with_threshold<T>(image: &GrayImage, threshold: u8) -> Vec<Contour<T>>
60where
61    T: Num + NumCast + Copy + PartialEq + Eq,
62{
63    let width = image.width() as usize;
64    let height = image.height() as usize;
65    let mut image_values = vec![vec![0i32; height]; width];
66
67    for y in 0..height {
68        for x in 0..width {
69            if image.get_pixel(x as u32, y as u32).0[0] > threshold {
70                image_values[x][y] = 1;
71            }
72        }
73    }
74
75    let mut diffs = VecDeque::from(vec![
76        Point::new(-1, 0),  // w
77        Point::new(-1, -1), // nw
78        Point::new(0, -1),  // n
79        Point::new(1, -1),  // ne
80        Point::new(1, 0),   // e
81        Point::new(1, 1),   // se
82        Point::new(0, 1),   // s
83        Point::new(-1, 1),  // sw
84    ]);
85
86    let mut contours: Vec<Contour<T>> = Vec::new();
87    let mut curr_border_num = 1;
88
89    for y in 0..height {
90        let mut parent_border_num = 1;
91
92        for x in 0..width {
93            if image_values[x][y] == 0 {
94                continue;
95            }
96
97            if let Some((adj, border_type)) =
98                if image_values[x][y] == 1 && x > 0 && image_values[x - 1][y] == 0 {
99                    Some((Point::new(x - 1, y), BorderType::Outer))
100                } else if image_values[x][y] > 0 && x + 1 < width && image_values[x + 1][y] == 0 {
101                    if image_values[x][y] > 1 {
102                        parent_border_num = image_values[x][y] as usize;
103                    }
104                    Some((Point::new(x + 1, y), BorderType::Hole))
105                } else {
106                    None
107                }
108            {
109                curr_border_num += 1;
110
111                let parent = if parent_border_num > 1 {
112                    let parent_index = parent_border_num - 2;
113                    let parent_contour = &contours[parent_index];
114                    if (border_type == BorderType::Outer)
115                        ^ (parent_contour.border_type == BorderType::Outer)
116                    {
117                        Some(parent_index)
118                    } else {
119                        parent_contour.parent
120                    }
121                } else {
122                    None
123                };
124
125                let mut contour_points = Vec::new();
126                let curr = Point::new(x, y);
127                rotate_to_value(&mut diffs, adj.to_i32() - curr.to_i32());
128
129                if let Some(pos1) = diffs.iter().find_map(|diff| {
130                    get_position_if_non_zero_pixel(&image_values, curr.to_i32() + *diff)
131                }) {
132                    let mut pos2 = pos1;
133                    let mut pos3 = curr;
134
135                    loop {
136                        contour_points
137                            .push(Point::new(cast(pos3.x).unwrap(), cast(pos3.y).unwrap()));
138                        rotate_to_value(&mut diffs, pos2.to_i32() - pos3.to_i32());
139                        let pos4 = diffs
140                            .iter()
141                            .rev() // counter-clockwise
142                            .find_map(|diff| {
143                                get_position_if_non_zero_pixel(&image_values, pos3.to_i32() + *diff)
144                            })
145                            .unwrap();
146
147                        let mut is_right_edge = false;
148                        for diff in diffs.iter().rev() {
149                            if *diff == (pos4.to_i32() - pos3.to_i32()) {
150                                break;
151                            }
152                            if *diff == Point::new(1, 0) {
153                                is_right_edge = true;
154                                break;
155                            }
156                        }
157
158                        if pos3.x + 1 == width || is_right_edge {
159                            image_values[pos3.x][pos3.y] = -curr_border_num;
160                        } else if image_values[pos3.x][pos3.y] == 1 {
161                            image_values[pos3.x][pos3.y] = curr_border_num;
162                        }
163
164                        if pos4 == curr && pos3 == pos1 {
165                            break;
166                        }
167
168                        pos2 = pos3;
169                        pos3 = pos4;
170                    }
171                } else {
172                    contour_points.push(Point::new(cast(x).unwrap(), cast(y).unwrap()));
173                    image_values[x][y] = -curr_border_num;
174                }
175                contours.push(Contour::new(contour_points, border_type, parent));
176            }
177
178            if image_values[x][y] != 1 {
179                parent_border_num = image_values[x][y].abs() as usize;
180            }
181        }
182    }
183
184    contours
185}
186
187fn rotate_to_value<T: Eq + Copy>(values: &mut VecDeque<T>, value: T) {
188    let rotate_pos = values.iter().position(|x| *x == value).unwrap();
189    values.rotate_left(rotate_pos);
190}
191
192fn get_position_if_non_zero_pixel(image: &[Vec<i32>], curr: Point<i32>) -> Option<Point<usize>> {
193    let (width, height) = (image.len() as i32, image[0].len() as i32);
194    let in_bounds = curr.x > -1 && curr.x < width && curr.y > -1 && curr.y < height;
195
196    if in_bounds && image[curr.x as usize][curr.y as usize] != 0 {
197        Some(Point::new(curr.x as usize, curr.y as usize))
198    } else {
199        None
200    }
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206    use crate::point::Point;
207
208    // Checks that a contour has the expected border type and parent, and
209    // that it contains each of a given set of points.
210    fn check_contour<T: Eq>(
211        contour: &Contour<T>,
212        expected_border_type: BorderType,
213        expected_parent: Option<usize>,
214        required_points: &[Point<T>],
215    ) {
216        for point in required_points {
217            assert!(contour.points.contains(point));
218        }
219        assert_eq!(contour.border_type, expected_border_type);
220        assert_eq!(contour.parent, expected_parent);
221    }
222
223    #[test]
224    fn test_contours_structured() {
225        use crate::drawing::draw_polygon_mut;
226        use image::Luma;
227
228        let white = Luma([255u8]);
229        let black = Luma([0u8]);
230
231        let mut image = GrayImage::from_pixel(300, 300, black);
232        // border 1 (outer)
233        draw_polygon_mut(
234            &mut image,
235            &[
236                Point::new(20, 20),
237                Point::new(280, 20),
238                Point::new(280, 280),
239                Point::new(20, 280),
240            ],
241            white,
242        );
243        // border 2 (hole)
244        draw_polygon_mut(
245            &mut image,
246            &[
247                Point::new(40, 40),
248                Point::new(260, 40),
249                Point::new(260, 260),
250                Point::new(40, 260),
251            ],
252            black,
253        );
254        // border 3 (outer)
255        draw_polygon_mut(
256            &mut image,
257            &[
258                Point::new(60, 60),
259                Point::new(240, 60),
260                Point::new(240, 240),
261                Point::new(60, 240),
262            ],
263            white,
264        );
265        // border 4 (hole)
266        draw_polygon_mut(
267            &mut image,
268            &[
269                Point::new(80, 80),
270                Point::new(220, 80),
271                Point::new(220, 220),
272                Point::new(80, 220),
273            ],
274            black,
275        );
276        // rectangle in the corner (outer)
277        draw_polygon_mut(
278            &mut image,
279            &[
280                Point::new(290, 290),
281                Point::new(300, 290),
282                Point::new(300, 300),
283                Point::new(290, 300),
284            ],
285            white,
286        );
287
288        let contours = find_contours::<i32>(&image);
289        assert_eq!(contours.len(), 5);
290
291        // border 1
292        check_contour(
293            &contours[0],
294            BorderType::Outer,
295            None,
296            &[
297                Point::new(20, 20),
298                Point::new(280, 20),
299                Point::new(280, 280),
300                Point::new(20, 280),
301            ],
302        );
303
304        // border 2
305        check_contour(
306            &contours[1],
307            BorderType::Hole,
308            Some(0),
309            &[
310                Point::new(39, 40),
311                Point::new(261, 40),
312                Point::new(261, 260),
313                Point::new(39, 260),
314            ],
315        );
316
317        // border 3
318        check_contour(
319            &contours[2],
320            BorderType::Outer,
321            Some(1),
322            &[
323                Point::new(60, 60),
324                Point::new(240, 60),
325                Point::new(240, 240),
326                Point::new(60, 220),
327            ],
328        );
329
330        // border 4
331        check_contour(
332            &contours[3],
333            BorderType::Hole,
334            Some(2),
335            &[
336                Point::new(79, 80),
337                Point::new(221, 80),
338                Point::new(221, 220),
339                Point::new(79, 220),
340            ],
341        );
342
343        // rectangle in the corner
344        check_contour(
345            &contours[4],
346            BorderType::Outer,
347            None,
348            &[
349                Point::new(290, 290),
350                Point::new(299, 290),
351                Point::new(299, 299),
352                Point::new(290, 299),
353            ],
354        );
355    }
356
357    #[test]
358    fn find_contours_basic_test() {
359        use crate::definitions::HasWhite;
360        use crate::drawing::draw_polygon_mut;
361        use image::Luma;
362
363        let mut image = GrayImage::new(15, 20);
364        draw_polygon_mut(
365            &mut image,
366            &[Point::new(5, 5), Point::new(11, 5)],
367            Luma::white(),
368        );
369
370        draw_polygon_mut(
371            &mut image,
372            &[Point::new(11, 5), Point::new(11, 9)],
373            Luma::white(),
374        );
375
376        draw_polygon_mut(
377            &mut image,
378            &[Point::new(11, 9), Point::new(5, 9)],
379            Luma::white(),
380        );
381
382        draw_polygon_mut(
383            &mut image,
384            &[Point::new(5, 5), Point::new(5, 9)],
385            Luma::white(),
386        );
387
388        draw_polygon_mut(
389            &mut image,
390            &[Point::new(8, 5), Point::new(8, 9)],
391            Luma::white(),
392        );
393
394        *image.get_pixel_mut(13, 6) = Luma::white();
395
396        let contours = find_contours::<u32>(&image);
397        assert_eq!(contours.len(), 4);
398
399        check_contour(
400            &contours[0],
401            BorderType::Outer,
402            None,
403            &[
404                Point::new(5, 5),
405                Point::new(11, 5),
406                Point::new(5, 9),
407                Point::new(11, 9),
408            ],
409        );
410        assert!(!contours[0].points.contains(&Point::new(13, 6)));
411
412        check_contour(
413            &contours[1],
414            BorderType::Hole,
415            Some(0),
416            &[
417                Point::new(5, 6),
418                Point::new(8, 6),
419                Point::new(6, 9),
420                Point::new(8, 8),
421            ],
422        );
423        assert!(!contours[1].points.contains(&Point::new(10, 5)));
424        assert!(!contours[1].points.contains(&Point::new(10, 9)));
425        assert!(!contours[1].points.contains(&Point::new(13, 6)));
426
427        check_contour(
428            &contours[2],
429            BorderType::Hole,
430            Some(0),
431            &[
432                Point::new(8, 6),
433                Point::new(10, 5),
434                Point::new(8, 8),
435                Point::new(10, 9),
436            ],
437        );
438        assert!(!contours[2].points.contains(&Point::new(6, 9)));
439        assert!(!contours[2].points.contains(&Point::new(5, 6)));
440        assert!(!contours[2].points.contains(&Point::new(13, 6)));
441
442        assert_eq!(contours[3].border_type, BorderType::Outer);
443        assert_eq!(contours[3].points, [Point::new(13, 6)]);
444        assert_eq!(contours[3].parent, None);
445    }
446
447    #[test]
448    fn get_contours_approx_points() {
449        use crate::drawing::draw_polygon_mut;
450        use image::{GrayImage, Luma};
451        let mut image = GrayImage::from_pixel(300, 300, Luma([0]));
452        let white = Luma([255]);
453
454        let star = vec![
455            Point::new(100, 20),
456            Point::new(120, 35),
457            Point::new(140, 30),
458            Point::new(115, 45),
459            Point::new(130, 60),
460            Point::new(100, 50),
461            Point::new(80, 55),
462            Point::new(90, 40),
463            Point::new(60, 25),
464            Point::new(90, 35),
465        ];
466        draw_polygon_mut(&mut image, &star, white);
467        let contours = find_contours::<u32>(&image);
468
469        let c1_approx = crate::geometry::approximate_polygon_dp(
470            &contours[0].points,
471            crate::geometry::arc_length(&contours[0].points, true) * 0.01,
472            true,
473        );
474        assert_eq!(
475            c1_approx,
476            vec![
477                Point::new(100, 20),
478                Point::new(90, 35),
479                Point::new(60, 25),
480                Point::new(90, 40),
481                Point::new(80, 55),
482                Point::new(101, 50),
483                Point::new(130, 60),
484                Point::new(115, 45),
485                Point::new(140, 30),
486                Point::new(120, 35)
487            ]
488        );
489    }
490}
imageproc/contours.rs

imageproc/
contours.rs
