air - User contributions [en]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-27T22:52:10Z

Renaud C: /* Sources */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Diagramme de Gantt effectif=

[[File:Diagramme-de-Gantt.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

Nous avons ajouté une option "faussaire" sur cette onglet. Lorsque l'option est cochée, la signature du compte sur lequel l'utilisateur essaie de s'identifier est affiché sur l'écran de signature. Cette option a été mise en place pour tester d'avantage notre système. Ainsi nous pouvons voir si, avec le dessin de la signature, un imposteur peut réussir à s'identifier.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

Lorsque l'utilisateur a tenté de s'identifier, il peut alors consulter différentes informations liées à sa tentative :

[[File:ihm31.png]]

''Le pourcentage de fausses acceptations et faux refus''

[[File:ihm32.png]]

''Un graphe qui affiche l'évolution de la pression sur la signature référence de l'utilisateur et sur sa dernière acquisition''

[[File:ihm33.png]][[File:ihm34.png]]

''Les informations du traitement algorithmique comme l'arbre de décision ou les résultats des différentes étapes de l'algorithme''

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

Cette méthode permet de calculer la ressemblance existante entre deux séries de données de même longueur, à savoir l'évolution des coordonnées en fonction du temps.

[[File:Equa.png]]

Le Résultat varie entre 1 et -1.

Plus le résultat est proche de 0, moins la relation est forte entre les deux listes de données.

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

[[Media:Rapport_des_seances.pdf|Rapport des séances]]

[[Media:Dossier_de_conception.pdf|Dossier de conception]]

[[Media:Notes_et_Conseils.pdf|Notes et Conseils]]

[[Media:SoutenanceProjetBiometrieSignatures.pdf|Présentation du projet]]

=Sources=
http://subversion.assembla.com/svn/projet-biometrie/

[[Media:SourcesBiometrieSignatures.rar|Archive des sources (+dll +lib +dump bdd)]]

File:SourcesBiometrieSignatures.rar

2012-03-27T22:48:45Z

Renaud C:

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-27T22:40:17Z

2012-03-27T08:53:15Z

Renaud C: /* Documents */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Diagramme de Gantt effectif=

[[File:Diagramme-de-Gantt.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

Nous avons ajouté une option "faussaire" sur cette onglet. Lorsque l'option est cochée, la signature du compte sur lequel l'utilisateur essaie de s'identifier est affiché sur l'écran de signature. Cette option a été mise en place pour tester d'avantage notre système. Ainsi nous pouvons voir si, avec le dessin de la signature, un imposteur peut réussir à s'identifier.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

Lorsque l'utilisateur a tenté de s'identifier, il peut alors consulter différentes informations liées à sa tentative :

[[File:ihm31.png]]
''Le pourcentage de fausses acceptations et faux refus''

[[File:ihm32.png]]
''Un graphe qui affiche l'évolution de la pression sur la signature référence de l'utilisateur et sur sa dernière acquisition''

[[File:ihm33.png]][[File:ihm34.png]]
''Les informations du traitement algorithmique comme l'arbre de décision ou les résultats des différentes étapes de l'algorithme''

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

Cette méthode permet de calculer la ressemblance existante entre deux séries de données de même longueur, à savoir l'évolution des coordonnées en fonction du temps.

[[File:Equa.png]]

Le Résultat varie entre 1 et -1.

Plus le résultat est proche de 0, moins la relation est forte entre les deux listes de données.

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

[[Media:Rapport_des_seances.pdf|Rapport des séances]]

[[Media:Dossier_de_conception.pdf|Dossier de conception]]

File:Diagramme-de-Gantt.png

2012-03-27T08:11:48Z

Renaud C:

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-27T08:11:04Z

Renaud C:

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Diagramme de Gantt effectif=

[[File:Diagramme-de-Gantt.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

Nous avons ajouté une option "faussaire" sur cette onglet. Lorsque l'option est cochée, la signature du compte sur lequel l'utilisateur essaie de s'identifier est affiché sur l'écran de signature. Cette option a été mise en place pour tester d'avantage notre système. Ainsi nous pouvons voir si, avec le dessin de la signature, un imposteur peut réussir à s'identifier.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

Cette méthode permet de calculer la ressemblance existante entre deux séries de données de même longueur, à savoir l'évolution des coordonnées en fonction du temps.

[[File:Equa.png]]

Le Résultat varie entre 1 et -1.

Plus le résultat est proche de 0, moins la relation est forte entre les deux listes de données.

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

[[Media:Rapport_des_seances.pdf|Rapport des séances]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T14:17:55Z

Renaud C: /* Coefficient de corrélation temporel */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

Nous avons ajouté une option "faussaire" sur cette onglet. Lorsque l'option est cochée, la signature du compte sur lequel l'utilisateur essaie de s'identifier est affiché sur l'écran de signature. Cette option a été mise en place pour tester d'avantage notre système. Ainsi nous pouvons voir si, avec le dessin de la signature, un imposteur peut réussir à s'identifier.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

Cette méthode permet de calculer la ressemblance existante entre deux séries de données de même longueur, à savoir l'évolution des coordonnées en fonction du temps.

[[File:Equa.png]]

Le Résultat varie entre 1 et -1.

Plus le résultat est proche de 0, moins la relation est forte entre les deux listes de données.

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

[[Media:Rapport_des_seances.pdf|Rapport des séances]]

File:Rapport des seances.pdf

2012-03-26T13:16:16Z

Renaud C:

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T13:15:20Z

Renaud C: /* Documents */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

[[Media:Rapport_des_seances.pdf|Rapport des séances]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:27:16Z

Renaud C: /* Génération d'un modèle classification */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de [http://www.cs.waikato.ac.nz/ml/weka WEKA] pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:25:40Z

Renaud C: /* Classification par arbre de décision */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle a rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:19:21Z

Renaud C: /* Matrice de radiation */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
modifie leur valeur suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:14:01Z

Renaud C: /* Dynamic Time Warping */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarités entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
fait passer leur valeur à certains seuils, suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:10:08Z

Renaud C: /* 6. Ré-échantillonnage sur le nombre de points */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelques-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarité entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
fait passer leur valeur à certains seuils, suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T12:07:12Z

Renaud C: /* 4. Centrage et Rotation */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation. Cette rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelque-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarité entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
fait passer leur valeur à certains seuils, suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T11:50:15Z

Renaud C: /* Prétraitement des acquisitions */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auxquels sont rattachés une abscisse, une ordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation.La rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelque-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarité entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
fait passer leur valeur à certains seuils, suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-26T11:28:36Z

Renaud C: /* Documents */

=Présentation du projet=

Le projet de Biométrie "Acquisition et reconnaissance de signatures" consiste à enregistrer une signature numérique d'un client ou utilisateur afin de permettre ultérieurement une identification grâce à cette modalité biométrique.

=Contexte=
===Etude de l'existant===

Ce projet d'acquisition et de reconnaissance de signatures a déjà été traité par une équipe d'étudiants en 2010-2011. Nous avons donc étudié ce qui avait été réalisé afin de ne pas perdre les efforts déjà fournis. De cette étude nous avons retenu les conseils et remarques faits sur la partie algorithmique de comparaison de signatures. De plus, nous allons reprendre quelques idées de leur IHM.
Pour plus de détails, consulter les parties "Algorithmes" et "IHM".

===Suites prévues===
L'année prochaine, une nouvelle équipe reprendra surement ce projet de biométrie. Il est donc important de laisser une bonne documentation et des conseils.

=Cadre de réponse=

Nous réaliserons une IHM qui nous permettra, d'une part, d'enregistrer un nouvel utilisateur dans la base de données (acquisition de signature), et d'autre part de tester l'identification d'un utilisateur. Pour cette identification, la signature sera comparée au modèle calculé et enregistré. Afin de pouvoir effectuer cette comparaison, nous récupèrerons, lors de l'acquisition des signatures, différentes informations qui nous permettront d'appliquer des algorithmes de comparaison de signatures (coordonnées de chaque point, pression du stylet, temps). Il faudra donc étudier les différentes méthodes possibles de comparaison de ces signatures et implémenter l'algorithme conçu à partir de cette étude.

=Organisation de l'équipe=

'''Renaud Collin''' :

*Chef de projet
*Responsable documents,
*Etude de l'existant

'''Flavien Garcia & Corentin Foucault :'''

*Etude de l'existant,
*Construction et codage de l'algorithme

'''Christophe Havard :'''

*Montage DS + Arduino,
*Conception et codage IHM

'''Thibaud Michel''' :

*Acquisition des données (depuis le montage DS + Arduino et depuis la tablette),
*Mise en place de la base de données,
*Conception et codage IHM

'''Aurélie Moiroux :'''

*Acquisition des données depuis la tablette,
*Conception et codage IHM

=Diagramme de Gantt prévisionnel=

[[File:Diagramme-de-Gantt-previsionnel.png]]

=Matériel=
===Tablette Bamboo CTH-460===

Cette tablette est un ajout de matériel par rapport à l'année précédente. Ainsi, nous avons pour notre projet deux interfaces pour l'acquisition des signatures. Cela nous a donc amené à étudier la tablette graphique et les librairies Java permettant de nous en servir.
L'IHM a également été modifiée pour permettre à l'utilisateur de choisir quelle interface d'acquisition il souhaite utiliser.

*La librairie permettant d'utiliser cette tablette est : Jpen [http://sourceforge.net/apps/mediawiki/jpen/index.php?title=Main_Page]
*Le driver de la tablette CTH-460 est disponible ici : [http://www.wacom-asia.com/download/download_index.html]

[[File:bamboo.jpg]]

===Montage Arduino + Ecran de DS===
[[File:Arduino_DS.png]]

[[File:Arduino.png]]

[[File:Arduino2.png]]

=IHM=

Lorsque l'utilisateur démarre l'application, celle-ci s'ouvre sur l'onglet "Nouvel utilisateur". Si il n'a pas encore de compte, il doit alors rentrer son nom, son prénom, et procéder à l'acquisition de cinq signatures (la même) afin de pouvoir s'enregistrer.

''Onglet "Nouvel Utilisateur"''

[[File:ihm1.jpg]]

Une fois que l'utilisateur possède un compte, il peut se rendre sur l'onglet "Identification". Afin de s'authentifier l’utilisateur doit sélectionner son nom, puis signer de la même signature que lors de l'acquisition.

''Onglet "Identification"''

[[File:ihm2.jpg]]

Le système affiche alors la réponse de l'authentification : la réussite ou l’échec. Une question apparaît également afin d'établir des statistiques de performance du système.

[[File:ihm21.jpg]]

''Onglet "Infos"''

[[File:ihm3.jpg]]

=Algorithmes=

Un système de reconnaissance par signature nécessite l'application d'algorithmes, que ce soit dans un premier temps pour obtenir des acquisitions de qualité, qu'ensuite pour pouvoir les comparer de manière cohérente et enfin construire un modèle efficace de reconnaissance.

==Prétraitement des acquisitions==
Les acquisitions obtenues par l'intermédiaire de l'interface, pour représenter la signature d'un individu, sont des listes de points, auquels sont rattachés une abscisse, une coordonnée, une valeur de pression et un temps d'acquisition.
Cependant, il est nécessaire d'appliquer un prétraitement à ces acquisitions afin d'en augmenter le nombre de points, corriger les différences entre des signatures successives (décalage, orientation et taille) et également obtenir un nombre de points fixe pour toutes les acquisitions pour pouvoir les comparer.

Voilà une image d'une acquisition originale:

[[File:0_origine_Aurélie_4.png|600px]]

===1. Ré-échantillonnage sur le temps===
La première étape est propre à l'utilisation de la tablette Bamboo et consiste à ne conserver qu'un seul point par temps d'acquisition. En effet, le système d'acquisition de la tablette renvoie la liste de points acquis durant chaque période de 16ms et attache à chaque point cette période d'acquisition plutôt que le temps réel.
Par exemple les points acquis en réalité aux temps 11ms et 14,5ms seront enregistrés avec un temps d'acquisition de 16ms alors qu'un point acquis au temps 16,8ms sera enregistré avec un temps d'acquisition de 32ms.
Nous avons considéré que ce temps de 16ms étant relativement court, on ne conserverait qu'un seul point pour un même temps d'acquisition (par défaut le premier de la liste).

De plus, on a également considéré que deux points espacés d'un temps d'acquisition supérieur à 32ms correspondait à un lever de stylo.

===2. Interpolation===

On applique une interpolation cubique sur l'acquisition dans le but d'obtenir un rendu de signature plus continu et lisse, et mieux comprendre les courbures de la signature d'un individu. De plus, il est nécessaire de travailler sur des données assez fournies notamment pour des algorithmes de recouvrement par exemple.

[[File:0_interpolee_Aurélie_4.png|600px]]

===3. Analyse en composantes principales===

[[File:PCA.png]]

L'ACP est utilisé pour trouver les informations mathématiques qui décrivent la position des points: {{rouge|l'axe principal}} et {{bleu|l'axe secondaire}} et le centre de gravité d'une forme binaire.

===4. Centrage et Rotation===
[[File:0_centree_Aurélie_4.png|600px]]

[[File:0_droite_Aurélie_4.png|600px]]

Pour réduire les problèmes de décalage, entre l'image à tester et le modèle, on utilise les informations fournies par l'ACP.

Le centre de gravité permet de centrer l'image comme le modèle.

Les deux axes qui décrivent l'alignement des points permettent de faire la rotation.La rotation est calculée à partir de l'angle entre l'axe principal et l'axe horizontal.

===5. Normalisation (Zoom)===
[[File:0_normalisee_Aurélie_4.png|600px]]

Le zoom est calculé pour obtenir la taille la plus grande possible pour l'image.

La distance entre le centre et le point le plus proche du rebord de l'image évaluée = (distance max).

Chaque point subit alors une translation proportionnelle au rapport (distance du point/distance max)*(demi-largeur de l'image).

===6. Ré-échantillonnage sur le nombre de points===

Suivant la durée totale d'acquisition, le nombre de points acquis peut être plus ou moins important et les précédentes étapes de prétraitement peuvent en supprimer quelque-uns également. Il est donc essentiel d'effectuer un ré-échantillonnage sur les acquisitions après normalisation pour obtenir un nombre de points fixe (2000 points choisis actuellement) pour que les différents algorithmes de comparaison soient cohérents.
On a choisi d'interpoler des points de manière uniforme si le nombre de points était inférieur à 2000 et d'en supprimer, également de manière uniforme, si ce nombre était supérieur.

==Algorithmes de comparaison==

Pour la création du modèle (voir plus loin), il est nécessaire d'obtenir un ensemble de données de comparaisons. On a ainsi sélectionné les comparaisons suivantes

===Comparaisons simplistes===

*Différence de temps total d'acquisition
*Différence de nombre de lever de stylos
*Différence de pression moyenne
*...

===Coefficient de corrélation temporel===

A COMPLETER

===Dynamic Time Warping===

Les données des signatures sont converties en graphe temporel. Par exemple : x/temps ; y/temps ; etc.

La méthode du DTW permet de calculer les dissimilarité entre les informations.

Ici, les deux listes permettent de calculer une matrice dont le dernier élément contient la distance minimale entre les deux listes d'informations.

===Matrice de radiation===

La matrice de radiation est une méthode de reconnaissance de forme.

Il existe deux possibilités pour calculer la matrice modèle :

1- Les points de la signature sont placés avec une valeur de 100. Autour de ces points, les cellules subissent une radiation qui
fait passer leur valeur à certains seuils, suivant la distance entre la cellule mentionnée et les points originaux de la signature.
Chaque cellule de la matrice ne peut que subir le rayonnement du point original le plus proche.

2- De même que précédemment sauf que chaque cellule de la matrice subie la somme des rayonnements des points originaux.

Après l'évaluation de cette matrice modèle, le calcul se fait de deux manières différentes :

1- Le résultat est la somme des valeurs enregistrées, dans la matrice modèle, qui sont aux coordonnées des points de la signature à tester.

2- Le résultat est le rapport du nombre de cellules non nulles communes entre la matrice modèle et la signature à tester et le nombre de cellules non nul total.

===Somme des différences d'angles entre vecteurs===

Cette méthode permet une reconnaissance de forme simple.

Elle permet d'obtenir l'angle d'écart entre la signature à tester et le modèle.

Le résultat est la somme des angles entre chaque vecteur et le vecteur horizontal. Chaque angle est compris entre -Pi et Pi.

==Génération d'un modèle classification==

Afin de réaliser la tâche de vérification pour la reconnaissance de signature, nous avons opté pour le choix de WEKA pour la création du modèle par apprentissage et la décision finale.

===Construction du fichier de comparaison (apprenstissage.arff)===

WEka utilise des fichiers ARFF pour construire et tester son modèle. Dans ce fichier on retrouve dans l'ordre:

* Le nom de la relation (utile pour nommer le fichier d'apprentissage aux fichiers d'identification et de décision)

@relation signature

* La liste des attributs de comparaison utilisés et leur type

@attribute totalTime numeric

@attribute numberPenUp numeric

...

@attribute CORTX numeric

@attribute CORTY numeric

@attribute pourcentageRadiance numeric

* L'attribut contenant les différentes classes (2 dans notre cas: signatures équivalentes ou non)

@attribute accepte {no,yes}

* Les données de comparaisons entre différentes signatures

@data

1019.466796875,2.0,0.9912756661011811,0.9970564473307176,17.837034225463867,yes

663.466796875,0.0,0.9837515744201278,0.996214642908734,15.106257438659668,yes

...

1278.466796875,0.0,0.9729839482086351,0.9951841501724467,9.820034980773926,no

1044.06640625,0.0,0.9859247460800329,0.9970413832907982,9.922861099243164,no

Pour construire ces données, on doit donc comparer des signatures équivalentes (d'une même personne) et des signatures différentes(de personnes différentes). Etant donné qu'un utilisateur enregistre 5 acquisitions pour former sa "signature", on peut donc réaliser 10 comparaisons entre signatures équivalentes par utilisateur.
Ainsi pour n utilisateurs, on aura 5*n comparaisons de signatures équivalentes.
Ensuite pour construire le modèle par apprentissage, il faut également comparer des signatures différentes. Pour cela, on effectue des comparaisons de manière aléatoire entre les signatures d'utilisateurs différents sans jamais refaire la même comparaison. On se permet de réaliser deux fois plus de comparaisons inter-utilisateur qu'intra-utilisateur (soit 10*n comparaisons).

===Construction du modèle===

Ensuite, on fournit ce jeu de données d'apprentissage à Weka qui construit son modèle selon le classifier choisi. Pour cela, il construit un modèle à partir des 9/10 des données et teste sur le 1/10 restant. Il répète l'opération 10 fois pour parcourir toutes les données et améliorer son modèle au fur et à mesure.

Nous avons opté pour un arbre de décision (plus précisément le J48) pour classer nos données parmi les nombreuses méthodes possibles car il nous permet à posteriori de voir quelles sont les paramètres discriminants et pour quelles raisons il a décidé que 2 signatures se ressemblaient ou non.

===Classification par arbre de décision===

Une fois le modèle construit, on peut via l'interface tenter de s'identifier en sélectionnant la personne que l'on prétend être et en faisant une acquisition. Le programme va alors récupérer les cinq acquisitions représentant la signature de la personne supposée, effectuer le prétraitement de ces acquisitions ainsi que de la nouvelle et les comparer comme pour la création du modèle.

On va ainsi créer un fichier ARFF "identification.arff" qui contiendra les données de comparaisons comme pour celui de l'apprentissage à la différence que le dernier attribut, celui de la classe, sera rempli d'un "?" pour signifier que c'est au modèle de décider à quelle classe associer cette comparaison (si les deux signatures se ressemblent ou pas).

Une fois que le modèle à rendu sa décision concernant ces cinq comparaisons, on a décidé que la personne avait réussie à s'identifier si la nouvelle acquisition était désignée comme ressemblante à au moins trois des cinq acquisitions enregistrées dans la base de données.

=Documents=

[[Media:Cahier_des_charges.pdf|Cahier des charges]]

File:Cahier des charges.pdf

2012-03-26T11:27:27Z

Renaud C:

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-21T12:11:09Z

Renaud C:

File:Arduino DS.png

2012-03-12T14:06:32Z

Renaud C: uploaded a new version of "File:Arduino DS.png"

File:Arduino DS.png

2012-03-12T14:04:35Z

Renaud C:

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-12T14:02:23Z

Renaud C: /* Montage Arduino + Ecran de DS */

PAGE WIKI ETUDIANTS 2011-12 SIGNATURES

2012-03-07T15:33:29Z

Renaud C: /* Organisation de l'équipe */

Projets 2011-2012

2012-03-07T15:02:29Z

Renaud C: /* RICM5 */

Lien vers [http://air.imag.fr/mediawiki/index.php/Projets_2010-2011 les projets 2010-2011]
==RICM4==

{|class="wikitable alternance"
|+ Affectation des projets RICM4 2011-2012
|-
|
!scope="col"| Sujet
!scope="col"| Enseignant(s)
!scope="col"| Etudiants
!scope="col"| Fiche de suivi
|-
!scope="row"| 1
| [[Qemu Cortex-M3 Boards | Qemu et carte ARM Cortex-M3]]
| Olivier Richard
| A.Clavelin, T. Eid, M. Mercier
| [[Proj-2011-2012-qemu | '''Fiche''' ]]
|-
!scope="row"| 2
| Risques Industriels:
| Didier Donsez, Didier Mazet-Brachet, Hassan Saïbi
| S. Vigier, F. Eloy
| [[Proj-2011-2012-Risques_Industriels | '''Fiche''']]
|-
!scope="row"| 3
| [[Home Security Sweet Home 2012]] + [[iVLC|Ventilation efficace énergétiquement]]
| Didier Donsez
| N.-J. Caramelli, M. Ho
| [[Proj-2011-2012-Home_Security_Sweet_Home | '''Fiche''']]
|-
!scope="row"| 4
| [[Camera d'observation à basse altitude]]:
| Didier Donsez, David Eon, Didier Hantz
| N. Tchounikine, T. Aufort
| [[Proj-2011-2012-CameraBasseAltitude | '''Fiche''']]
|-
!scope="row"| 5
| [[Education à la respiration]]
| Julie Fontecave, Pierre-Yves Gumery, Didier Donsez, Olivier Richard,
| M. Raoux, J. Segala
| [[Proj-2011-2012-ProjetAMO | '''Fiche''']]
|-
!scope="row"| 6
| [[Bras Robotique Handicap | Bras robotique à commande gestuelle pour le handicap]]
| Olivier Richard
| L. Xiao, M. Nicolaccini, Y. Fall, S. Prak
| [[Proj-2011-2012-BrasRobotiqueHandicap| '''Fiche''']]
|-
!scope="row"| 7
| [[Robot de télé-présence]]
| Didier Donsez
| F. Fourure, S. Bisch
| [[Pro-2011-2012-Telepresence | '''Fiche''']]
|-
!scope="row"| 8
| [[Visualisation de données volcanologiques]]
| Paule-Annick Davoine, Didier Donsez
| M. Chevallier, C. Oswald, C. Gnatto
| [[Proj-2011-2012-Visualisation_de_données_volcanologiques | '''Fiche''']]
|-
!scope="row"| 9
| [[elua arduino stm32F4 Discovery | eLua et approche Arduino sur STM32F4-DISCOVERY]]
| Olivier Richard
| S. Harrache, E. Paz
| [[Proj-2011-2012-elua-arduino | '''Fiche''']]
|-
!scope="row"| 10
| IHM mobile pour le visualisation et le contrôle d'onduleurs
| Didier Donsez
| Q. Gu, C. Wirth
| [[Proj-2011-2012-ihm_mobile_onduleurs| '''Fiche''']]
|-
!scope="row"| 11
| [[GroundCTRL]]
| Didier Donsez
| L. Dauvergne, F. Levêque, R. Ngouala
| [[Proj-2011-2012-GroundCTRL| '''Fiche''']]
|}

# [[Qemu Cortex-M3 Boards | Qemu et carte ARM Cortex-M3]]: ((extension de l'émulateur Qemu) (Olivier Richard) (2-3 RICM4-SR)
# Risques Industriels: (Didier Donsez, Didier Mazet-Brachet, RICM4 + PRI4 ?)
# [[Home Security Sweet Home 2012]] + [[iVLC|Ventilation efficace énergétiquement]]: (Didier Donsez, RICM4 SR + CM)
# [[Camera d'observation à basse altitude]]: (Didier Donsez, David Eon, Didier Hantz, RICM4, 3I4)
# [[Education à la respiration]]: (Projet AMO TIS4 2011-2012, Julie Fontecave, Pierre-Yves Gumery, TIS4, 3I4, RICM4 CM)
# [[Bras Robotique Handicap | Bras robotique à commande gestuelle pour le handicap]]:(Olivier Richard, RICM4 SR + CM)
# [[Robot de télé-présence]]: (RICM4 SR et CM, 3I4, Didier Donsez)
# [[Visualisation de données volcanologiques]]: (RICM4 CM et Geotech4)
# [[ArduiLab]] avec STM32 (RICM4 SR + CM, Olivier Richard)
# [[elua arduino stm32F4 Discovery | eLua et approche Arduino sur STM32F4-DISCOVERY]]: (RICM4 SR, Olivier Richard)
# IHM mobile pour le visualisation et le contrôle d'onduleurs: (RICM4 CM + SR, Didier Donsez)
# Shield Arduino pour pad gestuel 3D et bibliothèque Processing pour l'IHM (Didier Donsez, 1 RICM4 + 1 3I4)

Priorité 2
# [[3DWebCam]] (Didier Donsez, 1 à 2 RICM4)
# [[GroundCTRL]] (Didier Donsez, 2 RICM4)
# Projet AMO suite (Didier Donsez, RICM4 + 3I4 + TIS4)

==RICM5==
* [[Projet "Biométrie"]] (Laurent Besacier)
## [[PAGE WIKI ETUDIANTS 2011-12 SERRURE VOCALE]]
## [[PAGE WIKI ETUDIANTS 2011-12 SIGNATURES]]
* [[EA2011| Etudes d'Approfondissement]] 2011 en RICM5
## [[Haptic Glove]] (Didier Donsez)
## [[FreeRTOS on STM32 Discovery]]
* [[SmartGrid Marketplace]]
* [[GreenIT Autonomic Manager]]

==ERASMUS RICM5==
# [[FollowMe, CatchMe]] (un drone+webcam pour le suivi de personne) (Michaël Périn)
# [[KiFit]] Kinect + Wiifit for functional reeducation (Didier Donsez, Nicolas Vuillerme)

==M2PGI PM2M==
Contact: Didier Donsez, Thomas Calmant
# [[Drone roulant de Prévention des Risques Industriels]] (Didier Donsez)
# [[Fiche de Présence Contactless JavaCard]] (Gérard Forestier, Didier Donsez)
# [[eCOM Warehouse Management System]] (Didier Donsez)
# [[Détection de trafic automobile et de d’attente aux feux]] (Didier Donsez, Thomas Calmant)

==L3 Info==
Contact: Vincent Danjean

==Réserve==
# [[Serrure à clé MIDI multifactorielle]] (Didier Donsez)
# [[Table interactive musicale]] (Didier Donsez)
# [[iMailbox]] (Didier Donsez)
# [[AmILight]] (eclairage d'ambience intelligent) (Didier Donsez)
# [[PDAmeetPDA]] (synchronisation d'agenda) (Michaël Périn)
# [[1 000 000 VMs]] (expérimentation d'application distribuée à très grande échelle) (Olivier Richard) (2-3 RICM4)
# [[Multiple Kinect]] (utilisation simultanée de plusieurs Kinect) (Olivier Richard) (RICM ou 3I)
# [[Kinect musicale]] (Didier Donsez) (RICM)
# [[Ktechlab Simavr Arduino | Ktechlab et integration de Simavr(Arduino)]] (Olivier Richard) (2-3 RICM4-SR)
# Ocaml on AVR (Arduino)
# Ocaml on Cortex-M3
# [[Arduino on STM32 Discovery]]
# [[Reverse Geocache Puzzle Box]]
# [[OSGi ME]] (Didier Donsez)
# [[Affichage Etudiant à Polytech]]
# Synthèse 3D + motion capture Kinect
# Logiciel d'[[apprentissage du calcul]] sur tablette Android (reconnaissance de chiffres manuscrits)
# Plancher de verre (saint gobain) à la [http://www.wat.tv/video/mickael-jackson-billie-jean-oewj_2ey2h_.html Mickael Jackson dans Billie Jean] ! woo
# [[Ktechlab Simavr Arduino | Ktechlab et integration de Simavr(Arduino)]] (Olivier Richard) (2-3 RICM4-SR)
# [[CNC]]
# [[Idées en Vrac]]
# STM32 Primer2 et communication (Olivier Richard) (2-3 RICM4-SR)
# Scheme Everywhere (Olivier Richard) (2-3 RICM4-SR)
# [[Projet Station Météo]]
# Ocaml on AVR (Arduino)
# Ocaml on Cortex-M3
# [[Table interactive musicale]] (Didier Donsez)
# [[AmILight]] (eclairage d'amnbience intelligent) (Didier Donsez)
# [[Cube pointeur]] d'activité ingénieur
# [http://www.instructables.com/id/Puppeteer-Motion-Capture-Costume/ Puppeteer Motion-Capture Costume]
# [[Musical Staircase]] @ Polytech (Didier Donsez, 1 RICM4 + 1 3I4)
# [[Total Recall]] (Didier Donsez)

File:Bamboo.jpg

2012-03-07T15:00:31Z

Renaud C: Tablette Bamboo d'acquisition de signatures pour le projet de Biométrie (Signatures) RICM5 2011-2012

Tablette Bamboo d'acquisition de signatures pour le projet de Biométrie (Signatures) RICM5 2011-2012

File:Diagramme-de-Gantt-previsionnel.png

2012-03-07T14:59:51Z

Renaud C: Diagramme de Gantt prévisionnel pour le projet de Biométrie (Signatures) RICM5 2011-2012

Diagramme de Gantt prévisionnel pour le projet de Biométrie (Signatures) RICM5 2011-2012

2011-02-07T15:56:36Z

Renaud C:

2011-02-07T15:55:22Z

Renaud C: uploaded a new version of "File:Logo AIR TableTop.png"

Tabletop

2011-02-07T15:52:42Z

Renaud C:

[[File:Logo_AIR_TableTop.png|center|upright=0.5]]

* UE/Module: Projet innovant de RICM4 option CM
* Enseignant: Didier Donsez
* Elèves RICM4: Christophe Havard (chef de projet), Renaud Collin, Sebastien Skorupski

==Introduction==

Les technologies utilisées sont Flash (AS3) pour le codage de l'application, NFC pour l'identification et le paiement des utilisateurs.

Présentation commerciale du projet : [http://air.imag.fr/mediawiki/images/6/60/AIR_NFC_TableTop.pdf AIR_NFC_TableTop]

Les actualités du projet en anglais sur [http://youforkmywife.wordpress.com/ notre blog]

==Objectifs==
Les objectifs du projet sont
# de réaliser la partie matériel d'un tabletop à faible coût
# d'évaluer les canevas de développement d'IHM multitpoint (Flash/Android, C#/.NET/Windows7)
# de réaliser une application pour une table de restaurant (affichage des plats, commande, addition, enquête de satisfaction ...)
# d'utiliser la technologie NFC (Near Field Communication) pour permettre aux utilisateurs de s'identifier et payer via leur téléphone mobile

Ces informations peuvent être injectées dans un monde virtuelle d'avatars. Inversement, les capteurs et les usagers peuvent être simulés et représentés dans le monde réel augmenté. Pour cela, vous utiliserez [http://diasuite.inria.fr DiaSuite].

==Equipement==
* Table en verre IKEA (60")
* Miroir
* Mac Mini
* Videoprojecteur short-throw
* Illuminateur IR
* Webcam PS3 modifiée (IR filter removed & visible light bandpass filter added)
* Lentille grand angle (m12/0.5mm mount, 1.8mm, angle of view = 170°)
* RFID Reader ([[ACS ACR 122]] RFID reader)

[[File:TableTop_schema.jpg|center|upright=0.5]]

==Construction==

<gallery>
Image:TableTop 02.jpg|AIR NFC TableTop 1
Image:TableTop 05.jpg|AIR NFC TableTop 2
Image:TableTop 03.jpg|AIR NFC TableTop 3
</gallery>

==Logiciels==
* CCV (Community Core Vision) [http://ccv.nuigroup.com CCV]

<gallery>
Image:Test1.png|Community Core Vision
</gallery>

==Premières Démos==
* [http://www.dailymotion.com/video/xgpobl_test-application-fire-air-nfc-tabletop_tech Test Application "Fire"]
* [http://www.dailymotion.com/video/xgpobm_test-application-water-air-nfc-tabletop_tech Test Application "Water"]
* [http://www.dailymotion.com/video/xgpobr_test-application-paint-air-nfc-tabletop_tech Test Application "Paint"]

Tabletop

2011-02-07T15:52:31Z

Renaud C:

File:Logo AIR TableTop.png

2011-02-07T15:51:17Z

Renaud C:

Tabletop

2011-02-07T15:50:32Z

Renaud C: /* Logiciels */

* UE/Module: Projet innovant de RICM4 option CM
* Enseignant: Didier Donsez
* Elèves RICM4: Christophe Havard (chef de projet), Renaud Collin, Sebastien Skorupski

==Introduction==

Les technologies utilisées sont Flash (AS3) pour le codage de l'application, NFC pour l'identification et le paiement des utilisateurs.

Présentation commerciale du projet : [http://air.imag.fr/mediawiki/images/6/60/AIR_NFC_TableTop.pdf AIR_NFC_TableTop]

Les actualités du projet en anglais sur [http://youforkmywife.wordpress.com/ notre blog]

==Objectifs==
Les objectifs du projet sont
# de réaliser la partie matériel d'un tabletop à faible coût
# d'évaluer les canevas de développement d'IHM multitpoint (Flash/Android, C#/.NET/Windows7)
# de réaliser une application pour une table de restaurant (affichage des plats, commande, addition, enquête de satisfaction ...)
# d'utiliser la technologie NFC (Near Field Communication) pour permettre aux utilisateurs de s'identifier et payer via leur téléphone mobile

Ces informations peuvent être injectées dans un monde virtuelle d'avatars. Inversement, les capteurs et les usagers peuvent être simulés et représentés dans le monde réel augmenté. Pour cela, vous utiliserez [http://diasuite.inria.fr DiaSuite].

==Equipement==
* Table en verre IKEA (60")
* Miroir
* Mac Mini
* Videoprojecteur short-throw
* Illuminateur IR
* Webcam PS3 modifiée (IR filter removed & visible light bandpass filter added)
* Lentille grand angle (m12/0.5mm mount, 1.8mm, angle of view = 170°)
* RFID Reader ([[ACS ACR 122]] RFID reader)

[[File:TableTop_schema.jpg|center|upright=0.5]]

==Construction==

<gallery>
Image:TableTop 02.jpg|AIR NFC TableTop 1
Image:TableTop 05.jpg|AIR NFC TableTop 2
Image:TableTop 03.jpg|AIR NFC TableTop 3
</gallery>

==Logiciels==
* CCV (Community Core Vision) [http://ccv.nuigroup.com CCV]

<gallery>
Image:Test1.png|Community Core Vision
</gallery>

==Premières Démos==
* [http://www.dailymotion.com/video/xgpobl_test-application-fire-air-nfc-tabletop_tech Test Application "Fire"]
* [http://www.dailymotion.com/video/xgpobm_test-application-water-air-nfc-tabletop_tech Test Application "Water"]
* [http://www.dailymotion.com/video/xgpobr_test-application-paint-air-nfc-tabletop_tech Test Application "Paint"]