93
Universit ´ e Catholique de Louvain Ecole Polytechnique de Louvain M ´ emoire de fin d’ ´ etudes Reconnaissance et suivi de visages et impl´ ementation en robotique temps-r´ eel ealis´ e par Mathieu Van Wambeke en vue de l’obtention du diplˆ ome de Master Ing´ enieur Civil en G´ enie Biom´ edical Promoteur: Prof. Benoˆ ıt Macq Assistant: Christian Van Brussel Ann´ ee acad´ emique 2009-2010

Reconnaissance et suivi de visages et implémentation en robotique

  • Upload
    vodieu

  • View
    217

  • Download
    1

Embed Size (px)

Citation preview

Universite Catholique de LouvainEcole Polytechnique de Louvain

Memoire de fin d’etudes

Reconnaissance et suivi de visageset implementation en robotique

temps-reel

Realise par

Mathieu Van Wambeke

en vue de l’obtention du diplome de

Master Ingenieur Civil en Genie Biomedical

Promoteur:

Prof. Benoıt Macq

Assistant:

Christian Van Brussel

Annee academique 2009-2010

Remerciements

Je remercie particulierement ma famille pour le soutien qu’elle m’a apporte et la

motivation qu’elle a su me donner lorsque j’en avais le plus besoin.

Je tiens a remercier mon promoteur, le professeur Benoıt Macq, sans qui je n’aurais

pas pu realiser ce memoire ni avoir acces a Nao, le petit robot humanoıde.

Je remercie sincerement mon assistant-chercheur, Christian Van Brussel, pour ses

precieux conseils lors de la redaction et sa disponibilite sans failles.

Je remercie egalement mes compagnons memorants du local a143.10, Arnab Bhat-

tacharya, Mireia Montanola et les autres, grace auxquels l’ambiance de travail fut ex-

cellente.

Je remercie aussi Sebastien Brousmiche et Abdellatif Zaidi pour leurs conseils avises.

I

Resume

Dans ce memoire, il est question d’implementer sur un robot humanoıde les mecanismes

de base d’une relation entre individus. L’objectif est de reconnaıtre les personnes et de

s’orienter vers une d’entre elles pour commencer une interaction.

Le robot humanoıde Nao de Aldebaran Robotics sert de support au logiciel et la

reconnaissance se fait exclusivement sur base de donnees biometriques visuelles capturees

dans un environnement reel, donc soumis a des variations d’illumination. Nao effectuera

une localisation et une poursuite des visages et sera capable de se souvenir des gens qu’il

croise apres ne les avoir vu qu’une seule fois. Ce probleme de reconnaissance a partir

d’un seul cliche est traite dans la litterature sous le nom de ’one sample problem’ ou

reconnaissance avec un seul echantillon d’apprentissage par personne.

L’application de reconnaissance de visages convertit les images en modeles binaires

locaux (’local binary patterns’), les divise en plusieurs sous-regions et determine l’identite

d’un visage en comparant leurs histogrammes de sous-regions. Le nombre de manieres

de diviser l’image en sous-regions pouvant se chevaucher est colossal et empeche de

selectionner la meilleure en les essayant toutes. Ce memoire propose une mehode pour

garantir le choix d’une des meilleures combinaisons de sous-regions.

De plus, il est propose une technique de generation de cartes des zones les plus utiles

a la discrimination qui permet de mettre en evidence l’importance des zones frontieres

des elements cles du visage tels que le nez, la bouche ou les yeux dans le cas de la

reconnaissance de visages par comparaison d’histogrammes de modeles binaires locaux.

II

Table des matieres

Remerciements I

Resume II

Table des matieres III

Introduction 1

Structure du memoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

I Etat de l’art 4

1 Detection de visages 5

1.1 Algorithme de Viola & Jones . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 L’image integrale . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Algorithme d’apprentissage base sur Adaboost . . . . . . . . . . . 8

1.1.3 Cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Parametrisation & Entraınement . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Travaux existants suite a l’Algorithme de Viola & Jones . . . . . . . . . 12

1.3.1 Nouvelles caracteristiques . . . . . . . . . . . . . . . . . . . . . . 12

1.3.2 Ameliorations du Training set . . . . . . . . . . . . . . . . . . . . 12

1.3.3 Dernieres avancees : Wu et al. . . . . . . . . . . . . . . . . . . . . 12

1.3.4 Dernieres avancees : Xiaohua et al. . . . . . . . . . . . . . . . . . 13

2 Reconnaissance de visages 15

2.1 Probleme a echantillons multiples . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Probleme avec un seul echantillon d’entraınement par personne . . . . . . 16

2.2.1 Methodes holistiques . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.2 Methodes locales . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.3 Methodes hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3 Les ’Local Binary Patterns’ appliques a la reconnaissance faciale . . . . . 19

III

2.3.1 Dernieres avancees : Travail de Tan et Triggs . . . . . . . . . . . 22

2.4 Le traitement de l’illumination . . . . . . . . . . . . . . . . . . . . . . . . 25

II Application 26

3 Conception de l’application 27

3.1 Mise en situation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.1 Definition de l’objectif et enumeration de ses consequences . . . . 27

3.1.2 Importance du temps reel et des performances . . . . . . . . . . . 28

3.1.3 Materiel disponible et limitations . . . . . . . . . . . . . . . . . . 29

3.1.4 Le challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 Gerer le probleme du temps reel . . . . . . . . . . . . . . . . . . . . . . . 30

3.2.1 Difference entre temps de reaction et le temps de rafraichissement 30

3.2.2 Points importants pour choisir la distribution ideale des taches . . 32

3.2.3 Choix des lieux d’execution : l’architecture prototype . . . . . . . 33

3.3 Architecture prototype et cycle de fonctionnement standard . . . . . . . 33

3.3.1 Detection des visages . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.2 La poursuite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.3.3 Reconnaissance des visages . . . . . . . . . . . . . . . . . . . . . . 36

3.4 Pistes pour ameliorer les performances . . . . . . . . . . . . . . . . . . . 41

3.4.1 Nouvelles informations spatiales . . . . . . . . . . . . . . . . . . . 41

3.4.2 Collaboration des systeme de reconnaissance et de poursuite . . . 42

3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Entraınement sous MatLab du stage de reconnaissance 44

4.1 Ensembles d’entraınement, de validation et bases de visages . . . . . . . 45

4.2 Taille de fenetre utilisee . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.3 Selection de la combinaison de sous-regions pour la reconnaissance faciale 47

4.3.1 Difficulte et objectif . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3.2 Strategie et resultats . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.4 Conclusion et suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5 Obtenir une carte des zones utiles a la discrimination 54

5.1 Contexte et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.2 Division en parties contigues . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.3 Introduction aux ensembles d’apprentissage et de validation artificielle-

ment generes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

IV

5.4 Exploitation de parties non-contigues . . . . . . . . . . . . . . . . . . . . 57

