Bi-Directional Tracking Using Trajectory Segment Analysis

Jian Sun, Weiwei Zhang, Xiaoou Tang, Heung-Yeung Shum

Abstract

Visual tracking in complex environments remains a significant challenge for recursive algorithms, which often lose targets during extended occlusions or near visually similar distractors. This paper introduces a bi-directional tracking framework that utilizes information from both the start and end of a video sequence to reconstruct an object's trajectory. By extracting 2D modes and grouping them into 3D trajectory segments via spectral clustering, the proposed method performs global optimization to find the most likely path. Experimental results on challenging sequences demonstrate that this approach significantly outperforms traditional recursive filters, such as Particle Filters, in resolving ambiguity and maintaining track through long-duration occlusions.

Introduction: The Limitations of Recursive Tracking

Most visual tracking algorithms are recursive, estimating an object's position at time $t$ based solely on observations up to that point. While suitable for real-time applications, this approach is inherently "blind" to future information. If an object is hidden behind an obstacle for several seconds or passes near a nearly identical "distractor" object, a recursive tracker often loses the target and fails to recover.

In offline scenarios—such as video editing, surveillance analysis, or rotoscoping—researchers often have access to "keyframes" representing the starting and ending positions of the object. This paper addresses the challenge of finding the most likely path (the Maximum A Posterior or MAP solution) between these two known points, specifically focusing on handling sudden motion and long-duration occlusions.

Proposed Methodology

The authors propose a three-stage pipeline to solve the bi-directional tracking problem by treating it as a global optimization task rather than a step-by-step filtering problem.

  1. 2D Mode Extraction: Instead of searching the entire image, the system uses the Mean Shift algorithm to find "modes" (local maxima) in each frame where image content matches the object's color histogram. This creates a sparse set of candidate points in a 3D volume (x, y, time).
  2. 3D Trajectory Segment Extraction: To organize these points into meaningful paths, the authors employ Spectral Clustering. This groups 2D modes into short, coherent 3D trajectory segments. Unlike standard K-means, spectral clustering can identify complex, curved manifolds, which is essential for tracking non-linear motion.
  3. Occlusion Reasoning & Optimization: Because objects disappear during occlusions, trajectory segments are often disconnected. The system uses a bi-directional tree-growing algorithm to link segments and generates "occlusion segments" using weighted least-squares B-splines to bridge gaps. Finally, a discrete Hidden Markov Model (HMM) performs coarse-to-fine optimization to find the smoothest, most likely path.
The three-stage pipeline for bi-directional tracking.

Key Results and Insights

The bi-directional tracker was evaluated on several challenging video sequences, including the "Cup," "Leg," "Toy," and "Magic" datasets, each designed to highlight specific tracking failures.

Ambiguity Resolution

In the "Cup" sequence, two nearly identical green cups cross paths, creating high visual ambiguity. While both forward and backward Particle Filters were lured away by the distractor cup, the bi-directional tracker correctly maintained the target's identity by optimizing the path between the two keyframes.

The 'Cup' sequence showing 2D mode extraction for two identical targets.

Occlusion Handling and Efficiency

The system successfully bridged occlusions lasting dozens of frames (e.g., the "Leg" and "Toy" sequences) where recursive trackers typically drifted or stopped. Furthermore, the sparse segment-based representation makes the MAP solution computationally tractable; for a 10-second video, the final trajectory optimization stage took only approximately 8 seconds.

Conclusion and Future Work

By treating tracking as a global optimization problem and reasoning about segments of motion rather than individual points, this framework achieves high robustness to noise and ambiguity. The use of spectral clustering to identify motion manifolds is a key innovation that allows the system to handle non-linear movements effectively.

Future work will focus on automating the selection of the number of clusters ($K$) for spectral clustering, integrating more complex visual cues (such as edges or texture) into the observation model, and extending the framework to track multiple interacting objects simultaneously.

Summary updated

Abstract

In this paper, we present a novel approach to keyframe-based tracking, called bi-directional tracking. Given two object templates in the beginning and ending keyframes, the bi-directional tracker outputs the MAP (maximum a posterior) solution of the whole state sequence of the target object in the Bayesian framework. First, a number of 3D trajectory segments of the object are extracted from the input video, using a novel trajectory segment analysis. Second, these disconnected trajectory segments due to occlusion are linked by a number of inferred occlusion segments. Last, the MAP solution is obtained by trajectory optimization in a coarse-to-fine manner. Experimental results show the robustness of our approach with respect to sudden motion, ambiguity, and short and long periods of occlusion.
BibTeX
@inproceedings{sun2005bi,
  author = {Jian Sun and Weiwei Zhang and Xiaoou Tang and Heung-Yeung Shum},
  title = {{Bi-Directional Tracking Using Trajectory Segment Analysis}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2005},
  doi = {10.1109/iccv.2005.49},
}
Figure