Thèse
Auteur :
Schmitt Michel

Date de soutenance :
01 février 1989

Directeur(s) de thèse :
Matheron Georges



École :

MINES ParisTech
Intitulé de la thèse : Des Algorithmes morphologiques à l'intelligence artificielle


Résumé : Cette thèse se propose d'examiner sous un angle particulier quelques aspects de la morphologie mathématique. Nous montrons d'abord comment la notion de convergence d'ensembles fermés et celle d'ensemble aléatoire fermé peuvent être employées en géométrie algorithmique. Nous exposons ensuite une nouvelle technique permettant l'écriture d'algorithmes morphologiques efficace en imagerie binaire au moyen d'un codage de contours sous forme de chaînes et lacets. Les algorithmes concernés sont entre autres l'érosion, la dilatation, la fonction distance, tant dans le cas euclidien que géodésique, la fonction de propagation, en métrique hexagonale et dodécagonale, le labeling, la reconstruction. . . Nous abordons aussi les mesures morphologiques telles que variation diamétrale, diamètre de Ferret, périmètre, nombre d'Euler. . . L'emploi des transformations est alors illustré par la résolution complète d'un problème particulier en sciences des matériaux où nous discutons les qualités respectives d'une dizaine de solutions différentes. Enfin, un essai de formalisation de l'emploi des transformations morphologiques a abouti à l'écriture d'un système de programmation automatique.I Morphologie mathématique et géométrie combinatoire 5

1 La topologie en tout ou rien 9

1.1 Définition d'une topologie sur l'ensemble des fermés de IR n 9

1.2 Relations entre la topologie en tout ou rien et celle déduite de la distance de Hausdorff 11

1.3 Application: relations entre le squelette et la triangulation de Delaunay12

1.3.1 Convergence des centres des sphères de Delaunay vers le squelette 15

1.3.2 Vitesse de convergence 19

1.3.3 Forme du squelette 20

2 Ensembles fermés aléatoires 23

2.1 Définition d'une ?-algèbre et le théorème de Choquet 23

2.2 Relations avec la notion de loi spatiale 24

2.3 Application: étude des performances d'algorithmes de bucketisation dans le cas moyen 26

2.3.1 Le schéma booléen 26

2.3.2 Exemples de calculs 27

2.4 Conclusion 29

II Technique des lacets I: Algorithmes élémentaires 31

3 Hypothèses et notations 37

3.1 Définition de la trame hexagonale 37

3.2 Définition des directions 38

3.3 Définition des chaînes et lacets 39

3.4 Notion de transformation géodésique 40

4 Algorithme de suivi de contours 43

4.1 Cas d'une particule X simplement connexe 43

4.1.1 L'algorithme 44

4.1.2 Correction 46

4.1.3 Complexité 50

4.1.4 Accélération 51

4.1.5 Propriétés du lacet résultat 51

4.2 Cas d'un ensemble X ? H quelconque fini 53

4.2.1 Description de X par une suite d'ensembles simplement connexes 53

4.2.2 Détection de l'ensemble des contours d'un ensemble digital fini 56

4.2.3 Algorithme pratique 57

4.2.4 Exemple d'illustration 58

4.3 Digressions sur le théorème de Jordan digital 58

4.3.1 Rappel du théorème de Jordan dans le plan IR 2 60

4.3.2 La propriété de Jordan digitale 60

4.3.3 Quelques lemmes sur les triangulations 61

4.3.4 Le théorème central 63

4.3.5 Réciproque 66

5 Opérations morphologiques sur les chaînes et lacets 71

5.1 Dilatation des lacets 71

5.1.1 Dilatation d'un lacet par l'hexagone élémentaire 71

5.1.2 Propriétés du lacet dilaté 74

5.1.3 Dilatation d'un ensemble de lacets 78

5.2 Transformation des lacets en chaînes 79

5.2.1 Nouvelle représentation et règles de manipulation 79

5.2.2 Conservation de la représentation par dilatation 81

5.2.3 Optimalité de la représentation 82

5.2.4 Transformations géodésiques 82

5.3 Applications 83

5.3.1 Reconstruction 84

5.3.2 Etiquetage 84

5.3.3 Fonction distance hexagonale 85

5.3.4 Fonction distance hexagonale géodésique 86

5.3.5 Zones d'influence 87

5.4 Autres éléments structurants 88

5.4.1 Hexagone conjugué et dodécagone 88

5.4.2 Segments 91

5.5 Mesures 91

5.5.1 Variation diamétrale et périmètre 91

5.5.2 Diamètre de Ferre 93

