smart-package-tracker 0.4.0

//! Deciding which pixels are dark.
//!
//! A scan-line decoder needs a clean two-level signal, and a real image never
//! arrives as one: a photographed label is brighter on one side, a flatbed
//! scan carries a paper-grey background, an anti-aliased render has grey pixel
//! edges. A single global threshold gets all three wrong somewhere.
//!
//! So the threshold is computed per block and then smoothed across
//! neighbouring blocks, which lets it follow a lighting gradient while still
//! being stable inside a flat region. The approach is the one ZXing calls a
//! hybrid binariser.

use alloc::vec;
use alloc::vec::Vec;

use super::GrayImage;
use crate::symbology::BitMatrix;

/// Side of the square block each local threshold is computed over.
///
/// At 300 dpi and a 13 mil X-dimension a module is about 4 pixels, so an
/// 8-pixel block spans a bar or two: small enough to track a gradient, large
/// enough to contain both ink and paper.
const BLOCK: u32 = 8;

/// Radius, in blocks, of the neighbourhood each block's threshold averages
/// over. Two blocks each side is a 5x5 window.
const SMOOTH_RADIUS: u32 = 2;

/// A block whose luminance spans no more than this holds only one of ink and
/// paper, so its own average says nothing about where the boundary is.
const MIN_DYNAMIC_RANGE: u32 = 24;

/// Threshold `image` into dark (`true`) and light (`false`) modules.
///
/// The result is the same size as the image; one pixel is one entry, with no
/// resampling. Turning pixels into *modules* is the scan line's job, because
/// only it knows where the symbol starts.
pub(crate) fn binarize(image: &GrayImage) -> BitMatrix {
    let (w, h) = (image.width(), image.height());
    let (bw, bh) = (w.div_ceil(BLOCK), h.div_ceil(BLOCK));

    let black_points = black_points(image, bw, bh);
    let mut matrix = BitMatrix::new(w, h);

    for by in 0..bh {
        for bx in 0..bw {
            let threshold = smoothed(&black_points, bw, bh, bx, by);
            let (x0, y0) = (bx * BLOCK, by * BLOCK);
            for y in y0..(y0 + BLOCK).min(h) {
                for x in x0..(x0 + BLOCK).min(w) {
                    if u32::from(image.pixel(x, y)) <= threshold {
                        matrix.set(x, y, true);
                    }
                }
            }
        }
    }

    matrix
}

/// The luminance that separates ink from paper within each block.
fn black_points(image: &GrayImage, bw: u32, bh: u32) -> Vec<u32> {
    let (w, h) = (image.width(), image.height());
    let mut points = vec![0u32; (bw as usize) * (bh as usize)];

    for by in 0..bh {
        for bx in 0..bw {
            let (x0, y0) = (bx * BLOCK, by * BLOCK);
            let (x1, y1) = ((x0 + BLOCK).min(w), (y0 + BLOCK).min(h));

            let mut sum = 0u32;
            let mut count = 0u32;
            let mut min = u32::MAX;
            let mut max = 0u32;
            for y in y0..y1 {
                for x in x0..x1 {
                    let v = u32::from(image.pixel(x, y));
                    sum += v;
                    count += 1;
                    min = min.min(v);
                    max = max.max(v);
                }
            }

            let point = if count == 0 {
                128
            } else if max - min > MIN_DYNAMIC_RANGE {
                sum / count
            } else {
                // Uniform block. Half its own luminance keeps solid paper
                // light, but that would also read solid ink as light, so
                // prefer what the already-computed neighbours decided —
                // unless this block is darker than all of them, in which
                // case it really is the light one.
                let mut point = min / 2;
                if bx > 0 && by > 0 {
                    let idx = |x: u32, y: u32| (y as usize) * (bw as usize) + (x as usize);
                    let neighbours = (points[idx(bx, by - 1)]
                        + 2 * points[idx(bx - 1, by)]
                        + points[idx(bx - 1, by - 1)])
                        / 4;
                    if min < neighbours {
                        point = neighbours;
                    }
                }
                point
            };

            points[(by as usize) * (bw as usize) + (bx as usize)] = point;
        }
    }

    points
}

/// Average the black points over the neighbourhood around block `(bx, by)`.
fn smoothed(points: &[u32], bw: u32, bh: u32, bx: u32, by: u32) -> u32 {
    let x0 = bx.saturating_sub(SMOOTH_RADIUS);
    let y0 = by.saturating_sub(SMOOTH_RADIUS);
    let x1 = (bx + SMOOTH_RADIUS + 1).min(bw);
    let y1 = (by + SMOOTH_RADIUS + 1).min(bh);

    let mut sum = 0u32;
    let mut count = 0u32;
    for y in y0..y1 {
        for x in x0..x1 {
            sum += points[(y as usize) * (bw as usize) + (x as usize)];
            count += 1;
        }
    }

    // `bx`/`by` are always inside the grid, so the window is never empty.
    sum / count.max(1)
}

#[cfg(test)]
mod tests {
    use super::*;
    use alloc::vec::Vec;

    /// Build a grey image from a row pattern repeated down the image.
    fn image_from_rows(rows: &[&[u8]]) -> GrayImage {
        let w = rows[0].len() as u32;
        let h = rows.len() as u32;
        let luma: Vec<u8> = rows.iter().flat_map(|r| r.iter().copied()).collect();
        GrayImage::from_luma(w, h, luma).unwrap()
    }

    #[test]
    fn separates_ink_from_paper() {
        let row: Vec<u8> = (0..64)
            .map(|i| if (i / 4) % 2 == 0 { 20 } else { 235 })
            .collect();
        let rows: Vec<&[u8]> = (0..16).map(|_| &row[..]).collect();
        let matrix = binarize(&image_from_rows(&rows));

        for x in 0..64u32 {
            let expect_dark = (x / 4) % 2 == 0;
            assert_eq!(matrix.get(x, 8), expect_dark, "pixel {x}");
        }
    }

    #[test]
    fn follows_a_lighting_gradient() {
        // The same bars, but lit so that the darkest paper on the right is
        // darker than the lightest ink on the left. No single global
        // threshold can separate this; a local one can.
        let mut luma = Vec::new();
        for _ in 0..32 {
            for x in 0..64u32 {
                let shade = 160 - (x as i32) * 2; // 160 down to 34
                let ink = (x / 4) % 2 == 0;
                let v = if ink { shade - 30 } else { shade + 30 };
                luma.push(v.clamp(0, 255) as u8);
            }
        }
        let matrix = binarize(&GrayImage::from_luma(64, 32, luma).unwrap());

        for x in 0..64u32 {
            let expect_dark = (x / 4) % 2 == 0;
            assert_eq!(matrix.get(x, 16), expect_dark, "pixel {x}");
        }
    }

    #[test]
    fn a_blank_image_is_all_light() {
        let matrix = binarize(&GrayImage::from_luma(32, 32, vec![255; 32 * 32]).unwrap());
        for y in 0..32 {
            for x in 0..32 {
                assert!(!matrix.get(x, y), "({x}, {y}) should be light");
            }
        }
    }

    #[test]
    fn handles_an_image_smaller_than_one_block() {
        // One block wide and high, so the neighbourhood window degenerates.
        let matrix = binarize(&GrayImage::from_luma(3, 2, vec![0, 255, 0, 0, 255, 0]).unwrap());
        assert_eq!(matrix.width(), 3);
        assert_eq!(matrix.height(), 2);
    }
}