Introduction

Distance transform (DT) is a geometric operation fundamental to various applications in image processing, pattern recognition, computer vision, and machine learning. It converts a binary image (in theory, a set function) into a distance map where each pixel or voxel represents the shortest distance to a subset of interest, typically the object boundary. The choice of distance metric varies, which can significantly influence the computational efficiency and outcome of the distance transform.

In recent years, the demand for real-time applications has made it imperative to develop algorithms for distance transform that are computationally efficient. Among the most notable, fast algorithms include those based on the Euclidean distance metric due to its geometric significance and complexity. In this article, we'll discuss the fastest available algorithms for distance transform, focusing on the advances and optimizations that have paved the way for high-performance solutions.

Distance Transform Algorithms

Basic Algorithms

1. Naive Algorithms:
   • These algorithms compute the distance between each foreground pixel and every other pixel in the image straightforwardly. Although conceptually simple, they are computationally expensive, typically $O(n^3)$ in a naive 2D solution.
2. Wavefront Methods:
   • Based on breadth-first search, wavefront methods expand from object borders outward, updating distances step-by-step. While an improvement over naive approaches, these methods can still be suboptimal for large images, usually $O(n^2)$.

Fast Distance Transform Algorithms

1. Chamfer Distance Transform:
   • Uses integer approximations for distances via predefined distance templates and is effectively computed using raster scans of the image. The process involves two passes over the image - forward and backward.
   • Time Complexity: $O(n)$ for 2D images, where $n$ is the number of pixels.
2. Recursive Euclidean Distance Transform (REDT):
   • Utilizes a combination of parsing and propagation methods to perform DT in a lower-dimensional space efficiently, employing a recursive scanning approach.
   • Time Complexity: Linear time with respect to the number of image voxels.
3. Felzenszwalb and Huttenlocher's Distance Transform:
   • Implements a sweep-line technique for the computation of a Euclidean distance map. It processes image rows one by one and combines results across image dimensions for final results.
   • Time Complexity: $O(n)$ for continuous data, making it notably efficient and widely adopted.

Comparative Performance

Below is a table summarizing key information about these algorithms:

Implementation Example

Below is a simplified pseudocode example of Felzenszwalb and Huttenlocher's algorithm:

• Multiscale Processing: Utilizing varying resolutions and scales to speed up calculations by coarsely approximating areas and refining subsequently.
• Parallelization: Algorithms that adapt well to parallel computing architectures, such as GPUs, can see exponential performance improvements, especially relevant for high-dimensional data.
• Incremental Updates: In dynamic settings, where binary data changes over time, some algorithms can incrementally update the distance map without recomputing from scratch, saving significant computational resources.