GPU-Based Parallel Euclidean Distance Transform Algorithm

Yucheng Lu, Xiaoying Zhu, Aoyu Pang, Xi HeMathematics 2026 · DOI

TL;DR

This paper presents a novel GPU-accelerated algorithm for computing Euclidean Distance Transforms (EDT) on large images. By cleverly exploiting the structural similarity between adjacent image rows and using a recursive Voronoi diagram construction, their method achieves significant speedups (up to 52x) over traditional CPU-based approaches, making EDT more practical for high-resolution image processing tasks.

What Problem Does This Paper Address?

The Euclidean Distance Transform (EDT) is a fundamental operation in image processing and computer vision, used in applications like shape analysis and object segmentation. It calculates the distance of each pixel to its nearest background pixel. However, for large images, traditional EDT algorithms become computationally very expensive, limiting their practical use. While parallel approaches exist, they often struggle with the inherent data dependencies and irregular memory access patterns of EDT, especially on GPUs. This paper aims to overcome these limitations by developing an efficient, parallel EDT algorithm specifically designed for GPUs that significantly reduces computational cost and improves performance without sacrificing accuracy.

Methods

The core of the proposed method, termed PR-EDT (Partition-Based Recursive EDT), is a GPU-based parallel algorithm that leverages Voronoi diagrams. The key innovations include:

  • Block-wise Partitioning: The input image is divided into horizontal sub-blocks. This allows for parallel processing of these blocks.
  • Row-wise Recursive Voronoi Diagram Construction: Within each sub-block, the algorithm constructs Voronoi diagrams row by row. Instead of recomputing each row's diagram from scratch, it exploits the strong structural similarity between the Voronoi diagrams of adjacent rows. This is achieved through an incremental update mechanism, where the Voronoi information from a previous row is used to efficiently compute the next.
  • Candidate Proximate-Point Matrices: The algorithm first computes "candidate proximate-point" matrices for each row, representing potential nearest background pixels.
  • Proximate-Point Set Computation: It then refines these candidates into "proximate-point sets" for each row using a recursive strategy. This involves identifying and removing "dominated" points that are geometrically closer to other background pixels.
  • Parallel Distance Computation: Finally, the Euclidean distance for each foreground pixel is computed based on the derived Voronoi diagrams, leveraging the GPU's parallel processing capabilities.

Datasets

Not discussed in the paper. The paper uses generated images with varying resolutions and background-pixel ratios for experimental evaluation.

Key Insights and Ideas

  • Inter-row Voronoi Similarity is Key: The most significant insight is that adjacent rows in an image often have very similar Voronoi diagram structures. Exploiting this similarity through a recursive update strategy, rather than independent computation, drastically reduces redundant calculations.
  • Block-wise Processing for Scalability: Partitioning the image into sub-blocks is crucial for managing GPU memory and enabling parallel execution across multiple blocks.
  • Trade-off in Sub-block Size: The choice of sub-block size involves a trade-off between local computational overhead (smaller blocks) and global parallelism (larger blocks). The paper finds an optimal range around 20 rows per sub-block.
  • GPU Architecture Matters: The paper highlights how memory access patterns (coalescing) and the availability of threads significantly impact GPU performance, often creating a gap between theoretical and practical speedups.

Key Results

  • Significant Speedup: The proposed PR-EDT algorithm achieves up to a 52x speedup compared to traditional CPU-based EDT methods.
  • Competitive Performance: It consistently outperforms other parallel algorithms like the Man and Black algorithms across various resolutions and background-pixel densities.
  • Efficiency with Dense Backgrounds: The algorithm is particularly efficient when dealing with images that have a high density of background pixels, due to its ability to quickly eliminate groups of dominated proximate points.
  • Scalability: The algorithm scales well with image resolution, though it is ultimately limited by GPU memory capacity.

Limitations and Future Work

  • GPU Memory Constraints: The algorithm's scalability is limited by the GPU's global memory capacity, restricting the maximum image resolution that can be processed on a single GPU. For extremely large images, out-of-core processing or memory streaming would be necessary.
  • Sub-block Partitioning: The horizontal sub-block partitioning strategy introduces a trade-off between parallelism and overhead, requiring careful selection of sub-block size.
  • Multi-GPU and Distributed Systems: The current work focuses on a single-GPU model. Extending the algorithm to multi-GPU or distributed systems would require significant redesign of data partitioning and inter-device communication mechanisms.
  • Higher Dimensions and Approximations: The core idea of exploiting inter-row Voronoi similarity is theoretically extendable to higher-dimensional exact and approximate EDT formulations, but this would pose significant memory and complexity challenges.

Summary updated

Abstract

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.
BibTeX
@inproceedings{lu2026gpu,
  author = {Yucheng Lu and Xiaoying Zhu and Aoyu Pang and Xi He},
  title = {{GPU-Based Parallel Euclidean Distance Transform Algorithm}},
  booktitle = {Mathematics},
  year = {2026},
  doi = {10.3390/math14040597},
}
Figure