NCC Matching for Tiny Elan SPI Laptop Sensors for Linux libfprint

libfprint_elan_ncc.patch

# NCC patch-consensus matcher for Elan SPI fingerprint sensor
#
# These sensors have a tiny capture area, so the stock Bozorth3
# minutiae matcher can't find enough minutiae pairs and mostly
# fails to match. This patch:
#
#  - switches capture from swipe to press mode (full-height single
#    frame instead of stitched swipe strips)
#  - stores the raw enrolled images on FpPrint, not just minutiae
#  - adds an NCC (normalized cross-correlation) patch-consensus
#    matcher: aligns template/probe images globally, then checks
#    that many overlapping small patches agree on a consistent
#    local displacement (real prints deform smoothly; impostors
#    don't line up consistently)
#  - falls back to the original Bozorth3 match if NCC doesn't find
#    a confident match
diff --git a/libfprint/drivers/elanspi.c b/libfprint/drivers/elanspi.c
index c2e3cbc..28aec63 100644
--- a/libfprint/drivers/elanspi.c
+++ b/libfprint/drivers/elanspi.c
@@ -401,12 +401,20 @@ elanspi_determine_sensor (FpiDeviceElanSpi *self, GError **err)
   if (fpi_device_get_driver_data (FP_DEVICE (self)) & ELANSPI_HV_FLIPPED)
     {
       self->frame_width = self->sensor_height;
-      self->frame_height = self->sensor_width > ELANSPI_MAX_FRAME_HEIGHT ? ELANSPI_MAX_FRAME_HEIGHT : self->sensor_width;
+      /* In press mode capture the full sensor height; swipe mode caps the
+       * strip height so the movement-estimation stitcher has enough overlap. */
+      if (fp_device_get_scan_type (FP_DEVICE (self)) == FP_SCAN_TYPE_PRESS)
+        self->frame_height = self->sensor_width;
+      else
+        self->frame_height = self->sensor_width > ELANSPI_MAX_FRAME_HEIGHT ? ELANSPI_MAX_FRAME_HEIGHT : self->sensor_width;
     }
   else
     {
       self->frame_width = self->sensor_width;
-      self->frame_height = self->sensor_height > ELANSPI_MAX_FRAME_HEIGHT ? ELANSPI_MAX_FRAME_HEIGHT : self->sensor_height;
+      if (fp_device_get_scan_type (FP_DEVICE (self)) == FP_SCAN_TYPE_PRESS)
+        self->frame_height = self->sensor_height;
+      else
+        self->frame_height = self->sensor_height > ELANSPI_MAX_FRAME_HEIGHT ? ELANSPI_MAX_FRAME_HEIGHT : self->sensor_height;
     }
 }
 
@@ -1336,7 +1344,7 @@ elanspi_fp_frame_stitch_and_submit (FpiDeviceElanSpi *self)
   g_autoptr(FpImage) img = NULL;
   g_autoptr(FpImage) scaled = NULL;
   struct fpi_frame_asmbl_ctx assembling_ctx = {
-    .image_width = (self->frame_width * 3) / 2,
+    .image_width = self->frame_width,
 
     .frame_width = self->frame_width,
     .frame_height = self->frame_height,
@@ -1699,10 +1707,10 @@ fpi_device_elanspi_class_init (FpiDeviceElanSpiClass *klass)
   dev_class->full_name = "ElanTech Embedded Fingerprint Sensor";
   dev_class->type = FP_DEVICE_TYPE_UDEV;
   dev_class->id_table = elanspi_id_table;
-  dev_class->scan_type = FP_SCAN_TYPE_SWIPE;
-  dev_class->nr_enroll_stages = 7;       /* these sensors are very hit or miss, may as well record a few extras */
+  dev_class->scan_type = FP_SCAN_TYPE_PRESS;
+  dev_class->nr_enroll_stages = 18;
 
-  img_class->bz3_threshold = 24;
+  img_class->bz3_threshold = 12;
   img_class->img_open = elanspi_open;
   img_class->activate = elanspi_activate;
   img_class->deactivate = elanspi_deactivate;
diff --git a/libfprint/drivers/elanspi.h b/libfprint/drivers/elanspi.h
index 688f477..0eb4da0 100644
--- a/libfprint/drivers/elanspi.h
+++ b/libfprint/drivers/elanspi.h
@@ -369,9 +369,9 @@ static const FpIdEntry elanspi_id_table[] = {
 
 #define ELANSPI_MIN_FRAMES_DEBOUNCE 2
 
-#define ELANSPI_SWIPE_FRAMES_DISCARD 1
-#define ELANSPI_MIN_FRAMES_SWIPE (7 + ELANSPI_SWIPE_FRAMES_DISCARD)
-#define ELANSPI_MAX_FRAMES_SWIPE (20 + ELANSPI_SWIPE_FRAMES_DISCARD)
+#define ELANSPI_SWIPE_FRAMES_DISCARD 0
+#define ELANSPI_MIN_FRAMES_SWIPE 1
+#define ELANSPI_MAX_FRAMES_SWIPE 1
 
 #define ELANSPI_MAX_FRAME_HEIGHT 43
 #define ELANSPI_MIN_FRAME_TO_FRAME_DIFF (250 * 250)
diff --git a/libfprint/fp-print-private.h b/libfprint/fp-print-private.h
index 6d44700..2e3d0b7 100644
--- a/libfprint/fp-print-private.h
+++ b/libfprint/fp-print-private.h
@@ -43,4 +43,5 @@ struct _FpPrint
 
   GVariant  *data;
   GPtrArray *prints;
+  GPtrArray *images;
 };
diff --git a/libfprint/fp-print.c b/libfprint/fp-print.c
index 6953fd9..7048c9b 100644
--- a/libfprint/fp-print.c
+++ b/libfprint/fp-print.c
@@ -80,6 +80,7 @@ fp_print_finalize (GObject *object)
   g_clear_pointer (&self->enroll_date, g_date_free);
   g_clear_pointer (&self->data, g_variant_unref);
   g_clear_pointer (&self->prints, g_ptr_array_unref);
+  g_clear_pointer (&self->images, g_ptr_array_unref);
 
   G_OBJECT_CLASS (fp_print_parent_class)->finalize (object);
 }
