GPU-Based Parallel Euclidean Distance Transform Algorithm

Euclidean distance transform (EDT) often suffers from high computational complexity and limited processing efficiency, especially when applied to large-scale images. To address these challenges, this paper proposes a GPU-based parallel EDT algorithm. The proposed approach first partitions the input image into multiple horizontal sub-blocks. For each sub-block, a row-wise recursive computation strategy is adopted to construct its Voronoi diagram in parallel, thereby reducing computational overhead by exploiting the strong structural similarity between the Voronoi diagrams of adjacent rows. Based on the Voronoi diagrams of all sub-blocks, the Euclidean distance from each pixel to the nearest background pixel is subsequently evaluated, completing the transform. Experimental results demonstrate that the proposed algorithm achieves up to a 52× speedup over traditional CPU-based EDT methods, leading to a substantial improvement in computational performance. Nevertheless, the scalability of the method is influenced by GPU memory capacity and the chosen sub-block partitioning strategy when processing extremely large images. Moreover, the core idea of leveraging inter-row Voronoi similarity to reduce redundant computation can be naturally extended to higher-dimensional exact EDT as well as approximate EDT variants.