SSTVOS: Sparse Spatiotemporal Transformers for Video Object Segmentation

Brendan Duke, Abdalla Ahmed, Christian Wolf, Parham Aarabi, Graham W. Taylor

Abstract

In this paper we introduce a Transformer-based approach to video object segmentation (VOS). To address compounding error and scalability issues of prior work, we propose a scalable, end-to-end method for VOS called Sparse Spatiotemporal Transformers (SST). SST extracts per-pixel representations for each object in a video using sparse attention over spatiotemporal features. Our attention-based formulation for VOS allows a model to learn to attend over a history of multiple frames and provides suitable inductive bias for performing correspondence-like computations necessary for solving motion segmentation. We demonstrate the effectiveness of attention-based over recurrent networks in the spatiotemporal domain. Our method achieves competitive results on YouTube-VOS and DAVIS 2017 with improved scalability and robustness to occlusions compared with the state of the art.

Introduction

Video Object Segmentation (VOS) requires tracking and segmenting objects with pixel-level precision throughout a video sequence. This task is complicated by appearance changes, long-term occlusions, and the presence of visually similar distractors. Traditional approaches have largely relied on online fine-tuning—which is computationally expensive and slow—or Recurrent Neural Networks (RNNs/LSTMs). While RNNs process frames sequentially, they suffer from compounding errors and a "Markovian" bottleneck that limits their ability to leverage long-range temporal dependencies.

Transformers offer a compelling alternative by allowing simultaneous attention across all input data. However, the $O(N^2)$ complexity of dense attention makes it computationally prohibitive for high-resolution video volumes. SSTVOS addresses this by introducing sparse attention mechanisms that maintain the benefits of global context while ensuring scalability.

Methodology

The SST Architecture

The SST architecture consists of a ResNet-101 backbone for feature extraction, followed by an SST Encoder and a Convolutional Decoder. The encoder is the heart of the system, designed to perform "correspondence-like" computations by matching features across a temporal history buffer.

The SST architecture uses a sparse spatiotemporal self-attention encoder to process video features and object affinities.

Sparse Spatiotemporal Attention

To overcome the quadratic complexity of dense attention, SST employs two novel sparse attention patterns:

  • Grid Attention: This pattern factorizes attention along the X, Y, and T (time) axes. A pixel only attends to others sharing its coordinates in one of these dimensions. By stacking multiple layers, information propagates throughout the entire spatiotemporal volume with significantly reduced complexity.
  • Strided Attention: This approach decomposes attention into local "cubes" and global "strided" hops, ensuring that any two pixels in the video can interact within just two steps.
Grid and Strided attention patterns reduce computational complexity while maintaining global connectivity.

Positional Encodings

Since Transformers are permutation-invariant, 3D sinusoidal positional encodings are added to the features. These encodings provide the model with essential spatial and temporal context, allowing it to distinguish between recent and distant frames and understand spatial proximity.

Experiments and Results

The model was evaluated on the YouTube-VOS (2018 & 2019) and DAVIS 2017 datasets.

Performance and Efficiency

SST achieved state-of-the-art results, with an overall score ($G$) of 81.8% on YouTube-VOS 2019 and a $J\&F$ score of 82.5% on DAVIS 2017. Crucially, the sparse attention mechanisms proved highly efficient. Compared to a naive dense attention implementation which causes a 66.6% slowdown relative to the backbone, SST's sparse variants reduced this overhead to approximately 2%.

Robustness to Occlusion

A key advantage of the attention-based approach is its robustness to occlusions. Unlike RNNs, which rely on a decaying hidden state, SST maintains a history buffer. This allows the model to "re-identify" objects after they emerge from behind obstacles, even after several seconds of total occlusion. Qualitative analysis in complex scenes, such as fish tanks with multiple identical-looking objects, demonstrates that SST effectively prevents identity swaps during overlaps.

Conclusion

SSTVOS demonstrates that sparse Transformers are a powerful and efficient alternative to recurrent networks for video object segmentation. By treating VOS as a matching problem across a temporal history, the model achieves high accuracy and robustness. Future work will focus on further reducing memory requirements through techniques like locality-sensitive hashing or reversible networks, potentially enabling the processing of even longer video sequences.

Summary updated

Abstract

In this paper we introduce a Transformer-based approach to video object segmentation (VOS). To address compounding error and scalability issues of prior work, we propose a scalable, end-to-end method for VOS called Sparse Spatiotemporal Transformers (SST). SST extracts per-pixel representations for each object in a video using sparse attention over spatiotemporal features. Our attention-based formulation for VOS allows a model to learn to attend over a history of multiple frames and provides suitable inductive bias for performing correspondence-like computations necessary for solving motion segmentation. We demonstrate the effectiveness of attention-based over recurrent networks in the spatiotemporal domain. Our method achieves competitive results on YouTube-VOS and DAVIS 2017 with improved scalability and robustness to occlusions compared with the state of the art. Code is available at https://github.com/dukebw/SSTVOS.
BibTeX
@inproceedings{duke2021sstvos,
  author = {Brendan Duke and Abdalla Ahmed and Christian Wolf and Parham Aarabi and Graham W. Taylor},
  title = {{SSTVOS: Sparse Spatiotemporal Transformers for Video Object Segmentation}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2021},
  url = {https://openreview.net/forum?id=_9Y0zuqtJc},
}
Figure