Parallelization of Morphological Operators Based on Graphs

Autor: Youkana, Imane
Přispěvatelé: Youkana, Imane
Jazyk: angličtina
Rok vydání: 2017
Předmět:
Popis: Mathematical morphology is one of the most powerful frameworks which provides a set of filtering and segmenting tools that are very useful in applications to image analysis. The first field of applications of mathematical morphology was binary image by Matheron and Serra in 1964 [54]. The theory of mathematical morphology is based on that the underlying image space is a complete lattice [28] allowing to consider the processing of a very broad class of data with mathematical morphology operators. On the other hand, considering digital objects carrying structural information, mathematical morphology has been developed on graphs, simplicial complexes, and on hypergraphs. This thesis reportis focused on the framework of mathematical morphology on graphs spaces presented in [14]. This framework considers operators whose input and output are both graphs (sets of vertices as well as sets of edges). The basic operators go from one kind of sets to another one. They can be combined in order to obtain operators acting on the subset of edges, on the subset of vertices, and on the subgraphs of a given graph.The main objective is to provide efficient computation and implementation of these morphological operators on graphs. To this end, we study the (unweighted) graph-based mathematical morphology operators. These operators depend on a size parameter that specifies the number of iterations of elementary dilations/erosions. Thus, the associated running times of these iterated operators increase with the size parameter, the algorithm running in O(λ.n) time, where n is the size of the underlying graph and λ is the size parameter. In our work, we are focused in distance maps that allow us to recover (by thresholding) all considered dilations and erosions, hence all the operators proposed in [14]. In the first part, we propose three new distance maps on graphs called edge-edge, edge-vertex, and vertex-edge distance maps. Furthermore, based on new notion of path which considers both the numbers of edges and of vertices along the path, we present our vertex-vertex distance map. We show that these distance maps lead to original characterization of all operators presented in [14]. Then, a linear-time sequential algorithms for distance maps in unweighted graphs, hence the operators of dilations/erosions on graphs is proposed. In fact, any dilation, erosion, opening and closing on graphs can be obtained with a single iteration by thresholding these distance maps. Therefore, these operators can be computed in linear time with respect to the size of the graph, with a single iteration and without any dependence to this size parameter.In the second part, we investigate a parallelization strategy on multi-core architec-ture leading to efficiently compute our proposed distance maps, hence the morphological operators on graphs. The proposed strategy consists of building iteratively the succes-sive level-sets of the distance maps, each level set being traversed in parallel. Indeed, to state the time complexity of our parallel strategy we make assumptions about the graph and the sets under consideration. Under these assumptions, our parallel algorithms run in O(n/p + K log 2 p) where n, p, and K are the size of the graph, the number of available processors, and the number of distinct level-sets of the distance map, respectively. In the third part, a description of the 2D image and 3-dimensional meshes datasets used for experimental evaluations is provided. Then, we assess the regularity of the proposed assumptions on these experimental datasets. And, we perform an analysis of the results obtained by applying the implementations of the proposed sequential and parallel algorithms on the target architectures. This evaluation shows a significant improvement of the processing time over the previously available implementations.
La morphologie mathématique est un cadre puissant qui fournit un ensemble d’outils de filtrage et de segmentation très utiles dans les applications d’analyse d’image. Initialement le premier champ d’applications de la morphologie mathématique était sur les images binaires et proposé par Matheron et Serra en 1964 [54]. En outre la théorie de la morphologie mathématique repose sur le fait que l’espace de l’image est un treillis complet [28] ce qui permet d’envisager le traitement d’une très large classe de données avec les opérateurs de la morphologie mathématique. En prenant en considération les objets numériques portant des informations 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èse se focalise sur le cadre de la morphologie mathématique basée sur les graphes présenté dans [14]. Dans ce cadre les ensembles d’entrées et sorties des opérateurs considères sont des graphes (ensembles de sommets ainsi que des ensembles d’arêtes) et les opérateurs de base peuvent aller d’un type d’ensembles vers l’autre. Ils peuvent être combinés afin d’obtenir des 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 efficaces pour ces opérateurs morphologiques en se basant sur les graphes non pondérés. En effet, ces opérateurs dépendent d’un paramètre de taille qui spécifie le nombre d’itérations de dilatations et d’érosions élémentaires. Ainsi, le temps d’exécution associé à ces opérateurs ité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/ érosions considérées et par conséquent tous les opérateurs propos ´es dans [14]. En premier lieu nous avons proposés trois nouvelles cartes de distance basées sur les graphes. Il s’agit des cartes de distance arête-sommet, sommet-arête et arête - arête. En plus, basé sur une nouvelle notion de chemin qui considère à la fois le nombre d’arêtes et de 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 de toutes les dilatations et érosions présentées dans [14]. Ensuite, des algorithmes séquentiels en 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 avec une seule itération par le seuillage de ces cartes de distance. Ainsi, ces opérateurs peuvent être calculés en temps linéaire par rapport à la taille du graphe avec une seule itération et sans aucune dépendance avec le paramètre de taille. Afin de calculer efficacement les cartes de distance proposées et les opérateurs morphologiques basés sur les graphes, nous avons développé une stratégie parallèle sur une architecture multi-cœurs à mémoire partagée qui consiste à construire d’une manière itérative les niveaux successifs des cartes de distance avec un parcours en parallèle de chaque niveau. Afin d’estimer la complexité de notre stratégie parallèle, nous proposons et démontrons des hypothè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 + K log2p) où n, p, et K sont respectivement la taille du graphe, le nombre de processeurs disponibles et le nombre de niveaux distincts de la carte de distance, respectivement. Dans l’évaluation expérimentale, nous avons fourni une description des bases de données utilisées ; Il s’agit de deux bases d’images 2D et une base des 3D maillages triangulaires texturées. Nous avons évalué la régularité des hypothèses proposées sur les bases de données considérées pour effectuer ensuite une analyse des résultats obtenus par les implémentations séquentiels et parallèle des algorithmes proposés sur les architectures cibles. Cette évaluation montre une amélioration significative en termes de temps d’exécution par rapport aux implémentations disponibles auparavant.
Databáze: OpenAIRE
Externí odkaz: