Institut de la Francophonie pour l’Informatique Institut National des Télécommunications MEMOIRE DE FIN D’ETUDES MASTER D’INFORMATIQUE VERIFICATION DE SIGNATURE EN-LIGNE Responsable : Sonia SALICETTI Bao LY VAN Stagiaire : Trung Tung DOAN 10 janvier 2006 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je voudrais tout d’abord remercier Madame Bernadette Dorizzi, professeur, chef du département Electronique et Physique de m’avoir accueilli dans son équipe de recherche de l’Institut National des Télécommunications (INT). Je tiens à remercier Madame Sonia Salicetti et Monsieur Ly Van Bao pour avoir proposé ce sujet de stage et m’avoir encadré pendant neuf mois. Je voudrais remercier particulièrement Monsieur Ly Van Bao pour tous ses conseils et encouragements, non seulement pour la recherche mais aussi pour la vie quotidienne en France. Mes plus sincères remerciements vont également à tous les professeurs et les personnels de l'Institut de la Francophonie pour l'Informatique (IFI) pour m'avoir donné des cours de très bonne qualité et pour leur soutien tout au long de mes études à l'IFI.
Un grand merci aux toutes les personnes de l’équipe GET-INT à l’INT, AMSL-BIO à l’université de Magdeburg et UNIK à l’université de Kent pour leur coopération dans le projet Systèmes de Référence et pendant le premier Biosecure Residental Workshop. Merci enfin à mes parents, ma sœur, ma fiancée et mes amis pour leur soutien et leur encouragement à tout instant. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé La vérification de signature en ligne est une technique biométrique comportementale. Nous présentons en bref deux algorithmes célèbres pour signature en ligne : les Modèles de Markov Cachés et la Déformation Temporelle Dynamique.
Le premier algorithme a été implémenté dans un système de l’Institut National des Télécommunications. Ce système est joint aux Systèmes de Références, un projet de collaboration de trois labos. Grâce aux Systèmes de Références, on a fait quelques expériences de fusion de systèmes. Nous proposons enfin une nouvelle approche pour la vérification de signature en ligne : l’approche d’algorithme génétique.
Mots-clés : vérification de signature en ligne, biométrie, modèles de markov cachés, déformation temporelle dynamique, extraction des paramètres, normalisation, fusion, algorithme génétique. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract Online Signature Verification is one biometric behavioral technique. We present in brief two well-known algorithms for online signature: Hidden Markov Models and Dynamic Time Warping. The first one has been implemented in a system of INT (Institut National des Télécommunications).
We have also joined this system in the project Reference Systems which is a collaboration of three labs. With Reference Systems, we have done some experiences in fusing systems. In the end, we propose a new approach for Online Signature: genetic algorithm’s approach. Keywords: online signature verification, biometry, hidden markov models, dynamic time warping, feature extraction, normalization, fusion, genetic algorithm.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHAPITRE 1 INTRODUCTION .2 Objectif du stage.3 Environnement de travail .4 Plan de document .8 CHAPITRE 2 VERIFICATION DE SIGNATURE EN LIGNE .2 Modèle de Markov Cachés .3 Déformation temporelle dynamique .20 CHAPITRE 3 SYSTEMES DE REFERENCE .1 Analyse des données .3 Extraction des paramètres.4 Sélection des paramètres .5 Stockage de référence.6 Modèle de Client .25 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.9 Contrôleur de Framework .3 Module de GET-INT .2 Performance des algorithmes .1 Base de données .3 Fusion des systèmes .1 Base de données .3 Protocole de fusion.4 Techniques de normalisation.37 CHAPITRE 5 APPROCHE D’ALGORITHME GENETIQUE.1 Algorithme génétique en bref .2 AG pour la vérification de signature .54 CHAPITRE 6 CONCLUSIONS ET PERSPECTIVES .55 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 1 Introduction 1.1 Problématique Aujourd’hui, la Biométrie est de plus en plus courante. C’est un domaine qui se compose de plusieurs techniques : l'empreinte digitale, la signature, l'iris, la voix, le visage, la démarche, etc. Ce stage est centré sur la vérification de signature en ligne. Cette technique est assez efficace quoiqu’elle soit simple par rapport à d’autres techniques biométriques.
Dans un système de vérification de signature en ligne, il y a trois problèmes principaux : l’acquisition des signatures, la construction du système et la phase vérification des signatures. Qu’est-ce que une signature en ligne ? Comment peut-on l’acquérir ? Quelles sont les méthodes pour construire un système et l’utiliser pour vérifier l’identité d’une personne par sa signature ? On va étudier les réponses à ces questions dans ce rapport. Ce stage s’intéresse aussi aux expériences de fusion de différents systèmes de vérification de signature. Qu’est qui se passe quand on fusionne plusieurs systèmes ? Est-ce que le système est de meilleure qualité ou pas ? Les réponses à ces questions peuvent être trouvées dans le Chapitre 4.2 Objectif du stage Ce travail de stage s’insère dans la suite des travaux effectués à l’INT sur la vérification de signature en ligne, avec des Modèles de Markov Cachés.
Le premier objectif du stage est de regrouper ce système avec d’autres systèmes de deux laboratoires : UNIK (Université de Kent) et AMSL (Université de Magdeburg) pour construire un logiciel open-source mettant en oeuvre les « Systèmes de Référence » pour la vérification de signature. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Le deuxième objectif du stage est d’utiliser les Systèmes de Référence pour faire des expériences de fusion des systèmes.3 Environnement de travail Le département EPH (Electronique et Physique) regroupe plusieurs enseignants, chercheurs de l’Institut National des Télécommunications travaillant dans plusieurs domaines dont la Biométrie. L’équipe INTERMEDIA recherche sur la vérification de signature en ligne, l’identification par l’iris, la vérification multimodale de l’identité, etc.4 Plan de document La suite du rapport est organisée comme suit. Après une introduction de la vérification de signature en ligne, deux algorithmes de l’état de l’art sont présentés : les Modèles de Markov Cachés dans la partie 2.2 et la Déformation Temporelle Dynamique dans la partie 2.3Error! Reference source not found.
Ensuite, nous présentons les trois Systèmes de Référence dans le Chapitre 3. Les expériences que nous avons faites avec ces systèmes sont abordées dans le Chapitre 4. Dans le Chapitre 5, nous proposons une nouvelle approche pour la vérification de signature en ligne, c’est l’approche par algorithme génétique. Enfin, le Chapitre 6 donne la conclusion et les perspectives du travail.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 2 Vérification de signature en ligne 2.1 Introduction La biométrie est un ensemble des technologies (appelées les technologies biométriques) qui exploitent des caractéristiques humaines physiques ou comportementales telles que l'empreinte digitale, la signature, l'iris, la voix, le visage, la démarche, parmi d’autre pour différencier des personnes. À la différence des mots de passe ou des PINs (numéros d'identification personnelle) qui sont facilement oubliés ou exposés à l'utilisation frauduleuse, ou des clefs ou des cartes magnétiques qui doivent être portées par l'individu et sont faciles à être volées, copiées ou perdues, ces caractéristiques biométriques sont uniques à l'individu et il y a peu de possibilité que d'autres individus peuvent remplacer ces caractéristiques. Donc les technologies biométriques sont considérées les plus puissantes en termes de sécurité. En plus, les mesures biométriques sont confortables parce qu’elles n'ont pas besoin d'être portées séparément.
De telles caractéristiques peuvent être bien employées pour obtenir l'identification/authentification pour accéder à des systèmes tels que les ATMs (guichet automatique). La biométrie est également un outil puissant d'identification/vérification aux scènes de crime dans le secteur juridique. La vérification de signature en ligne est une technologie biométrique comportementale. La Figure 1 différencie des technologies physiques et comportementales : Non Biométrie Physique Comportemental Clés Signature en ligne Iris Signature en Mot de passe Iris Visage Marche PINs Visage Main Dactylographie … … … … Figure 1 – Classification de la vérification de signature en ligne LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com En fait, il y a deux types de signature : la signature en ligne et la signature hors ligne.
Comment peut-on les différencier ? La signature en ligne est acquise par des tablettes à digitaliser ou des écrans tactiles ; par contre, la signature hors ligne est l’image de la signature normale qui est acquise par un stylo et un feuil. La signature en ligne est plus pratique que la signature hors ligne parce qu’il fournit plus d’informations, par exemple la vitesse, la pression, l’altitude, l’azimut, etc. La vérification de signature en ligne devient de plus en plus courante grâce aux plusieurs avantages : • Elle est simple pour l’utilisateur. Signer sur un PDA n’est pas très différent que sur une feuille.
• Elle n’est pas coûteuse par rapport aux autres méthodes comme l’iris, le visage, etc. • La performance de vérification est acceptable. Pourtant, elle a aussi des désavantages par rapport à d’autres techniques biométriques: • Les autres peuvent imiter la signature en observant le processus de signature. En fait, des expériences montrent que le taux d’erreurs du système testé avec des imitations de haute qualité est toujours plus élevé que celui obtenu avec des imitations aléatoires.
• L’état du signataire influence fortement sa signature. Par exemple, quand il est heureux, il signe différemment que quand il est triste, ou quand il est malade, il signe différemment que quand il va bien. • Au cours du temps, la signature change et si le système n’est pas mis à jour, il ne pourra plus reconnaître la signature authentique. Nous présentons ensuite deux algorithmes de l’état de l’art pour la vérification de signature en ligne : les Modèles de Markov Cachés (MMC) et la Déformation Temporelle Dynamique (DTD).
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Modèle de Markov Cachés 2.1 Présentation Un MMC est représenté par : 1) N, le nombre d’états du modèle. Les états d’un MMC sont toujours cachés. Ils peuvent être interconnectés (chaque état peut être atteint de n'importe quelle autre état) ou non. Nous dénotons les états individuelles S = {S1, S2, …, SN} et l’état au temps t est qt.
2) M, le nombre des observations. Nous dénotons les observations individuelles V = {v1, v2, …, vM}. 3) La matrice des probabilités de transition des états A = {aij} où aij = P[qt+1 = Sj | qt = Si], 1 ≤ i, j ≤ N. Si les états sont interconnectés, tous les aij > 0, si non, il y a quelques aij = 0 (c'est-à-dire l’état Sj ne peut pas être atteint de l’état Si).
4) La matrice des probabilités des observations B = {bj(k)} où bj(k) = P[vk au t | qt = Sj], 1 ≤ j ≤ N, 1 ≤ k ≤ M. 5) Le vecteur des probabilités initiales π = {πi} où πi = P[q1=Si], 1 ≤ i ≤ N. En bref, un MMC est dénoté par λ = (A, B, π).2 Problèmes principaux Il y a trois problèmes principaux dans l’utilisation d’un MMCs. Ces problèmes sont abordés suivante : z Evaluation: Etant donné le MMC λ = (A, B, π) et une séquence d’observations O={o1, o2, ., oT}, comment calculer la probabilité pour que O soit générée par λ (le vraisemblance P(O | λ).
z Décodage: Etant donné le MMC λ = (A, B, π) et les observations séquentielles O={o1, o2, ., oT}, comment calculer la séquence d’états Q = q1q2…qT la plus probable. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com z Apprentissage: Etant donné les observations séquentielles O, comment déterminer les paramètres du MMC λ = (A, B, π) pour que P(O | λ) soit maximisé sur les observation O de le base d’apprentissage. Solution pour le problème d’évaluation. Etant donné une séquence des états Q = q1q2…qT.
La probabilité de la séquence des observations O pour la séquence des états Q est : T P (O | Q, λ ) = ∏ P (Ot | qt , λ ) t =1 Supposez que les observations sont indépendantes, on a : P (O | Q , λ ) = bq1 (O1 ).aqT −1qT La probabilité pour que O et Q aient lieu simultanément est le produit de ces deux termes : P(O, Q | λ ) = P(O | Q, λ ).