Source-linked AI summary
Learning a Neural Solver for Multiple Object Tracking
Guillem Brasó, Laura Leal-Taixé
TL;DR
MOT learning has usually focused on better features followed by separate optimization for data association. This paper instead uses a fully differentiable message passing network over the network-flow graph to predict final associations, reporting significant improvements on three public benchmarks.
Problem
Learning-based MOT has largely improved features while using established optimization frameworks, because operating directly on the structured graph domain is difficult.
Method
A fully differentiable message passing network operates on the classical network-flow graph to learn features and directly predict binary edge solutions.
Results
The method achieves significantly improved state-of-the-art results on three public benchmarks.
Takeaways & Limitations
Learning in MOT can extend beyond feature extraction to the data association step by predicting final graph solutions.
Takeaways & Limitations
The presented network-flow formulation is simplified by omitting source and sink nodes and assuming detection-edge costs are constant and 1-valued.
Abstract
from arXiv · showhide
Graphs offer a natural way to formulate Multiple Object Tracking (MOT) within the tracking-by-detection paradigm. However, they also introduce a major challenge for learning methods, as defining a model that can operate on such \textit{structured domain} is not trivial. As a consequence, most learning-based work has been devoted to learning better features for MOT, and then using these with well-established optimization frameworks. In this work, we exploit the classical network flow formulation of MOT to define a fully differentiable framework based on Message Passing Networks (MPNs). By operating directly on the graph domain, our method can reason globally over an entire set of detections and predict final solutions. Hence, we show that learning in MOT does not need to be restricted to feature extraction, but it can also be applied to the data association step. We show a significant improvement in both MOTA and IDF1 on three publicly available benchmarks. Our code is available at https://bit.ly/motsolv .
1. Introduction
MOT remains challenging despite its importance, and prior learning-based methods largely improve features while relying on separate graph optimization for data association. This work introduces a unified message-passing solver that learns features and predicts graph partitions directly, achieving improved benchmark results.
- MOT determines trajectories for all object instances in video and supports applications including autonomous driving, biology, and surveillance.
- Tracking-by-detection separates frame-wise detection from data association, which is generally formulated as graph partitioning.
- Prior graph-based MOT methods either develop complex optimization frameworks with partly handcrafted costs or learn improved edge costs within simpler graphs.
- The proposed unified solver learns MOT features and final graph solutions by reasoning over the entire graph with a message passing network.
- A novel time-aware message-passing update is introduced for MOT.
- The method reports significantly improved state-of-the-art results on three public benchmarks.
2. Related Work
Related work models MOT association with graph optimization or integrates solvers into learning, but these approaches generally learn costs rather than directly learning the final solver with higher-order graph information.
- Tracking-by-detection detects objects independently per frame and links corresponding detections across time into trajectories.
- Graph-based data association can use maximum-flow or minimum-cost formulations with fixed, motion-based, or learned edge costs.
- Some prior methods incorporate optimization solvers into learning, but primarily optimize pairwise costs or additional quadratic terms.
- Unlike those approaches, this work directly learns a solver by treating data association as edge classification and leveraging higher-order graph information.
3. Tracking as a Graph Problem
The paper represents MOT as a graph whose detections are connected across frames and whose trajectories correspond to constrained active-edge paths. It then replaces conventional cost optimization with direct prediction of the binary edge solution.
- The method builds on the classical min-cost flow formulation to reformulate MOT data association as a learning problem.
- Input detections include bounding-box pixels, image coordinates, and timestamps, and the goal is to find trajectories explaining the observations.
- Figure 1 depicts a pipeline that constructs a detection graph, initializes node and edge embeddings, propagates messages, classifies edges, and rounds scores into trajectories.
- The graph connects every pair of detections from different frames, allowing trajectories to recover missed detections.
- Trajectory partitions are represented by binary edge variables that mark same-trajectory, temporally consecutive links as active.
- The formulation assumes node-disjoint trajectories and enforces that each node links to at most one past and one future node through simplified flow constraints.
- The conventional approach assigns edge costs and optimizes a constrained binary partition, solvable with available polynomial-time solvers.
- The proposed alternative directly predicts active edges as a classification task, making the MOT problem fully learnable.
4. Learning to Track with Message Passing Networks
The paper presents a differentiable MOT solver that operates directly on detection graphs, using message passing to learn features and predict trajectory partitions. Its time-aware updates separate past and future information, while final edge predictions are rounded into trajectories.
- Graph-based solver: The model predicts binary flow variables for every graph edge, directly producing active or inactive trajectory connections.This replaces the conventional separation between learned edge costs and a subsequent optimization solver.
- Graph-based solver: Message passing propagates appearance and geometry information between nodes and edges, producing embeddings that depend on the overall graph structure.After repeated updates, node embeddings incorporate information from increasingly distant parts of the graph.
- Time-aware message passing: The proposed MPN encodes MOT temporal structure by aggregating embeddings from past and future neighboring frames separately before combining them.This design is intended to reflect flow constraints that permit connections to at most one past and one future node.
- Time-aware message passing: The time-aware update yields a significant performance improvement over the vanilla node update in experiments.The comparison is reported in the discussion of Figure 2 and Section 5.2.
- Feature encoding: Initial node embeddings can come from backpropagatable networks, including a CNN that extracts appearance features from detection image patches.Geometry and relative appearance features are also used to initialize edge embeddings.
5. Experiments
Experiments evaluate the model through ablations and benchmark comparisons, showing benefits from time-aware message passing, feature combinations, and global graph reasoning.
- Ablation study: Time-aware updates improve nearly all metrics over a tuned vanilla baseline, including nearly 3 IDF1 points and constraint satisfaction of 98.8% versus 82.1%.The improvement is attributed to neighboring information and graph structure producing more robust linking decisions and fewer identity switches.
- Ablation study: Relative position is the key edge-feature component, while CNN features reduce false positives and identity switches in the final configuration.The compared feature groups are time difference, relative position, and Euclidean distance between CNN embeddings.
- Benchmark evaluation: The method achieves state-of-the-art results on MOT15, MOT16, and MOT17, improving IDF1 by 11, 6.4, and 6.6 percentage points, respectively.The paper attributes the gains to higher-order information and globally informed trajectory-linking predictions; Mostly Tracked trajectories increase by up to 9 percentage points.
- Benchmark evaluation: Compared with previous graph-partitioning methods, the learned solver is more accurate and up to one order of magnitude faster than some methods.The cited example is method, and graph-partitioning approaches are described as using expensive optimization schemes.
6. Conclusion
The conclusion presents MOT as a fully learnable tracking problem by jointly learning feature extraction and data association with a time-aware message passing network. Experiments show clear improvement over previous state-of-the-art, motivating learning beyond feature extraction.
- 6. Conclusion: The method treats the entire MOT tracking problem as a learning task using the min-cost flow formulation.Its pipeline is fully differentiable and jointly learns feature extraction and data association.
- 6. Conclusion: A message passing network with a novel time-aware update captures MOT’s graph structure.The update is the core algorithmic component described in the conclusion.
- 6. Conclusion: Experiments show clear performance improvement over previous state-of-the-art methods.The conclusion frames this as evidence for integrating learning into the overall data association task.
Supplementary Material
The supplementary material explains a simplified min-cost flow graph that focuses on association edges while assuming detections are correct after preprocessing and post-processing.
- Graph formulation: The method represents detections as nodes, possible trajectory links as edges, and assigns binary variables only to association edges.A binary edge variable indicates whether a link between two detections is active.
- Simplification: Unlike the classical formulation, the method removes detection edges and their true-positive variables by assuming detections are correct.False positives can be filtered during preprocessing and post-processing.
- Simplification: The method also eliminates source and sink nodes, representing trajectory starts and ends through absent active incoming or outgoing edges.The classical formulation uses special variables for whether trajectories start or end at detections.
- Consequences: The resulting formulation isolates association edges, allowing the message passing network to focus on edge classification and learn the tracking task.The simplification decouples data association from incorrect-detection identification.
B. Rounding Solutions
The rounding procedure converts fractional or thresholded edge predictions into binary feasible trajectories by resolving local flow-conservation violations.
- Rounding procedure: A forward pass produces fractional edge values between 0 and 1, and thresholding at 0.5 satisfies close to 99% of flow-conservation constraints on average.The remaining violations require a rounding scheme to guarantee feasibility.
- Constraint violations: Violations occur when a node has more than one active incoming or outgoing edge after thresholding.The constraints require at most one link to a past-frame node and at most one link to an upcoming-frame node.
- Greedy rounding: Greedy rounding keeps the incoming or outgoing edge with the maximum classification score whenever a flow-conservation constraint is violated.All other conflicting edges are set inactive for that node.
- Toy example: The toy example thresholds predictions, extracts the subgraph containing four violated constraints, rounds that subgraph, and combines the corrected edges with the thresholded solution.The final graph no longer contains the illustrated constraint violations.
B.2. Exact Rounding
Exact rounding converts the network’s fractional edge outputs into binary solutions satisfying MOT flow constraints. Because the constraint matrix is totally unimodular, this can be solved as a polynomial-time linear program, while greedy rounding is usually sufficient in practice.
- Rounding schemes: Greedy rounding usually changes little because the network outputs already satisfy almost all constraints.It is not guaranteed to be optimal in general, so exact linear-program rounding remains available.
- Exact rounding: The exact rounding problem finds the closest binary, constraint-satisfying edge vector to the network’s fractional output.The constraints enforce the MOT flow conditions across all nodes, and closeness is measured by squared Euclidean distance.
- Exact rounding: Total unimodularity allows the integrality constraints to be relaxed to box constraints while preserving integer solutions.This converts the quadratic integer program into a linear program solvable in polynomial time.
- Rounding schemes: Thresholding directly resolves most edges, while only the small violating subgraph requires greedy or linear-program rounding.The remaining subgraph typically contains less than 5% of graph edges.
- Rounding comparison: Exact and greedy rounding have nearly identical tracking performance and speed, with greedy rounding lowering IDF1 by 0.2 percentage points.MOTA and speed are equal between the two schemes.
C. Further Implementation Details
This section provides additional implementation information for the proposed method.
- The section extends the implementation details provided in the main article.
- The additional material concerns how the proposed method is implemented in practice.
- The section serves as supplementary implementation documentation for the method.
C.1. Detailed Architecture
The implementation uses six neural components for encoding, message passing, and edge classification, while processing normalized, sparsified video graphs under cross-validation.
- Detailed Architecture: The architecture contains six networks for node and edge encoding, message passing, node updates, and edge classification.Two networks encode nodes and edges; the remaining components update edges and nodes and classify edges.
- Video processing: Videos are processed sequentially in overlapping batches of 15 frames.
- Video processing: Static and dynamic sequences are sampled at 6 and 9 frames per second, respectively.Graph connectivity is restricted to top-50 reciprocal nearest-neighbor detections.
- Evaluation setup: Experiments use 3-fold cross-validation on MOT17 training data, training one network for each validation split.The splits cover all MOT17 training sequences and support model and hyperparameter selection.
- Evaluation setup: Each validation split balances moving and static cameras, track counts, and sequence duration.Sequences outside the validation set are used for training together with MOT15 sequences.
- Detection preprocessing: Detection preprocessing filters boxes below confidence 0.5 and applies a Faster-RCNN bounding-box regressor.The procedure uses both classifier and regressor heads trained on the MOT17 Detection challenge.
D. Additional Comparison with Graph Methods
Additional comparisons show that the method remains strong without its detection-preprocessing baseline and outperforms prior graph-based approaches across MOTChallenge datasets.
- Comparison setup: The comparison evaluates the final method and an Ours* variant without baseline [9] against top-performing offline graph-based methods.Table 7 also records the additional features and information sources available to each method.
- Results: Without [9], the method improves MOT15 MOTA by 19.8 points and IDF1 by 15.6 points over.Method uses the same Min-Cost Flow formulation but a simpler learning scheme.
- Results: Across all three datasets, the method consistently improves over multi-cut methods despite using fewer detections and less image information.The comparison includes methods with more involved graph formulations and larger numbers of boxes from unsuppressed detections.
- Results: With additional features, the method outperforms previous works by an even larger margin.