Accueil » Publications » Le Bulletin Vert » Les dossiers » Un moyen d’identification simple : (...)
  APMEP   Un moyen d’identification simple : les empreintes digitales

Article du bulletin 495

Adhérer ou faire un don

Hervé Lehning [1]

Le positivisme scientifique n’a pas que des défauts. Depuis la fin du XIXe siècle, la police fait place aux preuves de nature scientifique. La première d’entre elles est fondée sur les empreintes digitales. Est-elle fiable et comment faire pour consulter les millions d’empreintes dont dispose la police ?

Cet article fait suite à celui de Rémi Belloeil

La première énigme policière résolue en comparant des empreintes digitales recueillies sur la scène d’un crime avec celles contenues dans un fichier préétabli date de 1892. L’histoire se déroule en Argentine et peut être retrouvée par ceux qu’elle intéresse sur l’Internet. Au préalable, Sir Francis Galton – cousin de Charles Darwin – (voir l’annexe I) avait établi l’unicité et la permanence de ces figures cutanées (voir l’annexe II). On attendra dix ans pour que la même histoire se produise en France où l’inventeur de la méthode se nomme Alphonse Bertillon.

Premier fichier français

Dans le premier fichier français d’Alphonse Bertillon, chaque doigt se voyait attribuer un chiffre entre 0 et 8 et donc chaque individu une signature de dix chiffres comme par exemple 13267 – 23486. Ce système permettait d’accélérer la recherche dans ce fichier en ne retenant que les fiches ayant une signature convenable. Depuis 1896, les détenus parisiens étaient ainsi tous fichés. En 1902, alors qu’ils sont appelés sur la scène d’un crime, les policiers trouvent comme seules traces quatre empreintes digitales sur une vitrine en verre (un pouce sur la face extérieure, un index, un majeur et un annulaire sur la face intérieure). Alphonse Bertillon les agrandit quatre fois, puis les compare avec celles de son fichier constitué par celles des détenus parisiens. En quelques jours, il trouve qu’elles coïncident avec celle d’un malfaiteur – Henri Léon Scheffer – condamné pour vol et abus de confiance. Arrêté à Marseille six jours plus tard, il passe aux aveux. Cette affaire Scheffer constitue le véritable acte de naissance de la police scientifique en France.

Comment chercher dans un gros fichier ?

Bertillon a réussi à retrouver un criminel grâce à son fichier car celui-ci était de taille modeste. De nos jours, le fichier de la police contient les empreintes de plus d’un million et demi d’individus. Comme chacun en possède dix, cela donne quinze millions d’empreintes  ! Comment chercher dans un tel fichier  ? À la main, c’est impossible. La recherche doit être confiée à un ordinateur. Quel algorithme doit-il suivre pour ce faire ? L’idée la plus simple est de tenter de superposer l’empreinte trouvée avec celles du fichier en commençant par la première jusqu’à la dernière. Le problème est beaucoup plus compliqué qu’il ne paraît à première vue : l’empreinte trouvée est forcément partielle et déplacée (décalée ou tournée). Même si l’on imagine une orientation préalable des empreintes trouvées, il est nécessaire de les comparer avec l’empreinte du fichier et des transformations de celle-ci par certains déplacements. Sans entrer dans les détails, il est facile de voir que cette voie est beaucoup trop lourde pour être efficace.

Signature d’une empreinte

