| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Scalable and Efficient Parallel Algorithms for Euclidean Distance Transform on the LARPBS Model
November 2004 (vol. 15 no. 11)
pp. 975-982
Abstract—A parallel algorithm for Euclidean Distance Transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n\times n pixels, the algorithm can complete EDT transform in {\rm{O}}\left( {\frac{n \cdot \log n}{c(n) \cdot \log d(n)}} \right) time using n\cdot d(n) \cdot c(n) processors, where c(n) and d(n) are parameters satisfying 1\le c(n)\le n, and 1, respectively. By selecting different c(n) and d(n), the time complexity and the number of processors used can be adjusted. This makes the algorithm highly scalable and flexible. The algorithm also provides a general framework for EDT algorithms on LARPBS, and many existing and unknown parallel EDT algorithms can be deduced from this framework. In particular, if we let c(n)= n,d(n)= n^\varepsilon, the algorithm can be completed in {\rm{O(1)}} time using n^{2+\varepsilon} processors. To the best of our knowledge, this is the most efficient constant-time EDT algorithm on LARPBS.
[1] L. Chen and H.Y.H. Chuang, “A Fast Algorithm for Euclidean Distance Maps for a 2-D Binary Image,” Information Processing Letters, vol. 51, pp. 25-29, 1994.
[2] L. Chen, “An Optimal Algorithm for Complete Euclidean Distance Transform,” Chinese J. of Computer, vol. 18, no. 8, pp. 611-616, 1995.
[3] A. Fujiwara, T. Masuzawa, and H. Fujiwara, “An Optimal Parallel Algorithm for the Euclidean Distance Maps of 2-D Binary Images,” Information Processing Letters, vol. 54, pp. 277-282, 1995.
[4] T. Hayashi, K. Nakano, and S. Olariu, “Optimal Parallel Algorithm for Finding Proximate points, with Applications,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 3, pp. 1153-1166, 1998.
[5] Y.H. Lee, S.J. Horng, and T.W. Kao et al., “Parallel Computation of Exact Euclidean Distance Transform,” Parallel Computing, vol. 22, pp. 311-325, 1996.
[6] S. Pavel and S.G. Akl, “Efficient Algorithms for Euclidean Distance Transform,” Parallel Processing Letters, vol. 5, no. 2, pp. 205-212, 1996.
[7] M.N. Kolountzakis and K.N. Kuatulakos, “Fast Computation of the Euclidean Distance Maps for the Binary Image,” Information Processing Letters, vol. 43, pp. 181-184, 1992.
[8] A. Datta and S. Soundaralakshmi, “Fast Parallel Algorithm for Distance Transform,” IEEE Trans. Systems, Man, and Cybernetics — Part A, vol. 33, no. 5, pp. 429-434, July 2003.
[9] Y. Pan and K. Li, “Constant-Time Algorithm for Computing the Euclidean Distance Maps of Binary Images on 2D Meshes with Reconfigurable Buses,” Information Science, vol. 120, pp. 209-221, 1999.
[10] A. Datta and S. Soundaralakshmi, “Constant-Time Algorithm for the Euclidean Distance Transform on Reconfigurable Meshes,” J. Parallel and Distributed Computing, vol. 61, pp. 1439-1455, 2001.
[11] Parallel Computing Using Optical Interconnections, K. Li, Y. Pan, and S.-Q. Zheng, eds., Boston: Kluwer Academic Publishers, Oct. 1998.
[12] Y. Pan, Y. Li, J. Li, K. Li, and S.-Q. Zheng, “Efficient Parallel Algorithms for Distance Maps of 2D Binary Images Using an Optical Bus,” IEEE Trans. Systems, Man, and Cybernetics— Part A: Systems and Humans, vol. 32, no. 2, pp. 228-236, Mar. 2002.
[13] A. Datta and S. Soundaralakshmi, “Fast and Scalable Algorithms for the Euclidean Distance Transform on a Linear Array with a Reconfigurable Pipelined Bus System,” J. Parallel and Distributed Computing, vol. 64, no. 3, pp. 360-369, 2004.
[14] L. Chen, Y. Pan, and X. Xu, “An Efficient Parallel Algorithm for Euclidean Distance Transform,” The Computer J., accepted for publication.
Index Terms:
Distance transform, parallel algorithm, image processing.
Citation:
Ling Chen, Yi Pan, Xiao-hua Xu, "Scalable and Efficient Parallel Algorithms for Euclidean Distance Transform on the LARPBS Model," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 11, pp. 975-982, Nov. 2004, doi:10.1109/TPDS.2004.71