@@ -328,6 +329,7 @@ fp_print_class_init (FpPrintClass *klass)
 static void
 fp_print_init (FpPrint *self)
 {
+  self->images = g_ptr_array_new_with_free_func (g_object_unref);
 }
 
 /**
@@ -677,6 +679,18 @@ fp_print_serialize (FpPrint *print,
 
   /* Unused a{sv} for expansion */
   g_variant_builder_open (&builder, G_VARIANT_TYPE_VARDICT);
+  if (print->images && print->images->len > 0)
+    {
+      GVariantBuilder img_array;
+      g_variant_builder_init (&img_array, G_VARIANT_TYPE ("a(uuudv)"));
+      for (guint i = 0; i < print->images->len; i++)
+        {
+          FpImage *img = g_ptr_array_index (print->images, i);
+          GVariant *data_var = g_variant_new_fixed_array (G_VARIANT_TYPE_BYTE, img->data, img->width * img->height, 1);
+          g_variant_builder_add (&img_array, "(uuudv)", img->width, img->height, img->flags, img->ppmm, g_variant_new_variant (data_var));
+        }
+      g_variant_builder_add (&builder, "{sv}", "images", g_variant_builder_end (&img_array));
+    }
   g_variant_builder_close (&builder);
 
   /* Insert NBIS print data for type NBIS, otherwise the GVariant directly */
@@ -774,6 +788,7 @@ fp_print_deserialize (const guchar *data,
   const gchar *driver;
   const gchar *device_id;
   gboolean device_stored;
+  GVariant *metadata = NULL;
 
   g_assert (data);
   g_assert (length > 3);
@@ -810,7 +825,7 @@ fp_print_deserialize (const guchar *data,
                  &username,
                  &description,
                  &julian_date,
-                 NULL,
+                 &metadata,
                  &print_data);
 
   finger = finger_int8;
@@ -893,6 +908,36 @@ fp_print_deserialize (const guchar *data,
       }
     }
 
+  if (metadata)
+    {
+      GVariant *images_var = g_variant_lookup_value (metadata, "images", G_VARIANT_TYPE ("a(uuudv)"));
+      if (images_var)
+        {
+          GVariantIter iter;
+          g_variant_iter_init (&iter, images_var);
+          guint width, height, flags;
+          gdouble ppmm;
+          GVariant *data_var_wrapped = NULL;
+          while (g_variant_iter_loop (&iter, "(uuudv)", &width, &height, &flags, &ppmm, &data_var_wrapped))
+            {
+              GVariant *data_var = g_variant_get_variant (data_var_wrapped);
+              gsize data_len;
+              const guchar *data_bytes = g_variant_get_fixed_array (data_var, &data_len, 1);
+              if (data_len == width * height)
+                {
+                  FpImage *img = fp_image_new (width, height);
+                  img->flags = flags;
+                  img->ppmm = ppmm;
+                  memcpy (img->data, data_bytes, data_len);
+                  g_ptr_array_add (result->images, img);
+                }
+              g_variant_unref (data_var);
+            }
+          g_variant_unref (images_var);
+        }
+      g_clear_pointer (&metadata, g_variant_unref);
+    }
+
   date = g_date_new_julian (julian_date);
   g_object_set (result,
                 "finger", finger,
@@ -904,6 +949,7 @@ fp_print_deserialize (const guchar *data,
   return g_steal_pointer (&result);
 
 invalid_format:
+  g_clear_pointer (&metadata, g_variant_unref);
   g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_DATA,
                "Data could not be parsed");
   return NULL;
diff --git a/libfprint/fpi-print.c b/libfprint/fpi-print.c
index b0f5eab..807b07d 100644
--- a/libfprint/fpi-print.c
+++ b/libfprint/fpi-print.c
@@ -22,6 +22,7 @@
 #include "fpi-log.h"
 
 #include "fp-print-private.h"
+#include <math.h>
 #include "fpi-device.h"
 #include "fpi-compat.h"
 
@@ -51,6 +52,15 @@ fpi_print_add_print (FpPrint *print, FpPrint *add)
 
   g_assert (add->prints->len == 1);
   g_ptr_array_add (print->prints, g_memdup2 (add->prints->pdata[0], sizeof (struct xyt_struct)));
+
+  if (add->images && add->images->len > 0)
+    {
+      for (guint i = 0; i < add->images->len; i++)
+        {
+          FpImage *img = g_ptr_array_index (add->images, i);
+          g_ptr_array_add (print->images, g_object_ref (img));
+        }
+    }
 }
 
 /**
@@ -189,6 +199,7 @@ fpi_print_add_from_image (FpPrint *print,
 
   g_clear_object (&print->image);
   print->image = g_object_ref (image);
+  g_ptr_array_add (print->images, g_object_ref (image));
   g_object_notify (G_OBJECT (print), "image");
 
   return TRUE;
@@ -209,6 +220,564 @@ fpi_print_add_from_image (FpPrint *print,
  *
  * Returns: Whether the prints match, @error will be set if #FPI_MATCH_ERROR is returned
  */
