Skip to main content

fprint_mindtct/
binarize.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Directional binarization of the padded image (`binarize_V2`) into a black-ridge/white-valley
6//! bitmap, driven by the direction map and the rotated dir-bin grids.
7//!
8//! Faithful port of the stock NBIS `_V2` binarization path — `binarize_V2` (binar.c L152),
9//! `binarize_image_V2` (binar.c L287), `dirbinarize` (binar.c L359) — plus the hole-filling
10//! morphology `fill_holes` (imgutil.c L246). The V2 path deliberately drops the V1 *isotropic*
11//! binarization: a block is either directionally binarized (valid direction) or forced WHITE
12//! (`INVALID_DIR`); there is no `isobinarize` branch.
13//!
14//! Output convention (the pre-`gray2bin` `bdata`): `0` = ridge (BLACK), `255` = valley (WHITE),
15//! full resolution at the *original* image size — the dir-bin grid pad is stripped exactly as
16//! `binarize_image_V2` computes `bw = pw - 2*pad`, `bh = ph - 2*pad`.
17//!
18//! ## Bit-exactness
19//!
20//! [`dirbinarize`]'s center-row index is `cy = sround(trunc_dbl_precision((grid_h-1)/2, 1/16384))`,
21//! matching stock verbatim (the `1/16384` truncation keeps the double→int rounding architecture-
22//! stable). All pixel accumulation is integer (`i32`) over 6-bit pixels, and the BLACK/WHITE
23//! decision is the integer comparison `csum * grid_h < gsum`. The scan orders — pixel raster,
24//! grid row/column walk, and the horizontal-then-vertical hole fill with its "skip the pixel we
25//! just proved isn't a hole" 2-step — are reproduced exactly.
26
27use crate::consts::TRUNC_SCALE;
28use crate::init::RotGrids;
29use crate::num::{sround, trunc_dbl_precision};
30use crate::params::LfsParms;
31
32/// `WHITE_PIXEL` (`lfs.h` L303) — valley intensity in the pre-`gray2bin` binary image.
33const WHITE_PIXEL: u8 = 255;
34/// `BLACK_PIXEL` (`lfs.h` L304) — ridge intensity in the pre-`gray2bin` binary image.
35const BLACK_PIXEL: u8 = 0;
36/// `INVALID_DIR` (`lfs.h` L320) — a block with no assigned ridge-flow direction.
37const INVALID_DIR: i32 = -1;
38
39/// The binarized image plus its (unpadded) dimensions — the structured analogue of stock
40/// `binarize_V2`'s `odata`/`ow`/`oh` out-parameters.
41///
42/// `data` is `width * height` bytes in row-major order, `0` = ridge and `255` = valley (the
43/// pre-`gray2bin` form). `width`/`height` equal the *original* image size, the dir-bin grid pad
44/// having been stripped.
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub(crate) struct BinaryImage {
47    /// Binary pixels, row-major, `0` = ridge (BLACK) / `255` = valley (WHITE).
48    pub(crate) data: Vec<u8>,
49    /// Width (in pixels) of the binary image (= original image width).
50    pub(crate) width: i32,
51    /// Height (in pixels) of the binary image (= original image height).
52    pub(crate) height: i32,
53}
54
55/// `binarize_V2` — binarize the padded image from its Direction Map, then fill 1-pixel holes.
56///
57/// Stock `binarize_V2` (binar.c L152). Runs [`binarize_image_V2`] to produce the raw directional
58/// bitmap, then scans it filling length-1 holes `lfsparms.num_fill_holes` times (the shipping `_V2`
59/// value is `3`). Returns the unpadded [`BinaryImage`].
60///
61// PORT: stock's `mh` (map height) parameter is intentionally omitted — `binarize_image_V2` never
62// reads it (only `mw` indexes the row-major Direction Map), the same way `init_rotgrids` drops
63// stock's unused `ih`. `blocksize` and `num_fill_holes` are taken from `lfsparms`.
64pub(crate) fn binarize_v2(
65    pdata: &[u8],
66    pw: i32,
67    ph: i32,
68    direction_map: &[i32],
69    mw: i32,
70    dirbingrids: &RotGrids,
71    lfsparms: &LfsParms,
72) -> BinaryImage {
73    // 1. Binarize the padded input image using directional block info.
74    let mut bin = binarize_image_v2(
75        pdata,
76        pw,
77        ph,
78        direction_map,
79        mw,
80        lfsparms.blocksize,
81        dirbingrids,
82    );
83
84    // 2. Fill black and white holes in the binary image. LFS scans the image, filling holes,
85    //    `num_fill_holes` times.
86    for _ in 0..lfsparms.num_fill_holes {
87        fill_holes(&mut bin.data, bin.width, bin.height);
88    }
89
90    bin
91}
92
93/// `binarize_image_V2` — directionally binarize every pixel of the padded image.
94///
95/// Stock `binarize_image_V2` (binar.c L287). Walks the *unpadded* pixel grid in raster order; for
96/// each pixel it finds the block it belongs to (`bx = ix/blocksize`, `by = iy/blocksize`), reads
97/// the Direction Map, and either forces WHITE (block direction is `INVALID_DIR`) or
98/// [`dirbinarize`]s the pixel against that direction's rotated grid. Note there is **no** isotropic
99/// binarization branch in V2. The input pointer starts at the padded image's interior origin
100/// (`pad*pw + pad`) so the rotated grids never read outside the allocation.
101fn binarize_image_v2(
102    pdata: &[u8],
103    pw: i32,
104    ph: i32,
105    direction_map: &[i32],
106    mw: i32,
107    blocksize: i32,
108    dirbingrids: &RotGrids,
109) -> BinaryImage {
110    let pad = dirbingrids.pad;
111    // Dimensions of the "unpadded" binary image results.
112    let bw = pw - (pad << 1);
113    let bh = ph - (pad << 1);
114
115    let mut bdata = vec![0u8; (bw * bh).max(0) as usize];
116
117    let mut bi = 0usize;
118    for iy in 0..bh {
119        // Index of the first interior pixel on this row of the padded image: (pad+iy)*pw + pad.
120        // This is stock's `spptr` (start) advanced by `iy*pw`, with `pptr = spptr + ix`.
121        let row_base = (pad + iy) * pw + pad;
122        // Block row for this pixel row.
123        let by = iy / blocksize;
124        for ix in 0..bw {
125            // Compute which block the current pixel is in.
126            let bx = ix / blocksize;
127            // Get the corresponding value in the Direction Map.
128            let mapval = direction_map[(by * mw + bx) as usize];
129            let pptr = (row_base + ix) as usize;
130            bdata[bi] = if mapval == INVALID_DIR {
131                // If the current block has an INVALID direction, set the pixel WHITE.
132                WHITE_PIXEL
133            } else {
134                // Otherwise the block has a valid direction: use directional binarization.
135                dirbinarize(pdata, pptr, mapval, dirbingrids)
136            };
137            bi += 1;
138        }
139    }
140
141    BinaryImage {
142        data: bdata,
143        width: bw,
144        height: bh,
145    }
146}
147
148/// `dirbinarize` — binarize one grayscale pixel against a VALID ridge-flow direction.
149///
150/// Stock `dirbinarize` (binar.c L359). Samples the `grid_w * grid_h` rotated grid for direction
151/// `idir` centered on the pixel at `pptr` (a flat index into `pdata`; the grid offsets are signed
152/// and already scaled by the padded width). It sums every grid pixel (`gsum`) and, separately, the
153/// center row's sum (`csum`, the row at `cy = sround(trunc_dbl_precision((grid_h-1)/2, 1/16384))`).
154/// If the center row treated as an average is darker than the whole grid — `csum * grid_h < gsum`
155/// — the pixel is on a ridge and returns [`BLACK_PIXEL`], else [`WHITE_PIXEL`].
156///
157/// # Panics
158/// If a grid offset lands outside `pdata`; the caller must pad the image to the grid's radius (the
159/// pipeline pads by `get_max_padding_V2`, which covers the dir-bin grid).
160fn dirbinarize(pdata: &[u8], pptr: usize, idir: i32, dirbingrids: &RotGrids) -> u8 {
161    // Nickname the rotated grid for this direction.
162    let grid = &dirbingrids.grids[idir as usize];
163    let grid_w = dirbingrids.grid_w;
164    let grid_h = dirbingrids.grid_h;
165
166    // Center (0-oriented) row in the grid. Truncate precision so the double→int rounding is
167    // consistent across architectures, exactly as stock does.
168    let dcy = f64::from(grid_h - 1) / 2.0;
169    let dcy = trunc_dbl_precision(dcy, TRUNC_SCALE);
170    let cy = sround(dcy);
171
172    let mut gi = 0usize;
173    let mut gsum: i32 = 0;
174    let mut csum: i32 = 0;
175
176    // Foreach row in the grid ...
177    for gy in 0..grid_h {
178        // Sum this rotated row.
179        let mut rsum: i32 = 0;
180        for _gx in 0..grid_w {
181            // Accumulate the next pixel along the rotated row in the grid.
182            let idx = (pptr as isize + grid[gi] as isize) as usize;
183            rsum += i32::from(pdata[idx]);
184            gi += 1;
185        }
186        // Accumulate the row sum into the grid pixel sum.
187        gsum += rsum;
188        // If the current row is the center row, save its sum separately.
189        if gy == cy {
190            csum = rsum;
191        }
192    }
193
194    // If the center row sum, treated as an average, is less than the grid's total pixel sum, the
195    // pixel is on a ridge -> BLACK; otherwise it is a valley -> WHITE.
196    if csum * grid_h < gsum {
197        BLACK_PIXEL
198    } else {
199        WHITE_PIXEL
200    }
201}
202
203/// `fill_holes` — fill 1-pixel-wide holes in the binary image, horizontally then vertically.
204///
205/// Stock `fill_holes` (imgutil.c L246). A "hole" is a pixel whose two opposing neighbors are equal
206/// to each other but different from it; it is overwritten with the neighbors' value. The horizontal
207/// pass scans each row (skipping the far-left/right columns), the vertical pass each column
208/// (skipping the top/bottom rows). Both passes, on filling a hole, **advance an extra step** past
209/// the just-proven-non-hole neighbor — reproduced here by the `+2` index jump and matching loop
210/// counter bump, because it changes which later pixels are examined and is therefore load-bearing.
211/// Operates in place on `bdata` (`iw * ih`, row-major).
212fn fill_holes(bdata: &mut [u8], iw: i32, ih: i32) {
213    let iw = iw.max(0) as usize;
214    let ih = ih.max(0) as usize;
215
216    // 1. Fill 1-pixel-wide holes in horizontal runs first ...
217    // The row anchor `sptr` (stock `bdata + 1` advanced by `iy*iw`) starts the middle pixel one
218    // column into each row.
219    for iy in 0..ih {
220        let sptr = 1 + iy * iw; // bdata + 1 + iy*iw
221                                // Left / middle / right pixel indices at the start of this row.
222        let mut lptr = sptr - 1;
223        let mut mptr = sptr;
224        let mut rptr = sptr + 1;
225        // Foreach column in the image (less the far left and right pixels) ...
226        let mut ix = 1usize;
227        while ix < iw.saturating_sub(1) {
228            // Do we have a horizontal hole of length 1?
229            if bdata[lptr] != bdata[mptr] && bdata[lptr] == bdata[rptr] {
230                // Fill it.
231                bdata[mptr] = bdata[lptr];
232                // Bump past the right pixel: we know it will not be a hole. (The extra `ix += 1`
233                // here plus the loop's own step is the stock `ix++` inside the fill branch.)
234                lptr += 2;
235                mptr += 2;
236                rptr += 2;
237                ix += 2;
238            } else {
239                // Otherwise, bump to the next pixel to the right.
240                lptr += 1;
241                mptr += 1;
242                rptr += 1;
243                ix += 1;
244            }
245        }
246    }
247
248    // 2. Now, fill 1-pixel-wide holes in vertical runs ...
249    let iw2 = iw << 1;
250    // The column anchor `sptr` (stock `bdata + iw` advanced by `ix`) starts one row down from the
251    // top of each column.
252    for ix in 0..iw {
253        let sptr = iw + ix; // bdata + iw + ix
254                            // Top / middle / bottom pixel indices at the start of this column.
255        let mut tptr = sptr - iw;
256        let mut mptr = sptr;
257        let mut bptr = sptr + iw;
258        // Foreach row in the image (less the top and bottom row) ...
259        let mut iy = 1usize;
260        while iy < ih.saturating_sub(1) {
261            // Do we have a vertical hole of length 1?
262            if bdata[tptr] != bdata[mptr] && bdata[tptr] == bdata[bptr] {
263                // Fill it.
264                bdata[mptr] = bdata[tptr];
265                // Bump past the bottom pixel: we know it will not be a hole.
266                tptr += iw2;
267                mptr += iw2;
268                bptr += iw2;
269                iy += 2;
270            } else {
271                // Otherwise, bump to the next pixel below.
272                tptr += iw;
273                mptr += iw;
274                bptr += iw;
275                iy += 1;
276            }
277        }
278    }
279}
280
281#[cfg(test)]
282mod tests {
283    use super::*;
284    use crate::init::Relative2;
285
286    /// Build a hand-made [`RotGrids`] whose single direction `0` samples a `grid_w * grid_h`
287    /// axis-aligned neighborhood centered on the pixel, on an image of padded width `pw`. Offsets
288    /// are `(ix-cx) + (iy-cy)*pw` — the identity (unrotated) grid — so [`dirbinarize`]'s sums are
289    /// easy to reason about directly.
290    fn axis_grid(grid_w: i32, grid_h: i32, pw: i32, pad: i32) -> RotGrids {
291        let cx = (grid_w - 1) / 2;
292        let cy = (grid_h - 1) / 2;
293        let mut grid = Vec::new();
294        for iy in 0..grid_h {
295            for ix in 0..grid_w {
296                grid.push((ix - cx) + (iy - cy) * pw);
297            }
298        }
299        RotGrids {
300            pad,
301            relative2: Relative2::Center,
302            start_angle: 0.0,
303            ngrids: 1,
304            grid_w,
305            grid_h,
306            grids: vec![grid],
307        }
308    }
309
310    // --- dirbinarize: the center-row-vs-whole-grid decision -----------------------------------
311    #[test]
312    fn dirbinarize_center_darker_is_black() {
313        // 3x3 axis grid on a 5-wide image. cy = sround((3-1)/2) = 1 (the middle row).
314        let pw = 5;
315        let grids = axis_grid(3, 3, pw, 1);
316        // Rows 0 and 2 bright (10), row 1 (center) dark (0). For the pixel at index `p`, the grid
317        // reads the 3x3 block around it. Put a dark horizontal band on the center row.
318        // gsum = 6*10 + 3*0 = 60; csum = 0; csum*3 = 0 < 60 -> BLACK.
319        let mut img = vec![10u8; pw as usize * 3];
320        for x in 0..pw as usize {
321            img[pw as usize + x] = 0; // middle row
322        }
323        let p = pw as usize + 2; // center pixel, row 1 col 2
324        assert_eq!(dirbinarize(&img, p, 0, &grids), BLACK_PIXEL);
325    }
326
327    #[test]
328    fn dirbinarize_uniform_is_white() {
329        // Uniform grid: csum*grid_h == gsum, so the strict `<` is false -> WHITE.
330        let pw = 5;
331        let grids = axis_grid(3, 3, pw, 1);
332        let img = vec![7u8; pw as usize * 3];
333        let p = pw as usize + 2;
334        assert_eq!(dirbinarize(&img, p, 0, &grids), WHITE_PIXEL);
335    }
336
337    #[test]
338    fn dirbinarize_center_brighter_is_white() {
339        // Center row bright, others dark: csum large -> csum*3 >= gsum -> WHITE.
340        let pw = 5;
341        let grids = axis_grid(3, 3, pw, 1);
342        let mut img = vec![0u8; pw as usize * 3];
343        for x in 0..pw as usize {
344            img[pw as usize + x] = 10; // middle row bright
345        }
346        // gsum = 3*10 = 30; csum = 30; csum*3 = 90 >= 30 -> WHITE.
347        let p = pw as usize + 2;
348        assert_eq!(dirbinarize(&img, p, 0, &grids), WHITE_PIXEL);
349    }
350
351    #[test]
352    fn dirbinarize_center_row_index_uses_sround_truncation() {
353        // grid_h = 9 -> cy = sround(trunc((9-1)/2)) = 4. Make only row 4 dark to prove csum tracks
354        // exactly that row. gsum = 8*grid_w*5 + 0; csum = 0 -> BLACK. If cy were wrong, csum != 0.
355        let grid_w = 3;
356        let grid_h = 9;
357        let pw = 7;
358        let grids = axis_grid(grid_w, grid_h, pw, 4);
359        let rows = grid_h as usize;
360        let mut img = vec![5u8; pw as usize * rows];
361        for x in 0..pw as usize {
362            img[4 * pw as usize + x] = 0; // row index 4 == cy
363        }
364        let p = 4 * pw as usize + 3; // center of the grid (col cx=1 -> but any interior col works)
365        assert_eq!(dirbinarize(&img, p, 0, &grids), BLACK_PIXEL);
366    }
367
368    // --- binarize_image_V2: INVALID_DIR block forced WHITE, valid block binarized --------------
369    #[test]
370    fn binarize_image_invalid_block_is_white() {
371        // 1x1 block map == INVALID_DIR. Every output pixel must be WHITE regardless of image.
372        // Use pad 1, blocksize huge so all pixels map to block (0,0).
373        let pad = 1;
374        let pw = 4;
375        let ph = 4;
376        let grids = axis_grid(3, 3, pw, pad);
377        let pdata = vec![0u8; (pw * ph) as usize]; // all dark -> would be BLACK if binarized
378        let dm = vec![INVALID_DIR];
379        let bin = binarize_image_v2(&pdata, pw, ph, &dm, 1, 64, &grids);
380        assert_eq!(bin.width, pw - 2 * pad);
381        assert_eq!(bin.height, ph - 2 * pad);
382        assert!(bin.data.iter().all(|&b| b == WHITE_PIXEL));
383    }
384
385    #[test]
386    fn binarize_image_valid_block_binarizes() {
387        // A valid direction (0) with a dark center band yields at least some BLACK pixels.
388        let pad = 1;
389        let pw = 6;
390        let ph = 6;
391        let grids = axis_grid(3, 3, pw, pad);
392        // Dark horizontal band across the middle padded rows -> interior center pixels see a darker
393        // center row than surroundings.
394        let mut pdata = vec![20u8; (pw * ph) as usize];
395        for x in 0..pw as usize {
396            pdata[(ph as usize / 2) * pw as usize + x] = 0;
397        }
398        let dm = vec![0]; // one block, valid direction 0
399        let bin = binarize_image_v2(&pdata, pw, ph, &dm, 1, 64, &grids);
400        assert_eq!((bin.width, bin.height), (pw - 2 * pad, ph - 2 * pad));
401        assert!(bin.data.contains(&BLACK_PIXEL));
402    }
403
404    // --- fill_holes: horizontal then vertical --------------------------------------------------
405    #[test]
406    fn fill_holes_fills_horizontal_hole() {
407        // Row: 0 255 0  -> the middle is a length-1 hole (neighbors equal, center differs) -> 0.
408        let mut img = vec![0u8, 255, 0];
409        fill_holes(&mut img, 3, 1);
410        assert_eq!(img, vec![0, 0, 0]);
411    }
412
413    #[test]
414    fn fill_holes_fills_vertical_hole() {
415        // Column of 3 (width 1): 0 / 255 / 0 -> middle filled to 0.
416        let mut img = vec![0u8, 255, 0];
417        fill_holes(&mut img, 1, 3);
418        assert_eq!(img, vec![0, 0, 0]);
419    }
420
421    #[test]
422    fn fill_holes_leaves_non_hole_untouched() {
423        // 0 255 255: left != middle but left != right -> not a hole; unchanged.
424        let mut img = vec![0u8, 255, 255];
425        fill_holes(&mut img, 3, 1);
426        assert_eq!(img, vec![0, 255, 255]);
427    }
428
429    #[test]
430    fn fill_holes_skips_pixel_after_a_fill() {
431        // 0 255 0 255 0 across one row. At ix=1 we fill (->0) and STEP PAST ix=2, so the pixel at
432        // ix=2 is never re-examined as a middle. Stock semantics: after filling index 1 (using
433        // neighbors 0 and 2), pointers jump to ix=3. Index 2 stays 0 (already equal to its left).
434        // Trace: start 0 255 0 255 0.
435        //  ix=1: L=0,M=255,R=0 -> hole, fill M=0 -> 0 0 0 255 0; jump to ix=3.
436        //  ix=3: L(idx2)=0,M(idx3)=255,R(idx4)=0 -> hole, fill -> 0 0 0 0 0.
437        let mut img = vec![0u8, 255, 0, 255, 0];
438        fill_holes(&mut img, 5, 1);
439        assert_eq!(img, vec![0, 0, 0, 0, 0]);
440    }
441
442    #[test]
443    fn fill_holes_noop_on_thin_image() {
444        // Width < 3 and height < 3: no interior pixels, nothing changes and nothing panics.
445        let mut img = vec![0u8, 255];
446        fill_holes(&mut img, 2, 1);
447        assert_eq!(img, vec![0, 255]);
448    }
449}