Comparaison d’images binaires reposant sur une mesure locale des dissimilarités. Application à la classification.

17

18

18

1.4.2 Analyse multir´esolution (2i`eme g´en´eration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.3 Ondelettes (2i`eme g´en´eration)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.4 Transformation en ondelettes rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.5 Lifting scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table des mati`eres

vi

2

Morphologie math´ematique et analyse multir´esolution

2.1 Morphologie math´ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1 D´efinitions g´en´erales

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Filtres morphologiques

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 Construction de filtres morphologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.3 Filtres altern´es s´equentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.4 Filtres auto-duaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Analyse multir´esolution morphologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1 D´ecomposition en ondelettes coupl´ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2 D´ecomposition en ondelettes d´ecoupl´ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.3 Ondelettes de Haar morphologiques en 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.4 Ondelettes de Haar morphologiques en 2d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Caract´erisation morphologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1 Granulom´etrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 M´ethodes utilis´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.1 Utilisation des d´etails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

´Etude des filtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.2

Partie II Mesures de Dissimilarit´es

1

La comparaison d’images : panorama

1.1 Les m´ethodes de comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1 Les descripteurs des images

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

19

20

20

22

23

23

24

26

26

27

27

28

28

28

28

29

29

30

31

31

36

39

40

42

47

47

1.1.2 Les mesures de similarit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.3 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Les m´ethodes sp´ecifiques aux images binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2 M´ethodes de comparaison directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3 Les m´ethodes indirectes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.5 Vers une nouvelle m´ethode de comparaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Distance de Hausdorff (DH) et ses variantes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.1 Distance de Hausdorff, g´en´eralit´es

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.2 Propri´et´es g´en´erales de la distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.3 Quelques versions modifi´ees de la distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . .

1.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

Mesure locale de la DH

2.1 Quel sens donner `a l’expression « dissimilarit´e locale » ? . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 D´efinition de la DH locale

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 D´efinition na¨ıve de la DH locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 Modification de la d´efinition na¨ıve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.3 Distance de Hausdorff locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Propri´et´es de la DH locale HDW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1 Propri´et´es g´en´erales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2 Propri´et´es d´ependant de la taille de la fenˆetre W . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Une DH locale adaptative et non-param´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1 Caract´erisation de la mesure d’une dissimilarit´e locale

. . . . . . . . . . . . . . . . . . . . . . . .

2.4.2 Crit`ere pour le calcul du rayon optimal rmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.3 G´en´eralisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

Carte des Dissimilarit´es Locales

3.1 D´efinition g´en´erale

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1 Algorithme g´en´eral

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.2 Complexit´e du calcul

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Cas de la Distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 Transformation en distance (TeD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Mise en œuvre de la Carte des Dissimilarit´es Locales bas´ee sur la distance de Hausdorff . . . . . . . . . .

3.4.1 Calcul de la distance de Hausdorff globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.2 Calcul de la Carte des Dissimilarit´es Locales a partir du th´eoreme 3.3.1 . . . . . . . . . . . . . . .

vii

49

49

49

49

50

54

56

56

56

56

56

57

59

61

62

62

63

64

65

66

66

66

66

72

72

75

77

78

78

78

78

79

80

82

82

82

viii

Table des mati`eres

3.5 R´esultats qualitatifs

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.1 Lignes et carr´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.2 Lettres « co » et « et » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5.3

Jeu des dix erreurs

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6 Comparaison aux DH modifi´ees

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 G´en´eralisation aux images en niveaux de gris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7.1 G´en´eralisation `a partir de la d´efinition g´en´erale de la Carte des dissimilarit´es locales

. . . . . . .

3.8

3.7.2 G´en´eralisation dans le cas de la distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . .

´Etude sur la fenˆetre glissante W . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.8.1 Utilit´e de l’adaptabilit´e de la fenˆetre W . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.8.2 Forme de la fenˆetre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.9 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Partie III Application `a la classification

0.1 La Carte des Dissimilarit´es Locales au sein d’un processus global de comparaison . . . . . . . . . . . . .

0.1.1 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

0.1.2

Sch´ema synoptique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

Classification d’impressions anciennes

1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Projet ANITA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

83

83

83

84

84

88

88

89

89

89

92

97

97

97

99

99

1.3 Pr´etraitement

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

1.3.1 Acquisition des ´echantillons

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

1.3.2 Binarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

1.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

2

Classification bas´ee sur la Carte des Dissimilarit´es Locales

2.1 Classification : g´en´eralit´es

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

2.1.1 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

