Papers › Lifted Disjoint Paths with Application in Multiple Object Tracking
Lifted Disjoint Paths with Application in Multiple Object Tracking
Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, Paul Swoboda
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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
| Task | Dataset | Model | Metric | Value | Rank at snapshot | Leaderboard | Report |
|---|---|---|---|---|---|---|---|
| Multi-Object Tracking | 2D MOT 2015 | Lif_T | IDF1 | 60.0 | #2 of 4 | Archive leaderboard | report |
| Multi-Object Tracking | 2D MOT 2015 | Lif_T | MOTA | 52.5 | #2 of 4 | Archive leaderboard | report |
| Multi-Object Tracking | MOT16 | Lif_T | IDF1 | 64.7 | #16 of 24 | Archive leaderboard | report |
| Multi-Object Tracking | MOT16 | Lif_T | MOTA | 61.3 | #16 of 24 | Archive leaderboard | report |
| Multi-Object Tracking | MOT17 | Lif_T | IDF1 | 65.6 | #41 of 48 | Archive leaderboard | report |
| Multi-Object Tracking | MOT17 | Lif_T | MOTA | 60.5 | #41 of 48 | Archive leaderboard | report |
Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections