Towards improving edge quality using combinatorial optimization and a novel skeletonize algorithm

Marvin Arnold, Stefanie Speidel, Georges Hattab

Abstract

Deep learning models excel at boundary identification but often produce thick, "fuzzy" probability maps rather than the crisp, one-pixel-wide lines required for many computer vision tasks. This paper introduces the Gray-Weighted Path Skeletonize (GWPS) algorithm and a combinatorial optimization framework to transform these thick "ramp edges" into precise, topologically correct thin edges. By optimizing thresholding, skeletonization, and pruning parameters across diverse datasets, the proposed method achieves up to a 2.3x improvement in edge quality metrics.

Introduction

In computer vision, a critical distinction exists between a boundary—an area of uncertainty where a transition occurs—and an edge—a precise, 1-pixel wide line. While modern neural networks are highly effective at predicting boundaries, their raw outputs are frequently thick and noisy. Standard skeletonization or thinning techniques often fail to bridge this gap because they typically ignore pixel intensity (confidence) or fail to preserve the correct topology of the object. Poor post-processing leads to misaligned edges, which can compromise downstream tasks such as surgical navigation or autonomous mapping. This research provides a standardized, optimized pipeline to transform these "ramp edges" into precise, topologically correct thin edges.

Methods

The proposed post-processing pipeline is defined by three primary parameters:

  1. Threshold ($\alpha$): Filters out low-confidence noise from the initial prediction.
  2. Skeletonize Algorithm ($\beta$): The core engine that thins the boundary.
  3. Pruning ($\gamma$): Removes small, erroneous "spurs" or branches created during the thinning process.
The proposed edge refinement pipeline, showing the transition from input images (S) through grayscale boundary prediction (G) to final optimized edges (O) using parameters alpha, beta, and gamma.

The centerpiece of this framework is the Gray-Weighted Path Skeletonize (GWPS) algorithm. Unlike traditional methods that binarize an image before thinning, GWPS treats the grayscale boundary as a 3D surface where pixel intensity represents height. It utilizes a Gray-Weighted Distance Transformation (GWDT) to identify the "ridge" of this surface—the path of maximum confidence. To determine the optimal settings, the authors employed combinatorial optimization (a discrete grid search) to test thousands of parameter combinations across various datasets, ensuring the resulting edges align as closely as possible with ground truth data.

Datasets

The pipeline's versatility was evaluated across three distinct domains to prove its robustness:

  • Medical Domain: 2,250 images of kidney boundaries from porcine partial nephrectomies.
  • Natural/Depth Domain: 1,449 images of various indoor scenes from the NYU-Depth V2 dataset.
  • Standard Benchmarks: 500 natural images from the BSDS 500 dataset, the gold standard for edge detection.

Key Insights and Results

The study reveals several critical aspects of edge refinement:

  • Intensity-Aware Thinning: By using grayscale intensity as a "cost" in the distance transform, GWPS remains centered on the most confident part of the prediction. This approach is significantly more robust than early binarization, which discards valuable information.
  • Dataset-Specific Optimization: Optimal parameters ($\alpha, \beta, \gamma$) varied significantly across domains. For instance, medical images required a much higher threshold ($\alpha$) than natural images, likely due to the unique noise profiles in surgical video.
  • Efficiency of GWPS: Interestingly, with a high-quality algorithm like GWPS, pruning ($\gamma$) was often unnecessary (optimal at 0), as the algorithm produced fewer erroneous spurs than traditional methods.

When compared against original post-processing methods from six established works, the GWPS pipeline demonstrated substantial gains:

  • Accuracy: On the BSDS 500 dataset, the Signed Distance Error (SDE)—a metric combining precision and recall—improved by 2.3 times compared to original work.
  • Shape Fidelity: The Intersection over Union (IoU-box), measuring bounding box alignment, saw improvements of up to 1.6 times on specific datasets.
  • Robustness: GWPS was the top-performing skeletonization algorithm in four out of six tested scenarios.

Limitations and Future Work

Despite its success, the framework faces some challenges. The combinatorial search for optimal parameters is computationally intensive, suggesting a need for more efficient strategies like Bayesian optimization. Additionally, the pipeline's reliance on a simple threshold ($\alpha$) may be insufficient for extremely noisy inputs, indicating a potential role for integrated denoising steps. Future research could focus on training neural networks to specifically produce "GWPS-friendly" distance fields to further enhance edge quality.

Summary updated

Abstract

Background Object detection and image segmentation of regions of interest provide the foundation for numerous pipelines across disciplines. Robust and accurate computer vision methods are needed to properly solve image-based tasks. Multiple algorithms have been developed to solely detect edges in images. Constrained to the problem of creating a thin, one-pixel wide, edge from a predicted object boundary, we require an algorithm that removes pixels while preserving the topology. Thanks to skeletonize algorithms, an object boundary is transformed into an edge; contrasting uncertainty with exact positions. Methods To extract edges from boundaries generated from different algorithms, we present a computational pipeline that relies on: a novel skeletonize algorithm, a non-exhaustive discrete parameter search to find the optimal parameter combination of a specific post-processing pipeline, and an extensive evaluation using three data sets from the medical and natural image domains (kidney boundaries, NYU-Depth V2, BSDS 500). While the skeletonize algorithm was compared to classical topological skeletons, the validity of our post-processing algorithm was evaluated by integrating the original post-processing methods from six different works. Results Using the state of the art metrics, precision and recall based Signed Distance Error (SDE) and the Intersection over Union bounding box (IOU-box), our results indicate that the SDE metric for these edges is improved up to 2.3 times. Conclusions Our work provides guidance for parameter tuning and algorithm selection in the post-processing of predicted object boundaries.
BibTeX
@article{arnold2021towards,
  author = {Marvin Arnold and Stefanie Speidel and Georges Hattab},
  title = {{Towards improving edge quality using combinatorial optimization and a novel skeletonize algorithm}},
  journal = {Bmc Medical Imaging},
  year = {2021},
  doi = {10.1186/s12880-021-00650-z},
}
Figure