Structure-Preserving Instance Segmentation via Skeleton-Aware Distance Transform

Zudi Lin, Donglai Wei, Aarush Gupta, Xingyu Liu, Deqing Sun, Hanspeter Pfister

TL;DR

Standard distance transforms struggle to segment non-convex objects with varying widths, often fragmenting a single object into multiple pieces. This paper introduces the Skeleton-Aware Distance Transform (SDT), an intermediate representation combining object skeletons with boundary distance maps to enforce intra-object connectivity while sharply separating touching instances. SDT achieves state-of-the-art performance on gland instance segmentation, notably slashing the shape-dissimilarity Hausdorff distance by 10.6%.

What Problem Does This Paper Address?

Segmenting biomedical structures—such as gland tissues in histology images—is notoriously tricky. These objects frequently touch one another, exhibit non-convex shapes, and have narrow "throttles" or necks connecting larger sections.

Existing bottom-up segmentation representations fall into common failure modes:

  1. Binary boundary maps are prone to false merges when small prediction errors bridge the boundary between touching instances.
  2. Euclidean Distance Transforms (DT) assign each pixel its distance to the nearest boundary. While DT separates rounded, touching objects effectively, non-convex objects with thin connections end up with multiple local peaks and dips. Thresholding or watershedding these landscapes inevitably causes over-segmentation (splitting single objects).

The authors address this dilemma: how can an intermediate representation preserve sharp boundaries between touching objects while strictly maintaining topological connectivity within complex, irregular instances?

Methods

The authors propose the Skeleton-Aware Distance Transform (SDT):

  • Unified Energy Function: Instead of measuring distance only to the boundary $\Gamma_b$, SDT also factors in the distance to the medial axis or skeleton $\Gamma_s$: $$E_{\text{SDT}}(x) = \left( \frac{d(x, \Gamma_b)}{d(x, \Gamma_s) + d(x, \Gamma_b)} \right)^\alpha$$ This formulation ensures that the energy is $0$ at the boundary and uniformly $1$ along the entire skeleton, creating a single connected ridge of global maxima throughout the instance interior regardless of varying widths.

  • Classification vs. Regression: Instead of regressing continuous distance values via $L_1$ or $L_2$ loss, the energy range $[0, 1]$ is quantized into 10 discrete bins plus an explicit background channel (11 channels total) and trained using standard cross-entropy.

  • On-the-Fly Local Skeletons: Spatial augmentations like cropping can slice an object, making a pre-computed global skeleton inconsistent with the visible part. SDT computes the skeleton on-the-fly after all geometric augmentations to avoid training the network to hallucinate out-of-frame structures.
  • Network and Inference: A DeepLabV3 network (ResNet backbone augmented with CoordConv) predicts the binned SDT map. At test time, pixels above an energy threshold ($\theta = 0.7$) form skeleton seeds; connected-component labeling and a watershed transform on the inverted energy landscape yield the final instance masks.

Datasets

The authors evaluate SDT on the Gland Segmentation Challenge (GlaS) dataset:

  • 85 training images and 80 test images (divided into Part A with 60 normal tissue images and Part B with 20 challenging abnormal/malignant tissue images).
  • Evaluated using three metrics: instance-level F1 score (detection), Dice index (overlap), and Hausdorff distance (shape boundary fidelity).

No new benchmarks were introduced.

Key Insights and Ideas

  • Skeletons remove multiple local maxima: Boundary distance alone produces valleys at narrow connections. Normalizing by the sum of boundary and skeleton distances flattens the peak value along the entire medial axis, eliminating over-segmentation.
  • Discretization stabilizes training: Treating distance map estimation as quantized classification rather than continuous regression prevents noisy, smeared predictions and makes the model robust to subtle energy perturbations.
  • Local skeleton consistency matters: Skeletons computed before random cropping drastically degraded performance (Hausdorff jumped from 32.29 to 47.50 on Part A), proving that deep networks suffer when forced to reconcile cropped image context with complete object topologies.

Key Results

SDT achieved state-of-the-art results on 5 out of 6 evaluation metrics on the GlaS challenge:

  • F1 Score: Reached 0.931 (Part A) and 0.866 (Part B), outperforming FullNet (0.924 / 0.853) and QSA (0.930 / 0.862).
  • Dice Index: Scored 0.919 on Part A and 0.851 on Part B.
  • Hausdorff Distance (lower is better): Achieved 32.29 on Part A and 82.40 on Part B (average of 44.82), representing a 10.6% relative improvement over the previous best method, FullNet (average 50.15).

Ablations confirmed that an energy curvature parameter of $\alpha = 0.8$, cross-entropy loss, and on-the-fly skeleton calculation provide the optimal configuration.

Limitations and Future Work

  • Skeleton Sensitivity: Standard topological thinning algorithms can sprout noisy branches from minor boundary indentations; the authors relied on Gaussian smoothing before skeletonization to mitigate this.
  • Single-Class Scope: SDT is class-agnostic. Handling multiple distinct classes requires coupling SDT with an independent semantic segmentation branch.
  • Dimensionality: Current validation is limited to 2D histology images; extending SDT to complex 3D biomedical volumes (e.g., connectomics or organ CT scans) remains an open challenge targeted for future work.

Summary updated

Abstract

Objects with complex structures pose significant challenges to existing instance segmentation methods that rely on boundary or affinity maps, which are vulnerable to small errors around contacting pixels that cause noticeable connectivity change. While the distance transform (DT) makes instance interiors and boundaries more distinguishable, it tends to overlook the intra-object connectivity for instances with varying width and result in over-segmentation. To address these challenges, we propose a skeleton-aware distance transform (SDT) that combines the merits of object skeleton in preserving connectivity and DT in modeling geometric arrangement to represent instances with arbitrary structures. Comprehensive experiments on histopathology image segmentation demonstrate that SDT achieves state-of-the-art performance.
BibTeX
@inproceedings{lin2023structure,
  author = {Zudi Lin and Donglai Wei and Aarush Gupta and Xingyu Liu and Deqing Sun and Hanspeter Pfister},
  title = {{Structure-Preserving Instance Segmentation via Skeleton-Aware Distance Transform}},
  booktitle = {International Conference on Medical Image Computing and Computer-Assisted Intervention},
  year = {2023},
  url = {https://openreview.net/forum?id=67GMVv2Mtn},
}

Loading related content...

Figure