Une idée simple est d’oublier la majorité des caractéristiques d’une empreinte pour se concentrer sur les points les plus typiques que l’on nomme minuties. Il s’agit de bifurcations, d’îles, de nœuds, de lignes qui disparaissent, etc. On peut en relever seize types dont les quatre plus importantes sont : terminaison, bifurcation, île et lac : La description de chaque minutie demande en moyenne seize octets. Pourquoi  ?
Oublions pour un instant le problème de la définition d’un repère intrinsèque à l’empreinte (voir l’annexe III). Une minutie est caractérisée par un type (terminaison, bifurcation, île ou lac) et trois ou quatre nombres réels suivant son type. Dans les deux premiers cas, trois nombres suffisent  : ses coordonnées et un angle (voir la figure ci-dessous), dans les deux autres, un de plus est nécessaire. Le type demande un seul octet pour être stocké et chacun des nombres, quatre. Il s’agit de la norme IEEE des nombres réels en simple précision. En tout, il faut donc treize octets pour stocker une terminaison ou une bifurcation, dix-sept pour une île ou un lac.
La question s’alourdit quand on remarque que, sur une empreinte digitale, on peut repérer un grand nombre de minuties comme le montre la figure sur cette empreinte. Comment automatiser leur repérage puis leur stockage afin d’obtenir une signature de l’empreinte ? Pour cela, elle est d’abord stockée sous un format de photographie numérique (comme le format JPEG) puis filtrée de façon à ce que les lignes aient toutes la même épaisseur (un pixel). On obtient ainsi une image squelettique en noir et blanc. Les minuties sont alors extraites. À ce stade, on en détecte normalement une centaine. Comme chaque minutie demande en moyenne seize octets pour être décrite, ce nombre est beaucoup trop grand. Arrivés à ce niveau, on ne conserve en fait que les quinze plus fiables ce qui donne une signature de 240 octets. Pour ce faire, parmi les minuties proches l’une de l’autre, on ne garde que la plus marquée.
Les minuties retenues sont alors classées dans l’ordre des nombres qui les représentent, le tout est regroupé dans un nombre de 240 octets ; L’important est que les algorithmes utilisés permettent ainsi de n’associer à chaque empreinte digitale qu’une seule et même signature. En revanche, il est possible que plusieurs empreintes possèdent la même. On trouvera une étude de ces minuties ainsi que leurs modélisations dans les empreintes digitales [4]. Cette propriété peut avoir des conséquences fâcheuses si aucune vérification humaine n’est faite comme le montre le cas de Shirley McKie (voir l’annexe II).

Structure du fichier

Le fichier d’empreintes digitales comprend trois parties : celui des signatures, celui des empreintes proprement dites et celui des biographies des individus ainsi recensés.
Chaque signature renvoie à une ou plusieurs empreintes qui elles-mêmes renvoient chacune à un individu. La recherche se fait dans le fichier des signatures. En moyenne, vu la taille du fichier, on trouve ainsi quelques dizaines d’empreintes possibles. Le reste de l’analyse se fait de façon traditionnelle c’est-à-dire par un spécialiste humain qui seul peut établir la concordance des empreintes. Dans cette analyse, l’ordinateur ne sert donc qu’à un tri préalable.
Revenons à cette étape informatique. Étant donnée une empreinte digitale trouvée sur la scène d’un crime ou ailleurs, on calcule sa signature de la façon décrite précédemment et on la recherche dans le fichier. Il s’agit ainsi de trouver un mot de 240 octets dans un fichier de plusieurs millions d’articles. S’il n’est pas structuré, la seule méthode possible consiste à essayer toutes les fiches les unes après les autres.
On ne peut pas même s’arrêter à la première réponse car deux empreintes distinctes peuvent avoir la même signature. Quinze millions de signatures doivent donc être essayées. Pour accélérer cette recherche, une idée simple est de trier le fichier comme l’est un dictionnaire. La méthode dichotomique permet alors de limiter les essais à 24 ! Pourquoi ? Tout simplement parce que chaque essai permet de diviser par deux le nombre de fiches possibles (voir l’annexe IV).

Mise à jour du fichier

Il reste une difficulté : celle de la mise à jour du fichier. Il est très facile d’ajouter de nouvelles fiches à un fichier non trié : il suffit de les mettre à la queue. Il est plus difficile d’en ajouter à un fichier trié. Pour cela, il faut d’abord trouver la place où insérer la nouvelle fiche, puis décaler les suivantes pour placer la nouvelle. Cela donne plusieurs millions de décalages nécessaires. Il est tout aussi long de supprimer une fiche. Pour tourner la difficulté, on a mis au point plusieurs façons de structurer les fichiers. Pour la plupart, elles utilisent la notion d’arbre et donc de graphe (voir les arbres de recherche dans [2], pages 165 – 168).

Problème d’identification

La même technique est utilisée pour identifier automatiquement les personnes ayant le droit d’accéder à certaines zones ou à certains services. Elle permet de remplacer avantageusement la méthode des mots de passe. En effet, ceux-ci peuvent être obtenus par la menace ou l’astuce. Voler un doigt reste possible c’est pourquoi un détecteur contrôle également la circulation sanguine. Dans cette application de la méthode, le fichier est réduit mais la même technique des signatures est employée.
On utilise normalement les quinze minuties les plus pertinentes, le risque d’erreur est alors très faible.

Annexe I : Francis Galton

