Space-Time Correspondence as a Contrastive Random Walk

By Allan Jabri, Andrew Owens, Alexei A. Efros. 2020

348 citations recorded by the source corpus.

This paper proposes a simple self-supervised approach for learning representations for visual correspondence from raw video. We cast correspondence as link prediction in a space-time graph constructed from a video. In this graph, the nodes are patches sampled from each frame, and nodes adjacent in time can share a directed edge. We learn a node embedding in which pairwise similarity defines transition probabilities of a random walk. Prediction of long-range correspondence is efficiently computed as a walk along this graph. The embedding learns to guide the walk by placing high probability along paths of correspondence. Targets are formed without supervision, by cycle-consistency: we train the embedding to maximize the likelihood of returning to the initial node when walking along a graph constructed from a `palindrome' of frames. We demonstrate that the approach allows for learning representations from large unlabeled video. Despite its simplicity, the method outperforms the self-supervised state-of-the-art on a variety of label propagation tasks involving objects, semantic parts, and pose. Moreover, we show that self-supervised adaptation at test-time and edge dropout improve transfer for object-level correspondence.

Subfields: Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

Citations in the corpus

Emerging Properties in Self-Supervised Vision Transformers (2021, neutral): “[30] and segment scenes with a nearestSupervised”
How to Represent Part-Whole Hierarchies in a Neural Network (2021, background): “Recent work that uses the similarity of patches along a possible object trajectory to inﬂuence whether contrastive learning should try to make them more similar has shown very impressive performance at ﬁnding correspondences between patches in video sequences [Jabri et al., 2020].”
PointOdyssey: A Large-Scale Synthetic Dataset for Long-Term Point Tracking (2023, background): “There is also a long line of work which trains directly on unlabelled data, using a variety of auxiliary objectives to encourage tracking to emerge [65, 60, 62, 29, 7].”
SiT: Self-supervised vIsion Transformer (2021, methodology): “Specifically, the features of the data tokens of the DAVIS-2017 videos are extracted by passing the videos to the frozen pretrained SiT model and then follow the experimental protocol in [81] by segmenting the scenes with nearest neighbour between consecutive frames.”
Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers (2021, background): “[31] estimate correspondences in a similar way, framing the problem as a contrastive random walk on a graph and apply explicit guidance via a cycle consistency loss.”
CoTracker3: Simpler and Better Point Tracking by Pseudo-Labeling Real Videos (2025, positive): “Accounting for cycle consistency [13, 30, 41] or temporal continuity [9, 43] in videos is another way to obtain a reliable proxy signal to learn correspondences without full supervision, or even to learn generic visual features [10, 40].”
Putting NeRF on a Diet: Semantically Consistent Few-Shot View Synthesis (2021, methodology): “Contrastive methods including CLIP learn visual representations by matching similar pairs of items, such as captions and images [33, 21], augmentated variants of an image [5], or video patches across frames [18].”
R3M: A Universal Visual Representation for Robot Manipulation (2022, background): “Finally, there is a rich literature of works that study learning image representations from videos [58, 59, 19, 60, 61] outside of the context of robotics.”
Emergent Correspondence from Image Diffusion (2023, methodology): “To overcome difficulties in collecting a large number of image pairs with annotated correspondences, recent works have started looking into how to build visual correspondence models with weak supervision [87] or self-supervision [88, 39].”
Self-Supervised Pretraining of 3D Features on any Point-Cloud (2021, background): “More recently, selfsupervised pretraining has become a popular alternative to supervised pretraining especially for tasks where annotations are time-consuming, such as detection and segmentation in images [9, 36, 37, 56, 93] or tracking in videos [41].”
TAP-Vid: A Benchmark for Tracking Any Point in a Video (2022, neutral): “Although JHMDB is designed for human pose tracking [29], numerous prior works [26, 33, 35, 78, 81] use it as an evaluation for class-agnostic point tracking.”
Objaverse: A Universe of Annotated 3D Objects (2022, background): “…of animations available in O BJAVERSE can support a wide range of research in temporal 3D learning, such as building text-based animation generative models [71], representing object changes over time with NERFs [51,54], and temporal self-supervised learning via. future frame prediction [28,82].”
A Survey on Deep Learning Technique for Video Segmentation (2021, neutral): “01 AFB-URR [154] 74.6 73.0 76.1 3.8 FAVOS [126] 58.2 54.6 61.8 0.56 Fasttan [155] 75.9 72.3 79.4 y7 MAST [160] 65.5 63.3 67.6 5.1 STM-Cycle [166] 71.7 68.7 74.7 38 CRW [174] 67.6 64.5 70.6 7.3 QMA [167] 71.9 - - 6.3 RGMP [127] 66.7 64.8 68.6 7.7 Fasttmu [156] 70.6 69.1 72.1 9.7 OSMN [128] 54.8 52.5 ”
Learning Temporal Dynamics from Cycles in Narrated Video (2021, background): “[20], which casts temporal edges as contrastive comparisons (i.”
A Survey on Self-Supervised Learning: Algorithms, Applications, and Future Trends (2023, methodology): “Extensions of this work have been explored by Li et al. [225] and Jabri et al. [226].”
Conditional Object-Centric Learning from Video (2021, methodology): “, 2020) or CRW (Jabri et al., 2020) propagate the initial masks through the remainder of the video sequence.”
Masked Visual Pre-training for Motor Control (2022, methodology): “More recently, contrastive learning methods, e.g., (Hadsell et al., 2006; Oord et al., 2018; Wu et al., 2018; Henaff, 2020; He et al., 2020; Chen et al., 2020c; Jabri et al., 2020), have been popular.”