Fingerprint algorithms
Algorithmes de reconnaissance d'empreintes digitales

Comparison methods
Méthodes de comparaison

If manual comparison by a fingerprint expert is always done to say if two fingerprint images are coming from the same finger in critical cases, automated methods are widely used now.

Si un expert en empreintes digitales effectue toujours une comparaison manuelle pour dire si deux images d'empreintes proviennent du même doigt dans les cas critiques, les méthodes automatiques sont à présent partout utilisées.

Many different algorithm types exist: / De nombreuses techniques existent:

Direct (optical) correlation is practically not used, as not very efficient for large database.
La comparaison directe par corrélation des images n'est pratiquement plus utilisée, car assez peu efficace pour les grandes bases de données.
The general shape of the fingerprint is generally used to pre-process the images, and reduce the search in large databases. This uses the general directions of the lines of the fingerprint, and the presence of the core and the delta. Several categories have been defined in the Henry system: whorl, right loop, left loop, arch, and tented arch.
L'allure générale de l'empreinte est généralement utilisée pour effectuer un premier tri des images, afin de réduire les temps de recherche dans les grandes base de données. On utilise la direction générale des lignes, ainsi que le coeur et le delta de l'empreinte. Plusieurs catégories ont été définies dans le système d'Henry: tourbillon, boucle à droite, boucle à gauche, arche.

Fingerprint categories general direction

Minutiae

Most algorithms are using minutiae, the specific points like ridges ending, bifurcation... Only the position and direction of these features are stored in the signature for further comparison.

La plupart des algorithmes utilisent les minuties, ces points spécifiques comme les fin de lignes, les embranchements... Seules les positions et directions de ces points sont stockées dans la signature de l'empreinte pour les futures comparaisons.

Some algorithms counts the number of ridges between particular points, generally the minutiae, instead of the distances computed from the position.

Certains algorithmes comptent le nombre de lignes entre deux points, généralement des minuties, au lieu des distances calculées à partir des positions.

Pattern matching

Pattern matching algorithms are using the general shape of the ridges. The fingerprint is divided in small sectors, and the ridge direction, phase and pitch are extracted and stored.

Les algorithmes basés sur la corrélation utilisent la forme générale des lignes. L'empreinte est divisée en petits secteurs où la direction, la phase et le pas des lignes sont extraits puis stockés.

Very often, algorithms are using a combination of all theses techniques.
Il est fréquent que les algorithmes combinent ces diverses techniques.

Matching

Matching of a "ten print card" fingerprint with a latent fingerprint using minutiae.

Accord entre une image d'empreinte provenant d'un enregistrement sur fiche (fiche de police où les 10 doigts encrées sont imprimés) et une empreinte latente, utilisant les minuties.

Not using minutiae nor pores

[2024 Jan] Unveiling intra-person fingerprint similarity via deep contrastive learning

Up to now, fingerprint recognition were using features classified into 3 levels :

general shape (whorl, loop...)
minutiae (ending, bifurcation...)
pores

These features are specific to one fingerprint, even from the same hand.

A collaboration between Hod Lipson’s Creative Machines lab at Columbia Engineering and Wenyao Xu’s Embedded Sensors and Computing lab at University at Buffalo, SUNY, discovered, using deep learning, that some other features are specific to one person, and moreover, are the same between the fingers of the same person. “Instead, it was using something else, related to the angles and curvatures of the swirls and loops in the center of the fingerprint.”

This is not yet perfect, but this will help to match someone, even if the target fingerprint is not in the database !

Matching probability

What is the probability of two fingerprints to match ?
Quelle est la probabilité que deux empreintes soient identiques ?

"On the individuality of fingerprints" (Pankanti/IBM) estimated to 6.10^-8 the probability for 12 minutiae matching among 36 to match, but lots of estimations exist...
L'article "On the individuality of fingerprints" (Pankanti/IBM) estime à 6.10^-8 la probabilité que 12 minuties parmi 36 correspondent, mais de nombreuses estimations existent...

In the following array, M & R defines "regions", N minutiae.
Dans le tabeau suivant, M & R sont les "régions", et N le nombre de minuties.

Sensor + algorithm integration

Integrating the recognition algorithm with the sensor has started in 1999.

Very small sensors

The previous algorithms just cannot work with very small sensors, because there is not enough minutiae information. As a result, some companies are developping new algorithms -well, not that new because it is based on simple pattern matching (what else?!?).

They are announcing sometimes very good numbers, but you just cannot get the source information to get these numbers and have to trust them.

Here are the main announcements:

(2013) Apple, with the smallest sensor.
FAR: 1/50 000 for a 88x88 pixels sensor @508dpi.
(2014 Jun) Crucialtec (CrucialSoft) Fermion algo is developped for small area-type fingerprint sensor.
FAR: 1/100 000 with a FRR 1/100. No size given.
(2016 Jan) Crucialtec (CrucialSoft) Muon algo
FAR: 1/50 000 for a 8mm² minimum recognition area.
(2016 Feb) Suprema Launches Smartphone Authentication Solution, supporting World’s Smallest Fingerprint Sensor.
"the lowest FAR in the market" for a 4x4mm sensor (BioSign algorithm).

Hey, guys, even with a FAR = 1/10 000, what you are saying is that with two independant finger areas as small as 4x4mm, you can recognize someone with a FAR = 1/100 000 000, much more better than all those governmental companies working on that topic for decades? Maybe the actual sensors are giving much more better images (something hard to believe with 300 microns thickness of glass above the sensor), and that you are not comparing your images with latent prints, but well, be humble (and prove your numbers...)

Within this fierce competition, a company is going the other way, demonstrating that we need large sensors:

Next Biometrics

But well, for sure, if you are using minutia-based algorithms, then large sensors are a must. I demonstrated that years ago with Cogent :

J.F. Mainguet, Wei Gong, Anne Wang "Reducing Silicon Fingerprint Sensor Area" International Conference on Biometric Authentication ICBA 2004 Hong-Kong July, 15-17 2004 Lecture Notes in Computer Science, Volume 3072 / 2004, pp. 301 - 308
the Madrid report (ordered by Next Biometrics), demonstrating that regular minutiae based algorithms requires sensors larger than 8x8mm²

which does not mean that algorithms using 3rd level features (for instance pores) do not work with a smaller area.

Evaluation

FAR & FRR evaluation is difficult, and you must show the origin of the numbers so that we can understand and compare. It is very easy to trick the databases, this is pretty well explained in this paper :

How to evaluate a fingerprint algorithm / Patrik Lindeberg | Precise Biometrics / 2015-06-25

But in fact, this is a little bit more complicated, because you also have to explain the enrollment strategy, you can also read my accuracy page to get some more info to make your mind.

Police & fingerprints
La police et les empreintes digitales

The FBI IAFIS homepage

The FBI latent print homepage

Accuracy and reliability of forensic latent fingerprint decisions

Accuracy and reliability of forensic latent fingerprint decisions / Bradford T. Ulery, R. Austin Hicklin, JoAnn Buscagli and Maria Antonia Roberts (local copy for the records)

This paper reports on the first large-scale study of the accuracy and reliability of latent print examiners’ decisions, in which 169 latent print examiners each compared approximately 100 pairs of latent and exemplar fingerprints from a pool of 744 pairs.

So it will tell you how accurate is a "human" algorithm...