smart_package_tracker/scan/

mod.rs

//! Reading barcodes back out of images.
//!
//! The mirror of [`render`](crate::render), meeting the rest of the crate at
//! the same seam:
//!
//! ```text
//! image ──▶ GrayImage ──▶ binarize ──▶ BitMatrix ──▶ Decoder::decode ──▶ payload
//! ```
//!
//! A [`Scanner`] locates the symbol and turns pixels back into modules; a
//! [`Decoder`] turns modules back into a payload. Neither half knows what the
//! other is doing, so adding a scannable symbology means implementing
//! [`Decoder`] and describing the symbology's character structure in
//! [`SymbologyKind::linear_character`], not touching this module.
//!
//! # Example
//!
//! ```
//! # #[cfg(all(feature = "scan", feature = "png"))]
//! # fn main() -> Result<(), smart_package_tracker::Error> {
//! use smart_package_tracker::{Barcode, RenderOptions, scan};
//!
//! let png = Barcode::code128("PKG-9ED9285C")?.to_png(&RenderOptions::default())?;
//!
//! let found = scan::scan_png(&png)?;
//! assert_eq!(found.payload(), "PKG-9ED9285C");
//! # Ok(())
//! # }
//! # #[cfg(not(all(feature = "scan", feature = "png")))]
//! # fn main() {}
//! ```
//!
//! # What this handles, and what it does not
//!
//! Reading a barcode off a photograph of a parcel and reading one out of a
//! rendered label, a flatbed scan or a screenshot are different problems. This
//! solves the second.
//!
//! Handled: any module width; extra margin or a crop flush to the bars; the
//! symbol anywhere in a larger image; light-on-dark as well as dark-on-light;
//! uneven lighting across the image; moderate noise and blur; a label turned
//! on its side, since columns are scanned as well as rows; and a printed width
//! that drifts from nominal, because each character is measured against its
//! own width rather than against one estimate for the whole symbol.
//!
//! Not handled: rotation by anything other than a quarter turn, perspective,
//! and the curvature of a barcode wrapped around a parcel. Those want a
//! dedicated scanning engine, not a label-generation crate — reach for one of
//! those if you are decoding camera frames.
//!
//! Only linear symbologies can be read. There is no QR decoder here; QR
//! encodes but does not scan.

mod binarize;
mod linear;

use alloc::string::String;
use alloc::vec::Vec;

use crate::error::{Error, Result};
use crate::symbology::{BitMatrix, Decoder, LinearCharacter, SymbologyKind};

/// Default number of scan lines tried along each axis.
///
/// The lines are spread over the image and tried from the middle outwards, so
/// this is a cost ceiling rather than a resolution: a barcode occupying any
/// reasonable fraction of the image is crossed by several of them.
const DEFAULT_SCAN_LINES: u32 = 32;

/// An 8-bit greyscale image: what a scanner actually works on.
///
/// Colour carries no information a barcode reader wants, so every input is
/// reduced to luminance on the way in. Transparent pixels are composited over
/// white first, because a barcode rendered with
/// [`Color::TRANSPARENT`](crate::Color::TRANSPARENT) as its background is
/// black ink on nothing, and "nothing" prints as paper.
#[derive(Clone, PartialEq, Eq)]
pub struct GrayImage {
    width: u32,
    height: u32,
    luma: Vec<u8>,
}

impl GrayImage {
    /// Wrap an existing 8-bit luminance buffer, one byte per pixel.
    ///
    /// # Errors
    ///
    /// Returns [`Error::InvalidImage`] if either dimension is zero, if the
    /// buffer length is not exactly `width * height`, or if the image is
    /// larger than the crate's pixel-count limit.
    pub fn from_luma(width: u32, height: u32, luma: Vec<u8>) -> Result<Self> {
        let expected = check_dimensions(width, height, 1)?;
        if luma.len() != expected {
            return Err(Error::InvalidImage(alloc::format!(
                "expected {expected} bytes for a {width}x{height} greyscale image, got {}",
                luma.len()
            )));
        }
        Ok(Self {
            width,
            height,
            luma,
        })
    }

