The Euclidean Distance Transform (EDT) is an important tool in image analysis and machine vision. It is compute-intensive and real-time applications call for highly parallel solutions. A new linear-time parallel algorithm for EDT is proposed in this paper. The algorithm readily maps to hardware. A pipelined cellular architecture is presented. The architecture is modular and cascadable. Preliminary results of FPGA implementation indicate that the proposed architecture can compute EDT at speeds much higher than the video rate using only a small percentage of the chip (components) for fairly large image sizes.