Modélisation des Empreintes Digitales

Cette unicit est donc une opportunit pour identifier un individu, mais alors quest-ce

qui caract rise lempreinte digitale?

a. Motif

En regardant les images dempreintes ci-dessous, on saper oit que les lignes fonc es

localement parall les appel es stries ou cr tes caract risent la forme de lempreinte. On peut

r pertorier trois grandes familles dempreintes : arches ou tentes (fig1), boucles droite

(fig2) ou boucles gauche, spires ou verticilles ou tourbillons (fig3).

Ces trois types dempreintes regroupent 95% des doigts humains : 30% pour les spirales, 60%

pour les boucles et 5% pour les tentes.

Figure 1 Figure 2 Figure 3

Des dessins beaucoup plus rares sont par exemple des doubles boucles imbriqu es.

.

Empreinte assez rare : deux spirales

6

b. Points singuliers

Les l ments qui permettent

de diff rencier deux

empreintes digitales ayant le

m me motif sont :

(cid:1) Dune part les points

singuliers globaux :

noyau ou centre :lieu de

convergences des stries.

delta : lieu de divergences des

stries.

(cid:1) Dautre part les points

singuliers locaux :

les minuties : points dirr gularit se

trouvant sur les lignes capillaires.

On peut relever jusqu seize types de minuties mais dans les algorithmes on nen retient

g n ralement que quatre types:

(cid:3) Terminaison droite ou gauche (minutie situ e en fin de strie): figure a.

(cid:3) Bifurcation droite ou gauche (intersection de deux stries) : figure b.

On peut citer galement :

(cid:3) le : assimil e deux terminaisons : figure d et e.

(cid:3) Lac : assimil e deux bifurcations : figure c.

Types de minuties possibles (stries en noir)

7

B. Traitement informatique dune empreinte digitale

Diff rents proc d s que nous ne d velopperons pas ici permettent lacquisition cest dire la

capture de lempreinte.

Limage dorigine est binaris e (noir et blanc) puis squelettis e (les stries ont toutes la m me

paisseur de 1 pixel).

On peut ensuite gr ce diff rents algorithmes extraire les minuties et jecter les fausses .

On r cup re ainsi en moyenne une centaine de minuties par empreinte.

On obtient alors la signature de lempreinte.

Chaque minutie est rep r e et r pertori e comme suit :

" Le type de minutie : bifurcation ou terminaison.

" La position de la minutie dans limage : coordonn es (

" La direction du bloc local associ la strie : q

)yx;

.

Cette tape permet alors le stockage de la signature int gr e ensuite dans une base de donn es

au moyen dune technique darchivage cest la classification. Ce fichier a une taille inf rieure

0,5 Ko ce qui est un gain de m moire non n gligeable par rapport au stockage dimages

consommatrices de Ko.

8

C. Traces et empreintes

Sur les lieux dun d lit ou dun crime, les agents de la police scientifique rel vent des

morceaux dempreintes appel s traces.

Ces traces sont captur es, trait es informatiquement et le proc d didentification est

possible.

Combien de minuties sont rep rer pour permettre de d terminer une corr lation entre

une trace de quelques millim tres carr s et une empreinte ? Le chiffre 12 en France, 8

aux Etats-Unis&.. ?

9

III. Essais de mod lisations de formes et de minuties

Nous nous proposons de mod liser laide d quations math matiques les trois principales

familles dempreintes. Pour les repr sentations graphiques, nous utiliserons les logiciels excel

et g oplan.

Il existe des logiciels de cr ation artificielle dempreintes permettant de tester des

programmes de reconnaissances.

Pour r aliser nos mod lisations, nous avons utilis les images de pseudo-empreintes produites

par le logiciel FingerPrint Creator de Optel10. Ces images correspondaient des empreintes

non d form es, par exemple une empreinte en spire avec quelques minuties :

10 http://www.optel.com.pl/software/english/method.htm

10

A. Mod lisation dune empreinte en forme darche avec huit

minuties.11

Nous avons choisi une famille de courbes

est donn e par :

a

x

0,3

+

=

a

y

3

avec a variant de 2 3,6 avec un pas de 0,1 et x compris entre -3 et 10,5.

aC (cubiques dAgnesi) dont l quation g n rale

A laide du tableur excel nous avons tabli un tableau de valeurs et repr sent ces diff rentes

