Modelling Neighbor Relation in Joint Space-Time Graph for Video Correspondence Learning

Zixu Zhao, Yueming Jin, Pheng-Ann Heng

Introduction

Visual correspondence—the task of identifying and tracking specific points or objects across video frames—is a fundamental challenge in computer vision. While humans can easily distinguish between similar-looking objects by observing their surroundings or movement patterns, automated models often struggle. Traditional self-supervised methods frequently fail due to "narrow views," where local patches lack enough context to be unique, and "common-fate" ambiguity, where uniform background textures like grass or sky create indistinguishable matches.

The Joint Space-Time Graph Framework

Researchers from The Chinese University of Hong Kong have addressed these limitations by developing a self-supervised framework that learns to track by "seeing broader and longer." Their approach represents video patches as nodes in a Joint Space-Time Graph, which is decomposed into two complementary sub-graphs to capture both spatial context and temporal dynamics.

The Joint Space-Time Graph framework uses broader spatial context and longer temporal views to resolve correspondence ambiguities between similar objects.

Neighbor Relation Graph (Seeing Broader)

To overcome the ambiguity of isolated patches, the Neighbor Relation Graph explicitly links a central patch to its spatial neighbors (for example, connecting a "hand" patch to an "arm" patch). Using a Graph Attention mechanism, the model learns which neighbors provide the most discriminative context. This "broader" view allows the model to distinguish between two similar objects (like two dogs of the same breed) by looking at their unique surrounding structures.

Similarity Graph (Seeing Longer)

Temporal correspondence is handled by the Similarity Graph, which links patches across time. Rather than relying on simple frame-to-frame matching, the framework formulates correspondence as a Markov chain of transitions over multiple frames. This "longer" view enables the model to leverage long-term temporal dynamics, making it more robust to temporary occlusions or rapid motion.

Training via Attentive Walk and Node Dropout

The model is trained without manual labels using a principle called cycle-consistency. In a process termed "Attentive Walk," the model is fed a "palindrome" sequence of frames ($t \to t+k \to t$). It performs a random walk along the graph; if it can successfully navigate from a starting patch and return to that exact same position after the round trip, the learned representation is considered accurate.

To solve the "common-fate" problem, the authors introduced Node Dropout. By calculating a pixel discrepancy threshold, the model identifies and drops uninformative patches (like flat blue sky) during training. This forces the network to focus on learning features for discriminative "thing" nodes rather than noisy background "stuff."

Experimental Results

Despite the lack of manual supervision, the method achieved state-of-the-art results across several tracking benchmarks:

  • DAVIS 2017: Achieved a 68.7% J&Fm score, outperforming previous self-supervised methods like VideoWalk and even surpassing features trained on ImageNet labels.
  • Human Part Propagation (VIP): Reached 40.2 mIoU, notably exceeding the performance of the fully supervised ATEN model (37.9 mIoU).
  • Pose Tracking (JHMDB): Outperformed the ImageNet-supervised baseline by 10.7% in the [email protected] metric, proving that temporal cues from unlabeled video are often superior to static labels for tracking tasks.

Conclusion

By integrating spatial neighbor relations and long-term temporal consistency into a unified graph framework, this research demonstrates that self-supervised models can achieve high-fidelity tracking. While the model is highly effective at using context to resolve ambiguity, future work will explore incorporating explicit motion patterns and 3D depth information to further refine performance in scenes with nearly identical instances.

Summary updated

Abstract

This paper presents a self-supervised method for learning reliable visual correspondence from unlabeled videos. We formulate the correspondence as finding paths in a joint space-time graph, where nodes are grid patches sampled from frames, and are linked by two type of edges: (i) neighbor relations that determine the aggregation strength from intra-frame neighbors in space, and (ii) similarity relations that indicate the transition probability of inter-frame paths across time. Leveraging the cycle-consistency in videos, our contrastive learning objective discriminates dynamic objects from both their neighboring views and temporal views. Compared with prior works, our approach actively explores the neighbor relations of central instances to learn a latent association between center-neighbor pairs (e.g., "hand – arm") across time, thus improving the instance discrimination. Without fine-tuning, our learned representation outperforms the state-of-the-art self-supervised methods on a variety of visual tasks including video object propagation, part propagation, and pose keypoint tracking. Our self-supervised method also surpasses some fully supervised algorithms designed for the specific tasks.
BibTeX
@misc{zhao2021modelling,
  author = {Zixu Zhao and Yueming Jin and Pheng-Ann Heng},
  title = {{Modelling Neighbor Relation in Joint Space-Time Graph for Video Correspondence Learning}},
  year = {2021},
  eprint = {2109.13499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.13499},
}
Figure