mtb_align/
shrink.rs

1use crate::Gray;
2use crate::strips::fill_rows;
3
4/// How a level of the pyramid is halved. Ward's table calls `ImageShrink2` a
5/// subsample; his text says "filtered down". Both readings are available.
6#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
7pub enum Shrink {
8    /// The mean of each 2x2 block, and the default: averaging keeps fine detail
9    /// from aliasing into the coarse levels.
10    #[default]
11    Average,
12    /// Every other row and column, as OpenCV's `AlignMTB` does.
13    Subsample,
14}
15
16/// Halves a plane, dropping an odd final row or column.
17///
18/// Flooring keeps both modes on the same grid and matches OpenCV.
19pub fn shrink2(gray: &Gray, shrink: Shrink) -> Gray {
20    let width = gray.width() / 2;
21    let height = gray.height() / 2;
22    let source = gray.as_slice();
23    let stride = gray.width();
24
25    let mut shrunk = vec![0; width * height];
26
27    fill_rows(&mut shrunk, width, |y, row| {
28        let top = 2 * y * stride;
29        let bottom = top + stride;
30
31        for (x, sample) in row.iter_mut().enumerate() {
32            let left = 2 * x;
33            *sample = match shrink {
34                Shrink::Average => {
35                    // u16: four samples overflow a u8. The +2 rounds to nearest.
36                    let total = source[top + left] as u16
37                        + source[top + left + 1] as u16
38                        + source[bottom + left] as u16
39                        + source[bottom + left + 1] as u16;
40                    ((total + 2) / 4) as u8
41                }
42                Shrink::Subsample => source[top + left],
43            };
44        }
45    });
46
47    Gray::from_vec(shrunk, width, height)
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53    use proptest::prelude::*;
54
55    fn counting(width: usize, height: usize) -> Gray {
56        Gray::from_vec((0..(width * height) as u8).collect(), width, height)
57    }
58
59    #[test]
60    fn averaging_takes_the_mean_of_each_block() {
61        let shrunk = shrink2(&counting(4, 4), Shrink::Average);
62
63        assert_eq!((shrunk.width(), shrunk.height()), (2, 2));
64        assert_eq!(shrunk.as_slice(), &[3, 5, 11, 13]);
65    }
66
67    /// Truncating would bias every level downward; rounding is free.
68    #[test]
69    fn averaging_rounds_to_nearest() {
70        let block = Gray::from_vec(vec![1, 2, 3, 4], 2, 2);
71
72        assert_eq!(shrink2(&block, Shrink::Average).as_slice(), &[3]);
73    }
74
75    #[test]
76    fn subsampling_takes_the_top_left_of_each_block() {
77        let shrunk = shrink2(&counting(4, 4), Shrink::Subsample);
78
79        assert_eq!((shrunk.width(), shrunk.height()), (2, 2));
80        assert_eq!(shrunk.as_slice(), &[0, 2, 8, 10]);
81    }
82
83    #[test]
84    fn an_odd_final_row_or_column_is_dropped() {
85        let source = counting(5, 3);
86
87        let averaged = shrink2(&source, Shrink::Average);
88        assert_eq!((averaged.width(), averaged.height()), (2, 1));
89        assert_eq!(averaged.as_slice(), &[3, 5]);
90
91        let subsampled = shrink2(&source, Shrink::Subsample);
92        assert_eq!((subsampled.width(), subsampled.height()), (2, 1));
93        assert_eq!(subsampled.as_slice(), &[0, 2]);
94    }
95
96    #[test]
97    fn a_saturated_block_averages_to_saturation() {
98        let block = Gray::from_vec(vec![255; 4], 2, 2);
99
100        assert_eq!(shrink2(&block, Shrink::Average).as_slice(), &[255]);
101    }
102
103    #[test]
104    fn a_plane_too_small_to_halve_shrinks_away() {
105        let shrunk = shrink2(&counting(1, 1), Shrink::Average);
106
107        assert_eq!((shrunk.width(), shrunk.height()), (0, 0));
108        assert!(shrunk.as_slice().is_empty());
109    }
110
111    proptest! {
112        /// The pyramid bookkeeping assumes both modes stay the same shape.
113        #[test]
114        fn both_modes_halve_to_the_same_size(width in 0usize..40, height in 0usize..40) {
115            let source = Gray::from_vec(vec![9; width * height], width, height);
116
117            let averaged = shrink2(&source, Shrink::Average);
118            let subsampled = shrink2(&source, Shrink::Subsample);
119
120            prop_assert_eq!(averaged.width(), width / 2);
121            prop_assert_eq!(averaged.height(), height / 2);
122            prop_assert_eq!(subsampled.width(), width / 2);
123            prop_assert_eq!(subsampled.height(), height / 2);
124        }
125
126        #[test]
127        fn a_constant_plane_survives_either_mode(
128            value in 0u8..=255,
129            width in 2usize..40,
130            height in 2usize..40,
131        ) {
132            let source = Gray::from_vec(vec![value; width * height], width, height);
133
134            for mode in [Shrink::Average, Shrink::Subsample] {
135                for &sample in shrink2(&source, mode).as_slice() {
136                    prop_assert_eq!(sample, value);
137                }
138            }
139        }
140    }
141}
mtb_align/shrink.rs

mtb_align/
shrink.rs
