Yangtao Wang

Xi Shen

Shell Xu Hu

Yuan Yuan

James L Crowley

Dominique Vaufreydaz

SELF-SUPERVISED TRANSFORMERS FOR UNSUPERVISED OBJECT DISCOVERY USING NORMALIZED CUT AUTHOR VERSION OF CVPR22 PAPER

Transformers trained with self-supervision using selfdistillation loss (DINO) have been shown to produce attention maps that highlight salient foreground objects. In this paper, we show a graph-based method 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 graphcut to group self-similar regions. We solve the graph-cut problem using spectral clustering with generalized eigendecomposition 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 state-of-the-art. For weakly supervised object detection, we achieve competitive performance on CUB and ImageNet.

Introduction

Object detection is a key enabling technology for realworld vision systems for tasks such as robotics, autonomous driving, traffic monitoring, manufacturing, and embodied artificial intelligence [START_REF] Geiger | Vision meets robotics: The kitti dataset[END_REF][START_REF] Wu | Squeezedet: Unified, small, low power fully convolutional neural networks for real-time object detection for autonomous driving[END_REF][START_REF] Xia | Dota: A large-scale dataset for object detection in aerial images[END_REF]. However, * Corresponding Author (a) DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] (b) LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF].

(c) TokenCut (ours) (d) Attention maps associated to different patches Figure 1: The attention map of the class token used in DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] (a) and the map of the inverse degrees used in LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] (b) are noisy for foreground / background separation. Our proposed method provides a clean attention map that can be used to segment salient objects (c). Considering the attention map associated to different patches highlight different regions of the object (d), it is reasonable to build a graph computing attention maps from multiple patches.

the performance of current state-of-the-art object detectors is limited by the high cost of annotating sufficient training data [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] for supervised learning. This limitation becomes even more apparent when using transfer learning to adapt a pre-trained object detector to a new application domain. Approaches such as active learning [START_REF] Hamed H Aghdam | Active learning for deep detection neural networks[END_REF], semisupervised learning [START_REF] Liu | Unbiased teacher for semi-supervised object detection[END_REF], and weakly-supervised learning [START_REF] Ren | Instance-aware, context-focused, and memoryefficient weakly supervised object detection[END_REF] have attempted to overcome this barrier by providing more efficient learning, but with only limited success.

In this work, we focus on object discovery in natural images with no human annotations. This is an important problem and a critical step for many downstream applications [START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF]. Poor object discovery can lead to poor overall system performance. Current approaches for this problem adopt some forms of bounding box proposal mechanism [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Huy | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF][START_REF] Wei | Unsupervised object discovery and co-localization by deep descriptor transformation[END_REF] and formulate object discovery as an optimization problem. However, this approach can be computationally expensive [START_REF] Huy | Unsupervised image matching and object discovery as optimization[END_REF] as each pair of bounding box proposals across different images needs to be compared, and the optimization may fail to scale to larger datasets due to the quadratic computation overhead [START_REF] Huy | Large-scale unsupervised object discovery[END_REF].

Transformers have recently been shown to outperform convolutional neural networks for visual recognition. Vision Transformers, such as ViT [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] accept image patches as input tokens and use stacked layers of encoders with self-attention to map tokens to image-level class labels.

Recent results with DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] have shown that when trained with self-distillation loss [START_REF] Hinton | Distilling the knowledge in a neural network[END_REF], the attention maps associated to the class token from the last layer indicate salient foreground regions. However, as illustrated in Fig. 1a, such attention maps are noisy and it is not clear that they can be used for unsupervised object discovery.

With LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF], the authors propose construction of a graph and use the inverse degrees of nodes to segment objects. A heuristic seed expansion strategy is used to overcome noise (Fig. 1b) and detect a single bounding box for a foreground object. The attention maps associated with different nodes often contain meaningful information, as illustrated in Fig. 1d. We have investigated whether it is possible to use the information in the entire graph by projecting the graph into a low dimensional subspace using eigendecomposition. We have discovered that such a projection can be used with Normalized Cut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] (Ncut) to significantly improve foreground / background segmentation (Fig. 1c).

In this paper, we propose TokenCut, a simple but effective graph-based approach for unsupervised object discovery. We build on the self-supervised vision transformer trained with DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] as our backbone feature encoder and locate objects with the resulting features. Instead of using only the class token, we use all token features. We construct an undirected graph based on the token features in the last self-attention layer, where the visual tokens are viewed as graph nodes with edges representing a connectivity score based on similarity of the features. We then use a normalized graph-cut to group self-similar regions and delimit the foreground objects. We solve the graph-cut problem using spectral clustering with generalized eigendecomposition and show that the second smallest eigenvector provides a cutting solution indicating the likelihood that a token belongs to a foreground object. Our approach can be considered as a run-time adaptation, which means that the model is able to adapt to each specific test image despite the shared training model.

Despite its simplicity, our approach significantly improves unsupervised object discovery. The method achieves 68.8%, 72.1% and 58.8% on VOC07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF], VOC12 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF], COCO20K [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] respectively, thus outperforming LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] by a margin of 6.9%, 8.1% and 8.1% respectively. TokenCut with second stage CAD further improves the performance to 71.4%, 75.3% and 62.6% on VOC07, VOC12, COCO20k respectively, which outperforms LOST + CAD by 5.7%, 4.9% and 5.1% respectively.

