PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Supervised Transformers for Unsupervised Object Discovery using Normalized Cut

Yangtao Wang, Xi Shen, Shell Hu, Yuan Yuan, James Crowley, Dominique Vaufreydaz

arXiv:2202.11539v2cs.CVstat.ML

TL;DR

Unsupervised object discovery needs methods that avoid costly annotations and proposal-based computation. TokenCut uses self-supervised transformer tokens in a similarity graph and segments foreground regions with normalized cut. It improves unsupervised discovery over LOST and extends to saliency detection and weakly supervised object detection.

  • Problem

    Unsupervised object discovery without human annotations is important for downstream applications, while annotation costs and proposal-based methods limit scalability.

  • Method

    TokenCut builds a similarity graph over self-supervised transformer tokens and uses normalized graph-cut spectral clustering, with the second-smallest eigenvector indicating foreground likelihood.

  • Results

    TokenCut improves unsupervised object discovery over LOST by 6.9%, 8.1% and 8.1% on VOC07, VOC12 and COCO20K respectively, with competitive or improved results on related tasks.

  • Takeaways & Limitations

    Self-supervised transformer features support a unified approach to unsupervised object discovery, unsupervised saliency detection, and weakly supervised object detection.

  • Takeaways & Limitations

    TokenCut assumes a single salient foreground object and cannot handle multiple overlapping objects or occlusion.

Abstract

from arXiv · show

Transformers trained with self-supervised learning using self-distillation loss (DINO) have been shown to produce attention maps that highlight salient foreground objects. In this paper, we demonstrate a graph-based approach that uses the self-supervised transformer features to discover an object from an image. Visual tokens are viewed as nodes in a weighted graph with edges representing a connectivity score based on the similarity of tokens. Foreground objects can then be segmented using a normalized graph-cut to group self-similar regions. We solve the graph-cut problem using spectral clustering with generalized eigen-decomposition and show that the second smallest eigenvector provides a cutting solution since its absolute value indicates the likelihood that a token belongs to a foreground object. Despite its simplicity, this approach significantly boosts the performance of unsupervised object discovery: we improve over the recent state of the art LOST by a margin of 6.9%, 8.1%, and 8.1% respectively on the VOC07, VOC12, and COCO20K. The performance can be further improved by adding a second stage class-agnostic detector (CAD). Our proposed method can be easily extended to unsupervised saliency detection and weakly supervised object detection. For unsupervised saliency detection, we improve IoU for 4.9%, 5.2%, 12.9% on ECSSD, DUTS, DUT-OMRON respectively compared to previous state of the art. For weakly supervised object detection, we achieve competitive performance on CUB and ImageNet.

1 Introduction

The paper frames unsupervised object discovery as important but difficult because annotation costs and proposal-based optimization limit scalable learning. TokenCut uses all self-supervised transformer tokens in a similarity graph and normalized cut to segment foreground objects, improving discovery and extending to related tasks.

  • Annotation costs limit supervised object detection, while active, semi-supervised, and weakly supervised approaches have had only limited success.
  • Proposal-based unsupervised object discovery can be computationally expensive because comparing proposal pairs creates quadratic overhead on larger datasets.
  • TokenCut constructs a graph from all last-layer visual-token features, uses feature similarity as connectivity, and applies normalized graph cuts via generalized eigendecomposition.
  • The second-smallest eigenvector supplies a cutting solution whose absolute values indicate foreground likelihood for each token.
  • 68.8%, 72.1% and 58.8% CorLoc on VOC07, VOC12 and COCO20K respectively outperform LOST by 6.9%, 8.1% and 8.1% respectively.
  • TokenCut also extends to weakly supervised object detection and unsupervised saliency detection, with improved CUB results, competitive ImageNet-1K performance, and improved saliency results.

2 Related Work

Related work covers self-supervised vision-transformer representations, unsupervised object discovery, weakly supervised detection, and unsupervised saliency detection. TokenCut differs by offering a unified transformer-based solution across object discovery and weakly supervised detection.

  • DINO showed that self-distillation can yield vision-transformer features containing explicit information useful for semantic image understanding.
  • Unsupervised object discovery methods either assume repeated object appearances or optimize over bounding-box proposals and inter-image similarities.
  • Weakly supervised detection traditionally uses image-level annotations and class activation maps to generate class-specific localization maps.
  • TokenCut proposes a unified transformer-based solution for unsupervised object discovery and weakly supervised object detection.
  • Unsupervised saliency detection has used color contrast, background priors, super-pixels, and heuristic pseudo-ground truth for CNN training.

