Apprentissage et Recherche par le Contenu Visuel.pdf

Apprentissage et Recherche par le Contenu Visuel de Catégories Sémantiques d'Objets Vidéo

Shuji ZHAO

Master 2 Informatique - parcours Images

Université Paris Descartes

Juillet 2007

Laboratoire des Equipes Traitement des Images et du Signal

CNRS UMR 8051

ENSEA

6 avenue du Ponceau 95014 Cergy-Pontoise, France

Encadré par: Frédéric PRECIOSO

REMERCIEMENTS

Je voudrais adresser mes sincères remerciements à Sylvie Philipp-Foliguet, Directrice de l’équipe MIDI du laboratoire ETIS, et à Frédéric Precioso, Responsable du stage, pour m’avoir accueilli très chaleureusement au sein du laboratoire, et pour avoir cru en mes capacités à mener ce travail à bien.

Frédéric Precioso a été un responsable de stage exemplaire. Il m’a apporté d’innombrables conseils précieux sur la recherche et les méthodes. Il m’a redonné confiance et encouragé pendant la période difficile où j’ai été malade. Grâce à lui j’ai pu rencontrer des spécialistes du domaine et participer à des séminaires m’ayant permis de découvrir les techniques les plus récentes.

Je voudrais aussi adresser toute ma reconnaissance à Inbar Fijalkow, Directrice du laboratoire ETIS, pour sa compréhension et sa gentillesse.

Par ailleurs, je remercie de tout cœur Matthieu Cord (laboratoire LIP6) pour ses conseils sur les méthodes à noyau, Jean-Emmanuel pour sa présentation sur la méthode d’AdaBoost, ainsi que toute l’équipe MIDI (Sylvie, Frédéric, Michel, Justine, Philippe-Henri, David) pour leurs conseils et les discussions concernant mon sujet. La très bonne ambiance et le dynamisme de l’équipe ont renforcé mon envie de poursuivre dans la voie de la recherche.

Mes remerciements s'adressent aussi à tous les professeurs qui m'ont encadré tout au long de cette année de master, spécialement Nicole Vincent, Nicolas Loménie, Florence Cloppet et Mohamed Cheriet pour leurs implications et pour tout le savoir dont ils m'ont imprégné.

Enfin, j’adresse de vifs remerciements à tous les ami(e)s qui ont pris soin de moi quand j’étais malade, et à ma famille pour être là, tout simplement.

Abstract:

During this internship, we focus on the problem of video semantic category learning and retrieval. Our framework associating both approaches – powerful visual feature extraction and statistical learning strategies – to carry out an efficient semantic class learning and retrieval system. Our approach is based on a new “definition” for video objects. Indeed, we will consider the spatiotemporal tube, containing several instances (one instance per frame of the shot sequence) of the extracted object of interest, identified and tracked, as one video object. In our context, the classification and learning methods will be applied on spatiotemporal tubes of detected people.

In this document, we will present our work of semantic category learning and retrieval of actor face in the film. We will detail in three parts: first, face detection, segmentation and tracking based on the algorithm AdaBoost (Chapter 2); second, visual feature extraction based on spatiotemporal tube description (Chapter 3); third, new kernel functions (kernel on sets, kernel on sequences) for learning and content-based retrieval (Chapter 4).

Résumé:

Durant ce stage, nous nous intéressons au problème de l’apprentissage et de la recherche de catégories sémantiques d’objets vidéo. Notre travail associe à la fois des méthodes puissantes et innovantes d’extraction de descripteurs visuels et des stratégies performantes d’apprentissage statistique, afin d’élaborer un système d’apprentissage et de recherche de catégories sémantiques. Notre approche est basée sur une nouvelle définition des objets vidéo. En effet, nous considérerons un tube spatio-temporel, contenant plusieurs instances (une par frame de la scène vidéo) de l’objet d’intérêt extrait, identifié et suivi, comme un unique objet vidéo. Dans notre contexte, les méthodes de classification et d’apprentissage seront appliquées aux tubes spatio-temporels de visages de personnes détectées.

Dans le cadre de ce stage, on se concentrera tout d'abord sur les catégories sémantiques correspondant à des visages d'acteurs de films. Ce stage est organisé suivant la réalisation de trois modules principaux: le premier concerne la détection, la segmentation et le suivi de visages dans le flux vidéo, basée sur l'algorithme AdaBoost (Chapitre 2) ; le deuxième module est dédié à l’extraction de caractéristiques visuelles à partir des tubes spatio-temporels (Chapitre 3) ; le troisième module s’intéresse aux méthodes à noyaux pour l’apprentissage et la recherche par le contenu sur les « tubes spatio-temporels » (Chapitre 4).

Mots clé

Catégorie sémantique, Détection d’objet, Segmentation, Reconnaissance de visage, Tube spatio-temporel, AFR, AdaBoost, Contour actif Splines, Gabor, HSV, SIFT, SVM, Méthodes à noyau, OpenCV

SOMMAIRE

1 Introduction ................................................................................................................... 1

1.1 Contexte................................................................................................................. 1 1.2 Etat d’art ................................................................................................................ 2

1.2.1 Challenges ......................................................................................................... 2 1.2.2 Détection du visage ........................................................................................... 2 1.2.3 Reconnaissance du visage ................................................................................. 3

1.3 Schéma général...................................................................................................... 4 2 Détection de visages...................................................................................................... 6

2.1 Introduction ........................................................................................................... 6 2.2 AdaBoost ............................................................................................................... 7

2.2.1 Descripteurs de Haar ......................................................................................... 7 2.2.2 Image Intégrale.................................................................................................. 9 2.2.3 Classifieur faible et classifieur fort ................................................................. 10 2.2.4 Cascade............................................................................................................ 12

2.3 Implémentation.................................................................................................... 14 2.3.1 OpenCV........................................................................................................... 14 2.3.2 Implémentation................................................................................................ 15 2.3.3 Résultat ............................................................................................................ 15

2.4 Discussion et perspective .................................................................................... 17 3 Extraction de caractéristiques...................................................................................... 19

3.1 Introduction ......................................................................................................... 19 3.2 Extraction de caractéristiques de la couleur ........................................................ 19

3.2.1 Espace de couleur HSV................................................................................... 19 3.2.2 Histogramme HS ............................................................................................. 20

3.3 Extraction de caractéristiques de la texture......................................................... 20 3.3.1 Filtre de Gabor................................................................................................. 21 3.3.2 Histogramme de Gabor Phase Patterns (HGPP) ............................................. 22 3.3.3 Histogramme de Gabor complexe................................................................... 25

3.4 Extraction de caractéristiques des points d’intérêt par SIFT............................... 26 3.4.1 SIFT................................................................................................................. 26 3.4.2 Implémentation................................................................................................ 29

3.5 Similarité sur les caractéristiques couleur et texture ........................................... 30

3.5.1 Distance 2χ .................................................................................................... 31 3.5.2 Distances des vecteurs de couleur et de texture .............................................. 31 3.5.3 Evaluation des caractéristiques .......................................................................33

3.6 Discussion et perspective .................................................................................... 34 4 Machines à noyaux...................................................................................................... 36

4.1 SVM .................................................................................................................... 36 4.2 Séparation linéaire............................................................................................... 36 4.3 Les fonctions noyaux........................................................................................... 38 4.4 Méthodes à noyaux pour discriminer les « tubes spatio-temporels ».................. 39 4.5 Discussion et perspective .................................................................................... 39

5 Conclusion générale .................................................................................................... 41 Bibliographie ....................................................................................................................... 42 Annexe 1: ............................................................................................................................ 45 Annexe 2: ............................................................................................................................ 46

- 1 -

1 Introduction

1.1 Contexte

Les contenus vidéo sont présents dans un nombre toujours croissant de domaines, tant scientifiques que commerciaux. Citons par exemple les applications de TV interactive, diffusion de contenus numériques, vidéo à la demande, simulations et entraînements, vidéo-conférences, etc., qui vont de paire avec le développement des matériels et infrastructures de communication nécessaires. Les limitations de la bande passante disponible pour l'accès à ces quantités de données vidéo nécessitent des techniques spécifiques pour l'administration des bases de données vidéo. De plus, les techniques actuelles de fouille d’archives multimédia ne permettent que la recherche par mots-clefs ou de méta-données. Or ce type de recherche ne permet d’accéder qu’aux données multimédia déjà annotées et surtout ne reflète pas toujours le contenu sémantique qu’un utilisateur pourrait vouloir retrouver. En effet, une séquence vidéo est une source d'information multimodale riche, contenant des données audio, parole, texte, couleurs et formes des objets présents dans l'image, et mouvements de ces objets. L'accès rapide au contenu vidéo est un sujet de recherche en pleine expansion. Des progrès considérables ont ainsi été effectués dans les quatre domaines fondamentaux permettant l'accès au contenu vidéo : l'analyse, la représentation, l’indexation et la recherche.

L’équipe « Masse de données et indexation multimédia » du laboratoire ETIS est impliquée dans les travaux sur les systèmes de recherche d'images et de vidéos par le contenu (« Content-Based Image and Video Retrieval », CBIVR). Le système RETIN, développé au sein de cette équipe, comporte pour l’instant deux modules : la segmentation automatique des séquences vidéo en plans, et le calcul pour chaque plan (« shot ») de différents attributs structurés en descripteurs, ou index. Ces index sont ensuite utilisés par le moteur de recherche pour comparer, classer, ordonner, etc., les plans.

Dans ce stage, nous nous intéressons à la segmentation et à la recherche des catégories sémantiques d’objets vidéo. Notre travail associe à la fois des méthodes puissantes et innovantes d’extraction de descripteurs visuels et des stratégies performantes d’apprentissage statistique, afin d’élaborer un système d’apprentissage et de recherche de catégories sémantiques. Notre approche est basée sur une nouvelle définition des objets vidéo. En effet, nous considérerons un tube spatio-temporel, contenant plusieurs instances (une par frame de la scène vidéo) de l’objet d’intérêt extrait, identifié et suivi, comme un unique objet vidéo. Dans notre contexte, les méthodes de classification et d’apprentissage seront appliquées aux tubes spatio-temporels de personnes détectées. Un tel projet nécessite la réalisation de trois modules principaux (Figure 1):

• Le premier concerne le partitionnement de la séquence vidéo en plans, considérés comme les primitives pour une analyse du contenu de plus haut niveau ;

• Le second module porte sur la détection, la segmentation, le suivi des personnes, dans ces plans, ainsi qu’une nouvelle approche d’extraction d’information visuelle basée sur la description en tubes spatio-temporels ;

• Le troisième module porte sur la conception et l’apprentissage de nouvelles fonctions noyaux, noyaux sur des ensembles, noyaux sur des séquences, afin d’obtenir des représentations pertinentes de similarité, une classification performante et des stratégies de recherche basées sur le contenu.

- 2 -

Figure 1 : Trois étapes de la recherche de catégories d’objets vidéo

Dans le cadre de ce stage, nous considérerons que le premier module est déjà existant (l’équipe ETIS a effectivement réalisé un prototype efficace) et on se concentrera tout d'abord sur les catégories sémantiques correspondant à des visages d'acteurs de films. Ce stage concerne la détection et la segmentation des visages dans le flux vidéo, l’extraction de caractéristiques visuelles pertinentes, l'apprentissage statistique pour identifier, traquer, et retrouver les visages dans des séquences vidéo.

1.2 Etat d’art

1.2.1 Challenges

Le principal problème dans la détection et la reconnaissance d’un objet est relatif aux différentes représentations possibles de celui-ci. Ainsi la détection et la reconnaissance du visage dépendent de plusieurs facteurs :

• La position : sur une image, un visage peut être vu de face, de profil, ou d’un angle quelconque.

• L’expression faciale : l’apparence d’un visage dépend aussi de son expression. • La présence d’attributs : une personne peut avoir un chapeau, des lunettes, une

moustache, une barbe, une cicatrice…. • Les conditions extérieures : la couleur, l’intensité, la taille, la texture sont différentes

sur chaque image. • L’occultation : une partie du visage peut être cachée par un autre objet ou une autre

personne.

1.2.2 Détection du visage

La détection de visage peut être définie comme : Etant donnée une image, le but est de déterminer si un ou des visages sont apparents dans l’image et s’il y en a, de localiser chacun des visages. Les techniques de la détection de visages sont développées et employées dans plusieurs domaines, surveillance, identification, biométrie, etc.

Les méthodes de la détection de visages peuvent être classifiées en quatre catégories, voir tableau 1 [Yang 2002] :

• Méthodes par a priori. Ces méthodes basées sur des règles tentent de modéliser la connaissance de ce qui caractérise un visage. Classiquement, ces règles représentent des relations en caractéristiques faciales.

• Approches par caractéristiques invariantes. Ces approches se basent sur des caractéristiques structurelles qui existent même quand la pose, le point de vue, ou les conditions d’illumination varient, et les utilisent pour localiser les visages.

• Méthodes basées modèles. Plusieurs modèles standard de visages sont utilisés pour définir un modèle de visage ou des modèles de caractéristiques faciales séparément.

Partitionnement de la vidéo en

plan-séquence

Machines à noyaux pour l’apprentissage et la recherche par le

contenu

Détection, segmentation, suivi d’objet et extraction

d'attributs

- 3 -

La corrélation entre une image présentée et la base des modèles est évaluée pour détecter la présence de visage.

• Méthodes par apprentissage. Par contraste avec les méthodes basées modèles, les modèles sont ici appris à partir d’un ensemble d’images d’apprentissage qui doivent permettre de caractériser la variabilité de l’apparence d’un visage. Ces modèles appris servent ensuite à la détection.

Tableau 1 : Catégories des méthodes de la détection de visage dans une image

Nous proposons dans notre travail une approche précise, robuste et rapide de détection et segmentation de visages dans les plans-séquences combinant les avantages de deux méthodes : un algorithme de détection d’objet AdaBoost [Viola 2001] devenu une référence de détection d’objet par ses qualités de rapidité suivi d’une segmentation précise et robuste basée sur des contours actifs [Precioso 2005] [Precioso 2004].

1.2.3 Reconnaissance du visage

Les réseaux de neurones (dans les années 1980), puis les machines à noyau (dans les années 1990), ont permis des avancées fondamentales dans le domaine de l'apprentissage artificiel. Depuis, les améliorations les plus significatives ont porté sur l'optimisation des représentations numériques et les techniques de régularisation. Un certain nombre de travaux [Gärtner 2003] [Kashima 2003] et de compétitions sont consacrés à l'extension des représentations vectorielles classiques, de manière à structurer de manière plus complexe les données. Les graphes et les ensembles de données sont des exemples de ces nouvelles représentations.

Dans plupart des travaux publiés, les plans sont représentés par une ou plusieurs images-clé (« key-frames »). De fait, plusieurs images clés peuvent être nécessaires dans le cas de zoom ou de mouvements de la caméra. La manière la plus usuelle d'extraire une image-clé est basée sur le « clustering » des images de chaque plan, l’image la plus proche de chaque centre de « cluster » étant retenue comme représentative.

Dans le travail de [Sivic 2005], les auteurs ont considéré l’ensemble de visages d’un tube

- 4 -

avec le calcul d’un histogramme pour déterminer la distribution « visual words » de l’ensemble de visages d’un tube.

Cependant, les méthodes d’indexation et de recherche d’information visuelle sur cette représentation du contenu de la vidéo sont celles existantes pour les images fixes et considèrent, la plupart du temps, l’information issue de l’image-clé dans sa globalité. La perte d’information est considérable. Pour remédier à cette limitation, nous proposons de considérer chaque plan comme un segment « spatio-temporel » composé de « tubes spatio-temporels », définissant donc les objets d'intérêt présents dans ce plan.

Après la détection et la segmentation dans la première étape, le suivi temporel des régions segmentées, nous permettra de définir les objets vidéo d’intérêt comme des tubes spatio-temporels d'objets d'intérêt. L'objectif sera alors de comparer ces tubes.

Pour chaque tube nous serons capable d’extraire à la fois des attributs locaux pertinents, tels que les points d’intérêt SIFT, et des attributs globaux robustes [Cámara Chávez 2006], tels que la couleur, la texture ou le mouvement, sans aucun prétraitement. En effet, grâce à notre segmentation précise, les tubes « spatio-temporels » ne comporteront que de l’information visuelle pertinente.

Une première représentation des données du tube – c'est-à-dire une première signature – sera donnée par le « sac » composé de tous les attributs extraits du tube. Nous pourrons nous intéresser, par la suite, à cette description des données contenues dans les tubes et considérer d’autres formes de représentation de ces données.

De nouvelles mesures de similarité doivent être définies afin de comparer ces signatures structurées, arbres et graphes d'adjacence. Les méthodes à noyaux renforcent les algorithmes de classification par apprentissage en déplaçant les calculs de similarité dans un espace vectoriel où la classification peut être linéaire [Rakotomamonjy, 2005]. Ces fonctions permettent de définir des similarités entre des objets plus complexes et même non vectoriels, tels que histogrammes ou ensembles d'histogrammes, graphes, etc. [Shawe-Taylor, 2004] [Suard, 2005].

Un grand nombre de travaux se sont intéressés récemment au calcul de vecteurs à partir des sacs avant leur comparaison. Arandjelovic et Zisserman [Arandjelovic 2005] ont proposé de modéliser l'information spatio-temporelle de chaque tube dans un vecteur unique. En utilisant un modèle des vecteurs tubes, Arandjelovic et Zisserman définissent explicitement la fonction d’injection. Une telle approche simplifie le problème, mais réduit également le champ des solutions. Au lieu de calculer un vecteur signature, le fait de travailler explicitement sur l'ensemble des attributs locaux constitue une alternative qui offre de nouvelles possibilités très intéressantes pour la comparaison et la classification de données [Kondor, 2003].

En s’inscrivant dans le cadre puissant de ces méthodes à noyaux, nous proposons de développer des solutions efficaces pour la reconnaissance de « tubes spatio-temporels ». Nous extrairons du tube spatio-temporel une séquence d'attributs structurés tels que mouvement, histogrammes couleurs, textures et ensembles de points d'intérêt. Chaque tube sera donc caractérisé par différentes séquences d'un attribut donné. Nous proposerons différentes méthodes pour construire des fonctions noyaux à partir des séquences.

1.3 Schéma général

Le travail de ce stage est organisé selon les étapes suivantes :

La première, la détection robuste et rapide d'objets d'intérêt, basée sur des adaptations

- 5 -

de l'algorithme AdaBoost. Cette partie sera détaillée dans le chapitre 2.

La seconde, la segmentation temporelle et suivi d'objets, basés sur des contours actifs splines 2D+t (cette partie est réalisée par Frédéric Precioso qui est spécialiste sur la méthode splines 2D+t).

Troisièmement, l’extraction d'attributs locaux (par exemple, descripteur SIFT autour de points d'intérêt) et d'attributs globaux (textures, couleurs, mouvements, etc.), ainsi que les mesures de la similarité. Cette partie sera détaillée dans le chapitre 3.

Finalement, la classification et apprentissage sur les « tubes spatio-temporels » et l’étude de différentes fonctions noyaux (Figure 2). Cette partie sera détaillée dans le chapitre 4.

Figure 2 : Schéma général de stage

Reconnaissance des acteurs

Vi

Vi

Vi

Détection des visages

Acteur ?

Segmentation et suivi des visages

Extraction de Caractéristiques

Classification des acteurs

Acteur 1

Acteur 2

Acteur n

Vecteur tube spatio-temporel

- 6 -

2 Détection de visages

2.1 Introduction

Dans l’étape de détection et de localisation des visages, nous proposons une approche par l’algorithme robuste et rapide basé sur la densité d’images, AdaBoost, qui combine des descripteurs simples (Haar feature) pour un classifieur fort.

La notion de Boosting était proposée en 1995 par Freund [Freund 1995]. L’algorithme Boosting utilise les hypothèses faibles (taux d’erreur ε < 0.5) des connaissances a priori pour construire une hypothèse forte. En 1996 Freund et Schapire ont proposé l’algorithme AdaBoost qui permit de choisir automatiquement les hypothèses faibles avec des poids adapté. AdaBoost ne dépend pas de connaissances a priori [Freund 1996].

En 2001, Viola et Jones ont appliqué l’algorithme AdaBoost dans la détection de visages pour la première fois. Avec des descripteurs simples (Haar feature), la méthode de calcul de valeur de descripteurs (l’image intégrale), la cascade des classifieurs, cette méthode est devenue une référence de détection de visage par ses qualités de rapidité et robustesse. La Figure 3 nous donne un des résultats du travail de [Viola 2001].

Figure 3 : Un des résultats de Viola & Jones 2001

En 2002, Lienhart et al. ont étendu les descripteurs Haar, expérimentés dans plusieurs l’algorithmes d’AdaBoost : Discrete Adaboost, Real Adaboost, Gentle Adaboost and Logitboost. Ces codes d’apprentissage et de détection par l’algorithme AdaBoost sont publiés dans la librairie de fonctions OpenCV (Open source Computer Vison) [Lienhart & Maydt 2002] [Lienhart et al. 2002].

L’algorithme Adaboost est désormais développé et amélioré dans plusieurs publications : [Viola 2003] ont utilisé cet algorithme pour toutes les poses et tous les angles de rotations de visages, aussi appelé Multi-View (Figure 4) ; [Viola 2005] ont appliqué cette méthode pour la détection de piéton, combinant les informations de mouvement et d’apparence (Figure 5) ; [Zhu 2006] utilisent les descripteurs des histogrammes de gradient orienté pour la détection de humains ou des vélos.

- 7 -

Figure 4 : Résultats de Viola & Jones 2003

Figure 5 : Un des résultats de Viola, Jones & Snow 2005

Dans notre travail nous avons appliqué l’algorithme « Gentle AdaBoost » à l’aide de la librairie de fonction OpenCV en utilisant deux cascades – « visage de face » et « visage de profil » -- pour détecter et localiser la plupart de visages dans les séquences vidéo.

2.2 AdaBoost

2.2.1 Descripteurs de Haar

Les valeurs d'un pixel ne nous informent que sur la luminance et la couleur d'un point donné. Il est donc plus judicieux de trouver des détecteurs fondés sur des caractéristiques plus globales de l'objet. C'est le cas des descripteurs de Haar [Viola 2001]. Les descripteurs de Haar sont des fonctions permettant de connaître la différence de contraste entre plusieurs régions rectangulaires contiguës dans une image. On code ainsi les contrastes existants dans un visage et les relations spatiales (Figure 6). En effet, ces descripteurs permettent de calculer la différence entre la somme des pixels dans les zones blanches et la somme des zones noires. La valeur de descripteur est calculée par :

