# Multi-Person Tracking by Multicut and Deep Matching

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2016.

## Built on by (most cited first, 23 of 23)

- [SimpleTrack: Understanding and Rethinking 3D Multi-object Tracking](https://mlsanity.com/paper/2111.09621/) (2021)
- [TransMOT: Spatial-Temporal Graph Transformer for Multiple Object Tracking](https://mlsanity.com/paper/2104.00194/) (2021)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (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)
- [ReST: A Reconfigurable Spatial-Temporal Graph Model for Multi-Camera Multi-Object Tracking](https://mlsanity.com/paper/2308.13229/) (2023)
- [Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths](https://mlsanity.com/paper/2108.10606/) (2021)
- [Learning of Global Objective for Network Flow in Multi-Object Tracking](https://mlsanity.com/paper/2203.16210/) (2022)
- [Towards PAC Multi-Object Detection and Tracking](https://mlsanity.com/paper/2204.07482/) (2022)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [Towards Frame Rate Agnostic Multi-Object Tracking](https://mlsanity.com/paper/2209.11404/) (2022)
- [Spatio-Temporal Point Process for Multiple Object Tracking](https://mlsanity.com/paper/2302.02444/) (2023)
- [I Spy With My Little Eye: A Minimum Cost Multicut Investigation of Dataset Frames](https://mlsanity.com/paper/2412.01296/) (2024)
- [Learnable Graph Matching: A Practical Paradigm for Data Association](https://mlsanity.com/paper/2303.15414/) (2023)
- [One Graph to Track Them All: Dynamic GNNs for Single- and Multi-View Tracking](https://mlsanity.com/paper/2507.08494/) (2025)
- [Transformer-based assignment decision network for multiple object tracking](https://mlsanity.com/paper/2208.03571/) (2022)
- [Two is a crowd: tracking relations in videos](https://mlsanity.com/paper/2108.05331/) (2021)
- [Using Keypoint Matching and Interactive Self Attention Network to verify Retail POSMs](https://mlsanity.com/paper/2110.03646/) (2021)
- [Four Algorithms for Correlation Clustering: A Survey](https://mlsanity.com/paper/2208.12636/) (2022)
- [MapTrack: Tracking in the Map](https://mlsanity.com/paper/2402.12968/) (2024)
- [PCSTracker: Long-Term Scene Flow Estimation for Point Cloud Sequences](https://mlsanity.com/paper/2603.19762/) (2026)
- [ClimateVID -- Social Media Videos Analysis and Challenges Involved](https://mlsanity.com/paper/2604.27968/) (2026)

## Abstract (arXiv)

In [1], we proposed a graph-based formulation that links and clusters person hypotheses over time by solving a minimum cost subgraph multicut problem. In this paper, we modify and extend [1] in three ways: 1) We introduce a novel local pairwise feature based on local appearance matching that is robust to partial occlusion and camera motion. 2) We perform extensive experiments to compare different pairwise potentials and to analyze the robustness of the tracking formulation. 3) We consider a plain multicut problem and remove outlying clusters from its solution. This allows us to employ an efficient primal feasible optimization algorithm that is not applicable to the subgraph multicut problem of [1]. Unlike the branch-and-cut algorithm used there, this efficient algorithm used here is applicable to long videos and many detections. Together with the novel feature, it eliminates the need for the intermediate tracklet representation of [1]. We demonstrate the effectiveness of our overall approach on the MOT16 benchmark [2], achieving state-of-art performance.