Searching, Not Learning, the Last Few Pixels of an Ambiguous Boundary

Medical segmentation networks usually get the inside of a tumor, vertebra, or polyp right and the edge wrong. Where tissue and background have nearly the same brightness, the network has almost no local signal, and a thin band of pixels ends up with probabilities near 0.5. Recent work fixes this band with reinforcement learning (RL): contour points or voxels act as agents that learn, through many trial-and-error rollouts, where to move. That works. It is also expensive to train, slow at inference, and still fails on shapes with holes.

We propose a different approach. Keep the trained segmentation network. Take only its uncertain band, typically a few hundred to a few thousand pixels. Score candidate binary masks on that band with an energy that includes a topology term, and find a good mask at test time with gradient-free population search, meaning optimizers such as evolution strategies that compare scores of sampled candidates and never compute derivatives. No policy is trained. Because the band is small, the same problem fits the qubit-efficient quantum encoding of Qubit-efficient Variational Quantum Algorithms for Image Segmentation. That gives us a clean, shot-accounted test of whether gradient-free quantum search adds anything once its measurement cost is counted honestly.

Core Claim

The claim has two parts. The first is the main bet. On low-contrast boundaries, a learned RL refinement policy can be replaced by black-box search over discrete band masks under a nonlocal energy. This should match or beat RL contour refinement on boundary F-score while removing RL training entirely. It should also fix the hole and disconnection failures that MARL-MambaContour reports, because topology becomes an explicit term in the score rather than something a policy must discover.

The second part is a measurement, not a promise. Restricting search to the band shrinks the problem to roughly $\log_2 n + 1$ qubits, about 11 qubits for $n = 1024$. This is the first setting where the exponential shot cost that Venkatesh et al. prove for their encoding can be measured on real medical boundaries rather than on 4×4 synthetic grids. Our prior expectation is that the quantum arm loses to classical search at matched cost. The value of the experiment is that it would establish this with actual numbers.

The energy over a binary band mask $y \in \{0,1\}^n$ is

$$E(y) = \sum_{i \in B} u_i(y_i) + \sum_{(i,j) \in \mathcal{N}} w_{ij}\,[y_i \neq y_j] + \lambda\,\big|\beta(y \cup F) - \beta^{*}\big|.$$

The terms are defined as follows:

  • $B$ is the uncertain band, the pixels whose base-network probability lies between 0.2 and 0.8, dilated by a few pixels.
  • $u_i$ is the negative log of the base network's probability for pixel $i$.
  • $\mathcal{N}$ contains short- and long-range pixel pairs.
  • $w_{ij}$ are pairwise weights computed from multi-scale intensity similarity and a predicted-edge map. These weights may be negative, which encourages a label change across a predicted thin wall.
  • $F$ is the confident foreground outside the band.
  • $\beta$ counts connected components and holes (the Betti numbers).
  • $\beta^{*}$ is an anatomical prior, for example one hole for a vertebra.
  • $\lambda$ weights the topology term.

Two properties of this energy matter. Negative weights and the topology term make it non-submodular and nonlocal, so the exact max-flow graph cut no longer applies. That is the regime where search is actually needed.

Research Program

Base networks. The base networks are conventional 2D/3D U-Nets trained with the boundary-sharpening losses of Combating Uncertainty with Novel Losses for Automatic Left Atrium Segmentation. That paper adds an Overlap Loss and a Focal Positive Loss to a 3D U-Net. Because the losses are already strong, any gain we report sits on top of the best non-iterative fix rather than replacing it.

Classical search. Search runs per image at inference. The candidates are CMA-ES on a relaxed band, with masks obtained by thresholding, and mutation-only evolution on the binary mask itself. Both choices come from Direction 1 evidence:

We test whether the mutation-only result also holds for mask search, where crossover of spatially coherent patches is a plausible counter-hypothesis.

Quantum arm. The quantum arm uses Adaptive Cost Encoding (ACE). ACE prepares a shallow circuit on $\log_2 n + 1$ qubits, samples it, collapses the samples to one discrete mask, and evaluates the cost directly on that mask. Because ACE scores the collapsed mask rather than a continuous energy expectation, our nonlocal topology term is admissible without being turned into a QUBO. This is the technical reason the quantum arm fits our energy at all.

The circuit parameters are tuned with Differential Evolution, which reached the exact global minimum on synthetic grids in the original work. We run with finite-shot simulation, never exact state vectors, and log every shot. Prior quantum-RL results were obtained on noiseless simulators and report speedups only in simulation time. We treat that as a known confound and refuse it.

Compute accounting. Every method is charged three costs: training GPU-hours, inference wall-clock per image, and peak memory. The RL costs we expect to remove are the ones Direction 2 documents:

Test-time search still costs compute, so the real question is whether those evaluations are cheaper than training a policy and then rolling it out.

Baselines

Naive reference. The do-nothing reference is the base U-Net trained with Overlap and Focal Positive losses, thresholded at 0.5. On the Atrial Segmentation Challenge 2018, Combating Uncertainty reports Dice 91.54% for 3D U-Net with these two losses and 92.24% for the full pipeline with recursive refinement. We will reproduce this pipeline on the same 80/20 split. Beating it means a statistically significant gain in boundary F-score and in topology error at no loss of Dice.