(1) )Sum(r)Sum(r noire i,blanche i, −=if

- 8 -

Figure 6 : Descripteurs de Haar

Ces descripteurs sont calculés dans une fenêtre de taille fixe (ex. 24x24 pixels). Généralement, ils sont classifiés en 3 sortes : 2-rectangles, 3-rectangles et 4-rectangles descripteurs (Figure 7). Les 2-rectangles descripteurs sont utilisés horizontalement et verticalement (Figure 7A et B). Les régions blanches ont des poids positifs et les régions noires ont des poids négatifs.

Figure 7 : Descripteurs de Haar dans une fenêtre : 2-,3-,4-rectangles détecteurs.

Un descripteur de Haar est caractérisé par:

• le nombre de rectangles (2,3 ou 4)

• la position (le sommet supérieur gauche) (x,y) de chaque rectangle

• la largeur w et la hauteur h de chaque rectangle avec 0<x,x+w<W ; 0<y,y+h< H

• les poids positifs ou négatifs de chaque rectangle

Un exemple est donné sur la Figure 8.

- 9 -

Figure 8 : Définition d’un descripteur de Haar dans une fenêtre

Les descripteurs de Haar sont très simples mais très nombreux du fait des variations de taille et de position. Etant donné une fenêtre de résolution 24x24 pixels, on peut définir environ 160 000 détecteurs possibles dans cette fenêtre selon [Viola 2001], sans compter les descripteurs « 45 dégrées » proposés par [Lienhart et al. 2002]. Quelques exemples sont montrés dans la Figure 9. La nécessité de balayer pour chaque sous-fenêtre tous les pixels de l'image est un processus trop coûteux en temps. L’idée d’image intégrale est donc introduite afin d’accélérer le calcul.

Figure 9 : Exemples des descripteurs de Haar dans une fenêtre 24x24

2.2.2 Image Intégrale

L'image intégrale est une nouvelle représentation qui va permettre de calculer plus rapidement les attributs du descripteur. L'idée est de calculer seulement une fois la somme de tous les pixels de l'image [Viola 2001]. Le pixel à la position (x,y) de l'image intégrale contient la somme de tous les pixels, de l’image initiale, supérieurs et à gauche de la position (x,y) (voir Figure 10).

- 10 -

Figure 10 : Image Intégrale

Soient l’image intégrale ii(x,y) et l'image originale i(x,y), l' image intégrale s'obtient par :

(2)

Avec l’image intégrale, à partir de ii(x,y) n’importe quel rectangle de l’images peut être calculé avec 4 points:

– 2 = A + B

– 3 = A + C

– 4 = A + B + C + D

– D = 4 + 1 − (2 + 3)

au lieu de l’addition de touts les pixels de région D (Figure 11). Cela nous permet de réduire le calcul en temps constant.

Figure 11 : Calcul de la somme du rectangle D avec l'image intégrale

2.2.3 Classifieur faible et classifieur fort

Avec les descripteurs de Haar, on forme les classifieurs faibles. Un classifieur h(x), composé d'un descripteur f, d'un seuil θ, et d'une parité p, donne une prédiction sur la classe à qui appartient x (ici, 1 pour visage et 0 pour non visage).

(3)

L’algorithme d’AdaBoost vise à combiner plusieurs classifieurs faibles pour obtenir un classifieur fort plus efficace.

- 11 -

Le tableau 2 décrit l’algorithme d’AdaBoost [Viola 2001]. Etant donné les exemples négatifs et positifs, on initialise les poids de chaque exemple et on applique un processus de boosting : T itérations sélectionnant T classifieurs faibles ht(x) avec chacun un poids аt pour obtenir finalement un classifieurs fort C(x). Pour chaque itération, un classifieur est choisi en minimisant le taux d’erreur calculé avec les poids courrant des exemples. On augmente ensuite les poids des exemples mal classifiés pour la sélection suivante. L’itération se termine quand le taux de bonnes détections et le taux de faux positifs atteignent le compromis choisi au départ.

Tableau 2 : Algorithme AdaBoost

Les classifieurs de précision plus élevée (taux d’erreur entre 0.1 et 0.3) sont sélectionnés au début de l’apprentissage, et les classifieurs moins précis (taux d’erreur entre 0.4 et 0.5) sont sélectionnés dans les dernières itérations. La Figure 12 présente deux exemples de descripteurs les plus discriminants sélectionnés par AdaBoost à partir d'une base d'images de visages [Viola 2001]. Le premier descripteur caractérise la différence d'intensité entre la zone des yeux et la zone des pommettes. Le second descripteur mesure la différence

- 12 -

d'intensité entre les yeux et la zone au dessus du nez.

Figure 12 : Deux descripteurs de Haar les plus discriminants

2.2.4 Cascade

Pour réaliser un traitement efficace, il est nécessaire d'avoir l'avis de plusieurs classifieurs forts (Figure 13). Une cascade de classifieurs est un arbre de décision dégénéré dans laquelle, chaque étape est entraînée pour détecter un maximum d'objets intéressants tout en rejetant une certaine fraction des objets non-intéressants.

La structure de la cascade reflète le fait que l'image est constituée majoritairement de sous-fenêtres négatives. Une sous-image doit passer tous les classifieurs afin d'être acceptée comme visage. Le déclenchement de tous les classifieurs par un résultat positif devient ainsi un événement rare. Il faut que le nombre de sous-images éliminées dès les premières étapes de la cascade soit très élevé.

La cascade des classifieurs commence par un taux de détection de presque 100% mais avec un taux de faux positifs élevé. Il diminue rapidement avec quelques itérations. Ainsi on rejette immédiatement un grand nombre de régions négatives, donc cela accélère l’apprentissage et la détection.

Figure 13 : Cascade de classifieurs forts

Pour une cascade, le taux global de faux positifs (fenêtres négatives déclarées comme positives) est le produit du taux de faux positifs de chaque étape :

- 13 -

(4)

Le taux global de bonnes détections est défini selon la même formule :

(5)

Par exemple pour obtenir une cascade avec un taux global de bonne détection de 0.9 et un taux global de faux positifs de 6x10-6, on peut entraîner 10 étapes avec di=0.99 et fi=0.3.

Le tableau 3 décrit l’algorithme d’apprentissage par une cascade d’AdaBoost [Viola 2001]. Le taux maximum de faux positifs pour une étape f, le taux minimum de détection pour une étape d et le taux global de faux positifs acceptés Ftarget sont définis à l’entrée de l’apprentissage. Les étapes de la cascade sont construites par entraînements successifs de classifieurs avec AdaBoost puis ajustement de leur seuil afin de minimiser le nombre de faux positifs. Chaque étape est entraînée en ajoutant des classifieurs faibles jusqu'à ce que les taux de détection demandés soient atteints. Des étapes sont ajoutées à la cascade jusqu’à ce que les taux de la cascade entière soient atteints. Après chaque étape, on diminue l’ensemble d’exemples négatifs et on ne garde que les exemples mal classifiés pendant la dernière étape.

Tableau 3 : Algorithme d’apprentissage par une cascade d’AdaBoost

La présence d'un visage dans les images est très rare et la cascade complète est ainsi très rarement appliquée à une sous-image. La grande majorité des sous-images sont rejetées en échouant dès les premières étapes.

- 14 -

Figure 14 : Exemple d’une cascade pour la détectant un visage

Sur l'image de la Figure 14, les deux descripteurs faibles votent « visage » pour la sous-image en rectangle rouge. Après la décision, le classifieur fort 1 classe la sous-image dans le rectangle rouge comme un visage et la passe au classifieur fort 2 qui va, lui aussi, avec d'autres descripteurs indépendants des descripteurs précédents, valider « visage » ou non et on itère N fois. Par contre, la plupart des sous-images « visage » comme la sous-image dans le rectangle vert sont rejetés dans les premières étapes. Ainsi on réduit le nombre de faux positifs.

2.3 Implémentation

2.3.1 OpenCV

OpenCV (Open Source Computer Vision Library) est une librairie de traitement d'images et de vision par ordinateur en langage C/C++, proposée par Intel pour Windows et Linux. Cette bibliothèque propose un grand nombre d'opérateurs « classique » : création, lecture et écriture d'images, accès aux pixels, traitement d'images, apprentissage, détection de visages, suivi d'objet vidéo, etc.

Avec OpenCV, nous pouvons entraîner une cascade en format xml pour la détection de visage. Pour l’apprentissage, on donne les exemples d’exemples positifs et négatifs, c'est-à-dire, de visages et de non visages, et on définit le taux de faux positifs de chaque étape fi, le taux de bonne détection de chaque étape di et le taux global de faux positifs acceptés Ftarget.

Une fois la cascade réalisée, nous pouvons lancer la détection en configurant les paramètres d’entrée de la fonction « cvHaarDetectObjects » : nom d’image, nom de cascade, facteur d’échelle, taille minimale de sous-image, etc. La précision et la vitesse de la détection peuvent être assez différents selon la configuration initiale choisie.

AdaBoost1

N

Visage x 99% Non visage x 30%

1

1

0

0

0

0

Non visage x 70%

Visage x 90% Non visage x 0.00006%

1

1

1

0

1

0

AdaBoost2

1 0

Non visage x 21%

Visage x 98% Non visage x 9%

- 15 -

2.3.2 Implémentation

Nous avons lancé l'apprentissage sur une base de 1000 visages et 2000 négatifs pour avoir une cascade avec un taux final de faux positifs inférieur à 0.520. On obtient donc une cascade de 20 classifieurs forts avec chacun un taux de faux positifs inférieur à 0.5. On obtient une cascade que l'on met sous le format xml.

Il existe différents algorithmes de boosting, tels que Discrete Adaboost, Real Adaboost ou encore Gentle Adaboost mais nous retiendrons uniquement le dernier car c’est celui qui offre les meilleures performances pour la détection de visages selon [Viola 2001].

Nous avons appliqué notre propre cascade pour la détection de visage. Nous avons utilisé trois cascades de classifieurs pour les visages de faces et pour les visages de profil gauche et droit. Pour obtenir une bonne cascade, la banque d’objets d’apprentissage devrait être assez grande, entre 10 000 à 100 000.

2.3.3 Résultat

Nous avons appliqué notre programme de l'algorithme AdaBoost sur des images et des vidéos de différentes tailles. Quelques exemples des résultats sont montrés sur la Figure 15. Les ellipses rouges sont les visages de face, les ellipses vertes sont les visages de profil gauche, les ellipses bleues sont les visages de profil droit. L’algorithme donne des bons résultats sur la détection de visage.

Figure 15 : Détection de visages par AdaBoost

- 16 -

Afin de quantifier la précision de la détection, nous avons appliqué notre programme sur une banque de données « NRC-IIT Facial Video Database » [Dmitry 2005] (Figure 16). Les vidéos sont 160 x 120 pixels, compressés en AVI Intel codec avec bit-rate de 481 Kbps.

Cette base de données contient un certain nombre de séquences vidéo courtes en basse résolution encodées en mpeg1, chacune présentant le visage d’un utilisateur assis devant la camera bougeant (changements d’échelle et d’orientation) et « grimaçant » (changements d’expressions faciales). Le contexte étant celui d’une capture par webcam lors d’une video-conférence.

Figure 16 : Séquences vidéo de 160x120 de la base IIT-NRC

Les résultats sont présentés en tableau 4. Grâce aux cascades « profil », nos résultats sont meilleurs que ceux présentés dans [Dmitry 2005] pour la plupart des vidéos, mais l’augmentation du taux de bonne détection entraîne l’augmentation du taux de faux positifs pour certaines vidéos.

- 17 -

Tableau 4 : Résultats de détection sur la base NRC-IIT

Vidéo Nombre de frame

Visage à face

Profil gauche

Profil droit

Bonnes Détections /Faux Positifs

Résultat BD/FP de

[Dmitry 2005]

00-1 228 183 1 12 196/0 77/121

00-2 249 165 1 6 172/0 131/63

01-1 237 52 0 0 52/1 96/1

01-2 329 47 0 0 47/0 54/0

02-1 257 219 10 3 232/0 176/3

02-2 339 215 22 18 255/4 184/2

03-1 448 183 62 15 260/0 232/2

03-2 438 213 62 22 297/0 308/2

04-1 353 166 60 22 248/20 172/1

04-2 404 240 52 49 341/6 276/3

05-1 198 180 0 0 180/0 78/0

05-2 248 163 2 0 165/0 121/1

06-1 324 226 17 39 282/2 231/10

06-2 353 204 30 34 268/6 237/1

07-1 258 152 15 19 186/0 208/6

07-2 328 172 9 1 182/0 239/1

08-1 346 192 55 20 267/0 351/12

08-2 426 340 17 16 373/0 401/1

09-1 318 254 28 14 296/0 300/1

09-2 388 188 31 6 225/3 273/26

10-1 338 196 12 1 209/1 184/81

10-2 378 248 13 11 272/2 274/36

2.4 Discussion et perspective

Selon les résultats du programme d’AdaBoost avec trois cascades de classifieurs (visage de face, de profil gauche et de profil droit), cet algorithme est rapide et robuste pour détecter les visages de différentes expressions et différentes luminosités. La combinaison de trois cascades nous permet d’obtenir un taux de bonnes détections plus important.

Cependant, les visages détectés doivent être acquis de face, de profil et/ou avec une faible rotation centrale (au maximum ±30°). Certains visages ne sont pas détectés car ils ont une rotation trop importante. Pour contrer cet inconvénient, il faut enrichir la base d'images de différentes positions et rotations pour entraîner des cascades plus pertinentes. Une des solutions pourrait être un arbre de décision avant les cascades de toutes les poses [Viola 2003].

Le taux de bonnes détections des dernières étapes de la cascade est limité par l'emploi de classifieurs faibles. Le problème peut être résolu par l'ajout de classifieurs plus complexes que les classifieurs faibles dans les dernières étapes de la cascade, tel que les histogrammes de gradient orienté [Dalal 2005] [Zhu 2006], les filtres de Gabor [Shan 2004] [Chen 2004] ou l’emploi d’Eigenface [Turk 1991].

- 18 -

Après la détection de visages, nous avons essayé d’utiliser l’AdaBoost pour la détection des yeux et de la bouche :

• Le premier essai est d’utiliser la méthode d’AdaBoost avec une cascade « parojosEyes22x5.xml » proposée par Modesto Castrillón. La détection atteind de bons résultats sur les images de haute révolution, voir la Figure 17. Cependant, dans les cas de résolution faible, cette cascade n’arrive pas à trouver des yeux. Pour la détection de la bouche, nous n’avons pas encore trouvé une cascade performante.

Figure 17 : Détection des yeux par AdaBoost

• Le deuxième essai est d’utiliser la méthode de [Hsu 2001][Casiraghi 2003]) basée sur le « eyemap » et le « mouthmap » couleur. L’implémentation de cette méthode est en cours.

