fprint_mindtct/remove.rs
1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! False-minutia removal (`remove_false_minutia_V2`): the sequence of island/lake, hole,
6//! invalid-block, side, hook, overlap, malformation and pore filters that prune spurious candidates —
7//! faithful port of stock NBIS `mindtct/src/lib/mindtct/remove.c` (the ten-stage `_V2` driver at
8//! L172), plus the small supporting routines the stage needs from `loop.c` (`on_hook`,
9//! `on_island_lake`), `imgutil.c` (`free_path`, `search_in_direction`), `maps.c` (`num_valid_8nbrs`)
10//! and `minutia.c` (`sort_minutiae_y_x`). The `util.c` helpers it also relies on (`distance`,
11//! `squared_distance`, `closest_dir_dist`, `minmaxs`) live in the shared [`crate::util`] module.
12//!
13//! The ten stages run in the exact reference order, each walking the minutiae list in the reference's
14//! scan direction so that `remove_minutia`'s in-place slide keeps subsequent indices consistent. Some
15//! stages edit the binary image in place (island/lake filling); that is reproduced so later stages see
16//! the same pixels the reference does — only the pruned minutiae list is exposed.
17
18// `too_many_arguments`: the routines carrying a per-function `#[allow]` below are verbatim
19// transcriptions of a stock `remove.c` (or supporting `loop.c`/`imgutil.c`/`util.c`) function whose
20// interface is fixed by the reference — the binary image (`bdata`, `iw`, `ih`), one or more block
21// maps (`map`, `mw`, `mh`), coordinate pairs, and the parameter block. Bundling those into ad-hoc
22// structs would obscure the one-to-one correspondence with the C; the reference-side arity is the
23// justification, applied at each function that needs it rather than to the whole file.
24
25use crate::consts::TRUNC_SCALE;
26use crate::detect::contour::{
27 fix_edge_pixel_pair, get_centered_contour, line2direction, trace_contour, CenteredContour,
28 Contour, ScanDir, TraceResult,
29};
30use crate::detect::line::line_points;
31use crate::detect::loops::{fill_loop, on_loop, OnLoop};
32use crate::detect::{DetMinutia, BIFURCATION};
33use crate::num::{sort_indices_int_inc, sround, trunc_dbl_precision};
34use crate::params::LfsParms;
35use crate::util::{closest_dir_dist, distance, minmaxs, squared_distance};
36
37/// Stock `INVALID_DIR` (`lfs.h` L320): a block whose ridge-flow direction could not be determined.
38const INVALID_DIR: i32 = -1;
39
40// ===========================================================================
41// Supporting routines ported from maps.c / imgutil.c / loop.c
42// ===========================================================================
43
44/// Count the valid (`>= 0`) blocks among the eight neighbors of a block — port of stock
45/// `num_valid_8nbrs` (`maps.c` L2044).
46///
47/// The eight neighbors are tested in the stock order NW, N, NE, E, SE, S, SW, W, each only when its
48/// coordinates lie within the map.
49fn num_valid_8nbrs(imap: &[i32], mx: i32, my: i32, mw: i32, mh: i32) -> i32 {
50 let mut nvalid = 0;
51
52 // PORT L2054–L2057: neighbor coordinate indices.
53 let e_ind = mx + 1;
54 let w_ind = mx - 1;
55 let n_ind = my - 1;
56 let s_ind = my + 1;
57
58 // PORT L2059–L2091: eight guarded neighbor tests in stock order.
59 if w_ind >= 0 && n_ind >= 0 && imap[(n_ind * mw + w_ind) as usize] >= 0 {
60 nvalid += 1;
61 }
62 if n_ind >= 0 && imap[(n_ind * mw + mx) as usize] >= 0 {
63 nvalid += 1;
64 }
65 if n_ind >= 0 && e_ind < mw && imap[(n_ind * mw + e_ind) as usize] >= 0 {
66 nvalid += 1;
67 }
68 if e_ind < mw && imap[(my * mw + e_ind) as usize] >= 0 {
69 nvalid += 1;
70 }
71 if e_ind < mw && s_ind < mh && imap[(s_ind * mw + e_ind) as usize] >= 0 {
72 nvalid += 1;
73 }
74 if s_ind < mh && imap[(s_ind * mw + mx) as usize] >= 0 {
75 nvalid += 1;
76 }
77 if w_ind >= 0 && s_ind < mh && imap[(s_ind * mw + w_ind) as usize] >= 0 {
78 nvalid += 1;
79 }
80 if w_ind >= 0 && imap[(my * mw + w_ind) as usize] >= 0 {
81 nvalid += 1;
82 }
83
84 nvalid
85}
86
87/// Whether a "free path" exists between two pixels — port of stock `free_path` (`imgutil.c` L341).
88///
89/// Walks the straight-line trajectory ([`line_points`]) between the two points and counts pixel-value
90/// transitions; the path is free (`true`) iff no more than `lfsparms.maxtrans` transitions occur.
91fn free_path(
92 x1: i32,
93 y1: i32,
94 x2: i32,
95 y2: i32,
96 bdata: &[u8],
97 iw: i32,
98 lfsparms: &LfsParms,
99) -> bool {
100 // PORT L350: points along the segment (its capacity guard is unreachable, so `Err` → not free).
101 let list = match line_points(x1, y1, x2, y2) {
102 Ok(l) => l,
103 Err(_) => return false,
104 };
105
106 // PORT L354–L356: count transitions, seeded at the first point's value.
107 let mut trans = 0;
108 let mut preval = bdata[(y1 * iw + x1) as usize];
109
110 // PORT L359–L381: a transition past `maxtrans` means no free path.
111 for &(x, y) in list.iter().skip(1) {
112 let nextval = bdata[(y * iw + x) as usize];
113 if nextval != preval {
114 trans += 1;
115 if trans > lfsparms.maxtrans {
116 return false;
117 }
118 preval = nextval;
119 }
120 }
121
122 // PORT L388: within the transition budget → free path.
123 true
124}
125
126/// Step in a direction until a pixel of value `pix` is found — port of stock `search_in_direction`
127/// (`imgutil.c` L419).
128///
129/// Advances `maxsteps` times by `(delta_x, delta_y)` from `(strt_x, strt_y)` (rounding each step via
130/// [`sround`]); on finding a `pix` pixel, adjusts the found/previous pair to be 4-connected
131/// ([`fix_edge_pixel_pair`]) and returns `Some((x, y, ex, ey))`. Returns `None` (stock `FALSE`) if the
132/// walk leaves the image or exhausts its steps.
133#[expect(clippy::too_many_arguments)]
134fn search_in_direction(
135 pix: u8,
136 strt_x: i32,
137 strt_y: i32,
138 delta_x: f64,
139 delta_y: f64,
140 maxsteps: i32,
141 bdata: &[u8],
142 iw: i32,
143 ih: i32,
144) -> Option<(i32, i32, i32, i32)> {
145 // PORT L429–L433: previous point and floating accumulators seeded at the start.
146 let mut px = strt_x;
147 let mut py = strt_y;
148 let mut fx = f64::from(strt_x);
149 let mut fy = f64::from(strt_y);
150
151 // PORT L436: take up to `maxsteps` steps.
152 for _ in 0..maxsteps {
153 // PORT L438–L443: accumulate and round to the next pixel.
154 fx += delta_x;
155 fy += delta_y;
156 let x = sround(fx);
157 let y = sround(fy);
158
159 // PORT L445–L454: stepped off the image → not found.
160 if x < 0 || x >= iw || y < 0 || y >= ih {
161 return None;
162 }
163
164 // PORT L456–L473: found the target pixel → make the pair 4-connected and return it.
165 if bdata[(y * iw + x) as usize] == pix {
166 let (ax, ay, aex, aey) = fix_edge_pixel_pair(x, y, px, py, bdata, iw);
167 return Some((ax, ay, aex, aey));
168 }
169
170 // PORT L477–L479: advance the previous point and step again.
171 px = x;
172 py = y;
173 }
174
175 // PORT L482–L487: exhausted the steps → not found.
176 None
177}
178
179/// Order the minutiae top-to-bottom, left-to-right — port of stock `sort_minutiae_y_x`
180/// (`minutia.c` L615).
181///
182/// Sorts by the 1-D pixel offset `y * iw + x` using the port's stable index sort, so equal keys keep
183/// their input order exactly as the reference's stable sort does.
184///
185/// PORT: `ih` is taken by the reference but never read, so it is dropped here.
186fn sort_minutiae_y_x(minutiae: &mut Vec<DetMinutia>, iw: i32) {
187 // PORT L629–L637: 1-D pixel offsets, then their sorted permutation.
188 let mut ranks: Vec<i32> = minutiae.iter().map(|m| (m.y * iw) + m.x).collect();
189 let order = sort_indices_int_inc(&mut ranks);
190
191 // PORT L648–L655: rebuild the list in sorted order.
192 let newlist: Vec<DetMinutia> = order
193 .into_iter()
194 .map(|o| minutiae[o as usize].clone())
195 .collect();
196 *minutiae = newlist;
197}
198
199/// Outcome of [`on_hook`] — the stock `int` return (`HOOK_FOUND`/`FALSE`/`IGNORE`).
200#[derive(Clone, Copy, PartialEq, Eq)]
201enum OnHook {
202 /// The two minutiae lie on a common qualifying hook (stock `HOOK_FOUND`).
203 HookFound,
204 /// They do not (stock `FALSE`).
205 NotFound,
206 /// The contour could not be traced (stock `IGNORE`).
207 Ignore,
208}
209
210/// Whether two opposite-type minutiae lie on a common hook — port of stock `on_hook` (`loop.c`
211/// L398).
212///
213/// Traces the feature contour from minutia 1's *edge* pixel toward minutia 2, first clockwise then (if
214/// that misses) counter-clockwise, each up to `max_hook_len` steps. A trace that walks onto minutia 2
215/// is a hook.
216#[expect(clippy::too_many_arguments)]
217fn on_hook(
218 m1x: i32,
219 m1y: i32,
220 m1ex: i32,
221 m1ey: i32,
222 m2x: i32,
223 m2y: i32,
224 max_hook_len: i32,
225 bdata: &[u8],
226 iw: i32,
227 ih: i32,
228) -> OnHook {
229 // PORT L413–L417: trace from minutia1's edge point clockwise, loop-trigger at minutia2.
230 match trace_contour(
231 max_hook_len,
232 m2x,
233 m2y,
234 m1ex,
235 m1ey,
236 m1x,
237 m1y,
238 ScanDir::Clockwise,
239 bdata,
240 iw,
241 ih,
242 ) {
243 TraceResult::Ignore => return OnHook::Ignore,
244 TraceResult::Loop(_) => return OnHook::HookFound,
245 TraceResult::Traced(_) => {}
246 }
247
248 // PORT L443–L447: retry counter-clockwise.
249 match trace_contour(
250 max_hook_len,
251 m2x,
252 m2y,
253 m1ex,
254 m1ey,
255 m1x,
256 m1y,
257 ScanDir::CounterClockwise,
258 bdata,
259 iw,
260 ih,
261 ) {
262 TraceResult::Ignore => OnHook::Ignore,
263 TraceResult::Loop(_) => OnHook::HookFound,
264 TraceResult::Traced(_) => OnHook::NotFound,
265 }
266}
267
268/// Outcome of [`on_island_lake`] — the stock `int` return (`LOOP_FOUND` with a combined loop contour,
269/// `FALSE`, or `IGNORE`).
270enum IslandLake {
271 /// The pair encloses a loop (stock `LOOP_FOUND`); the combined loop contour is returned.
272 Found(Contour),
273 /// The pair does not enclose a loop (stock `FALSE`).
274 NotFound,
275 /// A contour could not be traced (stock `IGNORE`).
276 Ignore,
277}
278
279/// Whether two same-type minutiae bound a common island or lake — port of stock `on_island_lake`
280/// (`loop.c` L252).
281///
282/// Traces the feature contour from minutia 1 toward minutia 2 and, if it arrives, from minutia 2 back
283/// toward minutia 1 (both clockwise, each up to `max_half_loop` steps). If both halves close, they are
284/// concatenated — minutia 1, the first half, minutia 2, the second half — into the loop's contour.
285#[expect(clippy::too_many_arguments)]
286fn on_island_lake(
287 m1x: i32,
288 m1y: i32,
289 m1ex: i32,
290 m1ey: i32,
291 m2x: i32,
292 m2y: i32,
293 m2ex: i32,
294 m2ey: i32,
295 max_half_loop: i32,
296 bdata: &[u8],
297 iw: i32,
298 ih: i32,
299) -> IslandLake {
300 // PORT L266–L270: first half, from minutia1 with loop-trigger at minutia2.
301 let c1 = match trace_contour(
302 max_half_loop,
303 m2x,
304 m2y,
305 m1x,
306 m1y,
307 m1ex,
308 m1ey,
309 ScanDir::Clockwise,
310 bdata,
311 iw,
312 ih,
313 ) {
314 // PORT L273–L274: trace impossible.
315 TraceResult::Ignore => return IslandLake::Ignore,
316 // PORT L370–L373: 1st trace did not reach minutia2 → not a loop.
317 TraceResult::Traced(_) => return IslandLake::NotFound,
318 // PORT L277: reached minutia2.
319 TraceResult::Loop(c) => c,
320 };
321
322 // PORT L283–L287: second half, from minutia2 with loop-trigger at minutia1.
323 let c2 = match trace_contour(
324 max_half_loop,
325 m1x,
326 m1y,
327 m2x,
328 m2y,
329 m2ex,
330 m2ey,
331 ScanDir::Clockwise,
332 bdata,
333 iw,
334 ih,
335 ) {
336 // PORT L290–L292: trace impossible.
337 TraceResult::Ignore => return IslandLake::Ignore,
338 // PORT L354–L359: 2nd trace did not reach minutia1 → not a loop.
339 TraceResult::Traced(_) => return IslandLake::NotFound,
340 // PORT L296: reached minutia1.
341 TraceResult::Loop(c) => c,
342 };
343
344 // PORT L299–L334: combine — minutia1, first half, minutia2, second half.
345 let nloop = c1.len() + c2.len() + 2;
346 let mut x = Vec::with_capacity(nloop);
347 let mut y = Vec::with_capacity(nloop);
348 let mut ex = Vec::with_capacity(nloop);
349 let mut ey = Vec::with_capacity(nloop);
350
351 x.push(m1x);
352 y.push(m1y);
353 ex.push(m1ex);
354 ey.push(m1ey);
355 x.extend_from_slice(&c1.x);
356 y.extend_from_slice(&c1.y);
357 ex.extend_from_slice(&c1.ex);
358 ey.extend_from_slice(&c1.ey);
359 x.push(m2x);
360 y.push(m2y);
361 ex.push(m2ex);
362 ey.push(m2ey);
363 x.extend_from_slice(&c2.x);
364 y.extend_from_slice(&c2.y);
365 ex.extend_from_slice(&c2.ex);
366 ey.extend_from_slice(&c2.ey);
367
368 // PORT L347–L348: island/lake found.
369 IslandLake::Found(Contour { x, y, ex, ey })
370}
371
372// ===========================================================================
373// The ten removal stages
374// ===========================================================================
375
376/// Remove minutia pairs bounding a lake or island, filling the enclosed loop — port of stock
377/// `remove_islands_and_lakes` (`remove.c` L851).
378fn remove_islands_and_lakes(
379 minutiae: &mut Vec<DetMinutia>,
380 bdata: &mut [u8],
381 iw: i32,
382 ih: i32,
383 lfsparms: &LfsParms,
384) {
385 let dist_thresh = lfsparms.max_rmtest_dist;
386 let half_loop = lfsparms.max_half_loop;
387
388 // PORT L871–L889: removal flags and the join-direction thresholds.
389 let mut to_remove = vec![false; minutiae.len()];
390 let full_ndirs = lfsparms.num_directions << 1;
391 let qtr_ndirs = lfsparms.num_directions >> 2;
392 let min_deltadir = (3 * qtr_ndirs) - 1;
393
394 // PORT L892: foreach primary minutia (bar the last).
395 let mut f = 0;
396 while f + 1 < minutiae.len() {
397 // PORT L896: skip a first minutia already flagged.
398 if !to_remove[f] {
399 let m1 = minutiae[f].clone();
400 // PORT L904: foreach secondary minutia to its right.
401 let mut s = f + 1;
402 while s < minutiae.len() {
403 let m2 = minutiae[s].clone();
404
405 // PORT L910: only same-type pairs are considered.
406 if m2.kind == m1.kind {
407 // PORT L923–L928: first minutia's pixel changed → next first.
408 if bdata[(m1.y * iw + m1.x) as usize] != m1.kind as u8 {
409 break;
410 }
411 // PORT L932–L934: second minutia's pixel changed → flag it.
412 if bdata[(m2.y * iw + m2.x) as usize] != m2.kind as u8 {
413 to_remove[s] = true;
414 }
415
416 // PORT L937: only proceed if the second is not flagged.
417 if !to_remove[s] {
418 // PORT L940–L942: vertical gap gate.
419 let delta_y = m2.y - m1.y;
420 if delta_y <= dist_thresh {
421 // PORT L948–L952: Euclidean distance gate.
422 let dist = distance(m1.x, m1.y, m2.x, m2.y);
423 if dist <= f64::from(dist_thresh) {
424 // PORT L958–L970: direction-difference gate.
425 let deltadir =
426 closest_dir_dist(m1.direction, m2.direction, full_ndirs);
427 if deltadir > min_deltadir {
428 // PORT L979–L982: island/lake test.
429 match on_island_lake(
430 m1.x, m1.y, m1.ex, m1.ey, m2.x, m2.y, m2.ex, m2.ey,
431 half_loop, bdata, iw, ih,
432 ) {
433 // PORT L984–L1002: fill the loop and flag both.
434 IslandLake::Found(loop_c) => {
435 // Result discarded like the stock reference: the loop is
436 // a closed contour of bounded length, so the fill cannot
437 // fail for this input.
438 let _ = fill_loop(&loop_c, bdata, iw, ih);
439 to_remove[f] = true;
440 to_remove[s] = true;
441 }
442 // PORT L1004–L1012: IGNORE → flag the first, next first.
443 IslandLake::Ignore => {
444 to_remove[f] = true;
445 break;
446 }
447 // PORT L1019–L1020: not on a loop → next second.
448 IslandLake::NotFound => {}
449 }
450 }
451 }
452 } else {
453 // PORT L1030–L1035: 2nd too far below → next first.
454 break;
455 }
456 }
457 }
458
459 // PORT L1043: next second minutia.
460 s += 1;
461 }
462 }
463 // PORT L1049: next first minutia.
464 f += 1;
465 }
466
467 // PORT L1053–L1065: remove flagged minutiae in reverse index order.
468 remove_flagged(minutiae, &to_remove);
469}
470
471/// Remove bifurcations sitting on small holes (short valley loops) — port of stock `remove_holes`
472/// (`remove.c` L261).
473fn remove_holes(
474 minutiae: &mut Vec<DetMinutia>,
475 bdata: &[u8],
476 iw: i32,
477 ih: i32,
478 lfsparms: &LfsParms,
479) {
480 // PORT L270: walk the list; a removal does not advance `i`.
481 let mut i = 0;
482 while i < minutiae.len() {
483 // PORT L276: only bifurcations.
484 if minutiae[i].kind == BIFURCATION {
485 // PORT L278: on a small loop?
486 match on_loop(&minutiae[i], lfsparms.small_loop_len, bdata, iw, ih) {
487 // PORT L280–L291: on a loop or IGNORE → remove.
488 OnLoop::LoopFound | OnLoop::Ignore => {
489 minutiae.remove(i);
490 }
491 // PORT L293–L296: not on a loop → advance.
492 OnLoop::NotFound => {
493 i += 1;
494 }
495 }
496 } else {
497 // PORT L304–L307: ridge-ending → advance.
498 i += 1;
499 }
500 }
501}
502
503/// Remove minutiae pointing (opposite their direction) at a nearby invalid block — port of stock
504/// `remove_pointing_invblock_V2` (`remove.c` L1863).
505fn remove_pointing_invblock_v2(
506 minutiae: &mut Vec<DetMinutia>,
507 direction_map: &[i32],
508 mw: i32,
509 mh: i32,
510 lfsparms: &LfsParms,
511) {
512 // PORT L1877: integer-direction → radians factor.
513 let pi_factor = std::f64::consts::PI / f64::from(lfsparms.num_directions);
514
515 // PORT L1879: walk the list; a removal does not advance `i`.
516 let mut i = 0;
517 while i < minutiae.len() {
518 let m = &minutiae[i];
519 // PORT L1885–L1894: translate opposite the minutia direction by `trans_dir_pix`.
520 let theta = f64::from(m.direction) * pi_factor;
521 let mut dx = theta.sin() * f64::from(lfsparms.trans_dir_pix);
522 let mut dy = theta.cos() * f64::from(lfsparms.trans_dir_pix);
523 dx = trunc_dbl_precision(dx, TRUNC_SCALE);
524 dy = trunc_dbl_precision(dy, TRUNC_SCALE);
525 let delta_x = sround(dx);
526 let delta_y = sround(dy);
527 let nx = m.x - delta_x;
528 let ny = m.y + delta_y;
529
530 // PORT L1898–L1907: block coords, clamped to the map.
531 let mut bx = nx / lfsparms.blocksize;
532 let mut by = ny / lfsparms.blocksize;
533 bx = bx.clamp(0, mw - 1);
534 by = by.clamp(0, mh - 1);
535
536 // PORT L1910–L1926: invalid block → remove, else advance.
537 if direction_map[(by * mw + bx) as usize] == INVALID_DIR {
538 minutiae.remove(i);
539 } else {
540 i += 1;
541 }
542 }
543}
544
545/// Remove minutiae in the margin of a nearby invalid block or the image edge — port of stock
546/// `remove_near_invblock_V2` (`remove.c` L1541).
547fn remove_near_invblock_v2(
548 minutiae: &mut Vec<DetMinutia>,
549 direction_map: &[i32],
550 mw: i32,
551 mh: i32,
552 lfsparms: &LfsParms,
553) {
554 // PORT L1591–L1610: neighbor-index LUTs (indexed by it*3+ix) and per-neighbor coord offsets.
555 const STARTBLK: [i32; 9] = [6, 0, 0, 6, -1, 2, 4, 4, 2];
556 const ENDBLK: [i32; 9] = [8, 0, 2, 6, -1, 2, 6, 4, 4];
557 const BLKDX: [i32; 9] = [0, 1, 1, 1, 0, -1, -1, -1, 0];
558 const BLKDY: [i32; 9] = [-1, -1, 0, 1, 1, 1, 0, -1, -1];
559
560 // PORT L1624–L1625: margin boundaries within a block.
561 let lo_margin = lfsparms.inv_block_margin;
562 let hi_margin = lfsparms.blocksize - lfsparms.inv_block_margin - 1;
563
564 // PORT L1627: walk the list; a removal does not advance `i`.
565 let mut i = 0;
566 while i < minutiae.len() {
567 let m = &minutiae[i];
568 // PORT L1634–L1646: block coords and pixel offset within the block.
569 let bx = m.x / lfsparms.blocksize;
570 let by = m.y / lfsparms.blocksize;
571 let px = m.x % lfsparms.blocksize;
572 let py = m.y % lfsparms.blocksize;
573
574 // PORT L1648–L1668: classify each axis offset as low margin / middle / high margin.
575 let ix = if px < lo_margin {
576 0
577 } else if px > hi_margin {
578 2
579 } else {
580 1
581 };
582 let it = if py < lo_margin {
583 0
584 } else if py > hi_margin {
585 2
586 } else {
587 1
588 };
589
590 let mut removed = false;
591
592 // PORT L1674: only act when the point is in a margin.
593 if ix != 1 || it != 1 {
594 // PORT L1677–L1679: neighbor index range for this (ix, it).
595 let sbi = STARTBLK[(it * 3 + ix) as usize];
596 let ebi = ENDBLK[(it * 3 + ix) as usize];
597
598 // PORT L1682: examine each neighbor in range.
599 let mut ni = sbi;
600 while ni <= ebi {
601 let nbx = bx + BLKDX[ni as usize];
602 let nby = by + BLKDY[ni as usize];
603
604 // PORT L1688–L1709: neighbor off the map (adjacent to the image edge) → remove.
605 if nbx < 0 || nbx >= mw || nby < 0 || nby >= mh {
606 minutiae.remove(i);
607 removed = true;
608 break;
609 }
610 // PORT L1710–L1733: invalid neighbor with too few valid neighbors → remove.
611 if direction_map[(nby * mw + nbx) as usize] == INVALID_DIR {
612 let nvalid = num_valid_8nbrs(direction_map, nbx, nby, mw, mh);
613 if nvalid < lfsparms.rm_valid_nbr_min {
614 minutiae.remove(i);
615 removed = true;
616 break;
617 }
618 }
619 ni += 1;
620 }
621 }
622
623 // PORT L1741–L1745: advance only if the point survived.
624 if !removed {
625 i += 1;
626 }
627 }
628}
629
630/// Remove or reposition minutiae sitting on the side of a ridge or valley — port of stock
631/// `remove_or_adjust_side_minutiae_V2` (`remove.c` L3180).
632///
633/// Extracts a centered contour; a point on an incomplete/looping contour is dropped. Otherwise the
634/// contour's rotated y-coords are analyzed for relative extrema: a single minimum (or a min-max-min
635/// triple) relocates the minutia onto the deepest minimum's contour point, dropping it instead if that
636/// lands in an invalid block; any other extremum pattern drops it.
637fn remove_or_adjust_side_minutiae_v2(
638 minutiae: &mut Vec<DetMinutia>,
639 bdata: &[u8],
640 iw: i32,
641 ih: i32,
642 direction_map: &[i32],
643 mw: i32,
644 lfsparms: &LfsParms,
645) {
646 // PORT L3206: integer-direction → radians factor.
647 let pi_factor = std::f64::consts::PI / f64::from(lfsparms.num_directions);
648
649 // PORT L3208: walk the list; a removal does not advance `i`.
650 let mut i = 0;
651 while i < minutiae.len() {
652 let m = minutiae[i].clone();
653
654 // PORT L3216–L3220: extract a contour centered on the minutia point.
655 let contour = match get_centered_contour(
656 lfsparms.side_half_contour,
657 m.x,
658 m.y,
659 m.ex,
660 m.ey,
661 bdata,
662 iw,
663 ih,
664 ) {
665 // PORT L3232–L3247: loop / impossible / short → remove.
666 CenteredContour::Loop | CenteredContour::Ignore | CenteredContour::Incomplete => {
667 minutiae.remove(i);
668 continue;
669 }
670 CenteredContour::Ok(c) => c,
671 };
672
673 // PORT L3272–L3286: rotate the contour y-coords by the negative feature direction.
674 let theta = f64::from(m.direction) * pi_factor;
675 let sin_theta = theta.sin();
676 let cos_theta = theta.cos();
677 let mut rot_y = Vec::with_capacity(contour.len());
678 for j in 0..contour.len() {
679 let mut drot_y =
680 (f64::from(contour.x[j]) * sin_theta) - (f64::from(contour.y[j]) * cos_theta);
681 drot_y = trunc_dbl_precision(drot_y, TRUNC_SCALE);
682 rot_y.push(sround(drot_y));
683 }
684
685 // PORT L3290: relative minima/maxima of the rotated y-coords.
686 let mm = minmaxs(&rot_y);
687 let minmax_num = mm.idx.len();
688
689 // PORT L3302–L3341: exactly one minimum → relocate (or drop if now invalid).
690 if minmax_num == 1 && mm.kind[0] == -1 {
691 let loc = mm.idx[0] as usize;
692 let side_minutia_adjust =
693 adjust_side_minutia(&mut minutiae[i], &contour, loc, direction_map, mw, lfsparms);
694 match side_minutia_adjust {
695 // PORT L3317: the reference removes it and does not advance — "the next minutia has
696 // slid into position pointed to by 'i'". Both halves are load-bearing: the relocated
697 // minutia is still at `i`, so leaving it there re-enters this arm forever.
698 SideAdjust::Removed => {
699 minutiae.remove(i);
700 }
701 SideAdjust::Kept => i += 1,
702 }
703 }
704 // PORT L3343–L3386: min-max-min → relocate onto the deeper minimum (or drop if invalid).
705 else if minmax_num == 3 && mm.kind[0] == -1 {
706 let loc = if mm.val[0] < mm.val[2] {
707 mm.idx[0] as usize
708 } else {
709 mm.idx[2] as usize
710 };
711 match adjust_side_minutia(&mut minutiae[i], &contour, loc, direction_map, mw, lfsparms)
712 {
713 // PORT L3376: as above — remove, and do not advance.
714 SideAdjust::Removed => {
715 minutiae.remove(i);
716 }
717 SideAdjust::Kept => i += 1,
718 }
719 }
720 // PORT L3388–L3407: any other pattern → remove.
721 else {
722 minutiae.remove(i);
723 }
724 }
725}
726
727/// Whether an adjusted side minutia was kept (advance) or removed (slide).
728enum SideAdjust {
729 Kept,
730 Removed,
731}
732
733/// Relocate a side minutia onto contour point `loc` and drop it if that lands in an invalid block —
734/// the shared tail of [`remove_or_adjust_side_minutiae_v2`]'s two adjustment cases (stock
735/// `remove.c` L3307–L3339 / L3353–L3385).
736///
737/// Returns whether the minutia was removed (so the caller must not advance) or kept.
738fn adjust_side_minutia(
739 minutia: &mut DetMinutia,
740 contour: &Contour,
741 loc: usize,
742 direction_map: &[i32],
743 mw: i32,
744 lfsparms: &LfsParms,
745) -> SideAdjust {
746 // PORT L3308–L3311: reset the minutia location to the extremum's contour point.
747 minutia.x = contour.x[loc];
748 minutia.y = contour.y[loc];
749 minutia.ex = contour.ex[loc];
750 minutia.ey = contour.ey[loc];
751
752 // PORT L3314–L3334: drop it if the adjusted point is now in an invalid block.
753 let bx = minutia.x / lfsparms.blocksize;
754 let by = minutia.y / lfsparms.blocksize;
755 if direction_map[(by * mw + bx) as usize] == INVALID_DIR {
756 SideAdjust::Removed
757 } else {
758 SideAdjust::Kept
759 }
760}
761
762/// Remove minutia pairs forming a hook on the side of a ridge or valley — port of stock
763/// `remove_hooks` (`remove.c` L332).
764fn remove_hooks(
765 minutiae: &mut Vec<DetMinutia>,
766 bdata: &[u8],
767 iw: i32,
768 ih: i32,
769 lfsparms: &LfsParms,
770) {
771 // PORT L347–L364: removal flags and the join-direction thresholds.
772 let mut to_remove = vec![false; minutiae.len()];
773 let full_ndirs = lfsparms.num_directions << 1;
774 let qtr_ndirs = lfsparms.num_directions >> 2;
775 let min_deltadir = (3 * qtr_ndirs) - 1;
776
777 // PORT L366: foreach primary minutia (bar the last).
778 let mut f = 0;
779 while f + 1 < minutiae.len() {
780 // PORT L371: skip a first minutia already flagged.
781 if !to_remove[f] {
782 let m1 = minutiae[f].clone();
783 // PORT L378: foreach secondary minutia to its right.
784 let mut s = f + 1;
785 while s < minutiae.len() {
786 let m2 = minutiae[s].clone();
787
788 // PORT L393–L397: first minutia's pixel changed → next first.
789 if bdata[(m1.y * iw + m1.x) as usize] != m1.kind as u8 {
790 break;
791 }
792 // PORT L400–L402: second minutia's pixel changed → flag it.
793 if bdata[(m2.y * iw + m2.x) as usize] != m2.kind as u8 {
794 to_remove[s] = true;
795 }
796
797 // PORT L405: only proceed if the second is not flagged.
798 if !to_remove[s] {
799 // PORT L408–L410: vertical gap gate.
800 let delta_y = m2.y - m1.y;
801 if delta_y <= lfsparms.max_rmtest_dist {
802 // PORT L415–L418: Euclidean distance gate.
803 let dist = distance(m1.x, m1.y, m2.x, m2.y);
804 if dist <= f64::from(lfsparms.max_rmtest_dist) {
805 // PORT L424–L435: direction-difference gate.
806 let deltadir = closest_dir_dist(m1.direction, m2.direction, full_ndirs);
807 if deltadir > min_deltadir {
808 // PORT L440: only opposite-type pairs form a hook.
809 if m1.kind != m2.kind {
810 // PORT L444–L446: hook test.
811 match on_hook(
812 m1.x,
813 m1.y,
814 m1.ex,
815 m1.ey,
816 m2.x,
817 m2.y,
818 lfsparms.max_hook_len,
819 bdata,
820 iw,
821 ih,
822 ) {
823 // PORT L449–L457: hook found → flag both.
824 OnHook::HookFound => {
825 to_remove[f] = true;
826 to_remove[s] = true;
827 }
828 // PORT L459–L468: IGNORE → flag the first, next first.
829 OnHook::Ignore => {
830 to_remove[f] = true;
831 break;
832 }
833 // PORT L474–L477: no hook → next second.
834 OnHook::NotFound => {}
835 }
836 }
837 }
838 }
839 } else {
840 // PORT L489–L497: 2nd too far below → next first.
841 break;
842 }
843 }
844
845 // PORT L503: next second minutia.
846 s += 1;
847 }
848 }
849 // PORT L509: next first minutia.
850 f += 1;
851 }
852
853 // PORT L513–L525: remove flagged minutiae in reverse index order.
854 remove_flagged(minutiae, &to_remove);
855}
856
857/// Remove minutia pairs sitting on opposite sides of an overlap — port of stock `remove_overlaps`
858/// (`remove.c` L1953).
859///
860/// Unlike the island/lake stage this does not edit the binary image.
861fn remove_overlaps(minutiae: &mut Vec<DetMinutia>, bdata: &[u8], iw: i32, lfsparms: &LfsParms) {
862 // PORT L1969–L1988: removal flags and the join-direction thresholds.
863 let mut to_remove = vec![false; minutiae.len()];
864 let full_ndirs = lfsparms.num_directions << 1;
865 let qtr_ndirs = lfsparms.num_directions >> 2;
866 let half_ndirs = lfsparms.num_directions >> 1;
867 let min_deltadir = (3 * qtr_ndirs) - 1;
868
869 // PORT L1990: foreach primary minutia (bar the last).
870 let mut f = 0;
871 while f + 1 < minutiae.len() {
872 // PORT L1995: skip a first minutia already flagged.
873 if !to_remove[f] {
874 let m1 = minutiae[f].clone();
875 // PORT L2002: foreach secondary minutia to its right.
876 let mut s = f + 1;
877 while s < minutiae.len() {
878 let m2 = minutiae[s].clone();
879
880 // PORT L2017–L2021: first minutia's pixel changed → next first.
881 if bdata[(m1.y * iw + m1.x) as usize] != m1.kind as u8 {
882 break;
883 }
884 // PORT L2024–L2026: second minutia's pixel changed → flag it.
885 if bdata[(m2.y * iw + m2.x) as usize] != m2.kind as u8 {
886 to_remove[s] = true;
887 }
888
889 // PORT L2029: only proceed if the second is not flagged.
890 if !to_remove[s] {
891 // PORT L2032–L2034: vertical gap gate.
892 let delta_y = m2.y - m1.y;
893 if delta_y <= lfsparms.max_overlap_dist {
894 // PORT L2039–L2042: Euclidean distance gate.
895 let dist = distance(m1.x, m1.y, m2.x, m2.y);
896 if dist <= f64::from(lfsparms.max_overlap_dist) {
897 // PORT L2048–L2059: direction-difference gate.
898 let deltadir = closest_dir_dist(m1.direction, m2.direction, full_ndirs);
899 if deltadir > min_deltadir {
900 // PORT L2064: only same-type pairs form an overlap.
901 if m1.kind == m2.kind {
902 // PORT L2071–L2082: joining direction relative to minutia1's
903 // opposite direction.
904 let mut joindir = line2direction(
905 m1.x,
906 m1.y,
907 m2.x,
908 m2.y,
909 lfsparms.num_directions,
910 );
911 let opp1dir =
912 (m1.direction + lfsparms.num_directions) % full_ndirs;
913 joindir = (opp1dir - joindir).abs();
914 joindir = joindir.min(full_ndirs - joindir);
915
916 // PORT L2089–L2102: shallow join angle or close pair, with a
917 // free path → overlap, flag both.
918 if (joindir <= half_ndirs
919 || dist <= f64::from(lfsparms.max_overlap_join_dist))
920 && free_path(m1.x, m1.y, m2.x, m2.y, bdata, iw, lfsparms)
921 {
922 to_remove[f] = true;
923 to_remove[s] = true;
924 }
925 }
926 }
927 }
928 } else {
929 // PORT L2118–L2126: 2nd too far below → next first.
930 break;
931 }
932 }
933
934 // PORT L2132: next second minutia.
935 s += 1;
936 }
937 }
938 // PORT L2138: next first minutia.
939 f += 1;
940 }
941
942 // PORT L2142–L2154: remove flagged minutiae in reverse index order.
943 remove_flagged(minutiae, &to_remove);
944}
945
946/// Remove "irregularly" shaped minutiae — port of stock `remove_malformations` (`remove.c` L1105).
947///
948/// For each minutia (walked in reverse) two `malformation_steps_2`-long contours are traced either
949/// way; a point on an incomplete/looping contour is dropped. Otherwise the across-feature spans at the
950/// two step marks are measured: a zero span, an over-long span in a low-flow block, or a large
951/// span-length ratio where the far span crosses opposite-colored pixels marks the minutia malformed.
952fn remove_malformations(
953 minutiae: &mut Vec<DetMinutia>,
954 bdata: &[u8],
955 iw: i32,
956 ih: i32,
957 low_flow_map: &[i32],
958 mw: i32,
959 lfsparms: &LfsParms,
960) {
961 let steps1 = lfsparms.malformation_steps_1;
962 let steps2 = lfsparms.malformation_steps_2;
963
964 // PORT L1122: walk the list in reverse (removal keeps lower indices valid).
965 let mut i = minutiae.len() as i32 - 1;
966 while i >= 0 {
967 let idx = i as usize;
968 let m = minutiae[idx].clone();
969
970 // PORT L1124–L1129: first contour, counter-clockwise.
971 let (ax1, ay1, bx1, by1) = match trace_contour(
972 steps2,
973 m.x,
974 m.y,
975 m.x,
976 m.y,
977 m.ex,
978 m.ey,
979 ScanDir::CounterClockwise,
980 bdata,
981 iw,
982 ih,
983 ) {
984 // PORT L1139–L1154: loop / impossible / short → remove.
985 TraceResult::Ignore => {
986 minutiae.remove(idx);
987 i -= 1;
988 continue;
989 }
990 TraceResult::Loop(_) => {
991 minutiae.remove(idx);
992 i -= 1;
993 continue;
994 }
995 TraceResult::Traced(c) => {
996 if (c.len() as i32) < steps2 {
997 minutiae.remove(idx);
998 i -= 1;
999 continue;
1000 }
1001 // PORT L1157–L1163: 'A1' and 'B1' contour points.
1002 (
1003 c.x[(steps1 - 1) as usize],
1004 c.y[(steps1 - 1) as usize],
1005 c.x[(steps2 - 1) as usize],
1006 c.y[(steps2 - 1) as usize],
1007 )
1008 }
1009 };
1010
1011 // PORT L1168–L1173: second contour, clockwise.
1012 let (ax2, ay2, bx2, by2) = match trace_contour(
1013 steps2,
1014 m.x,
1015 m.y,
1016 m.x,
1017 m.y,
1018 m.ex,
1019 m.ey,
1020 ScanDir::Clockwise,
1021 bdata,
1022 iw,
1023 ih,
1024 ) {
1025 // PORT L1183–L1198: loop / impossible / short → remove.
1026 TraceResult::Ignore => {
1027 minutiae.remove(idx);
1028 i -= 1;
1029 continue;
1030 }
1031 TraceResult::Loop(_) => {
1032 minutiae.remove(idx);
1033 i -= 1;
1034 continue;
1035 }
1036 TraceResult::Traced(c) => {
1037 if (c.len() as i32) < steps2 {
1038 minutiae.remove(idx);
1039 i -= 1;
1040 continue;
1041 }
1042 // PORT L1201–L1207: 'A2' and 'B2' contour points.
1043 (
1044 c.x[(steps1 - 1) as usize],
1045 c.y[(steps1 - 1) as usize],
1046 c.x[(steps2 - 1) as usize],
1047 c.y[(steps2 - 1) as usize],
1048 )
1049 }
1050 };
1051
1052 // PORT L1213–L1218: span lengths at the two step marks and the minutia's block.
1053 let a_dist = distance(ax1, ay1, ax2, ay2);
1054 let b_dist = distance(bx1, by1, bx2, by2);
1055 let blk_x = m.x / lfsparms.blocksize;
1056 let blk_y = m.y / lfsparms.blocksize;
1057
1058 let mut removed = false;
1059
1060 // PORT L1222–L1230: a zero-length span is malformed.
1061 if a_dist == 0.0 || b_dist == 0.0 {
1062 minutiae.remove(idx);
1063 removed = true;
1064 }
1065
1066 // PORT L1232–L1247: low-flow block cursory test on the far span.
1067 if !removed {
1068 let fmapval = low_flow_map[(blk_y * mw + blk_x) as usize];
1069 if fmapval != 0 && b_dist > f64::from(lfsparms.max_malformation_dist) {
1070 minutiae.remove(idx);
1071 removed = true;
1072 }
1073 }
1074
1075 // PORT L1249–L1284: span-ratio test along the far span line.
1076 if !removed {
1077 if let Ok(pts) = line_points(bx1, by1, bx2, by2) {
1078 for (x, y) in pts {
1079 // PORT L1257: far span crosses a pixel opposite the minutia type.
1080 if bdata[(y * iw + x) as usize] != m.kind as u8 {
1081 // PORT L1259–L1262: quantized span ratio.
1082 let mut ratio = b_dist / a_dist;
1083 ratio = trunc_dbl_precision(ratio, TRUNC_SCALE);
1084 // PORT L1264–L1277: far span sufficiently longer → malformed.
1085 if ratio > lfsparms.min_malformation_ratio {
1086 minutiae.remove(idx);
1087 break;
1088 }
1089 }
1090 }
1091 }
1092 }
1093
1094 i -= 1;
1095 }
1096}
1097
1098/// Remove minutiae located on pore-shaped valleys/ridges in unreliable regions — port of stock
1099/// `remove_pores_V2` (`remove.c` L2572).
1100///
1101/// Only tests minutiae in LOW RIDGE FLOW or HIGH CURVATURE blocks with a valid direction. For each, a
1102/// reference point R is placed just behind the minutia and the two white transitions P and Q either
1103/// side of it are found; short contours walked from P and Q give the four points A/B/C/D. If any step
1104/// fails, or the A-B / C-D squared-distance ratio is small enough, the minutia is a pore and is
1105/// removed.
1106#[expect(clippy::too_many_arguments)]
1107fn remove_pores_v2(
1108 minutiae: &mut Vec<DetMinutia>,
1109 bdata: &[u8],
1110 iw: i32,
1111 ih: i32,
1112 direction_map: &[i32],
1113 low_flow_map: &[i32],
1114 high_curve_map: &[i32],
1115 mw: i32,
1116 lfsparms: &LfsParms,
1117) {
1118 // PORT L2623: integer-direction → radians factor.
1119 let pi_factor = std::f64::consts::PI / f64::from(lfsparms.num_directions);
1120
1121 // PORT L2626: walk the list; a removal does not advance `i`.
1122 let mut i = 0;
1123 while i < minutiae.len() {
1124 let m = minutiae[i].clone();
1125
1126 // PORT L2636–L2643: only test unreliable blocks with a valid direction.
1127 let blk_x = m.x / lfsparms.blocksize;
1128 let blk_y = m.y / lfsparms.blocksize;
1129 let bi = (blk_y * mw + blk_x) as usize;
1130 let unreliable = low_flow_map[bi] != 0 || high_curve_map[bi] != 0;
1131
1132 let remove_it = if unreliable && direction_map[bi] >= 0 {
1133 pores_v2_is_pore(&m, bdata, iw, ih, pi_factor, lfsparms)
1134 } else {
1135 false
1136 };
1137
1138 // PORT L2929–L2933: remove a pore (no advance), else advance.
1139 if remove_it {
1140 minutiae.remove(i);
1141 } else {
1142 i += 1;
1143 }
1144 }
1145}
1146
1147/// The per-minutia pore test of [`remove_pores_v2`] — returns whether the minutia should be removed
1148/// (stock `remove.c` L2644–L2927).
1149fn pores_v2_is_pore(
1150 m: &DetMinutia,
1151 bdata: &[u8],
1152 iw: i32,
1153 ih: i32,
1154 pi_factor: f64,
1155 lfsparms: &LfsParms,
1156) -> bool {
1157 // PORT L2645–L2660: reference point R, `pores_trans_r` behind the minutia.
1158 let theta = f64::from(m.direction) * pi_factor;
1159 let sin_theta = theta.sin();
1160 let cos_theta = theta.cos();
1161 let mut drx = f64::from(m.x) - (sin_theta * f64::from(lfsparms.pores_trans_r));
1162 let mut dry = f64::from(m.y) + (cos_theta * f64::from(lfsparms.pores_trans_r));
1163 drx = trunc_dbl_precision(drx, TRUNC_SCALE);
1164 dry = trunc_dbl_precision(dry, TRUNC_SCALE);
1165 let rx = sround(drx);
1166 let ry = sround(dry);
1167
1168 // PORT L2663/L2925: R must be opposite the minutia's colour, else keep the minutia.
1169 if bdata[(ry * iw + rx) as usize] == m.kind as u8 {
1170 return false;
1171 }
1172
1173 // PORT L2670–L2674: find P (a white transition perpendicular to the minutia direction).
1174 let (px, py, pex, pey) = match search_in_direction(
1175 m.kind as u8,
1176 rx,
1177 ry,
1178 -cos_theta,
1179 -sin_theta,
1180 lfsparms.pores_perp_steps,
1181 bdata,
1182 iw,
1183 ih,
1184 ) {
1185 Some(p) => p,
1186 // PORT L2913–L2924: P not found → pore.
1187 None => return true,
1188 };
1189
1190 // PORT L2677–L2717: B — trace P counter-clockwise (forward).
1191 let (bx, by) = match pores_endpoint(
1192 lfsparms.pores_steps_fwd,
1193 px,
1194 py,
1195 pex,
1196 pey,
1197 ScanDir::CounterClockwise,
1198 bdata,
1199 iw,
1200 ih,
1201 ) {
1202 Some(p) => p,
1203 // PORT L2701–L2708: RMB → pore.
1204 None => return true,
1205 };
1206
1207 // PORT L2719–L2761: D — trace P clockwise (backward).
1208 let (dx, dy) = match pores_endpoint(
1209 lfsparms.pores_steps_bwd,
1210 px,
1211 py,
1212 pex,
1213 pey,
1214 ScanDir::Clockwise,
1215 bdata,
1216 iw,
1217 ih,
1218 ) {
1219 Some(p) => p,
1220 // PORT L2745–L2752: RMD → pore.
1221 None => return true,
1222 };
1223
1224 // PORT L2768–L2772: find Q (opposite side of R from P).
1225 let (qx, qy, qex, qey) = match search_in_direction(
1226 m.kind as u8,
1227 rx,
1228 ry,
1229 cos_theta,
1230 sin_theta,
1231 lfsparms.pores_perp_steps,
1232 bdata,
1233 iw,
1234 ih,
1235 ) {
1236 Some(q) => q,
1237 // PORT L2898–L2909: Q not found → pore.
1238 None => return true,
1239 };
1240
1241 // PORT L2776–L2816: A — trace Q clockwise (forward).
1242 let (ax, ay) = match pores_endpoint(
1243 lfsparms.pores_steps_fwd,
1244 qx,
1245 qy,
1246 qex,
1247 qey,
1248 ScanDir::Clockwise,
1249 bdata,
1250 iw,
1251 ih,
1252 ) {
1253 Some(p) => p,
1254 // PORT L2800–L2807: RMA → pore.
1255 None => return true,
1256 };
1257
1258 // PORT L2818–L2862: C — trace Q counter-clockwise (backward).
1259 let (cx, cy) = match pores_endpoint(
1260 lfsparms.pores_steps_bwd,
1261 qx,
1262 qy,
1263 qex,
1264 qey,
1265 ScanDir::CounterClockwise,
1266 bdata,
1267 iw,
1268 ih,
1269 ) {
1270 Some(p) => p,
1271 // PORT L2845–L2853: RMC → pore.
1272 None => return true,
1273 };
1274
1275 // PORT L2864–L2894: compare the A-B and C-D squared spans.
1276 let ab2 = squared_distance(ax, ay, bx, by);
1277 let cd2 = squared_distance(cx, cy, dx, dy);
1278 if cd2 > lfsparms.pores_min_dist2 {
1279 let ratio = ab2 / cd2;
1280 // PORT L2877–L2891: A-B not sufficiently longer than C-D → pore.
1281 if ratio <= lfsparms.pores_max_ratio {
1282 return true;
1283 }
1284 }
1285
1286 // PORT L2892/L2925: ratio too big or C-D span negligible → keep the minutia.
1287 false
1288}
1289
1290/// Trace `steps` points from a pore edge pixel and return the last contour point — the shared contour
1291/// walk of [`pores_v2_is_pore`]. Returns `None` on an impossible/looping/short trace (stock's remove
1292/// paths).
1293#[expect(clippy::too_many_arguments)]
1294fn pores_endpoint(
1295 steps: i32,
1296 x: i32,
1297 y: i32,
1298 ex: i32,
1299 ey: i32,
1300 scan: ScanDir,
1301 bdata: &[u8],
1302 iw: i32,
1303 ih: i32,
1304) -> Option<(i32, i32)> {
1305 match trace_contour(steps, x, y, x, y, ex, ey, scan, bdata, iw, ih) {
1306 TraceResult::Traced(c) if (c.len() as i32) >= steps => {
1307 let l = c.len() - 1;
1308 Some((c.x[l], c.y[l]))
1309 }
1310 _ => None,
1311 }
1312}
1313
1314/// Remove the minutiae whose `to_remove` flag is set, in reverse index order so earlier indices stay
1315/// valid — the shared tail of the flag-based stages (stock's reverse `remove_minutia` loop).
1316fn remove_flagged(minutiae: &mut Vec<DetMinutia>, to_remove: &[bool]) {
1317 for i in (0..minutiae.len()).rev() {
1318 if to_remove[i] {
1319 minutiae.remove(i);
1320 }
1321 }
1322}
1323
1324/// The number of numbered stages `remove_false_minutia_V2` runs — the width of a [`RemovalTally`].
1325pub(crate) const NUM_REMOVAL_STAGES: usize = 10;
1326
1327/// How many minutiae each numbered stage of [`remove_false_minutia_v2`] dropped, indexed by the
1328/// reference's own stage number minus one (slot `0` is stage 1, slot `9` is stage 10).
1329///
1330/// Slot `0` is the sort, which permutes the list and so is always `0`. Slot `5` (stage 6,
1331/// `remove_or_adjust_side_minutiae_v2`) both removes and *adjusts*; an adjust leaves the length
1332/// alone, so the slot counts its remove path only.
1333pub(crate) type RemovalTally = [usize; NUM_REMOVAL_STAGES];
1334
1335/// Detect and remove false minutiae — port of stock `remove_false_minutia_V2` (`remove.c` L172).
1336///
1337/// Runs the ten removal stages in the reference order over the detected minutiae list, editing the
1338/// binary image where the reference does (island/lake filling). `direction_map`, `low_flow_map` and
1339/// `high_curve_map` are the `mw`×`mh` **block** maps (indexed by block, not pixel); `bdata` is the
1340/// `iw`×`ih` binary image in stock convention (`0 == white/valley`, `1 == black/ridge`).
1341///
1342/// Returns the [`RemovalTally`] — the per-stage drop counts. The reference returns nothing but the
1343/// error code; the tally is a measurement taken around the same calls, and changes no behaviour.
1344///
1345/// # Errors
1346///
1347/// Returns `Ok`; the `Result` mirrors the reference signature (whose negative error codes are
1348/// unreachable in the port) so the driver in `lib.rs` can stay uniform with the detection stage.
1349#[expect(clippy::too_many_arguments)]
1350pub(crate) fn remove_false_minutia_v2(
1351 minutiae: &mut Vec<DetMinutia>,
1352 bdata: &mut [u8],
1353 iw: i32,
1354 ih: i32,
1355 direction_map: &[i32],
1356 low_flow_map: &[i32],
1357 high_curve_map: &[i32],
1358 mw: i32,
1359 mh: i32,
1360 lfsparms: &LfsParms,
1361) -> Result<RemovalTally, i32> {
1362 let mut tally: RemovalTally = [0; NUM_REMOVAL_STAGES];
1363
1364 /// Record the drop across one stage: the length before, minus the length after.
1365 macro_rules! staged {
1366 ($slot:expr, $call:expr) => {{
1367 let before = minutiae.len();
1368 $call;
1369 tally[$slot] = before - minutiae.len();
1370 }};
1371 }
1372
1373 // 1. PORT L179–L182: sort top-to-bottom, left-to-right.
1374 staged!(0, sort_minutiae_y_x(minutiae, iw));
1375
1376 // 2. PORT L184–L189: remove minutiae on lakes/islands (edits the binary image).
1377 staged!(
1378 1,
1379 remove_islands_and_lakes(minutiae, bdata, iw, ih, lfsparms)
1380 );
1381
1382 // 3. PORT L191–L195: remove minutiae on single-point holes.
1383 staged!(2, remove_holes(minutiae, bdata, iw, ih, lfsparms));
1384
1385 // 4. PORT L197–L202: remove minutiae pointing at an invalid block.
1386 staged!(
1387 3,
1388 remove_pointing_invblock_v2(minutiae, direction_map, mw, mh, lfsparms)
1389 );
1390
1391 // 5. PORT L204–L209: remove minutiae near an invalid block.
1392 staged!(
1393 4,
1394 remove_near_invblock_v2(minutiae, direction_map, mw, mh, lfsparms)
1395 );
1396
1397 // 6. PORT L211–L216: remove or adjust side minutiae.
1398 staged!(
1399 5,
1400 remove_or_adjust_side_minutiae_v2(minutiae, bdata, iw, ih, direction_map, mw, lfsparms)
1401 );
1402
1403 // 7. PORT L218–L221: remove hooks.
1404 staged!(6, remove_hooks(minutiae, bdata, iw, ih, lfsparms));
1405
1406 // 8. PORT L223–L226: remove overlaps.
1407 staged!(7, remove_overlaps(minutiae, bdata, iw, lfsparms));
1408
1409 // 9. PORT L228–L232: remove malformations.
1410 staged!(
1411 8,
1412 remove_malformations(minutiae, bdata, iw, ih, low_flow_map, mw, lfsparms)
1413 );
1414
1415 // 10. PORT L234–L240: remove pores.
1416 staged!(
1417 9,
1418 remove_pores_v2(
1419 minutiae,
1420 bdata,
1421 iw,
1422 ih,
1423 direction_map,
1424 low_flow_map,
1425 high_curve_map,
1426 mw,
1427 lfsparms,
1428 )
1429 );
1430
1431 // PORT L242: normal return.
1432 Ok(tally)
1433}
1434
1435#[cfg(test)]
1436mod tests {
1437 use super::*;
1438 use crate::detect::RIDGE_ENDING;
1439
1440 fn minutia(x: i32, y: i32, ex: i32, ey: i32, direction: i32, kind: i32) -> DetMinutia {
1441 DetMinutia {
1442 x,
1443 y,
1444 ex,
1445 ey,
1446 direction,
1447 reliability: 0.99,
1448 kind,
1449 appearing: true,
1450 feature_id: 0,
1451 nbrs: Vec::new(),
1452 ridge_counts: Vec::new(),
1453 }
1454 }
1455
1456 #[test]
1457 fn num_valid_8nbrs_counts_within_bounds() {
1458 // 3x3 map, all valid (0) except center's NW corner which is -1.
1459 let map = vec![-1, 0, 0, 0, 0, 0, 0, 0, 0];
1460 // Center (1,1): NW is index 0 == -1 (invalid), other seven valid → 7.
1461 assert_eq!(num_valid_8nbrs(&map, 1, 1, 3, 3), 7);
1462 // Corner (0,0): only E, SE, S in-bounds and valid → 3.
1463 assert_eq!(num_valid_8nbrs(&map, 0, 0, 3, 3), 3);
1464 }
1465
1466 #[test]
1467 fn free_path_counts_transitions() {
1468 // A 6-wide, 1-tall row: 0 0 1 0 0 0. Path (0,0)->(5,0) has 2 transitions (0->1, 1->0).
1469 let bdata = vec![0u8, 0, 1, 0, 0, 0];
1470 let mut p = crate::params::LFSPARMS_V2;
1471 p.maxtrans = 2;
1472 assert!(free_path(0, 0, 5, 0, &bdata, 6, &p));
1473 // With only 1 allowed transition, the same path is not free.
1474 p.maxtrans = 1;
1475 assert!(!free_path(0, 0, 5, 0, &bdata, 6, &p));
1476 }
1477
1478 #[test]
1479 fn sort_minutiae_y_x_orders_top_left_first() {
1480 let mut ms = vec![
1481 minutia(5, 2, 5, 1, 0, RIDGE_ENDING),
1482 minutia(1, 2, 1, 1, 0, RIDGE_ENDING),
1483 minutia(3, 1, 3, 0, 0, RIDGE_ENDING),
1484 ];
1485 sort_minutiae_y_x(&mut ms, 10);
1486 // y=1 row first, then y=2 row left-to-right.
1487 assert_eq!((ms[0].x, ms[0].y), (3, 1));
1488 assert_eq!((ms[1].x, ms[1].y), (1, 2));
1489 assert_eq!((ms[2].x, ms[2].y), (5, 2));
1490 }
1491
1492 #[test]
1493 fn remove_flagged_removes_in_reverse() {
1494 let mut ms = vec![
1495 minutia(0, 0, 0, 0, 0, RIDGE_ENDING),
1496 minutia(1, 1, 1, 1, 0, RIDGE_ENDING),
1497 minutia(2, 2, 2, 2, 0, RIDGE_ENDING),
1498 ];
1499 remove_flagged(&mut ms, &[true, false, true]);
1500 assert_eq!(ms.len(), 1);
1501 assert_eq!((ms[0].x, ms[0].y), (1, 1));
1502 }
1503
1504 #[test]
1505 fn driver_on_empty_list_is_ok() {
1506 let mut ms: Vec<DetMinutia> = Vec::new();
1507 let mut bdata = vec![0u8; 64];
1508 let map = vec![0i32; 1];
1509 let p = crate::params::LFSPARMS_V2;
1510 assert!(
1511 remove_false_minutia_v2(&mut ms, &mut bdata, 8, 8, &map, &map, &map, 1, 1, &p).is_ok()
1512 );
1513 assert!(ms.is_empty());
1514 }
1515}