FR2582831A1 - Procede d'identification d'une empreinte digitale, dispositif pour la mise en oeuvre de ce procede et utilisation de ce procede - Google Patents

Abstract

LA PRESENTE INVENTION CONCERNE UN PROCEDE D'IDENTIFICATION D'UNE EMPREINTE DIGITALE, LE DISPOSITIF POUR LA MISE EN OEUVRE DE CE PROCEDE ET L'UTILISATION DE CE PROCEDE. CE PROCEDE CONSISTE EN L'ACQUISITION DE L'IMAGE D'UNE EMPREINTE DIGITALE PAR UN PROCEDE OPTIQUE, A LA RECONNAISSANCE AUTOMATIQUE D'UN NOMBRE DETERMINE DE POINTS CARACTERISTIQUES DE CETTE IMAGE ET A LA COMPARAISON DE CES POINTS CARACTERISTIQUES AVEC CEUX D'IMAGES ACQUISES PRECEDEMMENT. AFIN D'EFFECTUER CES OPERATIONS, ON CALCULE POUR CETTE IMAGE UNE CLE SPECIFIQUE DE L'EMPREINTE, CETTE CLE ETANT DEFINIE EN FONCTION D'UN NOMBRE DE POINTS CARACTERISTIQUES SELECTIONNES COMME ETANT REPRESENTATIFS DE L'IMAGE DE L'EMPREINTE. CE PROCEDE EST UTILISE DANS LE CONTROLE DE L'IDENTITE D'UN INDIVIDU PAR COMPARAISON DE SON EMPREINTE DIGITALE AVEC CELLE DE SA PIECE D'IDENTITE.

Description

Procédé d'identification d'une empreinte digitale. dispositif pour la mise en oeuvre de ce procédé et utilisation de ce procédé
La présente invention concerne un procédé d'identification d'une empreinte digitale d'un individu, dans lequel on procède a l'acquisition de l'image de cette empreinte par un procédé optique, puis a la reconnaissance automatique d'un nombre déterminé de points caractéristiques de cette image et à la comparaison de ces points caractéristiques avec ceux d'images acquises précédemment.

Elle concerne egalement un dispositif pour la mise en oeuvre de ce procédé ainsi qu'une utilisation du procédé.

On connait différents moyens surs d'identifier un individu par reconnaissance de caractéristiques propres a cet individu. Parmi ces moyens comprenant l'analyse morphologique générale, l'analyse sanguine, l'analyse génétique, la reconnaissance de la parole, l'analyse de la forme de l'oreille, la poroscopie, la crétologie etc.., la reconnaissance des empreintes digitales est la plus couramment utilisée à ce jour. Par rapport aux autres procédés qui sont souvent longs, fastidieux, traumatisants pour le sujet concerné, ou qui ne restent surs que pour une faible population d'individus, cette dernière méthode présente l'avantage d'être simple et rapide d'accès. En effet, la visualisation de l'empreinte digitale est un procedé non contraignant qui ne nécessite pas, pour l'individu, de traitement médical ou chimique.De plus, l'information est disponible et l'acquisition est instantanée. En outre, cette méthode d'identification est fiable. Le dessin filigranique formé d'un ensemble de crêtes présentant des particularites de structures infiniment variées, present notamment sur les faces antérieures et latérales des doigts d'un individu, est immuable pendant toute la vie de cet individu et au-delà (jusqu'a la putréfaction). Ce dessin ne peut être modifié ni pathologiquement, ni par la volonté du sujet. Le résultat de l'apposition de cette zone soumise à la sécrétion sudorale, sur des supports réceptifs constitue l'empreinte papillaire. Cette empreinte est le reflet fidèle, en ses moindres détails, des particularités des crêtes des téguments.L'exa men de deux empreintes d'origne différente démontre la non-identité des deux empreintes par la présence de particularités distinctes.

L'expérience pratique demontre que la présence simultanée, sur deux empreintes, de douze points homologues entraîne l'identité apsolue des deux traces.

L'analyse des empreintes digitales s'effectue, actuellement encore, par examen visuel et comparaison directe, bien que de nombreuses tentatives aient été réalisées pour automatiser le procédé. Parmi ces tentatives, la plupart sont orientées vers le traitement optique qui met en oeuvre un filtrage approprié ou une correlation parfaite, de manière à permettre la comparaison directe de l'image d'une empreinte digitale devant etre identifiée à l'image d'une empreinte digitale préalablement enregistree. Dans certains cas, ces methodes de correlation comparent la transformée de Fourier des images, au lieu de comparer directement ces images. L'information image est souvent condensée lors d'un pré-traitement avant d'être analysée et corrélée.Ces pre- traitements peuvent avoir lieu lors de la prise de l'image, sous forme d'une recherche d'orientation des lignes de relief. Ils peuvent dgale- ment etre effectues apres analyse numérique de l'image sous forme de détection caractéristique générale de l'image, afin de réduire la quantite des informations à traiter.

D'autres tentatives réalisées pour automatiser le procédé ont recouru à l'informatique. Les appareils pour la mise en oeuvre de cette me- thode qui sont actuellement en service, sont conçus pour traiter par l'informatique les données correspondant à des empreintes digitales.

La technique utilisée consiste à transformer le dessin de l'empreinte en une image codee. A ce stade intervient un dactylotechnicien qui détermine - les familles de points caractéristiques de l'empreintes, tels que les deltas, les interruptions, les arrets de ligne, les deviations, les bifurcations, les crochets, les anneaux-îlots, - le nombre de points par famille, - la position relative de ces points entre eux.

