imageproc/
edges.rs

1//! Functions for detecting edges in images.
2
3use crate::definitions::{HasBlack, HasWhite};
4use crate::filter::gaussian_blur_f32;
5use crate::gradients::{horizontal_sobel, vertical_sobel};
6use image::{GenericImageView, GrayImage, ImageBuffer, Luma};
7use std::f32;
8
9/// Runs the canny edge detection algorithm.
10///
11/// Returns a binary image where edge pixels have a value of 255
12///  and non-edge pixels a value of 0.
13///
14/// # Params
15///
16/// - `low_threshold`: Low threshold for the hysteresis procedure.
17/// Edges with a strength higher than the low threshold will appear
18/// in the output image, if there are strong edges nearby.
19/// - `high_threshold`: High threshold for the hysteresis procedure.
20/// Edges with a strength higher than the high threshold will always
21/// appear as edges in the output image.
22///
23/// The greatest possible edge strength (and so largest sensible threshold)
24/// is`sqrt(5) * 2 * 255`, or approximately 1140.39.
25///
26/// This odd looking value is the result of using a standard
27/// definition of edge strength: the strength of an edge at a point `p` is
28/// defined to be `sqrt(dx^2 + dy^2)`, where `dx` and `dy` are the values
29/// of the horizontal and vertical Sobel gradients at `p`.
30pub fn canny(image: &GrayImage, low_threshold: f32, high_threshold: f32) -> GrayImage {
31    assert!(high_threshold >= low_threshold);
32    // Heavily based on the implementation proposed by wikipedia.
33    // 1. Gaussian blur.
34    const SIGMA: f32 = 1.4;
35    let blurred = gaussian_blur_f32(image, SIGMA);
36
37    // 2. Intensity of gradients.
38    let gx = horizontal_sobel(&blurred);
39    let gy = vertical_sobel(&blurred);
40    let g: Vec<f32> = gx
41        .iter()
42        .zip(gy.iter())
43        .map(|(h, v)| (*h as f32).hypot(*v as f32))
44        .collect::<Vec<f32>>();
45
46    let g = ImageBuffer::from_raw(image.width(), image.height(), g).unwrap();
47
48    // 3. Non-maximum-suppression (Make edges thinner)
49    let thinned = non_maximum_suppression(&g, &gx, &gy);
50
51    // 4. Hysteresis to filter out edges based on thresholds.
52    hysteresis(&thinned, low_threshold, high_threshold)
53}
54
55/// Finds local maxima to make the edges thinner.
56fn non_maximum_suppression(
57    g: &ImageBuffer<Luma<f32>, Vec<f32>>,
58    gx: &ImageBuffer<Luma<i16>, Vec<i16>>,
59    gy: &ImageBuffer<Luma<i16>, Vec<i16>>,
60) -> ImageBuffer<Luma<f32>, Vec<f32>> {
61    const RADIANS_TO_DEGREES: f32 = 180f32 / f32::consts::PI;
62    let mut out = ImageBuffer::from_pixel(g.width(), g.height(), Luma([0.0]));
63    for y in 1..g.height() - 1 {
64        for x in 1..g.width() - 1 {
65            let x_gradient = gx[(x, y)][0] as f32;
66            let y_gradient = gy[(x, y)][0] as f32;
67            let mut angle = (y_gradient).atan2(x_gradient) * RADIANS_TO_DEGREES;
68            if angle < 0.0 {
69                angle += 180.0
70            }
71            // Clamp angle.
72            let clamped_angle = if !(22.5..157.5).contains(&angle) {
73                0
74            } else if (22.5..67.5).contains(&angle) {
75                45
76            } else if (67.5..112.5).contains(&angle) {
77                90
78            } else if (112.5..157.5).contains(&angle) {
79                135
80            } else {
81                unreachable!()
82            };
83
84            // Get the two perpendicular neighbors.
85            let (cmp1, cmp2) = unsafe {
86                match clamped_angle {
87                    0 => (g.unsafe_get_pixel(x - 1, y), g.unsafe_get_pixel(x + 1, y)),
88                    45 => (
89                        g.unsafe_get_pixel(x + 1, y + 1),
90                        g.unsafe_get_pixel(x - 1, y - 1),
91                    ),
92                    90 => (g.unsafe_get_pixel(x, y - 1), g.unsafe_get_pixel(x, y + 1)),
93                    135 => (
94                        g.unsafe_get_pixel(x - 1, y + 1),
95                        g.unsafe_get_pixel(x + 1, y - 1),
96                    ),
97                    _ => unreachable!(),
98                }
99            };
100            let pixel = *g.get_pixel(x, y);
101            // If the pixel is not a local maximum, suppress it.
102            if pixel[0] < cmp1[0] || pixel[0] < cmp2[0] {
103                out.put_pixel(x, y, Luma([0.0]));
104            } else {
105                out.put_pixel(x, y, pixel);
106            }
107        }
108    }
109    out
110}
111
112/// Filter out edges with the thresholds.
113/// Non-recursive breadth-first search.
114fn hysteresis(
115    input: &ImageBuffer<Luma<f32>, Vec<f32>>,
116    low_thresh: f32,
117    high_thresh: f32,
118) -> ImageBuffer<Luma<u8>, Vec<u8>> {
119    let max_brightness = Luma::white();
120    let min_brightness = Luma::black();
121    // Init output image as all black.
122    let mut out = ImageBuffer::from_pixel(input.width(), input.height(), min_brightness);
123    // Stack. Possible optimization: Use previously allocated memory, i.e. gx.
124    let mut edges = Vec::with_capacity(((input.width() * input.height()) / 2) as usize);
125    for y in 1..input.height() - 1 {
126        for x in 1..input.width() - 1 {
127            let inp_pix = *input.get_pixel(x, y);
128            let out_pix = *out.get_pixel(x, y);
129            // If the edge strength is higher than high_thresh, mark it as an edge.
130            if inp_pix[0] >= high_thresh && out_pix[0] == 0 {
131                out.put_pixel(x, y, max_brightness);
132                edges.push((x, y));
133                // Track neighbors until no neighbor is >= low_thresh.
134                while !edges.is_empty() {
135                    let (nx, ny) = edges.pop().unwrap();
136                    let neighbor_indices = [
137                        (nx + 1, ny),
138                        (nx + 1, ny + 1),
139                        (nx, ny + 1),
140                        (nx - 1, ny - 1),
141                        (nx - 1, ny),
142                        (nx - 1, ny + 1),
143                    ];
144
145                    for neighbor_idx in &neighbor_indices {
146                        let in_neighbor = *input.get_pixel(neighbor_idx.0, neighbor_idx.1);
147                        let out_neighbor = *out.get_pixel(neighbor_idx.0, neighbor_idx.1);
148                        if in_neighbor[0] >= low_thresh && out_neighbor[0] == 0 {
149                            out.put_pixel(neighbor_idx.0, neighbor_idx.1, max_brightness);
150                            edges.push((neighbor_idx.0, neighbor_idx.1));
151                        }
152                    }
153                }
154            }
155        }
156    }
157    out
158}
159
160#[cfg(test)]
161mod tests {
162    use super::canny;
163    use crate::drawing::draw_filled_rect_mut;
164    use crate::rect::Rect;
165    use ::test;
166    use image::{GrayImage, Luma};
167
168    fn edge_detect_bench_image(width: u32, height: u32) -> GrayImage {
169        let mut image = GrayImage::new(width, height);
170        let (w, h) = (width as i32, height as i32);
171        let large = Rect::at(w / 4, h / 4).of_size(width / 2, height / 2);
172        let small = Rect::at(9, 9).of_size(3, 3);
173
174        draw_filled_rect_mut(&mut image, large, Luma([255]));
175        draw_filled_rect_mut(&mut image, small, Luma([255]));
176
177        image
178    }
179
180    #[bench]
181    fn bench_canny(b: &mut test::Bencher) {
182        let image = edge_detect_bench_image(250, 250);
183        b.iter(|| {
184            let output = canny(&image, 250.0, 300.0);
185            test::black_box(output);
186        });
187    }
188}
imageproc/edges.rs

imageproc/
edges.rs
