Brevet FR3107132A1 — publié le 20210813

Procédé d’identification d’un individu à partir d’informations contenues dans une base de données volumineuse comportant au moins les étapes suivantes: - Pour chaque donnée biométrique, calculer un gabarit binaire lié à chaque paramètre caractéristique d’une donnée biométrique, (402), - Utiliser une méthode de hachage afin d’obtenir plusieurs index pour chaque gabarit binaire, (403), - Pour chaque index obtenu pour une donnée biométrique, insérer un identifiant correspondant à la donnée biométrique minimisant la distance de Hamming entre l’index considéré et des index synthétiques correspondant à un ensemble d’intervalles autour d’un centre de classe (401) bornant ladite case, afin d’obtenir des couples {identifiant donnée biométrique, identifiant individu}, (404), - Capturer au moins une donnée biométrique propre à l’individu au moyen d’un capteur adapté, (405), - Rechercher (408) dans la table la ou les données biométriques les plus proches et émettre un résultat d’identification ou de rejet de l’indentification de l’individu, (406). Figure pour l’abrégé: figure 4 Procédé et dispositif pour identifier un individu à partir d’une donnée biométrique L’invention concerne un procédé et un dispositif permettant d’identifier un individu à partir d’une donnée biométrique. La donnée biométrique peut être des empreintes digitales, un visage, l’iris. L’identification d’un individu se fait habituellement en utilisant des données mémorisées dans une base de données qui se révèle être volumineuse lorsque l’on utilise des empreintes digitales, la taille de la base (ordre de l’échelle d’un pays, nombre d’individus par pays) peut être de l’ordre de 10 7 . La comparaison exhaustive des empreintes de l’individu recherché avec les N jeux d’empreintes de la base de données est donc très coûteuse en temps de calcul. Différentes solutions existent dans l’art antérieur pour classifier ou indexer des empreintes, afin de pouvoir sélectionner un sous-ensemble de la base de données contenant les empreintes les plus ressemblantes à celles de l’individu recherché et diminuer le volume de données à utiliser pour la comparaison. Une des méthodes d’indexation est la technique basée sur des structures de données 3D (appelées cylindres), construites à partir de distances et d'angles minutieux, plus connue sous l’abréviation anglo-saxonne «MCC» (Minutia Cylinder-Code). Cette méthode consiste à représenter chaque minutie de l’empreinte en considérant son voisinage local. Le voisinage local d’une minutie présente le comportement de cette minutie centrale par rapport à ses voisins proches. Cette représentation locale du voisinage de la minutie se fait en format binaire utilisant uniquement des «0» et des «1». La méthode d’indexation MCC utilise donc une représentation binaire des gabarits en considérant chaque minutie de l’empreinte comme une suite binaire. Un gabarit MCC T est une collection de |T| minuties binaires de longueur . L’indexation MCC consiste à construire des index sur chaque minutie du gabarit de référence reçu à l’enrôlement d’individus. Pour l’identification de l’individu, la méthode extrait toutes ces minuties au format binaire. Ensuite, pour chacune de ces minuties, on calcule les index en utilisant des fonctions de hachage, puis on compte les différentes collisions avec les individus déjà enrôlés dans la base. Lorsque l’on met en œuvre cette méthode, la perte d’un index a un impact important, car elle correspond à une perte d’information et à une augmentation possible du taux d’erreur pour l’identification. De plus, cette méthode nécessite la création d’une table d’index très volumineuse. Une telle méthode n’est donc pas vraiment adaptée pour adresser des problèmes d’identification à grande échelle et dans un laps de temps contraint. Un des objectifs de la présente invention est d’offrir un procédé d’identification d’un individu au moyen de données biométriques qui corrige notamment la perte éventuelle d’informations sur l’enrôlement et l’identification des gabarits afin d’optimiser les chances d’identification d’un individu. De plus cette méthode, du fait de la création de centres de classes et d’index synthétiques, permet une recherche plus rapide dans des bases de données volumineuses. Ces bases de données sont de l’ordre de l’échelle d’un pays par exemple 10 7 individus. Dans la suite de la description, le terme «représentatif» signifie que les index synthétiques créés sont en nombre suffisant pour couvrir l’espace de l’ensemble des index nécessaires pour réaliser le stockage d’une base de données biométriques, par exemple des empreintes digitales. Le terme « discriminant» signifie que les index synthétiques ne se chevauchent pas, sont uniques et suffisamment distant deux à deux. Le terme «gabarit» désigne les mesures qui sont mémorisées lors de l’enregistrement des caractéristiques morphologiques (empreinte digitale, forme de la main, iris, ...), biologiques ou comportementales de la personne concernée. Par abus de langage, on utilisera l’expression «donnée biométrique» pour désigner aussi les caractéristiques comportementales d’une personne. L’invention concerne un procédé d’identification d’un individu à partir d’informations contenues dans une base de données volumineuse caractérisé en ce qu’il comporte au moins les étapes suivantes: - Générer ou utiliser une table contenant des index synthétiques correspondant à un ensemble d’intervalles autour d’un centre de classe, - Enrôler plusieurs données biométriques en exécutant les étapes suivantes: - Pour chaque donnée biométrique à enrôler, calculer un gabarit binaire lié à chaque paramètre caractéristique d’une donnée biométrique, - Utiliser une méthode de hachage afin d’obtenir plusieurs index pour chaque gabarit binaire, - Pour chaque index obtenu pour une donnée biométrique, insérer un identifiant correspondant à la donnée biométrique minimisant la distance de Hamming entre l’index considéré et les index synthétiques bornant ladite case, afin d’obtenir une table contenant des couples {identifiant donnée biométrique, identifiant individu}, - Capturer au moins une donnée biométrique propre à l’individu au moyen d’un capteur adapté, - Rechercher dans la table (contenant les index synthétiques) la ou les données biométriques les plus proches, comparer la donnée biométrique capturée aux données biométriques de la base de données d’enrôlement et générer un résultat d’identification en cas de correspondance entre lesdites données comparées ou de non identification de l’individu et traiter le résultat obtenu. Selon une variante, on utilise les empreintes digitales pour identifier un individu et on exécute les étapes suivantes: - Enrôler plusieurs empreintes en exécutant les étapes suivantes: - Pour chaque empreinte, calculer un gabarit binaire lié à chaque minutie d’une empreinte en utilisant une méthode MCC, - Utiliser une méthode de hachage afin d’obtenir plusieurs index pour chaque gabarit binaire, - Pour chaque index obtenu pour une empreinte, insérer un identifiant correspondant à l’empreinte minimisant la distance de Hamming entre l’index considéré et les index synthétiques bornant ladite case, afin d’obtenir une table contenant des couples {identifiant minutie, identifiant individu}, - Capturer au moins une empreinte propre à l’individu au moyen d’un capteur adapté, transformer ladite empreinte en un format numérique binaire, - Rechercher dans la table des index synthétiques la ou les empreintes les plus proches et identifier l’individu ou rejeter l’identification en comparant le code binaire généré aux minuties mémorisées dans la table d’index. Pour générer une table contenant des index synthétiques, le procédé peut exécuter les étapes suivantes: Soit h une fonction de hachage et les paramètres conditionArrêt1, conditionArrêt2 , , ɛ , MaxDH , min, ST, SI, Avec conditionArrêt1 et conditionArrêt2 deux «timers» de valeurs choisies pour stopper les boucles de recherche d’index synthétiques à ajouter dans la table d’index, , la probabilité de générer un bit à ‘1’ sur un index synthétique en utilisant une distribution de Bernoulli, ɛ, la distance entre deux index voisins d’un même centre de classe, avec ɛ ∈ [3, 7], MaxDH : le maximum de la distance de Hamming, min : un paramètre de rejet ou seuil minimal de rejet sur le nombre de ‘1’, nombre minimum de bits à ‘1’ pour valider un index synthétique, ST : l’ensemble des centres de classes, SI : l’ensemble des index synthétiques en sortie, h la taille de la fonction de hachage, Initialiser Etape 1 - Créer des index cibles centres IC i de classes éloignés afin de couvrir l’espace des index, ! Tant que conditionArrêt1 alors: Créer un index i en générant h bits avec une distribution de Bernoulli , où dH(i, j) est la distance de Hammnig entre l’index et l’index , le nombre total de bits divergeant entre deux vecteurs binaires , Sinon valider l’index i comme un centre de classe {index i centre de classe valide} et l’ajouter à l’ensemble des centres de classes ST←ST + {i} Fin de la boucle Si Fin de l’étape 1 Etape 2 – Créer autour de chaque index centre de classe IC i , des index proches sans chevauchement: Tant que! exécuter la boucle suivante: Créer un index en générant bits avec une distribution de Bernoulli si Sinon considérer l’index comme un index synthétique valide Mettre à jour l’ensemble des index correspondant à des intervalles autour d’un centre de classe , = ensemble des intervalles autour d’un centre, Fin de la boucle Fin de tant que Fin de l’étape 2 Générer un ensemble des index synthétiques qui comprend des centres de classes et des intervalles autour de ces centres de classes . La phase d’enrôlement d’un individu dans une base utilise, par exemple, les index créés dans la table d’index synthétiques et comporte les étapes suivantes: Pour chaque empreinte digitale: - Un calcul des gabarits binaires liés à chaque minutie à partir de la méthode MCC, - L’obtention de plusieurs index pour chaque gabarit binaire en utilisant une fonction de hachage, - L’insertion de l’identifiant de l’empreinte dans plusieurs cases d’une table: pour chaque index obtenu pour une empreinte, on insère dans une case l’identifiant de l’empreinte qui minimise la distance de Hamming entre l’index considéré et les index synthétiques bornant la case, - A l’issue de cette étape, la table est complétée avec les identifiants des empreintes réelles d’individus qui constituent une base de données. Le procédé peut aussi comporter les étapes suivantes: Soit le gabarit, un ensemble de fonctions de hachage, le nombre de fonctions de hachage, la base de données des index synthétiques préalablement créée lors de la phase d’initialisation, initialisation de l’ensemble des index synthétiques, Pour chaque minutie , Pour chaque fonction de hachage , faire la distance de Hamming entre b et SI Enrôler sur et de la fonction Finpour Finpour et sont les bornes inférieure et supérieure de l’intervalle qui encadre l’index calculé pour chaque minutie du gabarit à enrôler. L’identification d’une empreinte d’un individu comporte, par exemple, les étapes suivantes: Soit , ; ensemble des index synthétiques établi précédemment, l’ensemble des gabarits contrôlés, la liste des candidats probables avec le score d’accumulation de chaque individu, , Initialiser un compteur de score , Pour chaque minutie , Pour chaque fonction de hachage , Initialiser un compteur de collisions , Les fonctions et calculent respectivement le premier et le deuxième minimum d’index au sens de la distance de Hamming dH entre un index en entrée et une collection d’index, Pour chaque gabarit trouvé sur les index et Pour chaque minutie j trouvée en collision sur , , lire la collision en comptant chaque ligne( , ) de , , puis en l’ajoutant dans le compteur de collision , Compter les gabarits en collision FinPour FinPour FinPour Mettre à jour la table des scores pour un gabarit FinPour Créer la liste des candidats en rangeant par ordre décroissant et utiliser le candidat ayant la plus forte valeur de score pour l’étape d’identification. La fonction de hachage est, par exemple, une function de hachage sensible à la similarité plus connue sous l’abréviation anglo-saxonne LSH (Locality Sensitive Hashing). Le procédé peut aussi comporter une étape supplémentaire d’émission d’un signal d’ouverture d’un portique suite à l’identification d’un individu. L’invention concerne aussi un système d’identification d’un individu comportant un dispositif d’acquisition d’une donnée biométrique dudit individu, relié à un dispositif de traitement de données comprenant une base de données, un processeur configuré pour exécuter les étapes du procédé selon l’invention, un dispositif de traitement du résultat d’identification, ladite base de données comprenant une table d’index synthétiques correspondant à un ensemble d’intervalles autour d’un centre de classe. Le dispositif de traitement du résultat de l’identification est un dispositif d’affichage ou encore un dispositif générant un signal de commande d’ouverture d’un moyen d’accès à une zone. Le dispositif d’acquisition est, par exemple, un dispositif de lecture d’empreintes et la donnée biométrique une empreinte. D’autres caractéristiques, détails et avantages de l’invention ressortiront mieux à la lecture de la description faite en référence aux dessins annexés donnés à titre d’exemple non limitatifs et qui représentent, respectivement: Une illustration d’un système d’identification utilisant le procédé selon l’invention, Un schéma de principe d’identification d’un individu, Une représentation des index centres de classes et des index synthétiques générés par le générateur d’index synthétique, les index sont utilisés lors de l’enrôlement et de l’indentification d’un individu, Les étapes pour l’identification d’un individu, Les étapes pour la construction d’un gabarit binaire pour une empreinte, Une comparaison entre le processus de création des index pour une empreinte selon le procédé de l’art antérieur et l’utilisation des index synthétiques créés pour l’indexation des empreintes mettant en œuvre le procédé selon l’invention. Le procédé selon l’invention utilise des gabarits représentés sous forme binaire et repose notamment sur la mise en œuvre des étapes suivantes: lors d’une première phase sur la génération d’un sous-ensemble d’index représentatifs et discriminants, qui conduit à la création d’une table d’index synthétiques (c’est l’initialisation du système). La deuxième phase consiste à enrôler une base d’empreinte digitales en exploitant la table créée à la phase d’initialisation. Et enfin la troisième phase est l’identification d’une empreinte digitale dans la base des empreintes enrôlées. Ces trois phases sont détaillées ci-après. La figure 1 illustre un exemple de système d’identification pouvant mettre en œuvre le procédé selon l’invention. Un tel système comprend, par exemple, un dispositif 1 d’acquisition de données biométriques, par exemple un lecteur d’empreintes relié à un dispositif de traitement 2 des données comprenant une base de données 3 dans laquelle sont mémorisées les données biométriques, un processeur 4 pour exécuter les étapes du procédé selon l’invention, un dispositif d’affichage 5 du résultat d’identification. La base de données comprend aussi la table générée après enrôlement d’une base d’empreintes. Une première application du procédé selon l’invention consiste, par exemple, à vérifier l’unicité d’une identité au sein d’une population, c’est-à-dire qu’un jeu de données biométriques n’est relié qu’à un seul jeu de données d’état civil au sein d’une base de données. Pour cela, on acquiert lors d’une phase d’enrôlement les données biométriques, par exemple les empreintes digitales à l’aide d’un capteur biométrique et les données d’état civil d’un individu à l’aide d’un dispositif d’acquisition adapté. Ces données sont ensuite transmises à un système d’identification biométrique qui va rechercher au sein des données biométriques présentes dans une base, des empreintes qui correspondraient aux nouvelles empreintes acquises. Si les empreintes acquises lors du procédé correspondent à des empreintes contenues dans cette base de données, l’étape suivante consistera à vérifier si «l’identité civile» enregistrée avec ces empreintes correspond à l’identité de la personne pour laquelle le système vient d’acquérir ces empreintes. Pour cela, le système comprendra un module configuré pour exécuter cette comparaison entre les données d’identité civiles et émettre un signal d’alerte, en affichant par exemple, une information de non correspondance entre les données civiles déjà présentes dans la base de données et les données civiles nouvellement enregistrées. Le résultat de la comparaison effectuée au niveau du processeur 4 peut générer un signal de commande d’ouverture d’un portique permettant l’accès 6 à une zone protégée lorsque le résultat d’identification de la personne est positif. Le portail recevra un signal permettant son ouverture générée par le processeur si l’identification d’un individu est validée. Le capteur d’acquisition des données biométriques peut aussi être un dispositif de lecture d’iris, lorsque les données traitées sont des caractéristiques de l’iris d’un individu. On pourra aussi utiliser une caméra configurée pour extraire des données biométriques faciales, ou encore un capteur vocal si les données permettant d’identifier l’individu sont des paramètres vocaux, des vecteurs cepstraux. La figure 2 illustre le principe d’identification d’un individu en utilisant des index spécifiques générés lors de la phase d’initialisation du procédé selon l’invention. Cette phase d’initialisation sera exécutée avant le premier enrôlement. Lorsque l’on souhaite identifier un individu, une requête d’identification Rq est émise. Les données biométriques acquises par le lecteur d’empreintes sont transmises, 21, au processeur 4 qui va les comparer en utilisant la base de données 3 des individus déjà enrôlés et connus par le système. La phase d’enrôlement consiste à réaliser un enrôlement par intervalle pour les index du gabarit. Cet enrôlement par intervalle exploite les index synthétiques générés précédemment en utilisant l’algorithme de génération d’index synthétiques de la phase d’initialisation. Lors de l’enrôlement, le procédé va utiliser l’ensemble des index synthétiques générés, puis calculer les intervalles d’index synthétiques pour chacune des minuties du gabarit afin de les enrôler sur le ou les intervalles les plus proches. La première phase d’initialisation du procédé selon l’invention comporte les étapes détaillées ci-après. Elle comporte dans un premier temps une construction d’index éloignés les uns des autres. Ces index constituent des centres de classe représentés par des carrés IC i (IC 1 ,….IC 9 ) sur la figure 3 et qui couvrent l’espace des index possibles. Dans un deuxième temps la phase comprend une construction autour de chaque centre de classes, des intervalles d’index suffisamment proches les uns des autres, tout en évitant le chevauchement, représentés par des cercles 31 sur la figure 3. Les valeurs indiquées dans les cercles sont par exemple: (1,1), (1,2), ..., (9,4). La première phase du procédé comporte les étapes suivantes: Soit une fonction de hachage et les paramètres conditionArrêt1, conditionArrêt2 , , ɛ , MaxDH , min, ST, SI , Avec conditionArrêt1 et conditionArrêt2 deux «timers» choisis pour stopper les boucles de recherche d’index synthétiques à ajouter, ces timers ont des valeurs prédéfinies et choisies en fonction du compromis temps de calcul, précision du résultat dans la recherche d’empreintes, , la probabilité de générer un bit à ‘1’ sur un index synthétique en utilisant une distribution de Bernoulli, ɛ, la distance entre deux index voisins d’un même centre de classe, avec ɛ∈ [3,7], MaxDH le maximum de la distance de Hamming, min un paramètre de rejet ou seuil minimal de rejet sur le nombre de ‘1’, nombre minimum de bits à ‘1’ pour valider un index synthétique ST L’ensemble des centres de classes, SI l’ensemble des index synthétiques en sortie, obtenus par le procédé, h La taille de la fonction de hachage (le nombre de bits fixés et sélectionnés pour le hachage par chaque fonction), Initialiser Etape 1 - Créer des index cibles centres de classes, IC i , assez éloignés pour couvrir l’espace des index, ce qui conduit à créer un ensemble représentatif, ! Tant que conditioArrêt1 alors: Créer un index en générant bits avec une distribution de Bernoulli , Si Où dH (i, j) est la distance de Hammnig entre l’index i et l’index j , i.e., le nombre total de bits divergeant entre deux vecteurs binaires , et Sinon valider l’index i comme un centre de classe {index i centre de classe valide} et l’ajouter à l’ensemble des centres de classes Fin de la boucle Si Fin de l’étape 1. Les index d’une façon générale sont des vecteurs binaires constitués de «0» et de «1». Un index comprenant un nombre trop important de zéros ne permet pas de discriminer les éléments. Par exemple, pour obtenir un index discriminant on choisira un index comprenant au moins cinq valeurs de «1». Etape 2 – Créer autour de chaque index centre de classe IC i , des index relativement proches sans chevauchement: Tant que ! conditionArrêt2 exécuter la boucle suivante: Créer un index en générant bits avec une distribution de Bernoulli si Sinon considérer l’index comme un index synthétique valide { index synthétique final i valide} Mettre à jour l’ensemble des index correspondant à des intervalles autour d’un centre de classe ST j ← ST j + {i}, ST j = ensemble des intervalles autour d’un centre, Fin de la boucle Fin de tant que Fin de l’étape 2 Générer un ensemble des index synthétiques qui comprend des centres de classes et des intervalles autour de ces centres de classes A la fin de la phase d’initialisation, on dispose d’un ensemble d’index synthétiques. La figure 3 est un schéma représentatif de la répartition des index synthétiques créés par l’exécution des étapes de la phase d’initialisation. Les index cibles centres de classe sont créés par l’exécution de l’étape 1 et indiqués par leur numéro, IC 1 ,…, IC 9 dans cet exemple. Sur l’espace global de recherche, une distance importante entre ces centres de classes se traduit par une grande distance de Hamming MaxDH . Les index synthétiques sont caractérisés par un couple (a, b), a indiquant le centre de classe de provenance et b son numéro unique dans cette classe. Chaque index synthétique est unique, il délimite l’étendue de son centre de classe et évite le chevauchement respecté par la distance de Hamming minimale dans l’étape 2. L’index synthétique constitue une borne d’intervalle. La fonction nombreMinimumDe1(i) permet de compter le nombre de `1' contenus dans un index créé et utilise la variable comme seuil minimal de rejet sur le nombre de `1'. La figure 4 illustre les étapes permettant l’exploitation des index synthétiques pour réaliser l’enrôlement puis l’identification d’un individu par la suite en utilisant le procédé de l’invention. La deuxième phase du procédé est une phase d’enrôlement d’un individu 407. Elle est réalisée en utilisant les index synthétiques 401 générés lors de la phase d’initialisation. La phase d’enrôlement 407 va comporter pour chaque empreinte digitale: - Un calcul des gabarits binaires liés à chaque minutie à partir de la méthode MCC, 402, - L’obtention de plusieurs index pour chaque gabarit binaire grâce à plusieurs fonctions de hachage, par exemple la méthode LSH, 403, - Pour chacune des minuties du gabarit on génère quelques index grâce à une technique de hachage, puis on calcule les index synthétiques les plus proches de ces index par distance de Hamming (en faisant appel à la table des index de l’initialisation 401). Ces index synthétiques sont ceux qui ont été créés à l’initialisation et représentent les bornes d’intervalles utilisés pour réaliser cette phase d’enrôlement. Pour chacune des minuties, après avoir calculé les bornes d’intervalles synthétiques, on va enrôler ces minuties sur lesdites bornes. C’est-à-dire que pour chaque index de chaque minutie, on écrit sur la borne correspondante, le numéro de la minutie ainsi que l’identifiant de l’individu (l’identifiant est soit son nom ou son matricule renseigné). On crée ainsi une table d’index représentant l’enrôlement des individus de la base. Chaque ligne de la table des index contient des couples (m i ,j) où m i indique le numéro de la minutie du gabarit de l’individu d’identifiant j que l’on essaye d’enrôler. Il faut noter que chaque index k de la table d’index a été créé préalablement de façon synthétique et est utilisé ici comme borne pour l’enrôlement de chacune des minuties des individus. - A l’issue de cette étape, la table d’index est complétée avec les identifiants des empreintes réelles d’individus qui constituent la base de données, 404. Pour réaliser l’enrôlement d’un individu, on suppose que le gabarit T est au format binaire avec, pour chaque minutie de l’empreinte digitale de l’individu, une longueur qui peut aller jusqu’à plus de 1500 bits. On suppose également que la phase d’initialisation a déjà été exécutée au moins une fois pour initialiser le système. Le procédé va calculer pour chaque minutie de l’empreinte, les deux index synthétiques les plus proches au sens de la distance de Hamming par rapport aux index synthétiques déjà générés (lors de la phase d’initialisation). Le procédé va enrôler la minutie sur deux index synthétiques les plus proches, c’est ce que l’on appelle “enrôlement par intervalle”. Les étapes mises en œuvre pour cet enrôlement sont les suivantes: Soit T le gabarit, F = {f h1 , … f hl } ; un ensemble de fonctions de hachage, le nombre de fonctions de hachage, la base de données des index synthétiques préalablement créée lors de la phase d’initialisation, SI ≠ø initialisation de l’ensemble des index synthétiques, Pour chaque minutie m i de T , Pour chaque fonction de hachage f hk de F, faire b = f hk ( m i ) b 1 = min 1 { dH b, SI)} dh la distance de Hamming entre b et SI b 2 = min 2 { dH b, SI)} Enrôler m i sur b 1 et b 2 , de la fonction f hk en écrivant ( m i , T ) sur les nouvelles lignes de la table des index aux numéros b 1 et b 2 Finpour Finpour; b 1 et b 2 sont les bornes inférieure et supérieure de l’intervalle qui encadre l’index b calculé pour chaque minutie du gabarit à enrôler. La troisième phase correspond à une phase d’identification d’une empreinte 408. On va rechercher dans la base d’empreintes enrôlées lors de la phase d’enrôlement 404, les empreintes les plus proches de la nouvelle empreinte acquise 405 pour l’identification. Pour identifier un gabarit binaire (ensemble de minuties) d’un individu, le procédé va rechercher pour chaque index de chacune des minuties les deux index synthétiques les plus proches. Sur les deux index synthétiques représentant les bornes trouvées, le procédé consulte chaque ligne de la table des index et lit en comptant sur chacune d’elle les minuties ainsi que les identifiants de gabarits correspondants et précédemment enrôlés. Le procédé va donc incrémenter une table de score correspondant au score de similarité de chaque gabarit retrouvé sur les bornes synthétiques de lecture. La première partie est une étape d’extraction correspondant à une capture d’une donnée biométrique 405, puis un calcul de gabarit binaire 402. La deuxième partie va lire et compter un ensemble de collisions pour les gabarits qui appartiennent aux mêmes index synthétiques pour chacune des fonctions de hachage en exploitant le résultat de la fonction de hachage 403, la recherche dans la base des empreintes enrôlées 406 et dans la table des index synthétiques 404. L’étape d’identification se fait en deux étapes que sont l’extraction du gabarit binaire (capture biométrique 405 et calcul de gabarit binaire 402) puis l’identification elle-même ensuite. Dans la première partie, le procédé va extraire le gabarit binaire correspondant, 402. Dans la deuxième partie de l’identification, le procédé va compter le score de similarité relatif à chaque minutie au travers de chacune des fonctions de hachage. C’est le score de similarité exprimé précédemment. Il est aussi appelé collision dans la description de l’algorithme. Lire une collision consiste pour une minutie, après avoir trouvé les index synthétiques représentant les bornes, à compter toutes les minuties des gabarits précédemment enrôlés afin d’incrémenter la table des scores. La collision est lue par l’étape 403 suivie de l’étape de recherche dans la table de correspondance et la génération d’un signal 406 et enfin les scores de collisions comptés par cette étape 406 dans l’étape de recherche dans la table des empreintes 404. Les étapes de la troisième phase sont alors les suivantes: Soit ensemble des index synthétiques établi précédemment BD = {T 1 , …} l’ensemble des gabarits déjà enrôlés précédemment et à contrôler; Base de données entière LC = {( T k , s k )} la liste des candidats probables où T k est l’identifiant du candidat et S k le score de similarité trouvé pour ce candidat de chaque individu, SI ≠ø, LC ≠ø Initialiser un compteur de score Pour chaque minutie m i de T Pour chaque fonction de hachage f hk de F Initialiser un compteur de collisions Pour chaque gabarit trouvé sur les index b 1 et b 2 . Pour chaque minutie j trouvée en collision sur b 1 , b 2 , lire la collision en comptant chaque ligne (j, t) de b 1 , b 2 , puis en ajoutant la collision dans le compteur de collision A Compter les gabarits en collision A [ t ,j ] ++// FinPour FinPour FinPour Mettre à jour la table des scores pour un gabarit t FinPour Créer la liste des candidats en rangeant par ordre décroissant. Les scores les plus grands sont les candidats les plus probables. Le compteur est, par exemple, une matrice accumulateur de score. Il est initialisé pour conserver le score total à la fin. La recherche d’un gabarit se fait minutie par minutie. Pour chaque minutie, le score est connu par la matrice accumulateur A , puis reversé en fin de boucle de la minutie dans S pour conserver le résultat final. Cet accumulateur est mis à jour pour chaque minutie parcourue. Les fonctions min 1 et min 2 calculent respectivement le premier et le deuxième minimum d’index au sens de la distance de Hamming dH entre un index en entrée et une collection d’index. La liste des candidats LC par ordre décroissant permet de retrouver le candidat le plus proche en tête du tableau de recherche. A l’issue de cette étape, le processeur va émettre un signal d’identification ou de refus d’identification d’un individu. Le signal peut se traduire par un affichage du résultat d’identification sur l’écran du dispositif d’affichage 7. Il peut aussi prendre la forme d’un signal d’une commande qui commande un portillon d’accès à une zone ou un site, 406. La figure 5 présente la première étape du processus d’indexation ; c’est l’extraction des descripteurs de l’empreinte. Elle a pour but de transformer une image d’empreinte en un format numérique binaire. Ainsi, la phase 51 consiste à extraire les différentes minuties M i ( x i , y i , t i ) caractérisées par leurs coordonnées x, y et t leur orientation, dix minuties M 1 , .., M 10 , dans l’exemple. Ensuite la phase 52 est la création d’un template binaire MCC. Chaque minutie M i est représentée sous forme d’un code binaire BC 1 , BC 2 ,…, BC 10 , (10100101), 53. En pratique le vecteur binaire d’une minutie de l’empreinte est long (jusqu’à plus de 1500 bits). La deuxième étape illustrée en figure 6 consiste donc à l’indexation du template MCC, 43. On utilise ensuite plusieurs fonctions de hachage fixes, 51, qui sont des suites de bits placés à des positions fixes pour toutes les minuties binaires. Ceci permet de représenter une minutie par un sous-ensemble de bits fixés par chacune de ces fonctions, par exemple trois fonctions de hachage H 1 , H 2 , et H 3 . Les bits i 1 , i 5 et i 9 sont ceux choisis pour la fonction H 1 . Comme chaque fonction de hachage utilise trois bits dans le cadre de cet exemple, l’intervalle [0 ; (2 3 -1)] soit [0; 7] est l’espace total des index pour chaque fonction de hachage. On va ensuite soumettre chaque minutie par les fonctions de hachage afin d’indexer l’empreinte digitale. L’indexation de l’empreinte est faite en créant un index pour chacune des minuties qui la constituent. id 1 ,1 correspond à l’index lié à la minutie id 1 et la fonction de hachage f H1 , soit la valeur 1 dans le tableau, id 1,1 correspond à l’index lié à la minutie id 2 et la fonction de hachage f H2 , soit la valeur 0 dans le tableau, et ainsi de suite pour tous les index. Deux cas d’indexation sont représentés en utilisant les fonctions de hachage. Le cas 62 est l’indexation classique de la méthode MCC existant dans l’état de l’art et le cas 63 présente l’indexation selon l’invention. Dans la méthode 62, MCC classique, après avoir passé chaque code binaire de la minutie à travers chacune des fonctions de hachage, on obtient M*l intervalles d’index possibles représentés sur l’intervalle des index possibles pour chaque fonction. Dans l’exemple, on obtient au total trente index pour l’empreinte représentée dans la table des index. Il faut noter que pour chacune des fonctions de hachage, les index sont représentés sur l’intervalle [0; 7] dans la table des index. La partie 63 illustre le procédé d’indexation des minuties de l’empreinte selon l’invention. Dans un premier temps l’espace des index possibles est contrôlé. Le procédé crée un ensemble d’index fixes sur l’espace des index possibles. Ces index sont fixes et constituent les bornes de représentation des index de l’empreinte digitale. En effet, aucun autre index supplémentaire ne pourra être créé par une minutie. Dans l’exemple, on choisit les index 1, 3, 5, 7 (générés normalement par l’algorithme de création d’index synthétique) comme synthétiques et fixes pour les différentes fonctions de hachage. Ainsi, après avoir passé chaque minutie au travers des trois fonctions de hachage, on calcule les deux distances de Hamming les plus proches entre la minutie à indexer et les index synthétiques créés. On indexe la minutie sur les deux bornes les plus proches (indexation par intervalle). Ceci permet de contrôler la table des index sur la plage globale possible ; de généraliser la création des index pour chacune des minuties binaires ; de réduire les pertes d’informations en cas de changement de valeur d’un bit et de maximiser la précision de l’identification de l’empreinte. En effet, dans le procédé selon l’art antérieur 62, la table 64 des index s’agrandit au fur et à mesure qu’un nouvel index possible est généré pour une empreinte par une fonction de hachage. Par exemple, pour la fonction H 3 , l’index 1 est uniquement créé pour la minutie 9 (id 9 dans la table des index). Il est donc impossible de prédire ou prévoir une taille fixe de la table d’index. On a donc un grand nombre d’index possibles à parcourir sur la table des index et surtout, des index très peu remplis. C’est pourquoi, dans le procédé selon l’invention 63, le nombre d’intervalles d’index est fixe et la taille de la table des index est totalement maîtrisée. Ceci va permettre d’accélérer le processus d’indexation. De même, dans 63 selon l’invention, on n’indexe pas sur la valeur exacte produite par une minutie contrairement à la partie 62 selon l’art antérieur. Sur deux échantillons d’une même empreinte digitale acquise à deux instants différents, les minuties ne sont pas absolument identiques bit à bit. 1, 2,3… ou plusieurs bits peuvent être différents selon les conditions d’acquisition. L’art antérieur ne permet pas un tel contrôle et si un bit change, l’index généré n’est pas identique pour les deux minuties des deux échantillons d’empreinte. Lorsqu’un bit varie, alors l’indexation de la minutie exacte change, cependant, l’index reste valide sur le même intervalle, 65. Le procédé permet ainsi de conserver l’indexation par intervalle. Le procédé selon l’invention augmente le taux de précision en contrôlant la perte d’informations liée aux variations des bits. L’exemple a été donné pour un procédé d’identification utilisant les empreintes digitales. Sans sortir du cadre de l’invention, les étapes décrites précédemment s’appliquent pour l’identification d’un individu à partir de l’iris, ou de tout autre caractéristique biométrique d’un individu, en considérant à la place de la minutie utilisée pour l’empreinte digitale une particularité du paramètre biométrique utilisé, tel que l’iris, ou d’un paramètre morphologique. L’homme du métier adaptera les méthodes de calcul de gabarit à chaque application, par exemple, dans le cas d’une identification à partir de l’iris, un homme du métier utilisera un algorithme de Daugmant pour générer un code binaire associé à l’iris. Le procédé selon l’invention présente notamment les avantages suivants: l’utilisation d’une table d’indexation avec un nombre d’entrées réduit, une génération synthétique des index qui permet d’assurer un caractère discriminant et représentative des index de la table. Le procédé permet d’améliorer les performances de traitement en termes de vitesse et de précision par rapport à la méthode d’indexation MCC, donc une reconnaissance plus rapide d’un individu. Procédé d’identification d’un individu à partir d’informations contenues dans une base de données volumineuse caractérisé en ce qu’il comporte au moins les étapes suivantes: - Générer ou utiliser une table contenant des index synthétiques correspondant à un ensemble d’intervalles autour d’un centre de classe, (401), - Enrôler plusieurs données biométriques (407) en exécutant les étapes suivantes: - Pour chaque donnée biométrique, calculer un gabarit binaire lié à chaque paramètre caractéristique d’une donnée biométrique, (402), - Utiliser une méthode de hachage afin d’obtenir plusieurs index pour chaque gabarit binaire, (403), - Pour chaque index obtenu pour une donnée biométrique, insérer un identifiant correspondant à la donnée biométrique minimisant la distance de Hamming entre l’index considéré et les index synthétiques bornant ladite case, afin d’obtenir une table contenant des couples {identifiant donnée biométrique, identifiant individu}, (404), - Capturer au moins une donnée biométrique propre à l’individu au moyen d’un capteur adapté et calculer un gabarit binaire, (402, 405), - Rechercher (408) dans la table la ou les données biométriques les plus proches, comparer la donnée biométrique capturée aux données biométriques de la base, générer un résultat d’identification en cas de correspondance entre lesdites données comparées ou de non identification de l’individu, (404, 406) et traiter le résultat obtenu. Procédé d’identification selon la revendication 1 caractérisé en ce que l’on utilise les empreintes digitales pour identifier un individu et on exécute les étapes suivantes: - Enrôler plusieurs empreintes en exécutant les étapes suivantes: - Pour chaque empreinte, calculer un gabarit binaire lié à chaque minutie d’une empreinte en utilisant une méthode MCC, - Utiliser une méthode de hachage afin d’obtenir plusieurs index pour chaque gabarit binaire, - Pour chaque index obtenu pour une empreinte, insérer un identifiant correspondant à l’empreinte minimisant la distance de Hamming entre l’index considéré et les index synthétiques bornant ladite case, afin d’obtenir une table contenant des couples, {identifiant minutie, identifiant individu}, - Capturer au moins une empreinte propre à l’individu au moyen d’un capteur adapté, transformer ladite empreinte en un format numérique binaire, - Rechercher dans la table la ou les empreintes les plus proches et identifier l’individu ou rejeter l’identification en comparant le code binaire généré aux minuties mémorisées dans la table d’index. Procédé selon l’une des revendications 1 ou 2 caractérisé en ce que pour générer une table contenant des index synthétiques, on exécute les étapes suivantes: Soit h une fonction de hachage et les paramètres Avec deux «timers» de valeurs choisies pour stopper les boucles de recherche d’index synthétiques à ajouter, , la probabilité de générer un bit à ‘1’ sur un index synthétique en utilisant une distribution de Bernoulli, ɛ, la distance entre deux index voisins d’un même centre de classe, avec ɛ ∈ [3,7] MaxDH : le maximum de la distance de Hamming, min : un paramètre de rejet ou seuil minimal de rejet sur le nombre de ‘1’, nombre minimum de bits à ‘1’ pour valider un index synthétique, ST : l’ensemble des centres de classes, SI l’ensemble des index synthétiques en sortie, h la taille de la fonction de hachage, Initialiser Etape 1 - Créer des index cibles centres IC i de classes éloignés afin de couvrir l’espace des index, Tant que le paramètre n’est pas atteint: alors: Créer un index en générant bits avec une distribution de Bernoulli , Si où est la distance de Hammnig entre l’index et l’index , le nombre total de bits divergeant entre deux vecteurs binaires , Sinon valider l’index i comme un centre de classe et l’ajouter à l’ensemble des centres de classes Etape 2 – Créer autour de chaque index centre de classe IC i , des index proches sans chevauchement: Tant que la valeur du paramètre n’est pas atteinte exécuter les étapes suivantes: Créer un index en générant bits avec une distribution de Bernoulli si Sinon considérer l’index comme un index synthétique valide Mettre à jour l’ensemble des index correspondant à des intervalles autour d’un centre de classe Générer un ensemble des index synthétiques qui comprend des centres de classes et des intervalles autour de ces centres de classes en ajoutant les valeurs à l’ensemble pour toutes les valeurs de j. Procédé selon la revendication 2 caractérisé en ce que la phase d’enrôlement d’un individu dans une base utilise les index créés dans la table d’index synthétiques et comporte les étapes suivantes: Pour chaque empreinte digitale: - Un calcul des gabarits binaires liés à chaque minutie à partir de la méthode MCC, - L’obtention de plusieurs index pour chaque gabarit binaire en utilisant une fonction de hachage, - L’insertion de l’identifiant de l’empreinte dans plusieurs cases d’une table: pour chaque index obtenu pour une empreinte, on insère dans une case l’identifiant de l’empreinte qui minimise la distance de Hamming entre l’index considéré et les index synthétiques bornant la case, - A l’issue de cette étape, la table est complétée avec les identifiants des empreintes réelles d’individus qui constituent une base de données. Procédé selon la revendication 4 caractérisé en ce qu’il comporte les étapes suivantes: Soit T le gabarit, F = { f h1 , … f hl } ; un ensemble de fonctions de hachage, le nombre de fonctions de hachage, la base de données des index synthétiques préalablement créée lors de la phase d’initialisation, SI ≠ø initialisation de l’ensemble des index synthétiques, Pour chaque minutie m i de T , Pour chaque fonction de hachage f hk de F , calculer b = f hk (m i ) la distance de Hamming entre b et SI Enrôler m i sur b 1 et b 2 de la fonction f hk b 1 et b 2 sont les bornes inférieure et supérieure de l’intervalle qui encadre l’index b calculé pour chaque minutie du gabarit à enrôler. Procédé selon l’une des revendications 2 et 4 caractérisé en ce que l’identification d’une empreinte d’un individu comporte les étapes suivantes: Soit , ; l’ensemble des index synthétiques établi précédemment, SI , l’ensemble des index synthétiques établi précédemment, BD = {T 1 , …} l’ensemble des gabarits contrôlés, LC = {( T k , S k )} la liste des candidats probables avec S k le score d’accumulation de chaque individu, Initialiser l’ensemble des index synthétiques établi précédemment et la liste des candidats probables à la valeur zéro Initialiser un compteur de score Pour chaque minutie m i de T , Pour chaque fonction de hachage f hk de F , Initialiser un compteur de collisions A , calculer Les fonctions min 1 et min 2 calculent respectivement le premier et le deuxième minimum d’index au sens de la distance de Hamming dH entre un index en entrée et une collection d’index, Pour chaque gabarit t trouvé sur les index b 1 et b 2 Pour chaque minutie j trouvée en collision sur b 1 , b 2 , lire la collision en comptant chaque ligne (j, t) de b 1 , b 2 , puis en le renseignant dans le compteur de collision Compter les gabarits en collision Mettre à jour la table des scores pour un gabarit i, avec Créer la liste des candidats en rangeant par ordre décroissant et utiliser le candidat ayant la plus forte valeur de score pour l’étape d’identification. Procédé selon l’une des revendications précédentes caractérisé en ce que la fonction de hachage est une fonction LSH. Procédé selon l’une des revendications précédentes caractérisé en ce qu’il comporte une étape supplémentaire d’émission d’un signal d’ouverture d’un portique suite à l’identification d’un individu. Système d’identification d’un individu comportant un dispositif d’acquisition d’une donnée biométrique dudit individu, relié à un dispositif de traitement de données (2) comprenant une base de données (3), un processeur (4) configuré pour exécuter les étapes du procédé selon l’une des revendications 1 à 8, un dispositif de traitement du résultat d’identification, ladite base de données (3) comprenant une table d’index synthétiques correspondant à un ensemble d’intervalles autour d’un centre de classe. Système selon la revendication 9 caractérisé en ce que le dispositif de traitement du résultat de l’identification est un dispositif d’affichage (5). Système selon la revendication 9 caractérisé en ce que le dispositif de traitement du résultat de l’identification est un dispositif générant un signal de commande d’ouverture d’un moyen d’accès à une zone. Système selon l’une des revendications 10 et 11 caractérisé en ce que le dispositif d’acquisition est un dispositif de lecture d’empreintes et la donnée biométrique une empreinte.