- 19 -

3 Extraction de caractéristiques

3.1 Introduction

Pour pouvoir apprendre les visages d’acteurs, maintenant que nous les avons localisés, il nous faut extraire des caractéristiques visuelles et établir des similarités sur ces caractéristiques suffisamment pertinentes. Nous avons actuellement étudié des caractéristiques de couleur comme les histogrammes HS, des caractéristiques texture comme les histogrammes de Gabor phase patterns et Gabor complexe, et des caractéristiques SIFT sur des points d’intérêt.

3.2 Extraction de caractéristiques de la couleur

3.2.1 Espace de couleur HSV

L’espace HSV (Hue, Saturation, Value) ou TSV (Teinte Saturation Valeur) est un espace colorimétrique, défini en fonction de ses trois composantes :

• Teinte (H) : le type de couleur. La valeur varie entre 0 et 360.

• Saturation (S) : l’« intensité » de la couleur. La valeur varie entre 0 et 100 %. Plus la saturation d'une couleur est faible, plus l'image sera « grisée » et plus elle apparaîtra fade, il est courant de définir la « désaturation » comme l'inverse de la saturation.

• Valeur (V) : la « brillance » de la couleur, elle varie entre 0 et 100%.

Dans OpenCV, la valeur H est normalisée en 0–180; les valeurs S et V sont normalisées en 0–255 (la Figure 18).

Figure 18 : Espace de couleur HSV

Le modèle HSV est une transformation non-linéaire de l'espace de couleur RVB. Il est défini dans OpenCV par la transformation ci-dessous :

- 20 -

3.2.2 Histogramme HS

L’espace de couleur HSV sépare les informations de couleurs en teinte, saturation et valeur. Ces informations peuvent être utilisées pour la reconnaissance de visage [Saxe 1996]. En considérant que la valeur de la « brillance » de la couleur est influencée par la condition extérieure, nous n’extrayons que les valeurs de H et S. Un histogramme 2D de la distribution de H-S est calculé pour chaque visage comme les caractéristiques couleurs. L’histogramme H-S est défini en 30 bins à l’axe H et 32 bins à l’axe S. Il peut être considéré comme un vecteur 960 composants pour l’apprentissage avec SVM. La Figure 19 donne un exemple de l’histogramme H-S d’un visage segmenté.

(a) (b) (c)

Figure 19 : Histogramme H-S (a) une frame (b) visage segmenté (c) Histogramme H-S

3.3 Extraction de caractéristiques de la texture

La texture est une caractéristique importante de l'apparence des objets dans des scènes réelles et la comprendre est une partie essentielle de la compréhension de la vision humaine. Une texture représente, à une échelle donnée, le même aspect quelle que soit la zone observée. Dans ces conditions, on considère l'image comme la réalisation d'un processus stochastique local et stationnaire. C'est-à-dire que chaque pixel est caractérisé par un petit voisinage et que cette caractérisation est la même pour tous les pixels de l'image.

De nombreuses approches de l'analyse de textures ou d’objets par attributs fréquentiels sont proposées : matrice de cooccurrence, dimension fractale, Transformation de Fourier, transformée en ondelettes, la pyramide laplacienne et la pyramide gaussienne. Nous avons adopté des méthodes d’ondelette de Gabor (proposé par David Gabor en 1946) pour l’extraction de caractéristiques de texture, car ils imitent le fonctionnement de certaines cellules spécialisées, localisées dans le cortex visuel primaire [Morizet 2006].

L’ondelette de Gabor caractérise la structure en spatial et en fréquentiel, et dans le même temps préserve les informations des relations spatiales. Elle est donc pertinente pour extraire le contenu fréquentiel orienté des patterns.

V = max(R,G,B)

S = (V-min(R,G,B))*255/V if V!=0, 0 otherwise

(G - B)*60/S, if V=R

H = 180+(B - R)*60/S, if V=G

240+(R - G)*60/S, if V=B

if H < 0 then H = H + 360

- 21 -

3.3.1 Filtre de Gabor

Les ondelettes (filtres) de Gabor sont des ondes sinusoïdales avec une fréquence et une orientation particulière modulée par une enveloppe gaussienne. [Zhang 2007]

(6)

où, , , , ,

, . Ici v est la fréquence (échelle) entre 0 et 4, u est l’orientation entre 0 et 7. La Figure 20 visualise une des filtres de Gabor en partie réelle et imaginaire. Ils ont une forme de « chapeau mexicain ».

(a) (b)

Figure 20 : Filtre de Gabor (a) réel (b) imaginaire

La Figure 21 présente les 40 filtres de Gabor de différentes fréquences et de différentes orientations par leur partie réelle et les modules de 5 fréquences [Zhang 2007].

Figure 21 : Filtre de Gabor (a) réel (b) module

La transformation de Gabor est la convolution complexe d’une image par un filtre de Gabor.

- 22 -

(7)

La Figure 22 donne les résultats de cette transformation, dans images des parties modules et des parties phases [Zhang 2007].

(a) (b)

Figure 22 : Transformation de Gabor (a) module (b) phase

Les recherches précédentes n’utilisent que la partie module, comme [Wiskott, 1997], [Zhang 2005], car les phases varient considérablement même dans des patterns locaux presque identiques et elles sont considérées comme des informations « inutiles » pour la reconnaissance d’objet.

Dans l’article [Zhang 2007], ils ont proposé une méthode de représentation de la texture pour la reconnaissance de visage, Histogramme de Gabor phase pattern (HGPP), basée sur la combinaison de l’histogramme spatiale et des informations de Gabor phase.

Nous commençons premièrement par la méthode d’Histogramme Gabor Phase Patterns (HGPP) [Zhang 2007] car elle donne le meilleur résultat pour la reconnaissance de visages selon cet article. La méthode HGPP sera détaillée dans 3.3.2.

Puis nous essayons notre propre méthode en considérant à la fois les informations de module et de phase, détaillée dans 3.3.3.

3.3.2 Histogramme de Gabor Phase Patterns (HGPP)

La méthode HGPP explore les informations de phase de Gabor par l’encodage de la partie réelle et de la partie imaginaire avec le codage QBC (Quadrant-bit codes) [Daugman 1993] et ensuite de l’opérateur LXP (Local XOR pattern). La mesure de la similarité sera donc basée sur l’histogramme de ces patterns.

(a) QBC (Quadrant-bit codes)

Le codage QBC calcule les patterns de phase de Gabor avec les formules suivantes :

(8)

On l’appelle « Quadrant-bit codes » car il sépare les convoluées de Gabor dans 4 quadrants dans l’espace complexe, 00 pour le quadrant I, 10 pour le quadrant II, 11 pour le quadrant III et 01 pour le quadrant IV, voir la Figure 23.

- 23 -

Figure 23 : Quadrant-bit codage de Gabor phase

A partir de QBC, on extrait deux sortes de Patterns : GGPP (Global Gabor Phase Patterns) et LGPP (Local Gabor Phase Patterns).

(b) GGPP (Global Gabor Phase Patterns)

Le pattern GGPP est un encodage d’informations globales d’orientations. Il combine les parties réelles (ou imaginaires) de QBC de toutes les orientations d’une fréquence, chacune un bit pour un pixel, dans une image de même taille d’image originale.

(9)

Ici k = 7, les 8 bits qui représentent 8 orientations forme un octet, c’est à dit, les pixels de 255 niveaux de gris dans une image. La Figure 24 nous montre les images de Patterns GGPP d’un visage, en 5 différentes fréquences.

Figure 24 : Patterns GGPP (a) réel (b) imaginaire

(c) LGPP (Local Gabor Phase Patterns)

Le pattern LGPP représente la variation locale de chaque pixel. Pour chaque orientation et chaque fréquence, la partie réelle (ou imaginaire) de LGPP encode la différence de signe d’un pixel et ses 8 voisins (Figure 25) par l’opérateur LXP (local XOR pattern) :

(10)

- 24 -

Figure 25 : Codage de LGPP

Les 8 bits qui représentent 8 voisins d’un pixel forment un octet (255 niveaux de gris) pour un pixel dans une image de même taille d’image originale. Toutes les orientations et toutes les fréquences forment 40 images de partie réelle du pattern LGPP, ainsi pour la partie imaginaire. (Figure 26)