+/* Local-mean box-blur radius for high-pass preprocessing (pixels).
+ * The blur window (2*radius+1)^2 must span several ridge periods so the
+ * local mean tracks the pressure/brightness background only and not ridge
+ * structure.  Ridge period at 2× scale is ~10–15 px, so radius 20 gives
+ * a 41×41 window (~3 ridge periods) which reliably separates background
+ * from texture without removing ridge signal. */
+#define NCC_BLUR_RADIUS       20
+
+/* ---- Stage 1: global rigid alignment (anchor only, not the decision) ---- */
+#define NCC_RANGE             40   /* ± pixels to search translation */
+#define NCC_COARSE_STEP        4   /* coarse grid step; refined to 1 px after */
+#define NCC_REFINE_RANGE       3   /* ± pixels of step-1 refinement around peak */
+#define NCC_ANGLE_REFINE       0.07853982 /* 4.5° — half the coarse angle step */
+#define NCC_MIN_OVERLAP     3000   /* min overlap (px) for a global candidate */
+/* Global NCC below this means no plausible overlap at all; skip the patch
+ * stage for this pair.  Deliberately low — it only prunes hopeless pairs. */
+#define NCC_GLOBAL_GATE       0.20
+
+/* ---- Stage 2: patch consensus (the actual match decision) ----
+ * The probe is tiled into patches; each patch independently finds its best
+ * alignment in the template near its globally-predicted position.  Genuine
+ * matches produce many high-scoring patches whose residual displacements
+ * agree (skin distortion is smooth); impostors produce a few flukes at
+ * random displacements.  Tune via the logged "NCC patch match:" lines:
+ * genuine attempts should show a high consistent/valid fraction. */
+#define NCC_PATCH_SIZE        32   /* patch side (px); ~2–3 ridge periods */
+#define NCC_PATCH_STRIDE      24   /* patch grid stride (overlapping tiles) */
+#define NCC_PATCH_SLACK       12   /* ± px local search around predicted pos */
+#define NCC_PATCH_MIN_VAR   64.0   /* high-pass variance floor: skips flat
+                                    * background and rotation-fill regions */
+#define NCC_PATCH_THRESHOLD 0.60   /* per-patch NCC to count as a candidate */
+#define NCC_CONSIST_TOL        6   /* ± px from median residual = consistent */
+#define NCC_MIN_VALID_PATCHES  8   /* overlap too small to judge below this */
+#define NCC_MIN_VOTES          6   /* consistent patches required to match */
+#define NCC_VOTE_FRACTION   0.40   /* consistent / valid fraction required */
+
+/* Compute a locally-normalised (high-pass) version of src using a box-blur
+ * local mean.  Output is signed (original − local_mean) so that a flat
+ * region maps to ~0 rather than some ambient brightness value.  Caller owns
+ * the returned buffer. */
+static gint16 *
+ncc_highpass (const guint8 *src, guint w, guint h, guint radius)
+{
+  guint n = w * h;
+  g_autofree float *blur_h = g_new (float, n);
+  g_autofree float *blur   = g_new (float, n);
+  gint16 *out = g_new (gint16, n);
+
+  /* Horizontal prefix-sum pass */
+  g_autofree float *hpfx = g_new (float, w + 1);
+  for (guint y = 0; y < h; y++)
+    {
+      hpfx[0] = 0.0f;
+      for (guint x = 0; x < w; x++)
+        hpfx[x + 1] = hpfx[x] + (float) src[y * w + x];
+      for (guint x = 0; x < w; x++)
+        {
+          guint lo = (x >= radius) ? x - radius : 0;
+          guint hi = MIN (x + radius, w - 1);
+          blur_h[y * w + x] = (hpfx[hi + 1] - hpfx[lo]) / (float) (hi - lo + 1);
+        }
+    }
+
+  /* Vertical prefix-sum pass over blur_h */
+  g_autofree float *vpfx = g_new (float, h + 1);
+  for (guint x = 0; x < w; x++)
+    {
+      vpfx[0] = 0.0f;
+      for (guint y = 0; y < h; y++)
+        vpfx[y + 1] = vpfx[y] + blur_h[y * w + x];
+      for (guint y = 0; y < h; y++)
+        {
+          guint lo = (y >= radius) ? y - radius : 0;
+          guint hi = MIN (y + radius, h - 1);
+          blur[y * w + x] = (vpfx[hi + 1] - vpfx[lo]) / (float) (hi - lo + 1);
+        }
+    }
+
+  /* Subtract local mean; clamp to [-255, 255] */
+  for (guint i = 0; i < n; i++)
+    out[i] = (gint16) CLAMP ((int) src[i] - (int) roundf (blur[i]), -255, 255);
+
+  return out;
+}
+
+/* Rotate a high-pass (gint16) image by angle_rad around its center.
+ * Out-of-bounds pixels are filled with 0 (the neutral high-pass value). */
+static void
+ncc_rotate_hp (const gint16 *src, guint sw, guint sh,
+               gint16 *dst, double angle_rad)
+{
+  double cos_a = cos (angle_rad);
+  double sin_a = sin (angle_rad);
+  double cx = sw / 2.0;
+  double cy = sh / 2.0;
+
+  for (guint y = 0; y < sh; y++)
+    {
+      for (guint x = 0; x < sw; x++)
+        {
+          double rot_x = x - cx;
+          double rot_y = y - cy;
+          double sx = rot_x * cos_a + rot_y * sin_a + cx;
+          double sy = -rot_x * sin_a + rot_y * cos_a + cy;
+
+          int src_x = (int) round (sx);
+          int src_y = (int) round (sy);
+
+          if (src_x >= 0 && src_x < (int) sw && src_y >= 0 && src_y < (int) sh)
+            dst[y * sw + x] = src[src_y * sw + src_x];
+          else
+            dst[y * sw + x] = 0;
+        }
+    }
+}
+
+/* NCC score of high-pass template t vs probe p shifted by (dx, dy) */
+static gdouble
+ncc_score_at (const gint16 *t, guint tw, guint th,
+              const gint16 *p, guint pw, guint ph,
+              int dx, int dy, int min_overlap)
+{
+  int sx = MAX (0, dx), sy = MAX (0, dy);
+  int ex = MIN ((int) tw, (int) pw + dx);
+  int eye = MIN ((int) th, (int) ph + dy);
+  if (ex <= sx || eye <= sy) return 0.0;
+
+  int area = (ex - sx) * (eye - sy);
+  if (area < min_overlap) return 0.0;
+
+  gint64 sum_t = 0, sum_p = 0;
+  gint64 sum_tt = 0, sum_pp = 0, sum_tp = 0;
+
+  for (int y = sy; y < eye; y++)
+    {
+      guint t_row_offset = y * tw;
+      guint p_row_offset = (y - dy) * pw;
+      for (int x = sx; x < ex; x++)
+        {
+          gint64 vt = t[t_row_offset + x];
+          gint64 vp = p[p_row_offset + (x - dx)];
+          sum_t  += vt;
+          sum_p  += vp;
+          sum_tt += vt * vt;
+          sum_pp += vp * vp;
+          sum_tp += vt * vp;
+        }
+    }
+
+  double d_sum_t = sum_t;
+  double d_sum_p = sum_p;
+  double num = (double) area * (double) sum_tp - d_sum_t * d_sum_p;
+  double den_t = (double) area * (double) sum_tt - d_sum_t * d_sum_t;
+  double den_p = (double) area * (double) sum_pp - d_sum_p * d_sum_p;
+
+  if (den_t <= 1e-10 || den_p <= 1e-10) return 0.0;
+  return num / sqrt (den_t * den_p);
+}
+
+/* Median of a small int array; sorts in place (insertion sort) */
+static gint
+ncc_median_int (gint *vals, guint n)
+{
+  for (guint i = 1; i < n; i++)
+    {
+      gint v = vals[i];
+      guint j = i;
+      while (j > 0 && vals[j - 1] > v)
+        {
+          vals[j] = vals[j - 1];
+          j--;
+        }
+      vals[j] = v;
+    }
+  return vals[n / 2];
+}
+
+/* Stage 2: tile the (rotated) probe into patches, find each patch's best
+ * local alignment in the template near its position predicted by the global
+ * transform (dx, dy), then count how many high-scoring patches agree on
+ * their residual displacement.  Each patch aligning independently is what
+ * absorbs elastic skin distortion; the consistency vote is what rejects
+ * impostor flukes (which land at random displacements). */
+static void
+ncc_patch_consensus (const gint16 *t, guint tw, guint th,
+                     const gint16 *p, guint pw, guint ph,
+                     int dx, int dy,
+                     volatile gint *found,
+                     guint *votes_out, guint *valid_out)
+{
+  const double n_px = (double) (NCC_PATCH_SIZE * NCC_PATCH_SIZE);
+  guint max_patches = ((ph / NCC_PATCH_STRIDE) + 1) * ((pw / NCC_PATCH_STRIDE) + 1);
+
+  g_autofree gint *res_dx = g_new (gint, max_patches);
+  g_autofree gint *res_dy = g_new (gint, max_patches);
+  guint n_accept = 0, n_valid = 0;
+
+  *votes_out = 0;
+  *valid_out = 0;
+
+  for (guint py = 0; py + NCC_PATCH_SIZE <= ph; py += NCC_PATCH_STRIDE)
+    {
+      for (guint px = 0; px + NCC_PATCH_SIZE <= pw; px += NCC_PATCH_STRIDE)
+        {
+          if (g_atomic_int_get (found))
+            return;
+
+          /* Patch sums; variance floor skips background / rotation fill */
+          gint64 sum_p = 0, sum_pp = 0;
+          for (guint y = 0; y < NCC_PATCH_SIZE; y++)
+            {
+              const gint16 *prow = p + (py + y) * pw + px;
+              for (guint x = 0; x < NCC_PATCH_SIZE; x++)
+                {
+                  gint64 v = prow[x];
+                  sum_p += v;
+                  sum_pp += v * v;
+                }
+            }
+          double var = (sum_pp - (double) sum_p * sum_p / n_px) / n_px;
+          if (var < NCC_PATCH_MIN_VAR)
+            continue;
+
+          gint tx_pred = (gint) px + dx;
+          gint ty_pred = (gint) py + dy;
+
+          gdouble  best = 0.0;
+          gint     best_ddx = 0, best_ddy = 0;
+          gboolean in_overlap = FALSE;
+
+          for (gint ddy = -NCC_PATCH_SLACK; ddy <= NCC_PATCH_SLACK; ddy++)
+            {
+              gint ty0 = ty_pred + ddy;
+              if (ty0 < 0 || ty0 + (gint) NCC_PATCH_SIZE > (gint) th)
+                continue;
+              for (gint ddx = -NCC_PATCH_SLACK; ddx <= NCC_PATCH_SLACK; ddx++)
+                {
+                  gint tx0 = tx_pred + ddx;
+                  if (tx0 < 0 || tx0 + (gint) NCC_PATCH_SIZE > (gint) tw)
+                    continue;
+                  in_overlap = TRUE;
+
+                  gint64 sum_t = 0, sum_tt = 0, sum_tp = 0;
+                  for (guint y = 0; y < NCC_PATCH_SIZE; y++)
+                    {
+                      const gint16 *trow = t + (ty0 + y) * tw + tx0;
+                      const gint16 *prow = p + (py + y) * pw + px;
+                      for (guint x = 0; x < NCC_PATCH_SIZE; x++)
+                        {
+                          gint64 vt = trow[x];
+                          sum_t += vt;
+                          sum_tt += vt * vt;
+                          sum_tp += vt * (gint64) prow[x];
+                        }
+                    }
+
+                  double num = n_px * sum_tp - (double) sum_t * sum_p;
+                  double den_t = n_px * sum_tt - (double) sum_t * sum_t;
+                  double den_p = n_px * sum_pp - (double) sum_p * sum_p;
+                  if (den_t <= 1e-10 || den_p <= 1e-10)
+                    continue;
+                  double ncc_sc = num / sqrt (den_t * den_p);
+                  if (ncc_sc > best)
+                    {
+                      best = ncc_sc;
+                      best_ddx = ddx;
+                      best_ddy = ddy;
+                    }
+                }
+            }
+
+          if (!in_overlap)
+            continue;           /* patch falls outside the overlap region */
+          n_valid++;
+          if (best >= NCC_PATCH_THRESHOLD)
+            {
+              res_dx[n_accept] = best_ddx;
+              res_dy[n_accept] = best_ddy;
+              n_accept++;
+            }
+        }
+    }
+
+  guint votes = 0;
+  if (n_accept > 0)
+    {
+      g_autofree gint *tmp_dx = g_memdup2 (res_dx, n_accept * sizeof (gint));
+      g_autofree gint *tmp_dy = g_memdup2 (res_dy, n_accept * sizeof (gint));
+      gint med_dx = ncc_median_int (tmp_dx, n_accept);
+      gint med_dy = ncc_median_int (tmp_dy, n_accept);
+
+      for (guint i = 0; i < n_accept; i++)
+        if (ABS (res_dx[i] - med_dx) <= NCC_CONSIST_TOL &&
+            ABS (res_dy[i] - med_dy) <= NCC_CONSIST_TOL)
+          votes++;
+    }
+
+  *votes_out = votes;
+  *valid_out = n_valid;
+}
+
+/* Per-thread work item for a single (template image, probe image) pair */
+typedef struct
+{
+  /* template high-pass image */
+  const gint16 *t;
+  guint         t_w, t_h;
+  /* probe: unrotated high-pass image + shared coarse rotations of it */
+  const gint16        *p_orig;
+  const gint16 *const *p_rot;    /* one per angle, same dims as p_orig */
+  const double        *angles;
+  guint                n_angles;
+  guint                p_w, p_h;
+  /* results */
+  gdouble        global_score;
+  guint          votes, valid;
+  gboolean       matched;
+  volatile gint *found;
+} NccPairWork;
+
+static void
+ncc_pair_thread_func (gpointer data, gpointer user_data G_GNUC_UNUSED)
+{
+  NccPairWork *w = data;
+  gdouble best_score = 0.0;
+  guint   best_a = 0;
+  int     best_dx = 0, best_dy = 0;
+
+  w->matched = FALSE;
+  w->global_score = 0.0;
+  w->votes = 0;
+  w->valid = 0;
+
+  if (g_atomic_int_get (w->found))
+    return;
+
+  /* ---- Stage 1a: coarse global alignment over angle × translation ---- */
+  for (guint a = 0; a < w->n_angles; a++)
+    {
+      const gint16 *p = w->p_rot[a];
+      for (int dy = -NCC_RANGE; dy <= NCC_RANGE; dy += NCC_COARSE_STEP)
+        {
+          if (g_atomic_int_get (w->found))
+            return;
+          for (int dx = -NCC_RANGE; dx <= NCC_RANGE; dx += NCC_COARSE_STEP)
+            {
+              gdouble ncc_sc = ncc_score_at (w->t, w->t_w, w->t_h,
+                                             p, w->p_w, w->p_h,
+                                             dx, dy, NCC_MIN_OVERLAP);
+              if (ncc_sc > best_score)
+                {
+                  best_score = ncc_sc;
+                  best_a = a;
+                  best_dx = dx;
+                  best_dy = dy;
+                }
+            }
+        }
+    }
+
+  const gint16 *best_p = w->p_rot[best_a];
+
+  /* ---- Stage 1b: translation refinement at 1 px around the peak ---- */
+  {
+    int cdx = best_dx, cdy = best_dy;
+    for (int dy = cdy - NCC_REFINE_RANGE; dy <= cdy + NCC_REFINE_RANGE; dy++)
+      for (int dx = cdx - NCC_REFINE_RANGE; dx <= cdx + NCC_REFINE_RANGE; dx++)
+        {
+          gdouble ncc_sc = ncc_score_at (w->t, w->t_w, w->t_h,
+                                         best_p, w->p_w, w->p_h,
+                                         dx, dy, NCC_MIN_OVERLAP);
+          if (ncc_sc > best_score)
+            {
+              best_score = ncc_sc;
+              best_dx = dx;
+              best_dy = dy;
+            }
+        }
+  }
+
+  /* ---- Stage 1c: rotation refinement at ±half the coarse angle step.
+   * Residual rotation after this is ≤2.25°, which shifts pixels within a
+   * 32 px patch by well under a pixel — the patch stage absorbs the rest. */
+  {
+    guint n = w->p_w * w->p_h;
+    g_autofree gint16 *rot_scratch_a = g_new (gint16, n);
+    g_autofree gint16 *rot_scratch_b = g_new (gint16, n);
+    gint16 *scratch[2] = { rot_scratch_a, rot_scratch_b };
+    const double deltas[2] = { -NCC_ANGLE_REFINE, NCC_ANGLE_REFINE };
+    int cdx = best_dx, cdy = best_dy;
+
+    for (guint r = 0; r < 2; r++)
+      {
+        if (g_atomic_int_get (w->found))
+          return;
+        ncc_rotate_hp (w->p_orig, w->p_w, w->p_h, scratch[r],
+                       w->angles[best_a] + deltas[r]);
+        for (int dy = cdy - NCC_REFINE_RANGE; dy <= cdy + NCC_REFINE_RANGE; dy++)
+          for (int dx = cdx - NCC_REFINE_RANGE; dx <= cdx + NCC_REFINE_RANGE; dx++)
+            {
+              gdouble ncc_sc = ncc_score_at (w->t, w->t_w, w->t_h,
+                                             scratch[r], w->p_w, w->p_h,
+                                             dx, dy, NCC_MIN_OVERLAP);
+              if (ncc_sc > best_score)
+                {
+                  best_score = ncc_sc;
+                  best_dx = dx;
+                  best_dy = dy;
+                  best_p = scratch[r];
+                }
+            }
+      }
+
+    w->global_score = best_score;
+    if (best_score < NCC_GLOBAL_GATE)
+      return;
+
+    /* ---- Stage 2: patch consensus (the decision) ---- */
+    ncc_patch_consensus (w->t, w->t_w, w->t_h,
+                         best_p, w->p_w, w->p_h,
+                         best_dx, best_dy,
+                         w->found, &w->votes, &w->valid);
+  }
+
+  if (w->valid >= NCC_MIN_VALID_PATCHES &&
+      w->votes >= NCC_MIN_VOTES &&
+      (gdouble) w->votes / (gdouble) w->valid >= NCC_VOTE_FRACTION)
+    {
+      w->matched = TRUE;
+      g_atomic_int_set (w->found, 1);
+    }
+}
+
+/* Runs parallel patch-consensus matching of every template image against
+ * every probe image.  All matching is done on high-pass (locally
+ * mean-subtracted) images so genuine ridge structure dominates, not ambient
+ * pressure/brightness gradients.  Reports the best pair's stats for tuning. */
+static gboolean
+run_ncc_patch_matching (FpPrint *print_template, FpPrint *print,
+                        gdouble *global_out, guint *votes_out, guint *valid_out)
+{
+  static const double angles[] = {
+    -0.31415927, -0.15707963, 0.0,
+    0.15707963, 0.31415927
+  };
+  const guint n_angles = G_N_ELEMENTS (angles);
+  guint nt = print_template->images->len;
+  guint np = print->images->len;
+
+  /* High-pass filter all template images */
+  gint16 **t_hp = g_new0 (gint16 *, nt);
+  for (guint j = 0; j < nt; j++)
+    {
+      FpImage *img = g_ptr_array_index (print_template->images, j);
+      t_hp[j] = ncc_highpass (img->data, img->width, img->height, NCC_BLUR_RADIUS);
+    }
+
+  /* High-pass filter probe images, plus coarse rotations shared by all
+   * template pairings */
+  gint16 **p_hp = g_new0 (gint16 *, np);
+  gint16 **p_hp_rot = g_new0 (gint16 *, np * n_angles);
+  for (guint k = 0; k < np; k++)
+    {
+      FpImage *img = g_ptr_array_index (print->images, k);
+      guint size = img->width * img->height;
+      p_hp[k] = ncc_highpass (img->data, img->width, img->height, NCC_BLUR_RADIUS);
+      for (guint a = 0; a < n_angles; a++)
+        {
+          if (angles[a] == 0.0)
+            {
+              p_hp_rot[k * n_angles + a] = g_memdup2 (p_hp[k], size * sizeof (gint16));
+            }
+          else
+            {
+              p_hp_rot[k * n_angles + a] = g_new (gint16, size);
+              ncc_rotate_hp (p_hp[k], img->width, img->height,
+                             p_hp_rot[k * n_angles + a], angles[a]);
+            }
+        }
+    }
+
+  /* One work item per (template image, probe image) pair; the angle sweep
+   * happens inside the worker so it can refine around its own best angle */
+  NccPairWork  *items = g_new0 (NccPairWork, nt * np);
+  volatile gint found = 0;
+
+  for (guint j = 0; j < nt; j++)
+    {
+      FpImage *t_img = g_ptr_array_index (print_template->images, j);
+      for (guint k = 0; k < np; k++)
+        {
+          FpImage *p_img = g_ptr_array_index (print->images, k);
+          NccPairWork *w = &items[j * np + k];
+          w->t        = t_hp[j];
+          w->t_w      = t_img->width;
+          w->t_h      = t_img->height;
+          w->p_orig   = p_hp[k];
+          w->p_rot    = (const gint16 *const *) &p_hp_rot[k * n_angles];
+          w->angles   = angles;
+          w->n_angles = n_angles;
+          w->p_w      = p_img->width;
+          w->p_h      = p_img->height;
+          w->found    = &found;
+        }
+    }
+
+  /* Dispatch to thread pool */
+  guint n_threads = CLAMP ((guint) g_get_num_processors (), 1u, nt * np);
+  GError       *pool_err = NULL;
+  GThreadPool  *pool     = g_thread_pool_new (ncc_pair_thread_func, NULL,
+                                              (gint) n_threads,
+                                              FALSE, &pool_err);
+
+  if (pool)
+    {
+      for (guint idx = 0; idx < nt * np; idx++)
+        g_thread_pool_push (pool, &items[idx], NULL);
+      g_thread_pool_free (pool, FALSE, TRUE);  /* blocks until done */
+    }
+  else
+    {
+      g_clear_error (&pool_err);
+      for (guint idx = 0; idx < nt * np; idx++)
+        ncc_pair_thread_func (&items[idx], NULL);
+    }
+
+  /* Report the best pair: a matched one if any, else highest vote fraction,
+   * else highest global score */
+  guint best_idx = 0;
+  for (guint idx = 1; idx < nt * np; idx++)
+    {
+      NccPairWork *a = &items[idx], *b = &items[best_idx];
+      gdouble fa = a->valid ? (gdouble) a->votes / a->valid : 0.0;
+      gdouble fb = b->valid ? (gdouble) b->votes / b->valid : 0.0;
+      if (a->matched != b->matched ? a->matched :
+          fa != fb ? fa > fb :
+          a->global_score > b->global_score)
+        best_idx = idx;
+    }
+  *global_out = items[best_idx].global_score;
+  *votes_out = items[best_idx].votes;
+  *valid_out = items[best_idx].valid;
+
+  /* Free high-pass buffers */
+  for (guint j = 0; j < nt; j++)
+    g_free (t_hp[j]);
+  g_free (t_hp);
+  for (guint k = 0; k < np; k++)
+    g_free (p_hp[k]);
+  g_free (p_hp);
+  for (guint i = 0; i < np * n_angles; i++)
+    g_free (p_hp_rot[i]);
+  g_free (p_hp_rot);
+  g_free (items);
+
+  return found;
+}
+
 FpiMatchResult
 fpi_print_bz3_match (FpPrint *print_template,
                      FpPrint *print,
@@ -219,6 +788,37 @@ fpi_print_bz3_match (FpPrint *print_template,
   gint probe_len;
   gint i;
 
+  /* ---- NCC patch-consensus image matching (parallel, with rotation) ---- */
+  if (print_template->images && print_template->images->len > 0 &&
+      print->images        && print->images->len        > 0)
+    {
+      gdouble global_score = 0.0;
+      guint votes = 0, valid = 0;
+
+      if (run_ncc_patch_matching (print_template, print,
+                                  &global_score, &votes, &valid))
+        {
+          g_message ("NCC patch match: %u/%u consistent patches (need %u and %.0f%%), "
+                     "global NCC %.3f — matched",
+                     votes, valid, NCC_MIN_VOTES, NCC_VOTE_FRACTION * 100,
+                     global_score);
+          return FPI_MATCH_SUCCESS;
+        }
+
+      g_message ("NCC patch match: %u/%u consistent patches (need %u and %.0f%%), "
+                 "global NCC %.3f — no match",
+                 votes, valid, NCC_MIN_VOTES, NCC_VOTE_FRACTION * 100,
+                 global_score);
+      /* NCC failed – fall through to Bozorth3 minutiae matching */
+    }
+  else
+    {
+      if (!print_template->images || print_template->images->len == 0)
+        g_warning ("NCC: template images are empty, falling through to bz3");
+      if (!print->images || print->images->len == 0)
+        g_warning ("NCC: probe images are empty, falling through to bz3");
+    }
+
   /* XXX: Use a different error type? */
   if (print_template->type != FPI_PRINT_NBIS || print->type != FPI_PRINT_NBIS)
     {

I am not a hardware or driver developer, and this patch was developed and tested exclusively on my personal laptop. It is highly experimental, so please don't expect it to work with yours.

However, if you are facing the specific issue where elan fingerprint enrollment works but verification fails, this might resolve it for you. For context and similar cases, see libfprint issues: #782, #753, #748, and #483.

If you want to compile and test this patch on your system, follow these steps to build libfprint from source:

1. Clone the repository and check out the target commit:
   Open your terminal, clone the official libfprint repository, and switch to the specific commit this patch targets:

git clone https://gitlab.freedesktop.org/libfprint/libfprint.git
cd libfprint
git checkout 111a3af

2. Download and apply the patch:
   Pull the raw patch file down from this Gist and apply it to the source tree:

curl -L "https://gist.github.com/taiwbi/6fd50e314f267f6ced839b57b0ef4700/raw/acd4a0486d3969836e251c34c1343af1c1fb6dd3/libfprint_elan_ncc.patch" -o elan_ncc.patch
git apply elan_ncc.patch

3. Install the build dependencies:
   You need Meson, Ninja, and the development headers for GLib, GUsb, NSS, Pixman, Cairo, and GUdev. Choose the command below that matches your distribution:

Fedora:

sudo dnf builddep libfprint

Ubuntu:
(Note: If you have source repositories enabled, you can run sudo apt build-dep libfprint. Otherwise, install them manually):

sudo apt install meson ninja-build libglib2.0-dev libgusb-dev libnss3-dev libpixman-1-dev libcairo2-dev libgudev-1.0-dev gobject-introspection libgirepository1.0-dev

Arch Linux:

sudo pacman -S --needed meson ninja glib2 libgusb nss pixman cairo libgudev gobject-introspection

4. Configure, compile, and install:
   Initialize the build directory using Meson, compile the code, install the modified binary onto your system, and restart the fingerprint service:

meson setup builddir
ninja -C builddir
sudo ninja -C builddir install
sudo systemctl restart fprintd

---

⚠️ Warning: Installing a library directly via sudo ninja install will overwrite files managed by your system package manager. If your distribution later pushes an official update to libfprint, your custom-built patch will be overwritten, and you will need to re-run steps 4.