La collection de ces renseignements nécessite un temps relativement long (environ 15 minutes). Dès que ces renseignements sont effectivement collectés, le processus d'identification peut commencer. Selon certains tests et, comme mentionné ci-dessus, il suffit de douze caractéristiques définies pour procéder å une identification certaine.

Le processus d'identification commence par la transmission des informations collectees, vers le centre informatique de traitement, via d'importants réseaux télé-informatiques complexes. Chaque fois qu'une empreinte à identifier est soumise à ce centre, des recherches sont effectuées dans'toute la collection-d'empreintes mémorisées. L'ordinateur central sélectionne alors les cinquante empreintes les plus problables. Le dactylotechnicien rappelle, à l'aide de son unite de traitement terminale, reliée à l'ordinateur central, les cinquante empreintes sélectionnées et les compare une à une a l'empreinte à analyser.

Les principaux inconvénients de ce système sont dus & l'intervention humaine importante, & la nécessite de disposer de systemes centralisés de grande capacité, aux longs délais de réponse et à l'impossibilité de traiter une population relativement vaste.

En ce qui concerne l'intervention humaine, le système impose, dans ses phases initiale et finale, le recours à des analystes spécialisés, ce qui engendre un certain risque d'erreurs à la saisie des données et lors des interprétations. Le temps de traitement est long et les frais occasionnés en raison du court élevé de la main-d'oeuvre spécialisée sont élevés.

L'existence d'une unite de traitement centralisée impose la mise en place d'un reseau télé-informatique important, d'une grande capacite de stockage d'informations, d'une équipe d'entretien de haut niveau, ainsi que la mise à disposition d'une grosse energie informatique.

En ce qui concerne la population traitée, les systèmes installés à ce jour ne sont opérationnels que pour une population inférieure ou égale à 100.000 individus.

La présente invention a pour but de pallier ces inconvénients en proposant un procedé et un dispositif d'identification des empreintes digitales entierement automatiques, travaillant en temps réel.

Ce but est atteint par le procédé de l'invention, caractérisé en ce que l'on calcule pour cette image une clé specifique de l'empreinte, cette clé étant définie en fonction d'un nombre de points caractéristiques, sélectionnés comme étant représentatifs de l'image de l'empreinte.

Selon un mode de realisation préferé, on effectue l'acquisition de l'image optique au moyen d'une camera de télévision å réseau de 256 lignes à 256 points et en ce qu'on transforme l'image carrée en une image rectangulaire de 280 lignes a 380 points.

Pour exploiter l'image optique prealablement acquise et pour permettre son analyse ultérieure, on procede s un traitement de cette image consistant a la numériser. A cet effet, on quantifie le niveau de luminosité sur un nombre défini de niveaux de gris, on determine en temps reel les composantes horizontale et verticale du vecteur gradient associé à chaque pixel, on calcule le module et l'orientation du vecteur gradient, et on sélectionne les pixels appartenant aux contours par recherche d'un maximum local du module du gradient dans la direction du vecteur gradient.

Selon un mode de realisation préféré, on mémorise ensuite l'image numérisée et on construit une image binaire de l'empreinte digitale en traçant les lignes de contraste reliant les points de contraste connexes et en effectuant un découpage de ces lignes en segments géométriques caractérisés par la courbure.

L'analyse de l'image binaire comporte de préférence une phase de suivi double des lignes de contraste, ces lignes de contraste étant indifféremment les images des cretes ou des sillons de l'empreinte digitale.

Elle comporte également une phase de détection des indices de cause d'arrêt qui s'effectue en déterminant les arrêts du suivi double des lignes de contraste.

Selon un mode de realisation particulierement avantageux, on attribue un code de cause d'arrêt à chaque indice de cause d'arrêt.

Selon un mode de réalisation prëféré, la determination des indices s'effectue en attribuant à chaque cause d'arrêt des coordonnées de position, une orientation correspondant à la ligne de suivi avant l'arrêt et un code d'arrêt numéroté de 1 a 8. On modélise ensuite l'empreinte en mémorisant pour chaque arrêt les coordonnées de position et le code d'arret. Cette modelisation de l'empreinte s'effectue de préférence sur la base d'une trentaine de points d'arret.

Pour fiabiliser la modélisation de l'empreinte, on la modelise de préférence à plusieurs reprises pour établir par cooptation une carte d'indices extraits correspondant au modèle d'une empreinte qui ne contient que les indices les plus significatifs, cette carte d'indices extraits permettant de definir ladite cle caracteristique de l'empreinte.

Le dispositif pour la mise en oeuvre du procédé est caractérisé en ce qu'il comporte des moyens pour saisir optiquement l'image d'une empreinte digitale, des moyens pour analyser cette image et des moyens pour determiner une clé caractéristique de l'empreinte analyse
Selon une forme de réalisation préférée, les moyens pour saisir optiquement l'image de l'empreinte comportent une caméra de télévision et des moyens pour numériser l'image optique.

Les moyens pour numériser l'image comportent avantageusement des organes pour quantifier le niveau de luminosité sur un nombre defini de niveaux de gris, ce nombre étant de préférence égal à 16, pour determiner en temps reel les composantes horizontale et verticale du vecteur gradient associé à chaque pixel, pour calculer le module et l'orientation du vecteur gradient et pour sélectionner les pixels appartenant aux contours par recherche d'un maximum local du module de gradient dans la direction du vecteur gradient.

