An O(1) Time Parallel Algorithm for the 3D Euclidean Distance Transform on the CRCW PRAM Model .

Y.-R. Wang and S.-J. Horng (PRC)

Keywords

Computer Vision, Euclidean Distance Transform, Image Processing, Parallel Algorithm, CRCW PRAM Model.

Abstract

In this paper, we develop a parallel algorithm for the 2D Euclidean distance transform (2D EDT) of a binary image of size N x N in 0/1 time using N^{2+ +ε} CRCW processors and a parallel algorithm for the 3D Euclidean distance transform (3D EDT) of a binary image of size N x N x N in 0(1) time using N^{3+ +ε} CRCW processors.