3 Approach: TokenCut

TokenCut discovers salient objects by converting self-supervised vision-transformer patch features into a similarity graph and partitioning it with normalized cut. The method selects the foreground using the second generalized eigenvector and derives a bounding box from its most salient connected region.

  • TokenCut Algorithm: TokenCut extracts final-layer latent variables from a DINO-trained vision transformer as patch features for object discovery.The implementation uses ViT-S/16 and the keys from its last layer, with τ = 0.2 across datasets.
  • Normalized Cut: Normalized cut is solved through the generalized eigensystem (D − E)y = λDy, whose second smallest eigenvector provides the real-valued partitioning solution.The second eigenvector is orthogonal to the smallest-eigenvalue solution and minimizes the normalized-cut energy.
  • Graph construction: Patch tokens form nodes in a fully connected undirected graph whose edge weights encode cosine similarity between token features.Transformer positional encoding implicitly supplies spatial information, while ε = 1e−5 keeps the graph fully connected.
  • Foreground segmentation: The eigenvector is partitioned using a mean threshold, which generally outperforms K-means and EM for clustering its values into two groups.The two partitions are formed by comparing each eigenvector value with the mean projection.
  • Foreground selection: TokenCut identifies the foreground partition as the one containing the maximum absolute eigenvector value, then retains its largest connected component to produce the object location.This selection assumes foreground tokens are less connected to the entire graph and therefore have larger absolute eigenvector values.

4 Experiments

TokenCut is evaluated on unsupervised object discovery, weakly supervised object localization, and unsupervised saliency detection, with strong benchmark results and explicit failure cases.

  • 4.1 Unsupervised Single Object Discovery: TokenCut improves unsupervised single-object discovery over prior methods by 6.9%, 8.1%, and 8.1% on VOC07, VOC12, and COCO20K, respectively.Evaluation uses CorLoc, where IoU above 0.5 with a ground-truth box counts as correct.
  • 4.1 Unsupervised Single Object Discovery: TokenCut + CAD further outperforms the state of the art by 5.7%, 4.9%, and 5.1% on VOC07, VOC12, and COCO20K, respectively.CAD is a second-stage unsupervised strategy trained using foreground pseudo-box labels.
  • 4.2 Weakly Supervised Object Localization: On weakly supervised localization, TokenCut achieves the best CUB performance and exceeds LOST by 2.1% on GT Loc and 1.6% on Top-1 Loc.The comparison covers CUB and ImageNet-1K using Top-1 Cls, GT Loc, and Top-1 Loc.
  • 4.2 Weakly Supervised Object Localization: On ImageNet-1K, TokenCut exceeds LOST by 5.4% on GT Loc and 4.4% on Top-1 Loc, while matching supervised-pretraining performance comparably.The authors attribute the supervised model’s ImageNet-1K advantage to dataset-tuned discriminative features.
  • 4.3 Unsupervised Saliency detection: TokenCut significantly outperforms prior methods for unsupervised saliency detection on ECSSD, DUTS, and DUT-OMRON, with Bilateral Solver further improving object boundaries.Figure 4 compares TokenCut, TokenCut + Bilateral Solver, and ground truth segments on ECSSD.
  • 4.4 Analysis and Discussion: TokenCut can fail by selecting the largest salient part, assuming a single foreground object, or failing under overlapping objects and occlusion.These limitations are illustrated as failure cases on VOC12 and COCO.

5 Conclusion

TokenCut uses self-supervised transformer features to construct a similarity graph whose patch nodes are separated with Normalized Cut. Across unsupervised object discovery, weakly supervised detection, and unsupervised saliency detection, it significantly improves over previous approaches.

  • TokenCut constructs a graph with patch nodes and similarity-based edges, then uses Normalized Cut to delimit salient objects.The approach uses self-supervised transformer features.
  • The method was evaluated on unsupervised single object discovery, weakly supervised object detection, and unsupervised saliency detection.
  • Self-supervised transformers provide a rich and general feature set that may support a variety of computer vision problems.

