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}