    /// Convert a packed 8-bit RGB buffer, three bytes per pixel.
    ///
    /// # Errors
    ///
    /// As [`from_luma`](Self::from_luma), for a buffer of `width * height * 3`.
    pub fn from_rgb8(width: u32, height: u32, rgb: &[u8]) -> Result<Self> {
        let expected = check_dimensions(width, height, 3)?;
        if rgb.len() != expected {
            return Err(Error::InvalidImage(alloc::format!(
                "expected {expected} bytes for a {width}x{height} RGB image, got {}",
                rgb.len()
            )));
        }
        let luma = rgb
            .chunks_exact(3)
            .map(|p| luminance(p[0], p[1], p[2]))
            .collect();
        Self::from_luma(width, height, luma)
    }

    /// Convert a packed 8-bit RGBA buffer, four bytes per pixel, compositing
    /// over a white background.
    ///
    /// # Errors
    ///
    /// As [`from_luma`](Self::from_luma), for a buffer of `width * height * 4`.
    pub fn from_rgba8(width: u32, height: u32, rgba: &[u8]) -> Result<Self> {
        let expected = check_dimensions(width, height, 4)?;
        if rgba.len() != expected {
            return Err(Error::InvalidImage(alloc::format!(
                "expected {expected} bytes for a {width}x{height} RGBA image, got {}",
                rgba.len()
            )));
        }
        let luma = rgba
            .chunks_exact(4)
            .map(|p| {
                let [r, g, b] = [p[0], p[1], p[2]].map(|c| over_white(c, p[3]));
                luminance(r, g, b)
            })
            .collect();
        Self::from_luma(width, height, luma)
    }

    /// Decode a PNG image.
    ///
    /// Handles every colour type and bit depth the `png` crate can normalise
    /// to 8 bits, including palettes and greyscale.
    ///
    /// # Errors
    ///
    /// Returns [`Error::InvalidImage`] if the bytes are not a PNG this crate
    /// can read, or if the image exceeds the pixel-count limit.
    #[cfg(feature = "png")]
    #[cfg_attr(docsrs, doc(cfg(feature = "png")))]
    pub fn from_png(bytes: &[u8]) -> Result<Self> {
        let mut decoder = ::png::Decoder::new(std::io::Cursor::new(bytes));
        decoder.set_transformations(::png::Transformations::normalize_to_color8());

        let mut reader = decoder
            .read_info()
            .map_err(|e| Error::InvalidImage(alloc::format!("{e}")))?;

        // Check the declared size before allocating for it, so a hostile
        // header cannot ask for a multi-gigabyte buffer.
        let info = reader.info();
        check_dimensions(info.width, info.height, 4)?;

        let size = reader
            .output_buffer_size()
            .ok_or_else(|| Error::InvalidImage(String::from("image is too large to decode")))?;
        let mut buf = alloc::vec![0u8; size];
        let frame = reader
            .next_frame(&mut buf)
            .map_err(|e| Error::InvalidImage(alloc::format!("{e}")))?;
        let pixels = &buf[..frame.buffer_size()];
        let (width, height) = (frame.width, frame.height);

        match frame.color_type {
            ::png::ColorType::Grayscale => Self::from_luma(width, height, pixels.to_vec()),
            ::png::ColorType::GrayscaleAlpha => {
                let luma = pixels
                    .chunks_exact(2)
                    .map(|p| over_white(p[0], p[1]))
                    .collect();
                Self::from_luma(width, height, luma)
            }
            ::png::ColorType::Rgb => Self::from_rgb8(width, height, pixels),
            ::png::ColorType::Rgba => Self::from_rgba8(width, height, pixels),
            other => Err(Error::InvalidImage(alloc::format!(
                "unsupported PNG colour type {other:?}"
            ))),
        }
    }

    /// Read a PNG file from disk.
    ///
    /// # Errors
    ///
    /// Returns [`Error::Io`] if the file cannot be read, or whatever
    /// [`from_png`](Self::from_png) reports.
    #[cfg(all(feature = "png", feature = "std"))]
    #[cfg_attr(docsrs, doc(cfg(all(feature = "png", feature = "std"))))]
    pub fn from_png_file(path: impl AsRef<std::path::Path>) -> Result<Self> {
        Self::from_png(&std::fs::read(path)?)
    }

    /// Width in pixels.
    pub fn width(&self) -> u32 {
        self.width
    }

    /// Height in pixels.
    pub fn height(&self) -> u32 {
        self.height
    }

    /// The luminance buffer, row-major, one byte per pixel.
    pub fn luma(&self) -> &[u8] {
        &self.luma
    }

    /// Luminance at `(x, y)`. Out-of-bounds reads as white, matching the way
    /// [`BitMatrix::get`] tolerates out-of-bounds coordinates.
    pub fn pixel(&self, x: u32, y: u32) -> u8 {
        if x >= self.width || y >= self.height {
            return u8::MAX;
        }
        self.luma[(y as usize) * (self.width as usize) + (x as usize)]
    }
}