Selon un mode de réalisation preferé, le dispositif comporte des moyens pour mémoriser l'image numérisée et des moyens pour construire une image binaire de l'empreinte digitale en traçant les lignes de contraste reliant les points de contraste connexes et en effectuant un découpage de ces lignes en segments géométriques caractérisés par la courbure.

Ce dispositif comporte également avantageusement des moyens pour analyser l'image binaire de l'empreinte digitale equipes d'un dispositif conçu pour effectuer un suivi double des lignes de contraste de cette image.

Les moyens pour analyser l'image comporte egalement de preference des moyens pour detecter les indices de cause d'arrêt en déterminant les arrets du suivi double des lignes de contraste ainsi que des moyens pour attribuer un code de cause d'arrêt & chaque indice de catie d'arrêt.

Pour définir les points caractéristiques, le dispositif comprend avantageusement des moyens pour attribuer, pour chaque indice, des coordonnées de position1 une orientation correspondant à la ligne de suivi avant l'arrêt et un code d'arret numéroté.

Le dispositif comporte également des moyens pour modéliser l'empreinte, des moyens pour fiabiliser la modélisation de l'empreinte et des moyens pour établir une carte d'indices extraits correspondant au modele de l'empreinte ainsi que des moyens pour definir ladite cle caractéristique de l'empreinte.

Selon une utilisation préférée du procédé ci-dessus, on appose de maniere inalterable ladite clé caractéristique de l'empreinte digitale sur une pièce d'identité d'un individu et on enregistre cette même cle dans des fichiers de contrôle. Pour contrôler l'identité d'un individu on peut, de ce fait, comparer en temps reel la clé correspondant a l'analyse directe de son empreinte digitale avec celle de sa piece d'identité.

La présente invention sera mieux comprise en référence à la description d'un exemple de réalisation et aux dessins annexes dans lesquels
La figure 1 représente une forme de réalisation préférée du capteur utilise pour acquérir l'image optique d'une empreinte digitale,
La figure 2 représente une vue de l'image numerisée d'une empreinte digitale,
La figure 3 représente une vue schématique illustrant les différentes phases du procédé,
La figure 4 représente une vue schématique illustrant le mode de determination du gradient correspondant à chaque pixel,
La figure 5 represente un circuit logique expliquant la structure de l'opérateur calculant les composantes du gradient,
La figure 6 représente une vue schématique du circuit logique de selection des pixels de contour, et
La figure 7 illustre une utilisation pratique du procédé selon l'invention.

Le procédé d'identification selon l'invention implique l'acquisition des informations concernant une empreinte digitale à analyser. Cette acquisition s'effectue en deux étapes principales qui sont l'acquisition et le traitement de l'image optique de cette empreinte suivis de l'analyse de cette image. L'acquisition de l'image est effectuée au moyen d'un capteur dont une forme de réalisation est illustrée par la fig. 1. Ce capteur comporte une fenetre 1 sous laquelle est fixé un prisme 2 à réflexion totale. Une source de lumiere 3 est agencée pour transmettre un faisceau incident 4 sur une surface réfléchissante 5 qui renvoie un faisceau refléchi 4' perpendiculairement à la face d'entrée 6 du prisme pour eclairer l'extrémité d'un doigt appuyé contre la fenetre 1.Un faisceau réfléchi 7 traver se la face de sortie 8 du prisme 2 et est capté par l'objectif 9 d'une camera de prises de vues 10. La distance entre le prisme 2 et la caméra 10 est réglee avec précision. La caméra, du type connu en soi, comporte par exemple un réseau de 256x256 soit 65'536 points appelés pixels. Toutefois on a constate qu'il était avantageux de former une image rectangulaire. A cet effet, en modifiant les séquences de comptage du systeme de détection de contours, on peut obtenir une image rectangulaire de 280 x 380 pixels avec une caméra standard dont le réseau sensible comporte 256 x 256 points. Ceci est réalise grace au choix d'un compromis entre le parametre définition de l'image (pour une bonne analyse des contours) et le parametre surface du champ d'observation (pour le calcul du referentiel).L'utilisation d'une fenêtre rectangulaire permet de mémoriser la totalité de l'image de l'empreinte et d'obtenir le maximum de points significatifs, c'est-adire un maximum d'indices allant des lignes basales jusqu' & l'extrémité supérieure de l'empreinte.

L'image est mise en memoire en 10 ms dans une unite de stockage des données (non reprdsentGe), directement connectée à la camera. Cette image est ensuite traitée par un processeur d'extraction de contrastes travaillant en temps réel. L'analyse d'images å plusieurs niveaux d'intensité lumineuse necessite une phase préalable d'extraction de contrastes pour déterminer le contour des objets. Compte tenu de la tres grande quantité d'informations à manipuler, la mise en oeuvre d'algorithmes de détection de contours sur un calculateur conventionnel entraîne des temps de calcul très longs. Pour cette raison, on utilise un processeur numerique qui travaille -å la volée" sur le signal d'image de la caméra de télévision.Ce processeur realise : la numerisation de l'image; c'est-à-dire la transformation de l'image réelle en une image binaire. A cet effet le niveau de luminosité est quantifié sur 16 niveaux de gris automatiquement repartis sur toute la dynamique du signal image. On détermine en temps réel les composantes horizontale et verticale du vecteur gradient associé à chaque point de l'image, ou pixel, on calcule le module et l'orientation du vecteur gradient, et on selectionne les pixels appartenant aux contours par recherche d'un maximum local du module du gradient dans la direction du vecteur gradient.