In addition, we show that TokenCut can be easily extended to weakly supervised object detection and unsupervised saliency detection. For weakly supervised object detection, the goal is to detect objects using only image-level annotations. We freeze the encoder and fine-tune a linear classifier with weakly-supervised image labels. We then apply TokenCut on the features extracted from the finetuned encoder. Our approach produces clearly improved results on the CUB dataset [START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF] and competitive performance on ImageNet-1K [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]. For unsupervised saliency detection, we use the foreground region discovered by the proposed approach and apply Bilateral Solver [START_REF] Barron | The fast bilateral solver[END_REF] as a post-processing step to refine edges of the foreground region. In terms of results, our approach significantly improves previous state-of-the-art methods on ECSSD [START_REF] Shi | Hierarchical image saliency detection on extended cssd[END_REF], DUTS [START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF] and DUT-OMRON [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF].

In summary, our main contributions are as follows:

• We propose a simple and effective method to discover objects in images without supervision based on the selfsupervised vision transformers. This method significantly outperforms previous state-of-the-art methods for unsupervised object discovery when tested on multiple datasets; • We extend the proposed method to weakly-supervised object detection and show that the simple approach can achieve competitive performance; • We also show that this method can be used for unsupervised saliency detection. The results demonstrate that TokenCut significantly improves the previous state-ofthe-art performance on multiple datasets.

Related Work

Self-supervised vision transformers. ViT [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] has shown that a transformer architecture [START_REF] Vaswani | Attention is all you need[END_REF] can be used as an effective encoder for images and provide useful features for supervised vision tasks. MoCo-v3 [8] demonstrated that ViT can provide self-supervised representation learning and achieve strong results using contrastive learning. Recently, DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] proposed to train transformers with self-distillation loss [START_REF] Hinton | Distilling the knowledge in a neural network[END_REF], showing that ViT contains explicit information that can be used for semantic segmentation of an image. Inspired by BERT [START_REF] Devlin | Bert: Pre-training of deep bidirectional transformers for language understanding[END_REF], [START_REF] Li | Mst: Masked self-supervised transformer for visual representation[END_REF] proposed MST, which dynamically masks some tokens and learns to recover missing tokens using a global image decoder. Also motivated by BERT [START_REF] Devlin | Bert: Pre-training of deep bidirectional transformers for language understanding[END_REF], BEIT [START_REF] Bao | Beit: Bert pretraining of image transformers[END_REF] first tokenizes the original image into visual tokens then randomly mask some tokens and learn to recover them using a transformer. Recently, MAE [START_REF] He | Masked autoencoders are scalable vision learners[END_REF] masks a high propor-Figure 2: An overview of the TokenCut approach. We construct a graph where the nodes are tokens and the edges are similarities between the tokens using transformer features. The foreground and background segmentation can be solved by Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Performing bi-partition on the second smallest eigenvector allows to detect foreground object.

tion of images and reconstructs the missing pixels with an asymmetric encoder-decoder.

Unsupervised object discovery. Given a group of images, unsupervised object discovery seeks to discover and delimit similar objects that appear in multiple images. Some methods [START_REF] Chen | Show, match and segment: Joint weakly supervised learning of semantic matching and object cosegmentation[END_REF][START_REF] Hsu | Coattention cnns for unsupervised object co-segmentation[END_REF][START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF][START_REF] Joulin | Multi-class cosegmentation[END_REF][START_REF] Vicente | Object cosegmentation[END_REF] are designed to segment common repeated objects in an image collection, but rely on strong assumptions about the frequency of appearance of an object. Other approaches [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Tang | Colocalization in real-world images[END_REF][START_REF] Huy | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF] use bounding box proposals and formulate the object discovery as an optimization problem. [START_REF] Huy | Large-scale unsupervised object discovery[END_REF] proposed a novel formulation of unsupervised object discovery as a ranking problem and showed that discovery could be scaled to datasets with more than 10K images. Recently, LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] significantly improved over state-of-the-art for unsupervised object discovery. LOST extracts features using a selfsupervised transformer based on DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] and designs a heuristic seed expansion strategy to obtain a single object region. Our work is closely related to LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF], as we also use self-supervised transformer features. However, rather than relying on the attention map of some specific nodes, we propose a graph-based method that employs the attention scores of all the nodes and can be used with Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] to obtain a more precise segmentation of the image object.

Weakly supervised object detection. Weakly supervised object detection [START_REF] Guo | Strengthen learning tolerance for weakly supervised object localization[END_REF][START_REF] Yuan | Temporal dynamic graph lstm for action-driven video object detection[END_REF][START_REF] Yuan | Marginalized average attentional network for weakly-supervised learning[END_REF][START_REF] Zhang | Weakly supervised object localization and detection: a survey[END_REF] can be used to locate image objects using only image-level annotation.