Strongest existing method. The strongest competitor is RL contour refinement in the style of MARL-MambaContour. That method treats each contour vertex as a cooperative Soft Actor-Critic agent with adaptive entropy control and a Mamba policy. It is the strongest competitor because it targets exactly our band and reports the largest boundary gains in the file. The file gives only relative gains over its strongest competitor: +3.29% mBoundF on BraTS2023 and +4.98% on VerSe. No absolute mBoundF value is reported on Lacuna for MARL-MambaContour.

We will use released code if it exists, or reimplement from the paper otherwise. It gets the same base-network initialization and the same tuning budget in trials, and its training cost is counted. Beating it means matching its mBoundF within noise at a large reduction in total compute, or exceeding it on images with holes.

For interactive 3D settings we also report against IteR-MRL (Iteratively-Refined Interactive 3D Medical Image Segmentation With Multi-Agent Reinforcement Learning), which treats each voxel as an agent and reports Dice 88.53 on BraTS2015. The comparison is run in non-interactive mode, with no user clicks given to either method.

Iterative classical refinement. RecycleNet (RecycleNet) refines predictions by feeding latent features back into earlier layers. It is the cheapest iterative competitor, and we give it the same number of refinement passes as our search's wall-clock allows. No reported result for RecycleNet on these datasets was found on Lacuna.

Exact classical solvers. For the energy without the topology term, we solve the submodular part exactly by max-flow and the full QUBO with Gurobi, as Venkatesh et al. did on synthetic grids. These solvers bound the attainable energy, and every search method is reported as an energy gap to them.

Ablation of the key ingredient. The key ingredient is the non-submodular, topology-aware energy. Removing $\lambda$ and the negative weights reduces the method to a classical graph cut. If search on the full energy does not beat max-flow on the reduced energy, the central claim is wrong.

Why not just…?

Why not just use better boundary losses and attention? Combating Uncertainty's losses lift left-atrium Dice from 82.01% to 91.54%. On polyps, MISNet (Multi-scale Information Sharing and Selection Network with Boundary Attention for Polyp Segmentation) uses boundary and reverse attention and reaches mDice 0.903 on Kvasir-SEG. These methods are strong, and we build on them rather than compete. However, a per-pixel loss cannot express "this vertebra has exactly one hole" or "these two pulmonary veins stay disconnected." The topology-error metric will show whether they already get topology right. If they do, the refinement step is unnecessary, and we will say so.

Why not just run a CRF or max-flow graph cut on the uncertain band? This is the most serious threat to the classical claim. Graph cuts are exact, fast, and decades old. Our defense is narrow: they require submodular energies, which rule out repulsive terms across thin walls and any global topology constraint. The submodular-only ablation settles the question directly. If max-flow matches us on VerSe and the left atrium, the honest conclusion is that topology terms do not pay off at the band scale.

Why not just train the RL refiner offline, or use RecycleNet? Offline Q-learning (Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes) removes online rollouts, but its authors needed 10 million gradient steps and single-seed runs. It also stays bound to the coverage of its dataset, which is weak precisely at unusual boundaries. RecycleNet avoids the memory cost of holding several RL networks but has no topology handle. Both are measured in our compute-matched comparison.

Why not just use Gurobi or simulated annealing instead of a quantum sampler? For the quantum arm, this is not merely a threat; we expect it to win. Venkatesh et al. use Gurobi as ground truth, and their own analysis shows shots grow as $O(2^q)$. The quantum arm stays in the proposal only because no one has measured that tradeoff on real boundaries, at band sizes where simulation is still feasible. We report energy gap against shots, and we state in advance that classical search is expected to dominate beyond about 64 band pixels.

Proposed Experiments

Datasets. We use four datasets:

  • Atrial Segmentation Challenge 2018: thin walls, pulmonary-vein branches, and an established Dice reference.
  • VerSe: vertebrae with a real hole, where MARL-MambaContour reported its largest gain.
  • BraTS2023: diffuse tumor edges.
  • Kvasir-SEG and ETIS-LaribPolypDB: flat polyps, with ETIS as a held-out shift test against MISNet's reported 16.8% generalization drop.

Metrics. We report Dice, mBoundF, 95th-percentile Hausdorff distance, and topology error (absolute Betti-number mismatch to ground truth). Alongside these we report training GPU-hours, per-image inference latency, and peak memory. All results use five seeds with paired tests.

Decisive check 1. On VerSe and the left atrium, full-energy search must reduce topology error relative to both the max-flow ablation and the MARL-MambaContour reimplementation, without worsening mBoundF.

Decisive check 2. At matched inference wall-clock, search must reach mBoundF within noise of RL refinement, using zero RL training hours. Otherwise, the overhead argument fails.

Decisive check 3. This check is for the quantum arm. On band crops of 16, 64, 256, and 1024 pixels, we plot the energy gap to Gurobi against total shots for ACE with Differential Evolution. We place classical CMA-ES and simulated annealing on the same axis, measured in cost evaluations.

Detector dependence. We also test the failure mode named in Gap 5 of the research file. The band comes from a probability map rather than a bounding box, so we count how often a lesion missed by a detector still produces a nonempty band. When the base network assigns the lesion no uncertain pixels at all, our method cannot recover it either.