Rostom PhD Theses

  • Upload
    hassen

  • View
    69

  • Download
    0

Embed Size (px)

Citation preview

  • UNIVERSITE DEVRY-VAL DESSONNELaboratoire dInformatique, Biologie Integrative et Syste`mes Complexes

    THE`SE

    Presentee par

    Rostom KACHOURI

    Pour lobtention du titre de

    Docteur de lUniversite dEvry-Val dEssonne

    Specialite: Sciences pour lingenieur - Traitement des IMages etdu SIgnal

    Classification multi-mode`les des images dansles bases heteroge`nes

    The`se soutenue le 29 juin 2010

    Devant le jury compose de:

    S. Ruan : Professeur, Universite de Reims, RapporteurW. Puech : Professeur, Universite de Montpellier II, RapporteurK. Hamrouni : MCF, ENIT-Universite de Tunis, RapporteurA. Ben Hamida : Professeur, ENIS-Universite de Sfax, ExaminateurD. S-Masmoudi : MCF, ENIS-Universite de Sfax, ExaminateurK. Djemal : MCF, Universite dEvry Val dEssonne, EncadrantN. Derbel : Professeur, ENIS-Universite de Sfax, Co-directeurH. Maaref : Professeur, Universite dEvry Val dEssonne, Directeur

  • Dedicaces

    A` lame de mon pe`re SadokA` ma me`re MoniaAuxquels, je dois ce que je suis

    A` ImenA` notre fille RahmaA` notre futur garcon Rayan

  • Remerciements

    Jaimerais avant tout exprimer ma gratitude et mes remerciements a` mon encadrantscientifique de the`se, M. Khalifa Djemal, matre de conferences de luniversite dEvry. Jaienormement appris a` ses cotes. Il a su minitier a` la recherche, me pousser a` toujoursfaire mieux et il ma souvent aide a` surmonter les difficultes de ce cheminement questle doctorat. Encore plus que ses grandes qualites scientifiques, jai beaucoup apprecie sesqualites humaines, en particulier lecoute, le partage et la comprehension, qui men ontfait un ami.

    Jadresse egalement a` mon directeur de the`se, M. Hichem Maaref, professeur de luni-versite dEvry, mes plus since`res remerciements. Cest un homme dune grande patience,tre`s a` lecoute et tre`s comprehensif et qui est directement responsable du bon deroulementde mes travaux. Je le remercie chaleureusement pour ses attentions et les nombreuses dis-cussions professionnelles et personnelles que nous avons eues.

    Je veux absolument remercier M. Nabil Derbel, professeur de luniversite de Sfax etMme Dorra Sellami-Masmoudi, matre de conferences a` lEcole nationale des ingenieurs deSfax et habilitee a` diriger les recherches, sans qui cette collaboration de the`se en cotutellene serait pas ce quelle est aujourdhui.

    Jexprime ma gratitude a` M.William Puech, professeur de luniversite de Montpellier IIainsi qua` Mme Su Ruan, professeur de luniversite de Reims, pour avoir accepte de jugermes travaux en tant que rapporteurs. Je remercie M. AHMED BEN HMIDA, professeurde luniversite de Sfax, qui a accepte de faire partie de ce jury. Je tiens egalement a` expri-mer ma reconnaissance a` M. Kamel Hamrouni, matre de conferences a` lEcole nationaledes ingenieurs de Tunis et habilite a` diriger les recherches, pour avoir accepte de jugermes travaux et presider ce jury.

    Une the`se est un travail assez personnel qui sinscrit toutefois dans une equipe. Jeremercie donc tous mes colle`gues doctorants, tous les membres temporaires ou perma-nents que jai croise au cours de cette experience, je pense en particulier a` Imen, Ahmed,Mohamed, Slim, Amin, Imen, Anwar, Anis, Asma, Salima, Iman, Mouna, christophe,Jean-yves, christophe, Pierre, Hamdi, Abdelkader, Samia, Nader, Majid, yassine, Khalid(ils sont trop nombreux pour pouvoir les citer tous). Ils mont beaucoup apporte pendantces dernie`res annees: joie, fous rires, complicite, soirees, voyages, ouverture desprit.

    Comme il y a aussi une vie en dehors du travail (si tout de meme un petit peu) jai eula chance de rencontrer hors du labo des personnes qui sont aujourdhui des amis: Tarek,Hedi, Mehdi, Hamdi, Sabeur, Khalil, Sebastien, Nader et tant dautres! Auxquels je doisaussi de bons moments de sincerite, rigolade et complicite.

    Enfin last but not least jexprime toute ma gratitude a` ma me`re Monia, ma femmeImen et ma petite fille Rahma qui ont supporte avec moi les meilleurs et les pires momentset qui mont donne la force daller au bout de cette aventure. Bref, pour ce bout de cheminfait ensemble.

  • Resume

    La reconnaissance dimages est un domaine de recherche qui a ete largement etudiepar la communaute scientifique. Les travaux proposes dans ce cadre sadressent principale-ment aux diverses applications des syste`mes de vision par ordinateur et a` la categorisationdes images issues de plusieurs sources. Dans cette the`se, on sinteresse particulie`rementaux syste`mes de reconnaissance dimages par le contenu dans les bases heteroge`nes.Les images dans ce type de bases appartiennent a` differents concepts et represententun contenu heteroge`ne. Pour ce faire, une large description permettant dassurer unerepresentation fiable est souvent requise. Cependant, les caracteristiques extraites nesont pas necessairement toutes appropriees pour la discrimination des differentes classesdimages qui existent dans une base donnee dimages. Dou`, la necessite de selection descaracteristiques pertinentes selon le contenu de chaque base. Dans ce travail, une methodeoriginale de selection adaptative est proposee. Cette methode permet de considerer uni-quement les caracteristiques qui sont jugees comme les mieux adaptees au contenu de labase dimages utilisee. Par ailleurs, les caracteristiques selectionnees ne disposent pasgeneralement des memes performances. En consequence, lutilisation dun algorithmede classification, qui sadapte aux pouvoirs discriminants des differentes caracteristiquesselectionnees par rapport au contenu de la base dimages utilisee, est vivement recom-mandee. Dans ce contexte, lapproche dapprentissage par noyaux multiples est etudiee etune amelioration des methodes de ponderation des noyaux est presentee. Cette approchesave`re incapable de decrire les relations non-lineaires des differents types de description.Ainsi, nous proposons une nouvelle methode de classification hierarchique multi-mode`lespermettant dassurer une combinaison plus flexible des caracteristiques multiples. Dapre`sles experimentations realisees, cette nouvelle methode de classification assure des taux dereconnaissance tre`s interessants. Enfin, les performances de la methode proposee sontmises en evidence a` travers une comparaison avec un ensemble dapproches cite dans lalitterature recente du domaine.

    Mots-cles: Reconnaissance dimages par le contenu, Bases dimages heteroge`nes, Ex-traction dattributs, Selection adaptative des caracteristiques les plus pertinentes, Ap-prentissage par noyaux multiples, Classification multi-mode`les.

  • Abstract

    Image recognition is widely studied by the scientific community. The proposed researchin this field is addressed to various applications of computer vision systems and multiplesource image categorization. This PhD dissertation deals particularly with content basedimage recognition systems in heterogeneous databases. Images in this kind of databasesbelong to different concepts and represent a heterogeneous content. In this case and toensure a reliable representation, a broad description is often required. However, the ex-tracted features are not necessarily always suitable for the considered image database.Hence, the need of selecting relevant features based on the content of each database. Inthis work, an adaptive selection method is proposed. It considers only the most adaptedfeatures according to the used image database content. Moreover, selected features donot have generally the same performance degrees. Consequently, a specific classificationalgorithm which considers the discrimination powers of the different selected features isstrongly recommended. In this context, the multiple kernel learning approach is studiedand an improved kernel weighting method is presented. It proved that this approach isunable to describe the nonlinear relationships of different description kinds. Thus, we pro-pose a new hierarchical multi-model classification method able to ensure a more flexiblecombination of multiple features. Experimental results confirm the effectiveness and therobustness of this new classification approach. In addition, the proposed method is verycompetitive in comparison with a set of approaches cited in the recent literature.

    Key words: Content based image recognition, Heterogeneous image databases, Fea-ture extraction, Adaptive feature selection, Multiple kernel learning, Multi-model classi-fication.

  • Table des matie`res

    Dedicaces

    Remerciements

    Resume

    Abstract

    Index des symboles 1

    Introduction generale 6

    1 Extraction dattributs et classification dimages dans les bases heteroge`nes 10

    1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

    1.2 Reconnaissance dimages par le contenu . . . . . . . . . . . . . . . . . . . 11

    1.2.1 Types dattributs . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

    1.2.1.1 La couleur . . . . . . . . . . . . . . . . . . . . . . . . . . 13

    1.2.1.2 La texture . . . . . . . . . . . . . . . . . . . . . . . . . . 14

    1.2.1.3 La forme . . . . . . . . . . . . . . . . . . . . . . . . . . 14

    1.2.2 Categories dattributs . . . . . . . . . . . . . . . . . . . . . . . . 15

    1.2.2.1 Attributs globaux . . . . . . . . . . . . . . . . . . . . . . 15

    1.2.2.2 Attributs locaux . . . . . . . . . . . . . . . . . . . . . . 16

    1.2.3 Methodes de classification et evaluation des performances . . . . . 17

    1.2.3.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . 17

    1.2.3.2 Retroaction et bouclage de pertinence . . . . . . . . . . 17

    1.2.3.3 Performances de classification dimages . . . . . . . . . . 18

    1.3 Bases dimages heteroge`nes utilisees . . . . . . . . . . . . . . . . . . . . . 18

    1.3.1 La base dimages COLUMBIA . . . . . . . . . . . . . . . . . . . . 19

    1.3.2 La base dimages COREL . . . . . . . . . . . . . . . . . . . . . . 19

    1.3.3 La base dimages CALTECH . . . . . . . . . . . . . . . . . . . . . 20

    1.4 Techniques de classification dimages . . . . . . . . . . . . . . . . . . . . 22

    1.4.1 Methodes de classification non-supervisee . . . . . . . . . . . . . . 22

  • 1.4.2 Methodes de classification supervisee . . . . . . . . . . . . . . . . 24

    1.5 Caracteristiques utilisees pour la description dimages dans les bases heteroge`nes 26

    1.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

    1.5.2 Les couleurs moyennes . . . . . . . . . . . . . . . . . . . . . . . . 27

    1.5.3 Les histogrammes couleurs . . . . . . . . . . . . . . . . . . . . . . 28

    1.5.4 La matrice correlogramme . . . . . . . . . . . . . . . . . . . . . . 28

    1.5.5 Les statistiques de premier ordre . . . . . . . . . . . . . . . . . . 29

    1.5.6 La matrice de co-occurrences . . . . . . . . . . . . . . . . . . . . 29

    1.5.7 Les transformees en ondelettes de Daubeshie . . . . . . . . . . . . 31

    1.5.8 Le descripteur GIST . . . . . . . . . . . . . . . . . . . . . . . . . 31

    1.5.9 La matrice norme du gradient . . . . . . . . . . . . . . . . . . . . 31

    1.5.10 Les moments de Hu . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    1.5.11 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    1.5.12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    1.6 Evaluation des caracteristiques . . . . . . . . . . . . . . . . . . . . . . . . 35

    1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

    2 Selection Adaptative des caracteristiques les plus pertinentes 40

    2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    2.2 Methodes de selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    2.2.1 Les methodes Filtres . . . . . . . . . . . . . . . . . . . . . . . . . 41

    2.2.2 Les methodes Enveloppantes . . . . . . . . . . . . . . . . . . . . . 42

    2.3 Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

    2.3.1 LAnalyse en Composantes Principales . . . . . . . . . . . . . . . 42

    2.3.2 La selection basee sur les Algorithmes Genetiques . . . . . . . . . 44

    2.4 La Selection Adaptative des Caracteristiques pertinentes . . . . . . . . . 45

    2.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

    2.4.2 Apprentissage multiple . . . . . . . . . . . . . . . . . . . . . . . . 45

    2.4.3 Discrimination lineaire de Fisher . . . . . . . . . . . . . . . . . . 46

    2.4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

    2.5 Evaluation de la selection des caracteristiques par ACP, AG et SAC . . . 49

    2.5.1 ACP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

    2.5.2 AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

    2.5.3 SAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

    2.5.4 Resultats de classification . . . . . . . . . . . . . . . . . . . . . . 57

    2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

    3 Machines a` Vecteurs Supports a` noyaux multiples 61

    3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

    3.2 Machines a` Vecteurs Supports . . . . . . . . . . . . . . . . . . . . . . . . 62

    3.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

  • 3.2.2 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

    3.2.3 Cas lineairement separable . . . . . . . . . . . . . . . . . . . . . . 63

    3.2.4 Cas non-lineairement separable . . . . . . . . . . . . . . . . . . . 64

    3.2.5 Extension aux proble`mes multi-classes . . . . . . . . . . . . . . . 65

    3.2.5.1 Algorithme SVM: Un contre tous . . . . . . . . . . . . . 66

    3.2.5.2 Algorithme SVM: Un contre un . . . . . . . . . . . . . . 66

    3.2.5.3 Algorithme DAG-SVM . . . . . . . . . . . . . . . . . . . 67

    3.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

    3.3 Approche dapprentissage par noyaux multiples . . . . . . . . . . . . . . 67

    3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

    3.3.2 Techniques de ponderation de noyaux . . . . . . . . . . . . . . . . 68

    3.4 Ponderation de noyaux basee sur les taux dapprentissage SVM . . . . . 70

    3.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

    3.4.2 Principe de MK SVM . . . . . . . . . . . . . . . . . . . . . . . . 70

    3.4.3 Apprentissage multiple . . . . . . . . . . . . . . . . . . . . . . . . 71

    3.4.4 Calcul des differents poids de noyaux . . . . . . . . . . . . . . . . 71

    3.4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

    3.5 Evaluation de la methode MK SVM . . . . . . . . . . . . . . . . . . . . . 73

    3.5.1 Resultats de classification . . . . . . . . . . . . . . . . . . . . . . 74

    3.5.2 Temps dexecution . . . . . . . . . . . . . . . . . . . . . . . . . . 75

    3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

    4 Methode de classification hierarchique multi-mode`les 78

    4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

    4.2 Classification hierarchique multi-mode`les . . . . . . . . . . . . . . . . . . 79

    4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

    4.2.2 Principe de lapproche multi-mode`les . . . . . . . . . . . . . . . . 79

    4.2.3 Resolution de conflit de decision par NCC . . . . . . . . . . . . . 80

    4.2.4 Classification hierarchique . . . . . . . . . . . . . . . . . . . . . . 81

    4.2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

    4.3 Evaluation et comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . 83

    4.3.1 Evaluation de MC-MM a` travers differentes methodes de selection 83

    4.3.2 Performances de MC-MM utilisant la methode de selection SAC . 84

    4.3.3 Comparaison des resultats MC-MM basee SAC avec des methodesde classification connues . . . . . . . . . . . . . . . . . . . . . . . 86

    4.3.3.1 Methode simultanee classique . . . . . . . . . . . . . . . 86

    4.3.3.2 Approche des Multiple Instance Learning . . . . . . . . . 88

    4.3.3.3 Approche des sacs de mots-visuels . . . . . . . . . . . . 89

    4.3.3.4 Approche dapprentissage par noyaux multiples . . . . . 92

    4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

  • Conclusion generale et perspectives 98

    Liste des publications 102

    Bibliographie 105

  • Table des figures

    1.1 Architecture dun syste`me de reconnaissance dimages par le contenubase sur la classification. . . . . . . . . . . . . . . . . . . . . . . . . . . 11

    1.2 Image couleur RVB : association de trois sous-images monochromes, cor-respondant respectivement au differentes composantes Rouge, Vert etBleu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

    1.3 Differents mode`les de texture. . . . . . . . . . . . . . . . . . . . . . . . 14

    1.4 Differentes transformations geometriques que peut subir une image. . . 15

    1.5 Echantillons dimages segmentees de la base COREL. . . . . . . . . . . 16

    1.6 Graphe typique de precision-rappel. . . . . . . . . . . . . . . . . . . . . 18

    1.7 Echantillons des 100 objets de la base dimages COIL-100 de COLUMBIA. 19

    1.8 Echantillons dimages de differentes classes de la base COREL utilisee. 20

    1.9 Echantillons dimages de differentes classes de la base CALTECH-256utilisee. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    1.10 Approche de classification supervisee: type de modelisation a) Intrinse`queet b) Discriminante. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

    1.11 Echantillons des caracteristiques extraites respectivement des imagesDinosaure et Rose: a) Histogramme, b) Matrice des normes du gradient,et c) GIST. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

    1.12 Coefficients dondelettes pour deux niveaux de decomposition. . . . . . 31

    1.13 Echantillons des descripteurs GIST extraits pour differentes images dela base COREL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    1.14 Nouvelle forme de la caracteristique des normes du gradient des imageDinosaure et Rose: a) la projection selon x et b) la projection selon y. . 35

    1.15 Taux de classification des mode`les individuels associes a` lensemble descaracteristiques employees pour differentes sous-bases dimages COREL(a` gauche) et CALTECH-256 (a` droite). . . . . . . . . . . . . . . . . . 38

    2.1 Les deux premie`res directions principales (b1 et b2) dun nuage de NImobservations dans Rd. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    2.2 Diagramme standard dun algorithme genetique. . . . . . . . . . . . . 44

    2.3 Diagramme de la methode de Selection Adaptative des Caracteristiquesles plus pertinentes qui correspondent aux mode`les selectionnes dansMs. 48

  • 2.4 Allure des valeurs propres rangees par ordre decroissant respectivementpour les sous-bases COREL avec : a) 3 classes, b) 5 classes, c) 7 classeset d) 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    2.5 Allure des valeurs propres rangees par ordre decroissant respectivementpour les sous-bases COLUMBIA avec : a) 3 classes, b) 5 classes, c) 7classes et d) 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    2.6 Comparaison des precisions moyennes de classification respectivementbasees sur les selections ACP (90%), AG2 et SAC pour differentes sous-bases dimages COREL. . . . . . . . . . . . . . . . . . . . . . . . . . . 58

    3.1 Exemple de classification SVM lineairement separable. . . . . . . . . . 64

    3.2 Exemple de classification SVM non-lineairement separable. . . . . . . . 65

    3.3 Exemple de classification SVM multi-classes (NC = 3). . . . . . . . . . 66

    3.4 Diagramme de la methode de classification MK SVM utilisant la nou-velle ponderation KW-BTR. . . . . . . . . . . . . . . . . . . . . . . . . 72

    3.5 Performances de classification moyenne des deux algorithmes MK SVMet SimpleMKL pour differentes sous-bases dimages COREL. . . . . . . 75

    3.6 Courbes precision-rappel de a) MK SVM et b) SimpleMKL pour differentessous-bases dimages COREL. . . . . . . . . . . . . . . . . . . . . . . . 75

    4.1 Re`gle de decision du classifieur NCC: classification de limage requeteIq dans lespace dattributs Fm, a` travers les deux classes evaluees Ci etCj. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

    4.2 Diagramme illustrant larchitecture de la methode de classification hierarchiquemulti-mode`les MC-MM. . . . . . . . . . . . . . . . . . . . . . . . . . . 82

    4.3 a) Les images correctement classifiees et b) celles mal classifiees de laclasse African peoples and villages pour la sous-base dimages CORELutilisee (10 classes). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

    4.4 Comparaison des precisions moyennes de MC-MM et de la methode declassification classique pour differentes sous-bases dimages COREL. . . 87

    4.5 Les dix histogrammes de mots-visuels qui representent lensemble desclasses de la sous-base dimages COREL avec 10 classes. Chaque his-togramme illustre le nombre doccurrence des differents mots-visuelsextraits a` partir des images de la classe correspondante. . . . . . . . . 89

    4.6 a) Sac de mots-visuels qui represente lensemble des images apparte-nant aux 10 classes de la sous-base COREL utilisee, b) Distances entreles caracteristiques histogrammes de mots-visuels des differentes pairesdimages de la sous-bases COREL utilisee (10 classes). . . . . . . . . . 90

    4.7 Graphes des deux matrices de confusion respectives de MC-MM (a`gauche) et BoF (a` droite) pour la sous-base dimages COREL avec 10classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

    4.8 Courbes precision-rappel de MC-MM et BoF pour la sous-base dimagesCOREL avec 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . 91

    4.9 Comparaison des precisions moyennes de MC-MM et SimpleMKL pourdifferentes sous-bases dimages a) COREL et b) CALTECH-256. . . . . 93

  • 4.10 Courbes precision-rappel de a) MC-MM et b) SimpleMKL pour differentessous-bases dimages COREL. . . . . . . . . . . . . . . . . . . . . . . . 93

    4.11 Courbes precision-rappel de a) MC-MM et b) SimpleMKL pour differentessous-bases dimages CALTECH-256. . . . . . . . . . . . . . . . . . . . 93

    4.12 Les images requetes de la classe Sunset scenes de la base COREL(a` gauche) et les images mal-classifiees (a` droite) avec respectivementMC-MM et SimpleMKL. Toutes les images requetes restantes (non illustreesa` droite) sont correctement classifiees a` travers chaque methode. . . . . 94

    4.13 Les images requetes de la classe Chimp de la base CALTECH-256(a` gauche) et les images mal-classifiees (a` droite) avec respectivementMC-MM et SimpleMKL. Toutes les images requetes restantes (non illustreesa` droite) sont correctement classifiees a` travers chaque methode. . . . . 94

  • Liste des tableaux

    1.1 Noms et identifiants des 23 classes utilisees a` partir des deux bases dimagesCOREL et CALTECH-256. . . . . . . . . . . . . . . . . . . . . . . . . . 21

    1.2 Evaluation de lefficacite de classification des mode`les individuels associesaux caracteristiques couleurs pour differentes sous-bases COREL. . . . . 36

    1.3 Evaluation de lefficacite de classification des mode`les individuels associesaux caracteristiques textures et formes pour differentes sous-bases COREL. 36

    1.4 Evaluation de lefficacite de classification des mode`les individuels associesaux caracteristiques couleurs pour differentes sous-bases COLUMBIA. . . 37

    1.5 Evaluation de lefficacite de classification des mode`les individuels associesaux caracteristiques textures et formes pour differentes sous-bases CO-LUMBIA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    2.1 Variation de la dimension des composantes principales selectionnees avecla methode de selection ACP en fonction de differentes sous-bases dimagesCOREL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    2.2 Variation de la dimension des composantes principales selectionnees avecla methode de selection ACP en fonction de differentes sous-bases dimagesCOLUMBIA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    2.3 Variation des parame`tres des differentes selections AGs pour la sous-baseCOREL avec 3 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    2.4 Variation des parame`tres des differentes selections AGs pour la sous-baseCOREL avec 5 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    2.5 Variation des parame`tres des differentes selections AGs pour la sous-baseCOREL avec 7 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    2.6 Variation des parame`tres des differentes selections AGs pour la sous-baseCOREL avec 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

    2.7 Variation des parame`tres des differentes selections AGs pour la sous-baseCOLUMBIA avec 3 classes. . . . . . . . . . . . . . . . . . . . . . . . . . 54

    2.8 Variation des parame`tres des differentes selections AGs pour la sous-baseCOLUMBIA avec 5 classes. . . . . . . . . . . . . . . . . . . . . . . . . . 54

    2.9 Variation des parame`tres des differentes selections AGs pour la sous-baseCOLUMBIA avec 7 classes. . . . . . . . . . . . . . . . . . . . . . . . . . 54

    2.10 Variation des parame`tres des differentes selections AGs pour la sous-baseCOLUMBIA avec 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . 55

  • 2.11 Variation des parame`tres SAC pour differentes sous-bases COREL. . . . 56

    2.12 Variation des parame`tres SAC pour differentes sous-bases COLUMBIA. . 56

    2.13 Resultats de classification SVM basee sur la selection ACP pour differentessous-bases dimages COREL. . . . . . . . . . . . . . . . . . . . . . . . . . 57

    2.14 Resultats de classification SVM basee sur la selection ACP pour differentessous-bases dimages COLUMBIA. . . . . . . . . . . . . . . . . . . . . . . 57

    2.15 Resultats de classification SVM basee ACP (90%), AG2 et SAC pourdifferentes sous-bases dimages COREL. . . . . . . . . . . . . . . . . . . 58

    3.1 Exemple de ponderation de noyaux KW-BTR pour la sous-base CORELavec 5 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

    3.2 Comparaison des resultats de classification MK SVM et SimpleMKL pourdifferentes sous-bases dimages COREL. . . . . . . . . . . . . . . . . . . 74

    3.3 Comparaison des temps dapprentissage et de ponderation (en Minutes)des deux algorithmes MK SVM et SimpleMKL pour differentes sous-basesCOREL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

    4.1 Classification MC-MM a` ravers differentes methodes de selection pourquatre sous-bases dimages COREL. . . . . . . . . . . . . . . . . . . . . . 84

    4.2 Evaluation de la generalisation MC-MM. Etude comparative avec les deuxprocedures de generalisation decroissante et max mode`les pour differentessous-bases COREL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

    4.3 Matrice de confusion de la classification MC-MM pour la sous-base CO-REL avec 10 classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

    4.4 Evaluation des deux methodes de classification MC-MM et classique pourdifferentes sous-bases dimages COREL. . . . . . . . . . . . . . . . . . . 87

    4.5 Comparaison de la la precision moyenne de classification de la methodeMC-MM avec celles de differentes methodes MIL de letat de lart pour lasous-base COREL avec 10 classes. . . . . . . . . . . . . . . . . . . . . . . 88

    4.6 Etude comparative des deux methodes MC-MM et SimpleMKL pour differentessous-bases dimages COREL et CALTECH-256. . . . . . . . . . . . . . . 92

    4.7 Comparaison des temps dapprentissage (en Minutes) deMC-MM et SimpleMKLpour differentes sous-bases COREL et CALTECH-256. . . . . . . . . . . 95

  • Index des symboles

    Symboles Significations

    P Nombre total des images pertinentes dans une base.TP Taux des vrai positifs, i.e. nombre dimages pertinentes retrou

    vees.FP Taux des faux positifs, i.e. nombre dimages non-pertinentes

    retrouvees.I Image couleur.R Matrice couleur Rouge de I dans lespace couleur RV B.V Matrice couleur Verte de I dans lespace couleur RV B.B Matrice couleur Bleue de I dans lespace couleur RV B.p Pixel de limage I.N Nombre de pixels p dans limage I.c = I(p) Couleur dun pixel p dans limage I.cl Nombre de couleurs dans limage I.RVB Caracteristique couleur moyenne de limage I, extraite a` partir

    de lespace couleur RV B.HSV Caracteristique couleur moyenne de limage I, extraite a` partir

    de lespace couleur HSV .HMMD Caracteristique couleur moyenne de limage I, extraite a` partir

    de lespace couleur HMMD.YCrCb Caracteristique couleur moyenne de limage I, extraite a` partir

    de lespace couleur Y CrCb.Hist Caracteristique histogrammes couleurs de limage I, extraite a`

    partir de lespace couleur RV B.L Norme infinie.Dist Distance inter-pixel dans une image.Cor Matrice correlogramme de limage I.A-Cor Caracteristique auto-correlogramme de limage I.NG Image niveau de gris correspondante a` limage I.ng Nombre de niveaux de gris dans limage NG.Moy Moyenne de la distribution des niveaux de gris de limage NG.

    Etype Ecart type de la distribution des niveaux de gris de limage NG.Var Variance de la distribution des niveaux de gris de limage NG.FOS Caracteristique statistiques de premiers ordres de limage I.Dir Direction inter-pixel dans une image.SGLD Matrice de co-occurences de limage I.SGLD Ensemble des attributs extraits de la matrice de co-occurence

  • INDEX DES SYMBOLES

    SGLD de limage I: {Moyenne, Energie, V ariance, Contr-aste, Entropie, Homogeneite & Correlation}.

    clij Coefficients dondelettes de Daubeshie de limage I pour unniveau de decomposition l, i,j [0,1].

    hi; hj Filtres de Daubeshie selon les lignes et les colones.hLAP Matrice de convolution du filtre Laplacien.elij Coefficient condense de la transformation dondelette de

    Daubeshie de limage I pour un niveau de decomposition l,i,j [0,1].

    Daub Caracteristique coefficients condenses de la transformationdondelette de Daubeshie de limage I a` deux niveaux dedecomposition.

    GIST Descripteur GIST de limage I.GX ; GY Gradients directionnels selon x et y (approximations des

    derivees horizontale et verticale) de limage NG.hX ; hY Masques de Sobel, i.e. matrices de convolution horizontale

    et verticale.G Matrice normes du gradient correspondante a` GX et GY .PX Projection de G selon X.PY Projection de G selon Y .G-norm Caracteristique projection de la matrice normes du gra-

    dient de limage I selon X et Y .i=1,2,...,7 Moments invariants de Hu, calcules a` partir de limage I.Hu Caracteristique des moments de Hu de limage I.Bapp Base dapprentissage.NIm Nombre dimages dapprentissage dans la base Bapp.xi Vecteur caracteristique de dimension d, i = [1,2,...,n].n Nombre de caracteristiques xi, i = [1,2,...,n].Fi = Rd Espace dattributs de la caracteristique xi, i = [1,2,...,n].Xi = [x

    i1,x

    i2,...,x

    iNIm

    ] Nuage des NIm points, dits aussi individus ou observationsdans lespace dattribut Fi, i = [1,2,...,n].

    X Caracteristique moyenne dun nuage dobservations X.C Matrice de covariance dun nuage dobservations X.dxj Deformation principales de lobservation xj par rapport a` la

    forme moyenne X. Base modale, correspond a` la diagonalisation de la matrice

    de covariance C.i Vecteur propre de la matrice de covariance C, i = [1,2,...,d].p Sous-matrice de contenant les p premiers vecteurs propres

    de la matrice de covariance C.bi Composante principale dun nuage dobservations X, i = [1,2,

    ...,p].B Vecteur des amplitudes modales de deformations, represente

    une forme dans lespace p-dimensionnel defini par les compo-santes principales retenues.

    T Inertie totale correspondante a` la matrice de covariance C. Pourcentage de variance relatif aux p premiers modes, i.e. le

    taux dinertie total correspondant.NC Nombre de classes contenues dans BApp.

    2

  • INDEX DES SYMBOLES

    C = {C1,C2,...,CNC} Ensemble des NC classes contenues dans BApp.M = {M1,M2,...,Mn} Espace des mode`les correspondants aux caracteristiques extr-

    aites a` partir de la base dimages Bapp, i.e. xi=1,2,...,n.NErr(Mi) Nombre dimages mal classifiees (ou erronees) selon le mode`le

    Mi, i = [1,2,...,n].NCorr(Mi) Nombre dimages correctement classifiees selon le mode`le Mi,

    i = [1,2,...,n].E(Mi) Taux derreur de classification du mode`le Mi, i = [1,2,...,n].Per(Mi) Taux de classification en phase dapprentissage (performance

    dapprentissage) du mode`le Mi, i = [1,2,...,n].T = {Per(Ms1),P er(Ms2),Performances dapprentissage des differents mode`les dans M,...,P er(Msn)} organisees par ordre de pertinence decroissant.m1(i) Valeur moyenne des performances dapprentissage situees a` ga-

    uche de la performance dapprentissage Per(Msi) dans la listeT , i = [1,2,...,n].

    m2(i) Valeur moyenne des performances dapprentissage situees a` dr-oite de la performance dapprentissage Per(Msi) dans la listeT , i = [1,2,...,n].

    v21(i); v22(i) Variances respectives a` m1(i); m2(i), i = [1,2,...,n].

    P (i) Discriminant de Fisher.FS Seuil adaptatif de selection des mode`les pertinents.Ts = {Per(Ms1),P er(Ms2),Liste des performances dapprentissage correspondantes aux mo-...,P er(Msk)} de`les selectionnes.Ms = {Ms1,Ms2,...,Msk} Sous-ensemble des mode`les selectionnes correspondants aux ca-

    racteristiques les plus pertinentes.Y = [y1,y2,...,yi,...,yNIm ] Ensemble des etiquettes correspondantes aux images dapprentis-

    sage; pour un proble`me de classification binaire, yi {-1,1}.f(x) Fonction de decision SVM.i; b Hyper-parame`tres dapprentissage SVM, i = [1,2,...,NIm].x Vecteur support SVM. Transformation non-lineaire de F dans un espace de Hilbert

    H; Card(H) > Card(F).K(x,xi) = (x),(xi)H Fonction noyau, i = [1,2,...,NIm].ct, u, et Parame`tres de noyaux.Mod1 Mode`le permettant de separer les deux classes C1 et C2 dans

    lalgorithme DAG-SVM.M Nombre de noyaux dans lapproche MKL.m Poids du noyau km, m = [1,2,...,M ].i Variables molles (slack variables en anglais).C Terme de regularisation de marge SVM.(L2, L1) Normes mixtes.L2 Norme quadratique.Sm() Fonction differentiable de (Sonnenburg et al., 2006). Valeur optimale dun sous-ensemble de contraintes selon le

    programme doptimisation de (Sonnenburg et al., 2006).K = [k1,k2,...,kM ] Ensemble des M noyaux de base.NCorr(km) Nombre dimages correctement classifiees avec le noyau km,

    m = [1,2,...,M ].TRkm Taux dapprentissage correspondant au noyau km, m = [1,2,

    3

  • INDEX DES SYMBOLES

    ...,M ].T R = [TRk1 ,TRk2 ,..., Ensemble des taux dapprentissage TRkm , m = [1,2,...,M ].TRkM ]K = [k1,k2,...,kM ] Organisation des noyaux de lensemble K selon lordre des ta-

    ux dapprentissage decroissant. = [1,2,...,M ] Ensemble des poids correspondants aux noyaux k

    m, m = [1,2,

    ...,M ].Ci Centres de la classe Ci dans un espace dattributs F , i = [1,2,

    ...,NC ].Nivl Niveau hierarchique l de la methode MC-MM, l = [1,2,...,k-1];

    k est le nombre de mode`les selectionnes par la methode SAC.Iq Image requete.Fm(Iq) Projection de Iq dans lespace Fm.di Distance Euclidienne entre Ci et F(Iq), i = [1,2,...,NC ].BTest Base dimages de test.CMsk(Iq) C Classification de limage Iq avec le mode`le Msk.CMsk,Msk1(Iq) C Classification de limage Iq avec les mode`les Msk, Msk1.C(Iq) = Classification de limage Iq selon la methode MC-MM.CMsk,Msk1,...,Ms1(Iq) C

    4

  • Introduction generale

    Contexte et motivations

    La classification dimages dans les bases heteroge`nes suscite de plus en plus dinteretdans le domaine de reconnaissance dimages. En effet, de nombreuses applications dessyste`mes de vision par ordinateur, comme les interactions Homme-Machine, la detectiondes evenements, le controle des processus et dautres applications specifiques a` un domainedonne, ont fait natre, conjointement au developpement croissant des images numeriquesissues du Web, un grand besoin pour mettre au point des techniques de classificationdimages plus efficaces. Toutefois, les performances de classification des images dans lesbases heteroge`nes dependent principalement de la qualite de description de ces images.

    Au debut, les techniques de description utilisees etaient, generalement, textuelles. Dansce cas, un ensemble de mots-cles est associe manuellement a` chaque image. Ce procede dedescription utilise beaucoup de semantique de par la description des images par un hu-main. Une expertise humaine, permettant dassurer une certaine correlation entre le texteet les images, est exigee. Il est cependant subjectif a` cause du tre`s grand nombre din-terpretations pouvant etre attribuees au contenu dune meme image. Ainsi, le proble`memajeur est que les resultats de reconnaissance dimages basee sur une description parmots-cles peuvent etre comple`tement hors sujet. Dautant plus, lorsquil sagit de baseheteroge`nes, ou` le contenu des images est assez varie et difficile a` decrire. Par ailleurs, las-sociation de mots-cles a` limage est une demarche realiste pour des petites bases dimages,mais elle est comple`tement impensable et impraticable pour des grandes bases. En raisonde ces limitations inherentes aux techniques de description textuelle, leur utilisation de-vient de plus en plus difficile dans les bases heteroge`nes, gerant une tre`s grande collectiondimages.

    De nouvelles techniques de description basees sur le contenu meme des images sontapparues et presentent de nos jours un interet croissant. Contrairement aux methodesdannotation textuelle, ces nouvelles techniques permettent lacce`s aux images via leursproprietes visuelles: informations qui peuvent etre tirees de limage elle-meme telles quela couleur, la texture, la forme, etc... Ces proprietes visuelles sont extraites sous formesdensembles dattributs appeles souvent caracteristiques. Par consequent, larchitecturetype dun syste`me de reconnaissance dimages par le contenu, designe generalement parlacronyme anglais CBIR (Content Based Image Recognition), repose principalement surdeux etapes primordiales: lExtraction dattributs visuels pour la description des imageset la Classification qui me`ne a` la reconnaissance de ces images. Dans ce cadre, plusieursapproches ont ete proposees pour developper soit des techniques dextraction dattributssoit des methodes de classification supervisees ou non supervisees.

    Dans le cas des bases heteroge`nes, dites aussi generalistes, les images sont de diverstypes et leur contenu est assez varie. De ce fait, les caracteristiques pertinentes pour ladescription dune categorie dimages ne sont pas necessairement efficaces pour dautres.

  • INTRODUCTION GENERALE

    Generalement face a` ce proble`me, des caracteristiques de differents types (dites aussiheteroge`nes) sont employees pour assurer une description robuste des images. Cette largedescription couvre, generalement, la majorite des caracteristiques visuelles des imagesdans les bases heteroge`nes. Cependant, elle souffre essentiellement dune grande dimen-sionnalite. De plus, selon la base dimage consideree, une partie de cette description estsouvent non adaptee au contenu de la base et par consequent inefficace lors de la phasede reconnaissance. Dou`, la necessite de selection des caracteristiques pertinentes selonle contenu de la base dimages consideree. En outre, generalement les caracteristiquesselectionnees ne disposent pas des memes performances de discrimination. Considerantleffet negatif des caracteristiques les moins performantes, une simple concatenation detoutes les caracteristiques selectionnees ne me`ne pas toujours a` des resultats de clas-sification optimaux. En consequence, lutilisation dun algorithme de classification, quisadapte aux pouvoirs discriminants des differentes caracteristiques selectionnees ainsi quele contenu de la base dimages utilisee, est bien recommandee. Cela permet dameliorerdavantage les taux de reconnaissance finaux.

    Dans ce travail nous nous interessons a` la reconnaissance dimages par le contenu dansles bases dimages heteroge`nes. La phase de reconnaissance est totalement automatiqueet adaptee au contenu de la base consideree. Aucune retroaction de lutilisateur pourindiquer un bouclage de pertinence nest envisagee. Le syste`me etudie se base ainsi surune construction hors ligne dune large description dimages, qui repose sur une varietede caracteristiques heteroge`nes. Ce sujet de recherche etait et reste un proble`me ou-vert et difficile a` cause de la grande difficulte de description des images dans ce typede bases et la complexite de combinaison des caracteristiques heteroge`nes. Dans cettethe`se, nous contribuons a` la resolution de quelques problematiques liees aux syste`mes dereconnaissance dimages heteroge`nes par le contenu. Une methode de selection adapta-tive des caracteristiques les plus pertinentes et une methode de classification hierarchiquemulti-mode`les sont proposees.

    Contribution et plan du manuscrit

    Les travaux effectues dans le cadre de cette the`se portent sur lextraction dattri-buts heteroge`nes, loptimisation de la description et/ou la dimension des caracteristiques,la selection des caracteristiques les plus pertinentes et le developpement dune nouvelleapproche de classification dimages heteroge`nes. Loriginalite de notre travail reside prin-cipalement dans la selection adaptative des caracteristiques les plus pertinentes et laclassification hierarchique multi-mode`les. Le manuscrit de la the`se est ainsi organise enquatre chapitres, de la manie`re suivante :

    Dans le premier chapitre, les elements fondamentaux dun syste`me de reconnaissancedimages par le contenu sont presentes. Nous discutons ainsi les bases dimages et leurscontenus, les types dattributs existants en litterature, les deux categories de classifica-tion et les mesures de pertinence dediees aux syste`mes CBIR. En particulier, les basesdimages heteroge`nes employees dans cette the`se sont exposees. Suite a` une presentationde letat-de-lart des differentes techniques de classification qui existent dans la litterature,lensemble des differentes caracteristiques heteroge`nes retenues est detaille. Pour ameliorerles performances de reconnaissance basee sur cet ensemble de caracteristiques, une op-

    7

  • INTRODUCTION GENERALE

    timisation de certaines dentres elles est egalement introduite. Une large evaluation deces caracteristiques, apre`s optimisation, est fournie a` la fin de ce chapitre. Cette etudemontre que le pouvoir discriminant de chaque caracteristique depend du contenu de labase dimages consideree.

    Le deuxie`me chapitre est consacree a` la selection des caracteristiques les plus perti-nentes. Initialement, les proprietes des deux categories de selection: Filtres et Envelop-pantes sont rappelees. Les methodes de selection les plus utilisees, en particulier la tech-nique lineaire danalyse en composantes principales et la selection basee sur les algorithmesgenetiques sont decrites. Une etude singulie`re des fonctions de selectivite employees parces algorithmes est aussi effectuee. Ensuite, une nouvelle methode de selection adaptativedes caracteristiques les plus pertinentes est proposee. Levaluation des performances decette methode de selection est ensuite presentee. Une comparaison avec les differentesmethodes de selection traitees, dans ce chapitre, est egalement fournie.

    Dans le troisie`me chapitre, lapproche dapprentissage par noyaux multiples connuepar lacronyme anglais MKL (Multiple Kernel Learning) appliquee a` la reconnaissancedes images heteroge`nes par le contenu est abordee. Dans cette the`se, lapproche MKLest consideree en particulier pour les Machines a` Vecteurs Supports (SVM). Suite a` unebre`ve exposition des notions de bases des SVMs, lapproche MKL est presentee. En tenantcompte de limportance de letape de calcul des poids de noyaux dans cette approche,une nouvelle methode de ponderation des noyaux est proposee. Une evaluation de laclassification SVM a` noyaux multiples basee sur la nouvelle ponderation, ainsi quunecomparaison avec un algorithme recent, sont fournies a` la fin de ce chapitre.

    Le quatrie`me chapitre est consacre a` la proposition dune nouvelle methode de clas-sification hierarchique multi-mode`les. Une evaluation de cette nouvelle methode de clas-sification en se basant sur la selection adaptative des caracteristiques, proposee dansle chapitre 2 est effectuee. Des comparaisons avec la methode de classification classique(employant un mode`le unique), lapproche des Multiple Instance Learning ainsi que lap-proche des sacs de mots-visuels et lapproche MKL sont fournies. Les performances denotre proposition en terme de temps de calcul sont aussi mises en evidence.

    Enfin, la conclusion generale presente une synthe`se des contributions apportees ainsique les pistes definissant des perspectives possibles pour des travaux futurs.

    8

  • Chapitre 1Extraction dattributs et classificationdimages dans les bases heteroge`nes

    Les elements fondamentaux dun syste`me de reconnaissance dimages par le contenusont presentes dans ce chapitre, une attention particulie`re est reservee au cas des basesheteroge`nes. Lensemble des caracteristiques heteroge`nes utilisees dans cette the`se estdiscute suite a` une presentation dun etat-de-lart des techniques de classification dimages.Une large evaluation des performances de reconnaissance de cet ensemble de caracteristi-ques est egalement fournie.

    10

  • 1.1. INTRODUCTION

    1.1 Introduction

    La recherche dimages a ete basee, initialement, sur lannotation textuelle des images(Jeon et al., 2003), (Ben-Ismail et al., 2008), sachant quune forte correlation doit existerentre le contenu de ces images et les etiquettes textuelles associees. Le cout de generation,ainsi que le fosse linguistique associes a` ces annotations (Hare et al., 2006), expliquentle grand interet accorde, aujourdhui, aux techniques de recherche dimages basees sur lecontenu (Gevers and Smeulders, 2004). Dans cet objectif et depuis une dizaine dannees,de nouvelles methodes ont permis la mise en place de differents syste`mes de recherche etde reconnaissance dimages par le contenu souvent designes par lacronyme anglais CBIR(Content Based Image Retrieval).

    Dans une premie`re partie de ce chapitre, les elements fondamentaux dun syste`mede reconnaissance dimages par le contenu sont etudies. Nous detaillons, en particulier,les bases dimages et leurs contenus, les types de description dimages, les methodes declassification et les mesures de pertinence dediees aux syste`mes CBIR dans la section 1.2.Les bases dimages heteroge`nes utilisees sont presentees dans la section 1.3. Dans unedeuxie`me partie, une synthe`se des techniques de classification dimages est exposee dansla section 1.4. Ensuite, lensemble des caracteristiques retenues pour la description desimages heteroge`nes est decrit dans la section 1.5. Une large evaluation des performancesde reconnaissance de cet ensemble de caracteristiques est egalement fournie a` la fin duchapitre.

    1.2 Reconnaissance dimages par le contenu

    ClassificationSupervise

    Basedimages

    dapprentissage

    Basedimagesde test

    Extractiondattributs

    Extractiondattributs

    Oui

    Non

    Apprentissage

    de classificationRsultas

    Classifieur

    pertinenceBoucle deOui

    Classification

    Fig. 1.1 Architecture dun syste`me de reconnaissance dimages par le contenu base surla classification.

    Larchitecture type des syste`mes CBIR est illustree par la figure 1.1. Cette architectureest composee principalement par deux etapes importantes, a` savoir lextraction dattributsvisuels pour la description des images et la classification qui me`ne a` la reconnaissance deces images. Dans ce cadre, plusieurs approches ont ete proposees pour developper soit destechniques dextraction dattributs, soit des methodes de classification. Par ailleurs, les

    11

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    performances dun syste`me CBIR reposent sur un ensemble delements fondamentaux telsque le type de la base dimage consideree, le type de la description dimages employee ainsique la methode de classification utilisee. Dans cette section, nous discutons lensemble deces elements. Lanalyse presentee, comporte les definitions principales de chaque partie, cequi permet de mieux comprendre son influence sur le syste`me de reconnaissance dimages.

    Un syste`me de reconnaissance dimages est souvent concu pour un type bien determinede base dimages. Les bases dimages se classent, generalement, en deux grandes categories:

    Les bases specialisees sont des bases dans lesquelles nous trouvons des imagesdun domaine particulier (images medicales, images satellitaires, images architectu-rales, images biometriques telles que les images de visages ou dempreintes, imagesartistiques telles que les tableaux de musee, etc...).

    Les bases heteroge`nes designees aussi par generalistes sont des bases dimagesde sujets tre`s varies comprenant des categories dimages tre`s differentes (par exemplecouchers de soleil, montagne, plage, animaux, vehicules, batiments, etc...).

    Les images dans le cas des bases specialisees ont le plus souvent un contenu semantiquehomoge`ne et presentent plusieurs caracteristiques en commun. Les applications visees sontgeneralement professionnelles. La reconnaissance dimages dans de telles bases est en faitun proble`me specifique a` un domaine bien particulier. On cite par exemple, lauthen-tification des individus dans les bases dimages biometriques telles que les bases diris(Jlassi and Hamrouni, 2010) et de visages (Rowshan et al., 2008). Ou encore la detectionde pathologies dans le cas des bases dimages medicales, tel que le depistage du cancerdu sein dans les bases mammographiques (Cheikhrouhou et al., 2009) et la segmenta-tion des tumeurs de cerveau dans les bases dimages IRM (Chen and Ruan, 2010). Uneintegration de la verite terrain definie par les connaissances dun expert du domaine estalors necessaire pour developper des algorithmes specifiques. Lobjectif est doptimiserlefficacite du syste`me de reconnaissance dimages dans ces bases et de repondre aussiaux attentes de lexpert. Par contre, la deuxie`me categorie de bases dimages generalistesregroupe des images appartenant a` des concepts heteroge`nes. Les images sont alors dedivers types et elles ont un contenu assez complexe. Par consequent, la difficulte de recon-naissance dimages est accrue dans ce type de bases a` cause des limitations de descriptiondes images. En outre, ces bases requie`rent lidentification prealable de concepts specifiquespour la creation dune verite-terrain.

    1.2.1 Types dattributs

    Les images sont des objets numeriques tre`s riches en terme dinformations. En plusde lespace memoire gigantesque exige, la manipulation directe de ces images dans unsyste`me de reconnaissance dimages par le contenu ne permet pas dobtenir des tempsde reponse realistes. Il convient donc dutiliser une representation de dimension reduitepour caracteriser le contenu de ces images. Lobjectif principal de lextraction dattri-buts est de determiner pour chaque image, une representation (signature) qui soit, dunepart compacte, pour etre rapidement accessible et facilement comparable, et dautrepart suffisamment comple`te pour bien caracteriser limage. Il est recommande dem-ployer des attributs invariants aux transformations colorimetriques telle que le changementdeclairage et aux transformations geometriques telle que le changement dechelle. Cecipermet de palier aux differentes transformations que peut subir une image. Cependant,

    12

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    la caracterisation robuste et discriminante des images reste un grand defi en traitementdimages. Generalement, les attributs dits de bas niveau sont souvent les plus utilisespour la description dimages par le contenu. Ces attributs decrivent les principales ca-racteristiques visuelles existant dans une image, a` savoir la couleur, la texture et la forme.

    1.2.1.1 La couleur

    Le physicien James Clerk Maxwell (Pascale, 2003) a prouve que toute couleur, etantinitialement une sensation provoquee par la lumie`re avec lil, le cerveau et notre experience,est une synthe`se de trois couleurs seulement: le rouge, le vert et le bleu. A` partir de cettedecouverte en 1865, la colorimetrie (la science qui etudie la couleur) a vu le jour.

    Les attributs couleurs sont les premiers utilises dans les syste`mes de reconnaissancedimages par le contenu et ils sont toujours les plus utilises grace a` leur simplicite dex-traction, leur richesse de description et leur efficacite de reconnaissance. Les auteurs dans(Bimbo, 2001) ont fourni une etude etendue des differentes methodes employees pour lex-traction dattributs couleurs. Un ensemble dattributs couleurs a ete teste pour etre inclusdans le standard MPEG-7 (Manjunath et al., 2001). Ces attributs couleurs dependent di-rectement de lespace couleur utilise pour la representation couleur de limage. Dans lalitterature, plusieurs espaces couleurs sont etudies.

    Defini en 1931 par la compagnie internationale de leclairage (C.I.E.), lespace couleurRVB (Rouge Vert et Bleu) represente les couleurs par synthe`se soustractive. Chaquecouleur est representee par trois composantes: rouge, vert et bleu. Lespace RVB estgeneralement lespace couleur de base dans lequel sont capturees les images. La figure 1.2illustre la decomposition dune image couleur en trois sous-images monochromes selonlespace couleur RVB.

    Fig. 1.2 Image couleur RVB: association de trois sous-images monochromes, corres-pondant respectivement au differentes composantes Rouge, Vert et Bleu.

    Les autres espaces couleurs representent des transformations directes de lespace RVB.Ces transformations ont pour objectif dameliorer la representativite colorimetrique delimage et dassurer des mesure de distance plus lineaires.

    Les espaces couleurs HSI, HSV, HSB et HLS (appeles communement HSx ) sont plusproches de la perception humaine de couleur que lespace couleur RVB, mais ils ne sont pasencore perceptuellement uniformes. Nous citons aussi les espaces couleurs YUV et YIQou` la composante Y represente la luminance du pixel et les pairs de composantes UV et IQ

    13

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    representent les composantes chromatiques. Nous pouvons trouver aussi lespace couleurXYZ, ou` les composantes X et Z sont les composantes chromatiques et la composante Y estla somme ponderee des valeurs R, V et B. Comme il nest pas perceptuellement uniforme,luniformisation de lespace XYZ se fait par une transformation projective qui debouchesur lespace couleur LUV. Dautres espaces couleurs existent aussi tels que HMMD, Lab,LST et YCrCb. Pour plus de details concernant les espaces couleurs, nous recommandionsle lecteur interesse de consulter la reference suivante (Pascale, 2003).

    1.2.1.2 La texture

    La texture est liee aux apparences de surface des images ce qui est dune grandeimportance dans tout domaine relatif a` la perception visuelle. Dans la litterature, noustrouvons plusieurs definitions de la texture. Nous citons parmi lesquelles: la textureest lattribut qui represente la distribution spatiale des niveaux de gris des pixels duneregion (IEEE-Press, 1990). Ou encore: la texture est lensemble des proprietes devoisinage locales des niveaux de gris dune region de limage (Livens et al., 1997). Bienquil ny ait pas jusqua` present une definition precise de la texture, toutes les definitionspossibles affirment que la texture est linformation generee par les variations des niveauxde gris entre des pixels voisins au sein dune image. Differents mode`les de texture sontillustres dans la figure 1.3.

    Fig. 1.3 Differents mode`les de texture.

    Les attributs textures sont de plus en plus utilises dans la description dimages car ilsattenuent certains proble`mes lies a` la description couleur. En effet, la description textureest tre`s efficace, surtout dans le cas dune distribution couleur tre`s proche. Les attributstextures sont divises en deux categories : La premie`re est deterministe et fait referencea` une repetition spatiale dun motif de base dans differentes directions. Cette approchestructurelle correspond a` une vision macroscopique des textures. La deuxie`me approche,dite microscopique, est probabiliste et cherche a` caracteriser laspect chaotique qui necomprend ni motif localisable, ni frequence de repetition principale.

    1.2.1.3 La forme

    Contrairement aux attributs couleurs et textures qui sinteressent a` la description ducontenu general de limage, les attributs formes sont capables de caracteriser les differentsobjets contenus dans limage.

    Generalement, ce type dattribut indique laspect general dun objet, comme soncontour, donc une segmentation sous forme de traitement preliminaire de limage est sou-vent necessaire. Deux categories dattributs formes peuvent etre extraites: La premie`re

    14

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    categorie est basee sur la geometrie des regions de limage. La deuxie`me est basee sur lesstatistiques des intensites de pixels des differentes regions dans limage.

    Une image peut subir des transformations geometriques comme la rotation, la trans-lation et le changement dechelle. Pour assurer une description assez robuste et efficace,les attributs formes couvrent, generalement, toutes les echelles de representation (allantdes details jusqu a` la forme grossie`re) que comporte un objet. De plus, ils sont sou-vent insensibles aux differentes variations causees par des transformations geometriques.La figure 1.4 presente un exemple des transformations geometriques que peut subir uneimage.

    Fig. 1.4 Differentes transformations geometriques que peut subir une image.

    1.2.2 Categories dattributs

    Les attributs visuels sont extraits a` partir de limage selon trois niveaux dabstractions:le niveau global, le niveau regions et le niveau points dinteret. Le premier niveau refle`teune description globale des images, tandis que les deux derniers permettent dassurer unedescription locale. De ce fait, les differents types dattributs, decrits dans la section 1.2.1,peuvent etre consideres pour limage entie`re ou pour une partie specifique de limage.Dans la litterature, il est dusage de distinguer deux categories dattributs: les attributsglobaux et les attributs locaux (Aly et al., 2009).

    1.2.2.1 Attributs globaux

    Lapproche globale de reconnaissance dimages par le contenu est initialement developpeedans les syste`mes Photo-Book (Pentland et al., 1994), QBic (Flickner et al., 1995) ouVirage (Bach et al., 1996), et plus recemment par ImageRover (Sclaroff et al., 1997),PicToSeek (Gevers and Smeulders, 1999), Compass (Brunelli and Mich, 2000) et Ikona(Boujemaa et al., 2001). Cette approche globale permet la reconnaissance des images ense basant sur des similarites visuelles mesurees sur les images entie`res. Une image decriteglobalement est representee par un seul vecteur dattributs, ce qui nest pas le cas avec lesattributs locaux. Par consequent, la phase de classification et de reconnaissance devientplus rapide. Generalement, ce type dattributs est robuste et peu affecte par le bruit quipeut sajouter au contenu de limage. Les histogrammes de couleur ou de niveaux de griset les correlogrammes sont des exemples typiques de ce type de description (Stricker and

    15

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    Swain, 1994), (Huang et al., 1997). Lensemble des caracteristiques globales, employeesdans ce travail de the`se, est presente dans la section 1.5.

    1.2.2.2 Attributs locaux

    Lapproche locale de reconnaissance dimages se base essentiellement sur la descriptionde parties specifiques dans limage, representees souvent par des sous-regions homoge`nes.Plusieurs travaux ont ete proposes pour la localisation de ces sous-regions. Les subdivisionssystematiques dimages en carres sont simples et rapides mais imprecises (Moghaddamet al., 1999), (Malki et al., 1999). Cependant, une subdivision manuelle assure des seg-mentations en regions plus proches des attentes de lutilisateur mais elle nest pas adapteepour des bases dimages de grande taille (Bimbo and Vicario, 1998). Generalement, lesmethodes de segmentation non-supervisees sont les plus utilisees. Ces methodes per-mettent de detecter automatiquement les sous-regions homoge`nes dans limage (Carsonet al., 1999), (Ma and Manjunath, 1999) en se basant sur les repartitions de couleuret de texture. Des echantillons dimages segmentees par region de la base COREL sontillustrees dans la figure 1.5. Les sous regions detectees sont representees par leurs couleursdominantes (Chen and Wang, 2004).

    Fig. 1.5 Echantillons dimages segmentees de la base COREL.

    La description dimage est construite dans ce cas par un ensemble de vecteurs dat-tributs. Les attributs utilises sont, generalement, extraits pour chaque sous regions danslimage. Une technique recente impliquant la mise en correspondance de regions pour larecherche dimages est proposee par (Wang et al., 2001) dans le syste`me SIMPLIcity etplus tard par (Sridhar et al., 2002) et (Stehling et al., 2002). En realite, la similariteentre deux images est mesuree comme une combinaison des similarites entre les regionsconstituantes de chaque image. Le syste`me effectue, dans ce cas, une recherche globalecar toutes les primitives de limage sont prises en compte.

    Il est possible egalement de caracteriser le contenu des images par le biais de la des-cription des points dinteret. Plusieurs methodes de detection de points dinteret dans lesimages sont proposees tout en soulignant differents aspects dinvariance avec differentesproprietes et differentes tailles dechantillons. On cite, par exemple, la Difference de Gaus-sienne (DoG pour Difference of Gaussian) (Lowe, 2004), Harris Laplace (Mikolajczyk andSchmid, 2004) et Hessien Affine (Mikolajczyk et al., 2005). Les approches locales baseessur des descriptions de points dinteret permettent deffectuer des recherches precises maisau prix dun temps de calcul tre`s eleve (Schmid et al., 1998), (Gouet and Boujemaa, 2001).Effectivement, le nombre eleve des points dinteret detectes par image (quelques centaines)et laspect dimensionnelle des descripteurs (128 dimensions pour un vecteur unique SIFTScale-Invariant Feature Transform (Lowe, 2004)) rendent la mise en correspondance entreles images tre`s couteuse en temps de calcul. Des travaux recents ont contribue a` la com-pensation des limites de ces descripteurs en utilisant une nouvelle approche appelee sacdes descripteurs ou sac de mots-visuels (Csurka et al., 2004b), (Willamowski et al., 2004),(Zhang et al., 2007). Lidee est de construire pour chaque image une caracteristique glo-bale qui determine les differentes occurrences dun ensemble de categories de descripteurs

    16

  • 1.2. RECONNAISSANCE DIMAGES PAR LE CONTENU

    locaux, appeles aussi mots-visuels. Les performances dune telle approche exigent unemajorite de points dinteret en commun des images appartenant a` un meme concept.

    Par consequent, les travaux employant une description locale se situent, generalement,dans des contextes precis et les approches utilisees sappuient sur certaines proprietesconnues de ces contextes pour fonctionner. Les syste`mes bases sur une description localesmanquent donc de generalite par rapport aux images quils peuvent traiter. Effectivement,les attributs locaux sont surtout utilises dans le cas des bases dimages dites specifiquesou` les images appartenant a` une categorie bien determinee representent une repartitionassez homoge`ne. Les methodes developpees sont souvent dediees aux corpus utilises etparfois peu adaptables a` dautres images. Ainsi, une description locale est beaucoup moinsperformante dans le cas des images heteroge`nes, ou` les images dune meme classe nepresentent pas forcement une majorite de sous regions ou de points dinterets en commun.

    1.2.3 Methodes de classification et evaluation des performances

    1.2.3.1 Classification

    On distingue principalement deux types de classification, supervisee et non-supervisee,suivant que lon dispose ou non dune expertise des images a` classifier (figure 1.1). Laclassification supervisee se base sur une phase dapprentissage ou` lon cherche a` produireautomatiquement des re`gles de decision a` partir dimages deja` classifiees. Le choix de latechnique dapprentissage a` utiliser est tre`s important dans un tel processus. La classifica-tion de nouvelles images de test est realisee dans une seconde phase, appelee generalisation.A` partir des images dapprentissage, le classifieur utilise doit bien generaliser les re`glesde decision apprises sur de nouvelles images requetes appartenant a` une base dite detest. Letape dapprentissage est realisee hors ligne, alors que celle de generalisation esteffectuee en ligne. La classification non-supervisee se rame`ne quand a` elle au regroupe-ment des images de la facon la plus naturelle possible sans aucune connaissance a priori ducontenu de la base. Cette volonte de regrouper naturellement les images est assez ambigue.Elle est formalisee, le plus souvent, par lobjectif de reduire la variation du contenu desimages intra-classe et de mieux caracteriser la discrimination des images inter-classe. Unetat-de-lart des differentes techniques de classification, qui existent dans la litterature,est presente dans la section 1.4.

    1.2.3.2 Retroaction et bouclage de pertinence

    Generalement, les resultats de classification sont obtenus dune facon automatiqueselon la description prealable du principe de base des differents types de classification.Toutefois, il est possible de se servir dune boucle de pertinence ou` lutilisateur raffineprogressivement lefficacite de reconnaissance. Dans ce cas, lutilisateur marque les imagesresultantes de la classe candidate comme pertinentes, non pertinentes ou neutres vis a` vislimage requete. Le processus de reconnaissance est ainsi repete a` chaque fois avec cesnouvelles informations jusqua` lobtention du resultat desire. Cette interaction nest pastoujours efficace, sachant quelle suppose un ensemble de connaissance chez lutilisateur.On distingue generalement deux types dutilisateurs: les experts et les non-specialistes.Uniquement, les experts peuvent interagir efficacement avec le syste`me pour ameliorer lesresultats de reconnaissance. Cependant, pour les non-specialistes, aucune interaction nepeut etre consideree.

    17

  • 1.3. BASES DIMAGES HETEROGE`NES UTILISEES

    1.2.3.3 Performances de classification dimages

    Levaluation des performances dun syste`me de reconnaissance dimages concerne a` lafois sa capacite de reconnaissance et son efficacite en terme de rapidite dexecution. Cettedernie`re est facile a` evaluer, il suffit de mesurer le temps de reponse moyen du syste`me surplusieurs requetes. Levaluation des capacites de reconnaissance est effectuee en comparantle resultat de classification obtenu a` un resultat de reference, appele souvent verite terrain.En effet, la connaissance de la verite-terrain permet de realiser une evaluation automatiqueet de fournir des performances fiables. Les crite`res de qualite les plus utilises sont desmesures de performance standard (Bimbo, 2001), il sagit principalement de la precisionet du rappel. Soit pour une image requete donnee, TP le taux des vrai positifs, FP letaux des faux positifs et P le nombre total des images pertinentes dans la base. Notonsque les taux TP et FP indiquent, respectivement, le nombre dimages pertinentes etnon-pertinentes retrouvees. La precision et le rappel sont definis comme suit:

    Precision =TP

    TP + FP, Rappel =

    TP

    P(1.1)

    En variant le nombre dimages requetes, un graphe de precision-rappel peut etre ob-tenu. La precision est souvent une fonction decroissante du rappel. Le graphe typique deprecision-rappel est illustre par la figure 1.6.

    Fig. 1.6 Graphe typique de precision-rappel.

    Vu que les valeurs scalaires de la precision et du rappel sont comprises toutes les deuxentre 0 et 1, le graphe de precision-rappel est dit ideal si la precision est egale a` un pourtoute valeur de rappel.

    1.3 Bases dimages heteroge`nes utilisees

    Pour evaluer et valider les differentes approches etudiees et developpees dans ce travail,trois bases dimages heteroge`nes sont utilisees, a` savoir, la base COLUMBIA, la base

    18

  • 1.3. BASES DIMAGES HETEROGE`NES UTILISEES

    COREL et la base CALTECH-256. Ces bases constituent des concepts bien definies ou`chaque image ne peut appartenir qua` une seule classe. Dans ce qui suit, une descriptiondes trois bases dimages utilisees est fournie.

    1.3.1 La base dimages COLUMBIA

    La base dimages COLUMBIA contient des images tirees dobjets 3D pris en differentespositions. Dans cette the`se, la collection utilisee de cette base est COIL-100 1. La collec-tion COIL-100 est utilisee surtout dans le domaine de reconnaissance dobjets. Elle estconstituee par des images en couleurs prises a` partir de 100 objets differents. Lensemblede ces objets est affiche dans la figure 1.7.

    Fig. 1.7 Echantillons des 100 objets de la base dimages COIL-100 de COLUMBIA.

    A` laide dun plateau motorise (tourne-disques) et un fond noir, chaque objet estcapture selon differentes positions pour constituer une classe de la base. Le plateau esttourne de 360 pour changer la position de lobjet par rapport a` une camera couleur fixe.Une image de lobjet est prise a` chaque intervalle de 5. Ceci correspond a` 72 positionsdifferentes pour chaque objet. COIL-100 contient donc 7200 images de taille 128 128pixels.

    1.3.2 La base dimages COREL

    La base COREL 2 est tiree de differents CD-ROMs publiees, strictement pour des rai-sons de recherche, par COREL corporation. Cette base comprend 2300 images categoriseespar le concepteur en une verite-terrain de 23 classes thematiques (personnes, animaux,fleurs, montagnes, etc.), contenant 100 images chacune. Chaque image est de taille 384256 pixels ou 256 384 pixels. Cette base est consideree comme une reference pour lesspecialistes travaillant sur la reconnaissance dimages dans les bases heteroge`nes. Desechantillons de differentes classes dimages contenues dans la base COREL utilisee sontrepresentes dans la figure 1.8.

    1. La base COIL-100 (Columbia Object Image Library) est accessible en ligne a` ladresse suivante:http://www.cs.columbia.edu/CAVE/databases.

    2. La base COREL peut etre telechargee du site web de James Z. Wangs Research Group, disponibleen ligne a` ladresse suivante: http://wang.ist.psu.edu/docs/home.shtml.

    19

  • 1.3. BASES DIMAGES HETEROGE`NES UTILISEES

    Fig. 1.8 Echantillons dimages de differentes classes de la base COREL utilisee.

    1.3.3 La base dimages CALTECH

    Fig. 1.9 Echantillons dimages de differentes classes de la base CALTECH-256 utilisee.

    La base CALTECH-256 3 (rassemblee par (Griffin et al., 2007)) est composee dimagestirees de 256 categories differentes, cest une extension de la base CALTECH-101 4. Ellecontient de 80 a` 827 images par categorie. Le nombre total des images contenues dans

    3. La base CALTECH-256 contient moins dalignement entre les images dune meme classesque dans le cas de la base CALTECH-101. Elle est disponible en ligne a` ladresse suivante:http://www.vision.caltech.edu/Image Datasets.

    4. La base CALTECH-101 (rassemblee par (Fei-Fei et al., 2006)) est composee dimages tirees de 101categories dobject, elle contient de 31 a` 800 images par categorie. Cette base dimages est connue par sagrande variabilite inter-classe.

    20

  • 1.3. BASES DIMAGES HETEROGE`NES UTILISEES

    cette base est 30608 images de taille 300 300 pixels. Cette base est connue par unegrande variabilite inter et intra-classes. Dans ce travail, nous utilisons un ensemble de 23classes de la base CALTECH-256, contenant 100 images chacune. La figure 1.9 illustredes echantillons de differentes classes dimages contenues dans le sous-ensemble utilise.

    Les noms ainsi que les identifiants (IDs) correspondants aux 23 classes utilisees a` partirdes deux bases dimages COREL et CALTECH-256 sont presentes dans le tableau 1.1 (onmaintient lappellation anglaise).

    Tab. 1.1 Noms et identifiants des 23 classes utilisees a` partir des deux bases dimagesCOREL et CALTECH-256.

    IDs Noms de classesCOREL CALTECH-256

    0 Buses Backpack1 Horses Baseball-bat2 Dinosaurs Bathtub3 Elephants Bear4 Flowers Billiards5 Forests Binoculars6 African peoples and villages Bowling-ball7 Food Bread-maker8 Mountains and glaciers Calculator9 Cars Camel10 Dogs Chandelier11 Lizards Chess-board12 Fashion models Chimp13 Sunset scenes Coin14 Beach Computer monitor15 Waterfalls Cormorant16 Antique furnitures Diamond-ring17 Battle Ships Dolphin18 Skiing Elk19 Desserts Fern20 Butterfly Fire-truck21 Historical buildings Harp22 Night scenes Ketch

    Nos experimentations sont realisees en utilisant, pour chaque base dimages, neuf sous-bases differentes. Ces sous-bases contiennent un nombre variable de classes thematiquesallant de 3 jusqua` 23 classes. Dans les bases heteroge`nes, certaines images de classesdifferentes peuvent se reveler dun aspect tre`s proches, alors que des images de la memeclasse peuvent avoir des structures dissemblables. De ce fait, la classification super-visee est utilisee. Grace a` letape dapprentissage, ce type de classification assure unemeilleure separation des differentes classes dans les bases dimages heteroge`nes. Unesynthe`se des techniques de classification, existant dans la litterature, est presentee dans lasection 1.4. Par ailleurs, vu la nature heteroge`ne et le manque de connaissance a` priori surle contenu des bases utilisees, les images appartenant semantiquement au meme conceptne presentent pas forcement une majorite de sous-regions ou de points dinteret com-muns. Par consequent, lutilisation dune description globale des images est adoptee.Dautre part, les resultats de reconnaissance obtenus restent fortement dependants de

    21

  • 1.4. TECHNIQUES DE CLASSIFICATION DIMAGES

    la description dimages utilisee. Pour couvrir les differentes caracteristiques visuelles desimages heteroge`nes, une large description est generalement recommandee (Manjunathet al., 2001), (Androutsos et al., 2005). Dans notre cas, un ensemble de caracteristiquesde differents types est extrait. Plus de details sont fournis dans la section 1.5. Ainsi,le syste`me CBIR etudie dans notre contexte de travail, se base essentiellement sur uneconstruction hors ligne dune large description globale des images. Letape de reconnais-sance est basee sur une technique de classification supervisee. Cette etape est totalementautomatique et adaptee au contenu de la base consideree. Aucune retroaction de lutilisa-teur, pour levaluation des resultats a` travers un bouclage de pertinence, nest envisagee.Dans la section suivante, un etat-de-lart des techniques de classification dimages estpresente.

    1.4 Techniques de classification dimages

    Les performances dun syste`me de reconnaissance dimages par le contenu reposentessentiellement sur les caracteristiques ainsi que la categorie dattributs utilisees pour ladescription des images. Cependant, le bon usage de cette description dimages, a` traversun algorithme de classification, qui sadapte au processus de reconnaissance considere, estdune extreme importance. Ainsi, la methode de classification utilisee influe, conjointe-ment avec la nature de description dimages employee, sur les resultats de reconnaissanceobtenus. Le crite`re principal de toute methode de classification se base sur le fait que lesimages appartenant au meme concept doivent avoir au moins une ou plusieurs proprietescommunes (Jurgen, 2004). Le processus de classification general comporte deux etapes:letape dapprentissage et celle de generalisation. Letape dapprentissage sert a` construireun mode`le a` partir des images de la base consideree. Letape de generalisation representela classification proprement dite. Particulie`rement, le mode`le construit en phase dappren-tissage est utilise en generalisation pour estimer les classes des differentes images requetes(Han and Kamber, 2006).

    Une grande variete de syste`mes/approches et techniques de classification se trouvedans la litterature. Cependant, aucune approche ne pretend etre la plus performante pourtous les proble`mes de classification (Stork et al., 2001). Dans ce cadre, un bref etat-de-lartdes differentes techniques de classification est presente dans cette section. Nous rappelonsque ces techniques sont principalement categorisees en deux familles: la classification non-supervisee et la classification supervisee (section 1.2.3.1).

    1.4.1 Methodes de classification non-supervisee

    Dans lapproche de classification non-supervisee, les classes qui constituent la basedimages ne sont pas identifiees. Generalement, le nombre de classes est egalement in-connu. Ainsi, la classification non-supervisee, connue en anglais par clustering consistea` determiner les differentes classes naturellement sans aucune connaissance prealable.Lobjectif, dans ce cas, est didentifier une structure dans les images de la base en se ba-sant sur leurs contenus. Tout en caracterisant la discrimination des images inter-classe etreduisant la variation du contenu des images intra-classe, les images sont attribuees auxdifferentes classes estimees selon la similarite de leurs caracteristiques. Par consequent, lechoix dune mesure de distance appropriee est une etape importante dans tout algorithmede clustering. Cette distance specifie la facon avec laquelle la similitude de deux images

    22

  • 1.4. TECHNIQUES DE CLASSIFICATION DIMAGES

    est calculee. Cela est dune grande influence sur la forme finale des classes. Effectivement,certaines images peuvent etre proches lune de lautre en fonction dune certaine distanceet plus eloignees selon une autre (Dengsheng and Guojun, 2003). La tache de regroupe-ment dimages peut etre eventuellement simplifiee si le nombre de classes dans la baseest connu, mais la classification reste toutefois non-supervisee puisque le classifieur nesttoujours pas guide par des images deja` etiquetees. De ce fait, lanalyse de la repartitiondes images, dites aussi observations, dans lespace des attributs reste le seul moyen quipermet de caracteriser la signification des veritables classes. Dans la suite, nous effectuonsun apercu plus detaille des methodes de classification non-supervisee qui existent dans lalitterature.

    Il existe plusieurs approches pour la categorisation des methodes de classificationnon-supervisee. Souvent, ces methodes sont regroupees en deux grandes categories: pa-rametriques et non-parametriques (Fukunaga, 1972). Les methodes parametriques sontbasees sur une pre-analyse dune structure de donnees globale. Les performances de cetype de methodes dependent essentiellement des hypothe`ses effectuees suite a` lapproxi-mation de leurs parame`tres (le nombre de classes par exemple). Le crite`re de classificationle plus intuitif et frequemment utilise est le crite`re de lerreur quadratique. Il est parfaite-ment adapte au cas des classes compactes et isolees (Jain et al., 1999). Parmi les methodesparametriques qui se basent sur ce crite`re, la methode la plus communement utilisee estcelle de lalgorithme K-means (McQueen, 1967). Plusieurs variantes de cet algorithmeont ete proposees pour gerer la sensibilite a` la repartition initiale (Anderberg, 1973).Dans le cas des methodes non-parametriques, aucune hypothe`se sur le(s) parame`tre(s)caracterisant(s) nest effectuee. Le nombre de classes est particulie`rement non defini. Lesimages sont regroupees selon une fonction de densite. Par consequent, la performance desmethodes non-parametriques est, naturellement, tre`s sensible a` la distribution dimagesdans la base. Lexemple classique dapproches non-parametriques est lalgorithme appeleCAST pour Cluster Affinity Search Technique. Cest une approche iterative (Portnoyet al., 2002) qui examine efficacement les observations aberrantes (Shamir and Sharan,2002).

    Une deuxie`me structuration des methodes de classification non-supervisee est couram-ment utilisee dans la litterature. Cette structuration inclut trois categories:

    Les methodes de classification hierarchiques: constituent la famille de tech-niques qui gene`rent des suites de partitions embotees les unes dans les autres, etallant depuis la partition triviale ou` une seule classe contient toutes les observationsjusqua` la partition triviale ou` chaque observation constitue une classe a` part. Lamethode de classification hierarchique doit choisir une partition assez adaptee entreces deux extremes. La taxonomie communement utilisee des methodes hierarchiques,comprend cinq sous-categories (Jain et al., 1999): Les approches Ascendantes /Descendantes , Monothetiques / Polythetiques , Deterministes / Floues , Deterministes / Stochastiques et Incrementales / Non-incrementales .

    Les methodes de classification par partitionnement: permettent principale-ment dorganiser les images en K classes. Comme K est un parame`tre dentree, unecertaine connaissance du domaine est necessaire, ce qui nest pas toujours dispo-nible en pratique (Ester et al., 1996). Un algorithme de partitionnement commencegeneralement par une partition initiale, puis utilise une strategie de controle iterativepour optimiser une certaine fonction objective. Chaque classe est representee par soncentre de gravite (K-centroid) ou par une des images de la classe situee a` proximitede son centre (K-medoid). Un ensemble de methodes appartenant a` cette categorie,

    23

  • 1.4. TECHNIQUES DE CLASSIFICATION DIMAGES

    telles que le mode`le de melange de gaussienne, lalgorithme EM pour Expectation-Maximization et le mode`le non-supervise de Bayes existent dans la litterature. Parailleurs, lalgorithme de partitionnement le plus populaire est lalgorithme K-means(Berry, 2003).

    Les methodes de classification par deux voies de clustering, connuespar co-clustering ou bi-clustering : sont des algorithmes ou` non seulement lesimages sont groupees, mais aussi leurs caracteristiques, cest a` dire, si les images sontrepresentees dans une matrice de donnees, les lignes et les colonnes sont regroupeesen meme temps (Kim and Cipolla, 2008).

    Lapercu presente des differentes approches de clustering demontre une large gammede methodes de classification non-supervisee. Le choix dune methode particulie`re dependfortement de lapplication et du type de sortie etant souhaite. Dans la section suivante,les methodes de classification supervisee sont exposees.

    1.4.2 Methodes de classification supervisee

    Dans cette approche de classification, une connaissance de la signification de chaqueclasse est exigee. Evidemment le nombre de classes est fixe et les images disponibles sontdeja` attribuees aux differentes classes de la base. Lobjectif est ainsi daffecter de nou-velles images aux classes appropriees suivant la modelisation effectuee en phase dappren-tissage. En general deux types de modelisation peuvent etre distinguees: la modelisationintrinse`que et la modelisation discriminante.

    Modelisation intrinse`que: permet dexpliciter les classes par la definition de leursproprietes intrinse`ques. Dans ce cas, lobjectif est de determiner un mode`le quicaracterise au mieux chaque classe dans lespace dattributs. La classification denouvelles images de test repose sur les mesures de similarite entre ces images et lesdifferents mode`les de classes.

    Modelisation discriminante: assure une description implicite des classes par ladefinition des frontie`res de decision permettant de discriminer ces classes. Ainsi,le but est de chercher des hyper-plans, dans lespace dattributs correspondant.Ces hyper-plans doivent separer au mieux les differentes classes de la base. Engeneralisation, il suffit de trouver de quel cote de ces hyper-plans se trouve chaqueimage requete.

    Une illustration de ces deux types de modelisation est presentee par la figure 1.10. Ense basant sur lune de ces modelisation, plusieurs methodes de classification superviseesexistent dans la litterature. Nous decrivons succinctement dans la suite les methodes lesplus utilisees pour la classification dimages.

    Comme methodes intrinse`ques, la classification bayesienne determine la probabilitedappartenance de chaque image aux differentes classes de la base (Langley and Sage,1999). Cette methode est dite Nave ou Simple car elles supposent que les images dap-prentissage sont toujours independantes. Si les images ne suivent pas une loi de distribu-tion connue, les conditions de probabilite employees seront erronees et la re`gle de Bayesne peut etre appliquee. Les arbres de decision, quand a` elles, representent des processusrecursifs (Quinlan and Rivest, 1989), (Quinlan, 1993). Les images requetes sont examineespar larbre de decision de chaque classe dans la base. Concre`tement, chaque noeud danslarbre de decision contient un test (de type Si ... Alors ) correspondant a` la valeur

    24

  • 1.4. TECHNIQUES DE CLASSIFICATION DIMAGES

    a) b)

    Fig. 1.10 Approche de classification supervisee: type de modelisation a) Intrinse`que etb) Discriminante.

    dun attribut donne. Les feuilles de larbre representent les decisions tirees a` partir desresultats de ces tests. Les arbres de decision fonctionnent mieux si le nombre de valeurspossible pour chaque attribut est faible. Par contre, pour un grand jeu de donnees, larbredevient illisible. Dans le meme contexte, les reseaux de neurones artificiels, connus parlacronyme anglais ANN (Artificial Neural Networks), reposent sur la theorie des percep-trons (Maren, 1990). Un ANN est compose de plusieurs neurones repartis sur une couchedentree, une couche de sortie et un nombre de couches cachees. Par ailleurs, il nexistepas de re`gle pour choisir le nombre de couches du reseau. Les MLP pour Multi LayerPerceptron sont constitues par une ou plusieurs couches cachees (Freeman and Skapura,1991). Par contre, les reseaux a` fonctions radiales de base, connus par lacronyme anglaisRBF (Radial Basis Functions), sont constitues par une seule couche cachee (Oyang et al.,2005). Generalement, les ANNs sont robustes aux erreurs et sont donc bien adaptes auxproble`mes dapprentissage dimages bruitees. Cependant, ils ont une pauvre possibilitedinterpretation et un choix de parame`tres tre`s delicats.

    Par ailleurs, les methodes discriminantes representent souvent des techniques de clas-sification lineaires. Deux types de classification lineaire sont utilises: les fonctions dis-criminantes et les machines a` vecteurs supports. Les fonctions discriminantes sont desmethodes de classification simples qui separent les images appartenant aux differentesclasses en se basant sur une analyse lineaire. Ces fonctions peuvent etre performantesdans le cas ou` les differentes classes de la base sont lineairement separables. Cependant,dans la plus part des cas, elles ne permettent pas datteindre des precisions considerables.Afin dameliorer les performances de ces fonctions, de nouvelles variantes sont presenteesdans la litterature (Kimura et al., 1997). Face aux fonctions lineaires, les machines a` vec-teurs supports, connues par lacronyme anglais SVMs (Support Vector Machines), sontinitialement concues pour les proble`mes de classification binaires. Elles permettent deseparer lineairement les exemples positifs des exemples negatifs dans lensemble des imagesdapprentissage par un hyper-plan qui garantisse un maximum de marge (Vapnik, 1999).Lefficacite des SVMs est souvent superieure a` celle de toutes les autres methodes declassification supervisees. Pour les proble`mes de non-separabilite, les SVMs permettentdeffectuer une transformation non-lineaire des observations dentree dans un espace dedimension superieure pour se ramener au cas lineaire. En outre, les SVMs peuvent sadres-

    25

  • 1.5. CARACTERISTIQUES U