Identification Biométrique des Individus par leurs Empreintes Palmaires « Palmprints » : Classification par la Méthode des Séparateurs à Vaste Marge (SVM) BoukhariWassila boukhari_wassila@yahoo.fr LAboratoire de Modélisation et d'Optimisation des Systèmes Industriels LAMOSI Université des Sciences et de la Technologie d'Oran USTO-Algerie BenyettouMohamed med_benyettou@yahoo.fr LAboratoire de Modélisation et d'Optimisation des Systèmes Industriels LAMOSI Université des Sciences et de la Technologie d'Oran USTO-Algerie Identification Biométrique des Individus par leurs Empreintes Palmaires « Palmprints » : Classification par la Méthode des Séparateurs à Vaste Marge (SVM) 5F511AC69D553178EA2804FE9AB9B85A GROBID - A machine learning software for extracting information from scholarly documents biométrie multi-classes identification Palmprint séparateurs à vaste marge (SVM)

L'identification des individus par leurs empreintes palmaires (Palmprints), considérée comme nouveau membre de la famille des modalités biométriques, est devenue un domaine de recherche très actif durant ces dernières années. Les travaux réalisés, jusqu'à présent, se sont basés sur les techniques de représentation des images de palmprints pour une meilleure classification. Dans notre travail, nous nous sommes basés sur la classification en utilisant une méthode d'apprentissage automatique, notamment la méthode des séparateurs à vaste marge (SVM) appliquée à plusieurs classes (multi-classes). Les taux de reconnaissance obtenus sont satisfaisants en utilisant la méthode par deux différentes approches : l'approche un-contre-un et l'approche un-contre-tous (le plus grand taux réalisé est 99.4%). On note que la différence majeure reste le temps de reconnaissance d'un individu qui est minimal pour l'approche un-contre-un. Cependant, étant donné la complexité des calculs dans la méthode SVM, on ne peut dire que cette dernière est appropriée pour des applications en temps réel.
Introduction

Le besoin d'accès sécurisés automatisés à des environnements physiques ou virtuels, notamment pour des services personnalisés, est en pleine croissance. Ces besoins requièrent des moyens fiables pour vérifier l'identité d'une personne qui se présente au système d'accès. Or les moyens classiques reposants sur des mots de passe ou des cartes magnétiques associées à un code personnel présentent un certain nombre d'inconvénients. Un mot de passe peut être oublié ou volé par un autre individu, ou même cédé à quelqu'un d'autre ; les cartes d'accès peuvent également être perdues ou volées. C'est ainsi que l'exploitation de caractéristiques ou mesures liées à la physiologie même de l'individu (sa voix, son visage, sa signature, ses empreintes digitales, la forme de sa main,...) est apparue naturellement comme la solution la plus fiable, chacune de ces différentes mesures est appelée "modalité biométrique".

Les systèmes biométriques constituent un instrument efficace de lutte contre la fraude, pour assurer la sécurité des échanges financiers et commerciaux, l'accès légitime aux services gouvernementaux, et contrer le vol d'identité sous toutes ses formes. Parmi les nouvelles modalités biométriques utilisées en ce moment nous nous intéressons aux empreintes palmaires des individus (palmprints). Les travaux réalisés, jusqu'à présent, sur la reconnaissance des individus par leurs palmprints se sont basés sur le prétraitement et l'extraction des caractéristiques principales des images de palmprints afin d'avoir une meilleure classification. Notre objectif à travers ce travail est de se baser sur la classification en utilisant l'apprentissage automatique, notamment une méthode robuste de classification à base de noyaux: les séparateurs à vaste marge (SVM).

Caractéristiques du système de reconnaissance par les palmprints