2.1.2 Formalisation de la fonction de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

2.2 Diff´erentes approches de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

2.2.1 M´ethodes probabilistes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

2.2.2

k plus proches voisins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

ix

2.2.3 R´eseaux de neurones de type perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

2.2.4

S´eparateurs `a vaste marge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

2.3 Repr´esentation vectorielle de la Carte des Dissimilarit´es Locales . . . . . . . . . . . . . . . . . . . . . . . 113

2.3.1 Histogramme de la Carte des Dissimilarit´es Locales . . . . . . . . . . . . . . . . . . . . . . . . . . 114

2.3.2 Granulom´etrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

2.3.3 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

2.4 Classification directe sur la Carte des Dissimilarit´es Locales

. . . . . . . . . . . . . . . . . . . . . . . . . 117

2.4.1 M´ethodologie d’´evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

2.4.2 Carte des Dissimilarit´es Locales bas´ee sur la distance de Hausdorff (CDLDH ) . . . . . . . . . . . 119

2.4.3 R´esultats en combinant la Carte des Dissimilarit´es Locales avec l’analyse multir´esolution . . . . . 121

2.4.4 Classification en trois groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

2.4.5 Carte de Diff´erence Simple (CDS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

2.4.6 Carte des Dissimilarit´es Locales bas´ee sur la diff´erence simple CDLDif Simple . . . . . . . . . . . . 124

2.4.7 Comparatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

2.4.8 Robustesse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

3

Autres applications

3.1 Classification sur une base de formes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.2 Classification sur une base de visages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.2.1 Description pratique

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.2.2 Analyse

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.3 Mesure globale tirant parti de la Carte des dissimilarit´es Locales dans le cas de la DH . . . . . . . . . . . 136

4

Bilan

Partie IV Conclusion g´en´erale

Annexes

A

Preuves

A.1 Preuve de la proposition 2.3.1 (identit´e) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

A.2 Preuve de la proposition 2.3.2 (majoration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

A.3 Preuve de la proposition 2.3.3 (croissance) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

x

Glossaire

Bibliographie

Table des mati`eres

155

157

Table des figures

1.1 Repr´esentation de l’analyse multir´esolution sur trois niveaux . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Sch´ema de l’analyse pour l’algorithme de Mallat.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Sch´ema de la synth`ese pour l’algorithme de Mallat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Exemple de d´ecomposition d’un signal s avec les ondelettes de Haar sur 5 ´echelles

. . . . . . . . . . . . . . .

1.5 Une image et sa d´ecomposition en ondelettes de Haar 2d.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.6 Sch´ema de l’analyse pour le lifting scheme.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1

Illustration des 4 op´erations morphologiques ´el´ementaires

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Sch´ema de l’analyse des ondelettes de Haar morphologiques en 2d . . . . . . . . . . . . . . . . . . . . . . . .

2.3 D´ecomposition en ondelettes de Haar 2d morphologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Une image et son analyse granulom´etrique par ouverture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 AMR morphologique de l’´erosion d´ecim´ee : les approximations et leurs d´eriv´ees granulom´etriques.

. . . . . .

2.6 AMR morphologique de Haar d´ecim´ee : les approximations et leurs d´eriv´ees granulom´etriques.

. . . . . . . .

2.7 Courbes et d´eriv´ees granulom´etriques pour l’AMR morphologique de la m´ediane d´ecim´ee

. . . . . . . . . . .

2.8

2.9

Image initiale et ses approximations aux ´echelles 1 et 2 par le filtre de Haar morphologique . . . . . . . . . .

Image initiale et ses approximations aux ´echelles 1 et 2 par l’ouverture morphologique . . . . . . . . . . . . .

2.10 Diagramme commutatif concernant la d´ecimation et la compl´ementation illustrant l’´egalit´e (2.39).

. . . . . .

2.11 Image initiale et ses approximations aux ´echelles 1 `a 4 par le filtre de la m´ediane morphologique

. . . . . . .

2.12 AMRM de la m´ediane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.13 AMRM dyadique avec le filtre de la m´ediane sur une image binaire . . . . . . . . . . . . . . . . . . . . . . . .

2.14 AMRM de la m´ediane par l’algorithme `a trous

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1 Deux couples d’images diff´erents donnant les mˆemes images de diff´erence simple

. . . . . . . . . . . . . . . .

1.2

In´egalit´e triangulaire : contre-exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Complexit´e du contour : formes proches mais contours tr`es diff´erents . . . . . . . . . . . . . . . . . . . . . . .

2.1