Outre ses travaux fondateurs sur les empreintes digitales, Francis Galton est connu pour ses travaux sur l’intelligence humaine. D’autre part, ses idées ont fortement influencé le développement des statistiques. Son introduction du terme « eugénisme » lui valut de voir son nom ensuite très mal associé puisque, pour Adolf Hitler, cette idée justifiait le massacre des juifs et des tziganes entre autres. Inutile de préciser que cette association est tout à fait abusive.

Annexe II : Probabilité d’identité des empreintes

Bien qu’il eut des précurseurs, Francis Galton (1822 – 1911) fut le premier à établir l’unicité et la permanence de ces figures cutanées. De plus, il proposa de les classifier suivant leurs formes : boucles, volutes ou arcs. En dénombrant ces formes, il arrivait de façon assez obscure à 2 36 configurations d’empreintes possibles. En les supposant équiprobables, cela donne une chance sur 64 milliards que deux doigts distincts aient les mêmes empreintes. Depuis Francis Galton, d’autres méthodes de calcul ont été proposées. Ainsi, Christophe Champod [1] propose un modèle probabiliste où plusieurs facteurs sont supposés indépendants. Par une étude statistique, il estime la probabilité de chaque facteur. La multiplication des probabilités de ces facteurs permet de conclure. L’étude de Christophe Champod conforte les règles d’identification édictées par Edmond Locard, directeur du laboratoire de police scientifique de Lyon, en 1914  : absence de discordance, existence de 12 points concordants. Ceci dit, ces notions ne doivent pas aboutir à un quelconque automatisme. Par exemple, en 1997, Shirley McKie, enquêtrice de la police écossaise, fut accusée d’un meurtre parce que ses empreintes digitales avaient été « identifiées » sur la scène d’un crime. En fait, elles n’étaient que quasiment identiques à celles du véritable meurtrier (voir the price of innocence [3]).

Annexe III : Définition d’un repère intrinsèque à une empreinte.

Pour être identifiable quelque soit l’orientation de l’empreinte, il est important que les coordonnées de chaque minutie soient calculées dans un repère lié à l’empreinte et non à sa position. Cela demande de définir le centre du repère et l’orientation de l’axe des abscisses. Pour le centre, le problème est relativement simple. Il suffit de chercher le point de convergence des circonvolutions au centre du doigt. Pour cela, un algorithme consiste à définir des lignes orthogonales à celles-ci et à trouver leur point de concours. Il nous suffit alors d’un autre point lié à l’empreinte pour définir un repère intrinsèque. Par exemple, on peut choisir le centre de gravité des quinze minuties retenues.

Annexe IV : Recherche dichotomique

Imaginons que nous cherchions une fiche parmi 100 fiches triées dans l’ordre alphabétique. Nous ne le savons pas à l’avance bien sûr mais la fiche cherchée « brigand » se trouve être la 10e du fichier. Nous essayons d’abord la 50e , « escroc ». La fiche cherchée se trouve précéder celle-ci. Nous essayons alors la 25e puis la 12e, la 6e, 9e, la 11e et nous trouvons enfin la 10e. Ainsi, en sept essais, nous avons trouvé la fiche cherchée. Remarquez qu’il en sera toujours ainsi. Cela tient au fait que $2^7 =128$ > 100 puisqu’à chaque fois, nous réduisons par deux le nombre de fiches à essayer. Par rapport à la méthode consistant à essayer toutes les fiches, le gain est considérable : sept fiches à tester au lieu de cent ! Si nous cherchons dans un fichier de quinze millions de fiches, le gain est encore plus impressionnant puisque le nombre d’essais est le plus petit nombre n tel que $2^n > 15.10^6$ c’est-à-dire 24.

Références

[1] Christophe Champod, Reconnaissance automatique et analyse statistique des minuties sur les empreintes digitales, Université de Lausanne, 1995.

[2] Hervé Lehning, Questions de maths sympas pour M. et Mme Toutlemonde, Ixelles éditions, 2011.

[3] Iain McKie et Michael Russel, Shirley McKie : The price of innocence, Birlinn, 2007.

[4] Véronique Messéant, Patrick Nizou et Nathalie Villain, Les empreintes digitales, mémoire de master de didactique, Université Paris VII, 2006.

(Article mis en ligne par Armelle BOURGAIN)

[1] lehning@noos.fr


 Accueil   Plan du site   Haut de la page   Page précédente