Parallelization of Morphological Operators Based on Graphs

Résumé

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 report is 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.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 3

Téléchargements : 0