Illustration de la notion de dissimilarit´e locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Deux exemples pour la d´efinition am´elior´ee.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

2.4

Illustration des sauts de valeurs pour la d´efinition modifi´ee lors du d´eplacement de la fenˆetre W . . . . . . . .

Illustration des sauts de valeurs pour la d´efinition modifi´ee lors de l’agrandissement de la fenˆetre W . . . . .

3.1 Une image binaire et ses trois T eD faites avec les trois distances classiques : L1, L2, L∞ . . . . . . . . . . . .

3.2 Trois formes simples et leurs CDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

13

13

14

18

21

25

30

31

32

34

35

36

37

37

38

39

40

41

42

52

53

55

62

63

64

65

81

83

xi

xii

Table des figures

3.3 Les lettres CO et ET et leur CDL illustrant leurs dissimilarit´es locales. . . . . . . . . . . . . . . . . . . . . . .

3.4 Le jeu des dix erreurs

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5 Contre-exemple pour les mesures globales `a partir de lignes . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6 Contre-exemple pour les mesures globales `a partir de cercles . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.7 CDL entre l’image d’un visage et les images ´erod´ees

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.8 Comparaison entre la CDL et les Cartes des dissimilarit´es `a taille de fenˆetre fixe.

. . . . . . . . . . . . . . . .

3.9 Deux images binaires et leur CDL avec des fenˆetres de mesure locale asym´etriques

. . . . . . . . . . . . . . .

0.10 Sch´ema du processus global utilisant l’AMR, la CDL et le module de d´ecision . . . . . . . . . . . . . . . . . .

84

85

86

87

90

91

92

98

1.1 Exemple d’acquisition initiale pour deux impressions anciennes . . . . . . . . . . . . . . . . . . . . . . . . . . 100

1.2 Deux illustrations diff´erentes provenant du mˆeme tampon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

2.1 Taux de reconnaissance de la classification des histogrammes bas´ee sur les SVM . . . . . . . . . . . . . . . . . 115

2.2 Deux CDL diff´erentes ayant le mˆeme histogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

2.3 R´esultats de la classification des courbes granulom´etriques bas´ee sur les SVM . . . . . . . . . . . . . . . . . . 118

2.4 CDLDH : taux de classification en fonction de la taille des ´echantillons d’apprentissage

2.5 Exemple d’images de d´etails recompos´es avec une approximation nulle . . . . . . . . . . . . . . . . . . . . . . 123

. . . . . . . . . . . . 120

2.6 CDLDH : Taux de classification de la CDLDH pour les 3 classes en fonction du param`etre C du SVM . . . . 124

2.7 Repr´esentation de la CDLdif Simple pour diff´erentes valeurs du param`etre d’arrˆet . . . . . . . . . . . . . . . . 125

2.8 CDLdif Simple : taux de classification en fonction du param`etre d’arrˆet . . . . . . . . . . . . . . . . . . . . . . 126

2.9 DH partielle : efficacit´e de la classification en fonction du param`etre p . . . . . . . . . . . . . . . . . . . . . . 127

2.10 Comparaison de la CDLDH et de la CDLdif Simple sur une exemple

2.11 CDLDH : robustesse aux tˆaches et aux effacements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

. . . . . . . . . . . . . . . . . . . . . . . 129

3.1 Quelques exemples de formes de la base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.2 Exemples de visages de la base ATT, de leur contours et de leurs CDL . . . . . . . . . . . . . . . . . . . . . . 135

3.3

Illustration pour la distance globale DH Filtr´ee (DHF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Liste des tableaux

1.1 Comparaison des m´ethodes de binarisation, partie 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

1.2 Comparaison des m´ethodes de binarisation, partie 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

2.1 Histogramme de la CDL : taux de reconnaissance `a la r´esolution 128 × 128.

. . . . . . . . . . . . . . . . . . . 114

2.2 CDLDH : taux de reconnaissance en fonction C et du type de noyau.

2.3 CDLDH : taux de reconnaissance en fonction de l’´echelle de l’AMR . . . . . . . . . . . . . . . . . . . . . . . 121

2.4 Exemple d’approximations par l’AMR de la m´ediane morphologique et leur CDL aux diff´erentes r´esolutions . 121

. . . . . . . . . . . . . . . . . . . . . . 120

2.4

suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

2.4 Commentaires sur la conservation des structures par L’AMR de la m´ediane morphologique

. . . . . . . . . . 122

2.5 CDLDH : taux de reconnaissance pour les d´etails recompos´es de taille 128 × 128 . . . . . . . . . . . . . . . . 123