impl core::fmt::Debug for GrayImage {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        // The buffer is megabytes; its dimensions are the useful part.
        f.debug_struct("GrayImage")
            .field("width", &self.width)
            .field("height", &self.height)
            .finish_non_exhaustive()
    }
}

/// Reject degenerate or oversized geometry, returning the buffer length a
/// well-formed image of this size has.
///
/// The limit is on the pixel *count*, not on either axis alone: two dimensions
/// that each look reasonable multiply out into an allocation that is not.
fn check_dimensions(width: u32, height: u32, channels: usize) -> Result<usize> {
    if width == 0 || height == 0 {
        return Err(Error::InvalidImage(alloc::format!(
            "image has a zero dimension ({width}x{height})"
        )));
    }
    let pixels = u64::from(width) * u64::from(height);
    if pixels > crate::render::MAX_PIXELS {
        return Err(Error::InvalidImage(alloc::format!(
            "image is {} megapixels, over the {} megapixel limit",
            pixels / 1_000_000,
            crate::render::MAX_PIXELS / 1_000_000
        )));
    }
    // The pixel-count limit bounds this well inside `usize` on 32-bit targets.
    Ok((pixels as usize) * channels)
}

/// Rec. 601 luma, the weighting a monochrome sensor approximates.
fn luminance(r: u8, g: u8, b: u8) -> u8 {
    ((77 * u32::from(r) + 150 * u32::from(g) + 29 * u32::from(b)) >> 8) as u8
}

/// Composite one channel over an opaque white background.
fn over_white(channel: u8, alpha: u8) -> u8 {
    let (c, a) = (u32::from(channel), u32::from(alpha));
    ((c * a + 255 * (255 - a) + 127) / 255) as u8
}

/// A barcode found in an image.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Scan {
    kind: SymbologyKind,
    payload: String,
}

impl Scan {
    /// The decoded payload.
    pub fn payload(&self) -> &str {
        &self.payload
    }

    /// Which symbology it was read as.
    pub fn kind(&self) -> SymbologyKind {
        self.kind
    }

    /// Take ownership of the payload.
    pub fn into_payload(self) -> String {
        self.payload
    }
}

/// Which way a scan line runs.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Axis {
    /// Left to right.
    Row,
    /// Top to bottom, for a label printed on its side.
    Column,
}

/// Reads barcodes out of images.
///
/// # Examples
///
/// ```
/// # #[cfg(all(feature = "scan", feature = "code128"))]
/// # fn main() -> Result<(), smart_package_tracker::Error> {
/// use smart_package_tracker::scan::{GrayImage, Scanner};
///
/// # let luma = {
/// #     use smart_package_tracker::symbology::{Code128, Symbology};
/// #     let symbol = Code128.encode("PKG-9ED9285C")?;
/// #     let row: Vec<u8> = core::iter::repeat_n(255u8, 30)
/// #         .chain(symbol.modules().row(0).iter().flat_map(|d| {
/// #             core::iter::repeat_n(if *d { 0u8 } else { 255 }, 3)
/// #         }))
/// #         .chain(core::iter::repeat_n(255u8, 30))
/// #         .collect();
/// #     (0..40).flat_map(|_| row.iter().copied()).collect::<Vec<u8>>()
/// # };
/// # let width = (luma.len() / 40) as u32;
/// let image = GrayImage::from_luma(width, 40, luma)?;
/// let found = Scanner::new().scan(&image)?;
///
/// assert_eq!(found.payload(), "PKG-9ED9285C");
/// # Ok(())
/// # }
/// # #[cfg(not(all(feature = "scan", feature = "code128")))]
/// # fn main() {}
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Scanner {
    max_scan_lines: u32,
}

impl Default for Scanner {
    fn default() -> Self {
        Self::new()
    }
}

impl Scanner {
    /// A scanner with default settings.
    pub fn new() -> Self {
        Self {
            max_scan_lines: DEFAULT_SCAN_LINES,
        }
    }

    /// How many scan lines to try along each axis.
    ///
    /// Raising this helps when the barcode occupies a small part of a large
    /// image; lowering it bounds the work done before giving up. Zero is
    /// treated as one.
    pub fn max_scan_lines(mut self, lines: u32) -> Self {
        self.max_scan_lines = lines.max(1);
        self
    }

