(:utilisation d'un arbre de décision pour la reco de visages:)

TP RdF, semaines 10-11: arbres de décision et reconnaissance de visages

Ce TP est réalisé dans l'environnement R.

Variante du jeu du pendu

Terminer le jeu de pendu de la semaine 9, car la même méthodologie est employée cette semaine.

Application des arbres à la reconnaissance de visages

1. Objectif

L'objectif de ce TP est d'illustrer l'utilisation d'arbres de décision dans le contexte de la reconnaissance de formes image. Pour ce faire, nous allons mettre en oeuvre un arbre de décision pour la reconnaissance de visages, en nous basant sur la décomposition du jeu du pendu vue à la semaine 9.

2. Données d'apprentissage

Nous disposons d'une image source contenant 10 exemples de 40 visages, que nous allons utilier pour construire notre modèle.

En la binarisant, nous obtenons l'image ci-dessous à droite dans laquelle pixels prennent des valeurs dans {0,1}.

Images de 10 exemples de 40 visages pour l'apprentissage et le test (niveau de gris)
Base de visages.
Images de 10 exemples de 40 visages pour l'apprentissage et le test (noir et blanc)
Visages N&B.


3. Préparation des données

On s'intéresse uniquement à la version n&b des visages. Charger l'image avec la fonction fournie par F. Cabestaing.

Quelle est la taille de chaque visage dans cette image?

Créez un tableau 3D contenant un empilement de tous les visages, que vous stockerez dans la variable "stackedFaces".

(Note : vous pourrez vous inspirer du code Scilab ci-dessous :

allFacesName="rdf-allFaces.png";
allFaces=im2bw(imread(allFacesName), 0.5);

// création de stackedFaces :
// Empilement des visages 40x33 dans une matrice stackedFaces 40x33x400
// Attention, exécution possiblement longue ~30 sec, pas de panique...)
stackedFaces=zeros(40,33,400); // numLignes, numColonnes, numFaces
for i=0:19
    for j=0:19
        stackedFaces(:,:, (i*20 + j + 1) ) = allFaces( 1+i*40 : (i+1)*40 , 1+j*33 : (j+1)*33 );
    end
end

4. Méthodologie

Nous avons maintenant l'ensemble des visages dans le tableau stackedFaces. La manière de procéder pour la construction de l'arbre est sensiblement identique à celle du jeu du pendu : à chaque noeud, la question du choix du prochain pixel à utiliser pour séparer l'ensemble des visages en 2 sous-ensembles (l'un pour les viages contenant ce pixel, l'autre pour les autres visages) se pose.

Comment choisir le "meilleur" pixel à chaque itération?

5. Différences avec le jeu du pendu

Le calcul de l'entropie est plus complexe que précédemment : on avait des exemples uniques par classe pour les mots du pendu. Il y a maintenant 10 images pour chaque visage (chaque classe).

Formulez à l'écrit le calcul de l'entropie pour le cas présent.

Note : on pourra passer par un vecteur I de booléen pour sélectionner les exemples qu'on utilise dans le calcul, i.e. (encore en Scilab, pour illustration) :

stackedFacesI=stackedFaces(:,:,I);

6. Réduction d'entropie

Pour un pixel donné (par exemple de coordonnées (12, 7)), calculez la variation d'entropie induite par le choix de ce pixel pour la séparation des données en 2 sous-ensembles. Pour cela, il vous faudra estimer l'entropie de l'ensemble courant des exemples.

Il vous sera utile de définir des tableaux "classCount" énumérant pour chaque indice le nombre d'exemples de la classe correspondante dans l'ensemble, et également sa normalisation "classRatio". Pensez également à créer un tableau "etiquettes" contenant pour chaque visage son étiquette, qui peut être un entier dans [1,40].

Créez le tableau deltaH qui contient, pour chaque pixel, la variation d'entropie équivalente (encore en Scilab, pour illustration) :

H - (pA*H_A) - (pB*H_B)

où pA (resp. pB) est la proportion de visages dans le sous-noeud gauche (resp. droit), et H_A (resp. H_B) est l'entropie du sous-noeud gauche (resp. droit).

7. Sélection de pixel

Nous pouvons maintenant définir la fonction de partage, qui prend en entrée un vecteur ligne I de booléens, et qui renvoie la coordonnée k du pixel associée au test le plus informatif pour le sous-ensemble de visages stackedFaces[,,I], ainsi que les vecteurs de booléens A et B associés à la partition de ce sous-ensemble (visage contenant le pixel pour A, sans le pixel pour B).

8. Induction de l'arbre

Construisez l'algorithme pour induire l'arbre, et déduisez la manière de classifier un nouveau visage.

Quelle performance peut-on espérer sur les exemples appris?