2.6 CDLDH : r´esultat du test de la classification en trois classes `a la r´esolution 128 × 128. . . . . . . . . . . . . . 124

2.7 Comparaison des m´ethodes avec celles bas´ees sur la CDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

2.8 CDLDH : r´esultat du test circulaire `a la r´esolution 128 × 128. . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

2.9 R´ecapitulatif des r´esultats pour toutes les m´ethodes de comparaison test´ees. . . . . . . . . . . . . . . . . . . . 131

3.1 R´esultat de la m´ethode sur la bases de formes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.2 R´esultat de la m´ethode sur la bases de visages

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

xiii

xiv

Liste des tableaux

Introduction g´en´erale

1 Contexte

L’essor du traitement de l’image et son investissement de secteurs aussi diff´erents que la vie priv´ee ou la m´edecine ont

donn´e naissance `a de nombreuses bases de donn´ees et en particulier d’images.

Le support informatique des images permet notamment de les comparer. Cela peut ˆetre utile `a plusieurs titres :

– pour visualiser les diff´erences entre les images, et les quantifier automatiquement ;

– pour retrouver des images dans une base d’images. En effet, ces derni`eres sont souvent trop volumineuses pour ˆetre

exploit´ees directement par l’homme. Elles n´ecessitent alors le d´eveloppement de m´ethodes d’exploitation automatiques

comme la recherche d’images `a partir d’une requˆete. Dans ce cas particulier de la recherche d’images, les m´eta-donn´ees

(texte descriptif, ...) sont parfois absentes ou inadapt´ees. Il est alors n´ecessaire de se baser sur le contenu des images

pour effectuer la recherche. Plusieurs m´ethodes existent, les unes bas´ees sur la comparaison de descripteurs des images

et les autres sur la comparaison directe des images.

Ainsi, la comparaison d’images est un point important dans plusieurs domaines. Les images binaires pr´esentent dans ce cadre

des difficult´es sp´ecifiques. La pauvret´e de leurs attributs, et parfois complexit´e des images font que si certains outils ont ´et´e

d´evelopp´es, par exemple dans le cas de formes simples, leur description reste difficile et leur comparaison aussi. Et pourtant,

les images binaires sont pr´esentes dans de nombreux processus. Elles peuvent provenir de capteurs binaires, d’une extraction

de contours, d’une binarisation... Leur comparaison peut alors ˆetre utile. C’est dans le cadre de la comparaison des images

binaires que s’inscrit cette th`ese.

2 Probl´ematique

Comparer des images binaires souleve plusieurs problemes. Le premier est le choix de la r´esolution de comparaison. En

effet, pour des applications qui peuvent ˆetre coˆuteuses en temps de calcul, il est int´eressant de ne comparer que ce qui est

n´ecessaire. Ce probleme n’est pas sp´ecifique aux images binaires mais donne des contraintes particulieres qui demandent une

´etude pour la multir´esolution. Le deuxieme probleme est la maniere de comparer les images a proprement parler. Enfin le

troisieme porte sur l’exploitation de cette comparaison. Ces trois problemes soulev´es par la comparaison d’images binaires

ont ´et´e abord´es dans cette th`ese.

3 Contribution de la th`ese

Le d´eveloppement d’une m´ethode de comparaison d’images binaires constitue la contribution majeure de cette th`ese.

1

2

Introduction g´en´erale

3.1 M´ethode de comparaison des images binaires

La solution propos´ee permet une comparaison directe des images. Elle est bas´ee sur la mesure locale des dissimilarit´es

entre les deux images. L’int´erˆet de cette mesure est double : d’une part, elle s’adapte automatiquement `a la taille de la

dissimilarit´e qu’elle doit ´evaluer localement, et d’autre part, le regroupement de toutes les mesures locales entre deux images

donne une carte des dissimilarit´es locales (abr´eg´ee en CDL) qui comporte l’ensemble des mesures et leur distribution spatiale.

Le principe de la carte des dissimilarit´es locales est g´en´eral dans le sens o`u une mesure de dissimilarit´e locale quelconque

peut ˆetre appliqu´ee pour peu qu’elle v´erifie quelques hypoth`eses (croissance, majoration). Cela permet une souplesse dans sa

mise en œuvre. Par ailleurs, dans le cas o`u cette mesure locale est d´eriv´ee de la distance de Hausdorff, la formule de calcul

est simple et rapide et rend compte des dissimilarit´es avec une bonne fid´elit´e.

Le fait que la carte des dissimilarit´es locales contienne l’information sur les valeurs des mesures de dissimilarit´e et leur

