La reconnaissance automatique des empreintes digitales

La reconnaissance automatique des empreintes digitales est une technique biométrique essentielle pour l’authentification et la vérification d’identité dans de nombreux domaines, tels que la sécurité informatique, l’accès aux bâtiments, ou les systèmes bancaires. Cet article s’adresse aux étudiants et chercheurs débutants en biométrie, souhaitant comprendre les principes, méthodes et enjeux de la reconnaissance d’empreintes digitales.

La question

Le travail s’intéresse au développement d’un système automatique d’authentification par empreintes digitales, capable de comparer efficacement une empreinte donnée à une base de données d’empreintes préenregistrées. Le défi principal est de concevoir un algorithme à la fois rapide et précis, capable de traiter les images d’empreintes, d’en extraire les caractéristiques distinctives (minuties), puis de les comparer pour identifier ou vérifier une identité. Ce problème est crucial car la reconnaissance biométrique est largement utilisée dans la sécurité, et une méthode fiable améliore la confiance dans les systèmes d’authentification.

Concepts de base

La reconnaissance d’empreintes digitales repose sur l’analyse des minuties, c’est-à-dire des points caractéristiques sur les lignes des empreintes. Ces minuties sont des singularités telles que les terminaisons de lignes ou les bifurcations (points où une ligne se divise). Francis Galton a introduit la notion de minuties en 1888 et a démontré que la probabilité que deux individus aient la même empreinte est extrêmement faible (une chance sur 64 milliards).

Les étapes fondamentales pour traiter une empreinte digitale sont :

• Binarisation : transformation de l’image originale en niveaux de gris en une image binaire noir et blanc, où les crêtes sont noires et les vallées blanches. Cette étape facilite la détection des minuties.
• Squelettisation : amincissement des lignes de l’empreinte jusqu’à une épaisseur d’un pixel, afin de réduire l’information redondante tout en conservant la structure essentielle. Cela simplifie l’extraction des minuties.
• Extraction des minuties : identification des points terminaux et des bifurcations sur le squelette. Cette extraction utilise notamment la méthode du crossing number (CN), qui calcule un indice basé sur le voisinage 3x3 de chaque pixel pour déterminer la nature du point (terminaison, bifurcation, ou erreur).

Le crossing number CN d’un pixel p est calculé par la formule :

CN = 0.5 * ∑ (|Pi - Pi+1|) pour i=1 à 8, avec P9 = P1

où Pi sont les pixels du voisinage 3x3 autour de p. Selon la valeur de CN, on identifie :

• CN = 1 : terminaison
• CN = 3 : bifurcation
• CN = 0, 2, 4 : erreurs ou points non pertinents

Pour assurer une identification fiable, il faut extraire un nombre suffisant de minuties (environ 12 minimum) qui ne soient pas affectées par des défauts d’acquisition ou des altérations temporaires de l’empreinte (blessures, érosion).

Approche

Le système développé suit un processus en plusieurs étapes :

1. Prétraitement de l’image : L’image d’empreinte est d’abord binarisée. Plusieurs méthodes de binarisation sont testées, notamment la méthode globale d’Otsu et des méthodes locales comme Bernsen ou Bradley, qui adaptent le seuil de binarisation en fonction des variations locales de l’image pour mieux gérer les images de faible qualité.
2. Squelettisation : Après binarisation, l’image est amincie par des algorithmes comme ceux de Zhang-Suen ou Hilditch. Ces algorithmes suppriment progressivement les pixels simples tout en préservant la topologie, jusqu’à obtenir un squelette d’une épaisseur d’un pixel.
3. Extraction des minuties : À partir du squelette, les minuties sont détectées en calculant le crossing number pour chaque pixel. Les coordonnées (x, y) des minuties (terminaisons et bifurcations) sont extraites et stockées.
4. Comparaison des minuties : Plutôt que de comparer les images pixel par pixel, ce qui est lent, la comparaison se fait sur les coordonnées des minuties extraites. Ces minuties sont stockées dans une base de données au format texte. La comparaison consiste alors à rechercher des correspondances entre les ensembles de minuties, ce qui accélère considérablement le processus.

Le système a été implémenté en Java, notamment pour sa portabilité et la richesse de ses API, avec une base de données SQLite contenant les minuties de 82 utilisateurs. Une interface permet d’analyser manuellement les empreintes, d’extraire les minuties, d’effectuer des comparaisons et de rechercher un utilisateur dans la base.

Par ailleurs, une autre approche étudiée utilise l’apprentissage artificiel via un réseau de neurones multilayer perceptron (MLP). Après extraction des minuties, un réseau est entraîné par rétro-propagation (back-propagation) sur un ensemble d’images d’empreintes (50 pour l’apprentissage, 50 pour le test). Ce réseau comporte 12 neurones en entrée (correspondant aux minuties), une couche cachée de 25 neurones et 6 neurones en sortie. Cette méthode vise à classifier les empreintes en fonction de leurs caractéristiques extraites.

Résultats

Les algorithmes classiques de reconnaissance basés sur la comparaison des minuties ont montré une bonne efficacité et rapidité, notamment en évitant la comparaison pixel par pixel. Parmi les méthodes de comparaison testées dans l’algorithme EFinger, la méthode Quad Tree est la plus rapide, bien que moins performante en précision que d’autres méthodes comme Image Mapping.

Le système de reconnaissance par réseau de neurones a atteint un taux de reconnaissance estimé à 100% sur les données testées, ce qui suggère une bonne capacité à apprendre et reconnaître les empreintes à partir des minuties extraites.

Le système développé permet de :

• Prétraiter les images d’empreintes (binarisation, squelettisation)
• Extraire automatiquement les minuties
• Comparer rapidement les empreintes en se basant sur les minuties
• Rechercher un utilisateur dans une base de données biométrique

Limites et questions ouvertes

Le travail n’aborde pas la reconnaissance des fausses empreintes, un aspect important pour la sécurité biométrique qui pourrait faire l’objet d’études futures. De plus, la qualité des images d’empreintes peut fortement influencer la performance des algorithmes, notamment lors de la binarisation et de la squelettisation. La méthode de binarisation globale d’Otsu peut être insuffisante pour des images de faible qualité, nécessitant des méthodes locales plus adaptées.

Enfin, bien que les résultats obtenus soient encourageants, la robustesse du système sur des bases de données plus larges et variées reste à évaluer. L’efficacité des méthodes de comparaison des minuties en termes de précision et rapidité selon la taille de la base de données est également un sujet à approfondir.

Glossaire

• Minuties : Points caractéristiques d’une empreinte digitale, tels que les terminaisons de lignes et bifurcations.
• Binarisation : Transformation d’une image en niveaux de gris en une image binaire noir et blanc.
• Squelettisation : Processus d’amincissement des lignes d’une image binaire jusqu’à une épaisseur d’un pixel.
• Crossing Number (CN) : Indicateur calculé sur le voisinage d’un pixel permettant d’identifier la nature d’une minutie.
• Back-propagation : Algorithme d’apprentissage supervisé pour entraîner un réseau de neurones.
• MLP (Multilayer Perceptron) : Type de réseau de neurones à plusieurs couches utilisé pour la classification.
• Quad Tree : Méthode de segmentation d’image en quatre parties pour faciliter la comparaison.
• Base de données biométrique : Ensemble d’empreintes digitales et de leurs caractéristiques stockées pour comparaison.