Fast distance transform computation using dual scan line propagation

Fatih Porikli, Tekin KocakReal-Time Image Processing 2007 · DOI

TL;DR

This paper introduces two novel, fast algorithms for computing distance transforms in 2D binary images: Dual Scan Line Propagation and Wave Propagation. These methods significantly speed up computation by avoiding explicit distance calculations, making them highly efficient for large datasets and computationally constrained applications.

What Problem Does This Paper Address?

The distance transform is a fundamental operation in image processing, computer graphics, and pattern recognition, mapping each pixel to its distance from the nearest object point. However, traditional methods for computing the exact Euclidean distance transform are computationally intensive, especially for large images with many object points. This often leads to approximations or algorithms that are difficult to parallelize. The paper aims to address this by developing fast, efficient, and potentially parallelizable algorithms that approximate the distance transform without the prohibitive computational cost of exhaustive searches.

Methods

The paper presents two primary algorithms:

  • Dual Scan Line Propagation: This method works by scanning each image line independently in opposite directions (forward and backward). During the scan, an incremental counter is used. When an object point is encountered, the counter is reset, and for subsequent background points, the counter is incremented. The key insight is that for points along a line originating from an object point, the distance generally increases. The algorithm cleverly uses this property to assign distances without explicit calculations. For points that might be closer to an object point on the "other side" of the line, a second scan in the opposite direction is performed, and the minimum of the two computed distances is taken. This approach can be extended to multiple directions to improve accuracy, with each additional direction refining the distance map.
  • Wave Propagation: This algorithm starts by identifying object points and assigning them a distance of zero. These points form the initial "wavefront." The algorithm then iteratively expands this wavefront. At each step, the counter (representing distance) is incremented, and all unprocessed neighbors of the current wavefront points are added to the new wavefront. Points that have been processed are marked as such. This method is conceptually similar to a breadth-first search. The type of distance metric (e.g., city-block or chess-board) depends on the connectivity rule used to define neighbors (4-connectivity for city-block, 8-connectivity for chess-board).

Datasets

The paper does not explicitly mention specific named datasets. Instead, it states that the algorithms were tested on "several binary images" and that the "average computation times for 512 × 512 images" were measured. The focus is on the performance of the algorithms on generic binary image structures rather than on specific benchmark datasets.

Key Insights and Ideas

  • Avoiding Explicit Distance Computation: The core innovation is the realization that distance transforms can be approximated by iterative incrementing and comparison operations, rather than calculating Euclidean distances for every pair of points.
  • Scan Line Propagation for Efficiency: The dual scan line approach leverages the inherent structure of image lines to propagate distance information efficiently, making it amenable to parallelization.
  • Wavefront Expansion for Simplicity: The wave propagation method offers a conceptually simple and fast way to approximate distances, particularly for city-block and chess-board metrics.
  • Accuracy vs. Computational Power Trade-off: The dual scan line method's precision can be adjusted by increasing the number of scanning directions, allowing a balance between accuracy and computational resources.
  • Parallelization Potential: Both proposed methods are highlighted for their suitability for parallel implementation, a significant advantage over many existing sequential algorithms.

Key Results

  • Speedup: Both the Dual Scan Line Propagation and Wave Propagation methods achieved significant speedups, reducing computation times to "almost one third of the current state-of-art implementation." For a 512x512 image, the paper reports average computation times: Breu's algorithm at 160 msec, Level-set at 1200 msec, Dual-scan at 100 msec, and Wave-front at 30 msec.
  • Approximation Quality: The dual-scan propagation method approximates the Euclidean distance, with accuracy improving with more scanning directions. The wave-front propagation approximates city-block or chess-board distances depending on the connectivity used.
  • Memory Efficiency: The dual scan method does not require additional memory space beyond the distance map itself, as propagation results update the same map.

Limitations and Future Work

  • Approximation Error: The paper acknowledges that in the dual scan propagation, if the number of scanning directions is less than the actual number of normal directions on a complex surface (e.g., sharp edges, concavities), approximation errors can occur. These errors become more apparent with larger data spaces.
  • Wavefront Memory: The wave-front propagation method requires a mask of labels, which "doubles the memory imprint" compared to the dual scan method.
  • Future Work: The paper suggests that increasing the number of scanning directions in the dual scan method can improve accuracy, implying that further exploration of optimal direction sets could be beneficial. The paper also mentions the straightforward extension of the formulation to higher dimensional spaces.

Summary updated

BibTeX
@inproceedings{porikli2007fast,
  author = {Fatih Porikli and Tekin Kocak},
  title = {{Fast distance transform computation using dual scan line propagation}},
  booktitle = {Real-Time Image Processing},
  year = {2007},
  doi = {10.1117/12.704760},
}
Figure