Scalable and efficient parallel algorithms for Euclidean Distance Transform on the LARPBS model
A parallel algorithm for Euclidean Distance Transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n x n pixels, the algorithm can complete EDT transform in O(n.log n/c(n).log d(n)) time using n.d(n).c(n) processors, where c(n) and d(n) are parameters satisfying 1 less than or equal to c(n) less than or equal to n, and 1 < d(n) &LE; n, 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(&epsilon;), the algorithm can be completed in O(1) time using n(2+&epsilon;) processors. To the best of our knowledge, this is the most efficient constant-time EDT algorithm on LARPBS.
parallel algorithm distance transform image processing