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.
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.
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