Schmitt, Michel (1989) Des Algorithmes morphologiques à l'intelligence artificielle. PhD thesis Morphologie mathématique, CMM- Centre de morphologie mathématique, ENSMP p.231.

Full text available as: - morpho.ps ( 9461 Kb )

Licence: Copyright

Abstract

The aim of this thesis is to examine some aspects of mathematical morphology from special viewpoints. We first show how the notion of convergence of closed sets and that of random closed sets can be used in computational geometry. Then we describe a new technique which allows us to write efficient morphological algorithms for binary image processing by means of boundary coding with chains and loops. We describe among others the following algorithms: erosion, dilation, distance function (both in the Euclidean and the geodesic case), propagation function, (in the hexagonal and dodecagonal metrics), labeling, particle reconstruction, etc. We also tackle morphological measures such as diametrical variation, Ferret's diameter, perimeter, Euler's number, etc. The use of these transformations is then illustrated by the complete resolution of one special problem in material sciences, where we discuss the respective quality of about ten different solutions. Finally, the attempt to formalize the use of the morphological transformations led to an automatic programming system in mathematical morphology.

Table of content

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

Statistiques de consultation

Repository Staff Only: edit this item