Source-linked AI summary
TokenCut: Segmenting Objects in Images and Videos with Self-supervised Transformer and Normalized Cut
Yangtao Wang, Xi Shen, Yuan Yuan, Yuming Du, Maomao Li, Shell Xu Hu, James L Crowley, Dominique Vaufreydaz
TL;DR
TokenCut addresses unsupervised salient-object detection and segmentation without annotated training data. It builds a fully connected patch graph from self-supervised transformer features and solves segmentation with normalized cut. The method significantly improves unsupervised image saliency and object discovery while remaining competitive for unsupervised video segmentation.
Problem
Supervised object segmentation requires large, high-quality annotated datasets, motivating methods that can operate without human annotations.
Method
TokenCut represents image or video patches as graph nodes, uses self-supervised feature similarities as edges, and applies normalized cut to obtain foreground masks.
Results
TokenCut significantly improves unsupervised image saliency detection and object discovery, while achieving competitive results on unsupervised video segmentation.
Takeaways & Limitations
Self-supervised transformer features can support a unified, training-free approach across image object discovery, image saliency detection, and video object segmentation.
Takeaways & Limitations
TokenCut assumes a single salient foreground object and can fail with overlapping or occluded objects.
Abstract
from arXiv · showhide
In this paper, we describe a graph-based algorithm that uses the features obtained by a self-supervised transformer to detect and segment salient objects in images and videos. With this approach, the image patches that compose an image or video are organised into a fully connected graph, where the edge between each pair of patches is labeled with a similarity score between patches using features learned by the transformer. Detection and segmentation of salient objects is then formulated as a graph-cut problem and solved using the classical Normalized Cut algorithm. Despite the simplicity of this approach, it achieves state-of-the-art results on several common image and video detection and segmentation tasks. For unsupervised object discovery, this approach outperforms the competing approaches by a margin of 6.1%, 5.7%, and 2.6%, respectively, when tested with the VOC07, VOC12, and COCO20K datasets. For the unsupervised saliency detection task in images, this method improves the score for Intersection over Union (IoU) by 4.4%, 5.6% and 5.2%. When tested with the ECSSD, DUTS, and DUT-OMRON datasets, respectively, compared to current state-of-the-art techniques. This method also achieves competitive results for unsupervised video object segmentation tasks with the DAVIS, SegTV2, and FBMS datasets.
1 Introduction
TokenCut addresses annotation-intensive salient-object segmentation by using self-supervised transformer features in a unified graph-based pipeline for images and videos. It combines graph construction, normalized-cut segmentation, and optional edge refinement, achieving strong image results and competitive video performance.
- Motivation: Self-supervised transformer features provide semantic information, but their attention maps are noisy and cannot directly segment objects.This motivates converting patch relationships into a graph rather than using attention maps directly.
- Method: TokenCut constructs patch graphs from learned similarities, applies normalized cut, and refines boundaries with CRF or Bilateral Solver methods.The second smallest eigenvector supplies a foreground-likelihood partition for mask generation.
- Results: 4.4%, 5.6%, and 5.2% are TokenCut’s improvements in IoU over prior state of the art on ECSSD, DUTS, and DUT-OMRON, respectively.TokenCut achieves 77.7%, 62.8%, and 61.9% mIoU on those datasets, respectively.
- Results: 6.1%, 5.7%, and 2.6% are TokenCut’s margins over DSS on VOC07, VOC12, and COCO20K object discovery, respectively.The method also achieves competitive unsupervised video segmentation results on DAVIS, FBMS, and SegTV2.
- Motivation: TokenCut targets salient-object detection and segmentation without human annotations for training.The approach is intended for both images and videos, addressing the annotation costs of supervised methods.
2 Related Work
Related work establishes self-supervised transformers as useful sources of semantic features and surveys unsupervised discovery, saliency, and video-segmentation approaches. TokenCut differs by applying a fully connected token-similarity graph and classical normalized cut to object segmentation.
- Self-supervised vision transformers: Self-supervised ViT variants, including MoCo-V3 and DINO, learn image representations containing information useful for semantic segmentation.These methods motivate using transformer features without supervised annotation.
- Unsupervised object discovery: Unsupervised object discovery seeks recurring objects across images, using frequency hypotheses, bounding-box optimization, or ranking formulations.LOST and DSS are more recent approaches based on self-supervised transformer features and graph-like representations.
- Unsupervised object discovery: DSS combines a weighted patch graph with KNN-based image matting, while both DSS and LOST assume the foreground occupies a smaller region than the background.DSS is reported as less able to detect large objects.
- Unsupervised object discovery: TokenCut forms a fully connected graph over image tokens and labels edges with transformer-feature similarity before applying classical normalized cut.Unlike LOST, it does not rely on attention maps from selected nodes.
- Saliency and video segmentation: Unsupervised saliency detection segments a salient image object, whereas unsupervised video segmentation generates pixel-level masks for an object in unlabeled video.Prior methods use color contrast, background priors, super-pixels, motion fields, adversarial learning, or optical-flow reconstruction.
3 Approach: TokenCut
TokenCut represents visual patches as a similarity graph and applies Normalized Cut to segment salient image or video objects. Its pipeline constructs the graph, performs a spectral graph cut, and refines the resulting coarse mask.
- Graph Construction: TokenCut represents image or video patches as graph nodes and connects them with edges labeled by transformer-feature similarity.For videos, edge similarity combines RGB appearance and optical-flow representations.
- Graph Cut: Normalized Cut partitions the graph by computing the second smallest generalized-eigensystem eigenvector, which indicates foreground-token likelihood.The eigenvector supplies the spectral solution used to separate salient regions.
- Graph Cut: TokenCut cuts the graph using the eigenvector’s average value, and experiments found this threshold generally outperformed clustering alternatives such as K-means and EM.The method then selects the foreground partition using the maximum absolute eigenvector value.
- Graph Cut: For images, TokenCut selects the connected foreground component containing the maximum absolute eigenvector value; for videos, it retains the entire foreground region.This reflects the different object-selection targets for image and video segmentation.
- Edge Refinement: The graph cut produces coarse object masks because transformer patches are large, so TokenCut applies standard edge-aware refinement such as Bilateral Solver or CRF.These post-processing techniques refine boundaries after graph segmentation.
4 Experiments
TokenCut is evaluated on unsupervised object discovery, saliency detection, and video segmentation, with strong image results and competitive video performance across standard benchmarks. Experiments also examine efficiency, refinement, feature choices, and graph construction.
- Evaluation setup: TokenCut is evaluated on unsupervised single object discovery, saliency detection, and video segmentation across established image and video benchmarks.The experiments include VOC07, VOC12, COCO20K, ECSSD, DUTS, DUT-OMRON, DAVIS, FBMS, and SegTV2.
- Analysis: The graph construction has O(n^2) complexity for n tokens, so processing time grows quadratically with the number of video frames.The reported implementation takes about 0.32 seconds for a 480 × 480 image bounding box and about 30 seconds for coarse masks from 20 video frames.
- Unsupervised single object discovery: 6.1%, 5.7%, and 2.6% are TokenCut’s margins over DSS on VOC07, VOC12, and COCO20K, respectively, using the same ViT-S/16 features.The comparison uses CorLoc for single-object localization, with one predicted bounding box per image.
- Unsupervised single object discovery: TokenCut consistently outperforms previous single-object discovery methods on VOC07, VOC12, and COCO20K without requiring inter-image similarities.Methods using inter-image similarities are described as harder to scale because region comparisons have quadratic complexity across images.
- Unsupervised single object discovery: 5.7%, 4.9%, and 5.1% are TokenCut with CAD’s margins over the state of the art on VOC07, VOC12, and COCO20K, respectively.CAD adds a second unsupervised stage that clusters first-stage boxes into pseudo-labels and trains Faster R-CNN on them.
- Unsupervised video segmentation: TokenCut achieves competitive video-segmentation results on DAVIS, FBMS, and SegTV2 without training, while CRF further improves segmented-region boundaries.The method is reported to generalize across all three datasets and to segment moving objects under challenging occlusions.
- Analysis: RGB appearance and optical flow are complementary, but their combined effect depends on dataset quality and edge refinement.Using both representations improves performance before refinement but can be slightly worse after refinement than RGB alone; low-quality flow limits gains on FBMS and SegTV2.
5 Discussion
TokenCut can segment multiple salient or moving objects, but its performance is constrained by assumptions about saliency, foreground occupancy, overlap, and occlusion.
- Multi-Object Segmentation: TokenCut can identify multiple connected components when multiple objects appear or move in different directions.The paper illustrates this capability in image and video examples and describes it as robust.
- Limitations: TokenCut may focus on the largest salient part rather than the desired object.This is reported as a failure case on VOC12 and COCO.
- Limitations: TokenCut assumes a single salient object occupies the foreground, limiting performance when overlapping objects are present.The paper reports that overlapping objects can cause one object to be missed.
- Limitations: TokenCut cannot handle occlusion properly for object detection.The paper identifies occlusion as a failure case shared with LOST.
6 Conclusion
TokenCut is an unsupervised image and video segmentation approach that builds a patch-similarity graph from self-supervised transformer features and applies Normalized Cut. It provides improvements over previous approaches across unsupervised discovery and segmentation evaluations, while remaining competitive for video object segmentation.
- 6 Conclusion: TokenCut provides a unified approach for image and video object segmentation without supervised learning.The method uses self-supervised transformer features and incorporates optical flow for videos.
- 6 Conclusion: TokenCut constructs a graph whose nodes are image patches and whose edges represent feature-based similarities, then detects salient objects with Normalized Cut.For videos, optical flow is used to determine moving objects.
- 6 Conclusion: TokenCut improves over previous approaches on unsupervised object discovery and saliency detection while achieving competitive unsupervised video object segmentation results.The evaluated tasks include single object discovery, saliency detection, and video object segmentation.