Multi-object tracking (MOT) systems frequently struggle with two fundamental challenges: error propagation and combinatorial explosion.
Traditional tracking-by-detection methods often operate online, making greedy, frame-by-frame associations. If an object is briefly occluded, or if a detector generates a noisy bounding box, an online tracker can easily misassign the target's identity. Because the system operates sequentially, this single mistake cascades forward, causing permanent identity switches. To avoid this, one could look globally across all frames simultaneously. However, comparing every single detection against every other detection across a long video creates a massive, quadratically scaling graph that quickly becomes computationally intractable.
Hierarchical tracklet association solves both problems by breaking the tracking process into a multi-tiered hierarchy. Instead of linking raw detections across an entire video all at once, the system first groups highly certain, consecutive detections into short-term segments called tracklets. These tracklets then serve as the fundamental building blocks for a global optimization layer that bridges long temporal gaps and occlusions.
[Raw Detections] ---> [Local Association] ---> [Short-Term Tracklets] ---> [Global Optimization] ---> [Final Trajectories]
(High Noise) (Low Ambiguity) (Rich Context) (Long-Term Gaps)
By shifting the primary unit of analysis from individual frames to extended temporal segments, hierarchical association linearizes the search space, pools visual context, and insulates the system against local tracking failures.
The Core Architecture: Local-to-Global Decomposition
The tracking problem is fundamentally easier to solve over short windows where object motion is highly predictable and appearance changes are minimal. Hierarchical tracking exploits this by dividing the optimization process into distinct temporal scales.
As Mei Chen and Takeo Kanade demonstrated in their early work on cell lineage construction, replacing greedy frame-by-frame decisions with a multi-stage approach that compiles local identities into intermediate segments allows systems to capture crucial short-term context before committing to a global trajectory (Cell Population Tracking and Lineage Construction with Spatiotemporal Context).
Modern frameworks formalize this into a multi-tiered pipeline:
- Low-Level (Tracklet Generation): Consecutive detections with high spatial overlap or clear motion consistency are fused into "safe" tracklets. Ambiguous associations—such as those occurring during cross-overs or occlusions—are intentionally left unresolved.
- Mid-to-High-Level (Global Merging): The generated tracklets are treated as discrete nodes in a graph. The system then uses long-range cues (like deep appearance features or global motion models) to link these tracklets across occlusions and frame boundaries.
Jingchen Liu et al. applied this multi-level hierarchy to sports tracking, showing that raw player detections could be grouped into short-term tracklets, optimized into mid-range trajectories, and finally resolved into full-game paths (Tracking Sports Players with Context-Conditioned Motion Models). Similarly, Ali Taalimi et al. leveraged a multi-tiered strategy to handle noisy detectors, resolving low-ambiguity local associations first to insulate the global optimizer from combinatorial challenges (Addressing Ambiguity in Multi-target Tracking by Hierarchical Strategy).
Why It Works: Taming Complexity and Noise
Understanding why hierarchical tracklet association outperforms flat, sequential tracking requires looking at three distinct mathematical and structural advantages.
1. Linearizing the Search Space
If a video contains $N$ detections, a global graph matching every detection to every other detection scales quadratically ($O(N^2)$). By grouping detections into tracklets, the number of graph nodes shrinks dramatically from $N$ detections to $M$ tracklets (where $M \ll N$).
Afshin Dehghan et al. utilized this reduction to make globally optimal tracking computationally feasible. By grouping unambiguous local detections into short-term tracklets first, they reduced the graph node count enough to solve tracking as a Generalized Maximum Multi Clique problem via a streamlined Mixed-Binary Integer Program (GMMCP tracker: Globally optimal Generalized Maximum Multi Clique problem for multiple object tracking).
To scale tracking to high-density scenes, Cheng-Yen Yang et al. introduced motion signatures for hierarchical clustering, explicitly reducing the computational complexity of merging fragmented tracks from quadratic to linear (MambaMOT: State-Space Model as Motion Predictor for Multi-Object Tracking).
2. Feature Aggregation and Context Pooling
A single bounding box provides a highly volatile appearance sample; lighting changes, motion blur, or poor crops can distort an object's visual signature. However, a tracklet contains a sequence of bounding boxes. This allows the system to pool information and extract a highly stable, aggregate representation of the target.
Anastasiia D. Sokolova et al. leveraged this in a detect-then-cluster pipeline for video surveillance, demonstrating that calculating the average feature vector of an entire tracklet sequence before applying L2-normalization yielded significantly more accurate global identity matching than frame-by-frame verification (Organizing Multimedia Data in Video Surveillance Systems Based on Face Verification with Convolutional Neural Networks).
3. Eliminating Sequential Error Propagation
Online trackers must make immediate decisions at every frame. If an object is misidentified at frame $t$, that error is baked into the track state for frame $t+1$. Hierarchical clustering flips this script by treating tracking as a retrospective, bottom-up grouping problem.
Andreu Girbau et al. showed that iteratively fusing tracklets based on global feature similarity across an entire sequence prevents the error propagation inherent in sequential tracking (Multiple Object Tracking from appearance by hierarchically clustering tracklets). Because the system evaluates similarity globally rather than locally in time, it remains robust even in low-frame-rate scenarios where motion models break down.
Advanced Optimization and Structural Extensions
The power of the tracklet abstraction is that it allows researchers to apply sophisticated optimization frameworks that would be impossibly heavy if applied directly to raw detections.
Structural and Graph Optimization
Instead of simple pairwise matching, tracklets can be composed using structural optimization. Yuanlu Xu developed a bottom-up framework that recursively merges individual detections into reliable tracklets before composing them into full 3D trajectories, allowing the system to adaptively stitch together appearance, motion, and geometry cues across multiple camera views (Multi-view People Tracking via Hierarchical Trajectory Composition).
To capture higher-order relationships beyond pairs of tracks, Longyin Wen et al. formulated data association as a dense neighborhood search on an undirected hierarchical relation hypergraph, allowing the system to resolve tracking ambiguities across multiple temporal scales simultaneously (Multiple Target Tracking Based on Undirected Hierarchical Relation Hypergraph).
[Raw Detections]
│
▼ (Local Data Association)
[Short Tracklets] ───► [Hypergraph / GCN Optimization] ───► [Robust Global Paths]
▲ (Multi-Scale Cues)
│
[Spatial/View Priors]
Other methods mirror modern deep learning architectures. For instance, Peng Dai et al. introduced a proposal-based tracking framework analogous to a two-stage object detector. Their method uses a dual-threshold graph clustering approach to generate candidate trajectory proposals from tracklets, which are then globally ranked and refined using a Graph Convolutional Network (GCN) (Learning a Proposal Classifier for Multiple Object Tracking).
Cross-View and Domain Priors
Hierarchical tracklet association also provides a natural interface for integrating domain-specific constraints. In multi-camera setups, Ruize Han et al. demonstrated that long video sequences could be broken into short clips to extract initial single-view tracklets based on spatial overlap, which were then linked via cross-view and temporal optimization to maintain identities through severe ground-level occlusions (Complementary-View Multiple Human Tracking).
In dense biological environments, Yu Song et al. utilized a coarse-to-fine framework that first links aggregate linear structures across frames before resolving individual cell nuclei, leveraging group-level motion stability to track visually identical objects (Accurate Tracking of Arabidopsis Root Cortex Cell Nuclei in 3D Time-Lapse Microscopy Images Based on Genetic Algorithm).
Extension to Unsupervised Segmentation and 4D Reconstruction
The utility of hierarchical association extends beyond bounding boxes to pixel-level tracking and 3D scene synthesis. Jonathon Luiten et al. developed the UnOVOST framework, which splits unsupervised video object segmentation into a two-stage hierarchy: first establishing short-term motion-based tracklets, and then performing long-term visual re-identification to bridge extended occlusions (UnOVOST: Unsupervised Offline Video Object Segmentation and Tracking).
This concept has even proven vital for 4D novel view synthesis from casual monocular videos. Colton Stearns et al. introduced a divide-and-conquer optimization strategy that processes short video subsequences independently before progressively merging them, simplifying the learning of complex long-term motion trajectories (Dynamic Gaussian Marbles for Novel View Synthesis of Casual Monocular Videos).
Similarly, Qisen Wang et al. organized monocular motion into a Temporal Partition Tree where finer sub-intervals inherit global motion properties from broader temporal windows, ensuring that local trajectory refinements remain structurally consistent with the global scene (WorldTree: Towards 4D Dynamic Worlds from Monocular Video using Tree-Chains).
Summary
By separating local tracking consistency from global trajectory optimization, hierarchical tracklet association provides a mathematically elegant solution to the core challenges of multi-object tracking. It transforms an intractable, noise-sensitive frame-by-frame matching problem into a robust, scalable, and globally coherent optimization framework.
Key Foundational Work
Tracking Sports Players with Context-Conditioned Motion Models (2013) — contributed 1 concept elements to this direction.
Cell Population Tracking and Lineage Construction with Spatiotemporal Context (2007) — contributed 1 concept elements to this direction.