Boundary-Gated Tree Scans for Segmenting Faint Edges

Many recent vision models read an image the way a language model reads a sentence, one position at a time, carrying a running memory from each position to the next. The order in which pixels are visited therefore decides which pixels can inform each other. A newer family of models chooses that order from the image content. It connects similar neighboring pixels into a tree and passes memory along the branches, so information flows inside objects rather than across them. This works well on everyday photographs, where object edges are sharp. It is likely to fail where it matters most: in ultrasound, CT and endoscopy, the edge between a lesion and healthy tissue is a faint, noisy gradient. There, "which neighbor is most similar" is decided by noise, the tree routes memory straight through the lesion border, and the border disappears from the model's representation.

We propose to build the scanning tree from a separately supervised, full-resolution estimate of where the boundary is, rather than from raw feature similarity. We also scale down the memory passed along each tree edge by the predicted boundary probability on that edge. Weak edges of the tree then act as an implicit, content-aware partition of the image, and nothing is pooled away. Pixels keep their own states, and regions exist only as places where memory flows freely. The claim is testable and specific. Under a controlled reduction of lesion contrast, boundary-gated trees should lose accuracy more slowly than similarity-built trees, fixed scans and boundary-loss decoders. The mechanism behind the gain should be visible as fewer tree edges crossing the true border.

What exists and where the gap is

Three strands of prior work each do part of this. The first strand changes the scan order to preserve spatial neighborhoods. MambaTree builds a minimum spanning tree over image tokens, with edges weighted by feature dissimilarity. It then propagates state-space memory along the tree in linear time, reaching 83.4% ImageNet top-1 and +3.6 mIoU over ViM-S on ADE20K. QuadMamba adapts scan windows through a learned quadtree, but its regions stay square and axis-aligned. TSP-Mamba orders pixels by solving a travelling-salesman tour on cosine similarity, but only inside fixed 4×4 windows. 2D-CrossScan Mamba and MaLViL add multiple fixed scan directions. All of them either ignore content or trust unsupervised similarity. None has been tested where similarity across the true border is near zero. MambaTree supplies our propagation method. Its reliance on raw dissimilarity is the specific weakness we target.

The second strand targets faint boundaries in medical segmentation. It does so with late-stage edge machinery attached to backbones that read the image on a rigid grid or in a fixed scan order. BELGNet fuses a CNN with a fixed-scan Mamba branch and adds a boundary-attention decoder, reaching 89.80% Dice on BUS-B. DB-MSMUNet warps convolutions to organ shape and adds an edge-supervised decoder path, reaching 89.47% Dice on NIH Pancreas. MISNet uses axial boundary and reverse attention, reaching 0.903 mDice on Kvasir-SEG. It also limits its generalization drop on ETIS to 16.8%, where competitors drop by more than 38%. These papers motivate the proposal: boundary supervision helps. They also constrain it, because their boundary modules depend on a coarse prediction that can be wrong on nearly invisible lesions. We move boundary information from the decoder into the path along which the encoder's memory flows. We also make its influence soft, so a wrong boundary estimate slows information flow rather than blocking it.

The third strand partitions images into irregular regions. SPFormer learns soft pixel-to-superpixel assignments. Subobject-level Image Tokenization (EPOC) floods a predicted boundary map with a watershed algorithm and average-pools each segment. Two findings from this literature constrain our design. EPOC's boundary detector runs at quarter resolution and pooling discards everything inside a segment. Separately, S³-Mamba shows that spatial smoothing inside Mamba blocks washes out small low-contrast lesions (77.13% small-lesion mIoU on ISIC2018 after removing it). Smoothness-driven grouping such as superpixels or watersheds is therefore dangerous for exactly our targets. We take the key idea of EPOC, a partition driven by a learned boundary map, and drop the parts that hurt faint lesions, namely hard segments and pooling.

Core Claim

The claim is that content-adaptive scans should be built from where boundaries are, not from how similar pixels look. Similarity is uninformative when contrast is low, whereas a boundary predictor can be trained directly for that case using supervision that segmentation masks already provide for free. Concretely, on a 4-connected grid of feature positions (stride 4 in the encoder's first stage, finer than EPOC's detector in later refinement), a small head predicts an edge boundary probability $b_e \in [0,1]$ for every pair of neighboring positions $e=(i,j)$. The head is supervised by boundaries extracted from ground-truth masks. We build the spanning tree with edge cost equal to $b_e$ plus a small feature-dissimilarity term. Memory then passes along tree paths with a boundary gate:

$$h_i = \sum_{j} \Big( \prod_{e \in P(i,j)} \bar a_e \,(1-b_e)^{\gamma} \Big) \bar B\, x_j .$$

Here $h_i$ is the state at position $i$, $x_j$ the input at position $j$, $P(i,j)$ the tree path between them, $\bar a_e$ the usual learned state-space decay on edge $e$, $\bar B$ the input projection, and $\gamma \ge 0$ a learned sharpness. This sum can be computed with MambaTree's two-pass leaf-to-root and root-to-leaf dynamic program, since the gate simply multiplies each edge's decay. The complexity stays linear. When $\gamma=0$ and the cost ignores $b_e$, the model reduces exactly to MambaTree. That gives a clean ablation.

Research Program

The work has three parts. The first is a diagnostic study. We take MambaTree, a raster/cross-scan VMamba and our model, and measure the crossing rate: the fraction of tree edges (or consecutive scan steps) that cross a ground-truth boundary, weighted by the gate mass they carry. We measure it while lesion contrast is reduced synthetically. The reduction blends lesion intensity toward the surrounding tissue mean and adds matched speckle or Gaussian noise, at several levels on BUS-B and Kvasir-SEG images. This tests the mechanism the file's Gap 1 only hypothesizes: that similarity trees start leaking across borders as contrast falls, and that leakage predicts the loss in boundary accuracy.