On procède ensuite à l'inscription dans une mémoire d'image des informations associées à chaque pixel, à savoir le module et l'orientation du vecteur gradient des pixels appartenant à un contour,
Ces operations sont réalisées par un ensemble de processeurs en structure pipeline. Elles sont terminées environ 128 ms apres la fin de l'acquisition de l'image.

On utilise ensuite un logiciel de traitement et d'interprétation de l'image qui travaille à partir des informations fournies par le processeur d'extraction de contrastes mentionné ci-dessus. Les fonctions de ce logiciel sont les suivantes - il construit les lignes de contraste en reliant les points de contraste connexes.

- il effectue le découpage de ces lignes en segments géométriques "indices visuels" caractérisés par la courbure, - il interprete les indices visuels en terme d'objets par une méthode dite d'accumulation de plausibilité".

L'ensemble du logiciel est contrôlé par une stratégie dite de "prédiction vérification". Cette strategie consiste à commander l'interprétation des indices visuels au fur et à mesure de leur obtention pour construire des hypothèses de points caracteristiques positionnés et, en fonction de ces hypotheses, à prédire l'emplacement de nouveaux indices visuels que l'on cherche alors à extraire. La présence ou l'absence des indices visuels permet de confirmer ou d'infirmer les hypothèses.

Cette méthode permet de réduire cqnsidérablement la quantite d'informations effectivement traitées.

L'identification et la localisation des points caractéristiques contenus dans une image d'empreinte, nécessitent une phase préalable de détection des contours. La mise en oeuvre d'un processeur numérique qui travaille sur le signal image numérisé d'une caméra de télévision, permet de pallier ce défaut. Ce processeur calcule, en temps réel, les composantes du vecteur gradient associé à chaque pixel d'image grâce à un opérateur de Sobel. il sélectionne ensuite les pixels de contour à partir de la répartition du gradient dans le proche voisinage de chaque pixel. Dans cette realisation, il est raisonnable de considerer que les images traitées sont constituées par la juxtaposition de régions présentant une certaine homogénéité du niveau de luminosite.

Ces régions sont divisées en zones de contraste < à savoir transitions entre zones de cretes et zones de sillons des empreintes digitales).

Ces zones de contraste constituent un ensemble de points dans le voisinage desquels il existe un changement significatif de niveau de luminosité. A l'intérieur des zones de contraste, se trouvent les contours des cretes de l'empreinte, lignes de partage entre régions, d'épaisseur 1 pixel.

Le processeur utilisé dans le cadre de l'invention a pour fonction de selectionner les pixels d'image appartenant à des contours, selon des critères qui ne nécessitent que des informations concernant les propriétés globales de l'image : dynamique des niveaux de luminosité, et bruit gaussien.

Le chaînage de ces pixels ainsi que les fonctions d'interprétation, sont réalisés par des logiciels spécifiques sur un calculateur auquel le processeur est relie par l'lntermediaire d'une mémoire image. La détection des zones de contraste est réalisée en temps réel sans mémorisation préalable de l'image par mise en oeuvre d'operateurs dont les fonctions sont basees sur une estimation du gradient.

A chaque pixel I (jk), en coordonnées complexes, de l'image, est associée une approximation G (jh) du vecteur gradient obtenue par différences finies. Les composantes horizontale et verticale Gh et Gv respectivement selon les détections horizontales et verticales, sont obtenues par convolution de l'image avec des masques Mh et Mv de dimensions n x n"(qui seront définis par la suite). Les elements des masques ainsi que la dimension ne sont pas caractéristiques de 1 'approximation realisee.

Le module et l'orientation du vecteur gradient sont calculés par la formule //G (jk)// = Gh2 (,R) + Gv2 (J,R) = arctg Gv/Gh
L'appartenance du pixel I (j,h) à une zone de contraste est alors déterminee par comparaison de //G(j,k)// à un seuil. Le choix du seuil est déterminé d'apres les caractéristiques globales de l'image.

La distribution de //G// est bimodulaire; elle est traduite par l'existence de 2 classes de pixels, à savoir ceux appartenant à des zones de contraste caractérisées par des valeurs élevées de //G//, et ceux pour lesquels G est petit.

Le seuil maximal est ainsi déterminé d'après un histogramme du gradient ou soit par une méthode d'apprentissage automatique. Les zones de contraste ainsi obtenues ont une epaisseur généralement superieure à 1 pixel. Il a donc été necessaire de mettre en oeuvre un algorithme de détection de contours à l'intérieur des zones de contraste. La definition de masques'est nécessaire au calcul des composantes de vecteur gradient. On utilise de préférence les masques de Sobel dont les composantes horizontale Mh et verticale Mv sont définies par les matrices suivantes

<SEP> 1 <SEP> 0 <SEP> -1
<tb> Mh <SEP> = <SEP> #2 <SEP> 0 <SEP> -2# <SEP> .<SEP> = <SEP> Mv: <SEP> = <SEP> #000# <SEP>
<tb> <SEP> 1 <SEP> 0-1 <SEP> 1 <SEP> 2 <SEP> 1
<tb>
De plus, ces masques possedent la très interessante propriété d'être séparables.En effet, les masques de Sobel, par exemple, s'obtiennent par