fonctions (voir figure page 15 ). Les minuties de type terminaison ont t obtenues par

interruption du tableau de valeurs et celles de type bifurcation ont t obtenues en tra ant

des segments.

11 Fichier arches.xls

11

Rep rage des minuties

Repr sentation graphique de lempreinte

-4

-2

y2

y2.9

bif1'

0

2

4

y2.1

y3

bif2

y2.2

y3.1

bif2'

y2.3

y3.2

bif3

y2.4

y3.3

bif3'

6

y2.5

y3.4

bif4'

8

10

12

y2.7

y3.6

y2.8

bif 1

y2.6

y3.5

bif4'

Remarque : le probl me de cette mod lisation est de respecter l' cart entre deux lignes

papillaires suppos constant.

12

B. Mod lisation dune empreinte en forme darche12

Logiciel utilis : g oplan

Figure obtenue :

On choisit un rep re (

;OIO;

)OJ

non orthonorm pour ne pas avoir

un axe de sym trie vertical .

I(1 ;0) et J(0,3 ;1) dans un rep re

orthonorm initial.

Les courbes ont pour quation :

=

y

3

a

+

2

b

.

2

x

A laide du logiciel, nous avons

observ les courbes obtenues selon les valeurs prises par a et par b.

Dans notre programme : a appartient lintervalle [

]8,2;5,0

et b lintervalle [1 ;2,8]

Texte du prototype cr e

D but de

a r el donn

b r el donn

I point de coordonn es (1,0) dans le rep re Roxy

J point de coordonn es (0.3,1) dans le rep re Roxy

r rep re (o,vec(o,I),vec(o,J)) (graduations: 1,1)

c courbe d finie par Y=a^3/(X^2+b^2), X d crivant [-3,3] (200 points, rep re r)

Description de l'interface

c courbe de a et b

Ant c dent 1 (nombre r el):

Ant c dent 2 (nombre r el):

R sultat (courbe):

Aide particuli re non crite.

Fin de

12 Fichier arches.g2w

Le texte int gral du programme figure en annexe 1.

13

C. Mod lisation dune empreinte en forme de spire avec six

minuties13

Logiciel utilis : g oplan

" Figure obtenue et r sum de la d marche utilis e

rep re (

)OJ

Pour d former les courbes, nous navons pas utilis le rep re orthonorm initial mais un

;OIO;

non orthonorm o I(1 ;0) et J(0,2 ;1,2) dans le rep re orthonorm initial.

La difficult principale tait de cr er des minuties tout en gardant des distances peu pr s

r guli res entre les spires.

Figures obtenues

Commentaire de la figure

Les coordonn es affich es sont celles des minuties dans le rep re orthonorm initial.

Les minuties apparaissent par appuis successifs sur les touches 1, 2, 3, 4, 5 et 6.

L'empreinte est effac e par appui sur la touche 7

A/R

:(4.88,-15.51)

B/R

:(23.55,23.55)C/R

:(16.08,-51.15) D/r:(14.3,-53.36) E/R

:(-36.88,55.31) F/R

:(-69.31,-69.31)

oxy

oxy

oxy

oxy

oxy

13 Fichier spires.g2w

Le texte int gral du programme figure en annexe 2.

14

D marche utilis e

Cr ation des courbes et dinterruptions

On fait tracer le d but de la spirale dArchim de de pas 2p .

Elle a pour quation polaire

t=r

ou encore pour courbe param tr e

t

;0

p

19

4

.

, on choisit

( )

tx

( )

ty

=

=

t

t

cos

t

sint

Extrait du texte de la figure

c1 courbe param tr e par X=tcos(t), Y=tsin(t), t d crivant [0,19pi/4] (500

points, rep re r)

On veut cr er une interruption, on a choisi dentourer la

p

19

p

27

( car

spirale par un cercle de rayon

27p

4

respecte ainsi un cart de 2p entre le point dinterruption de la

spirale et le point du cercle de m me angle polaire)

Extrait du texte de la figure

c3 courbe en polaires: rho=27pi/4, t d crivant [0,2pi] (500 points, rep re

r)

, on

p

2

=

+

4

4

Pour quil ny ait pas un cart trop important entre la spirale et

le cercle, on fait tracer un arc de cercle de rayon

ayant

19p

4