A Analysis of backbones.

Backbone ablations compare transformer architectures and patch sizes for unsupervised discovery and weakly supervised localization. MoCoV3 is slightly worse than DINO, while TokenCut is more robust across localization datasets and backbones than LOST.

  • Analysis of backbones: MoCoV3 performs slightly worse than TokenCut with DINO in the backbone ablation.The comparison concerns self-supervised transformer backbones.
  • Analysis of backbones: Table 5 reports CorLoc for unsupervised single object discovery on VOC07, VOC12, and COCO20K.
  • Analysis of backbones: TokenCut provides more robust performance across weakly supervised localization datasets and different backbones.
  • Analysis of backbones: LOST with ViT-S/8 performs much worse because its seed expansion relies on the top-100 lowest-degree patches and may not cover entire objects when patch counts are large.
  • Analysis of backbones: Table 6 reports Top-1 Cls, GT Loc, and Top-1 Loc on CUB and ImageNet-1K for weakly supervised object localization.

B Analysis of bi-partition strategies.

The study compares mean-value, Expectation-Maximisation, and K-means strategies for separating graph nodes using the second smallest eigenvector, reporting CorLoc for unsupervised object discovery.

  • Analysis of bi-partition strategies: Three bipartition strategies—Mean, Expectation-Maximisation, and K-means—are evaluated using the second smallest eigenvector.EM and K-means are implemented with scikit-learn.
  • Analysis of bi-partition strategies: The bipartition ablation reports CorLoc for unsupervised single object discovery.

C Analysis of Graph edge weight

The edge-weight ablation tests similarity-based graph weights for Normalized Cut. Direct similarity weights are invalid when negative values violate the algorithm's assumptions, while thresholding produces reported CorLoc results.

  • Analysis of Graph edge weight: Directly using similarity scores as edge weights is invalid because negative edges violate the Normalized Cut assumption.
  • Analysis of Graph edge weight: 68.9% CorLoc on VOC07 and 72% CorLoc on VOC12 are obtained with thresholded similarity scores.Thresholding retains similarities above τ and assigns ϵ otherwise.

D Visual results for unsupervised single object discovery on VOC07 and COCO12

TokenCut visualizations compare DINO, LOST, and TokenCut attention maps with predicted boxes on VOC07 and COCO12. The second-smallest eigenvector yields better object segmentation than the comparison methods.

  • Visual comparisons: TokenCut’s second-smallest eigenvector is compared with DINO CLS-token attention and LOST inverse-degree maps.The comparisons include both attention maps and bounding-box predictions.
  • Visual comparisons: TokenCut provides clearly better segmentation of the object across the compared datasets.
  • Attention maps: The TokenCut attention map is the second-smallest eigenvector of Equation 2, while LOST uses inverse node degrees for detection.

F Visual results for weakly supervised object localizatio on CUB and Imagenet-1k

TokenCut visual results on CUB and ImageNet-1K compare its eigenvector-based detections with LOST. The reported failure cases involve object selection, connected objects, and occlusion.

  • Visual comparisons: CUB and ImageNet-1K visualizations compare LOST and TokenCut attention maps with their predicted bounding boxes.
  • Visual comparisons: TokenCut’s eigenvector provides better object segmentation and leads to better detection results than LOST.
  • Failure cases: TokenCut may focus on the largest salient object when the annotation identifies a different object.
  • Failure cases: TokenCut, like LOST, cannot differentiate connected objects.
  • Failure cases: Under occlusion, neither LOST nor TokenCut can detect the entire object.

I Visual results for unsupervised saliency detecion on ECSSD, DUTS and DUT-OMRON

TokenCut visual results on ECSSD, DUTS, and DUT-OMRON compare its segmentation with LOST-based alternatives. TokenCut provides better object segmentation, with further improvement from a Bilateral Solver.

  • Datasets: The visual results cover unsupervised saliency detection on ECSSD, DUTS, and DUT-OMRON.
  • Visual comparisons: TokenCut provides better object segmentation than LOST and LOST combined with a Bilateral Solver across the three datasets.
  • Visual comparisons: A Bilateral Solver further improves TokenCut’s segmentation performance.
  • Visual comparisons: The comparisons include LOST segmentation, LOST plus Bilateral Solver, and the proposed approach.
Loading 2202.11539v2…