Introduite par David Zhang et Shu (chercheurs et professeurs à l'université polytechnique de Hong Kong) depuis 1996 pour remédier aux problèmes liés à la non visibilité d'une empreinte digitale ou bien le coût élevé des appareils de capture des images de l'iris et de la rétine ou encore les faibles taux de reconnaissance des autres modalités biométriques ; l'empreintes palmaire ou « palmprint » est cette surface très large et interne de la main, elle contient plusieurs traits caractéristiques tels que les lignes principales, les plis et les textures. Grace à cette large surface et l'abondance des traits caractéristiques, on prévoit que les palmprints soient très robustes aux bruits et uniques à chaque individu. Comparé aux autres caractéristiques physiques, l'identification par les empreintes palmaires (palmprint) a plusieurs avantages :

1. Traitement d'image à basse résolution. 2. Peu de risque d'intrusion.

3. Les traits des lignes sont stables. 4. Taux élevé d'acceptation par les utilisateurs.

Identification en ligne ou hors ligne ?

L'identification par les palmprints peut être divisée en deux catégories, en ligne et hors ligne. Les recherches sur l'identification hors ligne par les palmprints ont été le centre d'intérêt principal durant les dernières années où tous les échantillons de palmprints étaient ancrés sur papier, ensuite transmis à l'ordinateur par un scanner numérique (figure. 1). Due à la haute résolution relative aux images hors ligne des palmprints (plus de 500 dpi), quelques techniques utilisées pour les empreintes digitales peuvent être utiles pour l'identification hors ligne des palmprints où les lignes et les points de données ou points singuliers peuvent être extraits. Pour l'identification en ligne des palmprints, les échantillons d'images sont directement obtenus par un appareil de capture de palmprint. Il est évident que l'identification en ligne par les palmprints est beaucoup plus appropriée pour les applications en temps réel, c'est pour cela que notre intérêt c'est porté sur ce type d'identification.

Dispositif de capture des images de palmprints en ligne

Pour accomplir une identification en ligne par les palmprints en temps réel, il faut un dispositif particulier qui doit être plus rapide dans l'acquisition des palmprints [Zhang, 2003]. Un exemple d'un tel dispositif est présenté dans la figure. 2.

Etape de classification

Une fois l'ensemble des caractéristiques d'une image de palmprint défini, on peut l'utiliser pour représenter cette image. L'identification se fait, par la suite, par une méthode de classification qui va comparer cet ensemble de caractéristiques avec des enregistrements de références existants dans la base de données spécifique et ainsi trouver la classe à laquelle appartient cette image. Plusieurs méthodes de classification ont été utilisées pour les palmprints, on retrouve surtout les méthodes géométriques classiques qui utilisent le calcul des distances entre les vecteurs de caractéristiques telles que la distance euclidienne ou de hamming, des exemples d'applications de ces méthodes sont dans [Zhang, 2003], [Kong, 2003]

Principe des SVMs

Notions de base: Hyperplan, Marge, Vecteurs de support

Pour deux classes d'exemples données, le but de SVM est de trouver un classifieur qui va séparer les données et maximiser la distance entre ces deux classes. Avec SVM, ce classifieur linéaire est appelé hyperplan. Les points les plus proches, qui seuls sont utilisés pour la détermination de l'hyperplan, sont appelés vecteurs de support.

Fig. 5. Hyperplan optimal, marge maximale et vecteurs de support

Il est évident qu'il existe une multitude d'hyperplans valides mais la propriété remarquable des SVM est que cet hyperplan doit être optimal. Formellement, cela revient à chercher un hyperplan dont la distance minimale aux exemples d'apprentissage est maximale. On appelle cette distance « marge » entre l'hyperplan et les exemples. L'hyperplan séparateur optimal est celui qui maximise la marge (Fig. 5).

Linéarité et non linéarité

Dans la plupart des problèmes réels il n'y a pas de séparation linéaire possible entre les données, la notion de marge maximale ne peut pas être utilisée car elle fonctionne seulement si les classes de données d'apprentissage sont linéairement séparables. Dans le cas non linéaire, le principe consiste à projeter les données de l'espace d'entrée non linéairement séparables dans un espace de plus grande dimension appelé espace de caractéristiques de façon à ce que les données deviennent linéairement séparables. Ceci est illustré par le schéma suivant:

Fondements mathématiques

La méthode générale de construction de l'Hyperplan Optimal (HO) qui sépare des données appartenant à deux classes différentes linéairement séparables est comme suit : Soit H : (w . x) + b l'hyperplan qui satisfait la condition suivante :

( (2)

En appliquant le principe de Lagrange, on obtient le problème de programmation quadratique de dimension m (nombre d'exemples) suivant :

⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ∀ ⋅ − ∑ ∑ ∑ = = m i i i i m i j i j i j i j i i y i x x y y 1 1 , 0 , ) ( 2 1 max α α α α α (3)

Les α i sont les coefficients de Lagrange.

Définition

On définit les Vecteurs Supports VS tout vecteur x i tel que

Le système d'identification des individus par leurs palmprints

Le système que nous avons développé contient quatre étapes essentielles qui sont : le prétraitement des images de palmprint, extraction des paramètres ou codes pertinents, l'apprentissage des différentes classes de la base de données et la classification.

La base de données des images de palmprints

Les images de palmprints que nous avons utilisé dans nos expérimentations sont issues de la base de données PolyUDatabase. Les images de cette base ont été collectées parmi 200 individus en utilisant un dispositif de capture d'images de palmprints conçu par des chercheurs de l'université polytechnique de Hong Kong Les images ont été prises dans deux périodes différentes séparées par un intervalle de temps d'environ deux moi. Durant chaque période, chaque individu devait prendre au moins six images de ses palmprints. De plus, dans la deuxième période, la source de lumière et l'objectif de la caméra CCD ont été ajustés de telle sorte que les images de la première et deuxième période donnent l'impression d'avoir été prises par deux dispositifs de palmprints différents. Les images ont, aussi, été prises dans des conditions de lumière différentes afin de tester la robustesse du système de reconnaissance. La taille des images est de 384×284 avec une résolution de 75 dpi.

Prétraitement des images

La phase de prétraitement est essentielle dans les systèmes de reconnaissance des formes. Pour notre système, la phase de prétraitement se compose de trois étapes essentielles :

• Définir la région d'intérêt (Region Of Interest: ROI) ou bien un système de coordonnées pour les images palmprints. • Appliquer un masque aux ROI pour éliminer les contours non significatifs.

• Améliorer le contraste et les niveaux de lumière de ces régions.

4.2.1

Le système de coordonnées. Il est très important de définir un système de coordonnées qui sera utilisé pour aligner les différentes images des palmprints dans la comparaison. Les cinq étapes principales de ce traitement sont : Etape1 : Appliquer un filtre passe-bas, par exemple un filtre gaussien, à l'image originale. Un seuil est utilisé pour transformer cette image en une image binaire. Etape2 : Utiliser un algorithme de détection de contour pour obtenir les contours des espaces entre les doigts (F i x j , F i y j ) (i=1, 2). Etape3 : Calculer la tangente des deux espaces. Soient (x 1 , y 1 ), (x 2 , y 2 ) deux points sur (F 1 x j ,F 1 y j ) et (F 2 x j , F 2 y j ) respectivement. Si la ligne (y=m.x+c) passant sur ces deux points satisfait l'inégalité : F i y j ≤ m.F i x j +c pour tout i et j, alors la droite y=m.x+c est considérée comme la tangente des deux espaces ou intervalles. Etape4 : Dessiner la droite entre (x 1 ,y 1 ) et (x 2 ,y 2 ) pour avoir l'axe des Y du système de coordonnées du palmprint et utiliser la droite qui passe par le milieu de ces deux points, qui est perpendiculaire à l'axe des Y, pour déterminer l'origine du système de coordonnées. Etape5 : Extraire une partie de l'image d'une taille fixe en se basant sur le système de coordonnées.

Résultats et discussion

Le système a été implémenté en utilisant Matlab 6.5 sur un micro processeur Intel Pentium IV 1.6GHz, possédant 512 MO de RAM. La plateforme utilisée est celle de Microsoft Windows XP. Les résultats obtenus par les approches un-contre-tous et uncontre-un de SVM multi-classes sont donnés dans le tableau suivant : Table 1. Résultats obtenus par les approches un-contre-tous et un-contre-un de SVM multi-classes.

Approches SVM multiclasses
Temps d'apprentissage
Temps de test
Taux de reconnaissance

Un-contre-tous 2411.3 2

96.1%

Un-contre-un 3420.3 22

99.4%

Temps d'apprentissage et de test en secondes.

D'après ce tableau on peut dire que la méthode SVM donne de bons résultats que ce soit dans l'approche un-contre-tous ou bien l'approche un-contre-un. Les deux approches ont obtenu des résultats performants avec une légère différence entre les deux (99.4% pour le un-contre-un, 96.1% pour le un-contre-tous). Cependant, la différence du temps d'apprentissage et de test entre les deux méthodes est très grande. En effet, l'approche un-contre-un consomme un temps considérable par rapport à l'approche un-contre-tous. Le temps de test dans le un-contre-un est presque dix fois plus grand que dans le un-contre-tous, chose qui pourrait nuire à la fiabilité du système en particulier si il s'agit d'une application en temps réel.

Fig. 1 .Fig. 1. Image hors ligne et en ligne de palmprint.
Fig. 2 .Fig. 2. Dispositif de capture de palmprints en ligne.
Fig. 3 .Fig. 3. Images de palmprints avec des traits pas clairs.
Fig. 4 .Fig. 4. Images de différentes palmprints avec des traits similaires. La représentation en textures pour la classification des images de palmprints à basse résolution a fourni une approche efficace dans [You, 2002]. Donc l'une des solutions pour résoudre ce problème est d'extraire les caractéristiques de texture des images de palmprints à basse résolution. Dans ce contexte plusieurs méthodes ont été utilisées, en particulier le codage de phase par le filtre de Gabor à deux dimensions dans [Zhang, 2003], [A. Kong, 2005], [Zhenan, 2005] et [W. Kong, 2003]. On retrouve aussi l'utilisation des ondelettes (Wavelet Decomposition) [Pang (2), 2004]. D'autres chercheurs se sont basés sur les méthodes de projection : PCA (Principle Component Analysis) et ICA (Independent Component Analysis) [Connie, 2003] et [Shang, 2006], ou encore le discriminant de Fisher dans [Wu, 2003] et [Jing, 2006] et bien d'autres méthodes d'extraction des caractéristiques principales de palmprints.
Fig. 6 .Fig. 6. Hyperplan séparateur dans le cas non linéairement séparable.
Wsous la contrainte (1). Ceci est un problème de minimisation d'une fonction objective quadratique avec contraintes linéaires.
y i [(w o ⋅ x i ) + b o ] = 1. Ce qui est équivalent à : La fonction de classement class(x) est définit par : Si class(x) est inférieure à 0, x est de la classe -1 sinon il est de la classe 1. Dans le cas linéaire, on pouvait transformer les données dans un espace où la classification serait plus aisée. Dans ce cas, l'espace de caractéristiques utilisé le plus souvent est R (ensemble des nombres réels). Il se trouve que pour des cas non linéaires, cet espace ne suffit pas pour classer les entrées. On passe donc dans un espace de plus grande dimension. Avec card(F) > d. On doit donc résoudre (4) Plutôt que de choisir la transformation non-linéaire Φ : X→F, on choisit une fonction k:XxX→ R (nombres réels) appelée fonction noyau. origine, les SVM ont été conçus essentiellement pour les problèmes à 2 classes, cependant plusieurs approches permettant d'étendre cet algorithme aux cas à N classes ont été proposées. La généralisation dans le cas multi-classes peut se faire de trois façons différentes. Les deux premières méthodes sont basées sur une multiplication des classifieurs bi-classes tandis que la dernière propose une résolution globale. − Un-contre-tous : l'approche la plus naturelle est d'utiliser cette méthode de discrimination binaire et d'apprendre N fonctions de décision {f m } m=1…N permettant de faire la discrimination entre chaque classe de toutes les autres (chaque classe est opposée à toutes les autres).il faut donc poser N problèmes binaires. L'affectation d'un nouveau point x à une classe C i se fait par la relation : i= argmax m=1..N F m (x) (5) − Un-contre-un : la deuxième méthode est une méthode dite de un contre un. Au lieu d'apprendre N fonctions de décisions, ici chaque classe est discriminée d'une autre. Ainsi, N(N-1)/2 fonctions de décisions sont apprises et chacune d'entre elles effectue un vote pour l'affectation d'un nouveau point x. La classe de ce point x devient ensuite la classe majoritaire après le vote. − Méthode globale : la dernière méthode est une approche étendant la notion de marge aux cas multi-classes. Le problème fait intervenir N fonctions de décision et il est très gourmand en temps de calcul et en espace mémoire ce qui fait qu'il reste peu utilisé dans les cas réels.
Fig. 7 .Fig. 7. Les étapes principales d'extraction de la région d'intérêt de l'image. (a) image originale, (b) image binaire, (c) détection de contours, (d) construction du système de coordonnées, (e) extraction de l'image centrale (ROI), (f) la région extraite4.2.2 Elimination des informations redondantes (application d'un masque).Dans certain cas, l'utilisateur ne place pas sa main correctement sur le dispositif de capture d'images de palmprint ce qui inclut quelques pixels qui n'appartiennent pas à la surface de palmprint dans les images prétraitées. Pour enlever ce genre de régions et donc ces informations redondantes dans l'image, nous générons un masque pour identifier la localisation des pixels qui ne font pas partie du palmprint (Fig.8).
Fig. 8 .Fig. 8. Génération du masque de l'image.
Fig. 9 .Fig. 9. Résultat de l'ajustement du contraste.
Fig. 10 .Fig. 10. Vecteur de caractéristiques d'une image prétraitée.
Convertisseur A/D L'entrée Ordinateur Source en anneau Objectif Caméra CCD Vecteur de caractéristiques
de prétraitement des images de palmprints est très importante dans le processus de reconnaissance et que l'utilisation du filtre de Gabor pour extraire les vecteurs de caractéristiques à partir des images est une étape qui nous a permis de réduire le temps des calculs dans la classification WBoukhari Dans le cadre des méthodes d'apprentissage à base de kernel, nous avons présenté et discuté deux approches issues des SVM multi-classes, les stratégies un-contre Mémoire de Magister
USTOran
 Octobre 2007 Identification Biométrique des Individus par leurs Empreintes Palmaires (Palmprints) Palmprint identification using feature-level fusion AKong DZhang MKamel Journal of pattern recognition 39 Aout 2005 Palmprint recognition with PCA and ICA TConnie ATeoh MGoh DNgo proceeding of IVCNZ 26 28 Décembre 2003 An uncorrelated fisherface approach for face and palmprint recognition X-YJing CLu DZhang ICB 2006. 2006 Palmprint verification with moment Y-HPang ATeoh BJin DNgo CLing FHiew journal of WSCG 2004 Wavelet-based pseudo Zernike moments for palmprint authentification Y-HPang ATeoh BJin DNgo CLing LShiuan-Ni international symposium M2USIC 04 2004 Palmprint recognition using FastICA algorithm and radial basis probalistic neural network LShang DHuang J-XDu C-HZheng pattern recognition 69 2006 Palmprint Feature extraction using 2-D gabor filters VVapnik W-KKong DZhang W-XLi pattern recognition 36 1995. 2003 Springer Verlag The Nature of Statistical Learning Theory Fisherpalms based Palmprint recognition XWu DZhang KWang 2003 24 hierarchical palmprint identification via multiple feature extraction JYou WLi DZhang pattern recognition 35 4 2002 Online palmprint identification DZhang W-KKong JYou MWong IEEE transaction 25 9 Séptembre 2003 Ordinal palmprint representation for personal identification SZhenan TTieniu YWang SLi proceeding of IEEE eeding of IEEE 2005 1