r´epartition spatiale est particulierement int´eressant car cela permet de distinguer des types de dissimilarit´es a partir de la

mani`ere dont sont r´eparties les valeurs dans la carte (si les hautes valeurs sont regroup´ees ou ´eparpill´ees par exemple). Cela

est de plus novateur dans le sens ou il n’existe pas, a la connaissance de l’auteur, de repr´esentation concernant la distribution

spatiale des dissimilarit´es dans la litt´erature. Une exploitation de cette information contenue dans la carte des dissimilarit´es

locales concerne la classification des images binaires.

3.2 Exploitation pour la classification

La carte des dissimilarit´es locales est une repr´esentation d’une mesure des dissimilarit´es locales entre deux images. Dans la

classification, le but est de pouvoir classer les images par classes de similarit´e. Comme une carte des dissimilarit´es locales est

associ´ee a un couple d’images, cela revient a classer les cartes des dissimilarit´es locales en deux classes : celles comparant des

images similaires et celles comparant des images dissimilaires. Or la carte des dissimilarit´es locales est en deux dimensions.

Son exploitation pour la classification n’est donc pas imm´ediate. La th`ese se propose d’exploiter les donn´ees de la carte des

dissimilarit´es locales par un S´eparateur a Vaste Marge (SVM). En effet, les S´eparateurs a Vaste Marge supportent assez bien

les donn´ees de grande dimension, ce qui permet de leur soumettre int´egralement la CDL pour effectuer la classification.

Cependant toute l’information contenue dans les images peut ne pas ˆetre pertinente pour la comparaison. Le choix de

cette information s’effectue `a l’aide d’une analyse multir´esolution (AMR).

3.3 Choix de l’information `a comparer

Comme toute l’information contenue dans les images n’est pas pertinente, et que se posent aussi des questions ´evidentes

relatives au temps de calcul, il est int´eressant de d´ecomposer de mani`ere contrˆol´ee l’image afin de choisir la partie la mieux

adapt´ee a la comparaison. Le souhait de contrˆoler la d´ecomposition nous a conduit a nous placer dans le cadre de l’analyse

multir´esolution . Cependant le cas particulier des images binaires amene a sortir du cadre de l’analyse multir´esolution classique

pour utiliser celui des ondelettes de seconde g´en´eration et consid´erer les analyse multir´esolution non-lin´eaires bas´ees sur un

op´erateur morphologique. L’´etude dans ce cas est d´elicate car il n’y a pas d’´equivalent (non-lin´eaire) de l’analyse de Fourier

qui fournit au cas lin´eaire un puissant outil de caract´erisation. De ce fait, la caract´erisation des filtres et le d´eveloppement

de nouveaux filtres ne sont pas bien maˆıtris´es. L’apport de la th`ese sur ce point est d’avoir fait le point sur ce qui a ´et´e

d´ej`a propos´e, d’avoir test´e plusieurs op´erateurs (Haar, ouverture, m´ediane) pour la multir´esolution, d’avoir mis en œuvre

diff´erents algorithmes dans ce cadre et d’avoir ´etudi´e des outils de caract´erisation ainsi que la possibilit´e de nouveaux filtres.

4. Organisation de la th`ese

4 Organisation de la th`ese

La th`ese est organis´ee en trois parties.

3

Premiere partie La premiere partie porte sur l’analyse multir´esolution qui permet de choisir au mieux l’information `a

comparer dans les images. Le cadre g´en´eral de l’analyse multir´esolution classique y est pr´esent´e. Il permet d’introduire celui des

ondelettes de deuxi`eme g´en´eration. Un point est alors fait sur la morphologie math´ematique. Enfin l’analyse multir´esolution

morphologique est pr´esent´ee en utilisant les filtres morphologiques dans le cadre des ondelettes de deuxi`eme g´en´eration. Cela

conduit `a choisir l’analyse multir´esolution morphologique utilisant le filtre de la m´ediane.

Deuxieme partie La deuxieme partie pr´esente un panorama sur les m´ethodes de comparaison d’images puis situe notre

propre d´emarche. En se basant sur un cas concret (la distance de Hausdorff), le principe de la mesure locale est expos´e et

ses propri´et´es d´emontr´ees. Cela permet de d´efinir un crit`ere de choix pour la taille de la fenˆetre dans laquelle est faite la

mesure locale. La mesure des dissimilarit´es locale en d´ecoule dans le cas g´en´eral et dans le cas de la distance de Hausdorff.

Des exemples sont donn´es pour illustrer les propri´et´es de la carte des dissimilarit´es locales.

Troisieme partie Cette dernie...