How Fingerprints Identify You: The Algorithm Beneath the Biometric

---

Introduction

Have you ever wondered what happens when you simply touch your phone or biometric fingerprint sensor, and it instantly unlocks? It's a blend of electronics that capture your unique fingerprint, algorithms that understand and verify it, and machine learning that enhances security. In this blog, we will explore sensor electronics and the data structures and algorithms (DSA) that empower it.

Overview of the Process

FIG: 1 - The image illustrates the process of a fingerprint recognition system

Source: researchgate

A typical fingerprint recognition system performs the following steps:

1. Capture the fingerprint using a hardware sensor.
2. Preprocess the image to clean it up.
3. Extract key features (called minutiae).
4. Match those features to a stored template using algorithms.
5. Embedded system and machine learning to detect spoofing or fake inputs.

Sensors:

A fingerprint scanner is a sensor that converts the physical ridges and valleys of your finger into a digital image. Let's explore two common types:

1. Optical Sensors:light

FIG: 2 - This image illustrates the optical sensor used in fingerprint scanners
Source: researchgate

Optical sensors use an LED to illuminate your finger on a glass plate. A light-sensitive sensor array (like a CCD or CMOS) captures the reflected light. Ridges, in direct contact with the glass, reflect light differently than valleys (air gaps), creating a digital image where ridges appear darker and valleys lighter.

2. Capacitive Sensors: Electrical

Capacitive sensors consist of a grid of tiny capacitor plates. When your finger touches the sensor, ridges make direct contact, altering the electrical charge (capacitance) of the underlying capacitors. Valleys, being air gaps, cause a different, smaller change. The sensor measures these minute differences across its grid, converting the pattern of varying electrical charges into a digital map of your fingerprint.Your skin conducts electricity, completing a tiny circuit when a ridge touches a sensor point, changing its charge.

FIG: 3 - This image illustrates the electrical sensor used in fingerprint scanners
Source: ubergizmo

Image Preprocessing

Once the electronic sensor captures the raw image, it will become a bunch of pixel values. To make sense of it, we need some Digital Signal Processing (DSP) and Data Structures and Algorithms (DSA) to clean it up and extract meaningful features.

FIG: 4 - The image illustrates the process of fingerprint minutiae extraction and refinement
Source: researchGate

1. Grayscale Conversion & Normalization: Raw images are converted to grayscale and normalized for consistent intensity values.
2. Binarization: The grayscale image is converted into a binary (black and white) image, simplifying the data. 3.Thinning (Skeletonization): Ridges are reduced to a single-pixel width to simplify feature extraction

Python code: Simple Binarization
fingerprint_image is a 2D list (or NumPy array) of pixel values (0-255).

Minutiae Extraction

Now that we have a clean, thinned binary image, we have to find the minutiae using dsa. These are the tiny, unique features that truly distinguish one fingerprint from another.Minutiae are unique features of your fingerprint.

The most common minutiae are illustrated in the image:

FIG:5-The most common minutiae are illustrated in the image
Source:mdpi.

The system scans the image using a sliding window to locate these points, storing their (x, y) coordinates and orientation.A "minutia map" or template is created, which is a simplified representation of the fingerprint's unique characteristics. This map is then converted into a digital data stream, typically a binary code, for storage and comparison. These features are often stored in a hash map for quick lookup.

FIG:6-The image illustrates the process of converting a biometric, specifically a fingerprint, into a digital data stream for identification or verification purposes, a core concept in biometric security
source:timeteccloudblog.com

These features are often stored in a hash map, so that when the system needs to compare two fingerprints, it can look up corresponding features quickly in O(1) time.

––Python code using a list of dictionaries :––

Matching Algorithms

With two sets of minutiae (one from the scanned print, one from the database), the final step is comparison. Advanced DSA techniques ensure speed and accuracy. The goal is to find how many minutiae pairs from the two fingerprints "match" within a certain tolerance for position and orientation, even if the finger was placed slightly differently (rotated or shifted).

FIG: 7- Minutiae matching based on minutiae
Source: researchgate, www.irjet.net

Reference minutiae-These are the key points (e.g., ridge endings and bifurcations) extracted from a known or stored fingerprint, used as a basis for comparison.
A template minutia-A specific minutiae point belonging to the reference or stored fingerprint.
A query minutia-A specific minutiae point belonging to the fingerprint being compared (the one under investigation).
A pair of paired minutiae-This indicates a corresponding pair of minutiae points that have been successfully matched between the template and the query fingerprint, signifying a high degree of similarity in their location and orientation.

Simplified Matching (Euclidean Distance Concept)

This involves picking a reference minutia from the input fingerprint, aligning it to a stored template, and calculating how many other minutiae pairs are "close enough" after alignment.

Python code:

Spatial Trees for Efficient Searching

If you have millions of stored fingerprints in a database is it possible for you to quickly find a match without comparing your input to every single one.This is where spatial indexing data structures like R-trees and kd trees become incredibly useful.

FIG: 8 - The Kd-tree structure storing minutiae.
Source: researchGate