    /// Read any barcode this crate can decode out of `image`.
    ///
    /// Code 128 is currently the only symbology this crate can decode, so
    /// this is a shorthand for [`scan_with`](Self::scan_with). It stays a
    /// separate method because it is where any future symbology gets tried
    /// without callers changing.
    ///
    /// # Errors
    ///
    /// Returns [`Error::NoSymbolFound`] if no scan line yields a valid symbol.
    /// A barcode that is present but unreadable is indistinguishable from one
    /// that is absent, so there is only the one error.
    pub fn scan(&self, image: &GrayImage) -> Result<Scan> {
        self.scan_with(&crate::symbology::Code128, image)
    }

    /// Read a barcode of one specific symbology out of `image`.
    ///
    /// # Errors
    ///
    /// Returns [`Error::NoSymbolFound`] if no scan line yields a valid symbol,
    /// or [`Error::Decode`] if the symbology has no scan-line structure —
    /// matrix symbologies such as QR cannot be read this way.
    pub fn scan_with<D: Decoder + ?Sized>(&self, decoder: &D, image: &GrayImage) -> Result<Scan> {
        let kind = decoder.kind();
        let character = kind.linear_character().ok_or_else(|| {
            Error::Decode(alloc::format!(
                "{kind} cannot be read from an image: it is not a linear symbology"
            ))
        })?;

        let matrix = binarize::binarize(image);

        for axis in [Axis::Row, Axis::Column] {
            if let Some(payload) = self.scan_axis(decoder, character, &matrix, axis) {
                return Ok(Scan { kind, payload });
            }
        }

        Err(Error::NoSymbolFound(alloc::format!(
            "no {kind} symbol on any of the scan lines tried across a {}x{} image",
            image.width(),
            image.height()
        )))
    }

    /// Try every scan line along one axis.
    fn scan_axis<D: Decoder + ?Sized>(
        &self,
        decoder: &D,
        character: LinearCharacter,
        matrix: &BitMatrix,
        axis: Axis,
    ) -> Option<String> {
        let count = match axis {
            Axis::Row => matrix.height(),
            Axis::Column => matrix.width(),
        };

        for index in scan_line_order(count, self.max_scan_lines) {
            // The raw line first: it is exact where the image is clean, and
            // clean is the common case. Only if that fails is it worth
            // spending a vote across neighbouring lines to beat down speckle,
            // which costs sharpness at the top and bottom of the bars.
            for radius in [0, 1] {
                if radius > 0 && count < 3 {
                    continue;
                }
                let line = scan_line(matrix, axis, index, radius);
                if let Some(payload) = linear::decode_row(decoder, character, &line) {
                    return Some(payload);
                }
                // The same symbol printed light-on-dark. Cheaper to try than
                // to guess from the border, which guesses wrong on an image
                // cropped flush to the bars.
                let inverted: Vec<bool> = line.iter().map(|d| !d).collect();
                if let Some(payload) = linear::decode_row(decoder, character, &inverted) {
                    return Some(payload);
                }
            }
        }

        None
    }
}

/// Which lines to try, in the order to try them.
///
/// Lines are spread evenly over the axis and then ordered from the middle
/// outwards: a barcode is usually the middle of its label, and any
/// human-readable text is at the edge.
fn scan_line_order(count: u32, max_lines: u32) -> Vec<u32> {
    let lines = count.min(max_lines.max(1));
    let mut order: Vec<u32> = (0..lines)
        // Sample the centre of each of `lines` equal bands rather than the
        // edges, so neither the first nor the last line lands on the border.
        .map(|i| ((2 * i + 1) as u64 * count as u64 / (2 * lines as u64)) as u32)
        .map(|i| i.min(count - 1))
        .collect();
    order.dedup();

    let centre = i64::from(count) / 2;
    order.sort_by_key(|&i| (i64::from(i) - centre).abs());
    order
}

/// Extract one scan line, optionally as a majority vote over its neighbours.
fn scan_line(matrix: &BitMatrix, axis: Axis, index: u32, radius: u32) -> Vec<bool> {
    let (length, count) = match axis {
        Axis::Row => (matrix.width(), matrix.height()),
        Axis::Column => (matrix.height(), matrix.width()),
    };

    if radius == 0 {
        return match axis {
            Axis::Row => matrix.row(index).to_vec(),
            Axis::Column => (0..length).map(|y| matrix.get(index, y)).collect(),
        };
    }

    let lo = index.saturating_sub(radius);
    let hi = (index + radius + 1).min(count);
    let voters = hi - lo;
    (0..length)
        .map(|pos| {
            let dark = (lo..hi)
                .filter(|&i| match axis {
                    Axis::Row => matrix.get(pos, i),
                    Axis::Column => matrix.get(i, pos),
                })
                .count() as u32;
            2 * dark > voters
        })
        .collect()
}

