A parallel implementation of exact Euclidean distance transform based on exact dilations

OM Bruno and LD Costa

MICROPROCESSORS AND MICROSYSTEMS, 28(3):107-113, 2004

This article reports the effective implementation of the exact Euclidean distance transform in a distributed system based on standard PCs, by using a simple data exchange protocol. The approach is based on the concept of exact distances, namely the denumerable set of distances found on the orthogonal lattice. The exact dilation algorithm, introduced recently, involves the successive scanning of the image elements for consecutive exact distance values, while assigning these values to empty neighboring pixels. The use of data compression methodology, as well as the quantitative characterization of the parallel efficiency, are also investigated and discussed considering several image sizes and the quantity of foreground elements. Among the obtained results, we have that the latter parameter strongly affects the overall performance and that the compressing strategy represents a potentially useful resource for increasing the overall processing efficiency. (C) 2004 Elsevier B.V. All rights reserved.