| Autor: |
Braham, Yosra, Elloumi, Yaroub, Akil, Mohamed, Bedoui, Mohamed Hedi |
| Zdroj: |
Journal of Real-Time Image Processing; Jun2020, Vol. 17 Issue 3, p527-542, 16p |
| Abstrakt: |
Watershed Transform is a widely used image segmentation technique that is known to be very data intensive and time consuming. The M-border Kernel Algorithm computes watersheds in the framework of Edge-Weighted Graphs and allows to preserve the topology of the initial map. Parallelization represents an effective solution to accelerate it. However, this task remains challenging due to the nature of this technique. In this paper, we address this problem. We start by analyzing the data dependency issues that this algorithm raises when dealing with parallel execution. With respect to that, we propose a parallelization strategy that opts for vertex scanning instead of edges scanning of the graph while preserving the thinning paradigm on which the M-border Kernel Algorithm is based. We show that this strategy overcomes the problem of the simultaneous lowering of two adjacent M-border edges that may occur when edge scan is used. The implementation of the proposed algorithm on a shared memory multicore architecture proves its effectiveness in terms of speedup. In fact, the experimental results show that a speedup factor of 5.55 is achieved using eight processors for 2048 × 2048 images over the performance of the sequential algorithm using a single processor on the same architecture. Furthermore, the gain in terms of execution time and thus speedup is guaranteed whatever is the size of images on which the algorithm is applied. In fact, a speedup factor of 5.55 is obtained for 2048 × 2048 images, 5.11 for 1024 × 1024 images and 4.45 for 512 × 512 images using eight cores. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink