What Survives Label Downsampling? Exact Region Survival for Coarse Segmentation Targets

Zhiyuan Zhang, Yukun Ou, San Tek ChoiarXiv 2026 · arXiv

TL;DR

Standard label downsampling methods like majority pooling often "delete" small objects from training targets, leaving segmentation networks blind to them. This paper introduces MatchDown, a pre-processing method that uses bipartite matching to ensure the maximum possible number of regions survive in coarse targets, significantly improving the detection of small objects like nuclei without changing the underlying network architecture.

What Problem Does This Paper Address?

Many state-of-the-art segmentation architectures (e.g., StarDist, nnU-Net, and various Vision Transformers) operate at a "coarse" resolution, meaning they predict labels for a grid of cells rather than every individual pixel. To train these networks, researchers must downsample high-resolution ground truth labels into coarse targets.

The standard tools for this—strided sampling, nearest-neighbor resampling, or majority pooling—treat each grid cell independently. If a small object (like a tiny nucleus) doesn't occupy the majority of at least one cell, it simply vanishes from the training target. The network is never supervised to find it, leading to significant missed detections and count errors. The authors found that at a downsampling factor of 8, standard methods lose 4 to 5 times more regions than theoretically necessary on the COCO dataset.

Methods

The authors reframe label downsampling as a minimum-cost matching problem.

  1. Support Graph: They build a bipartite graph where one set of nodes represents the regions (objects) in the image and the other represents the coarse grid cells. An edge exists if a region overlaps a cell.
  2. MatchDown: By finding a maximum matching in this graph, they ensure that the largest possible number of regions are assigned a unique cell in the coarse target.
  3. Matroid Structure: A key theoretical contribution is proving that the sets of regions that can survive together form a transversal matroid. This allows the use of a greedy algorithm with priority tiers (MatchDown-P). For example, they can prioritize "evaluated regions" (those that matter for metrics) that are at least the size of one cell.
  4. Adjacency Repair: Because maximum survival can sometimes force weird, non-existent adjacencies between objects, they include a "repair" step that relabels cells to minimize spurious adjacencies while maintaining the survival count.
Overview of MatchDown vs. Majority Pooling. Majority pooling loses 21 nuclei in this example, while MatchDown loses only 1.

Datasets

The authors evaluated MatchDown across several diverse benchmarks:

  • COCO & Cityscapes: Used to measure region survival in complex natural and urban scenes.
  • BBBC038 & BBBC039: Nucleus datasets that serve as a "stress test" because they contain many small, crowded objects.
  • BSDS500: Used for evaluating binary topology and adjacency repair.

Key Insights and Ideas

  • Survival $\neq$ Reconstruction: The authors distinguish between keeping a region in the target and reconstructing its exact shape. Even if a coarse target represents a nucleus as a single square cell (poor shape reconstruction), a shape-predicting head (like StarDist's radial distances) can still use that cell as a "seed" to regress the correct outline.
  • The One-Cell Guarantee: MatchDown-P guarantees that every region at least the size of one grid cell will survive in the target. Standard methods offer no such guarantee.
  • Certified Losses: Using the Dulmage–Mendelsohn decomposition, MatchDown can provide a "certificate" for unavoidable losses—proving exactly why certain regions cannot be kept on a specific grid (e.g., three regions competing for only two available cells).

Key Results

MatchDown-P achieved the theoretical lower bound for region loss across all 20 dataset-factor pairs tested.

  • Region Survival: On COCO at factor 8, MatchDown-P lost only 1,854 regions, compared to over 8,400 lost by StarDist’s strided sampling and 9,200 by majority pooling.
  • Improved Detection: On the BBBC038 nucleus dataset, a star-convex head trained on MatchDown targets successfully segmented 35% of the nuclei that majority pooling would have deleted, compared to only 15% for a model trained on majority targets.
  • Count Accuracy: On BBBC039 (factor 16), an affinity head trained with MatchDown reduced the count error by 9.3 nuclei per image compared to majority pooling.
Comparison of regions lost across different downsampling factors. MatchDown-P consistently hits the theoretical lower bound.

Limitations and Future Work

  • Computational Overhead: MatchDown is slightly slower than majority pooling (roughly 1.7x to 1.9x), though it only needs to be run once before training begins.
  • Metric Sensitivity: The authors noted that in some star-convex settings, the ranking of different methods can shift depending on the Non-Maximum Suppression (NMS) range used during inference.
  • Domain Scope: While highly effective for nucleus and panoptic datasets, the paper primarily focuses on factors 2 to 16. The impact on extremely high downsampling factors or very different types of data (like 3D volumes) remains a path for future exploration.

Summary updated

Abstract

Segmentation networks that predict at an output stride are trained against label maps downsampled by strided sampling, nearest-neighbor resampling or majority pooling. These methods label each coarse grid cell on its own, so a region that wins no cell is absent from the target and receives no positive label. We present MatchDown, which builds the coarse target from a minimum-cost matching between regions and the grid cells they occupy. It keeps as many regions as any one-region-per-cell target can, certifies how many losses are unavoidable, and with priority tiers (MatchDown-P) keeps every evaluated region (a region that a metric scores) of at least one cell's area. On COCO, Cityscapes and BBBC038 at factors 2 to 16, MatchDown-P loses exactly the minimum number of regions, whereas the downsampling used by StarDist, nnU-Net and connectomics pyramids loses four to five times as many on COCO at factor 8. Keeping a region in the target and reconstructing its shape are different problems: we show that no region lost by majority pooling can be reconstructed above IoU 0.5 by upsampling any coarse target, yet on BBBC038 a star-convex head trained on MatchDown targets segments 35% of the nuclei that majority pooling loses above IoU 0.5, against 15% when trained on majority targets and 24% on StarDist's strided target. On two nucleus datasets, with thresholds cross-validated for count error, this head has instance accuracy at IoU 0.5 (Acc50) 2.6 to 4.2 points above the strided target and at most 2.8 points below cell-center sampling, and a lower count error than the strided and cell-center targets on BBBC039. On BBBC039, an affinity head, which outputs one label per cell, lowers count error relative to majority targets by 9.3 nuclei per image at 7.2 points lower Acc50. MatchDown runs once, before training, in place of the label-downsampling step.
BibTeX
@misc{zhang2026what,
  author = {Zhiyuan Zhang and Yukun Ou and San Tek Choi},
  title = {{What Survives Label Downsampling? Exact Region Survival for Coarse Segmentation Targets}},
  year = {2026},
  eprint = {2610.39880},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39880},
}
Figure