Figure 26 : Patterns LGPP (a) réel (b) imaginaire

(d) HGPP (Histogram de Gabor Phase Patterns)

Finalement, les histogrammes de Gabor Phase Patterns sont formulés comme :

(11)

Il consiste en 4 parties :

(12)

Si le calcul de ces histogrammes est sur une image entière de visage, les informations locales seront perdues. La solution est de diviser l’image originale dans 8x8 sous-régions (Figure 27 a) et calculer les histogrammes de HGPP de toutes les sous-régions. En effet, chaque histogramme est un micro-pattern, en 16 bins.

En général, le schéma de HGPP est présenté dans la Figure 27 (b). Les images de visages sont normalisées en 128x128 pixels avant la convolution avec les filtres Gabor afin d’avoir le meilleur résultat selon Zhang et al.

- 25 -

(a) (b)

Figure 27 : (a) 8x8 sous-régions de GGPP (b) schéma général de HGPP

Nous avons utilisé la méthode de Zhang et al. pour extraire les patterns HGPP des images de visage. Le nombre de micro-patterns HGPP sont 5760 (5x2x64 + 5x8x2x64 = 5760), soit un vecteur de 92160 composantes (5760x16 = 92160).

Le nombre de composantes extraites de HGPP est très important. En plus, en raison de division de 64 sous-régions, le HGPP est sensible à la pose de visage. Cela était prouvé par notre expérimentation. Nous pouvons considérer à l’utiliser justement sur les points d’intérêt (ou les régions saillantes) au lieu de l’utiliser sur l’image entière.

3.3.3 Histogramme de Gabor complexe

Le HGPP considère que l’information de la phase de Gabor mais pas d’information sur le module de Gabor, nous proposons dans ce travail un nouveau pattern, Gabor complexe, qui considère à la fois la module et la phase de pattern de Gabor, c’est à dit, considère à la fois la partie réel et la partie imaginaire de l’image convoluée par Gabor. En s’inspirant de l’idée HGPP, nous construisons les histogrammes pour toutes les échelles et toutes les orientations de pattern de Gabor. Les différences sont suivantes :

• Les histogrammes de Gabor complexe calculent les distributions globales des informations textuelles, sans les diviser en sous-régions ;

• Ils considèrent à la fois les informations réelles et imaginaires dans 16 bins respectivement, au lieu de les encoder seulement en 0 et 1 ;

• Ils analysent la distribution des informations textuelles dans toutes combinaisons (couple) de valeur de partie réelle et imaginaire. Justement les régions qui ont les mêmes informations textuelles de la partie réelle et imaginaire sont considérées comme de même texture.

• Ils sont les histogrammes complexes 16x16, ou autrement dit les histogrammes 2D;

D’abord, les convolutions d’une image de visage par les 40 ondelettes de Gabor sont calculées, sur les parties réelles et imaginaires. Les résultats sont montrés dans Figure 28. Puis, les histogrammes de Gabor complexe sont calculés pour chaque coupe de patterns réel et imaginaire, 40 coupes de différentes fréquences et de différentes orientations. Le nombre de histogrammes de Gabor complexe pour une image sont 40, soit un vecteur de 10240 composantes (40x16x16=10240). Le nombre de composantes est relativement faible par apport à celui du HGPP (92160).

- 26 -

(a) (b)

Figure 28 : Descripteurs de Gabor (a) réel (b) imaginaire

3.4 Extraction de caractéristiques des points d’intérêt par SIFT

Dans les sections 3.2 et 3.3, les caractéristiques de couleur et de texture sont extraites. Cependant, pour la représentation pertinente de la signature d’un visage, des points d’intérêt ou des régions saillantes devront être détectés et localisés afin d’obtenir les informations plus précises des nuances entre des personnes différentes.

Une approche représentative pour caractériser les informations des points d’intérêt est la méthode SIFT (Scale-Invariant Feature Transform) proposée et développée par David Lowe [Lowe 1999] [Lowe 2004]. SIFT est un algorithme qui permet de détecter des points d’intérêt et d’extraire des caractéristiques distinctives de ces points pour la reconnaissance d’objet. Les caractéristiques de SIFT sont invariantes à l’échelle et à la rotation, ce qui joue un rôle très important pour la reconnaissance des visages d’acteurs dans les séquences vidéo. Des travaux précédents ont utilisé cet algorithme pour la reconnaissance de visage [Sivic 2005]. Dans notre travail, nous avons utilisé SIFT à la fois pour détecter des points d’intérêt de visages, yeux, bouche, nez, etc., et pour extraire des caractéristiques autour de ces points

3.4.1 SIFT

La détection et l’extraction de caractéristiques sur les points d’intérêt se déroulent en quatre étapes :

• détection d’extrema d’espace-échelle (“scale-space”),

• localisation des points d’intérêt,

• choix de l’orientation des descripteurs,

• calcul des descripteurs.

