Brevet FR2848699A1 — publié le 20040618

La présente invention concerne d'une manière générale l'identification biométrique par utilisation des empreintes digitales. Ce type de technique est aujourd'hui réalisé par ordinateur pour des applications telles que contrôle d'accès ou identification pour accéder à des données confidentielles via un réseau informatique, par exemple. Ainsi, classiquement, une image numérique d'une empreinte digitale à reconnaître est tout d'abord réalisée. On travaille directement à partir de cette image ou elle peut être traitée par une technique dite de squelettisation pour que toutes les lignes de l'empreinte aient la même épaisseur de un pixel. Dans tous les cas, on utilise une image numérique représentative des lignes 20 physiques de l'empreinte. Les minuties de l'empreinte, c'est-à-dire les fins de lignes et les bifurcations d'une ligne en deux lignes, sont recherchées puis comparées aux minuties d'une empreinte de référence, préalablement mémorisées en mémoire. Cependant, il n'est pas possible d'assurer qu'une minutie sera à coup sur détectée à chaque acquisition. En outre, ce type de traitement est long, notamment en raison du nombre de minuties, variable d'une empreinte à l'autre, mais que l'on peut estimer à quarante en moyenne. En effet, lors d'une phase de recherche de 30 repère, ou phase d'alignement, chaque minutie de l'empreinte à reconnaître est comparée à chaque minutie de l'empreinte de référence. Le critère de comparaison est par exemple la position des minuties ainsi que des lignes qui leur sont respectivement associées. Lorsque deux minuties sont similaires, les deux empreintes sont recentrées l'une par rapport à l'autre par translation et rotation au cours d'une 5 phase de reconnaissance. Les similarités entre minuties des deux empreintes sont alors recherchées. Tant qu'on n'obtient pas un niveau élevé de similitudes entre les deux ensembles de minuties, on réitère les phases de recherche de repère et de reconnaissance. Lorsqu'un repère fournit un niveau élevé de similitudes entre les 10 deux ensembles de minuties, le traitement est terminé et l'empreinte à reconnaître est identifiée comme étant identique à l'empreinte de référence. Lorsque aucun repère ne fournit un niveau élevé de similitudes entre les deux ensembles de minuties, le traitement est terminé et l'empreinte à reconnaître n'est pas identifiée. Pour accélérer le traitement, il est connu d'utiliser des points invariants tels qu'un core, que l'on peut voir comme un rebroussement de ligne, ou un delta, que l'on peut voir comme un triangle de lignes. Ces points invariants sont moins nombreux que les minuties, puisqu'il y a au maximum deux cores et deux deltas par empreinte. Cependant, le nombre de cores et de deltas varie selon les empreintes, ce qui complique le traitement, notamment pour les empreintes de type arche qui n'ont ni core ni delta. En outre, les algorithmes de calcul des cores et deltas sont souvent imprécis et sont donc globalement difficiles à utiliser. La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un procédé et un dispositif biométriques de reconnaissance d'empreinte digitale qui permettent une reconnaissance fiable tout en étant de mise en oeuvre rapide. 30 A cette fin, l'invention propose un procédé biométrique de reconnaissance d'empreinte digitale, par comparaison d'une image de l'empreinte à reconnaître avec une image d'une empreinte de référence, caractérisé en ce qu'il comporte les étapes préalables de: - détermination d'un centre invariant à partir des lignes reproduisant la structure de l'empreinte, sur l'image de l'empreinte à reconnaître, - centrage de l'empreinte à reconnaître, en fonction du centre invariant précédemment déterminé. Grâce à l'invention, la reconnaissance d'empreinte digitale est fiable 10 et de mise en oeuvre rapide. En effet, le centre invariant existe toujours et est unique. Après l'opération de centrage, la comparaison de l'empreinte à reconnaître et de l'empreinte de référence est considérablement simplifiée. En effet, les deux empreintes sont alors presque superposées et il ne reste qu'un 15 petit ajustement à effectuer en rotation et translation. Le nombre de minuties à tester pour trouver un repère et vérifier la correspondance entre deux empreintes est très inférieur à celui de la technique antérieure. La complexité des calculs et le temps de traitement sont par conséquent réduits. Selon une caractéristique préférée, les étapes préalables de détermination d'un centre invariant et de centrage sont appliquées à l'empreinte de référence. Ces calculs sont par exemple faits une fois pour toutes et leur résultat est mémorisé. Selon une caractéristique préférée, le centre invariant de l'empreinte 25 est déterminé par: - formation de blocs dans l'image de l'empreinte, détermination d'une direction moyenne des lignes dans chaque bloc, détermination d'une direction perpendiculaire pour chaque direction 30 moyenne, - formation d'une image d'accumulation à partir des directions perpendiculaires, - détermination du centre invariant à partir de l'image d'accumulation. La détermination du centre est simple à mettre en oeuvre et fournit un résultat fiable. Selon des caractéristiques préférées et alternatives, le centre invariant correspond à une valeur maximale dans l'image d'accumulation ou le centre invariant correspond à un barycentre des plus grandes valeurs dans l'image d'accumulation. Selon une caractéristique préférée, la comparaison de l'image de 10 l'empreinte à reconnaître avec l'image de l'empreinte de référence comporte: - une première mise en correspondance de chacune des minuties de l'une des empreintes à reconnaître et de référence avec un nombre prédéterminé de minuties de l'autre des empreintes à reconnaître et de référence, - l'ajustement de position de l'empreinte à reconnaître par rapport à l'empreinte de référence, de manière à mettre en correspondance les minuties des deux empreintes. Selon une caractéristique préférée, la mise en correspondance des minuties des deux empreintes est effectuée à partir des résultats de la 20 première mise en correspondance. La complexité des calculs est ainsi réduite par rapport à la technique antérieure. Selon une caractéristique préférée, la comparaison de l'image de l'empreinte à reconnaître avec l'image de l'empreinte de référence est réalisée 25 dans une carte à puce. Corrélativement, l'invention concerne un dispositif biométrique de reconnaissance d'empreinte digitale, comportant des moyens de comparaison d'une image de l'empreinte à reconnaître avec une image d'une empreinte de référence, caractérisé en ce qu'il comporte: - des moyens de détermination d'un centre invariant à partir des lignes reproduisant la structure de l'empreinte, sur l'image de l'empreinte à reconnaître, - des moyens de centrage de l'empreinte à reconnaître, en fonction du centre invariant précédemment déterminé. Le dispositif selon l'invention comporte des moyens de mise en oeuvre des caractéristiques précédemment présentées. Le dispositif selon l'invention présente des avantages analogues à ceux précédemment présentés. Un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention. Un programme d'ordinateur lisible par un microprocesseur et comportant une ou plusieurs séquence d'instructions est apte à mettre en 15 oeuvre le procédé selon l'invention. L'invention peu également être mise en oeuvre par un composant de type ASICS. Les caractéristiques et avantages de la présente invention 20 apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels: - la figure 1 est un mode de réalisation d'un dispositif mettant en oeuvre l'invention, - la figure 2 représente un mode de réalisation de procédé 25 biométrique de reconnaissance d'empreinte digitale selon l'invention, - la figure 3 représente un mode de réalisation de calcul d'un centre invariant inclus dans le procédé précédent, - la figure 4 illustre le calcul d'un centre invariant de la figure 3, - la figure 5 représente un mode de réalisation de comparaison 30 inclus dans le procédé de la figure 2. Selon le mode de réalisation choisi et représenté à la figure 1, un dispositif mettant en oeuvre l'invention est par exemple un microordinateur 1 connecté à un lecteur 2 de carte à puce 3. Le lecteur de carte à puce est classique et est adapté à lire les 5 informations contenues dans une carte a puce. Notamment, dans le cadre de l'invention, ces informations comportent des données représentant une image d'une empreinte digitale de référence. Le lecteur 2 comporte en outre un lecteur 4 d'empreinte digitale. En variante, le lecteur d'empreinte digitale est un dispositif distinct du lecteur de 10 carte à puce, tout en étant relié à l'ordinateur 1. Le lecteur 4 est adapté à réaliser une lecture d'une empreinte digitale. Cette lecture peut être optique, capacitive, thermique ou encore par ultrasons. Après conversion analogique-numérique, le lecteur 4 délivre à l'ordinateur des données représentant une image d'une empreinte digitale à 15 reconnaître. L'ordinateur 1 comporte des moyens classiques de mémoire et de calculs, de manière à mémoriser l'algorithme de traitement qui est exposé dans la suite, ainsi que les données en cours de traitement. En variante, les moyens de calculs, le lecteur d'empreinte et le lecteur de carte à puce sont intégrés 20 dans un même appareil. Bien entendu, le lecteur de carte à puce et le lecteur d'empreinte digitale peuvent être intégrés à l'ordinateur. Le dispositif de reconnaissance d'empreinte digitale selon l'invention comporte des moyens de comparaison d'une image de l'empreinte à 25 reconnaître avec une image d'une empreinte de référence. Plus particulièrement, il comporte: - des moyens de détermination d'un centre invariant à partir des lignes reproduisant la structure de l'empreinte, sur l'image de l'empreinte à reconnaître, - des moyens de centrage de l'empreinte à reconnaître, en fonction du centre invariant précédemment déterminé. Comme il sera détaillé dans la suite, la comparaison des deux images est la comparaison d'un ensemble d'éléments représentatifs de chacune des images. Les éléments représentatifs sont ici les minuties. En variante, les images sont comparées par pixels, ou par blocs de pixels. Les mêmes traitements sont appliqués sur l'image de l'empreinte de référence. Par exemple, la carte à puce contient l'ensemble d'éléments représentatifs et le centre invariant de l'empreinte de référence, ces éléments ayant été calculés préalablement, une fois pour toutes. La carte à puce reçoit l'ensemble d'éléments représentatifs et le centre invariant de l'empreinte à 10 reconnaître. La comparaison de l'ensemble d'éléments représentatifs de l'image de l'empreinte à reconnaître avec l'ensemble d'éléments représentatifs de l'image de l'empreinte de référence est ensuite réalisée. Le fonctionnement du dispositif est décrit dans la suite à l'aide 1 5 d'algorithmes. La figure 2 représente un mode de réalisation de procédé biométrique de reconnaissance d'une empreinte digitale, selon l'invention. Ce procédé est mis en oeuvre dans le dispositif de codage et comporte des étapes 20 El à E8. Le procédé est réalisé sous la forme d'un algorithme qui peut être mémorisé en totalité ou en partie dans tout moyen de stockage d'information capable de coopérer avec le microprocesseur de l'ordinateur. Ce moyen de stockage est intégré ou non au dispositif, et peut être amovible. Par exemple, il 25 peut comporter une bande magnétique, une disquette ou un CD-ROM (disque compact à mémoire figée). L'étape El est la capture de l'empreinte à reconnaître. Cette capture est réalisée par le lecteur d'empreinte 4. Cette capture est classique et a pour résultat une image numérique de l'image à reconnaître. L'étape suivante E2 est la transmission des données représentant l'image de l'empreinte à reconnaître à l'ordinateur. L'étape suivante E3 est le calcul des minuties de l'empreinte à reconnaître. Ce calcul est classique. Les minuties sont identifiées par leur position et leur angle d'orientation. L'étape suivante E4 est le calcul d'un centre invariant pour l'empreinte à reconnaître. Cette étape est détaillée dans la suite. Elle a pour résultat un point unique. Le centre invariant existe pour toutes les empreintes. L'étape suivante E5 est la transmission des minuties et du centre invariant vers la carte à puce 3 insérée dans le lecteur 2. Les étapes suivantes sont mises en oeuvre dans la carte à puce de sorte que les données mémorisées dans la carte à puce, a priori confidentielles, ne sortent pas de celle-ci. L'étape E6 est la lecture des minuties et du centre invariant d'une empreinte de référence. Ces données ont été préalablement calculées de 15 manière identique au traitement réalisé sur l'empreinte à reconnaître et sont mémorisées dans la carte à puce. Les étapes E5 et E6 sont suivies de l'étape E7 qui est un centrage de l'empreinte à reconnaître par rapport à l'empreinte de référence. De manière générale, le centrage d'une empreinte est le choix de l'origine d'un repère. Par 20 exemple, l'origine du repère est égale au centre invariant de l'empreinte. L'empreinte à reconnaître et l'empreinte de référence sont centrées toutes les deux de la même façon. Ce centrage consiste ainsi à mettre en correspondance les centres invariants des deux empreintes. En d'autres termes, cela revient en quelque sorte à " superposer " les centres invariants 25 des deux empreintes. L'étape suivante E8 est la comparaison de l'empreinte à reconnaître avec l'empreinte de référence. Cette étape est détaillée dans la suite. Le calcul du centre invariant (étape E4) est détaillé en référence à la figure 3, sous la forme d'un algorithme comportant des étapes E40 à E43. La figure 4 représente l'image de l'empreinte à reconnaître. L'étape E40 est la formation de blocs Bi dans l'image de l'empreinte à reconnaître. Un bloc est un ensemble de pixels adjacents de l'image. Les blocs sont formés en nombre prédéterminé. Ils sont par exemple de forme carrée et tous de même taille. Les blocs sont répartis sur l'image de l'empreinte. L'étape suivante E41 est le calcul, dans chaque bloc Bi, de la direction moyenne Mi des lignes de l'empreinte. Les lignes sont formées par les crêtes ou par les vallées de l'empreinte. A chaque direction moyenne est associée une direction perpendiculaire Pi. L'étape suivante E42 est la formation d'une image d'accumulation à partir des perpendiculaires précédemment formées. L'image d'accumulation comporte des points respectivement associés aux points de l'empreinte. Une valeur est incrémentée pour chaque point de l'image d'accumulation lorsqu'une perpendiculaire passe par le point correspondant de l'image de l'empreinte. La plupart des perpendiculaires passent dans une zone centrale de l'image de l'empreinte. En conséquence, l'image d'accumulation comporte une zone correspondante dans laquelle les points d'accumulation ont de valeurs élevées. L'étape suivante E43 est la détermination du centre invariant. Le 20 centre invariant est par exemple le point de l'image de l'empreinte correspondant au point de l'image d'accumulation de valeur maximale. En variante, le centre invariant est calculé de la manière suivante: La valeur médiane des valeurs des points d'accumulation est déterminée. Les points d'accumulation dont la valeur est inférieure à la valeur 25 médiane sont éliminés. Les points d'accumulation restant, pondérés par leur valeur respective calculée E42, sont utilisés pour calculer leur barycentre. Le centre invariant est alors le barycentre calculé. L'étape E8 de comparaison est détaillée en référence à la figure 5 30 sous la forme d'un algorithme comportant des étapes E80 à E84. On rappelle que l'empreinte à reconnaître et l'empreinte de référence ont été précédemment centrées par " superposition " de leur centres invariants (étape E7). L'étape E80 est une première mise en correspondance des minuties 5 de l'empreinte à reconnaître avec celles de l'empreinte de référence. Chaque minutie de l'empreinte de référence est associée à quatre minuties de l'empreinte à reconnaître, par proximité géographique. Ces correspondances sont enregistrées dans un tableau. Bien entendu, en variante, il est possible d'inverser les rôles de 10 l'empreinte de référence et de l'empreinte à reconnaître, et ainsi d'associer chaque minutie de l'empreinte à reconnaître à quatre minuties de l'empreinte de référence. A l'étape suivante E81, une minutie de l'empreinte de référence est considérée. L'étape suivante E82 est la recherche d'une minutie de l'empreinte à reconnaître. Cette recherche est effectuée parmi les quatre minuties associées à la minutie courante de l'empreinte de référence. Le nombre de minuties à envisager est donc limité. L'étape E82 est suivie de l'étape E83 d'ajustement de la position de l'empreinte à reconnaître par rapport à celle de l'empreinte de référence. Les deux empreintes ayant été centrées l'une par rapport à l'autre grâce à leur centre invariant, il suffit ici d'effectuer un ajustement en rotation et translation pour chercher à superposer les deux minuties courantes des deux 25 empreintes ainsi que les lignes respectives associées à chacune des minuties courantes. L'étape E83 est suivie de l'étape E84 de recherche de correspondance. Le tableau de correspondance est à nouveau utilisé de la manière suivante. Pour chacune des minuties de l'empreinte de référence, on recherche parmi les quatre minuties qui lui sont associées s'il y a il correspondance entre la minutie de l'empreinte de référence et l'une des minuties de l'empreinte à reconnaître. Un score associé aux deux minuties courantes est mis à jour en fonction du résultat de la recherche de correspondance. Si le score n'indique pas que les minuties des deux empreintes sont parfaitement superposées, l'étape E84 est suivie de l'étape E82 précédemment décrite pour considérer une autre minutie de l'empreinte à reconnaître, sélectionnée parmi les quatre minuties associées à la minutie courante de l'empreinte de référence. Ce bouclage est effectué tant que le score n'indique 10 pas une superposition des minuties des deux empreintes et qu'il reste au moins une minutie de l'empreinte à reconnaître, parmi les quatre minuties associées à la minutie courante de l'empreinte de référence, à considérer. Si le score n'indique pas que les minuties des deux empreintes sont parfaitement superposées, et si toutes les minuties de l'empreinte à 15 reconnaître, parmi les quatre minuties associées à la minutie courante de l'empreinte de référence, ont été considérées, alors l'étape E84 est suivie de l'étape E81 pour considérer une autre minutie de l'empreinte de référence, et ce tant que toutes les minuties de l'empreinte de référence n'ont pas été traitées. Le résultat de ce traitement est donc binaire. Ce résultat peut être l'identification d'une correspondance à l'étape E84, l'empreinte à reconnaître est alors identifiée comme identique à l'empreinte de référence. Le résultat peut être qu'aucune correspondance n'a été trouvée à l'étape E84. L'empreinte à reconnaître est alors déclarée différente de 25 l'empreinte de référence. L'utilisation ultérieure de ce résultat est classique, notamment pour une autorisation d'accès à des données, et n'est pas détaillée ici. Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, 30 toute variante à la portée de l'homme du métier. REVENDICATIONS 1. Procédé biométrique de reconnaissance d'empreinte digitale, par comparaison d'une image de l'empreinte à reconnaître avec une image d'une empreinte de référence, caractérisé en ce qu'il comporte les étapes préalables de: - détermination (E4) d'un centre invariant à partir des lignes 10 reproduisant la structure de l'empreinte, sur l'image de l'empreinte à reconnaître, - centrage (E7) de l'empreinte à reconnaître, en fonction du centre invariant précédemment déterminé. 2. Procédé selon la revendication 1, caractérisé en ce que les étapes préalables de détermination d'un centre invariant et de centrage de l'ensemble d'éléments représentatifs sont appliquées à l'empreinte de référence. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que le 20 centre invariant de l'empreinte est déterminé par: - formation (E40) de blocs dans l'image de l'empreinte, - détermination (E41) d'une direction moyenne des lignes dans chaque bloc, - détermination (E41) d'une direction perpendiculaire pour chaque 25 direction moyenne, - formation (E42) d'une image d'accumulation à partir des directions perpendiculaires, détermination (E43) du centre invariant à partir de l'image d'accumulation. 4. Procédé selon la revendication 3, caractérisé en ce que le centre invariant correspond à une valeur maximale dans l'image d'accumulation. 5. Procédé selon la revendication 3, caractérisé en ce que le centre invariant correspond à un barycentre des plus grandes valeurs dans l'image d'accumulation. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que la comparaison de l'image de l'empreinte à reconnaître avec l'image de l'empreinte de référence comporte: - une première mise en correspondance (E80) de chacune des 10 minuties de l'une des empreintes à reconnaître et de référence avec un nombre prédéterminé de minuties de l'autre des empreintes à reconnaître et de référence, l'ajustement de position (E83) de l'empreinte à reconnaître par rapport à l'empreinte de référence, de manière à mettre en correspondance 15 (E84) les minuties des deux empreintes. 7. Procédé selon la revendication 6, caractérisé en ce que la mise en correspondance (E84) des minuties des deux empreintes est effectuée à partir des résultats de la première mise en correspondance. 20 8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que la comparaison de l'image de l'empreinte à reconnaître avec l'image de l'empreinte de référence est réalisée dans une carte à puce. 9. Dispositif biométrique de reconnaissance d'empreinte digitale, comportant des moyens de comparaison d'une image de l'empreinte à reconnaître avec une image d'une empreinte de référence, caractérisé en ce qu'il comporte: - des moyens de détermination d'un centre invariant à partir des 30 lignes reproduisant la structure de l'empreinte, sur l'image de l'empreinte à reconnaître, - des moyens de centrage de l'empreinte à reconnaître, en fonction du centre invariant précédemment déterminé. 10. Dispositif selon la revendication 9, caractérisé en ce que les 5 moyens de détermination d'un centre invariant et de centrage sont appliqués à l'empreinte de référence. 11. Dispositif selon la revendication 9 ou 10, caractérisé en ce que les moyens de détermination du centre invariant de l'empreinte comportent: 10 - des moyens de formation de blocs dans l'image de l'empreinte, - des moyens de détermination d'une direction moyenne des lignes dans chaque bloc, - des moyens de détermination d'une direction perpendiculaire pour chaque direction moyenne, - des moyens de formation d'une image d'accumulation à partir des directions perpendiculaires, - des moyens de détermination du centre invariant à partir de l'image d'accumulation. 12. Dispositif selon la revendication 11, caractérisé en ce que les moyens de détermination du centre invariant sont adaptés à le déterminer de sorte qu'il corresponde à une valeur maximale dans l'image d'accumulation. 13. Dispositif selon la revendication 11, caractérisé en ce que les 25 moyens de détermination du centre invariant sont adaptés à le déterminer de sorte qu'il corresponde à un barycentre des plus grandes valeurs dans l'image d'accumulation. 14. Dispositif selon l'une quelconque des revendications 9 à 13, 30 caractérisé en ce que les moyens de comparaison de l'image de l'empreinte à reconnaître avec l'image de l'empreinte de référence comportent: - des moyens de première mise en correspondance de chacune des minuties de l'une des empreintes à reconnaître et de référence avec un nombre prédéterminé de minuties de l'autre des empreintes à reconnaître et de référence, - des moyens d'ajustement de position de l'empreinte à reconnaître par rapport à l'empreinte de référence, de manière à mettre en correspondance les minuties des deux empreintes. 15. Dispositif selon la revendication 14, caractérisé en ce que les 10 moyens d'ajustement sont adaptés à effectuer la mise en correspondance des minuties des deux empreintes à partir des résultats de la première mise en correspondance. 16. Dispositif biométrique de reconnaissance d'empreinte digitale, 15 selon l'une quelconque des revendications 9 à 15, caractérisé en ce qu'il comporte: - un élément (4) de capture d'image de l'empreinte à reconnaître, - un moyen de calcul (1) relié à l'élément de capture et adapté à déterminer un centre invariant pour l'empreinte à reconnaître, un lecteur (2) de cartes à puce (3) relié au moyen de calcul, la carte à puce contenant le centre invariant de l'empreinte de référence et étant adaptée à recevoir le centre invariant de l'empreinte à reconnaître puis à réaliser la comparaison de l'image de l'empreinte à reconnaître avec l'image de l'empreinte de référence.