An Kd-tree organizes spatial data (like the (x, y) coordinates of minutiae or groups of minutiae) in a hierarchical tree structure. A non-leaf node in K-D tree divides the space into two parts, called as half-spaces. Points to the left of this space are represented by the left subtree of that node and points to the right of the space are represented by the right subtree.When you search for a fingerprint's minutiae, the system doesn't have to scan the whole thing. It quickly traverses the tree, going only into bounding boxes that overlap with the region where your input minutiae are located. This drastically reduces the number of comparisons needed, making the search much faster.

Creation of 2D tree
Consider the following points in 2D plane:(3,6), (17,15), (13,15), (6,12), (9,1), (2,7), (10,19)

FIG:9-Creation of 2D tree
source:greeksforgreeks

Tree Building Rule :
At even depths (0, 2, 4...), split by X (X-aligned).At odd depths (1, 3, 5...), split by Y (Y-aligned).Left subtree if key is less than, right if greater than or equal to.
Example: Insert (3, 6):Tree is empty → Make (3, 6) the root.Depth: 0 → X-aligned.
Insert (17, 15):Compare X: 17 > 3 → Go to right of (3, 6).Depth: 1 → Y-aligned.Insert at right → (17, 15).

K-D Tree space partitioned (2D):

Example:Point (3, 6):Divide the space vertically → Draw line X = 3
Point (2, 7):Goes to the left of X = 3 → Divide horizontally → Draw line Y = 7 to the left of X = 3.

Python Code:

Dry Run
You insert: (12,8), (10,9), (15,5), (13,7).KDTree splits based on X then Y to form a binary search space.A query for (12,8) returns nearby points by checking both branches efficiently.
Time Complexity: O(log n)— much faster than comparing every stored fingerprint point.

Hashing for Quick Pre-Filtering

Fingerprint Enrollment:An image of a fingerprint is captured. Minutiae(unique points like ridge endings and bifurcations) are extracted from the fingerprint image. These minutiae are then converted into hashes (digital representations). These hashes are stored in a Fingerprint hash database for future reference.

FIG:11-The image illustrates the process of fingerprint enrollment and verification using a hash-based system
Source:stack exchange.

Fingerprint Verification:A new Image of a fingerprint is captured for verification. Minutiae are extracted from this new fingerprint image, similar to the enrollment process. These minutiae are converted into new hashes.These new hashes are then compared (match) against the stored hashes in the fingerprint hash database to verify the individual's identity.

FIG-12-Components of hashing
source:greeksforgreeks.

Hashing is a process used in data structures (like hash tables) to efficiently store, retrieve, and manage data. The three core components involved in hashing are:
Key: Input to the hash function.
Hash Function:Takes a key and produces an integer output (hash code or index).
Hash Table: Data structure (typically an array) where key-value pairs are stored, with the index determined by the hash function..It allows for O(1) average time complexity for search, insert, and delete operations.In case of collisions, techniques like chaining or open addressing are used.
Example:Suppose we want to store a student's grade using their roll number:
Key: 1023 (Roll Number)
Hash Function: 1023 % 10 = 3
Hash Table: Store the grade in index 3 of the array.
Collision in Hashing
A collision occurs when two different keys generate the same hash index.It happens because many keys are mapped to a limited number of slots.

FIG:13-The image illustrates collosion
source:greeksforgreeks.

While you wouldn't hash an entire fingerprint for matching (due to collision risks and sensitivity to minor variations), hashing concepts can be used in clever ways for pre-filtering. For example, if you can extract certain invariant features from a fingerprint (like the overall pattern type - loop, whorl, arch, or a unique pattern formed by a small cluster of minutiae), you could generate a hash for that feature. This hash could then point to a smaller subset of the database, narrowing down the search before running the full minutiae matching algorithm.

Embedded Systems & ML

Tiny, powerful computers and intelligent software enhance the entire process:

FIG:14-An embedded system is a specialized computer system designed to perform a dedicated function within a larger mechanical or electronic system. The image illustrates the core components and interactions within such a system.
source:The engineering project

Embedded Systems : Modern fingerprint scanners are often powered by embedded systems.These are specialized computer systems designed to perform a dedicated function within a larger mechanical or electrical system. They contain a microcontroller/microprocessor, memory, I/O interfaces, and power management. They perform real-time processing for quick unlocking.These systems perform real-time processing, ensuring your phone unlocks in milliseconds. They are the dedicated "fingerprint processing units" that live inside your device.

FIG:15-This image illustrates a process involving "Model Fingerprinting" for edge model selection and anomaly detection in AI models.
source:medium.

Machine Learning : ML, especially deep learning, enhances accuracy and security.

• Enhanced Image Processing: ML models can denoise and enhance poor-quality images.
• Robust Feature Extraction: Advanced ML models can extract a richer set of features.
• Liveness Detection (Anti-Spoofing): ML models differentiate between real and fake fingers by analyzing subtle cues like skin elasticity, sweat pore activity, pulse/blood flow, texture, and depth.

Reference:

• Research gate
• sage journals
• www.mudpi.com
• Arrow electronic
• Bayometric
• Semiconductor engineering
• M2SYStechnology
• Starlink
• geeksforgeeks