Pour la première étape de détection d’extrema d’espace-échelle, l’image est convoluée avec un noyau gaussien. L’espace-échelle d’une image est donc défini par la fonction :

),(),,(),,( yxIyxGyxL ∗= σσ

où I(x, y) est l’image originale et

222 2/)(22

1),,( σ

πσσ yxeyxG +−=

- 27 -

A une normalisation près, cela revient à résoudre ∂I/∂σ=∆I, où ∆I représente le Laplacien de I.

La Figure 29 nous montre les images Gaussiennes groupées par quatre octaves. De gauche à droite, l’échelle augment. De haut à bas, la taille d’image divisée par deux.

Figure 29 : Images Gaussiennes groupées par octaves

La présélection des points d’intérêt et de leur échelle est faite en détectant les extrema locaux des différences de gaussiennes (Figure 30):

),()),,(),,((),,( yxIyxGkyxGyxD ∗−= σσσ ),,(),,( σσ yxLkyxL −=

Notons que D(x,y,σ) ≈ (k – 1) ∆I lorsque k→1.

Figure 30 : Différences de gaussiennes

- 28 -

Les extrema sont recherchés dans de petits voisinages en position et en échelle (typiquement 3 x 3 x 3) (Figure 31).

Figure 31 : Recherche des extrema

Une étape d’interpolation a pour but d’améliorer la localisation des points d’intérêt en espace et en échelle. Puis une analyse des rapports des valeurs propres de la matrice hessienne 2 x 2 permet d’éliminer les points d’intérêt situés dans des zones insuffisamment contrastées ou sur des bords présentant une courbure trop faible.

L’étape suivante consiste à assigner à chaque point une orientation. Cette orientation correspond à l’orientation majoritaire des gradients spatiaux d’intensité calculés dans un voisinage du point d’intérêt à l’échelle préalablement déterminée. Un point d’intérêt peut se voir associer plusieurs orientations. Cela entraîne par la suite une redondance des descripteurs.

Finalement, pour une position, une échelle et une orientation données, chaque point d’intérêt se voit associer un descripteur. Pour chaque image, la norme du gradient spatial m(x,y) et l’orientation du gradient spatial θ(x,y) correspondants à cette échelle sont calculées :

Le descripteur est constitué d’histogrammes d’orientation du gradient spatial d’intensité pondérés par la norme du gradient spatial (Figure 32).

Figure 32 : Vecteur de descripteur des points d’intérêt

En effet, le voisinage du point d’intérêt dont la taille dépend de l’échelle subit un

- 29 -

découpage 4 x 4 en blocs. Pour chaque bloc, un histogramme à 8 niveaux de quantification résume les orientations du gradient spatial d’intensité à l’intérieur du bloc. Le descripteur SIFT est donc un vecteur à 4 x 4 x 8 = 128 coordonnées.

3.4.2 Implémentation

Pour l’implémentation de SIFT, nous avons utilisé les codes « SIFT++ » de Andrea Vedaldi de l’ Université de California en 2006, qui est une implémentation de l’algorithme des détecteurs et descripteurs SIFT en C++ basée sur l’article [Lowe 2004]. Nous l’avons utilisé, à la fois pour détecter des points d’intérêt au sein des images de visages et pour appliquer le descripteur SIFT aux zones détectées.

Le premier essai est de configurer différents paramètres (échelle de premier octave, seuil de contraste, seuil de bord, etc.) sur des images de visages (Figure 33). Le nombre de points détectés est différent selon les paramètres configurés.

(a) (b) (c)

Figure 33 : Détection des points d’intérêt par SIFT en différents paramètres (a) fist-octave = -1, threshold = 0.007, edgeThreshold = 10

(b) fist-octave = 0, threshold = 0.02, edgeThreshold = 5 (c) fist-octave = 0, threshold = 0.03, edgeThreshold = 5

Avec les mêmes paramètres comme Figure 33 (c), nous avons détecté des points d’intérêt des images de visages de différentes échelles et de différentes positions (orientations) voir la Figure 34. Après une étude sur les points d’intérêt décrites sur la Figure 34, nous avons remarqué qu’on arrive à peu près tout le temps à avoir un ou les deux yeux, la bouche et/ou le nez, qui sont les points d’intérêt que nous recherchons.

Figure 34 : Détection des points d’intérêt par SIFT en différentes images

- 30 -

Pour l’extraction des caractéristiques sur les points d’intérêt, on obtient un fichier *.key qui contient les vecteurs des descripteurs SIFT pour chaque point détecté, représentant le coordonnées x et y, échelle, orientation, et les 128 composants des descripteurs SIFT.

Pour évaluer les vecteurs extraits par SIFT, quatre images de même visage en différentes échelles et différentes rotations sont calculées, comme montrées sur la Figure 35, les points d’intérêt détectés sont relativement stables, robustes, sur le même visage en différentes échelles et différentes rotations.

(a) (b) (c) (d)

Figure 35 : Détection des points d’intérêt par SIFT en différentes échelles et différentes rotations

Tableau 5 : Comparaison des descripteurs SIFT

image PI(x) PI(y) échelle orientation (de 0 à 8)

128 composants des descripteurs SIFT

(a) 54.52 73.08 5.39 3.259 0 12 43 31 3 0 0 0 23 62 17 0 0 0 0 0 155 17 0 …

(b) 26.98 36.26 2.65 3.251 0 13 45 29 2 0 0 0 22 64 16 0 0 0 0 0 154 17 0…

(c) 154.00 54.58 5.41 4.812 0 12 43 33 3 0 0 0 21 63 18 0 0 0 0 0 153 17 0…

(d) 76.72 26.95 2.66 4.815 0 13 46 29 2 0 0 0 21 65 16 0 0 0 0 0 153 17 0…

Une étude sur les 128 composants des descripteurs SIFT sur le Tableau 5 nous montre la invariabilité sur les points d’intérêt marqués en croix jaune des quatre images de la Figure 35. Les descripteurs SIFT pourraient être discriminants pour la reconnaissance de visages de différents acteurs dans des vidéos.

3.5 Similarité sur les caractéristiques couleur et texture

Dans cette section, nous avons calculé la similarité entre les caractéristiques couleur et texture uniquement, pour évaluer la performance de ces caractéristiques extraites.

Jusqu’à maintenant, nous avons extrait des caractéristiques de couleur et de texture sous la forme des vecteurs suivants :

• 960 vecteurs de couleur HS

• 92160 vecteurs de Gabor HGPP

- 31 -

• 10240 vecteurs de Gabor complexe

Nous avons segmenté les visages des acteurs (actrices) à partir d’une séquence vidéo « Prison Break » de Brett Ratner. Nous avons obtenu 1174 images des visages de 40 tubes de 5 acteurs (actrices). Les vecteurs de couleur HS, de Gabor HGPP, et de Gabor complexe sont extraits des images des visages. Les vecteurs ont été uniformément normalisés entre 0 et 1.

Afin d’évaluer les performances de ces vecteurs, nous avons utilisé la distance 2χ (comme un premier essai de distance de similarité) qui a été utilisée dans le travail de [Sivic 2005] pour comparer la similarité de deux histogrammes de « visual words » pour la reconnaissance de visages.

3.5.1 Distance 2χ

La distance 2χ est calculée par l’équation suivante:

(13)

où, p et q sont deux histogrammes à comparer, pk et qk sont les valeurs du kième bin des histogrammes p et q respectivement, s est le nombre de bins de ces histogrammes. 2χ (p, q) représente la dissimilarité de deux histogrammes. La valeur est entre 0 et 2, soit 0 quand p = q et 2 quand p et q sont « complètement différents ».

3.5.2 Distances des vecteurs de couleur et de texture

Nous avons effectué le calcul des distances sur 7 tubes de 2 acteurs extrait du film « prison break », soit 326 visages, voir tableau 6:

Tableau 6 : Tubes de visages à calculer

Acteur Tube Nombre de visages

A A02 32

A A05 61

A A06 29

A A10 39

B B06 59

B B07 40

B B15 66

Total 326

(a) Distances des visages de même tube

Nous avons d’abord calculé les distances des visages de même tube. Soit n nombre de

visages d’un tube, le nombre de coupes de visages est ∑−

=

1

1

n

i

i (Figure 36).

- 32 -

Figure 36 : Les couples des visages de même tube à comparer

Comme décrit dans le tableau 7, les 7 tubes de visages ont 8109 coupes à comparer.

Tableau 7 : Comparaisons des visages de même tube

Tube Nombre de visages Nombre de comparaisons

A02 32 496

A05 61 1830

A06 29 406

A10 39 741

B06 59 1711

B07 40 780

B15 66 2145

Total 326 8109

Les moyennes et des écart-types des distances 2χ des 8109 coupes de visages sont calculées et montrés dans le tableau 8.

Tableau 8 : Distances des 8109 coupes de visages de même tube

Vecteur Couleur HS Gabor HGPP Gabor complexe

Distances 0,0940 ± 0,0741 0,0496 ± 0,0116 0,2037 ± 0,1544

(b) Distances des visages de 2 tubes

Les distances des visages de 2 différents tubes sont calculées entre toutes les coupes possibles des visages des 2 tubes. Soit n le nombre de visages d’un tube, m le nombre de visages d’autre tube, le nombre de coupes de visages entre 2 tubes est n x m (Figure 37).

Figure 37 : Les couples des visages de 2 tubes à comparer

- 33 -

Nous considérons d’abord les distances des visages de 2 tubes de mêmes acteurs. Comme décrit dans le tableau 9, on a 9042 coupes de visages à comparer.

Tableau 9 : Comparaisons des visages de 2 tubes de mêmes acteurs

Tube 1 Tube 2 Nombre de visages de tube 1

Nombre de visages de tube 2

Nombre de comparaisons

A02 A05 32 61 1952

A06 A10 29 39 1131

B06 B07 59 40 2360

B06 B08 59 61 3599

Total 9042

Les moyennes et des écart-types des distances 2χ des 9042 coupes de visages sont calculées et montrés dans le tableau 10.

Tableau 10 : Distances des 9042 coupes de visages de 2 tubes de mêmes acteurs


Distances 0,4639 ± 0,3656 0,0703 ± 0,0068 0,3821 ± 0,1508

Idem, le tableau 11 décrit le nombre de coupes de visages à comparer, et le tableau 12 décrit les distances 2χ des 8577coupes de visages comparés.

Tableau 11 : Comparaisons des visages de 2 tubes de différents acteurs

Tube 1 Tube 2 Nombre de visages de tube 1

Nombre de visages de tube 2

Nombre de comparaisons

A02 B07 32 40 1280

A05 B15 61 66 4026

A06 B06 29 59 1711

A10 B07 39 40 1560

Total 8577

Tableau 12 : Distances des 8577 coupes de visages de 2 tubes de différents acteurs


Distances 1,1274 ± 0,2837 0,0731 ± 0,0043 0,4452 ± 0,1601

3.5.3 Evaluation des caractéristiques

Selon les résultats de 3.4.2, les distributions des distances sont décrites dans la Figure 38.

- 34 -

0,0940 ± 0,0741 0,4639 ± 0,3656

Attribut couleur HS

1,1274 ± 0,2837

0,0496 ± 0,0116 0,0703 ± 0,0068 0,0731 ± 0,0043

Attribut texture HGPP

0,2037 ± 0,1544 0,3821 ± 0,1508 0,4452 ± 0,1601

Attribut texture Gabor complexe

Distance de même tube

Distance de 2 tube mêmes acteurs

Distance de 2 tube différents acteursN

bre

de

com

par

aiso

ns

distance

distance

distance

Nbre

de

com

par

aiso

ns

Nbre

de

com

par

aiso

ns

0,0940 ± 0,0741 0,4639 ± 0,3656

Attribut couleur HS

1,1274 ± 0,2837

0,0496 ± 0,0116 0,0703 ± 0,0068 0,0731 ± 0,0043

Attribut texture HGPP

0,2037 ± 0,1544 0,3821 ± 0,1508 0,4452 ± 0,1601

Attribut texture Gabor complexe



Distance de 2 tube différents acteurs



Distance de 2 tube différents acteursN

bre

de

com

par

aiso

ns

distance

distance

distance

Nbre

de

com

par

aiso

ns

Nbre

de

com

par

aiso

ns

Figure 38 : Distributions des distances entre vecteurs

Les informations données par les distances sur la couleur sont plus aisément séparables que celles sur la texture. Les algorithmes pour la texture n’offrent pas de grandes différences dans les résultats pour la classification des classes. En revanche, le descripteur HGPP produit des vecteurs de plus grande dimension (9 fois plus que la méthode Gabor complexe) ce qui réduit l’efficacité de l’algorithme. De fait, nous pourrons l’utiliser plutôt pour la description de régions autour de points d’intérêt (ou les régions saillantes) au lieu de l’utiliser sur l’image entière.

Dans cet essai de l’évaluation, les vecteurs sont normalisés entre 0 et 1 avec une normalisation uniforme. Cette normalisation n’est pas performante pour la classification des catégories d’objets. En effet, une normalisation uniforme ne reflète pas la variabilité de la base de données que nous traitons. Nous allons plutôt réaliser une quantification des vecteurs de caractéristiques dédiée à la base. Une telle approche a déjà montré toute sa puissance dans l’implémentation du système d’indexation d’images (RETIN) du laboratoire ETIS.

Enfin, l’évaluation des caractéristiques sur seulement quelques tubes et quelques acteurs n’est pas suffisante. Plus de vecteurs devront être extraits pour améliorer l’apprentissage. Une des principales difficultés que nous avons déjà rencontrée et à laquelle nous devrons trouver une solution est l’absence de base de données de référence pour notre problématique.


Dans notre travail d’extraction, nous avons extrait des caractéristiques de la couleur de l’espace HS et des caractéristiques de la texture basée sur les ondelettes de Gabor. Dans notre 2ème phrase d’étude sur l’évaluation des caractéristiques couleur et texture, nous avons noté qu’une seule caractéristique ne peut pas être capable de distinguer les visages des

- 35 -

acteurs. Comme montré sur le tableau 13, l’intervalle des mesures de similarités entre des vecteurs de deux tubes du même acteur et entre des vecteurs de deux tubes de deux acteurs différents se chevauchent pour les caractéristiques couleur et texture (voir les chiffres en gras dans le tableau ci-dessous). Pour avoir un meilleur résultat, il faut combiner plusieurs caractéristiques extraites des images de visages dans une vidéo.

Tableau 13 : Distances entre vecteurs

Tube Nbr visages

Nbr comparaisons

Dis HS Dis HGPP Dis Gabor Complexe

A02 32 496 0.0560±0.0298 0.0544±0.0129 0.1695±0.0532

A05 61 1830 0.1014±0.0822 0.0477±0.0094 0.1292±0.0663

A06 29 406 0.0913±0.0421 0.0564±0.0107 0.2672±0.0956

A10 39 741 0.0546±0.0195 0.0404±0.0075 0.1094±0.0434

B06 59 1711 0.1644±0.0951 0.0602±0.0110 0.3881±0.2126

B07 40 780 0.0766±0.0417 0.0514±0.0081 0.2406±0.1012

1 tube, 1

acteur

B15 66 2145 0.0607±0.0204 0.0430±0.0070 0.1352±0.0492

A02A05 32/61 1952 1.1118±0.0958 0.0752±0.0032 0.2206±0.0404

A06A10 29/39 1131 0.4946±0.0375 0.0736±0.0022 0.5257±0.0934

B06B07 59/40 2360 0.1562±0.0863 0.0628±0.0056 0.3478±0.1780

2 tubes,

1 acteurs

B06B08 59/61 3599 0.3046±0.1007 0.0714±0.0059 0.4471±0.0841

A02B07 32/40 1280 0.5033±0.1106 0.0810±0.0020 0.6430±0.0721

A05B15 61/66 4026 1.1782±0.0773 0.0709±0.0024 0.3189±0.0475

A06B06 29/59 1711 1.2279±0.0470 0.0744±0.0028 0.4175±0.1195

2 tubes,

2 acteurs

A10B07 39/40 1560 1.3980±0.0640 0.0710±0.0020 0.6394±0.0583

Pour la représentation pertinente de la signature d’un visage, le descripteur SIFT, qui permet d’extraire des caractéristiques invariantes à l’échelle et à la rotation d’objet, est appliqué pour détecter des points d’intérêt de visages et pour extraire des caractéristiques autour de ces points. Cependant, les régions saillantes (yeux, bouche, nez, etc.) ne sont pas encore précisément localisées. De nouveaux descripteurs des caractéristiques des points d’intérêt, comme PCA-SIFT [Ke 2004] et SURF [Bay 2006], pourraient être étudié dans la suite du travail. En plus, le suivi des points d’intérêt pourrait aussi favoriser l’interprétation d’un tube de visages.

- 36 -

4 Machines à noyaux

4.1 SVM

Une machine à vecteurs de support ou séparateur à vaste marge (en anglais Support Vector Machine ou SVM) est une technique de discrimination. Elle consiste à séparer deux (ou plus) ensembles de points par un hyperplan. Selon les cas et la configuration des points, la performance de la machine à vecteurs de support peut être supérieure à celle d'un réseau de neurones ou d'un modèle de mixture gaussienne. Plusieurs applications sur la détection de visages et la reconnaissance de visages sont effectuées [Osuna1997] [Guo 2001] [Casiraghi 2003] [Sivic 2005] [Arandjelovic 2005].

Un SVM, comme un perceptron, trouve un séparateur linéaire entre les points de données de deux classes différentes. En général, il peut y avoir plusieurs séparateurs possibles entre les classes (en supposant le problème linéairement séparable) et un perceptron n'a pas de préférence parmi celles-ci. Dans les SVMs, cependant, nous faisons un choix particulier parmi tous les séparateurs possibles : nous voulons celui avec la “marge” maximale. Dans les SVMs, cependant, nous faisons un choix particulier parmi tous les séparateurs possibles : nous voulons celui avec la « marge » maximale.

Nous considérons d’abord les cas de la séparation linéaire dans la section 4.2. Pour les cas de la séparation non-linéaire, les méthodes à noyau seront introduites en section 4.3.

4.2 Séparation linéaire

La tâche de discrimination est de trouver un hyperplan qui sépare deux (ou plus) ensembles de vecteurs (Figure 39). Pour la détection et la reconnaissance de visages, ces deux classes peuvent être visage ou non-visage, actrice « Julia Roberts » ou « non- Julia Roberts ».

Margemaximale

Hyperplan

optimal

Hyperplanvalide

D(x) = 0

D(x) = +1

D(x) = -1

Vecteursde support

D(x) > 1

D(x) < -1

w

1

w

Figure 39 : Séparateur à vaste marge

La fonction linéaire de l’hyperplan :

(14) 0 . =+ bw x

- 37 -

où, x est le vecteur d'exemple.

Les deux hyperplans sur les frontières de deux ensembles de vecteurs sont sous forme canonique :

(15)

La distance d’un point à l’hyperplan est :

(16)

L’hyperplan optimal est celui pour lequel la distance aux points les plus proches (marge) est maximale. Cette distance vaut 2/||w||. Maximiser la marge revient donc à minimiser ||w|| sous contraintes:

(17)

où, y est l’étiquette de classe, 1 et -1 par exemple.

L'approche classique pour réaliser une telle minimisation en présence de contraintes est « la méthode des multiplicateurs de Lagrange ». L'approche basique implique la définition d'une nouvelle fonction L qui combine la fonction initiale à minimiser et les fonctions contraintes, chacune proportionnelle à une nouvelle variable, appelée multiplicateur de Lagrange. Dans notre cas, nous avons choisi d'appeler ces multiplicateurs αααα i. Dans notre cas, puisque les contraintes sont positives, les multiplicateurs de Lagrange doivent être tous positifs aussi.

(18)

où, n est le nombre d'exemples.

Maintenant, nous pouvons essayer de trouver les valeurs de w, w0, α qui minimisent L. On fait alors l’hypothèse que le minimum global est atteint quand les dérivées partielles de L par rapport à chacune de ses variables sont nulles. Si nous différencions L par rapport au vecteur des poids w, nous obtenons une expression simple qui, quand elle est fixée à 0, nous donne la valeur w* comme une combinaison linéaire des points xi (les exemples), des étiquettes yi et des multiplicateurs de Lagrange α i. On peut noter ici que ce résultat est très important, pusiqu’il nous informe que le vecteur de poids final qui définit la normale à l'hyperplan de séparation SVM peut s'écrire comme la somme pondérée des points d'apprentissage. Les poids sont précisément les multiplicateurs de Lagrange.

En différentiant par rapport à w0, on obtient une nouvelle contrainte – selon laquelle la somme des multiplicateurs de Lagrange (chacun multiplié par l’étiquette du point correspondant) est égal à 0. Dans la plupart des cas, nous pouvons juste considérer que w0 est nul et tout à fait négliger cette contrainte.

En substituant les résultats obtenus par l’annulation des dérivées partielles de L dans l’équation (18), on peut exprimer la minimisation de L dans sa forme duale (principe de Dualité de Wolfe), ainsi nous obtenons la maximisation donnée par l’expression suivante en terme des αi et des exemples xi d'apprentissage.

w

xwx 0 .

)(w

d+

=

≥−+∀ 0 1 ).(

min

0

2

2

1

wii xwyi

w

1 . ±=+ bw x

- 38 -

(19)

On remarquera que dans cette expression les points de données (ou exemples) n’apparaissent que comme produits scalaires avec d'autres points de données, ainsi tout ce dont nous avons besoin de connaître sur les données est l'ensemble des n2 valeurs scalaires résultants de ces produits scalaires. Ces n² valeurs sont souvent stockées dans une matrice : la matrice de Gram.

Une observation importante sur les valeurs optimales des αi est que seuls les points de données sur l'hyperplan de séparation auront des valeurs non-nulles pour les αi. Donc seuls les points avec une distance minimum à l'hyperplan de séparation, appelés vecteurs de support (Figure 39) , sont essentiels pour définir l'équation de l’hyperplan séparateur.

Avec les valeurs optimales de w0 et des αi en main, et la connaissance de la définition de w, nous avons maintenant un classifieur que nous pouvons utiliser sur des points inconnus. On rappelle, une fois de plus que l'unique chose dont nous avons besoin sont les produits scalaires du point inconnu avec les points exemples connus. Par la programmation quadratique, la solution de ce problème peut etre trouvée :

(20)

où, ns est le nombre de points de support, u est un point inconnu à classifier.

4.3 Les fonctions noyaux

Les méthodes à noyaux renforcent les algorithmes de classification par apprentissage, comme les SVMs (« Support Vector Machines » ou « Séparateurs à Vaste Marge ») que nous utiliserons ici, en déplaçant les calculs de similarité dans un espace vectoriel où la classification peut être linéaire. Ces fonctions permettent de définir des similarités entre des objets plus complexes et même non vectoriels, tels qu’histogrammes ou ensembles d'histogrammes, graphes, etc. En effet, dans le cas où l’on veut représenter l’information sous une forme complexe, les données ne peuvent pas être séparées linéairement. Au lieu de chercher un hyperplan dans l'espace des entrées, on passe dans un espace de représentation intermédiaire (feature space) de grande dimension où les données peuvent être séparées linéairement par un hyperplan. Le « passage » dans l’espace de représentation des caractéristiques se fait par le biais d’une injection :

(21)

On doit donc résoudre maintenant :

(22)

avec la solution :

(23)

Le problème et sa solution ne dépendent que des produits scalaires )'()( xxi Φ⋅Φ . Plutôt

))()(()(1

* buxysignuh sn

i iii +Φ⋅Φ= ∑ =α

)()(1

buxysignuh sn

i iii +⋅= ∑ =α

- 39 -

que de choisir la transformation non-linéaire , on choisit une fonction appelée fonction noyau.

)'()()',( xxxxk i Φ⋅Φ= (24)

Elle représente un produit scalaire dans l'espace de représentation intermédiaire. Elle traduit donc la répartition des exemples dans cet espace. Lorsque k est bien choisie, on n'a pas besoin de calculer la représentation des exemples dans cet espace pour calculer cette fonction. Le noyau matérialise une notion de proximité adaptée au problème.

Voici quelques exemples de fonctions noyaux :

• Linéaire : ')',( xxxxk ⋅=

• Polynomial : dxxxxk )'()',( ⋅= ou

dxxcxxk )'()',( ⋅+=

• Gaussien : 22

/')',( σxxexxk −−=

• Laplacien : 2/')',( σxxexxk −−=

Le noyau gaussien peut être étendu comme 22 /)'()',( σxxdexxk −−= , où d(x-x’) est une

distance, par exemple distance 2χ .

Le noyau peut être composé de plusieurs noyaux pour obtenir un noyau plus robuste. par exemple :

∑= )',()',( xxkxxk iiα (25)

4.4 Méthodes à noyaux pour discriminer les « tubes spatio-temporels »

Dans le chapitre 3, nous avons des vecteurs (le plus souvent sous forme d’histogrammes) de caractéristiques extraits des tubes spatio-temporels. Une première représentation des données du tube – c'est-à-dire une première signature – est donnée par le « sac » composé de tous les attributs extraits du tube. Notre but est de trouver des mesures de similaritéafin de comparer ces signatures structurées.

Jusqu’à présent, dans le domaine de la reconnaissance de visages, un grand nombre de travaux se sont intéressés récemment au calcul de vecteurs à partir des sacs avant leur comparaison, ou au calcul de vecteurs à partir de la probabilité de la distribution de vecteurs dans les sacs [Sivic 2005]. Les méthodes actuelles sont basées sur la simplification de la représentation à un unique vecteur (par moyennage ou post-traitement) pour une caractériser un objet vidéo. Si de telles approches peuvent simplifier le problème, elles réduisent également considérablement l’information visuelle acquise. Au lieu de calculer un vecteur signature, nous nous concentrons sur l'ensemble des caratcteristiques d’un tube spatio-temporel.


Parmi les caractéristiques que nous avons extraites, certaines sont sensibles à la variation d’illumination, d’autres sont sensibles à la pose. Par exemple, les vecteurs de la couleur HS sont sensibles à la luminance non cent pour cent blanche, mais insensibles à la

- 40 -

pose, les vecteurs de texture sont sensibles à la pose, mais insensibles à la luminance. Nous pouvons envisager de chercher des fonctions noyaux qui sont sensibles à certaines conditions et d’autres fonctions noyaux qui sont sensibles aux autres conditions. Une combinaison de ces fonctions noyaux pourra nous permettre d’obtenir un résultat plus idéel.

De plus, nous ne nous réduirons pas à une représentation à un unique vecteur signature, nous nous considérerons l'ensemble des caratcteristiques visuelles extraites d’un tube spatio-temporel. Nos fonctions noyaux doivent donc définir des mesures de similarité entre ensembles de vecteurs, à partir des tubes spatio-temporels. Ces questions représentent la phase 3 de mon stage et vont être abordées dans le mois qui vient.

- 41 -

5 Conclusion générale

Nous avons effectué une première partie de travail de ce stage, la détection de visages et l’extraction de caractéristiques visuelles. Nous avons commencé à étudier les distances de similarité entre les caractéristiques que nous avons utilisées. Nous allons, dans la suite du stage, poursuivre l’analyse de nouvelles caractéristiques, comme les points d’intérêt SIFT, tout en étudiant des fonctions noyaux pertinentes pour notre problème par l’implémentation de la classification de nos données avec un classifieur SVM.

Dans notre travail de détection, nous avons utilisé une méthode basée sur l’algorithme AdaBoost avec trois cascades de classifieurs (visage de face, de profil gauche et de profil droit) pour détecter les visages d’acteurs dans les séquences vidéo. Cet algorithme est rapide et robuste pour détecter les visages de différentes expressions et différentes luminosités. La combinaison de trois cascades nous permet d’obtenir un taux de bonnes détections plus important. Une amélioration peut être apportée en enrichissant la base d'images de différentes positions et rotations pour entraîner plusieurs cascades de différentes poses.

Dans notre travail d’extraction, nous avons extrait des caractéristiques de la couleur de l’espace HS et des caractéristiques de la texture basée sur les ondelettes de Gabor. Une évaluation sur ces caractéristiques nous montre qu’une seule caractéristique ne peut pas être capable de distinguer les visages des acteurs. La solution est de combiner plusieurs caractéristiques.

Pour la représentation pertinente de la signature d’un visage, le descripteur SIFT, qui permet d’extraire des caractéristiques invariantes à l’échelle et à la rotation d’objet, est appliqué pour détecter des points d’intérêt de visages et pour extraire des caractéristiques autour de ces points. Cependant, les régions saillantes (yeux, bouche, nez, etc.) ne sont pas encore précisément localisées. Un suivi sur les points d’intérêt pourrait aussi favoriser l’interprétation d’un tube de visages.

Les fonctions noyaux seront étudiées pour la mesure de la similarité entre ensembles de vecteurs caratcteristiques à partir des tubes spatio-temporels. Nous pouvons envisager de chercher des fonctions noyaux qui sont sensibles à certaines conditions et d’autres fonctions noyaux qui sont sensibles à d’autres conditions. Une combinaison de ces fonctions noyaux pourra nous permettre d’obtenir un résultat plus robuste et plus pertinent.

- 42 -

Bibliographie

[Arandjelovic 2005] O. Arandjelovic, A. Zisserman, Automatic Face Recognition for Film Character Retrieval in Feature-Length Films, Proc. of IEEE CIVR (2005) 860- 867.

[Bay 2006] H. Bay, T. Tuytelaars, and L. Van Gool, "SURF: Speeded Up Robust Features", European Conference on Computer Vision, Lecture notes in computer science, vol. 3951, pp. 404-417, 2006.

[Casiraghi 2003] Elena Casiraghi, Raffaella Lanzarotti, Giuseppe Lipori, A face detection system based on color and support vector machines, Springer Berlin / Heidelberg, Volume 2859, 2003 pages 113-120

[Chen 2004] Chen, J. Shan, S. Yang, P. Yan, S. Chen, X. Gao, W., Novel Face Detection Method Based on Gabor Features, Springer Berlin / Heidelberg, 2004, ISSU 3338, pages 90-99

[Cámara Chávez 2006] Cámara Chávez, G., Cord, M., Philipp-Foliguet, S., Precioso, F., de A. Araújo, Arnaldo (2006). Robust Scene Cut Detection by Supervised Learning. Submitted to EUSIPCO 2006.

[Dmitry 2005] Dmitry O. Gorodnichy Video-based framework for face recognition in video. Second Workshop on Face Processing in Video (FPiV'05) in Proceedings of Second Canadian Conference on Computer and Robot Vision (CRV'05), pp. 330-338, Victoria, BC, Canada, 9-11 May, 2005. ISBN 0-7695-2319-6. NRC 48216.]

[Daugman 1993] G. Daugman, “High confidence visual recognition of persons by a test of statistical independence,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 15, no. 11, pp. 1148–1161, Nov. 1993.

[Dalal 2005] N. Dalal, B. Triggs, Histograms of Oriented Gradients for Human Detection, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR) 2005, Vol. 1, pp. 886-893.

[Freund 1996] Y. Freund, R.E. Schapire, Experiments with a New Boosting Algorithm, In Proc. 13th Int. Conf. on Machine Learning, pp. 148.-156, 1996.

[Freund 1995] Y. Freund, Boosting a weak learning algorithm by majority, Information and Computation, 121(2):256–285, 1995.

[Fournier 2001] Fournier, J., Cord, M. & Philipp-Foliguet, S. (2001). RETIN: A content-based image indexing and retrieval system, Pattern Analysis and Applications Journal (PAA), vol.4 (2/3), pp.153-173, 2001

[Guérin-Dugué & Palagi 1996] A. Guérin-Dugué, P. M. Palagi, Implantations de filtres de Gabor par pyramide d'images passe-bas, Traitement du Signal 1996 - Volume 13 - n° 1

[Gärtner 2003] Gärtner, T. (2003). A survey of kernels for structured data. In SIGKDD Explorations, volume 5, 2003.

[Guo 2001] G. Guo, S. Z. Li, and C. Kapluk. Face recognition by support vector machines.

- 43 -

Image and Vision Computing, 19(910):631--638, 2001.

[Hsu 2001] R.L. Hsu, M. Abdel-Mottaleb, and A. K. Jain, Face detection in color images, In Proceedings of the IEEE International Conference on Image Processing, pages 1046–1049, 2001.

[Kashima 2003] Kashima, H., Tsuda, K. and Inokuchi, A. (2004). Marginalized kernels between labeled graphs. In 20th International Conference on Machine Learning, pages 321–328. AAAI Press, 2003.

[Ke 2004] Y. Ke and R. Sukthankar. Pca-sift: A more distinctive representation for local image descriptors. In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2004.

[Kondor 2003] R. Kondor and T. Jebara. A kernel between sets of vectors. In International Conference on Machine Learning (ICML), 2003

[Lienhart & Maydt 2002] R. Lienhart, J. Maydt, An Extended Set of Haar-like Features for Rapid Object Detection, IEEE ICIP 2002, Vol. 1, pp. 900-903, Sep. 2002.

[Lienhart et al. 2002] R. Lienhart, A. Kuranov, V. Pisarevsky, Empirical Analysis of Detection Cascades of Boosted Classifiers for Rapid Object Detection, MRL Technical Report, May 2002.

[Liu 2002] C. Liu, H. Wechsler, Gabor Feature Based Classification Using the Enhanced Fisher Linear Discriminant Model for Face Recognition, IEEE Trans. Image Processing, vol. 11, no. 4, pp. 467-476, 2002.

[Lowe 1999] Lowe, D.G. 1999. Object recognition from local scale-invariant features. In International Conference on Computer Vision, Corfu, Greece, pp. 1150-1157.

[Lowe 2004] D. Lowe. Distinctive Image Features from Scale-Invariant Keypoints. Accepted for publication in the International Journal of Computer Vision, 2004.

[Morizet 2006] Nicolas Morizet, Thomas Ea, Florence Rossant, Frédéric Amiel et Amara Amara, Revue des algorithmes PCA, LDA et EBGM utilisés en reconnaissance 2D du visage pour la biométrie, Tutoriel Reconnaissance d'images, MajecStic 2006 (MAnifestation des Jeunes Chercheurs STIC) .

[Osuna1997] E. Osuna, R. Freund, and F. Girosi. Training support vector machines: an application to face detection. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 130--136, 1997.

[Precioso 2005] Precioso, F., Barlaud., M., Blu, T., Unser, M. (2005). Robust Real-Time Segmentation of Images and Videos Using a Smoothing-Spline Snake Based Algorithm. IEEE Trans on Image Processing, Vol 14 N◦7 July 2005

[Philipp-Foliguet 2006] S. Philipp-Foliguet and J. Gony, FReBIR : Fuzzy Region-Based Image Retrieval, IPMU, Paris, juillet 2006

[Precioso 2004] Precioso F., Contours actifs paramétriques pour la segmentation d’images et vidéos, Thèse Frédéric Precioso 2004

- 44 -

[Rakotomamonjy 2005] Rakotomamonjy, A., Canu, S. (2005), Frames, Reproducing Kernels, Learning and Regularization, Journal of Machine Learning Research, Vol 6, pp 1485-1515.

[Shan 2004] S. Shan, Study on some Key Issues in Face Recognition, PhD thesis, 2004.

[Saxe 1996] D. Saxe and R. Foulds, Toward Robust Skin Identification in Video Images, Proc. Second International Conference, Automatic Face and Gesture Recognition, pp. 379-384, 1996.

[Shawe-Taylor 2004] Shawe-Taylor, J. Cristianini N. (2004), Kernel Methods for Pattern Analysis, Cambrigde University Press

[Suard 2005] Suard, F. Rakotomamonjy A. Bensrhair, (2005) A. Pedestrian Detection using stereovision and graph kernels. IEEE Intelligent Vehicles Symposium

[Sivic 2005] J. Sivic, M. Everingham, and A. Zisserman, Person spotting: video shot retrieval for face sets. Proc. of IEEE CIVR (2005) 226-236.

[Turk 1991] M. Turk and A. Pentland, Eigenfaces for Recognition, J. Cognitive Neuroscience, vol. 3, no. 1, pp. 71-86, 1991.

[Viola 2001] P. Viola, M. Jones, Rapid Object Detection using a Boosted Cascade of Simple Features, Conference On Computer Vision And Pattern Recognition 2001.

[Viola 2003] P. Viola, M. Jones, Fast Multi-view Face Detection, IEEE Conference on Computer Vision and Pattern Recognition, 2003.

[Viola 2004] P. Viola, M. Jones, Robust Real-Time Face Detection, International Journal of Computer Vision 57(2), 137–154, 2004.

[Viola 2005] P. Viola, M. Jones, D. Snow, Detecting Pedestrians Using Patterns of Motion and Appearance, International Journal of Computer Vision 63(2), 153–161, 2005

[Wiskott, 1997] Wiskott L., Fellous J.M., Krüger N., Von Der Malsburg C., Face Recognition by Elastic Bunch Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7) :775-779, 1997.

[Yang 2002] Yang M H, Kriegman D, Ahuja N. Detecting faces in images: A survey. IEEE Trans Pattern Analysis and Machine Intelligence, 2002, 24(1):34-58.

[Zhang 2005] W. Zhang, S. Shan, W. Gao, X. Chen, and H. Zhang, Local Gabor binary pattern histogram sequence (LGBPHS): A novel non-statistical model for face representation and recognition, in Proc. 10th IEEE Int. Conf. Computer Vision, 2005, pp. 786–791.

[Zhang 2007] B. Zhang, S. Shan, X. Chen, W. Gao, Histogram of Gabor Phase Patterns (HGPP): A Novel Object Representation Approach for Face Recognition, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 16, NO. 1, JANUARY 2007.

[Zhu 2006] Zhu Q., Avidan S., Yeh M-C, Cheng K-W, Fast Human Detection Using a Cascade of Histograms of Oriented Gradients, IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR) 2006, Volume 2, pp. 1491-1498.

- 45 -

Annexe 1:

Organigramme de l’algorithme AdaBoost

Choisir un classifieur faible

Choisir le classifieur ht qui possèdes l’erreur minimale

Initialiser poids des exemplesP: w1,i = 1/2m ;

N: w1,i = 1/2l

Classifieur fort

où

Évaluer l’erreur de chaque classifieur

Normaliser les poids wiDonner des exemples(x1, y1), . . . , (xn , yn )P: yi = 1; N: yi = 0

For t=1,2,…,T

begin

Next T

end

Mis à jour les poids

correct:

incorrect:

Obtenir un classifieur fort

Choisir un classifieur faible

Choisir le classifieur ht qui possèdes l’erreur minimale

Initialiser poids des exemplesP: w1,i = 1/2m ;

N: w1,i = 1/2l

Classifieur fort

où

Évaluer l’erreur de chaque classifieur

Normaliser les poids wiDonner des exemples(x1, y1), . . . , (xn , yn )P: yi = 1; N: yi = 0

For t=1,2,…,T

begin

Next T

end


correct:

incorrect:


correct:

incorrect:

Obtenir un classifieur fort

- 46 -

Annexe 2:

Organigramme de l’algorithme d’apprentissage par une cascade d’AdaBoost

Diminuer l’ensemble d’exemples négatifs

AdaBoost pour choisir le classifieur

Mis à jour le seuil pour queDi > d * Di-1

Fi > f * Fi-1 ?

Initialiser taux globauxF0 = 1 ; D0 = 1

Donner des exemples(x1, y1), . . . , (xn , yn )P: yi = 1; N: yi = 0

begin

end

Définir max f /étapes, min d /étapes, global Ftarget

Fi > Ftarget ?

prochaine étape

prochain classifieur

obtenir une cascade de classifieurs forts

Obtenir un classifieur fort de ie étape

classifieur faible

Diminuer l’ensemble d’exemples négatifs

AdaBoost pour choisir le classifieur

Mis à jour le seuil pour queDi > d * Di-1

Fi > f * Fi-1 ?Fi > f * Fi-1 ?

Initialiser taux globauxF0 = 1 ; D0 = 1

Donner des exemples(x1, y1), . . . , (xn , yn )P: yi = 1; N: yi = 0

begin

end

Définir max f /étapes, min d /étapes, global Ftarget

Fi > Ftarget ?

prochaine étape

prochain classifieurprochain classifieur

obtenir une cascade de classifieurs forts

Obtenir un classifieur fort de ie étape

classifieur faible

Documents

Apprentissage et Recherche par le Contenu Visuel.pdf