<tb> Mn <SEP> = <SEP> #2# <SEP> <SEP> #0# <SEP> = <SEP> <SEP> V1V2T, <SEP> Mv <SEP> = <SEP> #0# <SEP> <SEP> #2# <SEP> = <SEP> -V2V1T
<tb> <SEP> 1 <SEP> -1 <SEP> 1 <SEP> 1
<tb> de sorte que les composantes Gh et Gv du gradient G s'obtiennent par
Gh = I * Mh = -V1IV2T, G = I *Mv = V2IV2T, ou I est la matrice 3 x 3 du pixel I(J, k) et de ses 8 proches vol- sins

<tb> <SEP> I(j <SEP> +1, <SEP> k <SEP> - <SEP> <SEP> 1) <SEP> I(j <SEP> +1, <SEP> k) <SEP> I(j <SEP> + <SEP> 1, <SEP> k <SEP> + <SEP> 1)
<tb> I <SEP> = <SEP> # <SEP> I(j, <SEP> k <SEP> - <SEP> 1) <SEP> I(j, <SEP> <SEP> k) <SEP> <SEP> I(j,k <SEP> + <SEP> 1) <SEP> # <SEP>
<tb> <SEP> I(j <SEP> - <SEP> 1, <SEP> k <SEP> - <SEP> 1) <SEP> I(j <SEP> - <SEP> 1, <SEP> k) <SEP> I(j <SEP> - <SEP> 1, <SEP> k <SEP> + <SEP> 1)
<tb>
Afin d'estimer l'orientation du vecteur gradient par une arctangente, les masques de Sobel ont ete utilisées, étant performants vis-à-vis de l'immunité du bruit. Par convolution avec l'image, les masques Mh et
Mv permettent de calculer les composantes du vecteur gradient associe a un pixel I (J,kS.Ces masques etant séparables, leur utilisation permet d'écrire le produit de convolution de maniere à réduire le nombre d'opérations arithmétiques à deux additions et une soustraction et de donner à l'opérateur de convolution une structure série, propice à l'exécution en temps réel.

Le schema de la figure 5 explique la structure de l'opérateur calculant les composantes du gradient. R est un registre série- parallele qui contient une colonne de 3 pixels d'image. Le pixel d'échantillonnage (pixel des contours de la fenetre) I (j - 1,k), les pixels des lignes précédentes I (J,k) et I (j + 1,k), sont disponibles à la sortie des registres à decalage non figurés dans lesquels on mémorise dynamiquement 2 lignes d'image.

R1 et R2 sont des registres série-parallèles qui memorisent les
T T éléments de V2 I et V1 I.

L'horloge CK d'échantillonnage du signal image active les registres.

Les composantes du vecteur gradient associé à un pixel sont determi- nées en synchronisme avec l'échantillonage du signal vidéo avec un retard de 256 + 3 périodes d'horloge par rapport au pixel de contour echantillonne. A chaque pixel est alors associé un vecteur gradient (//G//) caractéristique de ce pixel par comparaison du module de ce vecteur à un seull S. L'opérateur de Sobel effectue à la fois la détection des zones de contraste et la caractérisation des pixels appartenant à cette zone. Le choix d'un seuil, plus ou moins élevé, tendant à plus ou moins amincir les zones de contour (d'ob perte possible de contour), la selection des pixels de contours a été effectuée de façon plus elaboree.Dans ce but, un critère de sélection base sur le passage par un maximum dans la direction du gradient, du module de ce gradient a été retenu. Cette fonction est réalisée par un algorithme implementable en temps réel sur un processeur de meme structure que le processeur du calcul du gradient. Le passage par un maximum local est détecte en comparant le vecteur commun associe aux pixels du contour de la fenetre d'observation du capteur, avec ceux des plus proches voisins dans la direction du gradient. Le pixel non précédé ou non suivi d'un pixel dans la direction perpendiculaire au gradient est un pixel isolé et par suite élimine.

La figure 6 explicite la structure du processeur contenant cet algorithme. R1, R2, R3, R4 sont des registres série-parallèle qui contiennent le pixel analysé P et ses 8 plus proches voisins, A, B, C,
D, E, F, G et H tels qu'illustres par la figure 4 ou T représente la direction du contour, alors que represente celle du gradient du pixel P.

Les voisins dans la direction du gradient et ceux dans la direction du contour des cretes sont aiguilles au moyen de multiplexeurs commandes par l'orientation du vecteur gradient vers la logique de décision.

G ( - 1, k) represente le gradient des pixels du contour, les pixels des lignes précédentes sont disponibles à la sortie des registres à decalage non représentes qui mémorisent deux lignes d'image du gradient. Les pixels de contour sont valides en synchronisme avec l'échatillonnage avec un retard constant de 256 + 3 périodes d'horloge, par rapport aux pixels de contour de la fenêtre d'observation du capteur. Ainsi, on effecue en temps reel, le chaînage des pixels correspondant aux contours des crêtes.

L'analyse de l'image numerisee représentée à titre d'exemple par la rig. 2, implique les phases suivantes - on effectue un suivi double des lignes de contraste sans distinguer si ces lignes correspondent à une crete ou à un sillon de l'empreinte, en partant d'un des bords d'observation. L'information crete ou sillon peut, dans certains cas, etre difficilement accessible, en particulier lorsque l'image est de qualité médiocre. Pour cette raison, on ne cherchera pas à classer les points caractéristiques ou indices par types, mais on memorisera la direction courante de la ligne.

A cet effet, on utilise des operateurs d'analyse de lignes. Ces operateurs effectuent l'analyse des lignes de contraste. A leur base se trouve le calcul de gradient, effectue en temps reel par le processeur. Le suivi produit sequentiellement les points d'une ligne de contraste. Pour chaque point, différents operateurs d'analyse de lignes, sélectionnés explicitement, sont activés. Parmi Ces consommateurs de points, on trouve en particulier un calculateur de courbure et plusieurs algorithmes de decoupage de lignes en segments de droites. Les consommateurs implantes possedent une structure de coroutines, analysant une ligne de façon incrémentale (au fur et à mesure du suivi).Ceci permet de conférer au système plusieurs propriétés importantes : parmi ces proprietes on notera en priorite le grand gain de temps d'exécution du au fait que l'atteinte de l'objectif défini par l'utilisateur est detectée immediatement, ce qui permet de suspendre le suivi et l'analyse et de memoriser le contrôle, permettant ainsi d'éviter toute analyse superflue par rapport à l'objectif à atteindre. On notera egalement l'important gain de place de memoire dA au fait qu'il n'est pas necessaire de stocker les points d'une ligne avant de l'analyser, de sorte que la place memoire utilise par ces programmes est fixe et ne depend en aucun cas de la longueur d'une ligne de contraste.Ceci s'avère particulierement important si lsson considère qu'une ligne de contraste peut comporter plus de mille points. On notera également la grande souplesse d'utilisation due au fait que le systeme offre la possibilité de suivre l'execution d'un algorithme en pas-a-pas lors d'une experimentation ou lors de la mise au point. Dans ce but, le système dispose également de commandes generant des traces d'exécution plus ou moins detaillées.

- on détermine les arrêts du suivi. Le suivi de ligne est interrompu a chaque fois qu'il rencontre un indice de cause d'arrêt pouvant être un point caracteristique tel qu'une bifurcation, un arrêt de ligne, un flot, un crochet etc ... ou du plus simplement à une mauvaise qualité de l'image de l'empreinte à un endroit donné. Pour chaque arrêt, on détermine la position du curseur, c'est-à-dire ses coordonnees selon deux axes orthogonaux, la direction des deux lignes suivies
Jusqu'avant l'interruption et on associe à ces données un code de cause d'arrêt.

Le code de cause d'arrêt est fonction de la convergence ou de la divergence des lignes à l'approche d'un indice. A titre d'exemple, à l'approche d'un arret de ligne (crete ou sillon) les directions des deuX lignes de suivi double convergent. Un code allant par exemple de
1 à 4 peut être attribue à cette cause d'arret, selon le degre de convergence c'est-à-dire de l'angle de convergence des lignes du double suivi. A l'approche d'une bifurcation, les directions des deux lignes de suivi double divergent. Un autre code allant par exemple de 5 à 8 peut être attribué à cette cause d'arrêt en fonction de l'angle de divergence desdites lignes.

En résume, la determination des indices s'effectue en attribuant à chaque cause d'arrêt des coordonnees de position (X, Y), une orientation correspondant à la direction de ligne de suivi avant l'arrêt et un code d'arrêt numerote par exemple de 1 à 8.

- on extrait les indices et on modélise l'empreinte : au cours de cette phase, on mémorise pour chaque arret les coordonnees de position et le code d'arrêt, ce qui permet de constituer une image modélisée de l'empreinte. En pratique, une modélisation valable s'effectue sur la base de la détermination d'une trentaine de points d'arrêt.

- on fiabilise la modélisation de l'empreinte en la modelisant à plusieurs reprises pour établir une carte d'indices extraits correspondant au modele d'une empreinte, qui ne contient que les indices les plus significatifs, c'est-a-dire ceux que l'on détecte systematiquement lors de l'étape de modélisation.

A cette fin, les différentes cartes d'indices extraits obtenues sont cooptées afin de n'en garder que les parties communes.

On notera que les types de renseigements mémorisés, à savoir les caractéristiques des indices permettent de modeliser l'image de l'empreinte en s'affranchissant totalement de toute distorsion consécutive à l'élasticité de la peau. La cooptation des cartes d'indices permet de s'affranchir de tout calcul de referentiel difficile en raison de la configuration de l'image à traiter. Elle s'effectue par une recherche heuristique, au moyen d'un programme specifique permettant de realiser des transformations géométriques combinées de translation et de rotation.

Pour comparer deux modèles d'empreintes maître-esclave, le système se positionne sur un indice extrait du "modele esclave", caracterise par un code d'arrêt et ses coordonnees de position. Il cherche ensuite un indice extrait du modale maître" ayant le meme code d'arret. Il détermine alors la transformation géométrique qui permet d'accéder à l'indice le plus proche sur le modèle maître. Cette meme transformation ainsi calculee sera pratiquee sur le premier indice du modèle maître. Si alors la transformation permet d'atteindre un indice esclave de meme caracteristique que celui auquel le dispositif a accéde sur le modèle maître, un autre indice sur le modèle maître sera recherche de la même manière et ainsi de suite jusqu'a l'identification formelle de la cooptation possible des deux modèles. Dans le cas contraire, le système se positionne sur un autre indice du modèle maître de meme code que le premier considéré lors du démarrage de l'analyse, et poursuit cette dernière Jusqu'a ce qu'une transformation géométrique calculee sur le modèle maître puisse être appliquée avec réusite sur le modèle esclave.

Afin d'eviter une perte de temps inutile, le système est conçu pour réaliser deux types de pré-traitements avant tout depart de suivi de contour.

D'une part, un filtrage numerique realise un produit de convolution afin de lisser les lignes de contraste. D'autre part, suite à ce filtrage, on met en oeuvre un algorithme de recherche du contour général des lignes de contrastes de l'image Ce contour général est mis en mémoire à l'aide d'une vingtaine de segments de droites repre- sentatifs de la forme globale de l'empreinte digitale. Ainsi, pour chacune des lignes traitees par le suivi de contour, l'allure générale de la ligne suivie sera connue.Lors d'un arrêt du suivi, l'analyse de la cause d'arrêt s'effectue de la maniere suivante 1) le curseur de suivi est stoppé à l'emplacement d'un point caracteristique et l'algorithme de reconnaissance du point specifique pourra alors se dérouler, 2) le curseur ne reconnaît aucun point et le logiciel est alors capable de detecter si la direction du contour relevé est compatible avec la direction générale des lignes de l'empreinte. Dans le cas contraire l'arrêt du suivi est leve.

L'etude dés zones de l'image mal definie s'effectue de la même manière; c'est notamment le cas des zones de l'empreinte recouvertes de masques correspondant à la presence de matière indésirable sur la peau du doigt.

Le résultat de la cooptation des differentes cartes d'indices extraits aboutit à la clé caracteristique de l'empreinte digitale d'un individu. L'apposition de cette clé sur un document caractérise le document de maniere certaine. La reconnaissance de cette clé à partir d'une lecture d'empreinte digitale certifie l'identification formelle de l'individu.

Etant donne que toute cette analyse aecrite ci-dessus s'effectue en temps reel, le procede de l'invention ouvre de tres vastes domaines d'application. La clé individuelle étant marquee sur une pièce d'identité, la comparaison de cette cle avec celle determinée instantanément par le système de contrôle de l'empreinte digitale tel que décrit cidessus, permet de certifier l'identité de l'individu porteur de la pièce d'identité.

Pour qu'un tel procéde soit applicable en pratique, il convient de rendre la piece d'identité inviolable. A cet effet, il est nécessaire d'enregistrer la cle de manière inaltérable. La carte à microcalculateur dite puce électronique à mémoire, permet de memoriser de façon inaltérable la cle caractéristique des empreintes digitales d'un individu ainsi d'ailleurs que de nombreux autres renseignements.

Le dispositif de mise en oeuvre du procédé de l'invention, qui travaille en temps réel, pourrait etre installé dans les portes frontières pour assurer un contrôle systématique absolument sur de tous les individus traversant les frontières. Le schéma de principe d'une telle installation est illustre par la figure 7 qui montre un ordinateur central 50 auquel sont reliés les organes suivants : une unité 51 de lecture de l'empreinte digitale comprenant un capteur tel que représenté par la figure 1, une unité 52 de lecture de la clé inscrite sur la carte d'identité et une unité 53 de lecture d'une carte d'habilitation.Par ailleurs, l'ordinateur central 50 est relie à un fichier 54 des suspects, à un écran de visualisation 55 pouvant afficher les données lues par les unités 51, 52 et 53, à un pupitre de commande 56 permettant au contrôleur d'autoriser ou de refuser le passage (feux vert 57, jaune 58 ou rouge 59), et éventuellement à un réseau téléinformatique 60. Une unite d'impression de la cle individuelle peut être raccordée au pupitre de commande.

Il est bien evident que les équipements peripheriques de l'ordinateur central 50 pourraient être complétés ou modifies. Le schéma décrit n'illustre qu'une utilisation pratique du système de l'invention.

Les organes de l'appareil permettant de réaliser les différentes phases du procédé sont illustrés schématiquement par la figure 3. Ces organes comprennent une caméra de télévision 30 qui transmet des signaux à l'unité de numérisation 31 de l'image. L'image numérisée est utilisée par une unité 32 de calcul des composantes du gradient qui est reliée à l'unité 33 de calcul du module du gradient et de codage de l'orientation du vecteur gradient. Ces informations sont directement utilisées par une unité 34 d'extraction des zones de contraste connectées à un calculateur 35 et à un moniteur de contrôle 36. On notera que le moniteur de contrôle 36 est également directement relié à l'unité de numérisation 31 pour permettre l'affichage direct de l'image numérisée.

Claims (22)

Revendications

1. Procede d'identification d'une empreinte digitale d'un individu, dans lequel on procède à l'acquisition de l'image de cette empreinte par un procédé optique, puis à la reconnaissance automatique d'un nombre déterminé points caractéristiques de cette image, et à la comparaison de ces points caractéristiques avec ceux d'images acquises précédemment, caractérise en ce que l'on calcule pour cette image une clé spécifique de l'empreinte, cette clé étant définie en fonction d'un nombre de points caracteristiques, selectionnes comme étant représentatifs de l'image de l'empreinte.

2. Procede selon la revendication 1, caracterise en ce qu'on effectue l'acquisition de l'image optique au moyen d'une caméra de télévision à réseau de 255 lignes à 256 points. et en ce qu'on transforme l'image carre en une Image rectangulaire de 280 lignes a 380 points.

3. Procede selon la revendication 2, caracterise en ce qu'on procède à la numérisation de l'image optique préalablement acquise, en quantifiant le niveau de luminosite sur un nombre defini de niveaux de gris, en determinant en temps réel les composantes horizontale et verticale du vecteur gradient associe a chaque pixel, en calculant le module et l'orientation du vecteur gradient, et en selectionnant les pixels appartenant aux contours par recherche d'un maximum local du module du gradient dans la direction du vecteur gradient.

4. Procédé selon la revendication 3, caracterise en ce qu'on mémorise l'image numerisee et en ce qu'on construit une image binaire de l'empreinte digitale en traçant les lignes de contraste reliant les points de contraste connexes et en effectuant un decoupage de ces lignes en segments géométriques caractérises par la courbure.

5. Procede selon la revendication 1, caractérisé en ce que l'analyse de l'image binaire comporte une phase de suivi double des lignes de contraste, ces lignes de contraste etant indlfteremment les images des crêtes ou des sillons de l'empreinte digitale.

b. Procède selon la revendication 5, caracterise en ce que l'analyse de l'image binaire comporte une phase de detection des indices de caused'arrêt qui s'effectue en déterminant les arrêts du suivi double des lignes de contraste.

7. Procede selon la revendication 6, caracterise en ce qu'on attribue un code de cause d'arret-a a chaque indice de cause d'arret.

Procéde selon la revendication 7, caracterise en ce que le code de cause d'arret est fonction de la divergence ou de la convergence des lignes du suivi double à l'approche d'un indice.

9. Procédé selon la revendication 8, caractérisé en ce que les codes de cause d'arrêt sont echelonnes de 1 a 8.

10. Procede selon la revendication 5, caractérise en ce que la dXter- mination des indices s'effectue en attribuant à chaque cause d'arret des coordonnees de position, une orientation correspondant à la ligne du suivi avant l'arrêt et un code d'arrêt numéroté de 1 à 8.

11. Procédé selon la revendication 10, caractérise en ce qu'on mode lise l'empreinte en memorisant pour chaque arret les coordonnees de position et le code d'arret.

12. Procédé selon la revendication 11, caractérisé en ce que la modelisation de l'empreinte s'effectue sur la base de trente points d'arret.

13. Procédé selon les revendications 1 et 12, caractérisé en ce qu'on fiabilise la modélisation de l'empreinte en la modélisant à plusieurs reprises pour établir par cooptation une carte d'indices extraits correspondant au modèle d'une empreinte, qui ne contient que les indices les plus significatifs, cette carte d'indices extraits permettant de definir ladite cle caracteristique de l'empreinte.

14. Dispositif pour la mise en oeuvre du procede selon l'une quelconque des revendications precedentes, caractérisé en ce qu'il comporte des moyens pour saisir optiquement l'image d'une empreinte digitale, des moyens pour analyser cette image et des moyens pour déterminer une clé caractéristique de l'empreinte analysée.

15. Dispositif selon la revendication 14, caractérise en ce que les moyens pour saisir optiquement l'image de l'empreinte comportent une camera de television et des moyens pour numériser l'image optique.

16. Dispositif selon la revendication 15, caracterise en ce que les moyens pour numériser l'image comportent des organes pour quantifier le niveau de luminosite sur un nombre défini de niveaux de gris, pour determlner en temps réel les composantes horizontale et verticale du vecteur gradient associe à chaque pixel, pour calculer le module et l'orientation du vecteur gradient et pour sélectionner les pixels appartenant aux contours par recherche alun maximum local du module du gradient dans la direction du vecteur gradient.

17. Dispositif selon la revendication 16, caracterise en ce qu'il comporte des moyens pour memoriser l'image numérisée et des moyens pour construire une image binaire de l'empreinte digitale en traçant les lignes de contraste reliant les points de contraste connexes et en effectuant un découpage de ces lignes en segments géometriques caractérises par la courbure.

18. Dispositif selon la revendication 14, caractérisé en ce qu'il comporte des moyens pour analyser l'image binaire de l'empreinte digitale equipes d'un dispositif conçu pour effectuer un suivi double des lignes de contraste de cette image.

19. Dispositif selon les revendications 14 et 18, caracterise en ce qu'il comporte des moyens pour detecter des indices de causes d'arrêt en déterminant les arrêts du suivi double des lignes de contraste.

2ü. Dispositif selon la revendication 19, caractérisé en ce qu'il comprend des moyens pour attribuer un code de cause d'arrêt à chaque indice de cause d'arret.

21. Dispositif selon la revendication 20, caractérise en ce qu'il comprend des moyens pour attribuer pour chaque indice, des coordonnées de fonction, une orientation correspondant a la ligne du suivi avant l'arrêt et un code d'arret numéroté.

22. Dispositif selon la revendication 14, caractérisé en ce qu'il comporte des moyens pour modéliser l'empreinte.

23. Dispositif selon les revendications 14 et 22, caractérisé en ce qu'il comporte des moyens pour fiabiliser la modélisation de l'empreinte, des moyens pour établir une carte d'indices extraits correspondant au modele de l'empreinte et et des moyens pour définir ladite cle caractéristique de l'empreinte.

24. Utilisation du procédé selon la revendication 1, caractérisée en ce que l'on appose de manière inaltérable ladite cle caractéristique de l'empreinte digitale sur une piece d'identite d'un individu.

25. Utilisation selon la revendication 24, caracterisee en ce qu'on contrôle l'identité d'un individu, en comparant en temps réel la cle correspondant à analyse directe de son empreinte digitale avec celle de sa piece d'identité.