Early approaches [START_REF] Chattopadhay | Grad-cam++: Generalized gradient-based visual explanations for deep convolutional networks[END_REF]41,[START_REF] Zhou | Learning deep features for discriminative localization[END_REF] mainly relied on a Class Activation Map (CAM) which is introduced in [START_REF] Zhou | Learning deep features for discriminative localization[END_REF] to generate class-specific localization maps and find discriminant regions. Several methods [START_REF] Choe | Evaluating weakly supervised object localization methods right[END_REF][START_REF] Choe | Attention-based dropout layer for weakly supervised object localization[END_REF][START_REF] Mai | Erasing integrated learning: A simple yet effective approach for weakly supervised object localization[END_REF][START_REF] Kumar | Hide-and-seek: Forcing a network to be meticulous for weakly-supervised object and action localization[END_REF][START_REF] Yuan | Marginalized average attentional network for weakly-supervised learning[END_REF][START_REF] Zhang | Adversarial complementary learning for weakly supervised object localization[END_REF] have been proposed to improve CAM by erasing the discriminant regions and forcing the networks to capture additional object regions. Data augmentation techniques such as Cutout [START_REF] Devries | Improved regularization of convolutional neural networks with cutout[END_REF] and CutMix [START_REF] Yun | Cutmix: Regularization strategy to train strong classifiers with localizable features[END_REF] have been shown to provide improvement for both classification and localization performance. Some methods achieve both classification and localization using two separate networks [START_REF] Guo | Strengthen learning tolerance for weakly supervised object localization[END_REF][START_REF] Lu | Geometry constrained weakly supervised object localization[END_REF][START_REF] Zhang | Rethinking the route towards weakly supervised object localization[END_REF]. [START_REF] Zhang | Rethinking the route towards weakly supervised object localization[END_REF] trained the localization network using pseudo bounding boxes generated by [START_REF] Wei | Unsupervised object discovery and co-localization by deep descriptor transformation[END_REF]. [START_REF] Zhang | Rethinking the route towards weakly supervised object localization[END_REF] first learns a classifier, then freeze its weights and train another detector. [START_REF] Guo | Strengthen learning tolerance for weakly supervised object localization[END_REF] learns a regressor and a classifier using the consistency of CAM between two transformations. Unlike these approaches, which are specifically designed for weakly supervised object detection, we propose an unified solution to both unsupervised object discovery and weakly supervised object detection based on transformer.

Unsupervised saliency detection. Unsupervised saliency detection seeks to segment a salient objects within an image. Earlier work on this problem [START_REF] Jiang | Salient object detection: A discriminative regional feature integration approach[END_REF][START_REF] Li | A weighted sparse coding framework for saliency detection[END_REF][START_REF] Yan | Hierarchical saliency detection[END_REF][START_REF] Zhu | Saliency optimization from robust background detection[END_REF] used classical techniques such as color contrast [START_REF] Cheng | Global contrast based salient region detection[END_REF], certain background priors [START_REF] Wei | Geodesic saliency using background priors[END_REF], or super-pixels [START_REF] Li | A weighted sparse coding framework for saliency detection[END_REF][START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF]. More recently, unsupervised deep models [START_REF] Nguyen | Deepusps: Deep robust unsuper-vised saliency prediction via self-supervision[END_REF][START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF][START_REF] Zhang | Deep unsupervised saliency detection: A multiple noisy labeling perspective[END_REF] have incorporated heuristic saliency methods as pseudo ground truth to train deep CNN models. However, these methods rely on a CNN model pretrained with supervised training. [START_REF] Voynov | Object segmentation without labels with large-scale generative models[END_REF] has proposed an unsupervised Large-Scale GAN that does not make use of labels during training. In the following, we show that incorporating a simple post-processing step into our unsupervised object discovery can provide a strong baseline method for unsupervised saliency detection.

Approach: TokenCut

The TokenCut algorithm can be used to predict bounding boxes that locate a salient object in an image. Our approach, illustrated in Fig. 2, is based on a graph where the nodes are tokens and the edges are similarities between the tokens using features based on the latent variables of the transformer. In the following, we first briefly present vision transformers in Section 3.1.1 and Normalized Cut in Section 3.1.2. We then introduce our solution and the implementation details in Section 3.2.

Background

Vision Transformers

Given an image of size H × W , vision transformers (ViT) [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] take non-overlapping 2D image patches of resolutions K × K as inputs, with the number of patches N = HW/K 2 . Each patch is represented as a token, described by a vector of numerical features, referred to as an embedding. An extra learnable token, denoted as a class token CLS, is used to represent the aggregated information of the entire set of patches. This CLS token and the set of patch tokens are fed to a standard transformer network with a "pre-norm" layer normalization [START_REF] Lei Ba | Layer normalization[END_REF].

The vision transformer is composed of a multiple layers of encoders, each with feed-forward networks and multiple attention heads for self-attention, paralleled with skip connections. For the unsupervised object discovery task, we use a vision transformer trained with self-supervised learning using DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] and extract latent variables from the final layer as the input features for our proposed method.

Normalized Cut (Ncut)

Graph partitioning. Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] can be used to partition a graph into two disjoint sets A and B. The method partitions the graph so as to minimizing the Ncut energy [START_REF] Shi | Normalized cuts and image segmentation[END_REF]:

N cut(A, B) = C(A, B) C(A, V) + C(A, B) C(B, V) (1)
where C measures the degree of similarity between two sets. C(A, B) = vi∈A,vj ∈B E i,j and C(A, V) is the total connection from nodes in A to all nodes in the graph.

As shown by Shi and Malik [START_REF] Shi | Normalized cuts and image segmentation[END_REF], the optimization problem in Eqn 1 is equivalent to:

min x N cut(x) = min y y T (D -E)y y T Dy . (2)
With the condition y ∈ {1, -b} N , b satisfies y T D1 = 0. D is a diagonal matrix with d i = j E i,j on its diagonal.

Ncut solution with the relaxed constraint. Taking z = D 1 2 y. Eqn 2 can be rewrite as:

min z z T D -1 2 (D -E)D -1 2 z z T z . (3)
Indicating in [START_REF] Shi | Normalized cuts and image segmentation[END_REF], the formulation in Eqn 3 is equivalent to the Rayleigh quotient [START_REF] Van Loan | Matrix computations[END_REF], which is equivalent to solve

D -1 2 (D -E)D -1 2 z = λz,
where D -E is the Laplacian matrix and known to be positive semidefinite [38]. Therefore z 0 = D 1 2 1 is an eigenvector associated to the smallest eigenvalue λ = 0. According to Rayleigh quotient [START_REF] Van Loan | Matrix computations[END_REF], the second smallest eigenvector z 1 is perpendicular to the smallest one (z 0 ) and can be used to minimize the energy in Eqn 3,

z 1 = argmin z T z0 z T D -1 2 (D -E)D -1 2 z z T z . Taking z = D 1 2 y, y 1 = argmin y T D1=0 y T (D -E)y y T Dy .
Thus, the second smallest eigenvector of the generalized eigensystem (D -E)y = λDy is the real valued solution to the Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] problem.

TokenCut Algorithm

Graph construction. Our method uses the vision transformers as described in Section 3.1.1 to produce a vector of features for each K×K image patch. A fully connected undirected graph G = (V, E) of patches is constructed where each V represents a patch with a feature vector {v i } N i=1 , and each patch is linked to adjacent patches by labeled edges, E. Edge labels represent a similarity score S based on the cosine similarity of the feature vectors of the two patches.

E i,j = 1, if S(v i , v j ) ≥ τ , else , (4)
where τ is a hyper-parameter and equals a small value 1e -5 to assure that the graph is fully connected and S is the cosine similarity between features. Note that the spatial information has been implicitly included in the features via positional encoding in transformer.

S(v i , v j ) = v i v j v i 2 v j 2 . (5)
We apply Ncut algorithm, as described in Section 3.1.2, on constructed graph G and obtain the second smallest eigenvector of the generalized eigensystem, which can be seen as an attention map of the potential objects. We provide visualization of this attention map in Section 4.

Discovering Salient Object with TokenCut. We assume that there is at least one object in the image and the object occupies the foreground region. To successfully segment the foreground objects from the image, we must solve three problems: i) We must determine a means to partition the graph into two subgraphs and ii) given a bipartition of the graph, we must determine which partition represents the foreground. iii) In case of detecting multiple connected components in the foreground, we must identify the most salient object.

For the first problem, in our initial experiments we have used a simple average value of the projection onto the second smallest eigenvector to determine the similarity value for cutting the graph

y 1 = 1 N i y i 1 . Formally, A = {v i |y i 1 ≤ y 1 } and B = {v i |y i 1 > y 1 }.
We have compared this to using the classical clustering algorithms of K-means and EM to cluster the second smallest eigen vector into 2 partitions. The comparison is available in the supplementary material Table 7, indicating that the mean generally provides better results.

For the second problem, the foreground contains the salient object and is assumed to be less connected to the [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] which is used for detection (b). LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] is mainly relied on the map of inverse degrees (c) to perform detection (d). For our approach, we illustrate the eigenvector in (e) and our detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively. entire graph. Intuitively, d i < d j if v i belongs to the foreground while v j is the background token. Therefore, the eigenvector of the foreground object should have a larger absolute value than the one of the background. We use the maximum absolute value v max to select the foreground partition and the most salient object. The partition that contains v max is taken as foreground. As our graph has no explicit spatial constraint, the foreground might contain more than one connected regions. We simply select the largest connected component existing in the foreground containing the maximum absolute value v max as our final object region.

In summary, the TokenCut algorithm consists of the following steps:

1. Given an image, build a graph G = (V, E) according to Equation 4 and 5.

2. Solve the generalized eigensystem (D -E)y = λDy for the eigenvector associated to the second smallest eigenvalue y 1 .

3. Compute bi-partition using the average over y 1 :

y 1 = i y i 1 N . A = {v i |y i 1 ≤ y 1 } and B = {v i |y i 1 > y 1 } 4.
Find the largest connected component associated to the maximum absolute value of y 1 .

Implementation details. For our experiments, we use the ViT-S/16 model [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] trained with self-distillation loss (DINO) [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] to extract features of patches. We employ the keys features of the last layer as the input features v. Ablations on different features as well as transformers trained with self-supervised learning are provided in the supplementary material Table 5. We set τ = 0.2 for all datasets, the dependency on τ is provided in Section 4.4. In terms of running time, our un-optimised implementation takes approximately 0.32 seconds to detect a bounding box of a single image with resolution 480 × 480 on a single GPU QUADRO RTX 8000.

Experiments

We evaluate our approach on three tasks: unsupervised single object discovery, weakly supervised object detection and unsupervised saliency detection. We present results of unsupervised single object discovery in Section 4.1. The results of weakly supervised object detection are in Section 4.2. The results of unsupervised saliency detection in Section 4.3. We provide analysis of τ in Sec-Table 1: Comparisons for unsupervised single object discovery. We compare TokenCut to state-of-the-art object discovery methods on VOC07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF], VOC12 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF] and COCO20K [START_REF] Lin | Microsoft coco: Common objects in context[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF] [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] ViT-S/16 [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] 65.7 70.4 57.5 TokenCut + CAD [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] ViT-S/16 [START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] 71.4 (↑ 5.7) 75.3 (↑ 4.9) 62.6 (↑ 5.1) +CAD indicates to train a second stage class-agnostic detector with "pseudo-boxes" labels. tion 4.4, other ablation studies will be presented in supplementary material.

Unsupervised Single Object Discovery

Evaluation metric. We report performance using the CorLoc metric for precise localisation, as used by [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Siva | Looking beyond the image: Unsupervised learning for object saliency and detection[END_REF][START_REF] Huy | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF][START_REF] Huy | Large-scale unsupervised object discovery[END_REF][START_REF] Wei | Unsupervised object discovery and co-localization by deep descriptor transformation[END_REF]. CorLoc counts a predicted bounding box as correct if the intersection over union (IoU) score between the predicted bounding box and one of the ground truth bounding boxes is superior to 0.5.

