fprint_mindtct/detect/mod.rs
1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Minutiae detection on the binary image (`detect_minutiae_V2`): scan each image block with valid
6//! ridge-flow direction for candidate ridge endings and bifurcations, tracing the contour of each
7//! feature and matching the fixed 2×3 pixel-pair patterns. Submodule root for the detection stage.
8//!
9//! Faithful port of the detection routines spread across stock NBIS
10//! `mindtct/src/lib/mindtct/{minutia,line,chaincod,matchpat,contour,loop,shape}.c`. The scan driver
11//! (`detect_minutiae_V2`, `scan4minutiae_*`) and the shared minutia type live here in the root; the
12//! per-primitive helpers are split into submodules mirroring the stock files:
13//!
14//! * [`line`] — straight-line pixel trajectories between two points (`line.c`).
15//! * [`chaincod`] — 8-connected chain-code of a contour and its turn analysis (`chaincod.c`).
16//! * [`matchpat`] — the fixed feature patterns and the 2×3 pixel-pair scan (`matchpat.c`).
17//! * [`contour`] — ridge/valley contour tracing around a candidate point (`contour.c`), plus
18//! `line2direction`/`angle2line` (`util.c`).
19//! * [`loops`] — detection/handling of small ridge/valley loops (`loop.c`; `loop` is a Rust keyword,
20//! hence `loops`).
21//! * [`shape`] — per-row shape of a closed loop for concave-aware filling (`shape.c`).
22//!
23//! See `docs/mindtct-algorithm.md`.
24
25mod chaincod;
26pub(crate) mod contour;
27pub(crate) mod line;
28pub(crate) mod loops;
29mod matchpat;
30mod shape;
31
32use crate::params::LfsParms;
33
34use contour::{
35 get_high_curvature_contour, line2direction, min_contour_theta, search_contour,
36 HighCurvatureContour, ScanDir,
37};
38use loops::{is_loop_clockwise, process_loop_v2};
39use matchpat::{
40 match_1st_pair, match_2nd_pair, match_3rd_pair, skip_repeated_horizontal_pair,
41 skip_repeated_vertical_pair, FEATURE_PATTERNS,
42};
43
44use crate::block::block_offsets;
45
46/// Stock `type` values for a detected minutia (`lfs.h` L152–L153): the point is a ridge
47/// **bifurcation** (two ridges meeting) or a ridge **ending**.
48pub(crate) const BIFURCATION: i32 = 0;
49/// See [`BIFURCATION`].
50pub(crate) const RIDGE_ENDING: i32 = 1;
51
52/// Stock `INVALID_DIR` (`lfs.h` L320): a block whose ridge-flow direction could not be determined.
53const INVALID_DIR: i32 = -1;
54/// Stock `SCAN_HORIZONTAL` (`lfs.h` L494): feature scan runs across rows.
55const SCAN_HORIZONTAL: i32 = 0;
56/// Stock `SCAN_VERTICAL` (`lfs.h` L495): feature scan runs down columns.
57const SCAN_VERTICAL: i32 = 1;
58/// Stock `APPEARING` (`lfs.h` L155).
59const APPEARING: i32 = 1;
60/// Stock `DISAPPEARING` (`lfs.h` L154).
61const DISAPPEARING: i32 = 0;
62/// Stock `TRUE` (`lfs.h` L673) — the default winding passed to [`is_loop_clockwise`].
63const TRUE: i32 = 1;
64/// Stock `LOOP_ID` (`lfs.h` L491): the `feature_id` assigned to minutiae extracted from a loop.
65pub(crate) const LOOP_ID: i32 = 10;
66/// Stock `MEDIUM_RELIABILITY` (`lfs.h` L506): reliability of a minutia in a LOW RIDGE FLOW block.
67pub(crate) const MEDIUM_RELIABILITY: f64 = 0.50;
68/// Stock `HIGH_RELIABILITY` (`lfs.h` L509): reliability of a minutia in a reliable block.
69pub(crate) const HIGH_RELIABILITY: f64 = 0.99;
70
71/// One candidate minutia during detection — the port's analogue of the stock `MINUTIA` structure
72/// (`lfs.h` L157), one field per member.
73///
74/// The stock C carries `int appearing` (`APPEARING`/`DISAPPEARING`) and `int type`
75/// (`RIDGE_ENDING`/`BIFURCATION`); here `appearing` is a `bool` and `type` becomes `kind` (a Rust
76/// keyword). The variable-length neighbor arrays (`nbrs` + `ridge_counts`, sized by `num_nbrs`)
77/// become owned `Vec`s whose shared length *is* the stock `num_nbrs`; both are empty until the
78/// ridge-count/neighbor stage fills them.
79#[derive(Clone, Debug, PartialEq)]
80pub(crate) struct DetMinutia {
81 /// X pixel coordinate of the minutia point (stock `x`).
82 pub x: i32,
83 /// Y pixel coordinate of the minutia point (stock `y`).
84 pub y: i32,
85 /// X pixel coordinate of the paired feature-edge pixel (stock `ex`).
86 pub ex: i32,
87 /// Y pixel coordinate of the paired feature-edge pixel (stock `ey`).
88 pub ey: i32,
89 /// Quantized ridge-flow direction at the point, `0..num_directions` (stock `direction`).
90 pub direction: i32,
91 /// Reliability estimate in `[0.0, 1.0]`; higher is better (stock `reliability`).
92 pub reliability: f64,
93 /// Feature class, [`RIDGE_ENDING`] or [`BIFURCATION`] (stock `type`).
94 pub kind: i32,
95 /// Ridge-scan polarity: `true` = `APPEARING`, `false` = `DISAPPEARING` (stock `appearing`).
96 pub appearing: bool,
97 /// Index of the matched feature pattern, `0..NFEATURES` (stock `feature_id`).
98 pub feature_id: i32,
99 /// Indices of neighboring minutiae, filled by the ridge-count stage (stock `nbrs`); its length
100 /// is the stock `num_nbrs`.
101 pub nbrs: Vec<i32>,
102 /// Ridge counts to each neighbor, in `nbrs` order (stock `ridge_counts`).
103 pub ridge_counts: Vec<i32>,
104}
105
106/// Allocate and initialize a minutia from its detected attributes — port of stock `create_minutia`
107/// (`minutia.c` L903).
108///
109/// PORT: the stock out-parameter / `-230` malloc-failure return collapse into a by-value `DetMinutia`
110/// (allocation aborts rather than returning an error). `type`/`appearing` map to
111/// [`kind`](DetMinutia::kind) (`i32`) / a `bool`; `nbrs`/`ridge_counts` start empty (stock `NULL`,
112/// `num_nbrs == 0`).
113#[expect(clippy::too_many_arguments)]
114pub(crate) fn create_minutia(
115 x_loc: i32,
116 y_loc: i32,
117 x_edge: i32,
118 y_edge: i32,
119 idir: i32,
120 reliability: f64,
121 kind: i32,
122 appearing: bool,
123 feature_id: i32,
124) -> DetMinutia {
125 // PORT L920–L933: copy attributes into a fresh minutia; neighbor lists start empty.
126 DetMinutia {
127 x: x_loc,
128 y: y_loc,
129 ex: x_edge,
130 ey: y_edge,
131 direction: idir,
132 reliability,
133 kind,
134 appearing,
135 feature_id,
136 nbrs: Vec::new(),
137 ridge_counts: Vec::new(),
138 }
139}
140
141/// Remove the minutia at `index` from the list — port of stock `remove_minutia` (`minutia.c` L994).
142///
143/// PORT: the stock in-place slide + `num--` (and its `free_minutia`) is a `Vec::remove`; the
144/// out-of-range guard is dropped (a bad index panics, matching the reference's undefined behavior on
145/// the same input).
146fn remove_minutia(index: usize, minutiae: &mut Vec<DetMinutia>) {
147 minutiae.remove(index);
148}
149
150/// Classify a feature pixel as a ridge ending or a bifurcation — port of stock `minutia_type`
151/// (`minutia.c` L1167).
152///
153/// A white (`0`) feature pixel is a valley-ending → [`BIFURCATION`]; a black (`1`) feature pixel is a
154/// [`RIDGE_ENDING`].
155pub(crate) fn minutia_type(feature_pix: u8) -> i32 {
156 // PORT L1171–L1178: white → bifurcation, black → ridge-ending.
157 if feature_pix == 0 {
158 BIFURCATION
159 } else {
160 RIDGE_ENDING
161 }
162}
163
164/// Decide whether a minutia is appearing or disappearing from its feature/edge geometry — port of
165/// stock `is_minutia_appearing` (`minutia.c` L1203).
166///
167/// The edge pixel always sits N/S/E/W of the feature pixel: for a horizontal scan an edge above the
168/// feature is [`APPEARING`], below is [`DISAPPEARING`]; for a vertical scan an edge to the left is
169/// [`APPEARING`], to the right is [`DISAPPEARING`].
170///
171/// # Errors
172///
173/// `Err(-240)` on the stock "bad configuration of pixels" path — unreachable for the cardinally
174/// adjacent pairs the detector supplies, retained for a faithful transcription.
175pub(crate) fn is_minutia_appearing(
176 x_loc: i32,
177 y_loc: i32,
178 x_edge: i32,
179 y_edge: i32,
180) -> Result<i32, i32> {
181 // PORT L1209–L1214: horizontal scan — edge above/below the feature.
182 if x_edge < x_loc {
183 return Ok(APPEARING);
184 }
185 if x_edge > x_loc {
186 return Ok(DISAPPEARING);
187 }
188 // PORT L1217–L1222: vertical scan — edge left/right of the feature.
189 if y_edge < y_loc {
190 return Ok(APPEARING);
191 }
192 if y_edge > y_loc {
193 return Ok(DISAPPEARING);
194 }
195 // PORT L1225–L1228: should never happen for a cardinally adjacent pair.
196 Err(-240)
197}
198
199/// Choose the scan orientation for a block from its ridge-flow direction — port of stock
200/// `choose_scan_direction` (`minutia.c` L1244).
201///
202/// Relatively vertical flow (`imapval <= ndirs/4` or `> 3*ndirs/4`) is scanned [`SCAN_HORIZONTAL`];
203/// otherwise (relatively horizontal flow) it is scanned [`SCAN_VERTICAL`] — always orthogonal to the
204/// ridge flow.
205fn choose_scan_direction(imapval: i32, ndirs: i32) -> i32 {
206 // PORT L1251: quarter of the directions in the semicircle.
207 let qtr_ndirs = ndirs >> 2;
208 // PORT L1256–L1264: vertical flow → horizontal scan, else vertical scan.
209 if imapval <= qtr_ndirs || imapval > (qtr_ndirs * 3) {
210 SCAN_HORIZONTAL
211 } else {
212 SCAN_VERTICAL
213 }
214}
215
216/// Convert a semicircle IMAP direction to a full-circle minutia direction — port of stock
217/// `get_low_curvature_direction` (`minutia.c` L3450).
218///
219/// A bi-directional block direction (`imapval` on `[0..ndirs]`) is disambiguated to a full-circle
220/// direction on `[0..2*ndirs]` using the feature's scan orientation and appearing/disappearing
221/// polarity: in each of the two flow quadrants, one (scan, polarity) combination points opposite the
222/// ridge flow (`idir += ndirs`) and the other points along it.
223fn get_low_curvature_direction(scan_dir: i32, appearing: bool, imapval: i32, ndirs: i32) -> i32 {
224 // PORT L3459: start from the block direction.
225 let mut idir = imapval;
226
227 // PORT L3468: CASE I — ridge flow in quadrant I (`imapval <= ndirs/2`).
228 if imapval <= (ndirs >> 1) {
229 if scan_dir == SCAN_HORIZONTAL {
230 // PORT L3473–L3486: I.A — horizontal scan, appearing points opposite the flow.
231 if appearing {
232 idir += ndirs;
233 }
234 } else {
235 // PORT L3492–L3506: I.B — vertical scan, disappearing points opposite the flow.
236 if !appearing {
237 idir += ndirs;
238 }
239 }
240 }
241 // PORT L3512: CASE II — ridge flow in quadrant II (`imapval > ndirs/2`).
242 else if scan_dir == SCAN_HORIZONTAL {
243 // PORT L3517–L3530: II.A — horizontal scan, disappearing points opposite the flow.
244 if !appearing {
245 idir += ndirs;
246 }
247 } else {
248 // PORT L3536–L3550: II.B — vertical scan, disappearing points opposite the flow.
249 if !appearing {
250 idir += ndirs;
251 }
252 }
253
254 // PORT L3555: full-circle direction on `[0..2*ndirs]`.
255 idir
256}
257
258/// The adjusted attributes of a high-curvature minutia, or a decision to drop it — the port's split of
259/// stock `adjust_high_curvature_minutia_V2`'s out-parameters vs. its `IGNORE` return.
260enum AdjustResult {
261 /// The minutia was relocated to the contour's point of highest curvature with a new direction.
262 Adjusted {
263 idir: i32,
264 x_loc: i32,
265 y_loc: i32,
266 x_edge: i32,
267 y_edge: i32,
268 },
269 /// The candidate should be dropped (stock `IGNORE`).
270 Ignore,
271}
272
273/// Relocate a high-curvature candidate to its point of highest curvature — port of stock
274/// `adjust_high_curvature_minutia_V2` (`minutia.c` L3272).
275///
276/// Extracts the feature's contour ([`get_high_curvature_contour`]); if it closes a loop, a clockwise
277/// loop is ignored and a counter-clockwise one is handed to [`process_loop_v2`] (which may add loop
278/// minutiae or erase the loop) and the triggering candidate ignored. Otherwise the contour's point of
279/// minimum interior angle ([`min_contour_theta`]) becomes the minutia's new location, provided that
280/// angle is sharp enough and the interior midpoint agrees with the feature's colour; the direction is
281/// the line from that point to the interior midpoint ([`line2direction`]).
282///
283/// PORT: the four out-parameters and the `IGNORE` return collapse into [`AdjustResult`]; `Err(i32)` is
284/// a genuine (unreachable-in-port) system error.
285#[expect(clippy::too_many_arguments)]
286fn adjust_high_curvature_minutia_v2(
287 x_loc: i32,
288 y_loc: i32,
289 x_edge: i32,
290 y_edge: i32,
291 bdata: &mut [u8],
292 iw: i32,
293 ih: i32,
294 plow_flow_map: &[i32],
295 minutiae: &mut Vec<DetMinutia>,
296 lfsparms: &LfsParms,
297) -> Result<AdjustResult, i32> {
298 // PORT L3290: half the desired contour length.
299 let half_contour = lfsparms.high_curve_half_contour;
300 // PORT L3297: edge length for the curvature angle is a quarter of the full contour.
301 let angle_edge = half_contour >> 1;
302
303 // PORT L3300: feature (interior) pixel value.
304 let feature_pix = bdata[(y_loc * iw + x_loc) as usize];
305
306 // PORT L3303: extract the feature's contour.
307 match get_high_curvature_contour(half_contour, x_loc, y_loc, x_edge, y_edge, bdata, iw, ih) {
308 // PORT L3319–L3369: the contour forms a loop.
309 HighCurvatureContour::Loop(c) => {
310 // PORT L3330: default winding TRUE so an indeterminate loop is ignored (not filled).
311 let ret = is_loop_clockwise(&c.x, &c.y, TRUE);
312 if ret != 0 {
313 // PORT L3335–L3341: system error (<0) or clockwise loop → IGNORE.
314 if ret < 0 {
315 return Err(ret);
316 }
317 return Ok(AdjustResult::Ignore);
318 }
319 // PORT L3347–L3363: process the counter-clockwise loop, then ignore the trigger.
320 process_loop_v2(minutiae, &c, bdata, iw, ih, plow_flow_map, lfsparms)?;
321 Ok(AdjustResult::Ignore)
322 }
323 // PORT L3374–L3376: empty contour → IGNORE.
324 HighCurvatureContour::Empty => Ok(AdjustResult::Ignore),
325 HighCurvatureContour::Ok(c) => {
326 // PORT L3385: point of highest curvature (minimum interior angle).
327 let (min_i, min_theta) = match min_contour_theta(angle_edge, &c.x, &c.y) {
328 // PORT L3387–L3393: too short → IGNORE.
329 None => return Ok(AdjustResult::Ignore),
330 Some(v) => v,
331 };
332
333 // PORT L3396–L3402: reject a curvature that is too gentle.
334 if min_theta >= lfsparms.max_high_curve_theta {
335 return Ok(AdjustResult::Ignore);
336 }
337
338 // PORT L3407–L3416: interior midpoint symmetric about the minimum-theta point must match
339 // the feature's colour.
340 let mid_x =
341 (c.x[(min_i - angle_edge) as usize] + c.x[(min_i + angle_edge) as usize]) >> 1;
342 let mid_y =
343 (c.y[(min_i - angle_edge) as usize] + c.y[(min_i + angle_edge) as usize]) >> 1;
344 let mid_pix = bdata[(mid_y * iw + mid_x) as usize];
345 if mid_pix != feature_pix {
346 return Ok(AdjustResult::Ignore);
347 }
348
349 // PORT L3420–L3428: new direction and relocated feature/edge points.
350 let idir = line2direction(
351 c.x[min_i as usize],
352 c.y[min_i as usize],
353 mid_x,
354 mid_y,
355 lfsparms.num_directions,
356 );
357 Ok(AdjustResult::Adjusted {
358 idir,
359 x_loc: c.x[min_i as usize],
360 y_loc: c.y[min_i as usize],
361 x_edge: c.ex[min_i as usize],
362 y_edge: c.ey[min_i as usize],
363 })
364 }
365 }
366}
367
368/// Add a detected minutia to the list unless a compatible one is already present — port of stock
369/// `update_minutiae` (**version one**, `minutia.c` L355), used by the loop processor.
370///
371/// Scans the list (forward) for a same-type minutia within `max_minutia_delta` in X and Y whose
372/// direction is within 45°; if such a neighbour shares the point exactly, or lies on the same contour
373/// (searched both ways up to `max_minutia_delta` steps), the new minutia is dropped. Otherwise it is
374/// appended.
375///
376/// PORT: the stock `realloc`/`IGNORE`/`0` returns collapse into `Vec::push` vs. an early `Ok(())`
377/// (the dropped minutia is simply not pushed).
378pub(crate) fn update_minutiae(
379 minutiae: &mut Vec<DetMinutia>,
380 minutia: DetMinutia,
381 bdata: &[u8],
382 iw: i32,
383 ih: i32,
384 lfsparms: &LfsParms,
385) -> Result<(), i32> {
386 // PORT L376/L379: 45° = quarter of the semicircle; full circle = 2*ndirs.
387 let qtr_ndirs = lfsparms.num_directions >> 2;
388 let full_ndirs = lfsparms.num_directions << 1;
389
390 // PORT L385–L448: forward scan for a compatible existing minutia.
391 for existing in minutiae.iter() {
392 let dx = (existing.x - minutia.x).abs();
393 if dx >= lfsparms.max_minutia_delta {
394 continue;
395 }
396 let dy = (existing.y - minutia.y).abs();
397 if dy >= lfsparms.max_minutia_delta {
398 continue;
399 }
400 if existing.kind != minutia.kind {
401 continue;
402 }
403 // PORT L403–L409: inner direction difference within 45°.
404 let mut delta_dir = (existing.direction - minutia.direction).abs();
405 delta_dir = delta_dir.min(full_ndirs - delta_dir);
406 if delta_dir > qtr_ndirs {
407 continue;
408 }
409 // PORT L412–L418: exact same point → drop.
410 if dx == 0 && dy == 0 {
411 return Ok(());
412 }
413 // PORT L423–L446: same contour either way → drop.
414 if search_contour(
415 minutia.x,
416 minutia.y,
417 lfsparms.max_minutia_delta,
418 existing.x,
419 existing.y,
420 existing.ex,
421 existing.ey,
422 ScanDir::Clockwise,
423 bdata,
424 iw,
425 ih,
426 ) || search_contour(
427 minutia.x,
428 minutia.y,
429 lfsparms.max_minutia_delta,
430 existing.x,
431 existing.y,
432 existing.ex,
433 existing.ey,
434 ScanDir::CounterClockwise,
435 bdata,
436 iw,
437 ih,
438 ) {
439 return Ok(());
440 }
441 }
442
443 // PORT L453–L457: not already present → append.
444 minutiae.push(minutia);
445 Ok(())
446}
447
448/// Add a detected minutia to the list, preferring the more-compatible of near-duplicate pairs — port
449/// of stock `update_minutiae_V2` (`minutia.c` L474), used by the V2 scans.
450///
451/// Like [`update_minutiae`] but scans the list in **reverse** and, when the new minutia shares a
452/// contour with an existing one, keeps whichever is compatible with the block's ridge-flow scan
453/// direction: if the new point's scan direction matches, the existing one is removed and the new one
454/// added; if not, the new one is dropped; if the block direction is invalid, the new one is dropped.
455///
456/// PORT: the stock `realloc`/`IGNORE`/`0` returns collapse into `Vec::push`/`Vec::remove` vs. an early
457/// `Ok(())`. The reverse walk with in-place removal is preserved so list order matches the reference.
458#[expect(clippy::too_many_arguments)]
459pub(crate) fn update_minutiae_v2(
460 minutiae: &mut Vec<DetMinutia>,
461 minutia: DetMinutia,
462 scan_dir: i32,
463 dmapval: i32,
464 bdata: &[u8],
465 iw: i32,
466 ih: i32,
467 lfsparms: &LfsParms,
468) -> Result<(), i32> {
469 // PORT L509/L512: 45° = quarter of the semicircle; full circle = 2*ndirs.
470 let qtr_ndirs = lfsparms.num_directions >> 2;
471 let full_ndirs = lfsparms.num_directions << 1;
472
473 // PORT L517–L604: reverse scan for a compatible existing minutia.
474 let mut i = minutiae.len() as i32 - 1;
475 while i >= 0 {
476 let idx = i as usize;
477 let dx = (minutiae[idx].x - minutia.x).abs();
478 let dy = (minutiae[idx].y - minutia.y).abs();
479 let same_type = minutiae[idx].kind == minutia.kind;
480 if dx < lfsparms.max_minutia_delta && dy < lfsparms.max_minutia_delta && same_type {
481 // PORT L531–L537: inner direction difference within 45°.
482 let mut delta_dir = (minutiae[idx].direction - minutia.direction).abs();
483 delta_dir = delta_dir.min(full_ndirs - delta_dir);
484 if delta_dir <= qtr_ndirs {
485 // PORT L540–L546: exact same point → drop.
486 if dx == 0 && dy == 0 {
487 return Ok(());
488 }
489 // PORT L551–L568: do they share the same contour (searched both ways)?
490 let same_contour = search_contour(
491 minutia.x,
492 minutia.y,
493 lfsparms.max_minutia_delta,
494 minutiae[idx].x,
495 minutiae[idx].y,
496 minutiae[idx].ex,
497 minutiae[idx].ey,
498 ScanDir::Clockwise,
499 bdata,
500 iw,
501 ih,
502 ) || search_contour(
503 minutia.x,
504 minutia.y,
505 lfsparms.max_minutia_delta,
506 minutiae[idx].x,
507 minutiae[idx].y,
508 minutiae[idx].ex,
509 minutiae[idx].ey,
510 ScanDir::CounterClockwise,
511 bdata,
512 iw,
513 ih,
514 );
515 if same_contour {
516 // PORT L570–L595: choose between the two on the block scan direction.
517 if dmapval >= 0 {
518 let map_scan_dir = choose_scan_direction(dmapval, lfsparms.num_directions);
519 if map_scan_dir == scan_dir {
520 // PORT L583–L588: new point wins — remove the existing one, keep going.
521 remove_minutia(idx, minutiae);
522 } else {
523 // PORT L591–L594: keep the existing one, drop the new one.
524 return Ok(());
525 }
526 } else {
527 // PORT L598–L604: invalid block direction → drop the new one.
528 return Ok(());
529 }
530 }
531 }
532 }
533 i -= 1;
534 }
535
536 // PORT L615–L619: not already present (or duplicates removed) → append.
537 minutiae.push(minutia);
538 Ok(())
539}
540
541/// Process a candidate detected by the horizontal scan — port of stock
542/// `process_horizontal_scan_minutia_V2` (`minutia.c` L2716).
543///
544/// Places the minutia half-way between the second and third feature pair (`x_loc = (cx + x2) / 2`),
545/// derives its direction (locally adjusted in a high-curvature block, else from the block direction),
546/// sets reliability from the Low Ridge Flow map, and hands it to [`update_minutiae_v2`]. An invalid
547/// block direction or an [`AdjustResult::Ignore`] drops the candidate.
548///
549/// # Errors
550///
551/// Propagates negative stock system-error codes (unreachable in the port).
552#[expect(clippy::too_many_arguments)]
553fn process_horizontal_scan_minutia_v2(
554 minutiae: &mut Vec<DetMinutia>,
555 cx: i32,
556 cy: i32,
557 x2: i32,
558 feature_id: usize,
559 bdata: &mut [u8],
560 iw: i32,
561 ih: i32,
562 pdirection_map: &[i32],
563 plow_flow_map: &[i32],
564 phigh_curve_map: &[i32],
565 lfsparms: &LfsParms,
566) -> Result<(), i32> {
567 let fp = &FEATURE_PATTERNS[feature_id];
568
569 // PORT L2735–L2739: x half-way between 2nd and 3rd pair; edge shares the x.
570 let mut x_loc = (cx + x2) >> 1;
571 let mut x_edge = x_loc;
572
573 // PORT L2743–L2757: appearing → feature on the 2nd row (edge on the 1st), else reversed.
574 let (mut y_loc, mut y_edge) = if fp.appearing {
575 (cy + 1, cy)
576 } else {
577 (cy, cy + 1)
578 };
579
580 // PORT L2759–L2761: map values at the feature point.
581 let dmapval = pdirection_map[(y_loc * iw + x_loc) as usize];
582 let fmapval = plow_flow_map[(y_loc * iw + x_loc) as usize];
583 let cmapval = phigh_curve_map[(y_loc * iw + x_loc) as usize];
584
585 // PORT L2764–L2766: invalid block direction → drop.
586 if dmapval == INVALID_DIR {
587 return Ok(());
588 }
589
590 // PORT L2769–L2783: high-curvature block → adjust locally, else derive from block direction.
591 let idir;
592 if cmapval != 0 {
593 match adjust_high_curvature_minutia_v2(
594 x_loc,
595 y_loc,
596 x_edge,
597 y_edge,
598 bdata,
599 iw,
600 ih,
601 plow_flow_map,
602 minutiae,
603 lfsparms,
604 )? {
605 AdjustResult::Ignore => return Ok(()),
606 AdjustResult::Adjusted {
607 idir: d,
608 x_loc: xl,
609 y_loc: yl,
610 x_edge: xe,
611 y_edge: ye,
612 } => {
613 idir = d;
614 x_loc = xl;
615 y_loc = yl;
616 x_edge = xe;
617 y_edge = ye;
618 }
619 }
620 } else {
621 idir = get_low_curvature_direction(
622 SCAN_HORIZONTAL,
623 fp.appearing,
624 dmapval,
625 lfsparms.num_directions,
626 );
627 }
628
629 // PORT L2786–L2791: reliability from the (original) Low Ridge Flow value.
630 let reliability = if fmapval != 0 {
631 MEDIUM_RELIABILITY
632 } else {
633 HIGH_RELIABILITY
634 };
635
636 // PORT L2794–L2807: create the minutia and offer it to the list.
637 let minutia = create_minutia(
638 x_loc,
639 y_loc,
640 x_edge,
641 y_edge,
642 idir,
643 reliability,
644 fp.kind,
645 fp.appearing,
646 feature_id as i32,
647 );
648 update_minutiae_v2(
649 minutiae,
650 minutia,
651 SCAN_HORIZONTAL,
652 dmapval,
653 bdata,
654 iw,
655 ih,
656 lfsparms,
657 )
658}
659
660/// Process a candidate detected by the vertical scan — port of stock
661/// `process_vertical_scan_minutia_V2` (`minutia.c` L2942).
662///
663/// The vertical analogue of [`process_horizontal_scan_minutia_v2`]: the minutia is placed half-way
664/// between the second and third pair on the Y axis (`y_loc = (cy + y2) / 2`), and appearing/
665/// disappearing shifts the X coordinate instead of the Y.
666///
667/// # Errors
668///
669/// Propagates negative stock system-error codes (unreachable in the port).
670#[expect(clippy::too_many_arguments)]
671fn process_vertical_scan_minutia_v2(
672 minutiae: &mut Vec<DetMinutia>,
673 cx: i32,
674 cy: i32,
675 y2: i32,
676 feature_id: usize,
677 bdata: &mut [u8],
678 iw: i32,
679 ih: i32,
680 pdirection_map: &[i32],
681 plow_flow_map: &[i32],
682 phigh_curve_map: &[i32],
683 lfsparms: &LfsParms,
684) -> Result<(), i32> {
685 let fp = &FEATURE_PATTERNS[feature_id];
686
687 // PORT L2960–L2974: appearing → feature on the 2nd column (edge on the 1st), else reversed.
688 let (mut x_loc, mut x_edge) = if fp.appearing {
689 (cx + 1, cx)
690 } else {
691 (cx, cx + 1)
692 };
693
694 // PORT L2979–L2981: y half-way between 2nd and 3rd pair; edge shares the y.
695 let mut y_loc = (cy + y2) >> 1;
696 let mut y_edge = y_loc;
697
698 // PORT L2983–L2985: map values at the feature point.
699 let dmapval = pdirection_map[(y_loc * iw + x_loc) as usize];
700 let fmapval = plow_flow_map[(y_loc * iw + x_loc) as usize];
701 let cmapval = phigh_curve_map[(y_loc * iw + x_loc) as usize];
702
703 // PORT L2988–L2990: invalid block direction → drop.
704 if dmapval == INVALID_DIR {
705 return Ok(());
706 }
707
708 // PORT L2993–L3007: high-curvature block → adjust locally, else derive from block direction.
709 let idir;
710 if cmapval != 0 {
711 match adjust_high_curvature_minutia_v2(
712 x_loc,
713 y_loc,
714 x_edge,
715 y_edge,
716 bdata,
717 iw,
718 ih,
719 plow_flow_map,
720 minutiae,
721 lfsparms,
722 )? {
723 AdjustResult::Ignore => return Ok(()),
724 AdjustResult::Adjusted {
725 idir: d,
726 x_loc: xl,
727 y_loc: yl,
728 x_edge: xe,
729 y_edge: ye,
730 } => {
731 idir = d;
732 x_loc = xl;
733 y_loc = yl;
734 x_edge = xe;
735 y_edge = ye;
736 }
737 }
738 } else {
739 idir = get_low_curvature_direction(
740 SCAN_VERTICAL,
741 fp.appearing,
742 dmapval,
743 lfsparms.num_directions,
744 );
745 }
746
747 // PORT L3010–L3015: reliability from the (original) Low Ridge Flow value.
748 let reliability = if fmapval != 0 {
749 MEDIUM_RELIABILITY
750 } else {
751 HIGH_RELIABILITY
752 };
753
754 // PORT L3018–L3031: create the minutia and offer it to the list.
755 let minutia = create_minutia(
756 x_loc,
757 y_loc,
758 x_edge,
759 y_edge,
760 idir,
761 reliability,
762 fp.kind,
763 fp.appearing,
764 feature_id as i32,
765 );
766 update_minutiae_v2(
767 minutiae,
768 minutia,
769 SCAN_VERTICAL,
770 dmapval,
771 bdata,
772 iw,
773 ih,
774 lfsparms,
775 )
776}
777
778/// Scan the whole binary image horizontally for minutiae — port of stock
779/// `scan4minutiae_horizontally_V2` (`minutia.c` L1508).
780///
781/// Walks every adjacent row pair top-to-bottom, left-to-right, matching the three feature pixel pairs
782/// (skipping runs of the repeated second pair) and processing each hit via
783/// [`process_horizontal_scan_minutia_v2`]. `bdata` is `&mut` because a detected loop can erase itself
784/// from the image mid-scan, exactly as in the reference.
785#[expect(clippy::too_many_arguments)]
786fn scan4minutiae_horizontally_v2(
787 minutiae: &mut Vec<DetMinutia>,
788 bdata: &mut [u8],
789 iw: i32,
790 ih: i32,
791 pdirection_map: &[i32],
792 plow_flow_map: &[i32],
793 phigh_curve_map: &[i32],
794 lfsparms: &LfsParms,
795) -> Result<(), i32> {
796 // PORT L1519–L1522: scan region is the entire image.
797 let (sx, ex, sy, ey) = (0, iw, 0, ih);
798
799 // PORT L1525–L1601: for each adjacent row pair (top row `cy`, bottom row `cy+1`).
800 let mut cy = sy;
801 while cy + 1 < ey {
802 let mut cx = sx;
803 // PORT L1530: walk the current scan row.
804 while cx < ex {
805 // PORT L1533–L1535: pixel pair (top, bottom) at the current column.
806 let mut p1 = (cy * iw + cx) as usize;
807 let mut p2 = ((cy + 1) * iw + cx) as usize;
808 // PORT L1538: first pair matches one or more features?
809 let possible = match_1st_pair(bdata[p1], bdata[p2]);
810 if !possible.is_empty() {
811 // PORT L1540–L1543: bump to the next pixel pair.
812 cx += 1;
813 p1 += 1;
814 p2 += 1;
815 // PORT L1545: still on the scan row?
816 if cx < ex {
817 // PORT L1548: second pair matches?
818 let possible = match_2nd_pair(bdata[p1], bdata[p2], &possible);
819 if !possible.is_empty() {
820 // PORT L1551–L1554: remember x, then skip repeated second pairs.
821 let x2 = cx;
822 skip_repeated_horizontal_pair(&mut cx, ex, &mut p1, &mut p2, bdata);
823 // PORT L1556: still on the scan row?
824 if cx < ex {
825 // PORT L1559: third pair matches a single feature?
826 let possible = match_3rd_pair(bdata[p1], bdata[p2], &possible);
827 if !possible.is_empty() {
828 // PORT L1562–L1573: process the detected minutia.
829 process_horizontal_scan_minutia_v2(
830 minutiae,
831 cx,
832 cy,
833 x2,
834 possible[0],
835 bdata,
836 iw,
837 ih,
838 pdirection_map,
839 plow_flow_map,
840 phigh_curve_map,
841 lfsparms,
842 )?;
843 }
844 // PORT L1578–L1585: if the 3rd pair differs, back up one so it can seed
845 // the next first-pair test.
846 if bdata[p1] != bdata[p2] {
847 cx -= 1;
848 }
849 }
850 }
851 }
852 } else {
853 // PORT L1595–L1597: first pair failed → next column.
854 cx += 1;
855 }
856 }
857 // PORT L1600: next scan row.
858 cy += 1;
859 }
860
861 Ok(())
862}
863
864/// Scan the whole binary image vertically for minutiae — port of stock
865/// `scan4minutiae_vertically_V2` (`minutia.c` L1769).
866///
867/// The vertical analogue of [`scan4minutiae_horizontally_v2`]: walks every adjacent column pair
868/// left-to-right, top-to-bottom, stepping one image row per pixel pair.
869#[expect(clippy::too_many_arguments)]
870fn scan4minutiae_vertically_v2(
871 minutiae: &mut Vec<DetMinutia>,
872 bdata: &mut [u8],
873 iw: i32,
874 ih: i32,
875 pdirection_map: &[i32],
876 plow_flow_map: &[i32],
877 phigh_curve_map: &[i32],
878 lfsparms: &LfsParms,
879) -> Result<(), i32> {
880 // PORT L1781–L1784: scan region is the entire image.
881 let (sx, ex, sy, ey) = (0, iw, 0, ih);
882 let step = iw as usize;
883
884 // PORT L1787–L1863: for each adjacent column pair (left column `cx`, right column `cx+1`).
885 let mut cx = sx;
886 while cx + 1 < ex {
887 let mut cy = sy;
888 // PORT L1792: walk the current scan column.
889 while cy < ey {
890 // PORT L1795–L1797: pixel pair (left, right) at the current row.
891 let mut p1 = (cy * iw + cx) as usize;
892 let mut p2 = p1 + 1;
893 // PORT L1800: first pair matches one or more features?
894 let possible = match_1st_pair(bdata[p1], bdata[p2]);
895 if !possible.is_empty() {
896 // PORT L1802–L1805: bump down one image row to the next pixel pair.
897 cy += 1;
898 p1 += step;
899 p2 += step;
900 // PORT L1807: still on the scan column?
901 if cy < ey {
902 // PORT L1810: second pair matches?
903 let possible = match_2nd_pair(bdata[p1], bdata[p2], &possible);
904 if !possible.is_empty() {
905 // PORT L1813–L1816: remember y, then skip repeated second pairs.
906 let y2 = cy;
907 skip_repeated_vertical_pair(&mut cy, ey, &mut p1, &mut p2, iw, bdata);
908 // PORT L1818: still on the scan column?
909 if cy < ey {
910 // PORT L1821: third pair matches a single feature?
911 let possible = match_3rd_pair(bdata[p1], bdata[p2], &possible);
912 if !possible.is_empty() {
913 // PORT L1824–L1835: process the detected minutia.
914 process_vertical_scan_minutia_v2(
915 minutiae,
916 cx,
917 cy,
918 y2,
919 possible[0],
920 bdata,
921 iw,
922 ih,
923 pdirection_map,
924 plow_flow_map,
925 phigh_curve_map,
926 lfsparms,
927 )?;
928 }
929 // PORT L1840–L1847: if the 3rd pair differs, back up one so it can seed
930 // the next first-pair test.
931 if bdata[p1] != bdata[p2] {
932 cy -= 1;
933 }
934 }
935 }
936 }
937 } else {
938 // PORT L1857–L1859: first pair failed → next row.
939 cy += 1;
940 }
941 }
942 // PORT L1862: next scan column.
943 cx += 1;
944 }
945
946 Ok(())
947}
948
949/// Expand a block map to per-pixel resolution — the stock `pixelize_map` (`maps.c` L724).
950///
951/// Assigns every pixel the value of the block it falls in, so block-map values can be addressed by
952/// pixel coordinate during the scan. It lives with the detection stage (rather than in `maps`)
953/// because detection is its only consumer — `maps` owns block-map *generation*, this owns their
954/// *pixelization*. Recovers the block grid via `block_offsets` (with zero padding, as in the
955/// reference) and requires it to match `mw`×`mh`.
956///
957/// # Errors
958///
959/// `Err(-591)` if the recovered block grid does not match `mw`×`mh`; otherwise propagates the
960/// `block_offsets` error codes.
961pub(crate) fn pixelize_map(
962 iw: i32,
963 ih: i32,
964 imap: &[i32],
965 mw: i32,
966 mh: i32,
967 blocksize: i32,
968) -> Result<Vec<i32>, i32> {
969 // PORT L731–L734: output pixel map, one value per pixel.
970 let mut pmap = vec![0i32; (iw * ih) as usize];
971
972 // PORT L738–L740: recover the (unpadded) block grid.
973 let bo = block_offsets(iw, ih, 0, blocksize)?;
974
975 // PORT L742–L747: the recovered grid must match the map dimensions.
976 if bo.map_w != mw || bo.map_h != mh {
977 return Err(-591);
978 }
979
980 // PORT L749–L758: paint each block's value across its `blocksize`×`blocksize` pixels.
981 for (bi, &val) in imap.iter().enumerate().take((mw * mh) as usize) {
982 for y in 0..blocksize {
983 let start = (bo.offsets[bi] + y * iw) as usize;
984 pmap[start..start + blocksize as usize].fill(val);
985 }
986 }
987
988 // PORT L765: return the pixelized map.
989 Ok(pmap)
990}
991
992/// Scan a binary image for minutiae — the stock `detect_minutiae_V2` (`minutia.c` L283).
993///
994/// Pixelizes the three block maps ([`pixelize_map`]), then scans the image horizontally and then
995/// vertically for the 2×3 feature patterns, collecting every accepted point into the returned list
996/// (points in `LOW FLOW` blocks are recorded with lower reliability). `bdata` is the binary image in
997/// stock convention (`0 == white/valley`, `1 == black/ridge`), `iw`×`ih` pixels; it is `&mut` because
998/// loop-fill can rewrite it mid-scan. `direction_map`, `low_flow_map`, and `high_curve_map` are each
999/// `mw`×`mh` blocks in row-major order.
1000///
1001/// # Errors
1002///
1003/// Propagates the negative stock error codes surfaced by [`pixelize_map`] and the scan routines.
1004#[expect(clippy::too_many_arguments)]
1005pub(crate) fn detect_minutiae_v2(
1006 bdata: &mut [u8],
1007 iw: i32,
1008 ih: i32,
1009 direction_map: &[i32],
1010 low_flow_map: &[i32],
1011 high_curve_map: &[i32],
1012 mw: i32,
1013 mh: i32,
1014 lfsparms: &LfsParms,
1015) -> Result<Vec<DetMinutia>, i32> {
1016 // PORT L292–L308: pixelize the three block maps.
1017 let pdirection_map = pixelize_map(iw, ih, direction_map, mw, mh, lfsparms.blocksize)?;
1018 let plow_flow_map = pixelize_map(iw, ih, low_flow_map, mw, mh, lfsparms.blocksize)?;
1019 let phigh_curve_map = pixelize_map(iw, ih, high_curve_map, mw, mh, lfsparms.blocksize)?;
1020
1021 let mut minutiae = Vec::new();
1022
1023 // PORT L310–L324: horizontal scan first, then vertical.
1024 scan4minutiae_horizontally_v2(
1025 &mut minutiae,
1026 bdata,
1027 iw,
1028 ih,
1029 &pdirection_map,
1030 &plow_flow_map,
1031 &phigh_curve_map,
1032 lfsparms,
1033 )?;
1034 scan4minutiae_vertically_v2(
1035 &mut minutiae,
1036 bdata,
1037 iw,
1038 ih,
1039 &pdirection_map,
1040 &plow_flow_map,
1041 &phigh_curve_map,
1042 lfsparms,
1043 )?;
1044
1045 // PORT L333: raw minutia list (before false-minutia removal).
1046 Ok(minutiae)
1047}