A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform.

Area of Science:

• Computer Vision
• Parallel Computing
• Image Processing

Background:

• The Euclidean Distance Transform (EDT) is a fundamental image processing operation.
• Existing algorithms for EDT are often not optimized for modern parallel architectures like GPUs.
• There is a need for efficient, parallelized EDT algorithms suitable for Single Instruction Multiple Data (SIMD) architectures.

Purpose of the Study:

• To present a fully-parallelized, work-time optimal algorithm for computing the exact 2D Euclidean Distance Transform (EDT).
• To design an algorithm suitable for implementation on modern GPU architectures.
• To improve the efficiency and performance of 2D EDT computation.

Main Methods:

• Developed a GPU-based algorithm for 1D EDT using CUDA binary functions, achieving O(log32n) time and O(n) work.
• Designed a three-step, fully-parallelized 2D EDT algorithm leveraging the optimized 1D EDT.
• Implemented the algorithm on GPUs, analyzing its time and work complexity.

Main Results:

• The 1D EDT GPU algorithm runs in O(log32n) time and O(n) work.
• The 2D EDT algorithm's steps achieve O(log32n) or O(logn) time complexity and O(N) total work on GPU (N=n^2).
• Experimental results demonstrate superior performance compared to state-of-the-art GPU algorithms.

Conclusions:

• This work presents the first fully-parallelized, work-time optimal algorithm for 2D EDT on GPUs.
• The proposed algorithm is efficient and suitable for modern SIMD architectures.
• The algorithm significantly outperforms existing GPU-based EDT methods.