Unsupervised semantic segmentation means labeling every pixel of an image with a category without ever seeing a human label. The strongest current systems take features from a frozen self-supervised Vision Transformer (a network that splits an image into patches and lets every patch attend to every other). They then group those features into clusters. There is a hidden tension in this setup. To see small objects, these systems process the image as several zoomed-in crops. The crops then lose the whole-image view that the transformer was supposed to provide. A pixel near a crop edge can no longer see the boat on the other side of the frame when it decides whether it is "water."
We propose a light, trainable "context stitcher." It takes per-tile transformer features, reassembles them into one full-resolution feature map, and passes information across the entire image. To do this it uses criss-cross attention, in which each location exchanges information only with its own row and column, so two rounds are enough to connect any pair of locations. The stitcher is trained jointly with a differentiable, balance-constrained clustering objective, so the clustering signal decides what long-range context is worth importing. The claim is concrete: the small-object versus global-context trade-off in unsupervised segmentation can be removed at sub-quadratic cost. The proposal also tests a related claim, that clustering gradients are safe as long as they reshape only the long-range routing and not the local features.
Core Claim
Our hypothesis concerns why earlier attempts to train features and clusters together on pixels produced blurry results. The cause was where the clustering gradient was allowed to act, not joint optimization as such. STEGO distills correspondences from a frozen DINO transformer into a small head and clusters the result with offline k-means and a conditional random field, a post-processing step that snaps labels to image edges. Its authors justify freezing by reporting that joint feature-and-cluster learning blurred outputs or missed objects. The same paper also relies on multi-crop processing to resolve small objects, and it admits persistent errors such as merging walls with ceilings.
PiCIE does train end-to-end, clustering pixels under invariance and equivariance constraints. However, its convolutional backbone sees only local neighborhoods, and it suffers co-occurrence errors such as boat labeled as water and snow labeled as sky. These two papers motivate the gap. One has global context but no clustering feedback and crop-limited context. The other has clustering feedback but only local context.
Our claim is that a stitcher trained by clustering gradients, sitting on top of locally sharp tile features, fixes both failure modes. It should do so without the instability that motivated freezing, because the local features stay fixed and only cross-image routing is learned.
Research Program
The system has three parts.
Tile features. A frozen DINO ViT-S/8 runs on overlapping high-resolution tiles. This is the same regime STEGO uses for small objects. Overlaps are averaged so the result is a single feature map at full image resolution.
The context stitcher. Two weight-shared criss-cross attention steps run over this full map, following CCNet. CCNet introduced this factorized attention for supervised segmentation and reports 11x less GPU memory and 85% fewer FLOPs than a dense non-local block. A residual connection keeps the tile features intact, so the stitcher can only add context. We reuse CCNet's operator but train it purely by unsupervised clustering signals, a setting CCNet never tested.
Dense balanced clustering. Instead of post-hoc k-means, $K$ learnable prototypes are assigned to pixels through entropic optimal transport solved by Sinkhorn iterations. This follows Differentiable Deep Clustering with Cluster Size Constraints, which showed on MNIST and CIFAR-10 vectors that marginal constraints prevent collapse into one cluster.
Those authors warn that a uniform size prior hurts unbalanced data, and pixel classes are extremely unbalanced (road versus traffic sign). We therefore relax the cluster-size constraint to a soft penalty toward a running estimate of dataset-level cluster frequencies. Writing $z_i$ for the stitched feature at pixel $i$, $\mu_k$ for prototype $k$, $Q$ for the Sinkhorn transport plan, and $P$ for the network's softmax assignment over prototypes, the objective is
$$\mathcal{L} = \mathcal{L}_{\text{corr}}(z) + \gamma\,\Big[-\textstyle\sum_{i,k} Q_{ik}\log P_{ik}\Big] + \lambda\,\mathrm{KL}\big(Q^\top \mathbf{1}\,\|\,\hat{\pi}\big).$$
Here $\mathcal{L}_{\text{corr}}$ is STEGO's correspondence distillation loss, which keeps the stitched features semantically anchored. $\gamma$ and $\lambda$ are weights. $\hat{\pi}$ is the running estimate of cluster frequencies. Gradients from the clustering terms flow into the prototypes and the stitcher.
As a controlled extension, we also unfreeze the last transformer blocks. This directly tests STEGO's claim about where joint training goes wrong.
Baselines
Naive reference. Frozen DINO tile features clustered with offline k-means and no stitching or distillation. This measures how much any learning adds.
Strongest existing method. STEGO, with the same ViT-S/8 backbone, the same crops, and its CRF, rerun with our code base and the same number of GPU-hours. Its published results are 28.2 unsupervised mIoU (mean intersection-over-union) on CocoStuff and 21.0 on Cityscapes (STEGO). Beating it means a gain over our reproduction of at least the seed-to-seed standard deviation across three seeds, under identical Hungarian-matched evaluation.
Adaptive-cluster method. ACSeg learns concept prototypes that cross-attend to frozen DINO tokens and are trained with a modularity loss. It reports 47.1% mIoU on PASCAL VOC and 16.4% on COCO-Stuff, under a protocol that should not be equated with STEGO's numbers. We compare to it on VOC under its protocol.
End-to-end convolutional reference. PiCIE, which reports 65.5% pixel accuracy on Cityscapes versus 47.9% for IIC (PiCIE).
Potsdam-3. On this aerial benchmark we found no reported result on Lacuna for STEGO, so all numbers there are our own reproductions.
Ablations. Two ablations isolate the key ingredient.
- Context-free stitcher: the stitcher is replaced by a parameter-matched stack of depthwise and dilated convolutions, giving local mixing at equal capacity.
- No clustering gradient: the stitcher is trained only with $\mathcal{L}_{\text{corr}}$, while Sinkhorn clustering stays downstream with stopped gradients.
Why not just…?
Why not just run the transformer on the whole image, since it is already global? This is the real threat. If whole-image inference at high resolution matched tiled inference on small objects, the stitcher would be unnecessary. At Cityscapes resolution with 8-pixel patches, dense attention over tens of thousands of tokens is very costly in memory. In practice, people downscale the image or crop it, and STEGO's reliance on crops for small objects suggests downscaling loses them. We will settle this empirically.
- Equal-memory comparison: whole-image DINO at the largest resolution that fits the same memory as tiles plus stitcher.
- Unlimited-memory comparison: whole-image DINO at full resolution where it fits.
- Reported metric: mIoU split by object area tercile.
If whole-image inference ties us at equal memory, we will report that the stitcher's value is purely efficiency.
Why not just add dilated convolutions or a dense CRF for long-range mixing? The de-raining work of Li et al. argues that stacked convolutions have effective receptive fields that decay quickly from the center. Dilation spreads samples into a checkerboard pattern rather than true image-wide context. A dense CRF mixes labels by color similarity and cannot learn that "flat blue region next to a hull" means water. The parameter-matched convolutional ablation and STEGO's own CRF test both points directly, and we will judge them on co-occurrence classes.
Why not just fine-tune the backbone with the clustering loss? STEGO reports this blurs results. Large-Scale Unsupervised Semantic Segmentation instead uses multi-stage pipelines and still fails on small objects. Our gradient-location ablation varies whether clustering gradients reach the last transformer blocks, the stitcher only, or neither. If backbone fine-tuning with the balanced transport objective matches stitcher-only training without blurring, then STEGO's freezing argument is wrong, and that is itself a publishable outcome.
Proposed Experiments
We train on COCO-Stuff (27-class split), Cityscapes, and Potsdam-3, plus PASCAL VOC for the ACSeg comparison. Potsdam-3 tests the domain-shift setting in which ACSeg's authors say frozen backbones degrade. Metrics are unsupervised mIoU and pixel accuracy after Hungarian matching, plus linear-probe mIoU for feature quality.
We add two diagnostic measures:
- Area-split mIoU: mIoU split by object size, which targets the small-object failure.
- Co-occurrence confusion rate: the confusion between pairs that frequently appear together (boat/water, snow/sky, wall/ceiling), which targets the context failure.
First decisive check. Against STEGO with identical tiles, the stitcher should improve co-occurrence pairs and large-region classes while matching STEGO on the smallest-object tercile. Improvement on context classes with no small-object loss is the predicted signature. A uniform gain or loss across classes would suggest something other than context is at work.
Second decisive check. The no-clustering-gradient ablation should recover a substantial part, but not all, of the stitcher's gain. If it recovers all of it, the joint-optimization half of the claim fails and the contribution reduces to an architectural one.
Third check. We plot memory and throughput against image resolution for tiles plus stitcher, whole-image dense attention, and STEGO. This shows whether the O(N√N) routing keeps full-resolution training feasible, since criss-cross cost per pixel grows with height plus width rather than with the total pixel count.
References
- Unsupervised Semantic Segmentation by Distilling Feature Correspondences
- PiCIE: Unsupervised Semantic Segmentation Using Invariance and Equivariance in Clustering
- CCNet: Criss-Cross Attention for Semantic Segmentation
- Differentiable Deep Clustering with Cluster Size Constraints.
- Dynamic Clustering Network for Unsupervised Semantic Segmentation
- Non-locally Enhanced Encoder-Decoder Network for Single Image De-raining
- Large-Scale Unsupervised Semantic Segmentation