Source-linked AI summary
Lifted Disjoint Paths with Application in Multiple Object Tracking
Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, Paul Swoboda
TL;DR
Multiple object tracking needs long-range temporal information, but basic disjoint paths score only direct detection transitions. The paper adds lifted edges and develops a tighter LP relaxation for global optimization; its tracker outperforms peer-reviewed systems on all three MOT Challenge benchmarks.
Problem
Basic disjoint paths can solve large MOT data-association instances, but their first-order costs score only whether detections directly follow one another, limiting trajectory accuracy and leaving long-range interactions inadequately represented in optimization formulations.
Source: §1 · p. 1, §2 · p. 3Method
The paper augments disjoint paths with lifted edges for long-range connectivity priors and proposes tighter linear inequalities and separation routines for global optimization.
Source: §1 · pp. 1–2Results
The tracker outperforms peer-reviewed systems on MOT15, MOT16, and MOT17; on MOT17, MOTA improves from 53.5 to 60.5.
Source: §7.6 · p. 9Takeaways & Limitations
For MOT, global optimization avoids poor local optima and initialization dependence, while improvements in discriminative cost features directly correlate with better tracking performance.
Source: §1 · p. 2The tracker reaches nearly optimal data association on MOT Challenge datasets; the authors conjecture further gains would require better detectors, better inter- and extrapolation, or solvers handling longer time gaps.
Source: §8 · p. 9
Abstract
from arXiv · showhide
We present an extension to the disjoint paths problem in which additional \emph{lifted} edges are introduced to provide path connectivity priors. We call the resulting optimization problem the lifted disjoint paths problem. We show that this problem is NP-hard by reduction from integer multicommodity flow and 3-SAT. To enable practical global optimization, we propose several classes of linear inequalities that produce a high-quality LP-relaxation. Additionally, we propose efficient cutting plane algorithms for separating the proposed linear inequalities. The lifted disjoint path problem is a natural model for multiple object tracking and allows an elegant mathematical formulation for long range temporal interactions. Lifted edges help to prevent id switches and to re-identify persons. Our lifted disjoint paths tracker achieves nearly optimal assignments with respect to input detections. As a consequence, it leads on all three main benchmarks of the MOT challenge, improving significantly over state-of-the-art.
1. Introduction
The paper extends disjoint paths with lifted edges to represent long-range connectivity priors for multiple object tracking. It develops a tighter LP relaxation for global optimization and reports that the approach outperforms state-of-the-art trackers on the MOT Challenge.
1. Introduction
- The lifted disjoint paths problem is NP-hard, and the paper proposes linear inequalities and separation routines for optimization.Source: §1 · p. 1
- Lifted edges add long-range connectivity priors without changing the feasible trajectory set, allowing endpoint similarity to encourage or penalize paths.An active lifted edge corresponds to an active trajectory between its endpoints.Source: §1 · p. 1
- For MOT, these long-range interactions help re-identify objects and prevent identity switches within long trajectories.Source: §1 · p. 1
- The proposed linear inequalities yield a high-quality relaxation, and the considered polyhedral relaxation is tighter than naively reusing known inequalities.The relaxation enables a global optimization approach incorporating long-range interactions for MOT.Source: §1 · pp. 1–2
- The formulation may also apply to problems beyond multiple object tracking.Source: §1 · p. 2
2. Related Work
Prior work models MOT with disjoint paths and other combinatorial formulations, but incorporating long-range temporal information into global data-association optimization remains a challenge. The paper distinguishes its model and relaxation from these approaches.
2. Related Work
- Earlier disjoint-path extensions for detector fusion and multi-camera tracking cannot integrate long-range information.Source: §2 · p. 2
- Long-range information is considered crucial for high-quality MOT, yet its incorporation into data-association optimization formulations has remained unsatisfactory.Source: §2 · p. 3
- The paper contrasts disjoint paths with multicut: disjoint paths automatically enforce that a track cannot contain distinct-object detections from the same time point, while multicut requires explicit soft constraints.Source: §2 · p. 3
- Reusing lifted-multicut polyhedral results with flow constraints gives a suboptimal relaxation; the paper derives tighter lifted-edge constraints from disjoint-path structure.The authors present this as the first global MOT optimization approach incorporating long-range interactions.Source: §2 · p. 3
- Prior approaches with long-range temporal edges use non-convex algorithms or heuristics, whereas this approach uses LP-based branch-and-bound for globally optimal solutions.Source: §2 · p. 3
3. Problem Formulation
The formulation uses a directed acyclic flow network for node-disjoint paths and a lifted graph to represent connectivity between nodes. For MOT, detections or tracklets form nodes, while ordinary and skip edges encode object correspondences across time.
3. Problem Formulation
- The flow network and lifted graph are directed acyclic graphs, with source and sink nodes in the flow network.Source: §3 · p. 3
- Binary node variables encode vertex-disjoint paths, while binary lifted-edge variables indicate whether their endpoints are connected by active flow.A lifted-edge variable is active exactly when a path in the flow network connects its endpoints.Source: §3 · p. 3
- The paper proposes linear inequalities to formulate the optimization problem as an ILP with a high-quality linear relaxation.Source: §3 · p. 3
- The MOT graph represents detections or tracklets as nodes, with edges between adjacent frames encoding correspondences of the same object.Skip edges connect farther-apart frames and can represent correspondences across occluded or undetected intermediate frames.Source: §3 · pp. 3–4
- Lifted edges can encourage re-identification with negative costs or prevent identity switches with positive costs.Source: §3 · p. 4
4. Constraints
The formulation uses flow and lifted-edge constraints to encode when a lifted edge is active, then strengthens the LP relaxation with path- and cut-based inequalities. Lifted variants and their symmetric counterparts provide strictly tighter relaxations than their basic forms.
4. Constraints
- Constraints on lifted-edge variables y′vw ensure they satisfy (2); when flow in G goes from v to w, y′vw = 1 under constraints (8) and (10).The corresponding LP relaxation can be strengthened by additional constraints.Source: §4 · p. 4
- The formulation defines reachability between vertices in the flow network, which is used in several of the constraints.The relation is reflexive when empty paths are allowed.Source: §4 · p. 4
- Path inequalities require a lifted edge to be active when flow connects its endpoints along a path.Their cut-based counterparts use cuts induced by paths; the basic cut inequalities generalize single-node cut inequalities.Source: §4 · p. 4
Furthermore the lifted path-induced cut inequalities (11)
- Lifted inequalities extend path and path-induced cut inequalities by allowing lifted edges within paths, representing possible connections between their endpoints.The lifted path-induced cut formulation also has symmetric counterparts that study paths ending at the destination and strictly strengthen the relaxation.Source: §4 · p. 5, Furthermore the lifted path-induced… · p. 5
- Lifted path and lifted path-induced cut inequalities define strictly tighter relaxations than their basic counterparts.Adding further inequalities also strictly improves the relaxation defined by lifted path-induced cuts alone.Source: §4 · p. 5, Furthermore the lifted path-induced… · p. 5
5. Separation
The separation procedure starts with basic constraints, solves the integer problem, and iteratively adds violated advanced constraints until the solution is feasible for the full formulation.
5. Separation
- The solver starts with constraints (5)–(7), adds violated advanced constraints, and resolves until it finds a feasible solution to the full problem.The advanced constraint families are exponentially large, so they are separated rather than added initially.Source: §5 · p. 5
- The algorithms inspect active s–t paths to find violated lifted path and lifted path-induced cut inequalities.Path inequalities are added when a lifted edge between vertices on an active path is zero; cut separation extracts a subpath when the relevant lifted-edge conditions are violated.Source: §5 · pp. 5–6
- Both separation algorithms can be implemented in time linear in the number of active base edges.The procedure also covers basic path and path-induced cut inequalities as special cases.Source: §5 · pp. 5–6
6. Complexity
The lifted disjoint paths problem is NP-hard, including restricted versions with only negative or only positive lifted edges.
6. Complexity
- The hardness results use reductions from integer multicommodity flow and 3-SAT, both known NP-complete problems.Source: §6 · p. 6
- The lifted disjoint paths problem is NP-hard even when restricted to negative lifted edges only.The proof reduces from integer multicommodity flow.Source: §6 · p. 6
- The lifted disjoint paths problem is also NP-hard when restricted to positive lifted edges only.The proof reduces from 3-SAT.Source: §6 · p. 6
7. Experiments
Experiments evaluate the tracker on MOT15, MOT16, and MOT17, using a two-step graph procedure and learned costs for base and lifted edges. Results report benchmark improvements and near-optimal assignments on MOT17 training data.
7.1. Graph Construction.
- A two-step procedure first solves detection graphs over short intervals, then solves graphs of tracklets and iteratively splits tracks when doing so improves the original objective.The procedure improves that objective at every iteration and terminates after finitely many iterations.Source: §7.1 · p. 6
- The first graph-construction step uses edges up to two seconds apart and sparsifies base and lifted graphs; the second step uses dense graphs.Lifted edges with costs close to zero are omitted, and higher-time-gap lifted edges are included more sparsely.Source: §7.1 · pp. 6–7
7.2. Preprocessing and Post-processing
- Preprocessing filters and reshapes detections; post-processing recovers missing detections and extends trajectories, with linear interpolation for remaining gaps in static-camera sequences.The tracker is also evaluated using only linear interpolation as post-processing.Source: §7.2 · p. 7
7.3. Cost Learning
- Base- and lifted-edge costs use a neural network that combines appearance, DeepMatching, motion, and spatio-temporal cues.The visual cues include re-identification descriptors and pixelwise correspondences from DeepMatching.Source: §7.3 · pp. 7–8
7.4. Experiment Setup
- Evaluation covers 39 test sequences across MOT15, MOT16, and MOT17, with training and parameter tuning performed on MOT17 train data.MOT16 and MOT17 share sequences, while MOT17 provides three detectors; training-set experiments use leave-one-out cross-validation.Source: §7.4 · p. 8
- The two principal tracking metrics are MOTA, which incorporates false negatives, false positives, and identity switches, and IDF1, which assesses identity consistency.Source: §7.4 · p. 8
7.5. Benefit of Long Range Edges
- Increasing the maximum time gap improves IDF1, while MOTA remains essentially constant without interpolation or extrapolation.ID precision and recall both increase, and the assignments are nearly optimal relative to the input detections.Source: §7.5 · p. 8, Table 1 · p. 8
7.6. Benchmark Evaluations
- On MOT17, MOTA rises from 53.5 to 60.5 and IDF1 from 52.3 to 65.6; the tracker outperforms peer-reviewed competitors across all three benchmarks.With only linear interpolation as post-processing, Lif_TsimInt achieves 58.2 MOTA and 65.2 IDF1; the ILP solver averages 26.6 minutes per sequence.Source: §7.6 · p. 9, Table 2 · p. 9
8. Conclusion
For MOT challenge datasets, the authors report nearly optimal data association and conjecture that further gains would require improvements to detections, interpolation and extrapolation, or solver capacity for longer time gaps.
Appendix
The appendix’s author line names Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, and Paul Swoboda.
- The appendix lists Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, and Paul Swoboda as its authors.Source: Appendix · p. 13
Abstract
The appendix supplies missing solver proofs and tracker details, including proof material for Sections 4 and 6 and supplementary information on assignments, post-processing, fusion, and evaluation.
- The appendix presents missing proofs regarding the solver and details about the tracker.Source: Abstract · p. 13
- Sections 10.1–10.4 provide proofs used in Sections 4 and 6.Source: Abstract · p. 13
- Further appendix sections explain optimal assignments, analyze tracker post-processing, describe the fusion network, and provide evaluation metrics for tracked sequences.Source: Abstract · p. 13
10. Appendix
The appendix establishes strict relaxation-strength comparisons among the path and cut inequalities. Its examples show how lifted-path constraints relate to the original path inequalities.
10.1. Proofs for Section 4
- Path inequalities (8) define a strictly tighter relaxation than lifted multicut path inequalities (13).Figure 1 illustrates a failure case for (13) in which (8) gives the correct lower bound for a lifted edge.Source: §10.1 · p. 13, Figure 1 · p. 14
- Lifted path inequalities (10) provide a strictly better relaxation than path inequalities (8).The proof shows that satisfying (10) implies satisfying (8), while an example separates the relaxations.Source: §10.1 · pp. 13–14
- Lifted path-induced cut inequalities (11) define a strictly tighter relaxation than path-induced cut inequalities (9).Source: §10.1 · p. 14
Furthermore the lifted path-induced cut inequalities (11)
This section develops lifted-disjoint-path optimization through additional cut inequalities and complexity results, then describes its tracking features, training, and evaluation.
Furthermore the lifted path-induced cut inequalities (11)
- Inequalities (11) and (12) together define a strictly better relaxation than (11) alone.Source: Furthermore the lifted path-induced… · p. 14
10.2. Symmetric Form of Cut Inequalities
- Symmetric cuts (16) tighten (15), (16) and (17) improve on (16) alone, and symmetric pairs (15)/(16) tighten (9) and (11).Source: §10.2 · p. 15
10.3. Other Valid Inequalities
- Additional lifted-flow inequalities exploit the at-most-one connection per node per time frame and, with a linear number of constraints, reduce early branch-and-bound search space.Source: §10.3 · pp. 15–16
10.4. Proofs for Section 6 Complexity
- Polynomial reductions from integer multicommodity flow and 3-SAT establish NP-hardness with negative-only and positive-only lifted edges, respectively.The reductions are described for the two edge-sign restrictions separately.Source: §10.4 · pp. 17–18
10.6. Optimal data association
- Optimal assignments are computed by maximum-weight Hungarian matching on per-frame detection–ground-truth IoU edges, removing edges below 0.5 and treating unmatched detections as false positives.Trajectories are synthetically split at skip-edges longer than the specified time threshold.Source: §10.6 · p. 18
10.7. Ablation study on post-processing methods.
- Solving the lifted disjoint paths problem assigns input detections to object identities very close to the best possible assignment.Source: §10.7 · p. 18
- 59.5 MOTA and 68.9 IDF1: Assignment+SI* improves tracking, but moving-camera spatial interpolation can propagate errors, so final Lif_T uses visual interpolation and static-camera SI.Static-camera SI is used to ensure robust spatial approximations; SI* applies it to all sequences.Source: §10.7 · p. 19
- About 20% MOTA and 10% IDF1 gains: visual extrapolation extends trajectories, while occlusion-only spatial interpolation adds a slight further improvement.Visual interpolation can be applied robustly across sequences when the object is visible.Source: §10.7 · p. 19
- 25%: With post-processing, the near-optimal data-association tracker improves over Tracktor, underscoring the importance of accurate association for high-quality results.The authors attribute the improvement to applying post-processing to the solver’s computed data association.Source: §10.7 · p. 19
10.8. Further Details on the Feature Fusion Network.
- The fusion network treats DeepMatching densities and temporal distance as control features that indicate the reliability of other input features, not assignment correctness.The lifted-path formulation aggregates multiple edge classifiers, allowing them to correct individual edge misclassifications.Source: §10.8 · pp. 20–21
- To address class imbalance, edge-classifier training samples edges to keep positive-to-negative ratios fixed by temporal distance, with a maximum edge distance of 2 seconds.This temporal range allows recovery of persons after long occlusions.Source: §10.8 · p. 20
10.9. Extended Quantitative Results.
- The extended evaluations report Lif_T results per sequence for MOT15, MOT16, MOT17 test sets and MOT17 train, alongside lifted-disjoint-path solver time in seconds.The results are presented in Table 5.Source: §10.9 · p. 21, Table 5 · p. 22