A HIGH PERFORMANCE 3D EXACT EUCLIDEAN DISTANCE TRANSFORM ALGORITHM FOR DISTRIBUTED COMPUTING

Julio Cesar Torelli and Ricardo Fabbri and Gonzalo Travieso and Odemir Martinez Bruno

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 24(6):897-915, 2010

The Euclidean distance transform (EDT) is used in various methods in pattern recognition, computer vision, image analysis, physics, applied mathematics and robotics. Until now, several sequential EDT algorithms have been described in the literature, however they are time- and memory-consuming for images with large resolutions. Therefore, parallel implementations of the EDT are required specially for 3D images. This paper presents a parallel implementation based on domain decomposition of a well-known 3D Euclidean distance transform algorithm, and analyzes its performance on a cluster of workstations. The use of a data compression tool to reduce communication time is investigated and discussed. Among the obtained performance results, this work shows that data compression is an essential tool for clusters with low-bandwidth networks.