Pixel Approximation Errors in Common Watershed Algorithms

Hans Meine, Peer Stelldinger, Ullrich KötheDGCI 2009 · OpenReview

Abstract

The exact, subpixel watershed algorithm delivers very accurate watershed boundaries based on a spline interpolation, but is slow and only works in 2D. On the other hand, there are very fast pixel watershed algorithms, but they produce errors not only in certain exotic cases, but also in real-world images and even in the most simple scenarios. In this work, we examine closely the source of these errors and propose a new algorithm that is fast, approximates the exact watersheds (with pixel resolution), and can be extended to 3D.

Introduction: The Discretization Dilemma

Watershed segmentation is a fundamental tool in image processing, conceptualizing an image as a topographic surface where catchment basins are filled to define boundaries. However, practitioners currently face a binary choice: utilize slow, 2D-limited subpixel algorithms for high precision, or employ fast, multi-dimensional pixel-based algorithms that suffer from significant "grid bias."

Pixel-based methods often produce jagged or topologically incorrect boundaries because they are constrained to immediate neighbors (4 or 8-connectivity). This causes boundaries to "snap" to preferred grid directions, leading to geometric distortion and oversegmentation. This paper analyzes these discretization errors and introduces a novel "Fast Flowline Algorithm" to bridge the gap between speed and subpixel accuracy.

The Fast Flowline Algorithm

The proposed method traces the path of "water" (flowlines) toward local minima using three key innovations:

  1. Subpixel Tracing: By employing Runge-Kutta integration on a continuous, interpolated version of the image, the algorithm avoids the rigid snapping inherent in grid-based jumps.
  2. Early Termination: To maintain efficiency, tracing stops as soon as a flowline enters a region where surrounding grid points have already been assigned to a basin.
  3. Priority Processing: A priority queue ensures pixels near minima are processed first, allowing early termination zones to expand rapidly and minimize redundant calculations.

Experimental Evaluation

Watershed segmentation of a synthetic distance transform used for error analysis. Source, p. 4

Watershed segmentation of a synthetic distance transform used for error analysis.

The authors evaluated the algorithm across 2,000 experiments using:

  • Synthetic Distance Transforms: Randomly placed points were used to generate mathematically perfect Voronoi tessellations, providing a rigorous ground truth for geometric error analysis.
  • Real-World Images: A suite of images where the "Exact Watershed" (using 5th-order spline interpolation) served as the gold standard.
  • Noise Sensitivity: Testing across various gradient scales ($\sigma \in \{1, 1.5, 2, 3\}$) to ensure robustness.

Key Insights and Results

The primary source of failure in standard algorithms is the accumulation of quantization errors. When a boundary is forced to follow a grid, it eventually snaps to the nearest axis, a phenomenon the authors term the "Preferred Direction Trap."

Comparison of different watershed algorithms showing boundary discrepancies due to grid bias.

Quantitatively, the Fast Flowline algorithm demonstrates a massive improvement:

  • Error Reduction: On real-world data, standard methods like Union-Find or Seeded Region Growing exhibited error rates of 10.3% to 15.7%. The proposed method reduced this to a mere 0.28%.
  • Consistency: In synthetic tests, error dropped from ~1.8% to 0.19%.
  • 3D Extensibility: Unlike the exact subpixel method, this approach scales to 3D data, offering a solution for medical imaging (MRI/CT) where grid artifacts are historically problematic.

Conclusion

By combining subpixel flowline tracing with clever optimization strategies, the Fast Flowline Algorithm provides near-exact accuracy without the computational burden of traditional subpixel methods. While future work will focus on further optimizing the Runge-Kutta iterations and implementing adaptive grid subdivision, this method represents a significant step forward in high-precision image segmentation.

Summary updated

Abstract

The exact, subpixel watershed algorithm delivers very accurate watershed boundaries based on a spline interpolation, but is slow and only works in 2D. On the other hand, there are very fast pixel watershed algorithms, but they produce errors not only in certain exotic cases, but also in real-world images and even in the most simple scenarios. In this work, we examine closely the source of these errors and propose a new algorithm that is fast, approximates the exact watersheds (with pixel resolution), and can be extended to 3D .
BibTeX
@inproceedings{meine2009pixel,
  author = {Hans Meine and Peer Stelldinger and Ullrich Köthe},
  title = {{Pixel Approximation Errors in Common Watershed Algorithms}},
  booktitle = {DGCI},
  year = {2009},
  url = {https://openreview.net/forum?id=uH3tBrt6ClF},
}
Figure