The second part is the model itself. It is a U-shaped encoder whose blocks use boundary-gated tree propagation. The boundary head is shared across blocks and refined per stage. Following S³-Mamba's finding, the blocks contain no depth-wise smoothing convolution. The decoder is kept deliberately plain, so that any gain cannot be credited to decoder engineering.

The third part is a robustness analysis of the boundary head's own errors. We inject false-negative boundaries by randomly zeroing $b_e$ on true-border edges. We compare soft gating against hard tree cuts. The expected result is that soft gating degrades gracefully while hard cuts reproduce the error propagation that afflicts reverse-attention decoders.

Baselines

The naive reference point is a plain visual state-space U-Net with a fixed cross-scan order and standard Dice plus cross-entropy loss. It shows how much any content adaptation buys. The most direct competitor is MambaTree used as a segmentation encoder under the identical U-shaped design and decoder. It is the strongest existing content-adaptive scan and the only one whose partition is irregular. We give it the same boundary auxiliary loss as our model, so the comparison isolates where boundary information enters. The strongest reported numbers on our benchmarks come from boundary-decoder methods. On BUS-B, BELGNet reports 89.80% Dice (BELGNet). On NIH Pancreas, DB-MSMUNet reports 89.47% Dice (DB-MSMUNet). On Kvasir-SEG, MISNet reports 0.903 mDice, and on ETIS a 16.8% cross-dataset drop (MISNet). On the ISIC2018 small-lesion subset, S³-Mamba reports 77.13% mIoU (S³-Mamba). No boundary-distance or boundary F-score results for any of these were found on Lacuna, so those comparisons require our own reruns.

For fairness, we rerun BELGNet, S³-Mamba and MambaTree with public or reimplemented code under our data splits, augmentation, epoch budget and a matched hyperparameter search of equal trial count. We match parameter counts within about 10%. Published numbers are reported alongside, and we flag them as protocol-dependent. The key ablation replaces boundary-derived costs with MambaTree's dissimilarity costs and sets $\gamma=0$, keeping everything else fixed including the auxiliary boundary loss. A second ablation keeps costs but removes the gate. Beating the baselines means two things. First, matching the strongest rerun on overall Dice. Second, a statistically clear improvement, across five seeds, on boundary-focused metrics (95th-percentile Hausdorff distance and boundary F-score within a 2-pixel band) and on the slope of accuracy against contrast level. A gain in overall Dice alone would not support the claim.

Why not just…?

Why not just fine-tune MambaTree on medical images? Its encoder features are learned, so after fine-tuning its dissimilarity may already encode boundaries. This is the most important threat, and the key ablation addresses it directly. MambaTree trained with the same boundary loss is compared against our model, which differs only in edge cost and gate. If crossing rates and boundary metrics are indistinguishable across the contrast sweep, the core claim is wrong and we will report it as such. We expect a difference because learned dissimilarity is shaped by the segmentation objective only indirectly. Dice and cross-entropy are dominated by interior pixels, whereas $b_e$ is trained on the border itself.

Why not just add a boundary loss or boundary-attention decoder to a fixed-scan backbone, as BELGNet and DB-MSMUNet do? This approach is already competitive, with 89.80% and 89.47% Dice reported. Its weakness is structural. The encoder mixes lesion and tissue memory before the decoder sees anything, and the file notes that boundary modules built on a coarse prediction inherit that prediction's false negatives. The rerun BELGNet with our training budget, evaluated on the contrast sweep and on ETIS-style out-of-distribution polyps, will show whether the late-stage fix suffices. If it matches us at every contrast level, encoder-side gating is unnecessary.

Why not just use a locality-preserving fixed curve such as Hilbert or multi-directional cross scans? These fix row-jump artifacts cheaply and need no custom kernels. However, they are blind to content by construction: a Hilbert curve crosses a lesion border wherever the border happens to lie. The crossing-rate diagnostic measures this directly. The fixed cross-scan baseline also serves as the naive reference, so this alternative is tested rather than argued away.

Why not just tokenize with superpixels or watershed segments first? S³-Mamba's evidence that smoothing destroys small faint lesions, together with EPOC's quarter-resolution detector and pooling, predicts that tiny lesions get absorbed into background segments. We include an EPOC-style variant, with a watershed on our own boundary head and pooled segment tokens, as an additional baseline. The ISIC2018 small-lesion subset is where it should fail.

Proposed Experiments

The decisive experiment is the contrast sweep on BUS-B and Kvasir-SEG, with five contrast levels and five seeds. For every model we plot boundary F-score and Hausdorff distance against contrast level, alongside the crossing rate. The proposal succeeds if three things hold. Our model's boundary accuracy declines measurably more slowly than MambaTree's under identical training. Its crossing rate stays low while MambaTree's rises. Across models, crossing rate predicts boundary error.

The benchmark evaluation covers BUS-B, NIH Pancreas (2D slices), Kvasir-SEG trained and ETIS tested for generalization, and the ISIC2018 small-lesion subset, reporting Dice, mIoU and the boundary metrics against the baselines above. ADE20K serves as a sanity check that the gate does not harm high-contrast scenes relative to MambaTree. The boundary head there is supervised from segmentation masks, so no extra labels are needed. We also measure wall-clock throughput against MambaTree to confirm that the gate adds negligible cost on top of its tree kernels. Finally, the boundary-corruption test compares soft gating with hard cuts at increasing rates of missed boundaries. If soft gating does not degrade gracefully, the design should be revisited before any claim about clinical robustness is made.