fprint_mindtct/detect/loops.rs
1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Analysis and filling of small ridge/valley loops (lakes and islands) in the binary image —
6//! faithful port of stock NBIS `mindtct/src/lib/mindtct/loop.c` (renamed `loops`, since `loop` is a
7//! Rust keyword).
8//!
9//! A bifurcation that closes a short contour encircles a small feature — a *lake* (an enclosed
10//! valley) or *island* (an enclosed ridge). This module decides which minutiae sit on such loops and
11//! either promotes the loop to a pair of minutiae or erases it from the image:
12//!
13//! * [`on_loop`] traces a minutia's contour clockwise up to a step limit and reports whether it
14//! closed a loop (stock `on_loop`); the false-minutia-removal stages (`remove.rs`) drive it.
15//! * [`is_loop_clockwise`] decides a loop contour's winding via its chain code
16//! ([`chain_code_loop`](super::chaincod::chain_code_loop) +
17//! [`is_chain_clockwise`](super::chaincod::is_chain_clockwise)).
18//! * [`get_loop_aspect`] measures a loop's widest and narrowest span, the shape test that decides
19//! whether it holds minutiae.
20//! * [`process_loop_v2`] turns a qualifying loop into a pair of minutiae, or — failing the shape
21//! test — erases it from the binary image via [`fill_loop`]. [`fill_loop`] and its row helper
22//! [`fill_partial_row`] fill a loop's concave-aware interior using a per-row
23//! [`Shape`](super::shape::Shape) built by [`shape_from_contour`](super::shape::shape_from_contour).
24//!
25//! The loop-determination and fill scan orders are reproduced step-for-step from the reference so the
26//! decisions and image edits are identical. Every routine here is live: [`process_loop_v2`] is wired
27//! into `detect_minutiae_V2` (through `adjust_high_curvature_minutia_V2`), and [`on_loop`] /
28//! [`fill_loop`] into `remove_false_minutia_V2`. See `docs/mindtct-algorithm.md`.
29
30use super::contour::{line2direction, trace_contour, Contour, ScanDir, TraceResult};
31use super::shape::shape_from_contour;
32use super::{
33 create_minutia, is_minutia_appearing, minutia_type, update_minutiae, DetMinutia,
34 HIGH_RELIABILITY, LOOP_ID, MEDIUM_RELIABILITY,
35};
36use crate::params::LfsParms;
37use crate::util::squared_distance;
38
39/// Outcome of [`on_loop`] — the stock `int` return (`IGNORE`/`LOOP_FOUND`/`FALSE`).
40///
41/// The stock `Negative` (system error) return is unreachable here: [`trace_contour`] cannot fail (its
42/// `malloc` paths have no analogue), so this enum is exhaustive over the real outcomes.
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub(crate) enum OnLoop {
45 /// The minutia's contour closed a qualifying loop (stock `LOOP_FOUND`).
46 LoopFound,
47 /// The contour was traced but did not close within the step limit (stock `FALSE`).
48 NotFound,
49 /// The contour could not be traced (stock `IGNORE`); the caller should drop the minutia.
50 Ignore,
51}
52
53/// Determine whether a minutia lies on a loop of at most `max_loop_len` circumference — port of stock
54/// `on_loop` (`loop.c` L192).
55///
56/// Traces the feature's contour clockwise from the minutia point (using the minutia point itself as
57/// the loop-trigger, so a walk back around to the start is detected), for up to `max_loop_len` steps.
58/// A [`TraceResult::Loop`] means the minutia sits on a qualifying loop; a full/short
59/// [`TraceResult::Traced`] means it does not; a [`TraceResult::Ignore`] means the contour could not be
60/// traced. `bdata` is the binary image (`0 == white/valley`, `1 == black/ridge`), `iw`×`ih` pixels.
61pub(crate) fn on_loop(
62 minutia: &DetMinutia,
63 max_loop_len: i32,
64 bdata: &[u8],
65 iw: i32,
66 ih: i32,
67) -> OnLoop {
68 // PORT L200–L204: trace the contour clockwise, with the minutia point as both start and
69 // loop-trigger.
70 match trace_contour(
71 max_loop_len,
72 minutia.x,
73 minutia.y,
74 minutia.x,
75 minutia.y,
76 minutia.ex,
77 minutia.ey,
78 ScanDir::Clockwise,
79 bdata,
80 iw,
81 ih,
82 ) {
83 // PORT L207–L208: trace impossible → IGNORE.
84 TraceResult::Ignore => OnLoop::Ignore,
85 // PORT L211–L214: the trace completed a loop → LOOP_FOUND.
86 TraceResult::Loop(_) => OnLoop::LoopFound,
87 // PORT L218–L221: traced but no loop within the step limit → FALSE.
88 TraceResult::Traced(_) => OnLoop::NotFound,
89 }
90}
91
92/// Decide whether a loop's contour is ordered clockwise — port of stock `is_loop_clockwise`
93/// (`loop.c` L492).
94///
95/// Derives the contour's 8-connected chain code
96/// ([`chain_code_loop`](super::chaincod::chain_code_loop)) and folds its turns into a winding
97/// decision ([`is_chain_clockwise`](super::chaincod::is_chain_clockwise)). When the contour is too
98/// short to produce a chain (three or fewer points, so `chain_code_loop` returns empty), the
99/// direction is indeterminate and the caller-supplied `default_ret` is returned. Returns `1` (`TRUE`,
100/// clockwise), `0` (`FALSE`, counter-clockwise), or `default_ret`.
101pub(crate) fn is_loop_clockwise(contour_x: &[i32], contour_y: &[i32], default_ret: i32) -> i32 {
102 // PORT L499–L500: derive the chain code from the contour points.
103 let chain = super::chaincod::chain_code_loop(contour_x, contour_y);
104
105 // PORT L504–L510: an empty chain means too few points to tell → the default.
106 if chain.is_empty() {
107 return default_ret;
108 }
109
110 // PORT L515: fold the chain's turns into a winding decision (passing `default_ret` on for the
111 // indeterminate net-zero case).
112 super::chaincod::is_chain_clockwise(&chain, default_ret)
113}
114
115/// Measure a loop's widest and narrowest span — port of stock `get_loop_aspect` (`loop.c` L885).
116///
117/// Walks opposite points of the loop (index `i` and its antipode `i + halfway`, wrapping) and
118/// records the squared distance between them, tracking the running minimum and maximum. An even-length
119/// loop only needs half a walk (the second half is exactly redundant); an odd-length loop is walked
120/// in full (its halves differ, and that difference "may" be meaningful — verbatim from the reference).
121///
122/// Returns `(min_fr, min_to, min_dist, max_fr, max_to, max_dist)`: the contour index pairs where the
123/// minimum and maximum spans occur and the corresponding squared distances.
124pub(crate) fn get_loop_aspect(
125 contour_x: &[i32],
126 contour_y: &[i32],
127) -> (i32, i32, f64, i32, i32, f64) {
128 let ncontour = contour_x.len() as i32;
129
130 // PORT L895: half the loop's perimeter.
131 let halfway = ncontour >> 1;
132
133 // PORT L900–L904: seed opposite points at index 0 and its antipode; their squared span.
134 let mut i = 0;
135 let mut j = halfway;
136 let mut dist = squared_distance(
137 contour_x[i as usize],
138 contour_y[i as usize],
139 contour_x[j as usize],
140 contour_y[j as usize],
141 );
142
143 // PORT L907–L912: initialize the running minimum and maximum at that first pair.
144 let mut min_dist = dist;
145 let mut min_i = i;
146 let mut min_j = j;
147 let mut max_dist = dist;
148 let mut max_i = i;
149 let mut max_j = j;
150
151 // PORT L914–L917: advance to the next opposite pair (`j` wraps around the end).
152 i += 1;
153 j += 1;
154 j %= ncontour;
155
156 // PORT L926–L933: odd loop → walk the whole perimeter; even loop → walk only half.
157 let limit = if ncontour % 2 != 0 { ncontour } else { halfway };
158
159 // PORT L936: walk until the perimeter limit.
160 while i < limit {
161 // PORT L937–L939: squared span of the current opposite pair.
162 dist = squared_distance(
163 contour_x[i as usize],
164 contour_y[i as usize],
165 contour_x[j as usize],
166 contour_y[j as usize],
167 );
168 // PORT L941–L945: track the running minimum.
169 if dist < min_dist {
170 min_dist = dist;
171 min_i = i;
172 min_j = j;
173 }
174 // PORT L946–L950: track the running maximum.
175 if dist > max_dist {
176 max_dist = dist;
177 max_i = i;
178 max_j = j;
179 }
180 // PORT L951–L955: advance to the next opposite pair (`j` wraps).
181 i += 1;
182 j += 1;
183 j %= ncontour;
184 }
185
186 // PORT L959–L964: return the min/max index pairs and their squared distances.
187 (min_i, min_j, min_dist, max_i, max_j, max_dist)
188}
189
190/// Process a contour known to form a complete loop — port of stock `process_loop_V2` (`loop.c`
191/// L707).
192///
193/// A sufficiently large, narrow/elongated loop yields two minutiae at the ends of its longest span
194/// (reliability set from the Low Ridge Flow map); otherwise the loop is assumed spurious and erased
195/// from the image via [`fill_loop`].
196///
197/// `contour` is the loop's traced contour; `bdata` is the binary image (`0 == white/valley`,
198/// `1 == black/ridge`), `iw`×`ih` pixels; `plow_flow_map` is the pixelized Low Ridge Flow map.
199///
200/// PORT: the two candidate minutiae are added with stock **version one** of `update_minutiae`
201/// (deliberately, per the reference comment), not the V2 variant the scan drivers use. On IGNORE the
202/// stock frees the rejected minutia; here it is simply dropped.
203///
204/// # Errors
205///
206/// Propagates the negative stock error codes surfaced by the minutia-update and fill routines.
207pub(crate) fn process_loop_v2(
208 minutiae: &mut Vec<DetMinutia>,
209 contour: &Contour,
210 bdata: &mut [u8],
211 iw: i32,
212 ih: i32,
213 plow_flow_map: &[i32],
214 lfsparms: &LfsParms,
215) -> Result<(), i32> {
216 let ncontour = contour.len() as i32;
217
218 // PORT L724–L725: an empty contour has nothing to process.
219 if ncontour <= 0 {
220 return Ok(());
221 }
222
223 // PORT L728: only loops above the minimum perimeter can carry minutiae.
224 if ncontour > lfsparms.min_loop_len {
225 // PORT L730: interior pixel value of the feature (first contour point).
226 let feature_pix = bdata[(contour.y[0] * iw + contour.x[0]) as usize];
227
228 // PORT L736–L738: widest/narrowest spans across the loop.
229 let (_min_fr, _min_to, min_dist, max_fr, max_to, max_dist) =
230 get_loop_aspect(&contour.x, &contour.y);
231
232 // PORT L742–L743: loop must be sufficiently narrow or elongated.
233 if min_dist < lfsparms.min_loop_aspect_dist
234 || (max_dist / min_dist) >= lfsparms.min_loop_aspect_ratio
235 {
236 let max_fr = max_fr as usize;
237 let max_to = max_to as usize;
238
239 // PORT L750–L753: the interior midpoint of the widest span must match the feature.
240 let mid_x = (contour.x[max_fr] + contour.x[max_to]) >> 1;
241 let mid_y = (contour.y[max_fr] + contour.y[max_to]) >> 1;
242 let mid_pix = bdata[(mid_y * iw + mid_x) as usize];
243 if mid_pix == feature_pix {
244 // PORT L758–L840: 1. widest-span endpoint as a candidate minutia.
245 let mut idir = line2direction(
246 contour.x[max_fr],
247 contour.y[max_fr],
248 contour.x[max_to],
249 contour.y[max_to],
250 lfsparms.num_directions,
251 );
252 let kind = minutia_type(feature_pix);
253 let appearing = is_minutia_appearing(
254 contour.x[max_fr],
255 contour.y[max_fr],
256 contour.ex[max_fr],
257 contour.ey[max_fr],
258 )?;
259 let fmapval = plow_flow_map[(contour.y[max_fr] * iw + contour.x[max_fr]) as usize];
260 let reliability = if fmapval != 0 {
261 MEDIUM_RELIABILITY
262 } else {
263 HIGH_RELIABILITY
264 };
265 let minutia = create_minutia(
266 contour.x[max_fr],
267 contour.y[max_fr],
268 contour.ex[max_fr],
269 contour.ey[max_fr],
270 idir,
271 reliability,
272 kind,
273 appearing == 1,
274 LOOP_ID,
275 );
276 // PORT L827: NOTE — deliberately version one of update_minutiae.
277 update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms)?;
278
279 // PORT L845–L848: 2. opposite endpoint, direction flipped 180°.
280 idir += lfsparms.num_directions;
281 idir %= lfsparms.num_directions << 1;
282
283 let appearing = is_minutia_appearing(
284 contour.x[max_to],
285 contour.y[max_to],
286 contour.ex[max_to],
287 contour.ey[max_to],
288 )?;
289 let fmapval = plow_flow_map[(contour.y[max_to] * iw + contour.x[max_to]) as usize];
290 let reliability = if fmapval != 0 {
291 MEDIUM_RELIABILITY
292 } else {
293 HIGH_RELIABILITY
294 };
295 let minutia = create_minutia(
296 contour.x[max_to],
297 contour.y[max_to],
298 contour.ex[max_to],
299 contour.ey[max_to],
300 idir,
301 reliability,
302 kind,
303 appearing == 1,
304 LOOP_ID,
305 );
306 // PORT L889: NOTE — deliberately version one of update_minutiae.
307 update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms)?;
308
309 // PORT L897–L898: loop processed successfully.
310 return Ok(());
311 }
312 }
313 }
314
315 // PORT L905–L909: otherwise the loop is assumed spurious — erase it from the image.
316 fill_loop(contour, bdata, iw, ih)
317}
318
319/// Fill a loop's interior in the binary image, honoring concave shapes — port of stock `fill_loop`
320/// (`loop.c` L991).
321///
322/// Builds a per-row [`Shape`](super::shape::Shape) from the loop's contour and fills each row between
323/// contour points, skipping the gaps that concavities open up so the flood does not escape the loop.
324///
325/// `contour` is the loop's traced contour; `bdata` is the binary image (`0 == white/valley`,
326/// `1 == black/ridge`), `iw`×`ih` pixels.
327///
328/// PORT: stock takes `ih` but the fill is row-addressed and never reads it; it is kept in the
329/// signature for parity with the reference but unused. A malformed (empty) row makes the stock post a
330/// warning and return normally — here it simply returns `Ok(())`.
331///
332/// # Errors
333///
334/// Propagates the negative stock error code surfaced by `shape_from_contour`.
335pub(crate) fn fill_loop(contour: &Contour, bdata: &mut [u8], iw: i32, ih: i32) -> Result<(), i32> {
336 let _ = ih;
337
338 // PORT L1001–L1003: build the per-row shape from the loop's contour.
339 let shape = shape_from_contour(&contour.x, &contour.y)?;
340
341 // PORT L1007–L1015: feature (interior) pixel and its opposite (the edge/fill value).
342 let feature_pix = bdata[(contour.y[0] * iw + contour.x[0]) as usize];
343 let edge_pix: u8 = if feature_pix != 0 { 0 } else { 1 };
344
345 // PORT L1018: foreach row in the shape ...
346 for row in &shape.rows {
347 // PORT L1020: y-coord of the current row.
348 let y = row.y;
349
350 // PORT L1024–L1032: a row is expected to hold at least one contour point; if not, the shape
351 // is malformed — preempt the fill and return normally.
352 if row.xs.is_empty() {
353 return Ok(());
354 }
355
356 // PORT L1035–L1041: fill the left-most contour point on the row.
357 let mut j = 0usize;
358 let mut x = row.xs[0];
359 bdata[(y * iw + x) as usize] = edge_pix;
360 // PORT L1043: index of the last contour point on the row.
361 let lastj = row.xs.len() - 1;
362
363 // PORT L1044: while the last contour point on the row has not been processed ...
364 while j < lastj {
365 // PORT L1055–L1057: pixel just right of the last filled contour point.
366 x += 1;
367 let next_pix = bdata[(y * iw + x) as usize];
368
369 // PORT L1060: if it matches the edge value, assume a concavity and skip to the next point.
370 if next_pix == edge_pix {
371 // PORT L1063–L1067: jump to and fill the next contour point.
372 j += 1;
373 x = row.xs[j];
374 bdata[(y * iw + x) as usize] = edge_pix;
375 } else {
376 // PORT L1074–L1084: fill from the current pixel through the next contour point.
377 j += 1;
378 let nx = row.xs[j];
379 fill_partial_row(edge_pix, x, nx, y, bdata, iw);
380 }
381 }
382 }
383
384 // PORT L1112: return normally.
385 Ok(())
386}
387
388/// Fill a contiguous range of pixels on one image row with a value — port of stock `fill_partial_row`
389/// (`loop.c` L1116).
390///
391/// Sets every pixel from `frx` to `tox` (inclusive) on row `y` to `fill_pix`. The coordinates are
392/// assumed within the image bounds (the caller guarantees this).
393///
394/// PORT: stock takes `ih` but never reads it, so it is dropped here (mirroring `fix_edge_pixel_pair`).
395/// `fill_pix` is a stock `int` on `[0..255]` but only ever a binary `0`/`1` from the loop routines, so
396/// it is a `u8` here.
397pub(crate) fn fill_partial_row(
398 fill_pix: u8,
399 frx: i32,
400 tox: i32,
401 y: i32,
402 bdata: &mut [u8],
403 iw: i32,
404) {
405 // PORT L1127–L1132: fill from `frx` through `tox` inclusive, left to right.
406 let mut x = frx;
407 while x <= tox {
408 bdata[(y * iw + x) as usize] = fill_pix;
409 x += 1;
410 }
411}
412
413#[cfg(test)]
414mod tests {
415 use super::super::BIFURCATION;
416 use super::*;
417
418 /// A 5×5 image whose bottom three rows (`y >= 2`) are ridge (`1`) — a straight horizontal feature
419 /// edge along `y == 2`.
420 fn half_plane() -> (Vec<u8>, i32, i32) {
421 let iw = 5;
422 let ih = 5;
423 let mut b = vec![0u8; (iw * ih) as usize];
424 for y in 2..ih {
425 for x in 0..iw {
426 b[(y * iw + x) as usize] = 1;
427 }
428 }
429 (b, iw, ih)
430 }
431
432 /// A 5×5 image with a solid 3×3 ridge block at `x,y ∈ [1,3]` — a closed feature whose interior
433 /// edge is an eight-pixel loop.
434 fn block_3x3() -> (Vec<u8>, i32, i32) {
435 let iw = 5;
436 let ih = 5;
437 let mut b = vec![0u8; (iw * ih) as usize];
438 for y in 1..=3 {
439 for x in 1..=3 {
440 b[(y * iw + x) as usize] = 1;
441 }
442 }
443 (b, iw, ih)
444 }
445
446 /// Construct a minutia with the given position/edge/type; the remaining fields are irrelevant to
447 /// the loop routines and set to inert defaults.
448 fn minutia(x: i32, y: i32, ex: i32, ey: i32, kind: i32) -> DetMinutia {
449 DetMinutia {
450 x,
451 y,
452 ex,
453 ey,
454 direction: 0,
455 reliability: 0.0,
456 kind,
457 appearing: true,
458 feature_id: 0,
459 nbrs: Vec::new(),
460 ridge_counts: Vec::new(),
461 }
462 }
463
464 #[test]
465 fn on_loop_detects_a_loop() {
466 let (b, iw, ih) = block_3x3();
467 // Top-left interior ridge (1,1) with its north valley edge (1,0): the contour walks clockwise
468 // back around to (1,1) → a loop.
469 let m = minutia(1, 1, 1, 0, BIFURCATION);
470 assert_eq!(on_loop(&m, 20, &b, iw, ih), OnLoop::LoopFound);
471 }
472
473 #[test]
474 fn on_loop_traces_without_a_loop() {
475 let (b, iw, ih) = half_plane();
476 // Feature (2,2)/edge (2,1) on a straight edge: the trace runs off the image before closing.
477 let m = minutia(2, 2, 2, 1, BIFURCATION);
478 assert_eq!(on_loop(&m, 4, &b, iw, ih), OnLoop::NotFound);
479 }
480
481 #[test]
482 fn on_loop_ignores_a_same_colored_pair() {
483 let (b, iw, ih) = block_3x3();
484 // Both (2,2) and (2,3) are ridge → not opposite colors → the contour can't be traced.
485 let m = minutia(2, 2, 2, 3, BIFURCATION);
486 assert_eq!(on_loop(&m, 20, &b, iw, ih), OnLoop::Ignore);
487 }
488
489 // A 2×2 pixel square walked clockwise on screen (image coords, `y` down).
490 const SQUARE_X: [i32; 8] = [0, 1, 2, 2, 2, 1, 0, 0];
491 const SQUARE_Y: [i32; 8] = [0, 0, 0, 1, 2, 2, 2, 1];
492
493 #[test]
494 fn is_loop_clockwise_reports_winding() {
495 // The screen-clockwise square is clockwise (TRUE == 1).
496 assert_eq!(is_loop_clockwise(&SQUARE_X, &SQUARE_Y, -1), 1);
497 // Reversed → counter-clockwise (FALSE == 0).
498 let mut rx = SQUARE_X;
499 let mut ry = SQUARE_Y;
500 rx.reverse();
501 ry.reverse();
502 assert_eq!(is_loop_clockwise(&rx, &ry, -1), 0);
503 }
504
505 #[test]
506 fn is_loop_clockwise_returns_default_for_short_contours() {
507 // Three or fewer points → no chain → the caller's default.
508 assert_eq!(is_loop_clockwise(&[0, 1, 2], &[0, 0, 0], 42), 42);
509 }
510
511 #[test]
512 fn get_loop_aspect_finds_min_and_max_spans() {
513 // Even-length loop (8): walk only the first half. Hand-traced against loop.c:
514 // i=0,j=4: (0,0)-(2,2) = 8 (seed → both min and max)
515 // i=1,j=5: (1,0)-(1,2) = 4 (new min)
516 // i=2,j=6: (2,0)-(0,2) = 8 (ties max, not > → no update)
517 // i=3,j=7: (2,1)-(0,1) = 4 (ties min, not < → no update)
518 let (min_fr, min_to, min_dist, max_fr, max_to, max_dist) =
519 get_loop_aspect(&SQUARE_X, &SQUARE_Y);
520 assert_eq!((min_fr, min_to, min_dist), (1, 5, 4.0));
521 assert_eq!((max_fr, max_to, max_dist), (0, 4, 8.0));
522 }
523
524 #[test]
525 fn fill_partial_row_fills_inclusive_range() {
526 let iw = 5;
527 let mut b = vec![0u8; (iw * 2) as usize];
528 fill_partial_row(1, 1, 3, 0, &mut b, iw);
529 // Row 0 filled from x=1..=3; row 1 untouched.
530 assert_eq!(&b[0..5], &[0, 1, 1, 1, 0]);
531 assert_eq!(&b[5..10], &[0, 0, 0, 0, 0]);
532 }
533}