| Titre : | Parallélisation of Morphological Operators Based on Graphs |
| Auteurs : | Imane YOUKANA, Auteur ; Rachida Saouli, Directeur de thèse |
| Type de document : | Mémoire magistere |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2017 |
| ISBN/ISSN/EAN : | TINF/112 |
| Format : | 1 vol. (94 p.) / ill. / 29 cm |
| Langues: | Anglais |
| Résumé : |
La morphologie mathématique est un cadre puissant qui fournit un ensemble d’outils defiltrage et de segmentation très utiles dans les applications d’analyse d’image. Initialementle premier champ d’applications de la morphologie mathématique était sur les images binaireset proposé par Matheron et Serra en 1964 [54]. En outre la théorie de la morphologiemathématique repose sur le fait que l’espace de l’image est un treillis complet [28] ce quipermet d’envisager le traitement d’une très large classe de données avec les opérateurs de lamorphologie mathématique. En prenant en considération les objets numériques portant desinformations structurelles, la morphologie mathématique a ´étédéveloppée sur des graphes,des complexes simpliciaux, et sur les hypergraphes. Ainsi le travail proposé dans cette thèsese focalise sur le cadre de la morphologie mathématiquebasée sur les graphes présenté dans[14]. Dans ce cadre les ensembles d’entrées et sorties des opérateursconsidères sont desgraphes (ensembles de sommets ainsi que des ensembles d’arêtes) et les opérateurs de basepeuvent aller d’un type d’ensembles vers l’autre. Ils peuvent êtrecombinés afin d’obtenirdes opérateurs agissant sur le sous ensemble d’arêtes, sur le sous-ensemble des sommets,et sur les sous-graphes d’un graphe donné.L’objectif principal dans cette thèse est de fournir un calcul et une implémentation efficacespour ces opérateurs morphologiques en se basant sur les graphes non pondérés. En effet,ces opérateursdépendent d’un paramètre de taille qui spécifie le nombre d’itérations dedilatations et d’érosionsélémentaires. Ainsi, le temps d’exécutionassociéà ces opérateursitératifs augmente avec le paramètre de taille et la complexité est de l’ordre de O(λ.n),où n est la taille du graphe et λ le paramètre de taille. Dans notre travail, nous sommes particulièrement intéressés par les cartes de distances qui nous ont permis (par seuillage)de caractériser et d’effectuer toutes les dilatations/ érosionsconsidérées et par conséquenttous les opérateurspropos ´es dans [14].En premier lieu nous avons proposés trois nouvelles cartes de distance basées sur lesgraphes. Il s’agit des cartes de distance arête-sommet, sommet-arête et arête - arête. Enplus, basé sur une nouvelle notion de chemin qui considèreà la fois le nombre d’arêtes etde sommets sur le chemin, nous présentons une carte de distance sommet-sommet. Nous montrons que ces nouvelles cartes de distance mènent à des caractérisations originales detoutes les dilatations et érosions présentées dans [14]. Ensuite, des algorithmes séquentielsen temps linéaire ont été proposés afin de calculer ces nouvelles cartes de distance dans les graphes et par conséquent les opérateurs de dilatations/érosions basés sur les graphes.Toute dilatation, érosion, ouverture et fermeture sur les graphes peuvent être obtenues avecune seule itération par le seuillage de ces cartes de distance. Ainsi, ces opérateurs peuventêtrecalculés en temps linéaire par rapport à la taille du graphe avec une seule itération etsans aucune dépendance avec le paramètre de taille.Afin de calculer efficacement les cartes de distance proposées et les opérateurs morphologiquesbasés sur les graphes, nous avons développé une stratégieparallèle sur une architecturemulti-cœurs à mémoire partagée qui consiste à construire d’une manièreitérativeles niveaux successifs des cartes de distance avec un parcours en parallèle de chaque niveau.Afin d’estimer la complexité de notre stratégieparallèle, nous proposons et démontrons deshypothèses sur le graphe et les ensembles considérés. Selon ces hypothèses, la complexitéde nos algorithmes parallèles est O(n/p + Klog2p) où n, p, et K sont respectivement lataille du graphe, le nombre de processeurs disponibles et le nombre de niveaux distincts dela carte de distance, respectivement.Dans l’évaluation expérimentale, nous avons fourni une description des bases de donnéesutilisées ; Il s’agit de deux bases d’images 2D et une base des 3D maillages triangulairestexturées. Nous avons évalué la régularité des hypothèsesproposées sur les basesde donnéesconsidérées pour effectuer ensuite une analyse des résultats obtenus par lesimplémentations séquentiels et parallèle des algorithmes proposés sur les architecturescibles. Cette évaluation montre une amélioration significative en termes de temps d’exécutionpar rapport aux implémentations disponibles auparavant. |
| Sommaire : |
1 General introduction 1 1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 State of the Art 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Digital Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 3-Dimensional Triangular Meshs . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Mathematical Morphology . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.1 Complete Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.2 Fundamental Operators of Mathematical Morphology . . . . . . . 11 2.4.2.1 Dilation and erosion . . . . . . . . . . . . . . . . . . . . . 11 2.4.3 Morphological filtering . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.3.1 Opening and Closing . . . . . . . . . . . . . . . . . . . . . 14 2.4.3.2 Granulometries . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.3.3 Alternative Sequential Filters . . . . . . . . . . . . . . . . 15 2.5 Graph-based mathematical morphology framework . . . . . . . . . . . . . 15 2.5.1 Basic theoretical concepts of graphs . . . . . . . . . . . . . . . . . . 16 2.5.2 Mathematical Morphology operators on graphs . . . . . . . . . . . 19 2.5.2.1 Lattice of graphs . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.2.2 Elementary morphological operators on graphs . . . . . . 21 2.5.2.3 Morphological filters on graphs . . . . . . . . . . . . . . . 23 2.5.3 Problem statement of iterated dilations and erosions on graphs . . . 25 2.6 Distance Map on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6.1 Shortest Paths Problem . . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 Introduction to Parallel Computing . . . . . . . . . . . . . . . . . . . . . . 31 2.7.1 Distributed Memory Machines . . . . . . . . . . . . . . . . . . . . . 31 2.7.2 Shared Memory Architectures . . . . . . . . . . . . . . . . . . . . . 32 2.7.3 Performance Models of Parallel Computing Systems . . . . . . . . . 33 2.7.3.1 Execution Time . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7.3.2 Speedup and efficiency . . . . . . . . . . . . . . . . . . . . 34 2.8 Overview of parallel implementation for distance map . . . . . . . . . . . . 34 2.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 Distance maps for Iterated morphological operators on graphs 37 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Proposed distance maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2.1 Edge-edge distance maps on graphs . . . . . . . . . . . . . . . . . . 38 3.2.2 Vertex-edge distance maps on graphs . . . . . . . . . . . . . . . . . 39 3.2.3 Edge-vertex distance maps on graphs . . . . . . . . . . . . . . . . . 41 3.2.4 Vertex-Vertex Distance map on graphs . . . . . . . . . . . . . . . . 42 3.3 Iterated Morphological operators based on distance maps . . . . . . . . . . 44 3.3.1 Edge-edge Dilation and Erosion . . . . . . . . . . . . . . . . . . . . 45 3.3.2 Vertex-edge Dilation and erosion . . . . . . . . . . . . . . . . . . . 46 3.3.3 Edge-vertex Dilation and erosion . . . . . . . . . . . . . . . . . . . 48 3.3.4 Vertex-vertex Dilation and erosion . . . . . . . . . . . . . . . . . . 50 3.4 Proposed sequential algorithms for morphological operators on graphs . . . 51 3.4.1 Vertex-edge and Vertex-vertex distance map algorithm . . . . . . . 53 3.4.1.1 The correctness of Vertex-edge and Vertex-vertex distance map algorithm . . . . . . . . . . . 54 3.4.1.2 Complexity analysis of Vertex-edge and Vertex-vertex distance map algorithm . . . . . . . . 54 3.4.2 Edge-edge and Edge-vertex distance map algorithm . . . . . . . . . 55 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4 Parallel strategy for distance maps on graphs 57 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Proposed parallel strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.1 Description of parallel algorithms . . . . . . . . . . . . . . . . . . . 58 4.2.2 Parallel partition and disjoint union algorithms . . . . . . . . . . . 59 4.2.3 Example of step illustration of parallel algorithm . . . . . . . . . . 62 4.3 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5 Evaluation and Experimental results of parallel implementation of Distance maps on graph on shared memory architectures 70 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 Target Platform and Multithreaded Implementation . . . . . . . . . . . . . 71 5.3 Datasets description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.3.1 2D image datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.3.2 3D triangular meshes dataset . . . . . . . . . . . . . . . . . . . . . 73 5.4 Experimental-assessment dataset and regularity-assumption assessment . . 74 5.4.1 Case of 2D image datasets . . . . . . . . . . . . . . . . . . . . . . . 76 5.4.2 Case of textured mesh dataset . . . . . . . . . . . . . . . . . . . . . 76 5.5 Performance evaluation and experimental results . . . . . . . . . . . . . . . 77 5.5.1 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 77 5.5.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6 General Conclusions and Perspectives 86 6.1 Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Bibliography 90 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/3441 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/112 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
