Neural networks that segment thin branching structures, such as blood vessels, nerve canals and roads, often produce outputs that look nearly perfect by overlap scores but are broken into pieces. A one-voxel gap barely moves the Dice score, yet it cuts the vessel in two and makes the mask useless for flow simulation or surgical planning. Today there are two ways to fix this. One is to train with topology-aware losses. The other is to pay an expert to redraw the structure voxel by voxel. We propose a third option that costs much less: show the expert a handful of yes/no questions of the form "do these two fragment ends belong to the same canal?". Each question is chosen so that its answer removes as much worst-case topological error as possible from the repaired structure.
The core idea borrows minimax regret from voting theory, a rule that picks the option whose worst-case loss is smallest when some preferences are still unknown. Here the "candidates" are not politicians. They are the possible ways the fragments could really be connected. The key observation is that many of these structures come with a strong shape prior. A mandibular canal is a single path per side, and a retinal or cerebral arterial tree is close to a tree. With that prior, the space of valid reconnections has a matroid structure: the family of forests in a graph, over which greedy algorithms find optimal solutions. That structure has two consequences. Worst-case regret can be computed with a greedy spanning-forest step rather than exhaustive enumeration. And because the constraint couples the gaps, the answer to one question also settles others.
Core Claim
We claim that on tree-like tubular anatomy, choosing expert queries by minimax regret over topologically valid reconnections will reach a given Betti error with substantially fewer yes/no answers than asking about gaps in order of model uncertainty or persistence. Betti error is the mismatch in the number of connected components and loops. We also claim that this selection can run in near-linear time per query in the number of candidate gaps.
The gain should come specifically from the coupling that the tree prior induces between gaps. The claim therefore predicts its own failure mode. On networks without such a prior, such as road grids with many loops, the advantage should disappear.
Where This Sits in Prior Work
Three lines of work motivate the gap. Topology-aware losses reduce fragmentation during training but do not remove it. clDice penalizes mismatched centerlines through a soft skeleton. TopoMatch matches persistent-homology features only when they overlap in space. It needs matching that is cubic in the number of pixels. Efficient Betti Matching brings this to 3D but remains CPU-bound. Even strong clDice-trained mandibular canal models still fail at low-contrast entry and exit zones, as reported for the transformer model of Automatic segmentation of mandibular canal using transformer based neural networks. Human input is therefore still needed at exactly those points.
The ToothFairy challenge shows how expensive dense labels are: of 443 volumes, only 153 are densely annotated. Existing active learning for segmentation, for example Bayesian Active Learning for Semantic Segmentation and Pool-Based Active Learning with Proper Topological Regions, picks images or regions to label densely by entropy. It asks neither cheap relational questions nor anything about connectivity.
The query-selection method comes from Robust Approximation and Incremental Elicitation in Voting Protocols. That paper computes minimax regret under incomplete ballots. Its Current Solution Strategy asks about the difference between the current best candidate and its adversarial "witness". It found the provable winner on the Sushi data with 11.82 pairwise queries per voter versus over 20 for random queries. We keep the strategy but change the candidate space.
The same paper documents a hazard that constrains our design. The regret-minimizing choice can be a candidate that could never actually win. In segmentation this would mean choosing a topologically impossible mask. We avoid it by construction: only valid forests are ever candidates.
Comparing Few to Rank Many (DopeWolfe) is the closest active-preference method. It chooses informative subsets for a Plackett-Luce model, a standard probabilistic ranking model, over vectors in $\mathbb{R}^d$. It gets its speed from a decomposition into pairwise terms. Connectivity is not pairwise-decomposable, so its design criterion does not transfer directly. We use it as a baseline, not as the mechanism.
The complexity literature enters as a constraint. Exact topological losses are cubic, and the tree-depth work shows that structural restrictions are what bring polynomial exponents down. Our restriction is the matroid structure of forests, which keeps each query step at roughly the cost of Kruskal's algorithm.
Research Program
The system first runs a trained segmenter, for example nnU-Net or Swin-UNetR with clDice, and extracts fragments by connected-component analysis. It then builds a fragment graph. Nodes are fragments. Candidate edges are plausible bridges between endpoint pairs within a distance and angle window. Each edge carries a model-derived weight: the mean foreground likelihood along the minimum-cost bridging path, and its length.
A reconnection hypothesis $H$ is a set of accepted bridges that forms a forest. For the canal it can be tightened to a spanning path per side. Expert answers fix some edges as present or absent. The loss between a chosen hypothesis $H$ and a true one $T$ is the length-weighted symmetric difference of bridges. This is a proxy for centerline sensitivity and precision in the spirit of clDice. The regret of $H$ is
$$R(H) = \max_{T \in \mathcal{F}_Q} \sum_{e \in H \triangle T} \ell_e ,$$
where $\mathcal{F}_Q$ is the set of plausible forests consistent with the answers so far, $\ell_e$ is the bridge length and $\triangle$ is symmetric difference.
For a fixed $H$, the inner maximization is a maximum-weight forest with signed weights: $+\ell_e$ for edges outside $H$ and $-\ell_e$ for edges inside it. That is solvable greedily because forests form a graphic matroid. At each step we take $H$ as the most likely forest, find the adversarial witness $T$, and ask about the uncertain edge in $H \triangle T$ with the largest weighted contribution. This is the Current Solution Strategy transplanted onto forests. Every answer contracts or deletes an edge, which can collapse other gaps at once. For example, a confirmed bridge makes competing parents of the same fragment impossible.
Analysis has three parts. We will bound query counts relative to the number of gaps on trees versus general graphs. We will characterize the non-matroid priors, such as degree bounds and fixed loop counts, where exact regret becomes hard, and show how far the forest relaxation degrades there. We will also handle noisy answers by softening fixed edges into weight penalties.
Baselines
The naive reference point is doing nothing: the segmenter output after connected-component cleanup, with zero queries. Next to it we run an automatic nearest-endpoint reconnection that accepts every bridge above a likelihood threshold. This tests whether a human is needed at all.
The strongest competitor, and the ablation that isolates our key ingredient, is persistence-ordered querying. It asks about the same candidate bridges, in the same yes/no format, on the same fragment graphs, ranked by persistence or by bridge uncertainty. It then accepts or rejects each bridge independently. It shares everything with our method except the coupling through the forest constraint and the witness-driven selection. A second ablation keeps minimax regret but drops the forest constraint, so edges become independent.
We also run DopeWolfe-style D-optimal selection over edge features, random querying, and entropy-based region active learning in the style of Pool-Based Active Learning with Proper Topological Regions. The region baseline is compared at matched annotation time, not matched query count, using a timing model calibrated in a small annotator study.
All methods get the same segmenter, candidate graph, answer oracle, noise model and budget sweep of 0 to 50 queries per volume. Any thresholds are tuned on the same validation split. Beating the persistence baseline means reaching its Betti error with at least 30% fewer queries on ToothFairy and DRIVE, averaged over seeds with confidence intervals, without worse HD95.
On the underlying segmentation, the ToothFairy top method reports DSC 0.796 and HD95 4.49 mm (ToothFairy). The clDice transformer reports Dice 0.844 and HD95 2.947 mm (mandibular canal transformer). We found no reported result on Lacuna for Betti error or clDice on ToothFairy, DRIVE or Vessap, so those zero-query baselines will be measured by us.
Why not just…?
Why not just ask about gaps in order of persistence or uncertainty? This is the real threat. If gaps are nearly independent, it should match us, and we expect exactly that on Massachusetts Roads. Our method has an advantage only when one answer constrains others, as in single-path canals and tree-like arteries. The ablation without the constraint and the roads-versus-canal comparison will show whether that coupling carries measurable savings. If it does not, the claim is wrong.
Why not just train with a stronger topological loss? TopoMatch and Betti matching reduce Betti error but guarantee nothing per case, and they cost cubic or CPU-bound computation. Clinical use needs a case-level fix. We apply our queries on top of clDice-trained models and report the residual errors that remain after the best loss.
Why not just have the expert redraw broken regions? Dense correction is what makes ToothFairy's dense labels scarce. Our annotator-time study compares one yes/no answer on a small crop with scribble correction of the same gaps.
Why not use D-optimal design as in DopeWolfe? It optimizes information about a linear utility and ignores the global connectivity that defines the loss. It is included as a baseline under the same budget.
Proposed Experiments
The primary benchmark is ToothFairy, with a strict prior of one path per side. It is followed by DRIVE and Vessap arterial subsets, which use a near-tree prior. Massachusetts Roads serves as the negative control, where the prior is weak and many loops exist. Answers come from an oracle that reads connectivity from the ground-truth mask, with symmetric flip noise of 0%, 5% and 10%. We report Betti error, clDice, HD95 and per-query wall-clock against the query budget.
The decisive checks are three. The first is a curve-level win over persistence ordering on canals and trees, with parity on roads. The second is sublinear query growth in the number of gaps on tree-structured volumes. The third is per-query computation that stays in milliseconds while exact enumeration over forests becomes infeasible beyond about twenty gaps. If the first check fails, the proposal reduces to the persistence heuristic and should be abandoned.
References
- clDice - A Novel Topology-Preserving Loss Function for Tubular Structure Segmentation
- Topologically Faithful Image Segmentation via Induced Matching of Persistence Barcodes
- Efficient Betti Matching Enables Topology-Aware 3D Segmentation via Persistent Homology
- Automatic segmentation of mandibular canal using transformer based neural networks
- Segmenting the Inferior Alveolar Canal in CBCTs Volumes: The ToothFairy Challenge
- Bayesian Active Learning for Semantic Segmentation
- Pool-Based Active Learning with Proper Topological Regions
- Robust Approximation and Incremental Elicitation in Voting Protocols
- Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
- On the Power of Tree-Depth for Fully Polynomial FPT Algorithms