Small segmentation networks, some under 100 KB, now match much larger models on dermoscopy and ultrasound. They have not been shown to survive the move to histopathology. In pathology, the same gland or nucleus looks very different from one hospital to the next because dyes, protocols and scanners vary. This proposal keeps the deployed network tiny and unchanged, and moves all robustness machinery into the training loss. During training, we build a graph that links image patches which look structurally alike once stain colour is removed. We then penalize the network whenever it predicts different labels for linked patches. Some links connect distant regions of one slide. Others connect labeled images from one site to unlabeled images from another. At inference the graph is discarded, so the clinic runs only the bare lightweight network.
The idea joins two older threads. Classical non-local regularization comes from image restoration. It penalizes differences between pixels that have similar neighbourhoods, wherever those pixels sit in the image, rather than differences between adjacent pixels. The second thread is the Beer–Lambert model of stained tissue, which splits an image into a stain-colour part and a stain-independent tissue-density part. Non-local methods fail under stain shift because their similarity weights are computed on raw colour. Computing those weights on tissue density fixes this. Placing the non-local term in the loss rather than the network removes its quadratic inference cost, which is the other reason it has been unusable at scale.
Core Claim
A non-local total-variation penalty applied to the predicted segmentation map can make a sub-1M-parameter network stain-robust without any inference-time normalizer or attention block. The penalty is built on concentration-normalized optical-density patches, and its edges span both labeled source images and unlabeled images from other sites. Its benefit is not reducible to colour augmentation or to pixel-aligned augmentation consistency, because it does something neither can: it moves label information along structural-similarity links between different tissue locations and different sites.
Write $p_\theta(x)$ for the network's foreground probability at pixel $x$, and $E$ for a sparse set of candidate pixel pairs. The training objective is
$$\mathcal{L}(\theta) = \mathcal{L}_{\text{BCE}} + \mathcal{L}_{\text{Dice}} + \lambda \sum_{(x,y)\in E} w(x,y)\,\lvert p_\theta(x) - p_\theta(y)\rvert,$$
with the weight defined as
$$w(x,y) = \exp\!\left(-\frac{\lVert \tilde D_x - \tilde D_y\rVert^2}{h^2}\right).$$
The terms in these two equations are as follows.
- $\lambda$ sets the strength of the non-local term.
- $\tilde D_x$ is the patch around $x$ in the per-image hematoxylin/eosin optical-density channels. It is mean-subtracted and scaled to unit norm.
- $h$ is a bandwidth.
The normalization is what buys stain invariance. Under Beer–Lambert, a change in dye concentration or section thickness rescales optical density multiplicatively, and unit-norm patch descriptors cancel that rescaling. A change in dye hue is absorbed by the per-image stain-matrix estimate.
Only the first two loss terms touch labels. The third term applies to every image in the batch, labeled or not. The supervised terms also stop the network from escaping the penalty by predicting a constant map.
Relation to Prior Work
The method comes from Non-local Regularization of Inverse Problems. That work defines non-local total variation over a patch-affinity graph and alternates between updating the image and updating the graph. It reports a gain from 23.24 to 24.79 dB PSNR over local total variation on 80% inpainting.
We change what the penalty acts on. It regularizes a network's predictions rather than a reconstructed image, and the graph lives in a physics-derived space rather than intensity space. That second change is exactly the failure mode the research file flags for non-local weights under chromatic shift. Non-local Image Dehazing supplies the transfer intuition: it clusters pixels globally so that clean estimates propagate to distant degraded regions. Our cross-site edges do the analogous thing for labels.
Non-Local U-Nets for Biomedical Image Segmentation put non-local self-attention inside the network. Its reported parameter savings come from summation skips, and its attention stays quadratic at inference and was tested only on MRI. We keep the non-local prior entirely outside the deployed model.
The stain representation comes from Adaptive Stain Normalization for Cross-Domain Medical Histology. Its BeerLaNet unrolls sparse non-negative factorization into network layers and feeds the density matrix to a downstream backbone. It is reported for classification and detection only, and the authors say segmentation is future work. We use the same decomposition, via classical Vahadane/Macenko estimation or a frozen BeerLaNet, but only to build training-time graph weights, never as an inference front end.
The evidence that stain shift matters comes from The importance of stain normalization in colorectal tissue classification with convolutional networks. There, external accuracy was 50.96% unnormalized and 79.66% normalized, against about 94% internally. Even the best global normalization leaves a large gap, which motivates a method that does not rely on normalization alone.
The deployed backbones come from EGE-UNet (0.053M parameters, 0.072 GFLOPs) and SimpleUNet (a 0.67 MB variant). Neither has been evaluated on H&E histology, as far as the file shows.
Learning Disentangled Stain and Structural Representations for Semi-Supervised Histopathology Segmentation, known as CSDS, is the closest competitor and the one to beat on accuracy. It separates colour and structure using two student networks and an EMA teacher, with uncertainty-weighted pseudo-labels, and it uses unlabeled data. Our proposal differs in mechanism and in cost. CSDS enforces agreement between augmented views of the same pixel through extra networks. We enforce agreement between different pixels that are structural twins, through a loss term on a single tiny network.
TransNuSeg constrains the design. Its Sobel-based self-distillation shows that multi-component consistency losses help histology segmentation. It also shows why they are fragile: they rely on local gradient operators, which respond to dye precipitates and stain edges as readily as to tissue boundaries. That fragility is the reason we express consistency non-locally, in density space.
Research Program
The first stage is a diagnostic that needs no training. On labeled GlaS and MoNuSeg images, we build k-nearest-neighbour patch graphs under three descriptors: raw RGB, raw optical density, and concentration-normalized optical density. We measure edge purity, defined as the weight-averaged fraction of edges joining pixels with the same ground-truth label. We then re-measure purity after pushing one side of each cross-image pair through realistic stain shifts. These shifts are sampled from RandStainNA-style colour statistics fitted on CRAG and on held-out MoNuSeg organs.
The method is only worth training if normalized-density edges keep high purity under shift where RGB edges lose it. This stage also fixes $h$ and $k$ from data rather than from downstream tuning.
The second stage sets the cost of training. A dense graph is quadratic in pixel count, so we never build one. Each step samples a few thousand anchor pixels per image and finds their $k$ nearest neighbours by approximate search over the batch's density descriptors. Batches deliberately mix labeled source tiles with unlabeled tiles from the target site, so a fixed fraction of edges crosses sites. This makes the added cost linear in anchors times $k$. We report it as wall-clock and memory overhead per training step. Inference cost is by construction identical to the bare backbone, and we verify this in parameters, GFLOPs and latency on CPU.
The third stage tests one extension from the classical block-coordinate scheme. Every few epochs, the density descriptor is concatenated with the network's own early-layer features, and the graph is rebuilt. We keep this only if it raises edge purity measured on held-out labels. It carries the known risk that errors in the network's features reinforce themselves.
Baselines
The naive reference point is the same lightweight backbone, EGE-UNet and separately SimpleUNet, trained with BCE plus Dice on raw RGB. There is no stain handling and the architecture, schedule and epochs are identical. It is the floor, and it tells us how badly tiny models degrade on histology shift at all, which the file does not report. No result for EGE-UNet or SimpleUNet on GlaS, CRAG or MoNuSeg was found on Lacuna.
The second reference applies classical Macenko normalization to a fixed template in preprocessing, then trains the same backbone. It is the cheapest thing practitioners actually deploy.
The strongest zero-inference-cost competitor is the same backbone trained with RandStainNA. RandStainNA samples virtual stain templates from Gaussian fits of dataset colour statistics in LAB, HED and HSV. On MoNuSeg it reports Dice 0.7802, against 0.7270 with no normalization and 0.7792 with standard normalization, though with its own heavier segmentation network. We rerun it on our backbones with its published sampling procedure. Our method uses the same augmentation, so the only difference is the non-local term.
The most direct ablation competitor is pixel-aligned consistency. Each image is paired with its RandStainNA-augmented copy and we penalize $\lvert p_\theta(x) - p_\theta(x')\rvert$ at the same pixel, with the same $\lambda$ search and the same unlabeled target images. Any gain we report must exceed this, because it has the same training data, unlabeled data and cost class, and lacks only the non-local links.
The strongest existing method on accuracy is CSDS. Its reported GlaS Dice is 82.86 ± 1.24% at 5% labels and 85.06 ± 0.57% at 10%. On CRAG it reports 75.25 ± 1.54% at 5% labels and 79.50 ± 0.88% at 10% (from Learning Disentangled Stain and Structural Representations for Semi-Supervised Histopathology Segmentation). We compare on its label fractions and splits, and rerun it where the code allows, reporting its parameter and FLOP count alongside ours. Beating it means either matching its Dice within its reported standard deviation using a single sub-1M-parameter network at inference, or exceeding it outright under cross-dataset shift, where it has no reported number.
As an architectural alternative, we insert a non-local global aggregation block from Non-Local U-Nets into the backbone bottleneck and report its inference cost.
Three ablations isolate the key ingredient. The first builds the graph on RGB instead of normalized density. The second drops cross-site edges and keeps only within-image ones. The third drops the unlabeled target images from the loss altogether. Every configuration gets the same tuning budget, a fixed small grid over $\lambda$ and learning rate selected on a source-only validation split. We use three seeds and report means with standard deviations.
Why not just…?
Why not just use RandStainNA augmentation with BCE plus Dice, which costs nothing at inference? This is the main threat, and the design is built to confront it. The research file shows RandStainNA's segmentation gain over plain normalization on MoNuSeg is only 0.7792 to 0.7802 Dice. Augmentation also only covers stain variation inside the fitted distribution, and never uses target-site images. Our method runs augmentation underneath, so the comparison measures exactly what the non-local term adds. If that addition sits within seed noise on cross-dataset transfer, the claim is refuted and we will say so.
Why not just feed optical density, or a frozen BeerLaNet decomposition, as the network input? This is plausible, and it would add a factorization stage at inference, a cascade cost the research file warns about. Density input also leaves concentration and thickness scaling in the input, which our unit-norm descriptors remove only inside the loss. We run density-input as an additional baseline and combine it with our loss. If density input alone matches the full method, the non-local term is not earning its place.
Why not just enforce consistency between each image and its stain-augmented copy? Pixel-aligned consistency buys stain invariance at a single location. It cannot carry a label from a labeled gland at one site to an unlabeled structural twin at another. The within-image-only and no-target-data ablations separate these effects. Our prediction is that the gap over pixel-aligned consistency appears mainly in the cross-site condition and shrinks in-domain. That pattern is itself a test of the mechanism.
Why not just add global attention or use a transformer? Quadratic attention at inference is what lightweight deployment forbids. EGE-UNet is reported as 494 times smaller than TransFuse. Windowed attention such as Swin in TransNuSeg does not link distant non-overlapping regions. We report both the accuracy and the latency of the non-local-block variant, so a reader can see what inference-time non-locality buys relative to its cost.
Proposed Experiments
The main in-domain experiment is semi-supervised gland segmentation on GlaS and CRAG at 5% and 10% labels, matching the CSDS protocol, with Dice, object-level F1 and Hausdorff distance. We also report parameters, GFLOPs, CPU latency per 512×512 tile, and training overhead.
The main shift experiment trains on GlaS labels, uses unlabeled CRAG training images for cross-site edges, and tests on the CRAG test split. The reverse direction is run as well. For nuclei, we use MoNuSeg with a leave-organ-out split, since organ groups also differ in acquisition. As a controlled stress test, we apply held-out stain transformations, sampled from statistics of a different dataset, to the GlaS test set. We plot Dice against shift magnitude for every baseline.
The decisive checks are three. The first is whether normalized-density edges keep their purity under stain shift in the training-free diagnostic. The second is whether the full method beats pixel-aligned consistency on cross-dataset Dice by more than seed variance. The third is whether the RGB-graph ablation loses that advantage. If the first check holds and the second fails, the right conclusion is that structural twins exist but label propagation along them adds little beyond augmentation for gland-level segmentation. We would then test whether the same loss helps dense nuclei clusters, where local contrast is weakest.
References
- Non-local Regularization of Inverse Problems
- Non-local Image Dehazing
- Non-Local U-Nets for Biomedical Image Segmentation
- Adaptive Stain Normalization for Cross-Domain Medical Histology
- The importance of stain normalization in colorectal tissue classification with convolutional networks
- EGE-UNet: An Efficient Group Enhanced UNet for Skin Lesion Segmentation
- Simple is what you need for efficient and accurate medical image segmentation
- Learning Disentangled Stain and Structural Representations for Semi-Supervised Histopathology Segmentation
- TransNuSeg: A Lightweight Multi-task Transformer for Nuclei Segmentation
- RandStainNA: Learning Stain-Agnostic Features from Histology Slides by Bridging Stain Augmentation and Normalization