/// Read any barcode this crate can decode out of a PNG image.
///
/// # Errors
///
/// Returns [`Error::InvalidImage`] if the bytes are not a readable PNG, or
/// [`Error::NoSymbolFound`] if it holds no barcode.
#[cfg(feature = "png")]
#[cfg_attr(docsrs, doc(cfg(feature = "png")))]
pub fn scan_png(bytes: &[u8]) -> Result<Scan> {
    Scanner::new().scan(&GrayImage::from_png(bytes)?)
}

/// Read any barcode this crate can decode out of a PNG file.
///
/// # Errors
///
/// Returns [`Error::Io`] if the file cannot be read, plus whatever
/// [`scan_png`] reports.
#[cfg(all(feature = "png", feature = "std"))]
#[cfg_attr(docsrs, doc(cfg(all(feature = "png", feature = "std"))))]
pub fn scan_png_file(path: impl AsRef<std::path::Path>) -> Result<Scan> {
    scan_png(&std::fs::read(path)?)
}

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

    #[test]
    fn rejects_a_buffer_that_does_not_match_its_dimensions() {
        let err = GrayImage::from_luma(4, 4, vec![0; 15]).unwrap_err();
        assert!(matches!(err, Error::InvalidImage(_)), "got {err:?}");
        assert!(GrayImage::from_luma(4, 4, vec![0; 16]).is_ok());
        assert!(GrayImage::from_rgb8(2, 2, &[0; 11]).is_err());
        assert!(GrayImage::from_rgb8(2, 2, &[0; 12]).is_ok());
        assert!(GrayImage::from_rgba8(2, 2, &[0; 15]).is_err());
        assert!(GrayImage::from_rgba8(2, 2, &[0; 16]).is_ok());
    }

    #[test]
    fn rejects_a_zero_dimension() {
        assert!(GrayImage::from_luma(0, 4, vec![]).is_err());
        assert!(GrayImage::from_luma(4, 0, vec![]).is_err());
    }

    #[test]
    fn rejects_an_image_larger_than_the_allocation_limit() {
        // Neither axis is extreme; their product is. This is the guard that
        // has to bound the allocation, not each axis on its own.
        let err = GrayImage::from_luma(20_000, 20_000, Vec::new()).unwrap_err();
        assert!(
            alloc::format!("{err}").contains("megapixel"),
            "expected a pixel-count error, got {err}"
        );
    }

    #[test]
    fn transparent_pixels_composite_over_white() {
        // Black ink on a fully transparent background is black on paper, not
        // black on black — a barcode rendered with `Color::TRANSPARENT` has to
        // stay readable.
        let rgba = [0, 0, 0, 0, 0, 0, 0, 255];
        let image = GrayImage::from_rgba8(2, 1, &rgba).unwrap();
        assert_eq!(image.pixel(0, 0), 255, "transparent should read as paper");
        assert_eq!(image.pixel(1, 0), 0, "opaque black should read as ink");
    }

    #[test]
    fn out_of_bounds_pixels_read_as_paper() {
        let image = GrayImage::from_luma(2, 2, vec![0; 4]).unwrap();
        assert_eq!(image.pixel(0, 0), 0);
        assert_eq!(image.pixel(2, 0), 255);
        assert_eq!(image.pixel(0, 2), 255);
        assert_eq!(image.pixel(u32::MAX, u32::MAX), 255);
    }

    #[test]
    fn scan_lines_start_in_the_middle_and_stay_in_range() {
        let order = scan_line_order(100, 8);
        assert_eq!(order.len(), 8);
        assert!(order.iter().all(|&i| i < 100));
        // The first line tried should be near the vertical centre.
        assert!((40..=60).contains(&order[0]), "started at {}", order[0]);
    }

    #[test]
    fn every_line_is_tried_when_there_are_fewer_than_the_cap() {
        let mut order = scan_line_order(5, 32);
        order.sort_unstable();
        assert_eq!(order, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn a_single_line_image_still_yields_one_line() {
        assert_eq!(scan_line_order(1, 32), vec![0]);
    }
}