Skip to Main content Skip to Navigation

Parallélisation de la ligne de partage des eaux dans le cadre des graphes à arêtes valuées sur architecture multi-cœurs

Abstract : Our work is a contribution of the parallelization of the Watershed Transform in particular the Watershed cuts which are a notion of watershed introduced in the framework of Edge Weighted Graphs. We have developed a state of art on the sequential watershed algorithms in order to motivate the choice of the algorithm that is the subject of our study, which is the M-border Kernel algorithm. The main objective of this thesis is to parallelize this algorithm in order to reduce its running time. First, we presented a review on the works that have treated the parallelization of the different types of Watershed in order to identify the issues raised by this task and the appropriate solutions to our context. In a second place, we have shown that despite the locality of the basic operation of this algorithm which is the lowering of some edges named the M-border edges; its parallel execution raises a data dependency problem, especially at the M-border edges which have a common non-minimum vertex. In this context, we have proposed three strategies of parallelization of this algorithm that solve this problematic: the first strategy consists of dividing the initial graph into bands called partitions processed in parallel by P processors. The second strategy is to divide the edges of the initial graph alternately into subsets of independent edges. The third strategy consists in examining the vertices instead of the edges of the initial graph while preserving the thinning paradigm on which the sequential algorithm is based. Therefore, the set of non-minima vertices adjacent to the minima ones are processed in parallel. Finally, we studied the parallelization of a segmentation technique based on the M-border kernel algorithm. This technique consists of three main steps which are: regional minima detection, vertices valuation and M-border kernel computation. For this purpose, we began by studying the data dependency of the different stages of this technique and we proposed parallel algorithms for each one of them. In order to evaluate our contributions, we implemented the parallel algorithms proposed in this thesis, on a shared memory multi-core architecture. The results obtained showed a notable gain in terms of execution time. This gain is translated by speedup factors that increase with the number of processors whatever is the resolution of the input images
Document type :
Complete list of metadata

Cited literature [119 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Friday, March 29, 2019 - 12:36:57 PM
Last modification on : Saturday, January 15, 2022 - 3:56:30 AM
Long-term archiving on: : Sunday, June 30, 2019 - 2:13:56 PM


Version validated by the jury (STAR)


  • HAL Id : tel-02083986, version 1


Yosra Braham. Parallélisation de la ligne de partage des eaux dans le cadre des graphes à arêtes valuées sur architecture multi-cœurs. Automatique. Université Paris-Est; Ecole nationale d'ingénieurs (Metz), 2018. Français. ⟨NNT : 2018PESC1137⟩. ⟨tel-02083986⟩



Record views


Files downloads