Quantitative Results. We evaluate our approach on three commonly used benchmarks for unsupervised single object discovery: VOC07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] , VOC12 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF] and COCO20K [START_REF] Lin | Microsoft coco: Common objects in context[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF]. The qualitative results are provided in Tab. 1. We evaluate the CorLoc scores in comparison with previous state-of-the-art single object discovery methods [START_REF] Kim | Unsupervised detection of regions of interest using iterative link analysis[END_REF][START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF][START_REF] Jasper Rr Uijlings | Selective search for object recognition[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF][START_REF] Huy | Large-scale unsupervised object discovery[END_REF][START_REF] Wei | Unsupervised object discovery and co-localization by deep descriptor transformation[END_REF][START_REF] Zhang | Object discovery from a single unlabeled image by mining frequent itemsets with multi-scale features[END_REF][START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF] on VOC07, VOC12, and COCO20K datasets. These methods can be roughly divided into two groups based on whether the model leverages information from the entire dataset and explores inter-image similarities or not. Because of quadratic complexity of region comparison among images, models with inter-image similarities are generally difficult to scale to larger datasets. The selective search [START_REF] Jasper Rr Uijlings | Selective search for object recognition[END_REF], edge boxes [START_REF] Zitnick | Edge boxes: Locating object proposals from edges[END_REF], LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] and TokenCut do not require inter-image similarities and are thus much more efficient. As shown in the table, TokenCut consistently outperforms all previous methods on all datasets by a large margin. Specifically, TokenCut improves the stateof-the-art by 6.9%, 8.1% and 8.1% in VOC07, VOC12 and COCO20K respectively using the same ViT-S/16 features.

We also list a set of results that including a second stage unsupervised training strategy to boost the performance, This is referred to as class-agnostic detection (CAD). A CAD is trained by assigning the same "foreground" category to all the boxes produced by the first stage single object discovery model. As shown in Tab. 1, TokenCut + CAD outperforms the state-of-the-art by 5.7%, 4.9% and 5.1% on VOC07, VOC12 and COCO20k respectively.

Qualitative Results. In Fig. 3, we provide visualization for DINO-seg [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] and Tokencut. For each method, we visualize the heatmap that is used to perform object detection. For DINO-seg, the heatmap is the attention map associated to the CLS token. For LOST, the detection is mainly based on the map of inverse degree ( 1 di ). For TokenCut, we display the second smallest eigenvector. The visual result demonstrates that Tokencut can extract a high quality segmentation of the salient object. Comparing with DINO-seg and LOST, TokenCut is able to extract a more complete segmentation as can be seen in the first and the third samples in Fig. 3. In some other cases, when all the methods have a high quality map, To-kenCut has the strongest intensity on the object, this phenomenon can be viewed in the last sample in Fig. 3. More visual results can be found in the supplementary material Fig. 7 and Fig. 8.

Weakly Supervised Object Localization

Evaluation metrics. We report three standard metrics: Top-1 Cls, GT Loc and Top-1 Loc. Top-1 Cls represents the top-1 accuracy of image classification. GT Loc is similar to CorLoc in which a predicted box is counted as correct if the IoU score is superior to 0.5 between the predicted bounding box and one of the ground-truth bounding boxes. Top-1 Loc is the most important metric as it uses ten crop augmentations to get final classification results. and ‡ learn a classifer and a detector separately.

Table 3: Comparisons for unsupervised saliency detection We compare TokenCut to state-of-the-art unsupervised saliency detection methods on ECSSD [START_REF] Shi | Hierarchical image saliency detection on extended cssd[END_REF], DUTS [START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF] and DUT-OMRON [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF]. TokenCut achieves better results comparing with other competitive approaches. considers measuring both the classification and the detection: a predicted bounding box is counted as a true positive if the class of the image is correctly predicted and the IoU is superior to 0.5 between the predicted bounding box and the ground-truth bounding box.

Results. We use two datasets to evaluate model performances on weakly supervised object localization: CUB-200-2011 [START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF] (CUB) and ImangeNet-1k [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF]. The finetuning details can be found in supplementary material. In Tab. 2, we compare TokenCut to the state-of-theart weakly-supervised object localization approaches on CUB and ImageNet-1K datasets. The methods can be divided to two groups: models initialized with ImageNet-1K supervised pre-training [START_REF] Bae | Rethinking class activation mapping for weakly supervised object localization[END_REF][START_REF] Choe | Attention-based dropout layer for weakly supervised object localization[END_REF][START_REF] Guo | Strengthen learning tolerance for weakly supervised object localization[END_REF][START_REF] Kumar | Hide-and-seek: Forcing a network to be meticulous for weakly-supervised object and action localization[END_REF][START_REF] Zhang | Rethinking the route towards weakly supervised object localization[END_REF][START_REF] Zhang | Inter-image communication for weakly supervised localization[END_REF][START_REF] Zhou | Learning deep features for discriminative localization[END_REF] and models inilialized with ImageNet-1K self-supervised pretraining [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF].

On the CUB dataset, TokenCut achieves the best performance over all methods, and outperforms the stateof-the-art LOST method by 2.1% and 1.6% on GT Loc and Top-1 Loc. Interestingly, all the ImageNet-1K selfsupervised pretraining models are better than the supervised pretrained models. We believe that this is because supervised pretraining learns a more discriminative representation of the pretrained dataset than self-supervised pretraining, leading to a reduction in transferability to downstream datasets such as CUB. In comparison, selfsupervised pretraining can learn a more general represenatation and thus provides better transferbility.

