Source-linked AI summary
Space-Time Correspondence as a Contrastive Random Walk
Allan Jabri, Andrew Owens, Alexei A. Efros
TL;DR
Learning temporal correspondence from video is difficult because matching views are latent and existing approaches may rely on complex greedy tracking. The paper learns correspondence by training a similarity-based random walk on a space-time graph with cycle-consistency supervision. The resulting representation outperforms self-supervised methods across object, pose, and semantic-part propagation, while edge dropout and test-time adaptation further improve object-centric transfer.
Problem
Video correspondence is difficult to learn because matching views are latent, creating a chicken-and-egg problem for self-supervised training.
Method
The method learns a similarity-based random walk over a space-time graph of video patches, using a sequence-level cycle-consistency constraint to supervise intermediate comparisons.
Results
The learned representation outperforms self-supervised methods on video object segmentation, pose keypoint propagation, and semantic part propagation without adaptation.
Takeaways & Limitations
Edge dropout and self-supervised test-time adaptation further improve transfer for object-centric correspondence.
Takeaways & Limitations
Multi-hop alignment is challenging because spurious features can diffuse similarity across the graph, and intermediate soft-bijection heuristics may be undesirable.
Abstract
from arXiv · showhide
This paper proposes a simple self-supervised approach for learning a representation for visual correspondence from raw video. We cast correspondence as prediction of links in a space-time graph constructed from 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 representation in which pairwise similarity defines transition probability of a random walk, so that long-range correspondence is computed as a walk along the graph. We optimize the representation to place high probability along paths of similarity. Targets for learning are formed without supervision, by cycle-consistency: the objective is to maximize the likelihood of returning to the initial node when walking along a graph constructed from a palindrome of frames. Thus, a single path-level constraint implicitly supervises chains of intermediate comparisons. When used as a similarity metric without adaptation, the learned representation outperforms the self-supervised state-of-the-art on label propagation tasks involving objects, semantic parts, and pose. Moreover, we demonstrate that a technique we call edge dropout, as well as self-supervised adaptation at test-time, further improve transfer for object-centric correspondence.
1 Introduction
The paper addresses the difficulty of learning temporal correspondence from video, where spatially aligned points may not correspond across frames and matching views are latent. It proposes learning correspondence as random-walk pathfinding on a space-time graph, achieving strong transfer across correspondence tasks.
- Temporal correspondence is fundamental because motion and camera movement can make the same spatial position represent unrelated physical points across frames.
- Existing self-supervised methods work well when matching views are known, but video correspondences are latent and create a chicken-and-egg problem.
- The method represents video as a space-time graph whose patch nodes connect across neighboring frames with similarity-weighted edges.
- A learned representation defines transition probabilities for random walks, with path-level targets supervising chains of intermediate comparisons.
- Without adaptation, the representation outperforms self-supervised state-of-the-art methods on object segmentation, pose keypoint propagation, and semantic part propagation.Edge dropout and test-time adaptation further improve object segmentation.
2 Contrastive Random Walks on Video
The method represents video correspondence as random-walk pathfinding over a space-time graph, then learns the transition affinities through long-range and cycle-consistent supervision. Palindromic sequences provide targets without labels, while edge dropout encourages alternative correspondence paths.
- Space-Time Graph: Each video becomes a directed graph whose patch nodes connect across neighboring frames through similarity-based transition probabilities.The encoder maps patches to normalized embeddings, and local affinities compose into a block-sparse Markov chain over the video.
- Space-Time Graph: Long-range correspondence is computed by multiplying transition matrices across multiple time steps, treating tracking as a random walk guided by neighboring-node similarity.The walker’s transitions are defined by the learned representation, so multi-step paths connect patches across temporally distant frames.
- Self-Supervision: Supervision at a distant target implicitly trains intermediate comparisons by marginalizing over all paths linking the query and target.The resulting objective reinforces paths with high correspondence likelihood while contrasting adjacent alternatives.
- Self-Supervision: Palindromic frame sequences create known query-target pairs without human labels by concatenating a sequence with its temporal reversal.Each query node’s position in the first half serves as its target after the walk returns through the reversed sequence.
- Self-Supervision: The cycle-consistency objective backpropagates through many alternative similarity paths, extending contrastive supervision to arbitrarily long chains without explicitly inferring intermediate views.This sequence-level constraint avoids requiring separate latent-view assignments at every intermediate step.
- Edge Dropout: Edge dropout randomly obstructs graph paths and encourages probability mass to hedge toward alternative paths sharing the ideal path’s fate.The method applies dropout to transition affinities, renormalizes them, and reports improved object-centric correspondence.
3 Experiments
The experiments transfer the learned representation to object, pose, and semantic-part label propagation using simple similarity-based inference, and test training and adaptation variations. The method outperforms self-supervised alternatives across these correspondence tasks, while edge dropout and longer training paths improve DAVIS performance.
- Evaluation setup: The representation is evaluated on object, keypoint, and semantic-part label propagation, using k-nearest neighbors to isolate its effect.The evaluation includes DAVIS 2017, JHMDB, and VIP benchmarks.
- Video object segmentation: DAVIS 2017 evaluation reports boundary alignment F and region similarity J for semi-supervised multi-object segmentation.Comparisons use 480p images and the stated label-propagation algorithm, except for CorrFlow and MAST.
- Video object segmentation: The approach outperforms other self-supervised methods on DAVIS without localization modules or multi-stage training, despite using a lower-resolution feature map.It also compares favorably with several supervised dense-tracking approaches and outperforms MoCo and VINCE.
- Pose tracking: On JHMDB pose tracking, the model outperforms existing self-supervised approaches, including video colorization models optimized for fine-grained matching.The task tracks 15 keypoints; the authors attribute the result to hard negatives from the same image, while propagating keypoints independently.
- Model variations: Moderate edge dropout improves DAVIS object correspondence, while longer training sequences accelerate convergence and improve performance despite harder multi-hop tasks.Edge dropout simulates partial occlusion and encourages reliance on reliable context; longer paths benefit from soft-attention over multiple paths.
- Model variations: DAVIS downstream performance improves as more data is seen during self-supervised training, with less indication of saturation than Wang et al. [110].This comparison concerns the downstream task's performance as training data increases.
4 Related Work
Related work spans temporal correspondence, graph-based learning, and self-supervised visual representation learning. The paper distinguishes its soft-attention, cycle-consistent random-walk formulation from approaches using fixed coordinates, optical flow, hard tracking, or explicit grouping.
- Temporal correspondence: Early video methods used spatio-temporal volumes, while optical flow later supplied short-range correspondences between neighboring-frame patches.Implicit coordinate correspondence was most suitable when cameras were static.
- Graph neural networks and attention: Graph neural networks use learned message passing and soft-attention to propagate information according to local and global graph relations.The paper uses this graph perspective for correspondence learning rather than presenting a general graph architecture.
- Graph partitioning: Graph partitioning methods explicitly group image or video entities, whereas this work models groups implicitly to scale to real, large-scale video data.The paper identifies explicit entity estimation as a possible future direction.
- Graph representation learning: Graph representation learning commonly fits node embeddings using fixed or stochastic neighborhoods and randomly sampled negatives; this work uses graph matching for representation learning.Its cycle-consistency objective supervises a chain of matches without inferring correspondence between separate graphs.
- Self-supervised visual representation learning: Video self-supervision includes pretext tasks such as future prediction, arrow-of-time prediction, and motion estimation.The broader self-supervised literature often predicts one view or part of data from another.
- Self-supervised correspondence and cycle-consistency: Prior cycle-consistency methods track forward and backward with hard attention one path at a time, whereas this approach uses soft attention to consider many paths and handle ambiguity.The related work also discusses colorization, grouping, and orthogonality-based cycle-consistency objectives.
5 Discussion
The paper presents space-time graph walking as a self-supervised route to correspondence, using temporal changes as natural augmentation. Its path-level constraint also connects contrastive representation learning with unsupervised grouping.
- The method learns space-time correspondence from unlabeled video by learning to walk on a graph of image patches.
- A path-level constraint implicitly supervises a chain of contrastive learning problems across intermediate frames.
- The objective exploits how objects change and interact over time as natural data augmentation, complementing synthetic augmentation.
- The formulation connects self-supervised representation learning with unsupervised grouping.
6 Broader Impact
The paper identifies potential benefits of temporal correspondence for safety and monitoring applications, while acknowledging risks from unauthorized surveillance. The authors describe a policy limiting contracts and software authorization for authoritarian regimes.
- Potential applications include pedestrian safety, patient monitoring, animal monitoring, and 3D reconstruction.
- The authors commit not to contract with or authorize software use by government or quasi-governmental agencies in countries scoring 4.0 or below on the EIU Democracy Index.
B Comparison to Supervised Methods on DAVIS-VOS
On DAVIS 2017 video object segmentation, the proposed unsupervised representation is compared with state-of-the-art supervised methods. It outperforms many of them despite simple label propagation and no DAVIS training.
- The proposed method outperforms many supervised methods for video object segmentation on DAVIS 2017.
- The method achieves this comparison result using simple label propagation without object-segmentation training or training on DAVIS.
- The comparison uses an unsupervised method against state-of-the-art supervised approaches on the DAVIS 2017 validation set.
C Using a Single Feature Map for Training
Using a single convolutional feature map for training allowed the network to exploit shortcut solutions in dense correspondence. Several controls failed to eliminate this behavior, although random videos reduced its success.
- A single feature-map approach enabled the network to solve dense correspondence through a learned shortcut across long sequences.
- Removing padding, reducing receptive fields, blurring frames, and using random videos were tested to control shortcut learning.
- The network learned a shortcut under each control, while the shortcut was less successful on random videos.
D Frame-rate Ablation
The experiments examine training and label-propagation settings that affect performance, including frame rate, context, neighborhood selection, and search radius. Careful k-nearest-neighbor implementation improves the ImageNet baseline.
- Frame-rate Ablation: Spatio-temporal transformations are evaluated by varying the frame rate used to generate training sequences for downstream object segmentation.Infinite frame rate reuses the same image at each time step to separate spatial-jitter augmentation from video-based augmentation.
- Hyper-parameters: The reported training and test settings include edge dropout, video length, and 20 frames of context for DAVIS.The effective training path length is twice the video sequence length.
- Baselines: Baseline performance improves when label propagation is carefully implemented with k-nearest neighbors.This finding motivates comparing the proposed representation with strong, carefully implemented baselines.
- Label Propagation: +4% J&F improves the ImageNet baseline when source nodes are restricted by spatial locality.This local-attention choice is described as effective and reasonable for label propagation.
- Label Propagation: +3% J&F improves the ImageNet baseline when all source nodes are considered jointly before selecting the top-k.The method differs from independently selecting neighbors within each frame.
- Label Propagation: Label propagation performance depends on context length m, neighbor count k, and search radius r.The experiments examine added context, more neighbors, and radius using settings including k = 10, r = 12, and m = 20.
G Encoder Architecture
The encoder uses a modified ResNet-18 with higher-resolution convolutional features, and evaluation uses res3 embeddings for fair comparison with pretrained baselines. The architectural changes are documented in Table 4.
- Encoder Architecture: The model uses ResNet-18 with the last two residual blocks modified to preserve higher spatial resolution.Their convolutional strides change from 2 to 1, increasing output resolution by a factor of four and yielding a downsampling factor of 1/8.
- Encoder Architecture: Evaluation uses res3 features as node embeddings to compare fairly with ImageNet, MoCo, and VINCE baselines.The authors also report that res3 features compare favorably to res4 features.
- Encoder Architecture: Table 4 provides the detailed modified ResNet-18 architecture, with the paper’s changes highlighted in blue.
H Test-time Training Details
The test-time training procedure fine-tunes the model on a temporal frame window before propagating labels. Its implementation uses standard patch extraction and spatial-jitter utilities.
- Test-time Training: The model is fine-tuned every five timesteps for 100 Adam updates before label propagation.Fine-tuning uses learning rate 0.0001 and the same optimization hyper-parameters as training.
- Test-time Training: Test-time fine-tuning uses frames {I_t−m, ..., I_t, ..., I_t+m} with m = 10.The context value m = 10 was not tuned.
- Implementation: The implementation defines utility functions for test-time training and correspondence processing.
- Implementation: Images are converted into patch lists with PyTorch and Kornia augmentation libraries.
- Implementation: Patch extraction uses an unfold operation, while random resized cropping applies spatial jitter.The crop scale is 0.7–0.9 and the aspect-ratio range is 0.7–1.3.