5.5.3 Nombre de particules et nombre d'Euler 94

III Technique des lacets

II: La fonction de propagation 97

6 La fonction de propagation 99

6.1 Introduction 99

6.2 Quelques lemmes sur les géodésiques 102

6.2.1 La notion d'arc et de chemin géodésiques 103

6.2.2 La distance géodésique 104

6.2.3 Existence et unicité des géodésiques 105

6.2.4 Encore quelques lemmes 105

6.3 Géodésiques dans l'espace (IR 2,?) 107

6.3.1 Définition d'une métrique associée à un compact K 108

6.3.2 Arcs rectifiables au sens de ? 110

6.3.3 Géodésiques dans le plan 112

6.3.4 Caractérisation des géodésiques de (X,?) 113

6.3.4.1 Cas d'une métrique non dégénérée 113

6.3.4.2 Cas d'une métrique dégénérée 115

6.3.5 Approximation d'une métrique dégénérée 117

6.4 Structure des boules géodésiques 118

6.5 Extrémités libres des géodésiques maximales 124

6.6 Plongement d'un ensemble digital dans IR 2 130

6.6.1 Cas de la distance hexagonale 130

6.6.2 Cas de la distance dodécagonale 131

6.7 Algorithmes de calcul 133

6.7.1 Cas de la métrique hexagonale 133

6.7.2 Cas de la métrique dodécagonale 133

6.8 Et la simple connexité? 134

6.9 Quelques propriétés mathématiques 134

IV Variations lamellaires ou comment résoudre un problème d'analyse d'images 139

7 Variations lamellaires 141

7.1 Introduction 141

7.1.1 Segmentation et morphologie mathématique 141

7.1.2 Un problème d'analyse d'images: détection des lignes de défaut dans un eutectique lamellaire 142

7.1.3 Comment apprécier la qualité d'un programme? 146

7.1.4 Quelques options 148

7.2 Etude de l'algorithme existant 150

7.2.1 La notion d'extrémités 150

7.2.2 Les zones de fracture 156

7.2.3 Passage des zones de fracture aux lignes de fracture 158

7.3 Algorithmes pour les lignes de défaut 159

7.3.1 Recherche des points de forte courbure 159

7.3.1.1 Les solutions morphologiques 159

7.3.1.2 Une autre solution 160

7.4 Procédures de connexion de points a priori 162

7.4.1 Connexion selon la distance 163

7.4.2 Graphe de Delaunay,Gabriel 164

7.4.3 Encore une autre procédure de connexion de points 166

7.5 Coupure des lames 171

7.5.1 Dilatation par des losanges 172

7.5.2 Erodés ultimes géodésiques 175

7.6 Recherche des lignes de défaut après coupure des lames 176

7.6.1 Un critère de direction globale 178

7.6.2 Critères de longueur 180

7.6.3 L'antisquelette 182

7.6.4 Retour à l'image originale 185

7.7 Recherche de chemins sur des fonctions particulières 185

7.7.1 Remontée vers l'amont 187

7.7.2 Les courbes de niveau de la fonction de propagation 188

7.8 Encore une solution 192

7.9 Quel algorithme? 195

7.10 Définitions et algorithmes utilisés 196

V Morphologie mathématique et intelligence artificielle 199

8 Morphologie mathématique et intelligence artificielle 201

8.1 Introduction 201

8.1.1 Reconnaissance des formes 201

8.1.2 Intelligence artificielle 202

8.1.2.1 Systèmes à base de règles 202

8.1.2.2 Langages objets 203

8.2 Les primitives morphologiques 203

8.2.1 Place de la morphologie mathématique en analyse d'images 203

8.2.2 La boîte à outil des primitives morphologiques 204

8.2.2.1 R-hmaxima et R-hminima 206

8.2.2.2 Résidus par ouverture: le chapeau haut-de-forme et le rolling ball 206

8.3 Un système de programmation automatique 208

8.3.1 Spécification de problèmes - Langage morphologique 210

8.3.2 Les briques de base du programme synthétisé 212

8.3.3 La base de règles 213

8.3.4 Les mécanismes d'inférence 213

8.3.4.1 Sélection de la règle à exécuter 213

8.3.4.2 Détection des échecs et back-track 214

8.3.5 Résultats-Evaluation 214

8.3.5.1 Exemple 214

8.3.5.2 Structure des programmes synthétisés 217

8.3.5.3 Classes d'objets et primitives morphologiques 217

8.3.6 Limites et perspectives 218

8.4 Conclusion: quelles connaissances avons-nous introduites? 218

© Mines de Paris 2018 - Réalisé par Winch Communication