# Lifted Disjoint Paths with Application in Multiple Object Tracking

arXiv: https://arxiv.org/abs/2006.14550 · HTML: https://mlsanity.com/paper/2006.14550/

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

## Built on by (most cited first, 30 of 55)

- [ByteTrack: Multi-Object Tracking by Associating Every Detection Box](https://mlsanity.com/paper/2110.06864/) (2021)
- [TrackFormer: Multi-Object Tracking with Transformers](https://mlsanity.com/paper/2101.02702/) (2021)
- [Observation-Centric SORT: Rethinking SORT for Robust Multi-Object Tracking](https://mlsanity.com/paper/2203.14360/) (2022)
- [SimpleTrack: Understanding and Rethinking 3D Multi-object Tracking](https://mlsanity.com/paper/2111.09621/) (2021)
- [Spatial-Temporal Transformer for Dynamic Scene Graph Generation](https://mlsanity.com/paper/2107.12309/) (2021)
- [TransMOT: Spatial-Temporal Graph Transformer for Multiple Object Tracking](https://mlsanity.com/paper/2104.00194/) (2021)
- [MOTSynth: How Can Synthetic Data Help Pedestrian Detection and Tracking?](https://mlsanity.com/paper/2108.09518/) (2021)
- [Multiple Object Tracking with Correlation Learning](https://mlsanity.com/paper/2104.03541/) (2021)
- [Unifying Short and Long-Term Tracking with Graph Hierarchies](https://mlsanity.com/paper/2212.03038/) (2022)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [GIAOTracker: A comprehensive framework for MCMOT with global information and optimizing strategies in VisDrone 2021](https://mlsanity.com/paper/2202.11983/) (2022)
- [Simple Cues Lead to a Strong Multi-Object Tracker](https://mlsanity.com/paper/2206.04656/) (2022)
- [Learning a Proposal Classifier for Multiple Object Tracking](https://mlsanity.com/paper/2103.07889/) (2021)
- [TransCenter: Transformers with Dense Representations for Multiple-Object Tracking](https://mlsanity.com/paper/2103.15145/) (2021)
- [LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking](https://mlsanity.com/paper/2111.11892/) (2021)
- [3D Multi-Object Tracking Using Graph Neural Networks with Cross-Edge Modality Attention](https://mlsanity.com/paper/2203.10926/) (2022)
- [Track without Appearance: Learn Box and Tracklet Embedding with Local and Global Motion Patterns for Vehicle Tracking](https://mlsanity.com/paper/2108.06029/) (2021)
- [One More Check: Making "Fake Background" Be Tracked Again](https://mlsanity.com/paper/2104.09441/) (2021)
- [The Caltech Fish Counting Dataset: A Benchmark for Multiple-Object Tracking and Counting](https://mlsanity.com/paper/2207.09295/) (2022)
- [Adiabatic Quantum Computing for Multi Object Tracking](https://mlsanity.com/paper/2202.08837/) (2022)
- [Looking Beyond Two Frames: End-to-End Multi-Object Tracking Using Spatial and Temporal Transformers](https://mlsanity.com/paper/2103.14829/) (2021)
- [ByteTrackV2: 2D and 3D Multi-Object Tracking by Associating Every Detection Box](https://mlsanity.com/paper/2303.15334/) (2023)
- [Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths](https://mlsanity.com/paper/2108.10606/) (2021)
- [Split and Connect: A Universal Tracklet Booster for Multi-Object Tracking](https://mlsanity.com/paper/2105.02426/) (2021)
- [Efficient tracking of team sport players with few game-specific annotations](https://mlsanity.com/paper/2204.04049/) (2022)
- [Online Multi-Object Tracking with Unsupervised Re-Identification Learning and Occlusion Estimation](https://mlsanity.com/paper/2201.01297/) (2022)
- [Online Multiple Object Tracking with Cross-Task Synergy](https://mlsanity.com/paper/2104.00380/) (2021)
- [Learning of Global Objective for Network Flow in Multi-Object Tracking](https://mlsanity.com/paper/2203.16210/) (2022)
- [Siamese-DETR for Generic Multi-Object Tracking](https://mlsanity.com/paper/2310.17875/) (2023)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)

## Abstract (arXiv)

We present an extension to the disjoint paths problem in which additional 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.