pour extr mit la fin de la premi re spirale.

Extrait du texte de la figure

c2 courbe param tr e par X=(19pi/4)cos(t), Y=(19pi/4)sin(t), t d crivant

[3pi/4,5pi/3] (500 points, rep re r)

15

A

Pour visualiser la minutie (interruption) ; on cr e un cercle de

centre A et un segment qui a pour support la tangente en A au

cercle.

Extrait du texte de la figure

A point de coordonn es ((19pi/4)cos(5pi/3),(19pi/4)sin(5pi/3)) dans le

rep re r

Objet dessinable A, particularit s: nom droite, marque paisse

m1 cercle de centre A et de rayon 5 (unit Uoxy)

Objet dessinable m1, particularit s: rouge, trait pais

d1 droite passant par A et de coefficient directeur -cos(5pi/3)/sin(5pi/3)

(rep re r)

Objet dessinable d1, particularit s: non dessin

A1 point d'intersection 1 de la droite d1 et du cercle m1

Objet dessinable A1, particularit s: rouge, non dessin

A2 point d'intersection 2 de la droite d1 et du cercle m1

Objet dessinable A2, particularit s: non dessin

d'1 droite munie du rep re (A,vec(A,A1)) graduation 1

Objet dessinable d'1, particularit s: non dessin

A3 point d'abscisse 2 dans le rep re d'1

Objet dessinable A3, particularit s: rouge, non dessin

Segment

Objet dessinable , particularit s: rouge, trait pais

On continue le proc d .

La courbe est compos e de :

" parties de spirales (en bleu)

" cercles (en vert)

" arcs de cercles (en rouge)

" courbes d quation polaire

( )tf=r

o f est une

fonction affine de t (en noir), voir exemple ci-dessous.

Exemple de r alisation dune minutie bifurcation

N

M

)

p

p

M

cos

cos

-

;

3

( )

p

18:0

p

47

sin(

3

)0

( )

sin

p

47

3

(

pN

18

On a cherch tracer une courbe reliant M N d quation

polaire de la forme

3

ou encore.

o f est une fonction affine de t

( )

0 =

-

3

( )

tf

On obtient

.

Extrait du texte de la figure

c8 courbe en polaires: rho=7t+18pi, t d crivant [-pi/3,0] (500

points, rep re r)

( )tf=r

p

47

3

p18

7 +

=

= t

telle que

p18

et

.

p

f

f

16

-

D. Mod lisation dune empreinte en forme de boucle14

Logiciel utilis : g oplan

Figure obtenue :

Apr s quelques essais infructueux obtenus partir de la fonction

cosinus (la p riodicit de la fonction posait trop de probl mes), il a

t plus simple de travailler partir de la fonction cosinus

hyperbolique.

On choisit un rep re (

)OJ

;OIO;

non orthonorm pour ne pas avoir

un axe de sym trie vertical .(I(1 ;0) et J(0,2 ;1) dans un rep re

orthonorm initial).

Les courbes ont pour quation :

y

+

-=

a

ch

2

puis a varie dans lintervalle [

1,0=a

x

a

a

3

,

]5,7;5,0

avec un pas de 0,5

Texte du prototype cr e

D but de

a r el donn

I point de coordonn es (1,0) dans le rep re Roxy

J point de coordonn es (0.2,1) dans le rep re Roxy

r rep re (o,vec(o,I),vec(o,J)) (graduations: 1,1)

c courbe d finie par Y=-(a/2)(exp(X/a)+exp(-X/a))+3a, X d crivant [-20,20] (500 points, rep re r)

Description de l'interface

c courbe param tre a

Ant c dent 1 (nombre r el):

R sultat (courbe):

Aide particuli re non crite.

Fin de

14 Fichier boucles.g2w

Le texte int gral figure en annexe 3.

17

E. Mod lisation dune bifurcation laide de courbes de

B zier15

Logiciel utilis : g oplan

Figure obtenue :

Les courbes ont pour

quation

y

=

1

+

2

x

1

+

a

, a

varie dans lintervalle

]5,0;3-