On the ImageNet-1K dataset, TokenCut outperforms LOST by 5.4% and 4.4% on GT Loc and Top-1 Loc, and achieves a comparable performance with the ImageNet-1K supervised pretrain model. If the downstream task is ImageNet-1K, then the supervised pretraining with ImageNet-1K can provide discriminative features that improve the localization task as they are tuned to the dataset. lowing previous works [START_REF] Shen | Learning co-segmentation by segment swapping for retrieval and discovery[END_REF][START_REF] Voynov | Object segmentation without labels with large-scale generative models[END_REF], we set β = 0.3 for consistency. IoU(Intersection over Union) score is computed based on the binary predicted mask and the ground-truth, the threshold is set to 0.5. Accuracy measures the proportion of pixels that have been correctly assigned to the object/background. The binarization threshold is set to 0.5 for masks.

Results

We further evaluate TokenCut on three commonly datasets for unsupervised saliency detection: EC-SSD [START_REF] Shi | Hierarchical image saliency detection on extended cssd[END_REF], DUTS [START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF] and DUT-OMRON [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF]. The qualitative results are in Tab. 3. TokenCut significantly outperforms previous state-of-the-art. Adding Bilateral Solver [START_REF] Barron | The fast bilateral solver[END_REF] refines the boundary of an object and further boosts the performance over TokenCut, which can also be seen from the visual results presented in Fig. 4.

Analysis and Discussion

Analysis of τ . In Tab. 4, we provide an analysis on τ defined in Equation 4. The results indicate that the effects of variations in τ value are not significant and that a suitable threshold is τ = 0.2.

Internet Images

We further test TokenCut on Internet images. The results are in Figure 5. We can see even the inputs images are with noisy background, our algorithm can still provide precise attention map cover the object leading to accurate bounding box prediction, which demonstrates again the robustness of our approach.

Limitations Despite the good performance of Token-Cut, it has several limitations. Examples of failure cases are shown in Fig. 6: i) TokenCut focuses on the largest salient part in the image, which may not be the desired object (Fig. 6, 1st row). ii) Similar to LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF], To-kenCut assumes that a single salient object occupies the foreground. If multiple overlapping objects are present in an image, both LOST and our approach will fail to detect one of the object (Fig. 6, 2nd row). iii) Neither LOST nor our approach can handle occlusion (Fig. 6, 3rd row).

Conclusion

We have introduced TokenCut, a simple but effective approach for unsupervised object discovery. TokenCut uses self-supervised learning with transformers to constructs a graph where nodes are patches and edges represent similarities between patches. We showed that salient objects can be directly detected and delimited using Ncut. We evaluated this approach on unsupervised single object discovery, weakly supervised object detection and unsupervised saliency detection, and showed that it provides a significant improvement over previous approaches. Our results indicate that self-supervised transformers can provide a rich and general set of features that may likely be used for a variety of computer vision problems.

C Analysis of Graph edge weight

In this section, we provide an ablation study on graph edge weight defininig on equation 4. We have tested to directly use the similarity score as edge weights (i.e., Eij = S(xi, xj))). However, it is not possible because there may exist negative edge values, which violates the Normalized Cut algorithm assumption. Thus, we also tried thresholding the similarity score (i.e., Eij = S(xi, xj) if S(xi, xj) > τ , else ). We obtain 68.9% on VOC07 dataset and 72% on VOC12 dataset, which is similar to our reported results.

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

We show visual results for unsupervised single object discovery on VOC07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] and COCO12 [START_REF] Lin | Microsoft coco: Common objects in context[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF], which are illustrated in Fig. 7 and Fig. 8 respectively.

For each dataset, we compare both attention maps and bounding box predictions among DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF], LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] and TokenCut. The attention map for DINO is extracted from the CLS token map of the last layer of key features. The attention map for LOST is the inverse degree map used in LOST for detection. The TokenCut attention map is the second smallest eigenvector of Equation 2. These results show that TokenCut provides clearly better segmentation of the object. [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] In (a), we show the attention of the CLS token in DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] which is used for detection (b). LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] is mainly relied on the map of inverse degrees (c) to perform detection (d). For our approach, we illustrate the eigenvector in (e) and our detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively. [START_REF] Lin | Microsoft coco: Common objects in context[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF]. In (a), we show the attention of the CLS token in DINO [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] used for detection (b). LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] mainly relies on the map of inverse degrees (c) to perform detection (d). For TokenCut, we illustrate the eigenvector in (e) and the detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively.

E Fine-tuning self-supervised transformers

For weakly supervised object localization, we use a pre-trained DINO model as our backbone and learn a linear classifier on the training set where we only have access to the class labels. We freeze the backbone weights and fine-tune a linear classifier, as shown in Tab. 2. For CUB, We train with a SGD optimizer for 1000 epochs and set the batch size to 256 per GPU, distributed over 4 GPUs. The learning rate is linearly warmed during the first 50 epochs, then follows a cosine learning rate scheduler. We decay the learning rate from batch size 256 ×5e-4 to 1e-6. The weight decay is set to 0.005. For ImageNet-1K, we use the models released by DINO. Other training setups and details can be found in the supplementary material.

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

We present visual results for weakly supervised object localization on CUB [START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF] and Imagenet-1k [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF] in Fig. 9 and Fig. 10 respectively.

For each dataset, we compare the attention map and bounding box prediction with LOST [START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] and our approach. The eigenvector of TokenCut provides better segmentation on objects and leads to better detection results.

Figure 3 :

 3 Figure3: Visual results of unsupervised single object discovery on VOC12. In (a), we show the attention of the CLS token in DINO[START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] which is used for detection (b). LOST[START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] is mainly relied on the map of inverse degrees (c) to perform detection (d). For our approach, we illustrate the eigenvector in (e) and our detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively.

