Parallel algorithms for arbitrary dimensional Euclidean distance transforms with applications on arrays with...

Area of Science:

• Computer Science
• Image Processing
• Parallel Computing

Background:

• The Euclidean distance transform (EDT) is a fundamental operation in image analysis.
• Efficient computation of EDT, especially in higher dimensions, is crucial for various applications.
• Existing algorithms may face limitations in speed and scalability on parallel architectures.

Purpose of the Study:

• To develop and present novel parallel algorithms for computing the Euclidean distance transform (EDT) on an Array with Reconfigurable Optical Buses (AROB).
• To achieve optimal time complexity for multi-dimensional EDT computations.
• To demonstrate the versatility of these algorithms by applying them to related geometric problems.

Main Methods:

• Development of a parallel algorithm, "Algorithm Expander," for computing higher-dimensional EDT from lower-dimensional results.
• Implementation of O(1) time complexity algorithms for 2-D and 3-D EDT on AROB architectures.
• Extension of algorithms for n-dimensional EDT computation with O(n) time complexity.

Main Results:

• Achieved O(1) time complexity for 2-D and 3-D Euclidean distance transforms on AROB with N x N x Ndelta and N x N x N x Ndelta processors, respectively.
• Developed a general "Algorithm Expander" for efficient multi-dimensional EDT computation.
• Extended the algorithms to compute nD-EDT in O(n) time on Nn+delta processors.

Conclusions:

• The presented parallel EDT algorithms offer state-of-the-art O(1) time performance on AROB for multi-dimensional binary images.
• These algorithms provide efficient solutions for related problems like Voronoi diagrams and medial axis transform.
• The work significantly advances the parallel computation of geometric transforms on optical bus architectures.