[

avec un pas de 0,5.

D marche utilis e pour la minutie bifurcation

D

D'

A

B

E

C

C'

On interrompt la courbe verte entre A et E

B appartient la partie interrompue de cette courbe.

On interrompt les deux courbes noires respectivement en D et D.

C et C appartiennent respectivement ces deux parties interrompues.

On fait tracer en bleu la courbe de B zier avec 4 points de contr le A, B, C et D :

" elle passe par les extr mit s A et D,

"

la tangente en A a pour vecteur directeur AB (en rouge),

"

la tangente en D a pour vecteur directeur CD (en rouge).

De m me on fait tracer en bleu la courbe de B zier avec 4 points de contr le A, B C et D.

Extrait du texte de la figure :

b1 courbe param tr e par X=(1-t)^3(-3)+3t(1-t)^2(-2)+3t^2(1-t)*(-1.5)+t^3(-0.5), Y=(1-t)^3(-0.4)+3t(1-t)^2(-

0.3)+3t^2(1-t)0.307+t^3(0.8), t d crivant [0,1] (500 points, rep re Roxy)

Objet dessinable b1, particularit s: ciel, trait pais, points li s

Remarques : il a fallu cr er une interruption qui va de pair avec la bifurcation.

Le probl me de la gestion d carts peu pr s r guliers entre les courbes reste non r solu.

15 Fichier bifurcation.g2w

Le texte int gral du programme figure en annexe 4

18

IV. Mod les de classifications dempreintes

A. Classification propos e par Galton (1891)16

Cette classification est expos e dans larticle intitul Method of indexing Finger-Marks paru

en 1891

Tableau des mod les

Explications du tableau ci-dessus :

Il existe trois sortes de formes :

Les primaires (arches) cod es 1 ou 2

1 pour celles qui ont un axe de sym trie, cest dire a, b et c,

2 pour les autres, cest dire d, e, f et h

Les spires cod es 3 ou 4

3 pour celles qui ont un axe normal , cest dire h et i,

4 pour les autres, cest dire j, k, l et m.

Les boucles cod es 5 ou 6

Elles nont pas daxe de sym trie, leur code est 5 si leur pente est normale , 6 sinon.

Pente normale empreinte main gauche :

Pente normale empreinte main droite :

La parit du code d pend donc de la normalit de lempreinte, les codes pairs sont plus

rares.

16 Il en existe dautres du m me auteur

19

Code des doigts

Pouce (thumb)

T

Index

1

Majeur

2

Annulaire

3

Auriculaire

4

Exemple de tableau

Galton reporte sur diff rents

tableaux les codes correspondants

aux dix doigts dune centaine de

personnes.

Il tudie les corr lations ventuelles

entre les formes et les doigts, les

fr quences de chaque forme

diff rent en effet selon le doigt.

Cest pour ces raisons que les doigts

ne sont plus dans lordre naturel

dans les colonnes de gauche.

Expliquons la ligne correspondant la quatri me personne :

Colonne left :

Auriculaire gauche : doigt 4

Annulaire gauche : doigt 3

doigt 2

Majeur gauche :

doigt 1

Index gauche :

doigt T

Pouce gauche :

Colonne right :

Pouce droit :

Index droit:

Majeur droit :

Annulaire droit:

Auriculaire droit :

doigt T

doigt 1

doigt 2

doigt 3

doigt 4

code 5 (boucle pente normale)

code 3 (spire avec axe)

code 5 (boucle pente normale)

code 3 (spire avec axe)

code 3 (spire avec axe)

code 3 (spire avec axe)

code 6 (boucle pente anormale)

code 5 (boucle pente normale)

code 3 (spire avec axe)

code 5 (boucle pente normale)

Ces codes sont report s et correspondent aux dix chiffres de gauche dans le tableau.

20

Exemple de tableau r capitulatif pour les formes concernant lindex gauche

Il y a donc :

30 % darches

29 % de spires

41 % de boucles

Ces tableaux pourraient tre refaits aujourdhui rapidement avec un tableur !

21

B. Classification de Henry ( 1896)

Code pour chaque forme :

Arche

A

Boucle

L

Spire

W

Cette classification est li e au syst me binaire

Les dix doigts sont cod s par une suite de dix lettres (A, L ou W), chaque doigt est

attribu un entier de 1 10.

Si un doigt a une empreinte en spirale, il lui est attribu une valeur qui est une puissance

de deux : 16, 8, 4, 2 ou 1, selon le doigt dont il sagit, sinon, il lui est attribu 0.

Le tableau ci-dessous donne lordre des doigts, lentier attribu , ainsi que sa valeur sil a

une forme de spirale:

Pouce

droit

1

Index

droit

2

Majeur

droit

3

Annulaire

droit

4

Auriculaire

droit

5

Pouce

gauche

6

Index

gauche

7

Majeur

gauche

8

Annulaire

gauche

9

Auriculaire

gauche

10

16

16

8

8

4

4

2

2

1

1

Num ro

du

doigt

Valeur

si

spirale

Exemple 1: LWAALALWLA

Num ro du

doigt

Type

dempreinte

Valeur

attribu e

1

2

3

4

5

6

7

8

9

10

boucle

spirale

arche

arche

boucle

arche

boucle

spirale boucle

arche

0

16

0

0

0

0

0

2

0

0

On calcule alors le rapport suivant :

=

r

+

(1

+

(1

somme

somme

des

des

valeurs

valeurs

attribu es

attribu es

aux

aux

num ros

num ros

pairs

)

impairs

)

Dans lexemple ci-dessus.

Lindividu appartient au groupe 19 :1.

22

Exemple 2 : reprenons la quatri me personne du tableau de Galton

Num ro du

doigt pour

Galton

Forme

Num ro du

doigt pour

Henry

Lettre

correspondante

Valeur

attribu e

T

1

2

3

4

T

1

2

3

4

Spire Boucle Boucle Spire Boucle Spire

1

2

3

6

4

5

Spire Boucle Spire Boucle

7

10

8

9

W

16

L

0

L

0

W

8

L

0

W

4

W

2

L

0

W

1

L

0

Dans ce nouvel exemple.

Lindividu appartient au groupe 13 :20.

=

++++

++++

)1248

)1248