Figure 4 :

 4 Figure 4: Visual results of unsupervised segments on ECSSD [44]. In (a), we show the input image. TokenCut detection result is presented in (b). TokenCut + Bilateral Solver results is shown in (c). (d) is the ground truth.

Figure 5 :

 5 Figure 5: Visual results of images taken from the Internet. We show the input images, our eigen attention and final detection in (a) (b) (c) respectively.

Figure 6 :

 6 Figure6: Failure cases on VOC12 (1st and 2nd row) and COCO (3rd row). LOST[START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] mainly relies on the map of inverse degrees (a) to perform detection (b). For our approach, we illustrate the eigenvector in (c) and our detection in (d). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively.

Figure 7 :

 7 Figure 7: Visual results of unsupervised single object discovery on VOC07[START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] In (a), we show the attention of the CLS token in DINO[START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] which is used for detection (b). LOST[START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] is mainly relied on the map of inverse degrees (c) to perform detection (d). For our approach, we illustrate the eigenvector in (e) and our detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively.

Figure 8 :

 8 Figure8: Visual results of unsupervised single object discovery on COCO20K[START_REF] Lin | Microsoft coco: Common objects in context[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF]. In (a), we show the attention of the CLS token in DINO[START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF] used for detection (b). LOST[START_REF] Siméoni | Localizing objects with selfsupervised transformers and no labels[END_REF] mainly relies on the map of inverse degrees (c) to perform detection (d). For TokenCut, we illustrate the eigenvector in (e) and the detection in (f). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively.

Figure 9 :Figure 10 :

 910 Figure 9: Visual results for weakly supervised object localization on CUB [59]. In (a), we show the map of inverse degrees used to perform detection with LOST (b) [45]. For TokenCut, we illustrate the eigenvector in (c) used for detection in (d). Blue and Red bounding boxes indicate the ground-truth and the predicted bounding boxes respectively. (a) LOST Inverse Degree Attention

Figure 13 :Figure 14 :

 1314 Figure14: Visual results of unsupervised segments on DUT-OMRON[START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF]

  datasets. Model performances are evaluated with CorLoc metric. "Inter-image Simi." means the model leverages information from the entire dataset and explores inter-image similarities to localize objects.

	Method	Inter-image Simi. DINO [6] Feat. VOC07 [19] VOC12 [20] COCO20K [33, 56]
	Selective Search [45, 51]	-	18.8	20.9	16.0
	EdgeBoxes [45, 79]	-	31.1	31.6	28.8
	Kim et al. [30, 45]	-	43.9	46.4	35.1
	Zhange et al. [45, 74]	-	46.2	50.5	34.8
	DDT+ [45, 61]	-	50.2	53.1	38.2
	rOSD [45, 56]	-	54.5	55.3	48.5
	LOD [45, 57]	-	53.6	55.1	48.5
	DINO-seg [6, 45]	ViT-S/16 [18]	45.8	46.2	42.1
	LOST [45]	ViT-S/16 [18]	61.9	64.0	50.7
	TokenCut	ViT-S/16 [18]	68.8 (↑ 6.9)	72.1 (↑ 8.1)	58.8 (↑ 8.1)
	LOD + CAD [45]	-	56.3	61.6	52.7
	rOSD + CAD [45]	-	58.3	62.3	53.0
	LOST + CAD

Table 2 :

 2 Comparisons for weakly supervised object localization. We report Top-1 Cls, GT Loc and Top-1 Loc on CUB[START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF] and ImageNet-1K[START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF] datasets. Compared state-of-the-art methods are divided into two groups: with ImageNet-1K supervised pretraining and with ImageNet-1K self-supervised pretraining.

	Pretrained Dataset	Method	Backbone	CUB [59], Acc. (%) Top-1 Cls GT Loc Top-1 Loc	ImageNet-1K [14], Acc. (%) Top-1 Cls GT Loc Top-1 Loc
		CAM [77]	GoogLeNet [48]	73.8	-	41.1	65	-	43.6
		HaS-32 [46] + [3] GoogLeNet [48]	75.4	61.1	47.4	68.9	60.6	44.6
	ImageNet-1K [14] supervised pretrain	ADL [13] + [3] ADL [13] I2C [76]	ResNet50 [24] InceptionV3 [49] 74.6 75.0 InceptionV3 [49] -	77.6 -72.6	59.5 53.0 56	75.8 72.8 73.3	62.2 -68.5	49.4 48.7 53.1
		PSOL [71] ‡	InceptionV3 [49] -	-	65.5	-	65.2	54.8
		SLT-Net [22]	InceptionV3 [49] 76.4	86.5	66.1	78.1	67.6	55.7
	ImageNet-1K [14]	LOST [45]	ViT-S/16 [18]	79.5	89.7	71.3	77.0	60.0	49
	self-supervised pretrain	TokenCut	ViT-S/16 [18]	79.5	91.8 (↑ 2.1) 72.9 (↑ 1.6) 77.0	65.4 (↑ 5.4) 52.3 (↑ 3.3)

Table 4 :

 4 Analysis of τ . P recision+Recall , where the Precision and Recall are defined based on the binarized predicted mask and ground truth mask. The maxF β is the maximum value of 255 uniformly distributed binarization thresholds. Fol-

				We report CorLoc for un-
	supervised single object discovery on VOC07, VOC12,
	COCO20K, and Top-1 Loc for weakly supervised object
	detection on CUB and ImageNet-1K.
	τ	CorLoc VOC07 VOC12 COCO20K CUB ImageNet-1K Top-1 Loc
	0	67.4	71.3	56.1	73.0	53.8
	0.1	68.6	72.1	58.2	73.2	53.4
	0.2	68.8	72.1	58.8	72.9	52.3
	0.3	67.7	72.1	58.2	70.8	50.4
	4.3 Unsupervised Saliency detection
	Evaluation Metrics We report three standard metrics:
	F-measure, IoU and Accuracy. F-measure is a standard
	measure in saliency detection. It is computed as F β =
	(1+β 2 )P recision×Recall
	β 2

