visioncortex/image/
sat.rs

1use crate::{ColorImage, PointI32};
2
3/// A data structure to efficiently compute summed pixel values over regions in an image (repeatedly).
4pub struct SummedAreaTable {
5    pub sums: Vec<u32>,
6    pub width: usize,
7    pub height: usize,
8}
9
10impl SummedAreaTable {
11    /// Creates an SAT of the same size of image, where each entry (x,y) is the sum of pixel
12    /// values of the block of pixels with bottom right corner at (x,y) in image.
13    ///
14    /// This construction takes 1 pass through the pixels in image.
15    pub fn from_color_image(image: &ColorImage) -> Self {
16        let (width, height) = (image.width, image.height);
17
18        let mut sums = vec![0; width * height];
19        let get_sum = |x: i32, y: i32, sums: &Vec<u32>| {
20            if x >= 0 && y >= 0 {
21                sums[(y * width as i32 + x) as usize]
22            } else {
23                0
24            }
25        };
26
27        // Closure to get pixel intensity from image
28        let get_val = |x: usize, y: usize| {
29            let c = image.get_pixel(x, y);
30            (c.r as u32 + c.g as u32 + c.b as u32) / 3
31        };
32
33        // Fill the sums starting from the top-left corner
34        for y in 0..height as i32 {
35            for x in 0..width as i32 {
36                let up_left = get_sum(x-1, y-1, &sums);
37                let up = get_sum(x, y-1, &sums);
38                let left = get_sum(x-1, y, &sums);
39                let curr = get_val(x as usize, y as usize);
40                sums[(y * width as i32 + x) as usize] = up + left + curr - up_left;
41            }
42        }
43
44        Self {
45            sums,
46            width,
47            height
48        }
49    }
50
51    /// Returns the entry in the SAT.
52    ///
53    /// If the input point is out of boundary, this function returns 0.
54    ///
55    /// This is only to facilitate the implementation of other functions; avoid calling this function directly.
56    pub fn get_bot_right_sum(&self, x: i32, y: i32) -> u32 {
57        if x >= 0 && y >= 0 && x < self.width as i32 && y < self.height as i32 {
58            self.sums[(y * self.width as i32 + x) as usize]
59        } else {
60            0
61        }
62    }
63
64    fn correct_top_left_bot_right(top_left: &PointI32, bot_right: &PointI32) -> bool {
65        top_left.x <= bot_right.x && top_left.y <= bot_right.y
66    }
67
68    /// Computes the sum of pixel values in the specified region in O(1) time.
69    pub fn get_region_sum_top_left_bot_right(&self, top_left: PointI32, bot_right: PointI32) -> u32 {
70        if !Self::correct_top_left_bot_right(&top_left, &bot_right) {
71            panic!("Top left and bottom right points are invalid.")
72        }
73        let left_region = self.get_bot_right_sum(top_left.x-1, bot_right.y);
74        let up_region = self.get_bot_right_sum(bot_right.x, top_left.y-1);
75        let overlap = self.get_bot_right_sum(top_left.x-1, top_left.y-1);
76        let total = self.get_bot_right_sum(bot_right.x, bot_right.y);
77
78        total + overlap - left_region - up_region
79    }
80
81    /// Computes the sum of pixel values in the specified region in O(1) time.
82    pub fn get_region_sum_x_y_w_h(&self, x: usize, y: usize, w: usize, h: usize) -> u32 {
83        let top_left = PointI32::new(x as i32, y as i32);
84        let bot_right = PointI32::new((x+w-1) as i32, (y+h-1) as i32);
85        self.get_region_sum_top_left_bot_right(top_left, bot_right)
86    }
87
88    /// Computes the mean of pixel values in the specified region in O(1) time.
89    pub fn get_region_mean_top_left_bot_right(&self, top_left: PointI32, bot_right: PointI32) -> f64 {
90        let w = bot_right.x - top_left.x + 1;
91        let h = bot_right.y - top_left.y + 1;
92        self.get_region_mean_x_y_w_h(top_left.x as usize, top_left.y as usize, w as usize, h as usize)
93    }
94
95    /// Computes the mean of pixel values in the specified region in O(1) time.
96    pub fn get_region_mean_x_y_w_h(&self, x: usize, y: usize, w: usize, h: usize) -> f64 {
97        self.get_region_sum_x_y_w_h(x, y, w, h) as f64 / (w*h) as f64
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use crate::Color;
104
105    use super::*;
106
107    fn create_color_image_helper(width: usize, height: usize, pixels: Vec<u8>) -> ColorImage {
108        let mut image = ColorImage::new_w_h(width, height);
109        for (i, &val) in pixels.iter().enumerate() {
110            image.set_pixel_at(i, &Color::new(val, val, val));
111        }
112        image
113    }
114
115    #[test]
116    fn sat_construct() {
117        // Example from wikipedia
118        let pixels = vec![
119            31, 2, 4, 33, 5, 36,
120            12, 26, 9, 10, 29, 25,
121            13, 17, 21, 22, 20, 18,
122            24, 23, 15, 16, 14, 19,
123            30, 8, 28, 27, 11, 7,
124            1, 35, 34, 3, 32, 6,
125        ];
126        let image = create_color_image_helper(6, 6, pixels);
127        let sat = SummedAreaTable::from_color_image(&image);
128        assert_eq!(sat.get_bot_right_sum(0, 0), 31);
129        assert_eq!(sat.get_bot_right_sum(1, 1), 71);
130        assert_eq!(sat.get_bot_right_sum(1, 2), 101);
131        assert_eq!(sat.get_bot_right_sum(5, 0), 111);
132        assert_eq!(sat.get_bot_right_sum(0, 5), 111);
133        assert_eq!(sat.get_bot_right_sum(5, 5), 666);
134        assert_eq!(sat.get_bot_right_sum(4, 4), 450);
135        assert_eq!(sat.get_bot_right_sum(1, 4), 186);
136        assert_eq!(sat.get_bot_right_sum(4, 2), 254);
137    }
138
139    #[test]
140    fn sat_region_sum() {
141        // Example from wikipedia
142        let pixels = vec![
143            31, 2, 4, 33, 5, 36,
144            12, 26, 9, 10, 29, 25,
145            13, 17, 21, 22, 20, 18,
146            24, 23, 15, 16, 14, 19,
147            30, 8, 28, 27, 11, 7,
148            1, 35, 34, 3, 32, 6,
149        ];
150        let image = create_color_image_helper(6, 6, pixels);
151        let sat = SummedAreaTable::from_color_image(&image);
152        assert_eq!(sat.get_region_sum_top_left_bot_right(PointI32::new(2, 3), PointI32::new(4, 4)), 111);
153        assert_eq!(sat.get_region_sum_x_y_w_h(2, 3, 3, 2), 111);
154        assert_eq!(sat.get_region_sum_x_y_w_h(0, 0, 6, 6), 666);
155        assert_eq!(sat.get_region_sum_x_y_w_h(0, 0, 1, 6), 111);
156        assert_eq!(sat.get_region_sum_x_y_w_h(0, 0, 6, 1), 111);
157        assert_eq!(sat.get_region_sum_x_y_w_h(2, 4, 3, 2), 135);
158        assert_eq!(sat.get_region_sum_x_y_w_h(1, 2, 3, 4), 249);
159    }
160
161    #[test]
162    fn sat_region_mean() {
163        // Example from wikipedia
164        let pixels = vec![
165            31, 2, 4, 33, 5, 36,
166            12, 26, 9, 10, 29, 25,
167            13, 17, 21, 22, 20, 18,
168            24, 23, 15, 16, 14, 19,
169            30, 8, 28, 27, 11, 7,
170            1, 35, 34, 3, 32, 6,
171        ];
172        let image = create_color_image_helper(6, 6, pixels);
173        let sat = SummedAreaTable::from_color_image(&image);
174        assert!(sat.get_region_mean_top_left_bot_right(PointI32::new(2, 3), PointI32::new(4, 4)) - (111.0 / 6.0) < 1e-6);
175        assert!(sat.get_region_mean_x_y_w_h(2, 3, 3, 2) - (111.0 / 6.0) < 1e-6);
176        assert!(sat.get_region_mean_x_y_w_h(0, 0, 6, 6) - (666.0 / 36.0) < 1e-6);
177        assert!(sat.get_region_mean_x_y_w_h(0, 0, 1, 6) - (111.0 / 6.0) < 1e-6);
178        assert!(sat.get_region_mean_x_y_w_h(0, 0, 6, 1) - (111.0 / 6.0) < 1e-6);
179        assert!(sat.get_region_mean_x_y_w_h(2, 4, 3, 2) - (135.0 / 6.0) < 1e-6);
180        assert!(sat.get_region_mean_x_y_w_h(1, 2, 3, 4) - (249.0 / 12.0) < 1e-6);
181    }
182}
visioncortex/image/sat.rs

visioncortex/image/
sat.rs