Remarques

Un individu qui na aucune spirale appartient au groupe 1 :1.

Un individu qui na que des spirales appartient au groupe 32 :32

+

16(1

+

16(1

Chaque terme de cette fraction est gal

1+(16 ou 0)+(8 ou 0)+(4 ou 0)+(2 ou 0)+ (1 ou 0).

Il y a donc

5

2

2

2

Au total, la classification comporte 1024 groupes.

52 sommes possibles.

10

.

32

32

024

=

=

.

1

5

Lunicit de la d composition dun entier en base 2 permet de valider la classification de

Henry.

A chaque codage des dix doigts (L et A non distingu s), correspond un unique rapport r

dont le num rateur et le d nominateur sont compris entre 1 et 32.

R ciproquement, chaque rapport r dont le num rateur et le d nominateur sont compris

entre 1 et 32 correspond un unique codage (L et A non distingu s).

23

On peut utiliser un tableur pour convertir rapidement les classifications de Henry

correspondant aux observations de Galton17 :

Les lignes 13 et 14 donnent les classifications des dix lignes du tableau de Galton.

Formules utilis es

17 fichier Henry.xls

24

Id es pour une exploitation en classe :

En seconde, en TS sp cialit ou en L sp cialit math matiques :

Travail sur la num ration en base 2.

Quel est le plus grand nombre de 5 chiffres en binaire ?

D nombrement des classifications.

Connaissant les formes de dessins dempreintes, donner la classification.

On peut ventuellement utiliser un tableur :

Probl me r ciproque :

Connaissant le groupe, faire retrouver les doigts (sachant quon ne peut pas distinguer

pour la r ciproque A et L).

On peut approfondir en liaison avec lunicit de l criture dun nombre en syst me

binaire.

25

Formules utilis es

26

V. Empreintes et probabilit s

Probabilit dune configuration de minuties

Pour calculer la probabilit que deux empreintes digitales soient identiques, il faut estimer le

nombre total dempreintes digitales pouvant exister ou tre g n r es. Pour cela, des mod les

diff rents ont t propos s.

A. Le mod le propos par Galton (1892)

Comment Galton d montre quil y a une chance sur 64 milliards que deux individus aient

les m mes empreintes.

On attribue Galton les premiers calculs de probabilit dans son ouvrage Finger Prints

paru en 1892.

Galton : Our problem is this: given two finger prints, which are alike in their minutiaes,

what is the chance that they are made by different persons?

R sum de ce premier essai de th orie didentification des empreintes digitales 18.

a) Comment Galton prouve que la seule observation des formes

dempreintes ne suffit pas. Combien existe-t-il dempreintes digitales

d...