Acknowledgements This work has been partially supported by the MIAI Multidisciplinary AI Institute at the Univ.

Grenoble Alpes (MIAI@Grenoble Alpes -ANR-19-P3IA-0003), and by the EU H2020 ICT48 project Humane AI Net under contract EU #952026.

//www.m-psi

Author version of CVPR22 paper

A Analysis of backbones.

In Tab. 5, we provide an ablation study on different transformer backbones. The "-S" and "-B" are ViT small [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF][START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] and ViT base [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF][START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] architecture respectively. The "-16" and "-8" represents patch sizes 16 and 8 respectively. The "MocoV3" is another pre-trained self-supervised transformer model [8]. The τ value is set to 0.3 for MoCov3, while for Dino the best tau value is 0.2. We observe that although the result of MoCov3 is slightly worse than the results of TokenCut with Dino, MoCov3 still outperforms previous state-of-the-art, indicating that TokenCut can provide similar results when used with other self-supervised Transformer architectures. Besides, the results demonstrates that a patch size of 16 provides better results than a patch size of 8. Several insights can be found: i) TokenCut outperforms LOST for different backbones. ii) As LOST relies on a heuristic seeds expansion strategy, the performance varies significantly using different backbones. While our approach is more robust. We provide another an ablation study on different backbones for weakly supervised object localization. Results are shown in Tab. 6.

The "-S" and "-B" designate ViT small [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF][START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] and ViT base [START_REF] Caron | Emerging properties in self-supervised vision transformers[END_REF][START_REF] Dosovitskiy | An image is worth 16x16 words: Transformers for image recognition at scale[END_REF] architecture respectively. The "-16" and "-8" indicate patch sizes 16 and 8 respectively. For our approach, we report results with τ = 0.2, which is the same on all the datasets. Note that LOST with ViT-S/8 achieves much worse results, because the seed expansion strategy in LOST relies on the top-100 patches which are with lowest degrees. When the total number of patches is large, the proposed seed expansion strategy is not able to cover entire objects. While our approach provides more robust performance on different datasets across different backbones. + B Analysis of bi-partition strategies.

In Tab. 7, we study different strategies to separate the nodes in our graph into two groups using the second smallest eigenvector.

We consider three natural methods: mean value (Mean), Expectation-Maximisation (EM), K-means clustering (K-means). We use python sklearn library for EM and K-means algorithm implementation. For EM algorithm, we set number of iteration to 300 and each component has its own general covariance matrix. The convergence threshold is set to 1e-3. For K-means algorithm, we use "k-means++" for initialization. The maximum number of iterations is set to 300. The convergence threshold is set to 1e-4. The result suggests that the simple mean value as the splitting point performs well for most cases. We have also tried to search for the splitting point based on the best Ncut(A,B) value. Due to the quadratic complexity, this approach requires substantially more computations. Thus, we finally obsolete it. G Failure cases on CUB and Imagenet-1k

We illustrate additional failure cases in Fig. 11. Those failure cases can be organised into three categories: 1) Where TokenCut focus on the largest salient object, whereas the annotation is highlights a different object, shown in the first and the second column in Fig. 11. 2) Similar to LOST, Tokencut is not able to differentiate the connected objects, such as the third and the fourth column in Fig. 11. 3) In case of occlusion, neither LOST nor our approach can't detect the entire object, such as the last two columns in Fig. 11.

H Datasets

We present in this section the details of the datasets used in our experiments:

• VOC07 and VOC12 correspond to the training and validation set of PASCAL-VOC07 and PASCAL-VOC12. VOC07 and VOC12 contain 5 011 and 11 540 images respectively which belong to 20 categories. They are commonly evaluated for unsupervised object discovery [START_REF] Cho | Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals[END_REF][START_REF] Huy | Unsupervised image matching and object discovery as optimization[END_REF][START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF][START_REF] Huy | Large-scale unsupervised object discovery[END_REF][START_REF] Wei | Unsupervised object discovery and co-localization by deep descriptor transformation[END_REF]]. • COCO20K consists of 19 817 randomly chosen images from the COCO2014 dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]. It is used as a benchmark in [START_REF] Huy | Toward unsupervised, multi-object discovery in large-scale image collections[END_REF] for a large scale evaluation. [START_REF] Xiao | Sun database: Large-scale scene recognition from abbey to zoo[END_REF]. Following the previous works [START_REF] Shen | Learning co-segmentation by segment swapping for retrieval and discovery[END_REF], we report the performance on the DUTS-test subset. • DUT-OMRON [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF] contains 5 168 images of high quality natural images for testing.

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

We present visual results for unsupervised saliency detecion on ECSSD [START_REF] Shi | Hierarchical image saliency detection on extended cssd[END_REF], DUTS [START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF] and DUT-OMRON [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF] in Fig. 12, 13 and 14 respectively.

Author version of CVPR22 paper

For each dataset, we compare LOST segmentation, LOST + Bilateral Solver and our approch. The TokenCut provides better segmentation on objects. The performance is further improved with Bilateral Solver. 12: Visual results of unsupervised segments on ECSSD [START_REF] Shi | Hierarchical image saliency detection on extended cssd[END_REF]