Source-linked AI summary
Deep Network Flow for Multi-Object Tracking
Samuel Schulter, Paul Vernaza, Wongun Choi, Manmohan Chandraker
TL;DR
Multi-object tracking requires associating detections into trajectories, but existing association costs are often hand-crafted or limited to linear parameterizations. The paper makes smoothed network-flow inference differentiable, enabling end-to-end learning of all costs and flexible input integration. Across its evaluations, learned costs outperform hand-crafted functions, while benchmark comparison is qualified by possible over-fitting of unary terms.
Problem
Existing data-association costs are often hand-crafted or limited to linear functions, despite their importance for network-flow-based tracking.
Method
The paper smooths a network-flow linear program so its solution is differentiable, allowing backpropagation to learn arbitrary parameterized costs for all association variables.
Results
End-to-end learned cost functions outperform hand-crafted functions without hand-tuning parameters across the evaluated settings.
Takeaways & Limitations
The formulation supports flexible neural cost functions and joint integration of bounding-box, temporal, appearance, and motion inputs.
Takeaways & Limitations
On the KITTI benchmark, the comparison is qualified because unary-term over-fitting may explain less pronounced motion-feature gains.
Abstract
from arXiv · showhide
Data association problems are an important component of many computer vision applications, with multi-object tracking being one of the most prominent examples. A typical approach to data association involves finding a graph matching or network flow that minimizes a sum of pairwise association costs, which are often either hand-crafted or learned as linear functions of fixed features. In this work, we demonstrate that it is possible to learn features for network-flow-based data association via backpropagation, by expressing the optimum of a smoothed network flow problem as a differentiable function of the pairwise association costs. We apply this approach to multi-object tracking with a network flow formulation. Our experiments demonstrate that we are able to successfully learn all cost functions for the association problem in an end-to-end fashion, which outperform hand-crafted costs in all settings. The integration and combination of various sources of inputs becomes easy and the cost functions can be learned entirely from data, alleviating tedious hand-designing of costs.
1. Introduction
Multi-object tracking is framed as a data-association problem over detected bounding boxes, where network-flow methods depend critically on learned or designed costs. The paper introduces end-to-end learning of arbitrary differentiable costs and reports advantages over hand-crafted functions.
- Motivation: Tracking-by-detection assigns detected bounding boxes to trajectories, turning multi-object tracking into a data-association problem.The task is challenging under occlusion, fast motion, and moving cameras, while supporting applications including surveillance and autonomous driving.
- Motivation: Prior association methods commonly use network flow or graph matching, but cost functions are usually hand-crafted, partially learned, or restricted to linear forms.The interplay of all variables and their costs determines tracking success.
- Contribution: The proposed formulation learns arbitrary parameterized costs for all association variables end-to-end by smoothing the linear program and backpropagating through its solution.Differentiable parameterized functions, including neural networks, can predict costs within a deep-learning framework.
- Experiments: The approach enables joint learning and integration of bounding-box, temporal, appearance, and motion inputs for network-flow tracking.Experiments on public datasets evaluate this end-to-end integration.
- Experiments: End-to-end learned cost functions outperform hand-crafted functions without requiring manual parameter tuning.The paper also reports encouraging results with appearance features.
2. Related Work
Related MOT work largely follows tracking-by-detection, with online methods favoring causal real-time use and batch methods exploiting future context. Existing learning approaches either optimize cost components with surrogate losses or constrain costs to linear parameterizations.
- Association problems in MOT: Tracking-by-detection first detects objects in each frame and then associates detections over time into object trajectories.This paradigm underlies much recent multi-object tracking work.
- Association problems in MOT: Online trackers associate incoming detections immediately, whereas batch methods use future or full-sequence context for more robust, nongreedy predictions.Batch methods are not applicable to real-time applications.
- Cost functions: Many tracking systems rely on hand-crafted costs built from detection confidence, spatial and temporal distances, or appearance information.Other methods learn pairwise affinity metrics and use them in tracking formulations.
- Integrating inference into learning: Prior learned-cost methods often optimize only parts of the tracking costs with surrogate losses rather than incorporating the full inference model.Structured SVM approaches integrate inference but remain limited in cost parameterization.
3. Deep Network Flows for Tracking
The paper formulates multi-object tracking as a network-flow problem and replaces hand-designed costs with differentiable, parameterized functions learned end-to-end. Smoothing the flow optimization enables gradient-based training from input features through the tracking solution.
- Network Flow Formulation: Tracking-by-detection represents detections as graph nodes and connects detections across nearby frames to form trajectories, including across occlusions or missed detections.Spatially distant links are removed to reduce graph size under a video smoothness assumption.
- Network Flow Formulation: The network-flow graph assigns variables and costs to trajectory birth, death, detection existence, and inter-detection links.Unary costs cover entry, exit, and detection variables, while pairwise costs cover links between detections.
- Network Flow Formulation: The globally optimal tracking solution is obtained by minimizing total flow cost subject to box and flow-conservation constraints in a linear program.The formulation relaxes integer flow variables to box constraints 0 ≤ x ≤ 1.
- End-to-end Learning of Cost Functions: Parameterized cost functions c(f, Θ) predict costs for all graph variables from input data, allowing the network-flow solution to be learned end-to-end.Inputs can include bounding boxes, detection scores, image features, and specialized features.
- End-to-end Learning of Cost Functions: Log-barrier smoothing and a null-space change of basis convert the constrained flow inference problem into a smooth unconstrained lower-level problem suitable for differentiation.The resulting gradients use implicit differentiation of the lower-level optimum and the chain rule to reach the cost-function parameters.
- Discussion: The formulation is presented as a general differentiable layer for learning costs in association problems and linear programs beyond multi-object tracking.The authors state that its applicability extends to problems satisfying the assumptions of the smoothed formulation.
- Defining ground truth and the loss function: The loss distinguishes true and false detections and association types, with weights controlling ambiguity, precision–recall trade-offs, and emphasis on links.The default weights are 1, while ambiguous edges can receive a weight below 1 and increasing the true-positive weight favors recall.
4. Experiments
Experiments evaluate learned network-flow cost functions against hand-crafted baselines across datasets, input sources, appearance integration, loss weighting, and benchmark tests. Learned functions generally outperform hand-crafted alternatives while enabling jointly trained combinations of diverse features, although benchmark gains from RGB are limited by unary-term overfitting.
- 4.1. Learned versus hand-crafted cost functions: Cross-validation on KITTI-Tracking and MOT16 shows that the proposed algorithm successfully learns network-flow cost functions from data.The comparison uses the same input information for learned and hand-crafted models.
- 4.1. Learned versus hand-crafted cost functions: Learned costs slightly outperform both hand-crafted baselines in MOTA, with lower identity switches and fragmentations on KITTI-Tracking and higher recall and mostly-tracked on MOT16.Nonlinear MLP costs also outperform linear learned costs in the reported experiments.
- 4.2. Combining multiple input sources: Learned costs outperform hand-crafted costs for raw detections, bounding-box overlap, and ALFD motion features, while using ALFD especially improves identity switches and fragmentations.The learned models jointly train diverse input features under the same loss function.
- 4.2. Combining multiple input sources: Adding RGB information to unary costs improves tracking over baselines, and adding it to pair-wise costs further improves results, especially for identity switches and fragmentations.The experiment uses MOT15 with provided ACF detections and compares Au+(B+O) with Au+(B+O+Ap).
- 4.3. Weighting the loss function: Loss weighting trades off recall, mostly tracked, precision, and identity switches by changing the relative influence of ambiguous cases, precision-recall terms, and link terms.Decreasing ωbasic slightly increases recall and mostly tracked, while increasing ωlinks lowers identity switches.
- 4.4. Benchmark results: On MOT15 benchmark evaluation, the RGB-unary model achieves MOTA 26.8, compared with 25.2 for the most similar model and 29.0 for a model using RGB pair-wise costs.The authors attribute the weaker RGB effect relative to cross-validation most likely to over-fitting of unary terms.
5. Conclusion
The work learns differentiable parameterized network-flow costs for multi-object tracking end to end, increasing design flexibility and avoiding hand-crafted costs. Future work extends this framework to integrated detection, richer trajectory interactions, and max-flow applications.
- End-to-end learning replaces delicate hand-crafting of network-flow cost functions with parameterized, differentiable costs for all graph variables.
- The formulation flexibly combines different input sources while jointly learning their cost parameters under the tracking objective.
- Future work will integrate object detectors end to end, investigate trajectory-interaction graphs, and explore max-flow applications.