Implementations of Parallel Computation of Euclidean Distance Map in Multicore Processors and GPUs
- 1 November 2010
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 120-127
- https://doi.org/10.1109/ic-nc.2010.55
Abstract
Given a 2-D binary image of size nxn, Euclidean Distance Map (EDM) is a 2-D array of the same size such that each element is storing the Euclidean distance to the nearest black pixel. It is known that a sequential algorithm can compute the EDM in O(n 2 ) and thus this algorithm is optimal. Also, work-time optimal parallel algorithms for shared memory model have been presented. However, these algorithms are too complicated to implement in existing shared memory parallel machines. The main contribution of this paper is to develop a simple parallel algorithm for the EDM and implement it in two parallel platforms: multicore processors and a Graphics Processing Unit (GPU). More specifically, we have implemented our parallel algorithm in a Linux server with four Intel hexad-core processors (Intel Xeon X7460 2.66GHz). We have also implemented it in a modern GPU system, Tesla C1060, respectively. The experimental results have shown that, for an input binary image with size of 10000 × 10000, our implementation in the multi-core system achieves a speedup factor of 18 over the performance of a sequential algorithm using a single processor in the same system. Meanwhile, for the same input binary image, our implementation on the GPU achieves a speedup factor of 5 over the sequential algorithm implementation.Keywords
This publication has 9 references indexed in Scilit:
- Efficient Parallel Algorithms for Euclidean Distance TransformThe Computer Journal, 2004
- Optimal parallel algorithms for finding proximate points, with applicationsIEEE Transactions on Parallel and Distributed Systems, 1998
- Parallel Computing Using Optical InterconnectionsPublished by Springer Science and Business Media LLC ,1998
- A unified linear-time algorithm for computing distance mapsInformation Processing Letters, 1996
- Parallel computation of exact Euclidean distance transformParallel Computing, 1996
- An optimal parallel algorithm for the Euclidean distance maps of 2-D binary imagesInformation Processing Letters, 1995
- EFFICIENT ALGORITHMS FOR THE EUCLIDEAN DISTANCE TRANSFORMParallel Processing Letters, 1995
- Linear time Euclidean distance transform algorithmsIeee Transactions On Pattern Analysis and Machine Intelligence, 1995
- A fast algorithm for Euclidean distance maps of a 2-D binary imageInformation Processing Letters, 1994