The paper presents a new parallel algorithm for computing Euclidean distance transform of a binary image. For an image of size nXn, the algorithm runs in O(n) time and takes O(n2) space. The Euclidean distance transform is computed by repeatedly performing identical local operations within a small neighbourhood of each pixel. The algorithm is therefore suitable for VLSI implementation in a cellular like structure.