5.4.1 Methode (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4.2 Methode (b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.4.3 Methode (c) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4.4 Methode (d) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5 Strategie proposee et resultats . . . . . . . . . . . . . . . . . . . . . . . . 63

5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6 Implementation C++ et test des performances 67

6.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2 Test de la detection des visages . . . . . . . . . . . . . . . . . . . . . . . 68

6.2.1 Orientations detectees . . . . . . . . . . . . . . . . . . . . . . . . 68

6.2.2 Cadrage des visages . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6.3 Test de la reconnaissance des visages . . . . . . . . . . . . . . . . . . . . 70

Conclusion 72

Bibliographie 78

Appendices 84

A Implementation C++ : la librairie ImProc 85

A.1 Les librairies utilisees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

A.2 La librairie ImProc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

V

Introduction

La reconnaissance faciale est une aptitude qui relie l’apparence d’une personne a son

identite. Lors d’une rencontre, cette competence permet de se rappeler des echanges

precedents et ainsi de construire une relation a long terme ou les individus finissent par

se connaıtre et savoir anticiper leurs comportements et besoins respectifs. Dans une

situation ou un delit est effectue a visage decouvert, reconnaıtre le coupable permet de

lui faire assumer la responsabilite de ses actes.

L’interet de la communaute scientifique a la reproduction de cette aptitude pour des

applications judiciaires, de controle et d’assistance est donc manifeste; la verification

d’identite pour le deverrouillage d’ordinateur ou la traque de suspects a travers les

enregistrements videos de stations de metro representent un echantillon des nombreuses

applications envisageables a partir de ce type de technologie.

L’objectif de ce memoire est de concevoir et d’implementer sur un petit robot hu-

manoıde commercialise par Aldebaran Robotics une application de reconnaissance fa-

ciale capable de reconnaıtre les individus apres une seule prise de vue. Nao, le petit

robot humanoıde, montrera son intention d’entrer en interaction avec une des personnes

reconnues en la poursuivant du regard.

Le logiciel developpe aura deux taches principales a effectuer. Tout d’abord la locali-

sation des visages dans le champ visuel de Nao et leur poursuite a chaque rafraıchissement

de l’image. Ensuite la reconnaissance des visages detectes.

Dans un contexte plus large, ce logiciel incarne l’assise d’applications plus sophis-

tiquees d’interactions homme-machine : une fois les personnes reconnues et le regard

oriente vers un individu, la voie est prete pour un echange. Celui-ci pourra, par exemple,

commencer par l’analyse des emotions du visage de la personne ou par le rassemblement

des donnees en memoire concernant l’individu.

De par cette position a la source d’une grande quantite d’applications potentielles,

l’execution du logiciel devra obeir a des exigences de fluidite et de rapidite et fournir un

resulat robuste.

1

Figure 1: Robot humanoıde Nao utilise comme support de l’application de ce memoire. Il

mesure 58 centimetres, est capable de se mouvoir et possede une camera sur le

front qui sera utilisee par le logiciel pour capturer l’image de l’environnement qui

lui fait face. Ses ressources au niveau du processeur et de la memoire sont faibles

et ameneront le logiciel final a etre execute a cote, sur un ordinateur distant plus

puissant.

La seconde tache chargee de la reconnaissance des visages convertit d’abord l’image

en ’modeles binaires locaux’ et divise l’image en sous-regions pouvant se chevaucher. Un

comptage des modeles binaires locaux est ensuite realise pour chaque sous-region et les

histogrammes ainsi obtenus servent de base a la comparaison d’individus.

La maniere de decomposer l’image a une influence capitale sur les performances finales

du classifieur: comme la transformation en histogrammes efface toutes les informations

quant a l’emplacement des modeles binaires locaux, la division est l’unique garante que

des donnees concernant l’organisation spatiale sont disponibles durant le processus de

comparaison.

Trouver la meilleure combinaison de sous-regions n’est pas facile vu leur nombre.

Ainsi, trouver la meilleure association de trois sous-regions contenues dans un visage de

60 × 60 pixels, signifie selectionner 1 combinaison parmi 6.2597 × 1018 candidats. Ce

memoire accorde une importance speciale a ce probleme et propose une solution pour

gerer ce grand nombre de candidats.

De plus, il a ete decide de developper une methode de generation d’une carte qui, par

sa consultation, permettrait de reperer tout de suite les zones du visage a considerer

2

prioritairement pour la reconnaissance. Cette carte offrirait par la meme occasion une

vue d’ensemble du visage en termes de ces zones les plus a meme de differencier les

individus.

Le developpement d’une telle methode s’est revele plus ardu que prevu et les prin-

cipaux problemes a resoudre ont ete les consequences negatives des effets de bord et la

tendance au gommage des contours de la carte lors de l’utilisation de methodes simples.

Structure du memoire

Dans les deux premiers chapitres j’introduirai les problemes de localisation et de

reconnaissance faciale et presenterai les principales methodes qui sont utilisees de nos

jours pour leurs resolutions.

Dans le troisieme chapitre, je parlerai de la conception du logiciel de reconnais-

sance faciale utilisant Nao comme support en precisant les contraintes materielles que

l’utilisation d’un tel robot provoque sur l’architecture d’une application de ce type.

Dans le quatrieme chapitre, je parametrerai le logiciel pense au chapitre 3 en utilisant

le logiciel MatLab.

Dans le cinquieme chapitre, j’expliquerai comment j’ai developpe un systeme qui per-

met de generer une carte des regions les plus utiles a la discriminination dans le cas de

la reconnaissance faciale a partir d’un seul cliche.

Dans le sixieme chapitre, je donnerai le resultat des tests de performance.

3

Partie I

Etat de l’art

4

Chapitre 1

Detection de visages

La detection des visage pose le probleme de la localisation des visages presents dans une

image d’entree. Idealement, la detection fourni aussi leurs dimensions pour un eventuel

traitement ulterieur.

L’interet de la localisation faciale va au-dela de l’application de ce present memoire.

Son utilite se manifeste dans des domaines varies allant de la videosurveillance au jeu

interactif. Les premieres difficultes rencontrees par les methodes s’attelant a detecter

les visages sont les variations de pose (vue de profil, de face), d’expression, de rotation

du visage1, d’age et d’illumination. Ce dernier type de difficulte pouvant etre surmonte

par un pretraitement de normalisation et de compensation de l’illumination presente

au chapitre 2.4. Pour le reste la difficulte est d’autant plus grande que la plupart des

applications ayant recours a cette technologie requierent une execution en temps reel,

limitant les marges de manoeuvre de l’algorithme.

Une classification des methodes de localisation faciale est proposee par Yang et al.

[49]:

• ”Knowledge-based methods”. Ces methodes se basent sur la connaissance des

differents elements qui constituent un visage et des relations qui existent entre

eux. Ainsi, les positions relatives de differents elements cles tels que la bouche, le

nez et les yeux sont mesures pour servir ensuite a la classification ’visage’ ’non-

visage’ chez Chiang et al. [13]. Le probleme dans ce type de methode est qu’il

est difficile de bien definir de maniere unique un visage. Si la definition est trop

detaillee, certains visages seront rates tandis que si la description est trop generale

le taux de faux positifs montera en fleche.

• ”Feature invariant approaches”. Ces approches utilisent les elements invariants

1selon un axe perpandiculaire a l’objectif

5

aux variations d’illumination, d’orientation ou d’expression tels que la texture ou

la signature de couleur de la peau pour la detection.

• ”Template matching methods”. Des modeles caracteristiques d’un visage entier

ou de sous-partie de visage (bouche, oeil, nez) sont crees. La localisation se fait

ensuite sur base de la correlation de ces modeles avec les candidats.

• ”Appearance-based methods”. Ces methodes utilisent le meme principe que presente

au point precedent mais se basent sur des modeles appris a partir de set d’entraınement.

Ces methodes presentent l’avantage de s’executer tres rapidement mais demandent

un long temps d’entraınement. Les methodes appartenant a cette categorie ont

montre de bons resultats par rapport aux 3 autres types de methodes [54], on peut

citer parmi celles-ci la methode basee sur les reseaux de neurones de Rowley et al.

[29], la methode de Schneiderman et Kanade [30] basee sur un classifieur de Bayes

naıf ainsi que le fameux algorithme de Viola et Jones [38] fonctionnant en temps

reel qui sera detaille plus loin.

Notons que la delimitation entre les trois premieres categories est parfois floue et que

dans les articles plus recents, ces categories sont fusionnees entre elles [54, 35, 20].

1.1 Algorithme de Viola & Jones

Une avancee majeure dans le domaine a ete realisee par Viola et Jones en 2001 [38]. Ces

derniers ont propose une methode basee sur l’apparence (”Appearance-based methods”)

robuste et tournant a 15 fps pour des images de 384 x 288 pixels sur un pc Intel Pentium

III 700Mhz. Ce fut la premiere methode en temps reel presentee. La renommee de cette

approche 2 est faite sur trois concepts :

1.1.1 L’image integrale

L’algorithme se base sur les caracteristiques de Haar (Haar features) pour localiser les

visages presents sur une image d’entree. Dans le but d’extraire rapidement ces car-

acteristiques, l’image est representee sous forme integrale. En effet, sous cette forme,

l’extraction d’une caracterisque a n’importe quel endroit et a n’importe quelle echelle est

effectuee en un temps constant tandis que le temps de conversion vers la representation

integrale ne remet pas en cause ce gain de temps offert par l’utilisation de la representation

en image integrale. La definition des caracteristiques de Haar et la maniere dont la

2L’article Robust Real-Time Face Detection [39] est cite plus de 1600 fois selon Google Scholar

6

representation integrale accelere considerablement leur extraction sont presentes ci-apres

pour une image en niveaux de gris.

Dans toute image, une zone rectangulaire peut etre delimitee et la somme des valeurs

de ses pixels calculee. Une caracteristique de Haar est une simple combinaison lineaire

de sommes ainsi obtenues.

Plusieurs caracteristiques de Haar peuvent etre definies selon le nombre, les echelles,

les positions et les dimensions des zones rectangulaires considerees. 4 exemples sont

presentes a la figure 1.1.

Figure 1.1: Exemple de 4 caracteristiques de Haar. La somme des valeurs des pixels ap-

partenant aux zones encadrees claires est soustraite a la somme des valeurs des

pixels appartenant aux zones encadrees sombres pour obtenir la caracteristique

de Haar. Chacune des quatre caracteristiques de Haar est representee avec son

cadre de detection respectif.

Presente comme tel, le calcul d’une caracteristique de Haar demande a chaque fois

l’acces aux valeurs de tous les pixels contenus dans les zones rectangulaires considerees.

Cela devient vite contraignant temporellement des que les caracteristiques de Haar sont

definies par des zones rectangulaires de grandes dimensions. L’image integrale permet

de surmonter ce probleme en rendant constant le temps de calcul d’une caracteristique

de Haar a n’importe quelle echelle.

L’image integrale est representee mathematiquement par :

ii(x, y) =∑

x′≤x,y′≤y

i(x′, y′) (1.1)

∀ 0 < x ≤ width, 0 < y ≤ height (1.2)

ou i(x, y) est l’image d’origine et i(x′, y′) l’image sous sa nouvelle representation. Ainsi

chaque pixel a pour valeur la somme des valeurs des pixels compris dans le rectangle

defini par le coin superieur gauche de l’image et lui-meme.

7

Le calcul de la somme des valeurs des pixels appartenant a une zone rectangulaire

s’effectue donc en accedant seulement a quatre pixel de l’image integrale : Soit un

rectangle ABCD dont les sommets sont nommes dans le sens des aiguilles d’une montre

en commencant par le sommet superieur gauche et soit x la valeur sous la representation

integrale d’un sommet X du rectangle (X ∈ {A,B,C,D}). La somme des valeurs des

pixels appartement a ABCD est, quelle que soit sa taille, donnee par c− b− d+ a.

Une caracteristique de Haar etant une combinaison lineaire de tels rectangles ABCD,

son calcul se fait alors en un temps independant sa taille.

1.1.2 Algorithme d’apprentissage base sur Adaboost

Pour localiser les visages sur l’image d’entree, cette derniere est scannee par une fenetre

de dimension determinee. La fenetre parcourt l’image et son contenu est analyse pour

savoir s’il s’agit d’un visage ou non. Comme dit plus haut, les caracteristiques de Haar

sont extraites pour effectuer la classification et de ce fait la representation integrale

de l’image accelere l’analyse. Mais, pour une fenetre de 24x24 pixels il y a 45 396

caracteristiques de Haar, les traiter toutes prendrait beaucoup trop de temps pour une

application en temps reel. Pour surmonter ce probleme, une variante de la methode de

boosting Adaboost est utilisee.

Ci-dessous Adaboost est brievement presente suivi de sa variante qui constitue le

deuxieme apport du travail de Viola & Jones.

Adaboost est une methode d’apprentissage permettant de ”booster” les performances

d’un classifieur quelconque nomme ”classifieur faible”. L’idee est de faire passer les

candidats a classifier a travers plusieurs classifieurs faibles, chacun etant entraıne en

portant plus d’attention sur les candidats mal classifies par le classifieur precedent.

Pour arriver a ce resultat des poids sont associes aux echantillons du set d’entraınement3

((xi, yi) i = 1, ...,m), tout d’abord de maniere equilibree :

w0i =

1

m(1.3)

pour i = 1, ...,m. Le 0 en exposant indique qu’il s’agit des poids initiaux.

Ensuite le premier classifieur faible est entraıne comme suit :

h0 = argminhj∈Hεj (1.4)

avec l’erreur εj =∑m

i=1w0i δ(yi − hj(xi)) et H l’ensemble des classifieurs faibles. Puis

une nouvelle generation de poids w1i sont crees tels qu’ils accordent plus d’importance

3Pour un echantillon (x, y) appartenant au set, x est la valeur de l’echantillon et y la classe a laquelle

il appartient

8

aux echantillons mal classifies par h0. Ensuite un nouveau classifieur h1 est entraıne,

puis de nouveaux poids w2i sont generes et ainsi de suite. Enfin, apres T iterations, le

classifieur fort H(x) est obtenu :

H(x) = sign

(T∑t=1

αtht(x)− θ

)(1.5)

avec α = 12ln

1−εtεt et θ un seuil a determiner. La valeur a attribuer a ce dernier sera dis-

cutee plus loin. Chaque classifieur fort est donc constitue d’un nombre T de classifieurs

faibles.

Adaboost sert donc a booster une classifieur deja existant et a priori chaque clas-

sifeur faible possede le meme espace d’entree. Dans la variante d’Adaboost de Viola

& Jones, les classifieurs faibles hj ∈ H ont pour entree une caracteristique de Haar

differente. Adaboost s’apparente alors a une selection de caracteristiques (feature selec-

tion). Cette variante d’Adaboost est utilisee lors de l’apprentissage pour selectionner

les caracteristiques de Haar les plus a meme de detecter un visage et permet ainsi de

surmonter le probleme du nombre eleve de caracteristiques de Haar existant pour une

fenetre de recherche.

1.1.3 Cascade

L’idee de base derriere le concept de Cascade est que parmi l’ensemble des candidats,

c’est a dire l’ensemble des etats de la fenetre de recherche, une partie peut etre eliminee

sur base de l’evaluation de seulement quelques caracteristiques de Haar. Une fois cette

elimination effectuee, les candidats restants sont analyses par des classifieurs forts plus

complexes (utilisant plus de caracteristiques de Haar) demandant un plus grand temps de

traitement. En utilisant plusieurs ’etages’ de ce type, le processeur evite d’effectuer des

analyses lourdes en temps de calcul sur des echantillons pour lesquels il est rapidement

possible de se rendre compte qu’ils sont negatifs. Le processus de classification apparaıt

alors comme une cascade de classifieurs forts de plus en plus complexes ou a chaque

etage les echantillons classifies negatifs sont sortis tandis que les echantillons classifies

positifs sont envoyes aux classifieurs suivants. Ceci est represente a la figure 1.2.

Si le premier etage rejette un faux negatif, c’est un gros probleme car il ne sera

jamais recupere par la cascade. Autrement dit c’est un visage qui ne sera pas detecte.

Par contre, si le premier etage transmet un faux positif, il pourra toujours etre elimine

aux etages suivants de la cascade. Ce petit raisonnement permet de mettre en evidence

que les premiers noeuds constitutifs de la cascade peuvent se permettre d’avoir un taux

de faux positifs eleves (de l’ordre de 40-50%) mais doivent absolument assurer un taux

9

Figure 1.2: Cascade de classifieurs forts. A chaque etage, uniquement les candidats classifies

positifs sont transmis a l’etage suivant.

de detection maximum. La parametrisation de l’algorithme en ce sens sera detaillee

dans la prochaine section.

Ce concept permet donc a l’algorithme de consacrer son temps a de longues analyses

complexes uniquement lorsque cela en vaut la peine. Il s’agit a nouveau d’un mecanisme

qui accelere la vitesse d’execution de la methode proposee par Viola & Jones.

1.2 Parametrisation & Entraınement

Le nombre d’etages dans la cascade, leurs seuils de detection θ et le nombre de car-

acteristiques T considere a chaque etage sont a ajuster pour que la localisation soit

rapide et atteigne un taux de detection eleve. Cet ajustement se fait pendant la phase

de construction de la cascade qui sera decrite apres l’introduction des quelques elements

cles ci-dessous.

Premierement, pour une image d’entree en situation reelle, le nombre de candidats

qui s’avereront positifs est relativement faible par rapport au nombre total de candidats.

Le probleme est dit asymetrique. Il faut des lors pour assurer une detection fiable que le

taux de detection des negatifs soit bien plus eleve que le taux de detection des positifs.

On parle typiquement d’un taux de detection autour de 95%-99% et d’un taux de faux

positif extrement faible4 de l’ordre de 10−7. L’asymetrie constitue donc une difficulte a

la resolution du challenge de localisation faciale. Notons que le probleme de localisation

faciale est asymetrique pour 3 raisons categorisees par Wu et al. dans [44].

Ensuite et enfin, les elements cles taux globaux de detection D et taux de faux

4Un taux de detection des negatifs eleve (= TNFP+TN ) equivaut a un faible taux de faux positifs

(= FPFP+TN )

10

positifs F sont definis comme suit :

D =K∏i=1

di (1.6)

F =K∏i=1

fi (1.7)

ou K est le nombre d’etages de la cascade, di l’objectif local de detection (voir plus

loin) et fi l’objectif local de faux positifs (idem).

La methode de construction de la cascade utilisee par Viola & Jones recoit ses objectifs

en terme de taux de detection et taux de faux positifs globaux. Ceux-ci permettent

de determiner les objectifs locaux (entendre par noeud) par les formules presentees-ci

dessus. Puis, la cascade est construite un etage apres l’autre, le processus prenant fin

des lors que les objectifs globaux sont atteints. La construction d’un etage est faite en

utilisant Adaboost, ce dernier ajoute des caracteristiques au classifieur fort jusqu’a ce

que les taux locaux de detections de positifs et negatifs soient atteints.

Imaginons une cascade de 15 etages pour laquelle nous souhaitons obtenir un taux de

detection de 99% et un taux de faux positif de 10−7. Par les formules ci-dessus l’objectif

local en taux de detection doit donc etre de 99.93%. Ce dernier semble au premier

abord difficile mais l’operation est facilitee par le fait que le taux de faux positifs local

necessaire est de 34.14% (>> 10−7). Ainsi la difficulte attribuee au haut taux de faux

positif global est surmontee par l’utilisation de la cascade qui ”divise” l’embuche parmi

les etages. Notons que le taux de detection local est quant a lui superieur a son equivalent

global.

On observe qu’une cascade entraınee comme telle repond aux attentes de rapidite

formulee par l’exigence du temps reel. Les premiers niveaux traitent quelques car-

acteristiques en rejettant plus de 50% des negatifs tandis que les derniers niveaux plus

complexes analysent jusqu’a plusieurs milliers de caracteristiques de Haar pour arriver au

meme resultat. La complexite et le temps de calcul sont donc bien distribues de maniere

a ce qu’uniquement les candidats les plus prometteurs soient soumis aux analyses les

plus gourmantes en instructions.

Une technique de boostrapping est utilisee lors de l’entraınement du detecteur en

cascade. Apres la construction de chaque etage, un nouveau set de non-visages est

construit pour l’entraınement du suivant. Celui-ci est constitue des echantillons negatifs

qui n’auront pas ete detectes par la cascade en cours de construction. Le set d’echantillon

positif reste quant a lui toujours le meme.

11

1.3 Travaux existants suite a l’Algorithme de Viola

& Jones

1.3.1 Nouvelles caracteristiques

Lienhart et al. ont propose en plus de la represenation integrale une representation

integrale inclinee ou chaque pixel a pour valeur la somme des valeurs des pixels com-

pris dans la zone rectangulaire inclinee de 45◦ dont le point extreme droit est le pixel

considere. Aux modeles initiaux de Viola & Jones sont donc ajoutes leurs equivalents

inclines de 45◦. Le set obtenu ainsi et utilise par Lienhart et al. est presente a la figure

1.3. Lienhart et al. ont obtenu ainsi des ameliorations de l’ordre d’un demi-pourcent

d’erreur.

Figure 1.3: Set de caracteristiques de Haar obtenu par Lienhart et al. en utilisant les concepts

d’image integrale et d’image integrale inclinee.

1.3.2 Ameliorations du Training set

Les performances du classifieur final peuvent etre ameliorees en preparant le set d’entraınement.

Les travaux recents effectues par Chen et al. [9] proposent une methode basee sur un

algorithme genetique pour etendre le set de visages. L’utilisation de leur approche est

selon leurs dires la plus prometteuse dans le domaine de l’optimisation du Training set.

En reconnaissance faciale, le ”one sample problem” ou un seul echantillon est disponible

par personne a reconnaıtre, des travaux s’interessent a la generation de nouveaux echantillons

positifs a partir d’un seul visage. Cette optimisation du training set sera traitee dans le

chapitre 2 consacre a la reconnaissance faciale.

1.3.3 Dernieres avancees : Wu et al.

La version developpee par Wu et al. en 2008 [44] est prise dans un article recent comme

reference en terme de vitesse et de performance [46]. Leurs travaux se consacrent a

la fois a la vitesse de traitement, la vitesse d’apprentissage et aux performances en

12

termes de taux de detection. L’algorithme de Viola & Jones effectue la selection de car-

acteristiques et l’apprentissage en une seule etape lors de l’intervention d’Ababoost dans

l’algorithme. Wu et al. proposent de traiter ses deux phases separement et avancent que

cela permet de mieux gerer les difficultes liees a l’asymetrie du probleme de localisation

faciale. Ils enumerent leurs contributions au nombre de trois. Premierement une analyse

appronfondie du probleme qui revele trois causes d’asymetrie du probleme et les diffi-

cultes qu’elles engendrent. Deuxiemement une methode de selection de caracteristiques

est proposee, la FFS pour ”forward feature selection”, cette derniere accelerant 50 a

100 fois l’apprentissage d’Ababoost. Et troisiemement un algorithme d’apprentissage

nomme ”Linear Asymetric Classifier” (LAC) est presente. Il est montre que ce dernier

ameliore les performances du classifieur.

1.3.4 Dernieres avancees : Xiaohua et al.

Comme vu plus haut, lors de l’entraınement de la cascade, un nouveau set de non-visages

est genere par bootstrapping a la fin de la construction de chaque etage. Xiaohua et

al. [46] ont remarque qu’au fur et a mesure que la cascade grandissait, les non-visages

collectes sont de plus en plus similaires aux visages et que le taux d’erreur des noeuds

les plus profonds sur un set de validation compose uniquement d’echantillons negatifs

tendait vers 0.5. Cela signifie qu’il devient ardu de trouver des caracteristiques encore

capables de distinguer les non-visages des visages. Ils observent aussi que le nombre

de caracteristiques necessaires pour atteindre les objectifs locaux en terme de taux de

detection et de faux positifs augmente selon une pente de plus en plus raide pour les

noeuds profonds. Ceci confirme la difficulte de trouver des bonnes caracteristiques.

Notons que les echantillons positifs utilises sont des carres couvrant la zone yeux-nez-

bouche.

Xiaohua et al proposent qu’au dela d’une certaine profondeur soient considerees

les parties entourant la zone yeux-nez-bouche en se basant sur le fonctionnement du

systeme visuel humain [34]. Ils avancent que les informations de ces zones peuvent etre

benefiquement utilisees lorsque la zone centrale est epuisee. Ainsi une hierarchie est mise

en place ou 3 dimensions standards d’echantillons positifs sont utilisees successivement

pour entraıner la cascade. Ceci est presente a la figure 1.4.

De plus, ils proposent une extension du set de caracteristiques de Haar compose

de wavelets de Gabor simplifiees. Ces wavelets sont des fonctions inspirees du profil

des champs receptifs de l’oeil des mammiferes [14]. Elles sont simplifiees car elles sont

calculees a partir des representions integrales et integrales inclinees de maniere a ne pas

compromettre l’aspect temps reel de l’algorithme de Viola et Jones. Ceci est illustre a

13

Figure 1.4: 3 types d’echantillons positifs utilises par Xiaohua et al. pour ameliorer les

performances du classifieur en cascade. Le format de gauche est d’abord utilise

puis lorsque son potentiel en caracteristiques devient trop faible le format suivant

est utilise et ainsi de suite.

la figure 1.5.

Figure 1.5: En haut : quelques wavelets de Gabor. Une frequence a plusieurs orientations

est presentee. En bas : echantillon des Wavelets de Gabor simplifiees utilisees

comme caracteristiques pour le classifieur en cascade.

Les experiences menees par l’equipe montre des ameliorations en terme de vitesse et

de taux de detection par rapport a la version de Wu et al.

14

Chapitre 2

Reconnaissance de visages

Le domaine de la reconnaissance faciale se veut de proposer des methodes pour parvenir

a identifier des personnes a partir d’informations visuelles. Pour cela la reconnaissance

faciale fait partie des methodes de biometrie qui visent a l’identification des personnes

a partir d’informations biologiques. D’autres methodes appartenant a cette categories

sont par exemple la capture de l’image de l’iris ou des empreintes digitale.

La reconnaissance faciale est un domaine de recherche aux publications foisonnantes

en raison de ses nombreuses applications. Parmi celles-ci les systemes de controle d’acces,

de surveillance, d’interaction homme machine dans des applications multimedia de di-

vertissement ou a finalites educatives, de verification de carte de credit et bien d’autres.

Une premiere distinction au sein des approches existantes peut se faire entre les

methodes a echantillons multiples et les methodes a echantillon unique. Dans la premiere

categorie, le training set est compose de plusieurs prises de vue par sujet et ces dernieres

peuvent inclure des variations diverses telles que l’illumination, l’age, l’orientation du

visage ou l’expression. La seconde categorie, quant a elle, s’attarde sur des problemes de

reconnaissance ou il n’y a qu’un seul echantillon disponible par personne pour construire

le reconnaisseur de visage.

Un breve description de l’etat de la technique pour le probleme a echantillons mul-

tiples est faite ci-dessous suivi d’un etat de l’art de la resolution du probleme de la

reconnaissance faciale a partir d’une seule image. Cette demarche qui accorde plus

d’interet sur le probleme a echantillon unique est utilisee car l’attention de ce memoire est

premierement portee sur ce probleme aussi denomme le ”one sample problem”. Apres cet

etat de l’art, je m’attarderai a decrire et faire l’inventaire detaille des dernieres avancees

relatives a la methode des ’Local Binary Patterns’ qui sera utilisee pour l’application de

ce memoire.

15

2.1 Probleme a echantillons multiples

Les methodes s’attelant a la resolution de ce probleme peuvent etre classees en plusieurs

categories [53]:

1. Les methodes de projection qui prennent en entree un vecteur constitue de la

concatenation des lignes de l’image. On compte entre autres parmi ces methodes

l’analyse en composante principale (PCA) [36] et l’analyse en discriminant lineaire

de Fisher(FLDA) [7]. Les limitations de ces methodes viennent de leur sensibilite

aux variations d’expression et d’illumination car elles considerent chaque visage

comme une combinaison de vecteurs de base appeles ”Eigen Face” ou ”Fisher

Face”, ce qui est evidemment faux [5].

2. Les reseaux de neurones parmi lesquels ont peut noter la presence de la methode

Elastic Bunch Graph Matching (EBGM) [43] ou un graphe est superpose au visage

de maniere a faire correspondre les noeuds a des points cles du visage tels que les

yeux et le bout du nez. Chacun de ses noeuds est rattache a un ou plusieurs ”jets”

de Gabor constitues de reponses du voisinage du noeud en question face a des

filtres associes a plusieurs wavelets de Gabor. Ces jets de Gabor attribuent a la

methode EBGM une robustesse face aux variations d’illumination, aux distortions

et aux changements d’echelle [26]. Notons que le champ de recherche issu des EBM

(Elastic Graph Mathing) est large et compte dans ses rangs d’autres methodes

que le EBGM tels que le morphological elastic graph matching (MEGM) [22] ou

le discriminant elastic graph matching (DEGM) [52].

3. Les autres methodes sont basees sur l’obtention d’informations complementaires

telles que la profondeur ou le profil infrarouge. Ces techniques ouvrent la voie a de

nouvelles methodes pour contrer les variations d’illumination qui seront traitees

dans le chapitre 2.4.

2.2 Probleme avec un seul echantillon d’entraınement

par personne

Les avantages d’un systeme capable de resoudre ce probleme sont (1) la facilite de

rassembler un training set car une simple photo suffit par personne; (2) une economie de

memoire pour le stockage de la base de donnees; (3) une economie de temps d’apprentissage

peut avoir lieu puisqu’il n’y a qu’une seule image par personne a considerer [32]. L’interet

16

d’un tel systeme est donc tout a fait tangible que ce soit pour un systeme de poursuite

de suspect a travers un reseau de cameras ou pour la verification d’identite.

Dans ce type de probleme, on ne peut compter sur la taille du training set pour

distinguer les variabilites intra-class (au sein d’un meme groupe, ici l’ensemble des vari-

ations pouvant affecter un meme visage, a savoir l’illumination, la pose, l’expression,

l’age) et inter-class (entre les individus)[42].

L’ensemble de ces methodes peut faire l’objet d’une classification, celle de Tan et al.

[32] compte 3 categories qui seront detaillees dans les sections suivantes : les methodes

holistiques, les methodes locales et les methodes hybrides.

2.2.1 Methodes holistiques

Ces dernieres utilisent comme entree l’image complete sous forme d’un vecteur de niveau

de gris pour decider d’une identite. Ici tombent des extensions au ”one sample problm”

issues des methodes de projection presentee plus haut. Malheureusement, ces methodes

de projection concues pour le probleme a echantillons multiples ne sont pas directement

utilisables ici. En effet, les methodes de projection telle que la LDA [51] ayant fait leurs

preuves dans le domaine du probleme a echantillons multiples souffrent du probleme du

petit nombre d’echantillons (small sample size (SSS) problem) [19] [55] qui degrade leurs

performances. Neanmoins, on trouve dans les developpement recents des travaux qui

passent au dessus de ce probleme et presentent des resultats corrects. Parmi ces travaux

la (PC)2A [45] suivi de sa generalisation la E(PC)2A [11]; et la 2DPCA [48].

Toujours dans le domaine des methodes holistiques, des strategies consistent a elargir

artificiellement le training set par la generation de nouveaux echantillons a partir du pre-

mier, ouvrant ainsi la porte a l’utilisation de methodes a echantillons multiples. Citons

parmis celles-ci l’idee simple de Yang et al. [50] qui utilisent les images symmetriques

gauche et droite pour generer de nouvelles vues. A noter aussi, le travail de Beymer et

al. [8] qui ont presente la methode de deformation parallele pour generer de nouvelles

poses a partir d’une premiere photo (voir figure 2.1 pour un exemple).

2.2.2 Methodes locales

Cette categorie se divise en deux sous-categories basees respectivement sur des car-

acteristiques et des apparences locales.

Methodes basees sur des caracteristiques locales

Ici des proprietes geometriques sont extraites a partir de la localisation de points cles

sur le visage. Deux faiblesses en decoulent directement : d’une part la localisation de

17

Figure 2.1: Mehode de deformation parallele developpee par [8] pour la generation de nou-

veaux echantillons via generation de nouvelle pose. L’image d’entree est la photo

centrale, les 8 autres ont ete generees automatiquement.

tels points n’est pas toujours une mince affaire lorsque des occlusions ou des variations

de position ou d’expression surviennent et d’autre part toute l’information necessaire a

une reconnaissance robuste n’est pas forcement contenue dans ces quelques points cles,

en effet beaucoup d’informations passent a la trappe lorsque l’image est compressee aux

informations contenues a quelques endroits. Un exemple parlant est la methode DCP

de Gao et al. [18] qui, appliquee au probleme de la reconnaissance faciale de personnes

qui crient, presente une chute de performance de pres de 60% [32].

On peut noter parmi ces mehodes basees sur les caracteristiques locales les developpements

de Gao et al. [18] deja mentionnes plus haut et les EBGM [43]. Du a l’etape necessaire

de recherche des points cles, cette derniere technique a pour defaut de pouvoir demander

plus de temps de calcul pour son execution que la PCA.

Methode basees sur des apparences locales

Ici ce sont plusieurs vecteurs correspondant a des caracteristiques du visage qui sont

utilises en entree. Ces methodes sont a priori mieux taillees pour le probleme a echantillon

unique [32]. Tout d’abord car un set de plusieurs vecteur de faible dimension au lieu d’un

seul de grande dimension permet des le debut de s’attaquer a la malediction de la dimen-

18

sionnalite (curse of dimensionality). Ensuite le fait d’avoir plusieurs sous-vecteurs de car-

acteristiques permet l’utilisation d’un systeme de poids donnant priorite dans la decision

finale aux sous-vecteurs identifies comme etant les plus discriminatifs, ce qui ameliore

les performances [37]. Enfin, un nombre eleve de sous-vecteurs de caracteristiques peut

augmenter la diversite des types de classifieurs utilises par le biais d’equipe de classi-

fieurs et ainsi ameliorer les performances du classifieur global [23]. Notons que ces trois

observations peuvent s’appliquer aussi a certaines methodes de la premiere categorie des

methodes locales tel que l’Elastic Bunch Graph Matching (EBGM) ou a chaque point

cle correspond un vecteur d’information.

Ci-apres sont citees quelques autres techniques appartenant a cette categorie qui sont

reprises dans le tableau recapitulatif de performance compile par Tan et al. [32] presente

a la figure 2.2. Les travaux de Tan utilisant les ’self-organizing-map’ (SOM) [31], une

technique pour rendre la LDA utilisable pour le one sample problem [10], une appoche

analytic-to-holistic de Lam et al. [24], la methode basee sur les Hidden Markov Model

[25] et les Local Binary Patterns [4]. Ces derniers feront l’objet d’explications et d’un

etat de l’art detaille a la section 2.3.

2.2.3 Methodes hybrides

Comme leur nom le fait penser, ces approches combinent des methodes holistiques et

locales. L’idee est de les combiner de maniere a utiliser les avantages de l’une pour con-

trebalancer les defauts de l’autre. La combinaison efficace entre caracteristiques locales

et globales reste pour le moment un probleme et peu de travaux sur son application au

probleme de la reconnaissance faciale existent [32].

A la figure 2.2 sont reprises les performances des methodes phares dans le domaine

de la reconnaissance faciale a partir d’une seule image par personne.

2.3 Les ’Local Binary Patterns’ appliques a la re-

connaissance faciale

Ci-dessous sera decrite la methode de Ahonen et al., la majeure partie des informations

etant reprise de leur article [4].

L’operateur LBP basique prend comme entree un carre de 9 pixels et a pour sortie

un nombre binaire 8 bits. Ce dernier est presente a la figure 2.3. La motivation qui

a pousse a utiliser cet operateur est qu’un visage peut etre vu comme un assemblage

19

Figure 2.2: Tableau recapitulant les scores de certaines methodes s’attaquant au probleme

de la reconnaissance faciale avec des training sets composes d’un seul echantillon

par personne. La base de donnees utilisee pour les tests est a chaque fois in-

diquee ainsi que des informations complementaires sur les conditions de test

(nombre d’images, de personnes a tester, etc.). Le dataset accessoire designe un

set exterieur utilise lors de l’entraınement, il peut s’agir par exemple d’identifier

les deformations que le visage subit lorsque la position du sujet change d’une

photo a l’autre dans le but de les reproduire pour elargir le training set artifi-

ciellement comme dans la methode de deformation parallele [8].

de micro-patterns dont la description par LBP est a la fois bonne, robuste face aux

variations de gris et rapide a generer.

Figure 2.3: Operateur LBP basique. L’entree est un carre de 9 pixels. Un seuil est applique

tel que tous les pixels peripheriques dont la valeur est superieure a la valeur

du pixel central se voient attribuer la valeur 1 tandis que les autres recoivent

la valeur 0. La valeur LBP finalement obtenue est le nombre binaire se lisant

dans le sens des aiguilles d’une montre autour du pixel central. La convertion

de toute une image se fait en deplacant une fenetre de conversion de 3x3 pixels

sur l’entierete de l’image. Pour obtenir une image convertie de meme dimension

que l’image d’entree on peut par exemple repeter les pixels du bord de l’image.

Figure tiree de [4].

20

Cet operateur simple a ete etendu pour rester fiable a differentes echelles. Ainsi, P

points decrivent le nombre binaire et ceux-ci sont distribues le long d’un cercle de rayon

R. Cet entourage sera note (P,R). Comme ces P points ne tombent pas necessairement

au centre d’un pixel de l’image, leurs valeurs sont obtenues par interpolation bilineaire.

Ceci est illustre a la figure 2.4.

Figure 2.4: Extension de l’operateur lbp basique. Les entourages (8,1), (16,2), (8,2) sont

representes. Figure tiree de [4].

Ensuite ne sont gardes que les patterns ’uniformes’ ne presentant au plus que deux

transitions 1-0 ou 0-1 lorsqu’ils sont regardes comme des cercles. Ainsi 00110000 et

10000001 sont uniformes tandis que 10010001 et 11011101 ne le sont pas. En pratique,

la conversion d’un pattern non uniforme donne le resultat 0. On se rend compte ainsi

que 90% des patterns (8, 1) appartiennent a la categorie des uniformes. Cette extension

permet l’interpreter les LBPs en termes de coins et arretes inclinees et sera revue a la

section 3.3.3.

Ensuite pour inclure une information quant a la disposition spatiale des textures et

eviter de se limiter a une description holistique des textures qui souffrirait des limitations

connues des methodes de ce type, l’image convertie est divisee en plusieurs sous-regions

pour lesquelles autant d’histogrammes LBP seront faits. Ainsi pour 4 sous-regions, 4

histogrammes seront generes. Ces derniers seront concatenes pour former une matrice a

2 dimensions appelee ’histogramme spatialement ameliore’. Notons que les sous-regions

peuvent se recouvrir et ne doivent pas necessairement etre rectangulaires.

La comparaison de deux histogrammes spatialement ameliores suppose d’une part

d’etablir une methode de mesure de distance entre deux histogrammes simples et d’autre

part l’utilisation de poids pour rassembler les distances obtenues pour chaque sous-

region. La methode 2 en 1 proposee par Ahonen et al. est la distance carre de Chi

balancee :

χ2w(x, ξ) =

∑j,i

wj(xi,j − ξi,j)2

xi,j + ξi,j

ou x et ξ sont des histogrammes spatialement ameliores normalises a comparer, i cor-

respond a iieme valeur du jieme sous-histogramme et wj est le poids accorde a la sous-

region j.

21

Notons maintenant l’ensemble des elements parametrisables : tout d’abord le choix

de l’entourage (P,R) a utiliser pour la conversion LBP, ensuite la maniere dont les sous-

regions sont delimitees, puis le poids accorde a chacune d’elles et enfin la methode de

calcul de distance qui sera utilisee pour comparer deux histogrammes. Ces parametrages

bien effectues amelioreront les performances du classifieur final.

2.3.1 Dernieres avancees : Travail de Tan et Triggs

Leur travail [33] fait suite a celui de Ahonen et al. et propose 3 nouveaux concepts qui

permettent d’ameliorer significativement les performances (plus de 40% sur la database

FRGC-104 selon leur publication). Ces trois concepts sont les Local Ternary Patterns

(LTP), une methode de pretraitement de l’image et enfin une methode de mesure de

distance pour la comparaison d’echantillons au format LBP ou LTP. Ces concepts sont

detailles ci-dessous.

Les ’local ternary patterns’

Il s’agit de la generalisation des ’local binary patterns’ au systeme ternaire. Elle a ete

proposee par Tan et Triggs [33] comme solution au probleme de sensibilite qu’eprouve

le LBP face au bruit aleatoire et celui de quantification. Le principe est le suivant :

alors que les LBP appliquaient un seuil egal a la valeur du pixel central, la conversion en

Local Ternay Patterns (LTP) attribue a la valeur 0 aux pixels dont la valeur se trouve

dans un voisinage de la valeur du pixel central, 1 a ceux dont la valeur est au-dela de

ce voisinage et -1 a ceux dont la valeur est en dessous. La formulation mathematique

est la suivante pour u un pixel peripherique d’un entourage a convertir, ic la valeur du

pixel central et t le voisinage :

s(u, ic, t) =

1 si u ≥ ic + t

0 si |u− ic| < t

−1 si u ≤ ic − t

Comme fait pour l’operateur lbp basique, une illustration de l’operateur ltp basique

est faite a la figure 2.5.

Figure 2.5: Operateur LTP basique. [33].

22

Ensuite, ce code ternaire peut etre transforme soit en un nombre reel soit en code

binaire pour passer a la phase suivante. Dans le premier cas on pourrait utiliser un code

de valeurs 3n similaire au code binaire 2n. Tan et Triggs ont quant a eux divise le code

ternaire en deux codes binaires traites separement et rassembles ensuite lors de la phase

de comparaison. Cette methode a l’avantage de garder le systeme simple d’elimination

des patterns non-uniformes.

La methode de preparation de l’image

Celle-ci s’effectue en trois etapes :

1. Correction Gamma. L’idee de base est que comme l’image reflechie par un visage

est le produit de la lumiere qui l’atteint par la reflectance de la surface, une varia-

tion de la reflectance representant un trait discriminatif aura une influence relative

a l’illumination qu’elle subit, introduisant par la meme un biais. La solution pro-

posee est d’appliquer l’operateur logarithmique par lequel ce produit deviendra

une somme. Ainsi, pour une illumination locale uniforme, un saut de reflectance x

provoquera la meme incrementation sur l’image reflechie quelle que soit la valeur

de l’illumination de depart. Neanmoins, selon Tan et al., un logarithme a tendance

a trop amplifier le bruit dans les zones sombres. Pour cette raison, un exposant

γ compris dans l’intervalle [0, 0.5] est utilise a la place du logarithme. Ainsi la

premiere etape se decrit par la relation mathematique :

I ′(i, j) = I(i, j)γ

ou I(i, j) est l’intensite du pixel de coordonnees (i, j) de l’image d’entree et I ′

l’image issue de cette premiere etape de pretraitement.

2. Filtrage par difference de Gaussiennes. Il s’agit de l’implementation d’un passe

bande pour supprimer les basses frequences contenant les effets non desirables des

ombres et les hautes frequences contenant l’aliasing et le bruit.

3. Egalisation des contrastes. Celle-ci s’effectue en trois etapes sur la region delimitant

le visage.

I(x, y) ← I(x, y)

(mean(|I(x′, y′)|a))1/a

I(x, y) ← I(x, y)

(mean(min(τ, |I(x′, y′)|)a))1/a

I(x, y) ← τtanh(I(x, y)

τ)

23

ou τ est utilise dans l’etape deux pour tronquer les grandes valeurs, a est un

exposant inferieur a 1 reduisant l’effet des grandes valeurs. L’etape trois limite

l’espace de l’image a l’intervalle [−τ, τ ].

Effectuer cette methode sur une zone presentant plusieurs visages ne donnera

pas le meme resultat que l’application sur chacun des visages separement. Par

consequent, si une etape de masquage doit etre effectuee, il faut qu’elle le soit

avant cette etape d’egalisation des contrastes.

L’application de cette methode a un meme visage soumis a differentes conditions d’illumination

est illustre a la figure 2.6.

Figure 2.6: Illustration de l’application de la methode de correction d’illumination proposee

par Tan et Triggs. Figure tiree de [33].

La metrique utilisee pour comparer deux histogrammes

La mesure de distance proposee par Tan et Triggs prend intrinsequement compte de

l’organisation spatiale des LTP distribues sur l’entierete de l’image. Ici plus question

d’histogramme non plus. Soit deux images a comparer X et Y . Pour chaque LTP (aussi

nombreux que le nombre de pixels) de Y , la methode va regarder parmi les LTPs de

meme valeur de X celui qui est le plus proche et utiliser la distance qui les separe pour

incrementer proportionnellement la distance globale.

Concretement, pour chaque valeur k possible de LTP, une matrice binaire bkX representant

la distribution des patterns k dans X est creee. Ensuite, les matrices de distances dkX

sont compilees tel que l’element (i, j) de dkX represente la distance entre (i, j) et la posi-

tion du plus proche pixel de X dont la valeur est k. L’exemple d’une matrice bkX et de

sa matrice dkX associee est presente a la figure 2.7.

Finalement le calcul de la distance entre deux images X et Y se fait comme suit:

D(X, Y ) =∑

pixels(i,j)of Y

w(dkY (i,j)X (i, j))

ou w(d) est une fonction (a choisir) qui associe a une distance de pixel la penalite corre-

spondante. Tan et Triggs proposent la gaussienne1 w(d) = exp−(d/σ)2/2 et la troncation

1A noter que dans ce cas-ci un grand D(X,Y ) correspondra a deux images X et Y proches

24

Figure 2.7: A gauche : Exemple de matrice binaire de distribution des patterns. A droite :

Matrice de distances correspondante. Figure tiree de [33].

lineaire w(d) = min(d, τ) et disent que leurs performances sont similaires.

2.4 Le traitement de l’illumination

Les problemes lies aux variations d’illumination sont tres presents dans le domaine de la

reconnaissance et de la detection faciale. L’importance liee a ce domaine pour ameliorer

les performances des reconnaisseurs de visage se manifeste par le nombre d’articles sur

le sujet rien que pour les 5 premiers mois de 2010 [12, 6, 21, 40]. Un inventaire des

techniques existantes en deux categories actives et passives est fait par Zou dans [56].

Les techniques passives s’occupent de l’illumination a partir des donnees en niveaux de

gris ou en couleur recues par l’appareil de capture. De l’autre cote, les techniques actives

obtiennent des donnees supplementaires telles que la profondeur ou le profil infrarouge

pour arriver a leurs fins.

Plus recemment est parue une etude comparative des differentes techniques de preprocessing

dans le domaine de la reconnaissance basee sur les espaces de vecteurs propres [15], c’est

a dire les methodes holistiques ou de projections. Un point important de cette etude

est qu’elle rend compte de la simplicite de la methode, de sa rapidite et sa robustesse.

Il est par contre dommage que les comparaisons en termes de performances ne soient

faites que sur base de la reconnaissance par des methodes de projections. Neanmoins

Ruiz-del-Solar donne ainsi un bon apercu objectif des techniques existantes et de leurs

performances ainsi qu’un releve de leurs temps d’execution sur une meme machine pour

le meme boulot, ce qui peut s’averer tres utile pour le design d’application en temps

reel.

La methode qui ressort comme etant l’etat de l’art pour la reconnaissance par

methode de projection est la combinaison de SQI [41] et du LBP modifie [17]. Neanmoins

cette methode est surpassee en terme de performance par une methode contemporaine

a l’etude comparative : le pretraitement de Tan et Triggs [33] presentee plus haut.

25

Partie II

Application

26

Chapitre 3

Conception de l’application

Ce troisieme chapitre est consacre a la conception de l’application qui permettra a

Nao d’etablir des relations avec les personnes qui l’entourent. Tout d’abord, dans la

premiere section ’Mise en situation’, je preciserai l’enonce du probleme et identifierai les

limitations materielles qui guideront le developpement de l’application. Je consacrerai

ensuite la section 3.2 au probleme du temps reel en general et applique a l’application

de ce memoire. Puis, j’expliquerai le fonctionnement complet de l’application finale a la

section 3.3 ’Architecture prototype et cycle de fonctionnement standard’. Je terminerai

par apporter quelques pistes qui permettraient d’ameliorer les performances generales a

la section 3.4 et par conclure a la section 3.5.

3.1 Mise en situation

3.1.1 Definition de l’objectif et enumeration de ses consequences

L’objectif de l’application est de permettre a Nao de reconnaıtre les personnes qui

l’entourent, de memoriser sur demande l’identite d’un nouveau personnage et d’etablir

une relation avec quelqu’un en le suivant du regard. Un scenario type de l’utilisation

de ces capacites se deroule en deux phases. Premierement Nao fait la connaissance

d’un personnage (Paul), sauvegarde ses informations visuelles et les associe a un label.

La deuxieme phase se produit lorsque Paul revient voir Nao, ce dernier le reconnaıt et

tourne le visage vers lui en le saluant. Cette deuxieme phase est illustree a la figure 3.1

p.28.

Un tel comportement implique en consequence que Nao soit capable d’effectuer en

temps reel

1. la localisation de tous les visages dans son champ visuel,

27

Figure 3.1: Situation typique que Nao doit etre capable d’effectuer. Paul est un personnage

que Nao a rencontre auparavant. Lors d’une seconde rencontre, Paul rentre dans

le champ visuel de Nao et ce dernier le reconnaıt, se tourne vers lui et le salue

par son prenom.

2. la poursuite des visages d’une capture du champ visuel a l’autre,

3. la reconnaissance faciale,

4. une sauvegarde de nouveaux visages dans une base de donnees et

5. la construction de l’ordre de mouvement de la tete pour fixer une personne en

particulier.

3.1.2 Importance du temps reel et des performances

Cette application est une routine a la base de toute une serie d’applications d’interaction

homme-machine d’ordre superieur telles qu’une conversation ou la poursuite a travers

la foule d’une personne en particulier. Elle doit par consequent (1) utiliser un minimum

de ressources et (2) etre la plus robuste possible, un dysfonctionnement a cet etage se

propagerait de maniere desastreuse en aval. Si le robot presente ces deux caracteristique

de temps reel et de performance, on pourra dire qu’il s’integre dans son milieu de maniere

limpide, ce qui s’avere etre precieux pour toutes les applications potentielles. Prenons

l’exemple d’un systeme charge de transmettre des informations confidentielles a un trader

internationnal presse. Il sera malvenu que (1) le systeme transmette les informations a

la mauvaise personne ou (2) le systeme prenne 15 secondes pour reconnaıtre le trader.

28

La conception devra donc s’orienter des le debut vers des choix qui permettront au

systeme d’etre rapide et robuste. La tache sera d’autant plus ardue qu’il s’agit la de

deux elements antagonistes ou l’amelioration de l’un se fait souvent au detriment de

l’autre.

3.1.3 Materiel disponible et limitations

Figure 3.2: Materiel disponible pour l’application developpee dans le cadre de ce memoire.

Une unite de traitement embarquee sur Nao et une unite de traitement a distance

puissante communiquant entre-elles par wifi.

Le materiel disponible (voir fig. 3.2 p.29) est constitue de

• L’ordinateur Zosma AMD Athlon 64 X2 Dual 3800+ (2.01 GHz) 2 Go de RAM

(ressources distantes).

• Le robot Nao fourni par Aldebaran Robotics [1]. Ce dernier est equipe d’un pro-

cesseur AMD X86 GEODE 500MHz et de 256 Mo de SDRAM (ressources em-

barquees). Une camera est placee sur le haut de sa tete et fonctionne en trois modes

: 640x480, 320x240 et 180x120 pixels. Une transmission sans fil est disponible en-

tre Nao et l’ordinateur distant. Une seconde connection par fil est aussi disponible

mais s’oppose a l’idee d’autonomie du robot.

29

Avec fil Sans fil

Resolution N&B Couleur N&B Couleur

160×120 47 47 58 95

320×240 94 141 150 270

640×480 333 510 555 1000

Table 3.1: Releve en ms des temps de transmission avec et sans fil entre le robot Nao et

l’ordinateur distant pour differentes resolutions. La transmission d’images de

couleur implique le transfert de 3 chaınes de couleur.

Ce materiel a pour principaux defauts des ressources embarquees faibles et un temps

de transmission eleve comme le montre le releve des temps de transmission dans differentes

conditions a la table 3.1 p.30.

3.1.4 Le challenge

Le challenge a relever est donc de choisir l’architecture et les methodes pour obtenir le

meilleur compromis entre temps reel et performance en s’arrangeant avec des ressources

embarquees faibles et un temps de transmission eleve.

3.2 Gerer le probleme du temps reel

Des solutions au probleme du temps reel peuvent deja etre trouvees des la conception

de l’architecture ou il est possible de jouer sur la distribution des taches entre les deux

processeurs disponibles. Il sera donc question ici de choisir les lieux d’execution des

differentes etapes du traitement enumerees a la section 3.1.1 p.27 : la detection, la pour-

suite, la sauvegarde, la reconnaissance et la construction de l’ordre de mouvement. Mais

tout d’abord, deux concepts temporels importants, a savoir le temps de reaction et le

temps de rafraichissement, sont introduits a la section 3.2.1 et une liste des elements a

prendre en compte pour le choix des lieux d’execution des differentes etapes du traite-

ment est etablie a la section 3.2.2.

3.2.1 Difference entre temps de reaction et le temps de rafraichisse-

ment

Le temps de reaction est le temps entre l’occurence d’un stimulus au systeme et le debut

de l’execution de la reponse souhaitee. Le temps de rafraichissement s’apparente au

nombre d’images capturees par seconde ou le nombre d’images affichees par seconde

30

dans le cas ou il y a un ecran temoin. Bien que l’optimisation de l’un semble decouler

de l’optimisation de l’autre, ce n’est pas necessairement le cas.

Ainsi, en prenant l’application a developper pour ce memoire, les architectures po-

tentielles1 (A) et (B) presentees ci-dessous illustrent une situation ou l’augmentation du

nombre d’images par seconde (fps = frames per second) est synonyme de diminution de

temps de reaction, voir figure 3.3 p.31.

Figure 3.3: Illustration de deux situations pour lequelles la diminution du temps de

rafraıchissement n’est pas synonyme de diminution du temps de reaction du

systeme. Dans la situation A, l’entierete du traitement s’effectue sur Nao, don-

nant un temps de rafraıchissement egal au temps de reaction. Dans la situation

B, une partie du traitement se fait sur l’ordinateur distant, plus rapide. Bien que

cela ait permis de diminuer le temps de rafraıchissement, on voit que le temps

de reaction a quant a lui augmente par rapport a la situation A (L’hypothese est

faite que les deux plateformes sont multitaches, sachant a la fois traiter et trans-

mettre/recevoir. La relaxation de cette hypothese forcerait Nao a commencer la

capture de l’image 1 seulement a la fin de la transmission a l’ordinateur mais ne

remettrait pas en cause cette conclusion).

A Tout le traitement s’effectuent sur Nao, la detection des visages et la reconnais-

1Pour illustrer le concept, seules deux etapes de traitement sont considerees : la detection et la

reconnaissance des visages. Ceci est aussi valable pour la figure 3.3.

31

sance.

B Seule la detection s’effectue sur le processeur embarque, la reconnaissance se fait

sur l’ordinateur distant, plus rapide. Cela implique un temps de transmission.

Les temps de rafraıchissement et de temps de reaction sont donc deux concepts

differents et lorsque le temps de transmission entre les deux processeurs est significatif

l’optimisation de l’un peut conduire a la deterioration de l’autre.

3.2.2 Points importants pour choisir la distribution ideale des

taches

L’obtention de la distribution ideale des taches entre le processeur embarque et le pro-

cesseur distant se deroule en etant attentif a plusieurs points :

• La grandeur temporelle a minimiser: l’architecture ne sera pas la meme pour une

application aval demandant beaucoup d’informations en un minimum de temps

(temps de rafraıchissement faible) ou une application aval demandant un temps

de reaction faible. La premiere categorie correspond par exemple a une application

chargee de verifier l’identite du personnel d’entreprise a l’entree du batiment et

d’avertir de la presence d’un etranger. Pour ne pas alerter inutilement le garde,

l’application pourra augmenter sa robustesse en basant son jugement sur plus d’un

cliche. La deuxieme categorie comprend par exemple les applications d’interaction

de divertissement ou le ’lag’ est un phenoneme tres peu apprecie.

• Les ressources disponibles, pas uniquement les processeurs, la memoire RAM aussi.

• Le lieu de stockage de la base de donnees. En effet, pour chaque information la

base doit entierement etre parcourue et le transfert entre la base et le processeur

qui effectue la reconnaissance peut donner lieu a des temps d’acces significatifs.

• La quantite d’informations devant etre transmise sur l’ordinateur distant. Une

situation ou toute l’image doit etre transmise et une autre ou seulement les visages

sont demandes pourront conduire a des choix d’architecture differents.

La determination de la repartition ideale des taches a utiliser est donc influencee

par (1) les temps de transmission et de traitement sur les differentes plateformes, ceux-

ci dependant du materiel et (2) les objectifs de l’application en aval demandeuse du

systeme de reconnaissance, a savoir principalement la grandeur temporelle a minimiser

(temps de rafraıchissement ou temps de reaction) et les besoins en affichage.

32

3.2.3 Choix des lieux d’execution : l’architecture prototype

L’architecture developpee est un prototype ou tout se deroule sur l’ordinateur distant

(voir figure 3.4 p.33). Les raisons qui ont pousse a ce choix sont (1) les ressources limitees

de Nao (le processeur, l’espace disponible et la RAM), (2) l’absence d’application aval;

(3) la facilite de developpement car pour charger un nouveau programme sur Nao il faut

l’eteindre, ouvrir sa tete, retirer une cle USB, la flasher, la remettre en place et rallumer

Nao, operation pouvant prendre facilement 3 a 5 minutes; et (4) l’importance d’avoir un

affichage du champ visuel complet pour une application prototype de ce type.

Figure 3.4: Un cycle complet de l’application. Il commence par la capture de l’image sur Nao

et se poursuit par la transmission de l’image a l’ordinateur distant. Ensuite trois

etapes de traitement sont effectuees a l’issue desquelles un ordre de mouvement

est envoye par wifi a Nao.

3.3 Architecture prototype et cycle de fonctionnement

standard

L’application fonctionne par cycles qui commencent par la capture du champ de vision

de Nao et se termine par l’envoi ou non de l’ordre de mouvement de la tete de Nao vers

33

une personne en particulier. Un cycle standard n comprend trois stages2 de traitements

cites ci-dessous, decrits en detail a partir de la prochaine section et illustres a la figure

3.4 p.33.

• La detetion des visages. Il s’agit d’extraire les zones rectangulaires qui delimitent

les visages du cycle n contenus dans le champ de vision de Nao.

• La poursuite des visages qui est chargee de faire correspondre les visages du cycle

n a ceux du cycle n− 1. Cette poursuite permettra au stage de reconnaissance de

tenir un historique sur plusieurs cycles des identites attribuees a un meme visage.

• La reconnaissance des visages : les visages du cycles n sont compares avec ceux con-

tenus dans la base de donnees et les identites ponctuelles (uniquement basees sur

les informations du cycle n) sont deduites puis ajoutees a l’historique. L’identite

divulguee est le resultat d’un vote des identites ponctuelles de plusieurs cycles.

3.3.1 Detection des visages

Figure 3.5: La boıte de detection des visages. L’entree est une capture du champ visuel de

Nao tandis que la sortie comprend les visages extraits, leurs dimensions et leurs

positions dans l’image de depart.

La detection des visages recoit une capture du champ visuel de Nao et a pour but (1)

d’extraire les zones rectangulaires de l’image qui contiennent les visages et (2) de fournir

leurs dimensions et leurs positions. Cette localisation est effectuee par la librairie C++

OpenCV [2] qui fournit une implementation de l’algorithme de detection de Viola et

Jones [38] decrit a la section 1.1 p.6. La description de la boıte ’detection des visages’

est faite a la figure 3.5 p.34.

2Le mot ’stage’ est utilise ici comme synonyme du mot ’etape’ pour eviter toute confusion plus loin

dans le texte

34

OpenCV ( Open Source Computer Vision ) est une librairie initialement developpee

par Intel qui fournit plus de 500 algorithmes pour la vision par ordinateur en temps

reel. L’algorithme de Viola et Jones y est implemente et des apprentissages sont fournis.

Ainsi OpenCV peut deja localiser les visages, les yeux, les bouches ou d’autres parties

du corps.

3.3.2 La poursuite

Figure 3.6: La methode de poursuite utilisee. Le fonctionnement normal est presente a

gauche. Les trois situations suivantes correspondent a trois situations ou la

poursuite ne parvient pas a poursuivre correctement les visages d’un cycle a

l’autre

La poursuite doit etablir la correspondance entre les visages de deux cycles successifs.

La methode utilisee dans cette application consiste a appliquer la regle simple suivante :

”si le centre du visage dans la frame n est compris a l’interieur d’une zone definissant un

visage dans la frame n− 1, alors il s’agit de visages appartenant a la meme personne”.

L’execution normale de cette methode est illustree a la figure 3.6.

Les inconvenients et faiblesses de cette methode sont listes ci-dessous et les trois

premiers (a), (b) et (c) font aussi l’objet d’une illustration a la figure 3.6.

(a) Lorsque le temps de rafraıchissement est faible, les distances parcourues par les

centres des visages en mouvement peuvent depasser leur cadre de delimitation

provoquant ainsi l’echec de la poursuite.

(b) Lorsque deux candidats repreneurs sont presents (voir point (b) de la figure 3.6)

une indecision a lieu. Bien que l’algorithme n’associera pas deux fois la meme iden-

35

tite, le resultat de la poursuite dependra de l’ordre dans lequel les deux candidats

auront ete detectes durant le stage de detection et ne sera donc pas fiable.

(c) Lors du croisement de deux visages, il se peut que les identites soient inversees,

faussant ainsi tout resultat du vote ulterieur pour l’identification.

(d) Si le systeme de detection de visage manque le visage x lors du cycle n, le lien entre

le visage x du cycle n− 1 et du cyle n+ 1 ne sera pas etabli. Comme consequence

immediate la phase de vote de l’etape de reconnaissance ne pourra plus compter

que sur un seul exemplaire du visage x lors de l’identification du cycle n + 1. Le

meme probleme survient lorsqu’un visage quitte le champ visuel pendant un court

instant.

Pour eviter la majorite de ces inconvenients, une methode de poursuite alternative

basee sur la correspondance des couleurs entre visages de cycles successifs pourrait etre

utilisee. Il faudra alors etre attentif a sa sensibilite aux variations d’illumination.

Cette application utilise donc une methode de poursuite simple dont les faiblesses

ont ete repertoriees. Elle presente les avantages de sa simplicite, sa rapidite d’execution

et son fonctionnement sur n’importe quel type d’image (couleur, niveau de gris,etc.).

De plus, les performances qu’elle a su montrer lors de tests se sont averees suffisantes.

3.3.3 Reconnaissance des visages

Ce stage recoit en entree un visage candidat et trouve son identite si il est deja enregistre

dans la base de donnees. Dans le cas contraire, c’est l’identite de l’element le plus proche

de la base de donnees qui est renvoyee. Ce traitement de l’information se fait en plusieurs

phases decrites ci-dessous et illustrees a la figure 3.7 p.37 :

1. Le traitement de l’illumination. En conditions reelles, l’eclairage peut varier

et causer une degradation des performances de reconnaissance. Cette phase de

preparation de l’image prend ce probleme en charge.

2. La conversion LBP. L’image est decrite en termes de ’Local binary patterns’ intro-

duits a la section 2.3 p.19. L’interpretation de cette description en termes d’aretes

et de coins sera donnee a la section 3.3.3 p.38.

3. La division en sous-regions. Il s’agit d’une phase cle qui a fait l’objet d’une

parametrisation complexe decrite a la section 4.3 p.47. En separant l’image en

plusieurs petites images traitees separement, cette phase permet de tenir compte

d’informations spatiales precieuses pour la classification.

36

Figure 3.7: Illustration du stage de reconnaissance. L’entree est un visage dans sa zone

rectangulaire de delimitation. Il subit d’abord un traitement d’illumination avant

d’etre converti au format LBP. Il est ensuite divise en sous-regions qui seront

traitees separement durant le reste du processus. Un histogramme par region

est calcule et ensuite compare avec ses homologues chez chacun des elements de

la base de donnees pour obtenir l’identite ponctuelle. Un vote sur l’historique a

enfin lieu pour determiner l’identite divulguee. L’ajout de l’identite ponctuelle a

l’historique n’a pas ete dessinee pour simplifier la lecture du schema.

4. La construction des histogrammes pour chaque sous-region. Ensemble ils forment

un set d’histogrammes associe au candidat.

5. La comparaison avec les elements de la base de donnees. Le set d’histogrammes du

candidat est compare avec tous les personnages de la base de donnee qui eux aussi

possedent leur propre set d’histogrammes. Le membre le plus proche est ensuite

selectionne comme identite ponctuelle du candidat et ajoute a un historique.

6. Enfin, l’identite divulguee est obtenue par le vote sur plusieurs cycles, rendu pos-

37

sible par le stage de poursuite et la tenue de l’historique.

Le traitement de l’illumination

Cette phase du stage de reconnaissance emploie la methode utilisee par Tan et al. [33]

et qui est presentee a la section 2.3.1.

La conversion en ’local binary Patterns’

Cette phase de conversion recoit en entree une image decrite en niveaux de gris et rend

une image decrite en ’local binary patterns’. La description theorique de cette technique

a ete presentee a la section 2.3 p.19 et fait l’objet dans cette section d’une interpretation

en termes de coins et aretes (voir figure 3.8 p.39).

Pour rappel, la conversion basique d’un pixel en un ’local binary pattern’ se fait en

deux etapes a partir des relations ’plus petit’ ’plus grand’ qu’entretient sa valeur et avec

celles des 8 pixels peripheriques qui l’entourent. Tout d’abord l’association d’un label

binaire a chacun des pixels peripheriques est faite en leur associant le label ’1’ si leur

valeur est superieure a celle du pixel a convertir et le label ’0’ dans le cas contraire.

Ensuite, les huits labels sont lus dans le sens des aiguilles d’une montre pour former un

nombre binaire appele ’local binary pattern’ (lbp). L’endroit ou commence la lecture

n’a pas d’importance et a ete choisi comme etant le pixel peripherique situe au dessus

du pixel a convertir.

Finalement, seuls les lbp ’uniformes’ sont conserves pour la construction de l’image

convertie. Un lbp est qualifie d’uniforme lorsque la lecture cyclique de ses labels com-

prend moins de trois transitions 0-1 ou 1-0. Ainsi 11000011 et 00100010 sont respective-

ment uniforme et non-uniforme.

L’interpretation des lbp est faite sur base de l’emplacement des transitions 0-1 1-0

dans le nombre binaire. Ainsi les nombres binaires 11000001, 01110000 et 01000000

correspondent respectivement a une arete verticale, une arete horizontale et un coin

inferieur gauche. Plusieurs exemples de ce type sont presentes a la figure 3.8.

La description lbp decrit donc les contours des objets presents dans l’image et dans

le cas de la reconnaissance faciale cela peut etre interprete comme une description des

silhouettes des elements cles du visage tel que le nez ou la bouche.

38

Figure 3.8: Interpretation de la description en ’local binary patterns’. L’image a convertir en

LBP est ici le trapeze. Les arrangements de 8 pixels en carres correspondent cha-

cun aux pixels peripheriques d’un pixel a convertir. Lorsqu’un pixel peripherique

est associe au label ’1’ il est colorie en gris et dans le cas contraire en bleu. En

commencant en haut a gauche et en continuant dans le sens des aiguilles d’une

montre, les conversions LBP des arrangements representes donnent respective-

ment 16, 12, 14 et 112.

La division en sous-regions et la contruction des histogrammes

Cette phase incarne l’utilisation d’informations spatiales dans le stage de reconnaissance

en decoupant l’image en sous-regions qui seront traitees et comparees separement. Les

tailles et les positions des sous-regions ont fait l’objet d’une optimisation presentee a la

section 4.3 p.47.

Des histogrammes sont ensuite construits pour chacune des sous-regions et rassembles

dans un set d’histogrammes associe au visage a reconnaıtre. Ce rassemblement en set

d’histogrammes est le format sous lequel les personnages connus de Nao sont stockes

dans la base de donnees.

L’antagonisme de ces deux operations, la division en sous-regions et la construction

des histogrammes, merite d’etre souligne et est explique ci-dessous.

Dans l’evolution du contenu informatif tout au long du traitement, l’operation de

mettre les donnees sous forme d’un histogramme efface toute information concernant la

distribution geographique des elements au sein de l’image. Cette operation permet donc

de diminuer la sensibilite de la reconnaissance face aux deformations rigides locales ou

globales que peut subir une personne entre deux cliches mais interdit aussi a toute etape

ulterieure d’appliquer un traitement different a des regions dont le contenu discriminatif

39

serait different, telles qu’une region a contours marques et une region de peau continue3.

La division en sous-regions en amont agit dans le sens contraire de la generation des

histogrammes car elle permet de differencier le traitement de regions en fonction de leur

emplacement dans la fenetre de delimination du visage.

La divisions en sous-regions et la generation des histogrammes peut donc etre in-

terpretee comme deux processus qui permettent ensemble de moduler la quantite d’informations

spatiales qui sera prise en compte lors de la classification.

La comparaison avec les elements de la base de donnees

Cette phase recoit en entree le set d’histogrammes du candidat assembles lors de la

phase precedente et determine quel set d’histogrammes de la base de donnees lui est

le plus proche. La proximite de deux sets est donnee par la distance qui les separent.

Celle-ci est une combinaison lineaire des distances entre leurs histogrammes homologues.

Ainsi pour deux histogrammes de la premiere sous-region ~H1 = (H11 , H

21 , ..., H

n1 ), ~H2 =

(H12 , H

22 , ..., H

n2 ) et H i

x la valeur du bin i de l’histogramme Hx, la distance qui les separe

est

D1( ~H1, ~H2) =|| ~H1 − ~H2|||| ~H1|| · || ~H2||

(3.1)

La similarite entre deux visages est donc mesuree par la combinaison lineaire des

distances qui separent leurs histogrammes homologues. Les coefficients de cette combi-

naison ont fait l’objet d’une optimisation presentee a la section 4.3.

Le vote

Cette phase utilise les multiples exemplaires4 du visage a reconnaitre pour voter l’identite

divulguee. Celle-ci est obtenue en moyennant les rangs de proximite des elements de la

base de donneess avec les exemplaires.

3Vu l’utilisation des lbp, un simple changement du sens d’un degrade provoque par une source lu-

mineuse sur une zone de peau plane pourra provoquer la generation de deux histogrammes completement

differents4Ces multiples exemplaires sont les occurences du visages a reconnaıtre dans les cycles precedents

40

3.4 Pistes pour ameliorer les performances

3.4.1 Nouvelles informations spatiales

Les informations spatiales sont actuellement integrees a la classification lors de la division

en sous-regions et elle concerne la distribution des donnees discriminatives parmis les

sous-regions. Il m’est venu l’idee d’ajouter a cela des informations spatiales contenues a

l’interieur des sous-regions.

Cette capture d’informations spatiales contenues dans une sous-region se deroule en

deux etapes. Tout d’abord les centres de gravite de chaque valeur de lbp sont calcules

et ensuite les distances qui separent certains d’entre-eux sont ajoutees a l’histogramme

selon facteur a parametrer.

Les paires de lbp dont la distance des centres de gravite est evaluee sont selectionnes

tels qu’elles puissent effectivement representer une caracteristique discriminative du vis-

age. Ainsi, pour une sous regions englobant les sourcils, il est possible de mesurer la

distances qui les separent tel qu’illustre a la figure 3.9.

Figure 3.9: La distance entre les centres de gravite de lbp au sein d’une sous-region peut

representer une distance physionomique. Ici deux sourcils sont representes en

orange pale et les deux lignes rouges representent des patterns identiques avec

leurs centres de gravite indiques par un point noir.

Des exemplaires de paire de lbp dont l’espacement des centres de gravite peut

representer une distance discriminative sont presente a la figure 3.10. Ne font pas partie

de ces paires les lbp representant les aretes verticales ou horizontales car leur espacement

correspond a l’epaisseur d’un trait, ne fournissant pas d’informations discriminatives.

J’ai donc montre ici comment extraire des lbps des informations spatiales d’une autre

maniere que par la division en sous-regions et propose l’utilisation de cette methode pour

ameliorer les performances des systemes de reconnaissance faciale.

41

Figure 3.10: Set de quatre paires dont l’espacement des centres de gravite peut aider a la

reconnaissance faciale en donnant des informations quant a l’organisation spa-

tiale a l’interieur d’une sous-region. Ces paires sont toutes issues d’une symetrie

axiale. La premiere paire illustree est constituee des lbp 224 et 131.

3.4.2 Collaboration des systeme de reconnaissance et de pour-

suite

La poursuite et la reconnaissance ont le point de commum d’associer un visage a un

autre issu d’une autre frame ou d’une base de donnees. Cet objectif commum permet

d’envisager une collaboration entre les deux techniques.

Actuellement, la poursuite aide deja la reconnaissance en lui permettant d’avoir acces

a plusieurs exemplaires du visage a identifier et en augmentant ainsi sa robustesse. C’est

deja un premier pas vers la collaboration mais il est possible de faire plus.

Tout d’abord en rendant inutile la reconnaissance dans les situations ou la poursuite

est capable d’affirmer avec certitude qu’un visage est le meme que celui d’un autre cycle

deja identifie. Ce type d’entraide a deux benefices : celui de diminuer le temps de

traitement et celui d’offrir un support au systeme de reconnaissance lorsque sa tache est

rendue difficile par une occlusion partielle ou une deformation du visage. Ainsi le facheux

probleme du cri qui survient quand la personne a reconnaıtre crie est esquive lorsque le

systeme de reconnaissance a la possibilite de faire appel au systeme de poursuite.

Ensuite en donnant la possibilite au systeme de poursuite de faire appel au systeme

de reconnaissance pour retrouver la trace d’un visage disparu apres une occlusion totale.

La mise en place d’une collaboration entre les systemes de reconnaissance et de pour-

suite demanderait donc a ces deux systemes de pouvoir fournir un degre de certitude

quant a leurs resultats et dans le meme temps permettrait d’ameliorer d’une part la

robustesse des deux techniques face a des situations difficilles et d’autre part le nombre

moyen d’images traitees par intervalle de temps.

42

3.5 Conclusion

La conception de l’application en tenant compte des contraintes materielles et de l’exigence

d’une execution en temps reel est maintenant terminee. Elle a sollicite une reflexion sur

les concepts de temps de rafraıchissement et de temps reaction et a finalement abouti a

l’organisation presentee ci-dessous.

La capture du champ de vision de Nao est directement envoyee par wifi a un or-

dinateur puissant charge, en fonction de la personne avec qui etablir un contact, de

commander un mouvement de tete qui centrera le visage de l’interlocuteur au centre du

champ de vision de Nao. La station distante effectue pour cela deux stages majeurs5

de traitement: une localisation des visages dans le champ de vision de Nao et une re-

connaissance faciale pour chacun d’eux6. La detection utilise le fameux algorithme de

localisation en temps reel de Viola et Jones et la reconnaissance est basee principalement

sur une division de l’image en sous-regions suivie de la generation pour chacune d’elles

d’histogrammes de ’local binary patterns’.

Les interpretations de deux phases importantes du stage de reconnaissance ont ete

faites: celle de la conversion en ’local binary patterns’ comme description en termes

d’aretes et de coins, et celle de la division en sous-regions suivie de la generation

d’histogrammes comme moyen de modulation de la quantite d’informations spatiales

prise en compte lors de la classification.

D’autre part, deux ameliorations ont ete proposees: une concernant la prise en

compte d’informations spatiales au sein des sous-regions et l’autre concernant la col-

laboration des systemes de reconnaissance et de poursuite de visages a travers plusieurs

champs visuels successifs.

Apres cette conception, la parametrisation qui doit necessairement avoir lieu est faite

au chapitre suivant et determinera premierement la taille des fenetres de delimitation

qui seront utilisees et deuxiemement la maniere de diviser l’image en sous-regions pour

obtenir le meilleur taux de bonnes classifications.

5Pour rappel, c’est ainsi que les macro etapes de traitement sont nommees pour eviter la confusion

avec des etapes de traitement d’ordre inferieur6Si la personne avec qui etablir un contact est connue d’avance, une verification d’identite aurait

suffi. La reconnaissance est ici utilisee pour donner a Nao la conscience permanente de l’identite des gens

qui l’entourent et ainsi lui permettre d’ajuster son comportement en fonction des personnes presentes

ou non. Cela permet aussi de rester dans un cas general et d’offrir un maximum d’informations a tout

logiciel d’ordre superieur telle que pourrait constituer une application chargee de rendre un accueil

personnalise a l’entree d’une institution

43

Chapitre 4

Entraınement sous MatLab du stage

de reconnaissance

Ce chapitre est destine a parametrer l’application pensee au chapitre precedent. Pour

cela, le stage de reconnaissance de visage a ete entierement implemente a l’aide du

Logiciel Matlab.

Les elements a parametrer sont:

1. La taille de fenetre qui sera utilisee. Tous les visages d’entree, qu’ils soient destines

a la sauvegarde dans la base de donnees ou a l’identification, devront presenter

les memes dimensions. En effet, la reconnaissance est basee sur la generation

d’histogrammes de ’local binary patterns’ (lbp) et par consequent l’utilisation

de visages de resolutions differentes poserait deux problemes : celui des lbp qui

detectent la presence d’aretes et coins pour des environnements de 9 pixels quelque

soit la resolution de l’image et celui des histogrammes qui, s’ils sont generes sur

des regions de tailles differentes, ne pourront pas etre compares. La solution la

plus simple est de redimensionner l’image des le debut. La principale critique a

l’encontre de cette solution est que l’interpolation qui devra necessairement avoir

lieu degrade la qualite de l’information contenue dans l’image originale.

2. Les dimensions, les positions et les poids des sous-regions utilisees pour la re-

connaissance. Pour rappel, l’application comprend une phase de decoupage de

l’image en sous-regions traitees separement pour apporter des informations con-

cernant l’organisation spatiale a la classification. Cette methode, comme cela sera

vu au chapitre 6, augmente de maniere significative les resultats et merite donc de

s’y attarder.

Ce chapitre decrit la parametrisation de ces elements aux sections 4.2 et 4.3. Une

conclusion a la section 4.4 p.51 reprend les elements a retenir et donne un avis critique

44

accompagne des elements qui conduiront au chapitre 5.

Avant de commencer la parametrisation, les ensembles d’entraınement et de validation

qui seront utilises sont introduits a la section 4.1.

4.1 Ensembles d’entraınement, de validation et bases

de visages

Figure 4.1: Methode de detection de Viola et Jones implementee par OpenCV appliquee a un

echantillon de la base de donnees FERRET gray. Cette extraction qui forme les

ensembles d’apprentissage et de validation pour l’application de parametrisation

en Matlab a ete effectuee avec le meme code c++ que celui qui est utilise pour

l’application avec Nao.

Le contenu des ensembles d’entraınement et de validation se veut le plus proche pos-

sible des visages auxquels le stage de reconnaissance aura affaire. Par consequent leurs

cadrages dans leurs fenetres de delimitation seront faits en utilisant l’implementation

OpenCV de l’algorithme de Viola et Jones [38] tel que c’est le cas pour les visages

detectes dans le champ visuel de nao. Les images d’entrees sont issues de la base de

donnees FERRET gray [27, 28](voir figure 4.1 pour un echantillon cadre avec OpenCV).

L’ensemble d’apprentissage compte 60 visages differents et celui de validation compte

100 prises de vue des 60 personnes de l’ensemble d’apprentissage. Un test standard

comprend l’apprentissage des 60 visages differents suivi du calcul du taux de bonnes

classifications sur l’ensemble de validation.

45

La base de donnees FERRET est largement utilisee a travers la litterature pour

mesurer les performances d’un classifieur [4, 47, 6, 16] et n’est pas disponible en telechargement

libre. J’ai pu la telecharger entierement apres avoir suivi les procedures qui sont de-

mandees sur le site web du projet [3].

4.2 Taille de fenetre utilisee

Pour determiner la taille de fenetre a utiliser, plusieurs dimensions d’image ont ete

testees sur l’ensemble de validation. Le graphe de la figure 4.2 reprend les resultats qui

montrent qu’il existe un intervalle de taille de fenetre d’entree pour lequel la methode

de classification est plus performante. Je n’ai pas pu tester l’utilisation de taille d’image

d’entree superieure a 105 pixels de cote car je n’avais pas assez de memoire virtuelle

pour effectuer les calculs.

Figure 4.2: Taux de bonnes classifications obtenus pour differentes longueurs de cote d’image

d’entree. Des petites longueurs donnent de mauvais resultats car elle ne capturent

pas beaucoup d’informations. Bien qu’il m’ait ete impossible de tester pour

des tailles d’images d’entree plus grande, le graphe laisse paraıtre qu’une fois

passe une certaine dimension le taux de bonnes classifications par rapport a la

taille de l’image d’entree diminue. La raison serait qu’a partir d’une certaine

dimension, l’information capturee par les lbps devient moins discriminative car

elle est relative a un environnement de 8 pixels autour de chaque pixel et est

donc invariable aux dimensions de l’image.

46

Au vu de ces resultats, j’ai choisi une taille de 60 pixels de cote. Ce choix est aussi

motive par le fait que la resolution de l’image d’entree capturee du champ de vision

de Nao sera d’une resolution faible (320 × 240 ou 160 × 120 pixels) pour minimiser les

temps de transmission a la station distante et que par consequent les visages extraits

par la methode de detection ne seront pas de dimensions tres elevees a moins que les

personnes ne se tiennent juste en face de la camera, situation impossible a garantir.

Donc un choix d’image d’entree de 60 pixels de cote a ete fait en tenant compte de

la resolution des images qui seront effectivement apportees par la camera de Nao et de

la taille d’image d’entree qui semble permettre aux ’local binary patterns’ de capter le

plus d’informations discriminatives.

4.3 Selection de la combinaison de sous-regions pour

la reconnaissance faciale

L’objectif de cette parametrisation est de trouver la combinaison de sous-regions qui

permettra de distinguer au mieux les personnages. Pour rappel, le stage de reconnais-

sance divise le visage en plusieurs sous-regions traitees separement pour tenir compte de

la distribution geographique des zones utiles a la discrimination lors de la classification.

L’identification de la difficulte de cette parametrisation et la precision de l’objectif

en consequence sont d’abord faits a la section 4.3.1, puis la strategie et la combinaison

finalement selectionnee sont repris a la section 4.3.2. Enfin, une conclusion comprenant

une critique de la strategie adoptee et des pistes pour la suite est faite a la section 4.4.

4.3.1 Difficulte et objectif

La majeure difficulte de ce probleme est de selectionner la meilleure combinaison de x

sous-regions parmi le nombre titanesque qu’il est possible de trouver. Ainsi il y a deja

6.2597× 1018 manieres differentes de prendre x = 3 sous-regions parmi les n = 3348900

que compte une fenetre de 60 pixels de cote1 :

n!

(n− x)!x!=

3348900!

(3348897)!3!

= 6.2597× 1018

L’objectif de cette section sera donc de developper et d’executer une strategie efficace

qui permettra de trouver une combinaison performante sans devoir utiliser d’ordinateur

quantique.

1Ce nombre a ete obtenu par Matlab en tentant de toute les generer.

47

4.3.2 Strategie et resultats

La strategie est globalement de faire une pre-selection parmi les 3348900 sous-regions

rectangulaires que contient une fenetre de 60 pixels de cote pour que le nombre de

combinaisons possibles devienne accessible. Il sera possible de toutes les essayer pour

trouver la meilleure. Pour obtenir cette pre-selection, il faut tout d’abord trouver le

moyen de les comparer entre elles.

Une technique simple serait de comparer les resultats que chacune des sous-regions

parvient a atteindre sur l’ensemble de validation2. Neanmoins, l’application directe de

cette technique pose plusieurs problemes :

• Les premieres zones selectionnees sont de grande dimension et correspondent en fait

a un simple recadrage du visage (voir fig 4.3). Or il est recherche des zones de taille

moyenne couvrant plusieurs parties differentes pour rendre compte l’organisation

spatiale des donnees discriminantes.

(a) Meilleur score (b) Score en fonction de la surface

Figure 4.3: (a) La plus petite des sous-regions offrant le meilleur score de 67%. (b) Score

des sous-regions en fonction de leur surface.

Une idee pour passer au-dela de ce probleme serait de penaliser le score obtenu

par les zones de grande taille, mais determiner de quelle maniere effectuer cette

penalisation n’est pas evident. Normaliser les scores par la surface ne donne pas

2La methode de test d’une sous-region consiste a ne considerer que les pixels qu’elle inclue pour

effectuer la reconnaissance

48

de bons resultats et ne fait que retourner le probleme en privilegiant de maniere

excessive les sous-fenetres de petite taille.

• Cette technique considere que la force d’une combinaison de sous-regions se trouve

dans les performances individuelles de ses membres, or la richesse de leur combi-

naison est aussi recherchee: si une zone contient les trois quarts de l’information et

une autre un quart, il est aussi important de selectionner au moins une sous-region

issue de chaque zone que de selectionner la meilleure sous-region de chaque zone.

L’idee apportee pour resoudre ces deux problemes est de n’effectuer la comparaison

des resultats que sur des sous-regions de dimensions identiques et de constituer la

preselection avec les premiers classes de chaque categorie. Bien qu’il soit evident que

cette idee resolve le premier probleme, il est moins manifeste que ce procede selectionne

des sous-regions d’horizons differents.

Pourtant c’est bien le cas. Comme montre dans la figure 4.4 p.49, des zones cles du

visages telles que le nez et les yeux semblent etre contenues dans des rectangles de dimen-

sions differentes assurant ainsi que chacune d’elle a la chance d’etre classee premiere dans

une categorie differente et que les sous-regions preselectionnees proviendront d’endroits

differents de du visage. En complement, les classements au sein de quatre categories de

sous-regions de dimensions differentes sont presentes a la figure 4.5.

Figure 4.4: Trois zones classees premieres dans leurs categories. Elles correpondent aux deux

yeux et le nez. Il est montre ainsi que la methode de preselection ne selectionne

pas que des sous-regions provenant du meme endroit

A ce stade, la preselection des sous-regions classees premieres dans leurs categories

permet de reduire le nombre de sous-regions a combiner de 99.89% en passant de 3348900

a 3540 (=60 largeurs possibles × 60 hauteurs possibles - 60 repetitions que constituent

les carres). Neanmoins le nombre de possibilites de combiner trois d’entre elles reste

49

Figure 4.5: Classements au sein des categories de sous-regions de dimensions 60× 9, 60× 3,

18×9 et 12×24 pixels2. Les zones rouges fonces sont les plus discriminatives sur

l’ensemble de validation tandis que les zones bleues sont les moins discriminatives.

eleve (8.0315e+ 009) et le test de chacune de ces combinaisons prendrait 38 ans et une

septantaine de jours 3.

Figure 4.6: Resultat de la parametrisation des sous-regions traitees separement durant la

reconnaissance. Les zones 1 et 2 ont un poids de 5 tandis que les deux autres ont

un poids de 1.

Ont alors ete mises sur le cote les sous-regions dont la surface n’etait ni comprise entre

280 et 420, ni entre 1600 et 1700. Il s’est avere apres quelques tests que cette preselection

3Temps obtenu a partir du temps moyen necessaire au test d’une seule combinaison selon plusieurs

combinaisons de poids

50

semblait mener aux meilleurs resultats. Avec ce critere et en prenant seulement les

premieres sous-regions de chaque categorie, 47 sous-regions ont ete preselectionnee. En-

suite les 178365 moyens de prendre 4 de ses 47 sous-regions ont ete testes sur l’ensemble

de validation pour 455 configurations de poids differentes4. Cela fait un total de 81 156

075 configurations. Le resultat est donne a la figure 4.6

Plusieurs remarques sont a faire a la decouverte de ce resultat. Tout d’abord la

presence de deux grandes sous-regions (1 et 2) englobant plusieurs elements cles du

visage tels que les yeux, le nez et la bouche. Une seule d’entre elles obtient sur l’ensemble

de validation un taux de bonnes classifications avoisinnant les 67% tandis que leur

combinaison avec les trois autres sous-regions permet une diminution de 45% de l’erreur,

soit un taux de bonnes classifications obtenu de 82%5. Ensuite les poids tres faibles

accordes aux deux sous-regions de dimensions moyennes 3 et 4. L’algorithme avait la

possibilite de leur attribuer un poid nul, le fait qu’il ne l’ait pas fait semble indiquer

que dans une combinaison, les sous-regions de petites dimensions permettent par des

petites influences de mener le reconnaisseur de visage a la bonne decision. Enfin, le

positionnement exclusivement sur la partie gauche du visage des zones 3 et 4. Une

hypothese quant a ce phenomene serait la symetrie du visage diminuant l’interet d’une

sous-region du visage lorsque son homologue symetrique est deja considere.

4.4 Conclusion et suite

Le premier objectif de ce chapitre etait de trouver les dimensions de l’image d’entree

telles que le logiciel de reconnaissance fonctionnant sur Nao puisse atteindre les meilleurs

resultats. Il a ete decide d’utiliser des images d’entree de 60 pixels de cote car cela per-

mettait (1) aux modeles binaires locaux de tirer un maximum d’informations discrimi-

natives et (2) de rester proche des dimensions d’images d’entree qui seront typiquement

rencontrees par Nao en conditions reelles.

Le deuxieme objectif etait de trouver la combinaison de sous-regions qui permet

d’obtenir le meilleur taux de bonnes classifications. La principale difficulte rencontree

est le nombre colossal de combinaisons possibles parmi l’ensemble des sous-regions :

4Nombre de facon differentes d’attribuer 4 poids compris entre 0 et 12 dont la somme vaut 125Ceci est une premiere estimation de l’amelioration que peut apporter l’utilisation de la combinaison

de sous-regions. Le veritable potentiel de cette methode sera revele au chapitre 6 lors de l’utilisation

de la combinaison sur un ensemble de test. Ahonen et al. [4] avaient deja mentionne l’importance de

la division en sous-regions mais n’en avait implemente qu’une version simplifiee ne supportant pas la

superposition des sous-regions

51

pour une fenetre de 60 × 60 pixels2 il y a deja 6.2597 × 1018 possibilites differentes de

prendre 3 sous-regions.

Pour enjamber cette difficulte, une methode a ete developpee pour eliminer un max-

imum des sous-regions qui, combinees avec les autres, ne permettraient pas d’obtenir

un bon taux de bonnes classifications. Cette methode consiste a preselectionner un

representant de chaque categorie de dimensions de sous-regions et a ecarter les autres.

Apres s’etre assure que cela permettait de compter dans la preselection des sous-regions

de localisations variees contenant differents elements cles du visage, la technique a ete

adoptee.

Le resultat donne par cette methode de preselection comptait encore un nombre

eleve de sous-regions. Par consequent, une seconde epuration selon un critere de surface

a ete effectuee pour conduire finalement a un nombre de 47 sous-regions preselectionnees.

Ensuite, les 81 156 075 possibilites de prendre 4 sous-regions parmi ces 47 sous-regions

’d’elite’ selon differentes distributions de poids ont ete testees sur l’ensemble de vali-

dation. La combinaison qui ressort premiere de cette optimisation est presentee a la

figure 4.6 et a permis, sur l’ensemble de validation, de diminuer de 45% le pourcentage

d’erreur. Le veritable potentiel cette combinaison sera vu au chapitre 6 sur un ensemble

de test.

Apres ce chapitre, la meilleure combinaison est constituee de petites sous-regions

imbriquees dans des sous-regions de plus grande taille, englobant la totalite des elements

cles du visage tels que les yeux, la bouche et le nez. Ce resultat est probablement

influence par le nombre de sous-regions considerees fixe a quatre. L’etape suivante du

developpement serait de voir, avec un ordinateur le permettant, si ces sous-regions de

grande taille sont toujours presentes pour une combinaison d’un nombre plus eleve.

Les plus petites sous-regions se repartissent sur un seul cote du visage, phenomene

qui serait du a la symetrie du visage qui rend inutile la connaissance d’une sous-region

si son homologue symetrique est deja connu. Ce dernier resultat devrait faire l’objet de

plus d’etude avant de pouvoir etre generalise.

Dans le cas d’un nombre fixe de 4 sous-regions combinees, il est remarque que les

sous-regions de petites dimensions centrees sur des elements cles du visage semblent aider

le reconnaisseur de visage a se diriger vers la bonne decision par de petites influences

tandis que des sous-regions de grandes dimensions indiquent la direction generale.

La technique de preselection a comme principaux defauts de (1) ne selectionner au

maximum qu’une sous-region par categorie de dimensions et (2) de ne pas garantir par

son fonctionnement intrinseque une preselection comptant des sous-regions de toutes les

52

zones supposees cles du visage telles que les yeux, le nez, la bouche et les oreilles. Une

amelioration de la methode proposee consisterait alors a diviser l’image en plusieurs

’macro sous-regions’ au sein desquelles des classements entre sous-regions de meme sur-

face serait effectues. Ensuite chaque macro sous-regions apporterait ses sous-regions

d’elite a la preselection.

Parallelement a la recherche de la meilleure combinaison rendue difficile par le nombre

eleve de combinaisons possibles, une recherche des zones les plus utiles a la discrimination

peut etre menee pour tenter d’apporter des indices quant aux zones a explorer en priorite

lors de la preselection. Cela augmenterait le potentiel discriminatif de la preselection

et ainsi les performances de la meilleure combinaison de sous-regions qui en sera tiree.

Une tentative de generation d’une telle carte des zones les plus utiles a discrimination

est faite au chapitre suivant.

53

Chapitre 5

Obtenir une carte des zones utiles a

la discrimination

L’objectif de ce chapitre est d’etablir une carte du visage indiquant les zones les plus

utiles a la discrimination. L’elaboration de la strategie pour y parvenir n’a pas ete aussi

simple qu’attendu et je reprends ici les etapes de mon raisonnement qui ont mene a la

strategie finalement proposee de la section 5.5 p.63.

Une conclusion a la page 65 reprend les resultats et les points importants du developpement

de la strategie de generation de la carte des zones les plus utiles a la discrimination et

apporte un avis critique.

5.1 Contexte et motivations

Le developpement de cette strategie s’est fait en meme temps que celui de la strategie

de preselections des sous-regions pour la recherche de la meilleure combinaison capable

de discriminer les visages (voir chapitre 4 p.44).

La principale motivation vient de la difficulte de comparer des sous-regions de di-

mensions differentes entre elles, comme constate au chapitre precedent. Apres la con-

struction d’une carte des zones les plus utiles a la discrimination, il est espere que, par

sa consultation, la selection des sous-regions pour construire la meilleure combinaison

sera facilitee.

Cette chapitre presente en plus du precedent les problemes qui se sont presentes

lors du developpement des deux strategies, le raisonnement complet pour les contourner

et des precisions quant a l’obtention des graphes de la figure 4.5 p.50. Les sections 5.2

jusqu’a 5.4 comprise retracent dans l’ordre chronologique les etapes de mon raisonnement

et de mes experimentations qui m’ont menes a la solution finalement presentee a la

section 5.5 p.63.

54

5.2 Division en parties contigues

Une premiere facon de proceder pour obtenir la carte des zones les plus utiles a la

discrimination est de la diviser en plusieurs parties contigues et de tester chacune d’entre

elles sur l’ensemble de validation. La taille des sous-regions devra etre choisie ni trop

grande ni trop petite. En effet, une taille trop grande donnerait une faible resolution a

la carte finale tandis qu’une taille trop petite soumettrait les resultats aux consequences

nefastes d’un positionnement irregulier du visage ou de parties du visage par rapport a

la fenetre de delimitation. Cet effet est explique et illustre a la figure 5.1.

Figure 5.1: Effets du positionnement irregulier du visage ou de parties de visage par rapport

a la fenetre de delimitation pour deux tailles de sous-regions differentes. La ligne

du haut presente la robustesse d’une grande fenetre tandis que la seconde montre

l’incapacite de la petite sous-region a garder son contenu discriminatif lorsque

sa position par rapport a l’oeil change. Ces variations de positions peuvent etre

provoquees par le stage de detection qui ne cadre pas toujours les visages de la

meme facon, par des variations d’inclinaison du visage, par des variations d’angle

de prise de vue ou encore par des variations liees a l’expression du visage.

Finalement, comme le montre la figure 5.2, il n’aura pas ete possible de trouver

un compromis satisfaisant entre les effets nefastes de la grande taille sur la resolution

et la sensibilite problematique des petites sous-regions au positionnement irregulier du

visage ou de parties de visages qui peut etre provoque par le stage de detection, par

une variation d’inclinaison du visage ou par une variation d’angle de prise de vue. C’est

pourquoi j’ai decide d’exploiter des sous-regions non contigues pouvant se recouvrir a

la section 5.4. Mais tout d’abord, la section 5.3 introduit les ensembles d’apprentissage

et de validation artificiels qui permettront de valider la strategie de generation de la

carte des zones les plus utiles a la discrimination avant de l’utiliser sur les ensembles de

visages.

55

Figure 5.2: Cartes des zones les plus utiles a la discrimination obtenues par la technique de la

division en parties contigues pour differentes tailles de sous-regions elementaires:

3, 5, 10 et 15 pixels de cote. Le resultat des cartes haute resolution est mauvais

pour les raisons evoquees dans le texte et celui des cartes basse resolution n’est

pas assez precis pour localiser avec precision les elements les plus utiles a la

discrimination.

5.3 Introduction aux ensembles d’apprentissage et

de validation artificiellement generes

Suite a des resultats inattendus obtenus lors d’essais de construction de la carte des

zones utiles a la discrimination, j’ai decide d’utiliser des ensembles artificiels de donnees

pour valider la technique de construction de la carte avant de l’employer sur des donnees

reelles. J’ai ainsi genere quatre ’personnes’ presentees a la figure 5.3. Chaque visage est

constitue de deux zones discriminatives qui permettent de les distinguer.

Figure 5.3: Les quatres ’personnes’ generees artificiellement pour valider la technique de

construction de la carte des zones utiles a la discrimination.

Plus loin dans le texte, cet ensemble d’apprentissage et son ensemble de test corre-

spondant serviront a comparer l’efficacite de methode de creation de carte. Ces cartes

auront une resolution de 6 × 6 carres de 100 pixels2 (voir figure 5.4). Les deux zones

discriminatives sont placees exactement au centre de deux de ces carres de 100 pixels2.

Quelques notations et precisions utiles pour la suite : les quatres ’personnes’ de

l’ensemble artificel sont constitues de N = 2 zones discriminatives pouvant prendre

deux valeurs chacune (ξ = 2). Ainsi la chance ψ d’identifier une des quatre ’personnes’

56

artificielles en devinant au hasard est de :

ψ =

(1

ξ

)N(5.1)

=

(1

2

)2

= 0.25

Pour simuler une situation reelle ou le cadrage du visage et l’organisation spatiale

des elements importants pour la discrimination ne sont pas toujours les memes, il est

possible d’ajouter des perturbations de dimension et de position aux ensembles artificiels.

Neanmoins, afin de pouvoir reperer le plus precisement possible les effets indesirables

sur les resultats des methodes qui seront testees plus loin, l’ajout des perturbations de

position et de dimension aux ensembles de donnees artificielles ne sera pas effectue dans

un premier temps.

5.4 Exploitation de parties non-contigues

Une solution alternative a la division en parties contigues est de rassembler les scores

de classification de plusieurs parties non contigues pouvant se chevaucher. Ainsi j’ai (1)

considere toutes les sous-regions delimitables dans une fenetre de 60 pixels de cote dont

les dimensions et les positions etaient des multiples de 151, (2) regarde le pourcentage

de personnes qu’elles pouvaient classer correctement sur l’ensemble de validation et (3)

recoupe les resultats pour obtenir la carte des zones les plus utiles a la discrimination.

La bonne facon de les rassembler n’est pas evidente a trouver et les etapes successives

qui m’ont menees a la strategie finale de la section 5.5 p.63 sont passees en revue ci-

dessous.

5.4.1 Methode (a)

La premiere methode (a) que j’ai essayee se deroule en deux etapes : dans un premier

temps les resultats des sous-regions sont normalises par unite de surface (les scores

sont divises par le nombre de pixels contenus dans la sous-region) et ensuite a chaque

pixel de la carte est attribuee la moyenne des resultats des sous-regions qui l’incluent.

La normalisation est utilisee pour departager les sous-regions de surface differente qui

contiennent la meme quantite d’informations discriminatives en favorisant les regions

1Ce choix est fait pour limiter le nombre de fenetres existantes et pour faciliter le reperage des points

faibles des methodes qui seront successivement testees

57

(a) (b) (c) (d)

Figure 5.4: Cartes obtenues par differentes methodes de rassemblement des resultats des

sous-regions. La methode (a) effectue une moyenne des resultats normalises par

leur surface. La methode (b) effectue une moyenne ponderee par l’inverse de la

surface des resultats normalises. La methode (c) utilise la technique d’expansion

pour annuler les effets de bords. La methode (d) introduit la notion de fraction

d’informations discriminatives et utilise le maximum au lieu de la moyenne.

de dimensions plus faibles qui cadrent mieux l’information discriminative2. La carte

obtenue par cette methode est la carte (a) de la figure 5.4. La carte est incorrecte car

elle attribue une importance differente aux deux zones discriminatives.

La raison de cette difference d’importance aux deux zones discriminatives attribuee

par la premiere methode est que la normalisation par la surface a plus affecte les zones

centrales de carte que les zones peripheriques. En effet, une zone issue du centre de

la fenetre de 60 × 60 pixels2 a une proportion plus grande de sous-regions de grandes

tailles qui l’incluent que celle d’une zone peripherique (voir fig. 5.5) et par consequent,

comme les scores penalises s’additionnent, la zone centrale est plus penalisee que les

zones exterieures.

5.4.2 Methode (b)

La premiere technique (b) proposee pour contrer ce probleme est de diminuer l’impor-

tance des grandes zones dans le moyennage final en ponderant la contribution a la

moyenne des sous-regions par l’inverse de leurs surfaces. Cette technique donne la carte

(b) presentee a la figure 5.4. Il est constate que la seconde methode gomme l’effet nefaste

de la normalisation des scores de la methode (a) mais ne l’efface pas totalement.

2Avec le positionnement irregulier de l’image par rapport a sa fenetre de delimitation (cfr fig. 5.1

p.55), n’est-il pas dangereux de favoriser des petites sous-regions? Non, car les sous-regions soumises au

probleme du positionnement irregulier auront deja ete defavorisees en aval, lors du test sur l’ensemble

de validation. En effet, si ce dernier est realiste, il contient des irregularites de position qui conduiront

a un faible taux de bonnes classifications pour les sous-regions de petites dimensions

58

Figure 5.5: Illustration de la difference de proportion de

sous-regions de grandes tailles qu’il existe pour

une image de 60 × 60 pixels2. Ce graphique

represente pour chaque pixel le nombre de sous-

regions de 900 pixels de surface qui le contien-

nent.

5.4.3 Methode (c)

La troisieme methode (c) proposee resout totalement le probleme de la methode (a)

dont la mesure de l’information discriminative d’une zone depend de l’endroit ou elle se

trouve sur l’image. Pour supprimer la difference entre une zone centrale et peripherique,

l’image de depart 60×60 pixels est placee au centre d’un grand carre de 180×180 pixels

ne contenant aucune information discriminative et le dessin de la carte des zones les plus

utiles a la discrimination est fait en considerant les sous-regions de la grande image dont

aucune des dimensions ne depasse 60 pixels. De cette maniere, tous les pixels de l’image

originale sont dorenavant les pixels centraux de la grande image et donc un pixel central

et un pixel peripherique auront la meme population de sous-regions qui les incluent.

Cette methode appliquee en amont de la methode (b) donne la carte (c) presentee a la

figure 5.4. La carte (c) accorde la meme importance aux deux zones discriminatives,

contrairement aux cartes (a) et (b).

5.4.4 Methode (d)

Les motivations qui m’ont pousse a developper la methode suivante emane de l’observation

de la carte produite par la methode (c). Cette carte indique que la region situee entre

les deux zones de discrimination contient plus d’informations utiles a la discrimina-

tion qu’ailleurs. Ceci s’explique par le fait que prendre une sous-region de dimensions

aleatoires et placer son centre a mi-chemin des deux zones de discrimination donne le

plus de chances de reunir les deux zones discriminatives. Neanmoins, pour un nombre

plus eleve de zones discriminatives, cet effet aura tendance a gommer les contours et

diminuer la precision de la carte des zones les plus utiles a la discrimination.

J’ai donc decide de continuer a reflechir sur le probleme et j’en suis arrive a developper

la methode (d) qui apporte deux contributions a la precedente. La premiere est l’utilisa- Premiere

contribu-

tiontion du maximum au lieu de la moyenne des resultats. Applique directement a la

methode (c) cette contribution donne la carte presentee a la figure 5.6.

Bien que cette carte detecte exactement les deux zones de discrimination, une critique

importante est a faire : cette carte n’a ete obtenue qu’a partir des sous-regions de

59

Figure 5.6: Carte obtenue par l’utilisation du maximum a

la place du moyennage dans l’execution de la

methode (c). Les deux zones discriminatives sont

parfaitement reperees.

15 × 15 pixels, la plus petite unite utilisee lors de ces simulations. De ce fait, elle

n’utilise absolument pas l’information de plusieurs sous-regions non contigues pouvant

se chevaucher et donne le meme resultat et souffre des memes problemes que la methode

de division en parties contigues presentee a la section 5.2. Ce probleme est provoque par

la normalisation qui est trop penalisante pour les sous-regions de moyennes et grandes

dimensions et les empechent de se manifester dans la carte finale : soit le cas de deux

zones 15 × 15 et 30 × 15 pixels2 qui contiennent respectivement sur les deux zones

discriminatives aucune zone discriminative et 1 zone discriminative, la premiere donne

un resultat observe de 25% et la seconde un resultat de 50% (donnees reellement obtenues

avec les ensembles artificiels) tandis que leurs resultats normalises sont respectivement de

25/225 = 0.111 et 50/450 = 0.111. Ces resultats normalises egaux rendent equivalentes

les participations a la carte finale d’une sous-region contenant 50% de l’information et

d’une autre ne contenant aucune information et montre donc que dans ce cas precis

la carte des zones les plus utiles a la discrimination n’a ete contruite qu’a partir des

sous-regions de 15× 15 pixels.

Un autre moyen de se convaincre que la normalisation est trop penalisante est de voir

que la normalisation par la racine carree de la surface plutot que la surface fait resurgir

la participation des sous-regions de dimensions moyennes a la carte des zones les plus

discriminatives (voir figure 5.7).

Figure 5.7: Carte obtenue par l’utilisation du maximum a

la place du moyennage dans l’execution de la

methode (c) et la diminution de la penalite im-

posee aux sous-regions de grande dimension.

La deuxieme contribution de cette methode (d) permet de conserver l’utilisation de Deuxieme

contribu-

tionla normalisation par la surface dont le but premier est de permettre de cadrer au mieux

les zones les plus utiles a la discrimination en penalisant la participation a la carte finale

des sous-regions de surface inutilement trop grande. Une fois la methode (d) au point,

il sera meme possible d’utiliser la normalisation par une puissance de la surface comme

60

un parametre de precision de la carte des zones les plus utiles a la discrimination.

Le coeur de la deuxieme contribution est la transformation des resultats de taux de

bonnes classifications des sous-regions sur l’ensemble de validation a une expression de

la fraction d’informations discriminatives contenues dans la sous-region. L’idee de base

de cette approche vient du fait que si la fraction d’informations discriminatives etait

utilisee au lieu du taux de bonnes classifications, la normalisation lors de l’utilisation du

maximum a la place de la moyenne n’aurait pas l’effet ennuyeux sur la carte finale decrit

plus haut : en reprenant l’exemple on obtient des fractions d’informations discriminatives

normalisees de 0% pour la sous-region de 15 × 15 pixels ne contenant aucune zone

discriminative et de 0.111% pour la sous-region de 15 × 30 pixels contenant une zone

discriminative.

La formule pour passer du taux de bonnes classifications C a la fraction d’informations

discriminatives QI dans le cas des ensembles artificiels est notee ci-dessous et son graphe

est represente a la figure 5.8 :

QI = 1− log0.25(C) (5.2)

La relation 5.2 a ete obtenue en partant de sa reciproque plus intuitive, le taux de

bonnes classifications en fonction de la fraction d’informations discriminatives. Celle-ci

se construit en raisonnant comme suit sur l’identification des ’personnes’ artificielles :

Si aucun bit n’est connu, deux sont devines au hasard et cela donne une chance sur 4 de

trouver la bonne identite; si 1 bit est connu, 1 est devine au hasard et cela donne une

chance sur 2 de trouver la bonne identite; si 2 bits sont connus, aucun n’est devine au

hasard et cela donne 100% de chance de trouver la bonne identite. La generalisation de

ce concept pour N bits ξ-iaire donne la formule 5.3.

C =

(1

ξ

)N(1−QI)

(5.3)

ou N est le nombre total d’elements discriminatifs et N(1−QI) le nombre d’elements

discriminatifs indetermines en fonction de la fraction d’informations discriminatives. La

reciproque de 5.3 donne la fonction generalisee de la fraction d’informations discrimina-

tives par rapport au taux de bonnes classifications :

QI = 1− log(1/ξ)N (C) (5.4)

La methode (d) apporte donc deux contributions : la premiere est l’utilisation du

maximum a la place de la moyenne qui permet de diminuer la tendance de la methode

(c) a gommer les contours et diminuer la precision de la carte. La seconde transforme

61

Figure 5.8: Fonction de conversion de taux de bonnes classifications vers fraction

d’informations discriminatives contenue dans la sous-region pour le cas des en-

sembles artificiels composes de quatre visages. Trois points cles sont indiques

sur la figure : le point (0.25, 0) qui correspond a la situation ou aucune infor-

mation n’est disponible et ou le taux de bonnes classifications correspond a la

chance de d’identifier au hasard la bonne personne. Le point (0.5, 0.5), ce cas

represente une region qui contient 50% de l’information discriminative necessaire

a une identification correcte, c’est a dire un bit sur un nombre binaire de 2 bits

dans le cas des ensembles artificiels. La chance de trouver au hasard la bonne

personne est donc de 50%. Le point (1, 1) ou toute l’information discriminative

est connue et donc ou le taux de bonnes classifications est maximum.

les resultats de taux de bonnes classifications en fraction d’informations discriminatives

contenue dans la sous-region consideree et permet ainsi d’utiliser la normalisation par

une puissance de la surface comme un parametre de precision de la carte finale des zones

les plus utiles a la discrimination. En effet, lors de l’assignation du score maximal, une

puissance elevee favorisera les grandes sous-regions tandis qu’une puissance plus faible

augmentera la participation des sous-regions de faibles dimensions a la carte des zones

les plus utiles a la discrimination.

62

5.5 Strategie proposee et resultats

La methode finalement utilisee pour la creation de la carte des zones les plus utiles a la

discrimination est la methode (d) presentee ci-dessus qui consiste a

1. Placer l’image d’entree de 60× 60 pixels2 au centre d’une grande image neutre de

180× 180 pixels2 pour contrer les effets de bords.

2. Determiner l’ensemble des sous-regions dont la hauteur et la largeur sont inferieures

a 60 pixels pour la grande image de 180× 180 pixels.

3. Tester pour toutes les sous-regions le taux de bonnes classifications qu’elle perme-

ttent d’obtenir sur l’ensemble de validation.

4. Transformer les taux de bonnes classifications en fraction d’informations discrim-

inatives.

5. Normaliser les fractions d’informations discriminatives par une puissance de la

surface pour diminuer la participation des sous-regions de grande taille a la carte

finale. Une puissance elevee l’annule completement tandis qu’une puissance nulle

les met sur un pied d’egalite et produit une carte peu precise.

6. Pour chaque pixel reperer toutes les sous-regions qui l’incluent et lui assigner la

valeur de la sous-region qui, selon le test sur l’ensemble de validation, a la plus

grande fraction d’informations discriminatives apres normalisation par une puis-

sance de la surface.

Figure 5.9: Carte des zones les plus utiles a la discrimination obtenue par la methode finale

(d). La normalisation s’est faite par la racine quinzieme de l’aire et la carte a ete

obtenue en ne considerant que les regions ont la position et les dimensions sont

des multiples de 5.

63

Apres quelques essais pour trouver la puissance de surface ideale par laquelle il faut

normaliser pour avoir un bon resultat, la carte des zones les plus utiles a la discrimination

est dressee a la figure 5.9. Les zones les plus utiles sont les sourcils, le bas des yeux et

les coins gauche et droit de la bouche. D’autres resultats presentes a la figure 5.10

abondent aussi dans ce sens. Neanmoins, il faut signaler que ce resultat ne ressort

pas de maniere categorique a toutes les resolutions et pour toutes les puissances de

surface de normalisation. De plus, pour ce genre d’objectif, les visages constituant les

ensembles d’apprentissage et de validation devraient etre parfaitement reguliers pour

que les variations d’inclinaison et de cadrage ne viennent pas biaiser les resultats. Or

les ensembles de visages utilises ici etaient destines a reproduire une situation reelle de

detection de visages soumise a la contrainte du temps reel et a plusieurs inclinaison des

visages.

Une autre remarque a faire est liee a la resolution de l’image: comme l’algorithme de

generation de la carte n’avait pas la possibilite de tracer une limite de sous-regions entre

le bas des yeux et les sourcils, les deux sous-regions contenant les sourcils et le contour

inferieur des yeux peuvent s’averer etre quelque peu decalee. Neanmoins, cela ne remet

pas en doute l’observation d’un creux d’importance entre les sourcils et les yeux.

Figure 5.10: Deux autres configurations de test pour confirmer les resultats obtenus a la

figure 5.9. Ces deux cartes montrent qu’au niveau des yeux deux zones sont

importantes : les sourcils et une zone situee plus bas. Ici seules les sous-regions

de hauteur 6 ont ete considerees pour des positions et des largeurs multiples de

3 (contrairement aux positions et dimensions multiples de 5 pour la figure 5.9)

Figure 5.11: Carte obtenue par la methode (c) avec une puis-

sance d’aire de normalisation d’un quinzieme.

La carte est floue et ne permet pas de distinguer

les details. Les raisons de ce flou sont expliquees

a la section 5.4.4 p.59 et sont accompagnees de

la description de la methode (d) qui passe au

dessus de ce probleme.

64

Il est interessant maintenant de voir ce que donne l’utilisation d’une autre methode

sur les ensembles de visages reels. A cette fin, le resultat de la methode (c) avec les

meme parametres est presente a la figure 5.11.

L’obtention de la carte des zones les plus utiles a la discrimination ne s’est donc pas

faite sans mal mais a abouti a un resultat qui apporte des informations precises quant

a la distribution des zones qui discriminent au mieux un visage (voir fig 5.9).

5.6 Conclusion

L’objectif de depart etait de generer une carte indiquant les zones les plus utiles a la

discrimination en vue d’aider a la recherche de la combinaison de sous-regions qui donne

le meilleur taux de bonnes classifications (voir section 4.3). La tache s’est averee difficile

et le developpement d’une strategie de construction d’une telle carte a permis de se

pencher sur les elements qui influencaient le caractere discriminatif d’une sous-region

tels que le probleme du positionnement irregulier du visage ou de parties de visage par

rapport a la fenetre de delimitation.

Les principaux defis qui ont ete releves sont l’effet desastreux des effets de bord et la

tendance des methodes simples de gommer les contours de la carte. Pour les identifier

et cerner leurs consequences sur la carte finale, des ensembles artificiels de donnees ont

ete generes et mis sur le banc d’essai. Parmi les propositions qui ont finalement mene

a la strategie finale, une fonction associant la fraction d’informations discriminatives

contenue dans une sous-region au taux de bonnes classifications a constitue un tournant

dans le developpement de la strategie.

La solution finalement adoptee construit la carte a partir des taux de bonnes clas-

sifications individuels des sous-regions. Elle admet deux parametres : le premier agit

pendant la phase de normalisation des donnees et permet de jouer sur la precision de

la carte finale en defavorisant plus ou moins les sous-regions de grande superficie. Le

second concerne la resolution de la carte finale. A cote de ces parametres, il est possible

de construire la carte a partir d’ensembles de sous-regions dont une des caracteristiques,

telle qu’une dimension ou la surface, est comprise dans un intervalle particulier.

Toutes ces possibilites de configurer la generation de la carte des zones les plus utiles

a la discrimination menent finalement a un large panel de cartes desquelles il est difficile

de faire la synthese. Ainsi le premier parametre de precision s’apparente a un bouton

de mise au point qui produit une multitude de niveaux de resultats correspondant a

differents niveaux de defavorisation des sous-regions de superficie elevee.

65

La technique ne repond donc pas entierement aux attentes de depart mais resout

les premieres grosses embuches a la generation d’une telle carte. Je n’ai pas trouve

d’indications pour m’aider dans la litterature concernant la reconnaissance faciale que

j’ai consultee. Une des premieres etapes de la suite du developpement de cette methode

serait donc de regarder ce que peuvent apporter des techniques statistiques ou d’imagerie.

Les presents resultats permettent d’en savoir un peu plus sur l’organisation des zones

les plus utiles a la discrimination malgre qu’ils doivent encore faire l’objet de tests pour

etre affirmes avec certitude. Ainsi il semble que ce ne soit pas les zones comprenant

completement des elements cles du visage tels que les yeux, le nez ou la bouche qui sont

les plus utiles a la discrimination mais des zones frontieres comme les bords de la bouche

(sous doute moins soumis a des legers deplacements des levres causant l’apparition des

dents) ou la region inferieure des yeux.

66

Chapitre 6

Implementation C++ et test des

performances

6.1 Implementation

L’application a ete entierement implementee en C++ (voir appendice A) et interfacee

avec Nao. Une capture d’ecran de l’application en fonctionnement est presentee a la

figure 6.1.

Figure 6.1: Capture d’ecran de l’application en fonctionnement. Deux personnes sont re-

connues par l’application qui leur attribue une couleur differente. Les deux

images temoins en bas a gauche sont le resultat de la phase de traitement de

l’illumination effectuee durant le stage de reconnaissance.

67

L’enregistrement d’un nouveau visage se commande par le clavier et il est aussi

possible de commander l’enregistrement sur le disque dur d’un visage dans sa fenetre de

delimitation.

6.2 Test de la detection des visages

Les tests de la detection des visages ont ete effectues car elle se trouve en amont du

traitement de l’image et conditionne donc tout le reste du traitement. Une bonne

comprehension et connaissance de ses capacites est importante pour l’interpretation

des resultats de la reconnaissance faciale ou de tout autre traitement ulterieur.

Deux elements seront testes ici : l’orientation en degres des visages detectes et le

cadrage du visage dans son rectangle de delimitation.

6.2.1 Orientations detectees

OpenCV fournit entre autres deux apprentissages utiles pour cette application : un pour

detecter les visages de face et le second pour les visages de profil. J’ai voulu en savoir

plus sur les taux de detection en fonction de l’orientation du visage de ces deux methodes

et j’ai donc mene l’experience. Les resultats sont presentes a la figure 6.2.

L’apprentissage FRONTFACE donne des resultats en faveur de son utilisation comme

routine de localisation de visages presentes face a la camera : une zone de detection

superieure a 94% s’etend de -20◦ a 20◦. L’apprentissage PROFILFACE vient soutenir

le FRONTFACE en elargissant cette zone de detection vers la gauche jusqu’a -70◦.

6.2.2 Cadrage des visages

Les resultats de la parametrisation montrent que les zones de discrimination sont toutes

deplacees vers la gauche (voir figure 6.3), comme si l’ensemble des visages issus de la

detection etaient mis trop a gauche dans leur fenetre de delimitation.

J’ai voulu confirmer ces resultats en effectuant deux tests. Tout d’abord, pour voir

si cette asymetrie venait de mon code MatLab, j’ai reeffectue les tests sur l’ensemble de

validation ayant subi une symetrie horizontale. Le resultat est negatif, mon code n’est

pas en cause. Le probleme doit donc provenir d’une etape en amont: la detection des

visages ou les conditions dans lesquelles se sont deroulees les seances photos desquelles

sont issues les photos de la base de donnees FERRET.

Une premiere hypothese serait que le cadrage du stage de detection soit incorrect.

J’ai alors releve manuellement la position des yeux, des coins des yeux pour chacune des

60 images de l’ensemble d’apprentissage. Le resultat est que la moyenne et la mediane

68

Figure 6.2: Taux de detection des apprentissages fournit avec OpenCV en fonction de

l’orientation du visage. La courbe verte correspond a l’apprentissage pour la

detection des visages de face tandis que la bleue montre les performances de

l’apprentissage destine a detecter les visages de profil. Les photos proviennent

de la base de donnees GRAY FERET. Les courbes ont ete construites a partir

de tests portant sur 30 sujets presentes chacun selon 9 orientations differentes

s’etalant uniformement de -90 a 90◦.

Figure 6.3: Resultats representant les zones les plus utiles a la discrimination obtenus selon

differentes methodes developpees au chapitre 5 ’Obtenir une carte des zones

utiles a la discrimination’. Tous montrent un decalage des zones les plus utiles a

la discrimination sur la gauche de l’image.

des centres de gravites des deux yeux sont decales d’un dixieme de pixel vers la gauche,

ce qui n’est pas suffisant pour provoquer l’asymetrie observee dans 6.3.

Une seconde hypothese et que pour les visages inclines a gauche ou a droite, l’apprentissage

de detection fourni par OpenCV privilegie un positionnement regulier de l’oeil gauche

69

a un positionnement regulier de l’oeil droit, produisant plus d’effets nefastes dus au

positionnement irregulier de la fenetre de delimitation (voir section 5.2 p.55 et figure

5.1 p.55) pour les parties du visage se trouvant a droite que pour celles se trouvant a

gauche. La premiere observation des variances des positions en x et y relevees manuelle-

ment pour l’oeil gauche et de l’oeil droit semblent abonder en ce sens mais il faudrait

encore des tests pour valider l’hypotese.

Une derniere hypothese serait que l’eclairage durant les seances de photo etait privilegierement

situe a la gauche des sujets. Ceci aurait provoque une augmentation de contraste sur

la partie vue a gauche de la photo, apportant ainsi plus de details que les ’local binary

patterns’ peuvent exploiter.

Donc, on observe un deplacement vers la gauche des zones riches en informations sur

toutes les cartes generees automatiquement. Un test simple de symetrie centrale sur

les donnees d’entree a permis d’ecarter l’hypothese d’un souci dans l’implementation

Matlab. Apres quelques tests, deux hypotheses a confirmer sont formulees: (1) une fa-

vorisation par l’apprentissage de detection d’OpenCV du placement regulier de la partie

gauche de l’image et (2) des conditions d’illuminations regulieres favorisant l’apparition

d’une zone plus contrastee a gauche, soulignant les traits du visages et fournissant ainsi

plus d’informations pour la discrimination.

La premiere etape dans la suite des investigations est de confirmer ce decalage vers

la gauche sur un autre ensemble de test dont le cadrage aura ete obtenu de la meme

facon, c’est-a-dire par l’algorithme de Viola et Jones implemente par OpenCV.

6.3 Test de la reconnaissance des visages

Les taux de bonnes classifications pour un ensemble de test comptant 60 visages differents

pour l’apprentissage et 69 prises de vue de ces 60 visages pour le test sont presentes a la

figure 6.4. Les methodes testees sont la simple classification a partir des images d’origine,

la classification utilisant les sous-regions selectionnees par la technique presentee au

chapitre 4 et idem avec les images ayant subi un traitement contre l’illumination.

Ce resultat est a replacer dans son contexte: deux facteurs principaux le demarque

des situations de tests rencontrees dans les articles de la litterature.

• Les visages ont ete cadres par l’algorithme de localisation de visages de Viola et

Jones et aucune operation visant a recentrer le visage par rapport a sa fenetre

de delimitation, a mettre le visage droit ou a gommer un background genant n’a

ete effectuee. Par exemple, l’article de Deng et al. [16] obtenant des resultats

70

Figure 6.4: Taux de bonnes classifications obtenus a partir des images originales (BMP),

des images originales et en utilisant la technique de la division en sous-regions

traitees separement (COMBI) et idem avec un pretraitement d’illumination

(COMBI+ILLU).

avoisinant les 95% place les yeux au pixel pres dans une fenetre de delimitation de

128× 128 pixels2.

• La dimension de l’image est de 60×60 = 3600 pixels2 pour rejoindre les dimensions

que l’algorithme rencontrera lors de son utilisation avec le robot Nao. Dans la

litterature, des dimensions superieures a 10000 pixels2 sont souvent rencontrees

[42, 4].

71

Conclusion

L’objectif de ce memoire etait de concevoir et d’implementer sur un petit robot hu-

manoıde, Nao, une application de reconnaissance faciale capable, en temps reel, de

reconnaıtre les visages et de diriger le regard de Nao vers eux apres une seule prise de

vue. Vu la quantite de logiciels potentiels pouvant se baser sur cette application, celle-ci

devait repondre a des exigences de rapidite et de robustesse des resultats.

En ce sens, la premiere partie de l’application qui consiste a localiser les visages

employe l’algorithme de Viola et Jones [38], largement reconnu comme methode fonc-

tionnant en temps reel et fournissant des resultats robustes et fiables. Il s’est avere

que l’algorithme detectait une proportion tres elevee (> 98%) des visages presentes de

face et plus de 94% des visages qui s’ecartaient de la position frontale de moins de 20◦.

Ces resultats sont consideres amplement suffisants pour son utilisation par le logiciel

developpe.

Les visages localises sont extraits et font l’objet du traitement d’illumination propose

par Tan et al. [33] qui est compose de deux etapes majeures. Tout d’abord l’elevation a

une puissance qui diminue l’influence de l’intensite d’illumination sur la couleur percue

d’un pixel. Ensuite une filtration par difference de gaussiennes qui supprime les basses

frequences contenant les effets non desirables des ombres et les hautes frequences con-

tenant l’aliasing et le bruit.

La seconde partie de l’application s’occupant de la reconnaissance des visages localises

convertit d’abord l’image en ’modeles binaires locaux’ et ensuite divise l’image en sous-

regions pouvant se chevaucher. Enfin, un comptage des modeles binaires locaux est

realise pour chaque sous-region et les histogrammes ainsi obtenus servent de base a la

comparaison d’individus.

La conversion en modeles binaires locaux aboutit a une description de l’image en

termes des structures, coins ou aretes, auxquelles appartiennent les pixels de l’image.

Ainsi, deux pixels de meme couleur appartenant respectivement a une arete verticale et

une arete horizontale auront deux modeles binaires locaux associes differents devrivant

72

leurs types de structure (ici: deux aretes) et leurs orientations (ici: verticale et horizon-

tale). Cette description en termes de coins et d’aretes est une premiere interpretation

de l’image et donne une signification plus pertinente aux valeurs des pixels.

La division peut se faire de beaucoup de manieres differentes et certaines zones du

visages ne sont parfois pas du tout considerees pour la classification. De la meme facon,

certaines combinaisons sont plus aptes a reconnaıtre les visages que d’autres.

Trouver la meilleure combinaison de sous-regions est difficile vu leur nombre. Ainsi,

trouver la meilleure association de trois sous-regions contenues dans un visage de 60×60

pixels2, signifie selectionner 1 combinaison parmi 6.2597× 1018 candidats.

La solution proposee a cette situation est d’operer une preselection. La technique

consiste a classer les sous-regions au sein de chaque categorie de dimensions et de

preselectionner ensuite la meilleure combinaison des meilleures sous-regions de chaque

categorie.

La methode de preselection a comme principaux defauts de (1) ne selectionner

au maximum qu’une sous-region par categorie de dimensions et (2) de ne pas garan-

tir par son fonctionnement intrinseque une preselection dont la complementarite des

elements accordera au classifieur final les meilleures performances. Une amelioration de

la methode proposee consisterait alors a diviser l’image en plusieurs ’macro sous-regions’

au sein desquelles des classements entre sous-regions de meme surface seraient effectues.

Ensuite chaque macro sous-region apporterait ses sous-regions d’elite a la preselection.

Figure 6.5: Resultat de la parametrisation des sous-regions traitees separement durant la

reconnaissance. Les zones 1 et 2 ont un poids de 5 tandis que les deux autres ont

un poids de 1.

La meilleure combinaison obtenue (voir fig. 6.5) en utilisant la methode developpee

est constituee de petites sous-regions inclues dans des sous-regions de plus grandes di-

73

mensions qui englobent la totalite des elements cles du visage tels que les yeux, la

bouche et le nez. Or, il etait attendu plusieurs sous-regions de dimensions moyennes ne

se chevauchant que legerement. Ce resultat est probablement influence par le nombre

de sous-regions considerees impose a quatre. L’etape suivante du developpement serait

donc de voir, avec un ordinateur le permettant, si ces sous-regions de grande taille sont

toujours presentes pour une combinaison d’un nombre plus eleve.

Les plus petites sous-regions se repartissent sur un seul cote du visage, phenomene

qui pourrait etre du a la symetrie du visage qui rend inutile la connaissance d’une sous-

region si son homologue symetrique est deja connu. Ce dernier resultat est interessant

et devrait faire l’objet de plus d’etudes pour le generaliser.

Dans le cas d’un nombre fixe de 4 sous-regions combinees, l’analyse de la distribution

des poids fait remarquer que les sous-regions de petites dimensions centrees sur des

elements cles du visage semblent aider le reconnaisseur de visage a se diriger vers la

bonne decision par de petites influences tandis que les sous-regions de grandes dimensions

indiquent la direction generale.

Au vu de cette methode de preselection qui ne garantit pas d’obtenir la combinaison

dont les sous-regions sont les plus complementaires, ce memoire propose une methode

de generation de carte dont la consultation permettrait de reperer tout de suite les zones

du visage a considerer prioritairement.

Le developpement d’une telle methode s’est revele plus ardu que prevu et les prin-

cipaux problemes a resoudre ont ete les consequences negatives des effets de bord et la

tendance au gommage des contours de la carte lors de l’utilisation de methodes sim-

ples. Pour identifier ces problemes et cerner leurs consequences sur la carte finale, des

ensembles artificiels de donnees ont ete generes et mis sur le banc d’essai. Parmi les

propositions qui ont finalement mene a la strategie finale, une fonction associant la frac-

tion d’informations discriminatives contenue dans une sous-region au taux de bonnes

classifications a constitue un tournant.

La solution finalement adoptee construit la carte a partir des taux de bonnes clas-

sifications individuels des sous-regions. Elle admet deux parametres : le premier agit

pendant la phase de normalisation des donnees et permet de jouer sur la precision de

la carte finale en defavorisant plus ou moins les sous-regions de grande superficie. Le

second concerne la resolution de la carte finale. A cote de ces parametres, il est possible

de construire la carte a partir d’ensembles de sous-regions dont une des caracteristiques,

telle qu’une dimension ou la surface, est comprise dans un intervalle particulier.

Toutes ces possibilites de configurer la generation de la carte des zones les plus utiles

74

a la discrimination menent finalement a un large panel de cartes desquelles il est difficile

de faire la synthese. Ainsi le premier parametre de precision s’apparente a un bouton

de mise au point qui produit une multitude de niveaux de resultats correspondant a

differents niveaux de defavorisation des sous-regions de superficie elevee.

La technique ne repond donc pas entierement aux attentes de depart mais resout

les premieres grosses embuches a la generation d’une telle carte. Une des premieres

etapes de la suite du developpement de cette methode serait de regarder ce que peuvent

apporter des techniques statistiques ou d’imagerie.

Figure 6.6: Carte des zones les plus utiles a la discrimination.

Les presents resultats (voir fig. 6.6) permettent d’en savoir un peu plus sur l’organisation

des zones les plus utiles a la discrimination malgre qu’ils doivent encore faire l’objet de

tests pour etre affirmes avec certitude. Ainsi il semble que ce ne soit pas les zones com-

prenant completement des elements cles du visage tels que les yeux, le nez ou la bouche

qui sont les plus utiles a la discrimination dans le cas de l’utilisation d’histogrammes de

modeles binaires locaux, mais les zones frontieres comme les bords de la bouche (sans

doute moins soumis a des legers deplacements des levres causant l’apparition des dents)

ou la region inferieure des yeux.

Le logiciel finalement concu reconnaıt 85.5% des visages presentes pour une base de

visages de 60 elements. Avant d’etre compare aux resultats obtenus dans la litterature,

une remarque importante est a faire. Pour reproduire au mieux les conditions reelles

d’execution de l’application, les visages utilises lors des tests ont ete extraits d’images

originales de la base de donnees FERRET par l’algorithme de localisation des visages

de Viola et Jones implemente par OpenCV. Par consequent, les visages des ensem-

bles d’apprentissage et de test presentaient des variations d’echelles, de cadrages et

d’inclinaisons des visages (visages penches a droite ou a gauche jusqu’a 7◦).

75

De plus, pour reproduire les dimensions des visages qui seront extraits du champ vi-

suel de Nao en conditions reelles, les visages utilises lors des tests avaient des dimensions

de 60× 60 pixels2.

Les resultats obtenus dans la litterature atteignent des valeurs superieures a 95% mais

font souvent recours a des recadrages et mises a l’echelle manuels placant les elements

cles du visage au pixel pres dans une fenetre de delimitation de surface superieure a

100× 100 pixels2 [42, 4, 16].

Les points cles de ce memoire sont:

• La proposition d’une methode de selection d’une combinaison de sous-regions pour

la classification des visages qui supporte le chevauchement.

• La proposition d’une methode de generation de cartes des zones les plus utiles a

la discrimination.

• La mise en evidence des roles joues par les petites et les grandes sous-regions dans

une combinaison performante.

• La mise en evidence du role des zones frontieres des elements cles du visage dans

la reconnaissance faciale.

• La conception d’un logiciel de reconnaissance sur le robot Nao en tenant compte

de ses limitations materielles.

• L’interpretation des modeles binaires locaux en termes d’aretes et de coins.

• L’interpretation de la division et de la conversion en histogrammes comme moyen

de moduler la quantite d’informations spatiales utilisee pour la classification des

visages.

• La proposition d’utiliser la distance entre les centres de gravite de modeles binaires

locaux identiques comme information spatiale au sein d’une sous-region.

• Une reflexion sur ce que pourrait apporter une meilleure collaboration des systemes

de poursuite et de reconnaissance des visages.

• Une reflexion sur la difference entre le temps de rafraıchissement et le temps de

reaction d’un systeme.

• La transposition du concept de l’image integrale a celui de l’histogramme integral

sans laquelle la plupart des simulations de ce memoire n’aurait pas pu etre ef-

fectuee.

La suite du travail pourrait se concentrer specifiquement sur la generation de cartes

des zones les plus utiles a la discrimination et la selection de la meilleure combinaison de

76

sous-regions pour la classification. Je propose tout d’abord l’amelioration de la gestion

de la memoire et du processeur des algorithmes utilises et l’emploi de machines plus

puissantes pour atteindre des resolutions plus elevees et des nombres de sous-regions par

combinaison plus grands. Ensuite je conseille l’utilisation de base de visages parfaitement

homogenes en ce qui concerne le cadrage, les poses et les inclinaisons des visages.

Cela permettrait d’obtenir des resultats plus precis qui augmenteraient les connais-

sances concernant la repartition des zones les plus utiles a la discrimination dans le cas

de la classification par comparaison d’histogrammes de modeles binaires locaux.

Ensuite, ces connaissances en situation ideale serviraient a mieux apprehender le

probleme de la reconnaissance faciale en conditions reelles ou les visages sont soumis a

des variations d’inclinaison, d’orientation, d’illumination et d’expression.

77

Bibliographie

[1] http://www.aldebaran-robotics.com/.

[2] http://opencv.willowgarage.com/wiki/.

[3] http://face.nist.gov/colorferet/release agreement v1.html.

[4] Timo Ahonen, Abdenour Hadid, and Matti Pietikainen. Face description with local

binary patterns: Application to face recognition. IEEE Transactions on Pattern

Analysis and Machine Intelligence, 28(2006):2037–2041, 2006.

[5] Alberto Albiol, David Monzo, Antoine Martin, Jorge Sastre, and Antonio Albiol.

Face recognition using hog-ebgm. Pattern Recognition Letters, 29(10):1537–1543,

2008.

[6] Gaoyun An, Jiying Wu, and Qiuqi Ruan. An illumination normalization model

for face recognition under varied lighting conditions. Pattern Recognition Letters,

31(9):1056 – 1067, 2010.

[7] Peter N. Belhumeur, Joao P. Hespanha, and David J. Kriegman. Eigenfaces vs.

fisherfaces: Recognition using class specific linear projection. In Computer Vision -

ECCV ’96, volume 1064/1996 of Lecture Notes in Computer Science, pages 43–58.

Springer, Heidelberg, 1996.

[8] David Beymer and Tomaso Poggio. Face recognition from one example view. In

Fifth International Conference on Computer Vision (ICCV’95), 1995.

[9] Jie Chen, Xilin Chen, Jie Yang, Shiguang Shan, Ruiping Wang, and Wen Gao.

Optimization of a training set for more robust face dectection. Pattern Recognition,

42(2009):2828–2840, 2009.

[10] Songcan Chen, Jun Liu, and Zhi-Hua Zhou. Making flda applicable to face recog-

nition with one sample per person. Pattern Recognition, 37(7):1553–1555, 2004.

78

[11] Songcan Chen, Daoqiang Zhang, and Zhi-Hua Zhou. Enhanced (pc)2a for face

recognition with one training image per person. Pattern Recognition Letters,

25(10):1173 – 1181, 2004.

[12] Yong Cheng, Yingkun Hou, Chunxia Zhao, Zuoyong Li, Yong Hu, and Cailing

Wang. Robust face recognition based on illumination invariant in nonsubsampled

contourlet transform domain. Neurocomputing, 73(10-12):2217 – 2224, 2010.

[13] Cheng-Chin Chiang, Wen-Kai Tai, Mau-Tsuen Yang, Yi-Ting Huang, and Chi-

Jaung Huang. A novel method for detecting lips, eyes and faces in real time.

Real-Time Imaging, 9(4):277–287, 2003.

[14] Charles K Chui. An Introduction to Wavelets. Academic Press, Boston, 2002.

[15] Javier Ruiz del Solar and Julio Quinteros. Illumination compensation and nor-

malization in eigenspace-based face recognition: A comparative study of different

pre-processing approaches. Pattern Recognition Letters, 29(14):1966 – 1979, 2008.

[16] Weihong Deng, Jiani Hu, Jun Guo, Weidong Cai, and Dagan Feng. Robust, accu-

rate and efficient face recognition from a single training image: A uniform pursuit

approach. Pattern Recognition, 43(5):1748 – 1762, 2010.

[17] B. Froba and A. Ernst. Face detection with the modified census transform. In

Proceedings of the 6th IEEE International Conference on Automatic Face and Ges-

ture Recognition AFGR6th IEEE International Conference on Automatic Face and

Gesture Recognition AFGR, pages 91–96, Seoul, Korea, May 2004.

[18] Yongsheng Gao and Yutao Qi. Robust visual similarity retrieval in single model

face databases. Pattern Recognition, 38(7):1009 – 1020, 2005.

[19] Peg Howland, Jianlin Wang, and Haesun Park. Solving the small sample size prob-

lem in face recognition using generalized discriminant analysis. Pattern Recognition,

39(2):277–287, 2006.

[20] Samuel Kadoury and Martin D. Levine. Face detection in gray scale images using

locally linear embeddings. Computer Vision and Image Understanding, 105(1):1 –

20, 2007.

[21] Wen-Chung Kao, Ming-Chai Hsu, and Yueh-Yiing Yang. Local contrast enhance-

ment and adaptive feature extraction for illumination-invariant face recognition.

Pattern Recognition, 43(5):1736 – 1747, 2010.

79

[22] Constatine Kotropoulos, Anastasios Tefas, and Ioannis Pitas. Frontal face authen-

tication using morphological elastic graph matching. IEEE Transactions on Image

Processing, 9(4):555–560, 2000.

[23] Ludmila I. Kuncheva and Christopher J. Whitaker. Feature subsets for classifier

combination: An enumerative experiment. In Multiple Classifier Systems, volume

Volume 2096/2001 of Lecture Notes in Computer Science, pages 228–237. Springer,

Heidelberg, 2001.

[24] Kin-Man Lam and Hong Yan. An analytic-to-holistic approach for face recognition

based on a single frontal view. IEEE Transactions on pattern analysis and machine

intelligence, 20(7):673–686, 1998.

[25] Hung-Son Le and Haibo Li. Recognizing frontal face images using hidden markov

models with one training image per person. In 17th International Conference on

Pattern Recognition (ICPR’04) - Volume 1, volume 1, pages 318–321, 2004.

[26] Tai Sing Lee. Image representation using 2d gabor wavelets. IEEE Trans. Pattern

Analysis and Machine Intelligence, 18:959–971, 1996.

[27] P.J. Phillips, H. Wechsler, J. Huang, and P. Rauss. The feret database and eval-

uation procedure for face recognition algorithms. Image and Vision Computing J,

16(5):295–306, 1998.

[28] P.J. Phillips, H. Wechsler, J. Huang, and P. Rauss. The feret evaluation method-

ology for face recognition algorithms. IEEE Trans. Pattern Analysis and Machine

Intelligence, 22:1090–1104, 2000.

[29] H.A. Rowley, S. Baluja, and T. Kanade. Neural network-based face detection. IEEE

Transactions on Pattern Analysis and Machine Intelligence, 20(1):23–38, 1998.

[30] H. Schneiderman and T. Kanade. Probabilistic modeling of local appearance and

spatial relationships for object recognition. Computer Vision and Pattern Recogni-

tion, IEEE Computer Society Conference on, 0:45, 1998.

[31] Xiaoyang Tan, Songcan Chen, Zhi-Hua Zhou, and Fuyan Zhang. Recognizing par-

tially occluded, expression variant faces from single training image per person with

som and soft knn ensemble. IEEE Transactions on Neural Networks 1, 16(4):875–

886, 2005.

80

[32] Xiaoyang Tan, Songcan Chen, Zhi-Hua Zhou, and Fuyan Zhang. Face recognition

from a single image per person: A survey. Pattern Recognition, 39(2006):1725–1745,

2006.

[33] Xiaoyang Tan and Bill Triggs. Enhanced local texture feature sets for face recog-

nition under difficult lighting conditions. In Analysis and Modelling of Faces and

Gestures, volume 4778 of LNCS, pages 168–182. Springer, oct 2007.

[34] Antonio Torralba and Pawan Sinha. Detecting faces in impoverished images. Jour-

nal of Vision, 2(7):601, 2002.

[35] Wen-Kwang Tsao, Anthony J.T. Lee, Ying-Ho Liu, Ting-Wei Chang, and Hsiu-Hui

Lin. A data mining approach to face detection. Pattern Recognition, 43(3):1039 –

1049, 2010.

[36] M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuro-

science, 3(1):71–86, January 1991.

[37] Patricia Rayon Villela and Juan Humberto Sossa Azuela. Face description with

local binary patterns: Application to face recognition. In MICAI 2002: Advances

in Artificial Intelligence, volume 2313/2002 of Lecture Notes in Computer Sciences,

pages 282–291. Springer, Heidelberg, 2002.

[38] Paul Viola and Michael Jones. Robust real-time object detection. In Second inter-

national workshop on statistical and computational theories of vision, Vancouver,

Canada, July 13 2001.

[39] Paul Viola and Michael Jones. Robust real-time face detection. International

Journal of Computer Vision, 57:137–154, 2004.

[40] Chao Wang and Yongping Li. Combine image quality fusion and illumination

compensation for video-based face recognition. Neurocomputing, 73(7-9):1478 –

1490, 2010.

[41] Haitao Wang, Stan Z Li, and Yangsheng Wang. Face recognition under varying

lighting conditions using self quotient image. Automatic Face and Gesture Recog-

nition, IEEE International Conference on, 0:819, 2004.

[42] Jie Wang, K.N. Plataniotis, Juwei Lu, and A.N. Venetsanopoulos. On solving the

face recognition problem with one training sample per subject. Pattern Recognition,

39(2006):1746–1762, 2006.

81

[43] Laurenz Wiskott, Jean-Marc Fellousc, Norbert Kruger, and Christopher von der

Malsburg. Face recognition by elastic bunch graph matching. IEEE Trans. Pattern

Anal. Mach. Intell., 19(7):775–779, 1997.

[44] Jianxin Wu, S. Charles Brubaker, Matthew D. Mullin, and James M. Rehg. Fast

asymmetric learning for cascade face detection. IEEE Transactions on pattern

analysis and machine intelligence, 30(3):369–382, 2008.

[45] Jianxin Wu and Zhi-Hua Zhou. Face recognition with one training image per person.

Pattern Recognition Letters, 23(14):1711–1719, 2002.

[46] Li Xiaohua, Kin-Man Lam, Shen Lansun, and Zhou Jiliu. Face detection using

simplified gabor features and hierarchical regions in a cascade of classifiers. Pattern

Recognition Letters, 30(2009):717–728, 2008.

[47] Quan xue Gao, Lei Zhang, and David Zhang. Face recognition using flda with single

training image per person. Applied Mathematics and Computation, 205(2):726–734,

2008.

[48] Jian Yang, David Zhang, Alejandro F. Frangi, and Jing yu Yang. Two-dimensional

pca: A new approach to appearance-based face representation and recognition.

IEEE Transactions on pattern analysis and machine intelligence, 26(1):131–137,

January 2004.

[49] Ming-Hsuan Yang, David J. Kriegman, and Narendra Ahuja. Detecting faces in

images : A survey. IEEE Transactions on pattern analysis and machine intelligence,

24(1):1746–1762, 2002.

[50] Qiong Yang and Xiaoqing Ding. Symmetrical pca in face recognition. In ICIP (2),

pages 97–100, 2002.

[51] Hua Yu and Jie Yang. A direct lda algorithm for high-dimensional data – with

application to face recognition. Pattern Recognition, 34(10):2067 – 2070, 2001.

[52] Stefanos Zafeiriou, Anastasios Tefas, and Ioannis Pitas. The discriminant elastic

graph matching algorithm applied to frontal face verification. Pattern Recognition,

40(10):2798 – 2810, 2007.

[53] W. Zhao, R. Chellappa, P.J. Phillips, and A. Rosenfeld. Face recognition : a

literature survey. ACM Computing Surveys, 28:399–458, 2003.

82

[54] Wenlong Zheng and Suchendra M. Bhandarkar. Face detection and tracking using

a boosted adaptive particle filter. Journal of Visual Communication and Image

Representation, 20(1):9 – 27, 2009.

[55] Xiao-Sheng Zhuang and Dao-Qing Dai. Inverse fisher discriminate criteria for small

sample size problem and its application to face recognition. Pattern Recognition,

38(11):2192–2194, 2005.

[56] Xuan Zou, J. Kittler, and K. Messer. Illumination invariant face recognition: A sur-

vey. In First IEEE International Conference on Biometrics : Theory, Applications,

and Systems, pages 1–8, Crystal City, VA, September 2007.

83

Appendices

84

Appendix A

Implementation C++ : la librairie

ImProc

Le module de reconnaissance est concu pour etre utilise a partir de n’importe quelle

source visuelle. Il est contenu dans une librairie statique pour ensuite etre liee a

n’importe quel projet. En quelques minutes seulement, une application capable de

reconnaıtre des personnes peut etre concue. Ainsi, pour l’elaboration de ce present

memoire, une application video d’une trentaine de lignes liee a la libraire ImProc est

deja capable de localiser, memoriser et reconnaıtre des individus.

Le module recoit en entree une image sous le format IplImage de la librairie OpenCV.

Celle-ci est ensuite traitee et le resultat (nombre de personnes presentes, leurs positions

et leurs identites) est directement utilisable pour des taches d’ordre superieur tel que la

creation d’un historique des rencontres ou l’elaboration d’un mouvement de la camera

vers un individu en particulier. L’architecture de la librairie est detaillee dans la section

A.2.

A.1 Les librairies utilisees

Pour l’elaboration de ce module, plusieurs libraires externes ont ete utilisees :

• OpenCV ( Open Source Computer Vision ) est une librairie initialement developpee

par Intel qui fournit plus de 500 algorithmes pour la vision par ordinateur en temps

reel. L’algorithme de Viola et Jones y est implemente et des apprentissages sont

fournis. Ainsi OpenCV peut deja localiser les visages, les yeux, les bouches ou

d’autres parties du corps.

• GTK ( Gimp toolkit ) est une librairie destinee a la creation d’interfaces visuelles.

Elle permet aussi l’interaction avec le clavier et la souris.

85

A.2 La librairie ImProc

Cette section decrit l’architecture de la librairie ImProc que j’ai developpee dans le

cadre du memoire. Les elements cles sont decrit brievement ci-dessous tandis qu’une

vue d’ensemble est propose a la figure A.1.

• Display : Cet objet sera charge de l’affichage des resultats a l’ecran. Il relaie via

ImgBufferOUT l’information visuelle generee par la ImProc a la librairie GTK qui

s’occupe ensuite de son affichage a l’ecran. Il est constitue d’un threath qui verifie

regulierement s’il y a une nouvelle information a afficher a l’ecran.

• ImageBufferIN : Il s’agit du tampon dans lequel est charge une image brute a

traiter.

• ImageBufferOUT : Lors du traitement de l’image brute, celle-ci se voit modifiee

par l’ajout de rectangles indiquant l’emplacement des visages, de texte, etc. Cette

image traitee est stockee dans ImageBufferOUT, lue par Display et envoye pour

affichage.

• LogWriter : Objet destine a l’ecriture d’information issue de l’execution dans des

fichiers. L’acces au disque dur est souvent synonyme de ralentissement or nous

cherchons a construire une application en temps reel. C’est pourquoi LogWriter

stocke en memoire RAM toutes les informations qui lui sont transmises au fur et

a mesure. Il est ensuite possible de commander l’ecriture sur disque dur a des

moments plus appropries, a la fin de l’execution de l’application par exemple.

• ImProc : Le coeur de la librairie. C’est cet objet qui est charge de la localisation,

le tracking, l’enregistrement et la reconnaissance des individus. C’est lui qui prend

l’image brute dans ImageBuffer1 pour la traiter et la placer dans ImageBuffer2.

• KBEvent : Cette objet permet aux autres (typiquement ImProc) de savoir si un

intervention utilisateur a eu lieu. Typiquement il s’agit de l’ordre d’enregistrer les

personnes presentes, de prendre une photo ou de quitter l’application. Il travaille

en collaboration avec Display qui avec la librairie GTK detecte les evenements

claviers. L’application peut aussi utilise KBEvent comme vecteur pour ordonner

l’enregistrement du visage courant ou pour quitter l’application.

86

Figure A.1: Vue d’ensemble de l’architecture de la Librairie ImProc creee dans le cadre du

memoire. La boucle de traitement commence en haut a droite par l’application

qui capture l’image d’une source quelconque est la transmet a ImgBuffer IN.

L’image est ensuite traitee par l’object ImProc(coeur de la librairie ImProc) en

collaboration avec OpenCV. Le resultat est stocke dans ImbBuffer OUT pour

affichage. L’objet KBEvent est concu pour modifier le comportement d’ImProc

en fonction de messages recu en cours d’execution soit par l’utilisateur soit par

l’application.

87