Skip to main content

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}