Source-linked AI summary
Multi-Person Tracking by Multicut and Deep Matching
Siyu Tang, Bjoern Andres, Mykhaylo Andriluka, Bernt Schiele
TL;DR
Multi-person tracking must associate noisy detection hypotheses despite false positives, occlusions, and camera motion. The paper extends multicut tracking with DeepMatching affinities and a plain multicut formulation that supports efficient optimization without intermediate tracklets, achieving state-of-the-art performance on MOT16.
Problem
Multi-person tracking remains challenged by false positives, long-term occlusions, and camera motion, especially in crowded scenes.
Method
The approach uses DeepMatching-based local appearance affinities and a plain multicut formulation with post-processing and efficient optimization.
Results
The method achieves the second-best MOTA on the MOT16 Challenge, 0.1 point below the best reported result, while linking people through occlusions and producing long-lived tracks.
Takeaways & Limitations
Multicut tracking is reported as robust to noisy detection input because it jointly clusters multiple plausible detections belonging to the same target over time and space.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends graph-based multicut tracking to handle ambiguous detections, challenging visual conditions, and large detection graphs. It introduces DeepMatching-based affinities and a plain multicut formulation with efficient optimization, eliminating the need for intermediate tracklets.
- Motivation: False positives, long-term occlusions, and camera motion remain challenging in crowded multi-person tracking.Tracking-by-detection reduces the task to associating detection hypotheses across video frames.
- Multicut formulation: Multicut clusters multiple plausible detections jointly across time and space instead of finding disjoint paths.This avoids requiring non-maximum suppression on detections or final tracks.
- Multicut formulation: Positive and negative edge costs respectively encourage detections to share or not share a track, leaving track number and size determined by the solution.Unlike distance-based clustering, the formulation does not require specifying, constraining, or penalizing the number and size of tracks.
- Extensions: DeepMatching supplies local appearance affinities that are robust to camera motion and partial occlusion.The feature makes the formulation applicable to moving-camera videos with arbitrary person motion.
- Extensions: The plain multicut formulation enables efficient optimization on detection graphs and removes the need for an intermediate tracklet representation.Small clusters are removed afterward to eliminate false positive detections.
- Multicut formulation: A multicut solution’s connected components indicate both the number of tracks and the membership of every detection.In the illustrated three-frame example, two tracks are represented by yellow and magenta components.
2 Related Work
Prior multi-person tracking methods commonly associate detections directly or through tracklets using local or global optimization. This work builds on multicut tracking and generalizes it to large-scale sequences.
- Existing approaches: Tracking-by-detection methods either link detections over time directly or group them into tracklets before combining tracks.Common association strategies include Hungarian optimization, network flow, and multiple hypotheses tracking.
- Global formulations: Global-objective approaches include continuous formulations, generalized minimum clique optimization, and multicut-based tracking.These methods differ in how they model occlusions, dynamics, appearance, and joint track recovery.
- Position of this work: The paper builds on the multicut formulation proposed in and generalizes it to large-scale sequences.This extension is presented alongside the paper’s subsequent formulation and feature modifications.
3 Multi-Person Tracking as a Multicut Problem
The paper casts multi-person tracking as a minimum cost multicut problem over detection graphs, using DeepMatching-based pairwise features and efficient optimization to handle occlusion, camera motion, and noisy detections.
- Minimum Cost Multicut Problem: Tracking is formulated on a graph whose nodes are detections and whose edges connect detections that may belong to the same person.Edge costs or rewards determine whether incident detections are assigned to distinct tracks.
- Minimum Cost Multicut Problem: Long-range temporal edges preserve tracks across occlusions and missing detections, but the implementation limits connections to detections at most 10 frames apart.Pairwise features become less reliable as temporal distance increases.
- Minimum Cost Multicut Problem: The plain multicut formulation absorbs detection confidence into edge costs, removes small clusters, and enables direct KLj optimization without intermediate tracklets.Clusters smaller than five are deleted, and KLj uses iterative subgraph bipartition updates with fewer than 30 updates in the experiments.
- Deep Matching based Pairwise Costs: DeepMatching supplies local appearance correspondences that are intended to remain robust under camera motion and partial occlusion.The method uses image content rather than the velocity-based affinity from the earlier formulation.
- Deep Matching based Pairwise Costs: For each detection pair, five matching-based features are learned through logistic regression and converted into an edge cost for the tracking objective.The features use matched keypoints and detection properties, while low-confidence detections receive low probability of association with other detections.
4 Experiments and Results
Experiments compare DeepMatching and spatio-temporal pairwise potentials, test robustness to detection noise, and evaluate the multicut tracker on MOT16. DeepMatching remains accurate over longer temporal gaps, while the formulation maintains performance under varied detection inputs and achieves the second-best MOTA overall.
- 4.1 Comparison of Pairwise Potentials: The comparison evaluates DeepMatching against spatio-temporal features using verification accuracy on MOT16-09 and MOT16-10 sequences.The test sets represent static- and moving-camera conditions, with positive and negative detection pairs defined by ground-truth identity.
- 4.1 Comparison of Pairwise Potentials: DeepMatching maintains superior pairwise verification accuracy over longer temporal distances, whereas spatio-temporal features deteriorate rapidly beyond two frames.On MOT16-10, DeepMatching reaches 0.925 accuracy at a 20-frame distance despite rapid camera motion.
- 4.2 Robustness to Input Detections: Changing the minimum detection score from 0.1 to −0.3 increases detections from 3405 to 4636 while decreasing MOTA by only 1 percentage point, from 44.1% to 43.1%.The experiments also examine extreme noisy and sparse detection inputs using standard CLEAR MOT metrics.
- 4.2 Robustness to Input Detections: The multicut formulation remains robust when detection inputs are noisy or sparse, using the same parameters and removing clusters smaller than five.No further track splitting or merging is performed in these experiments.
- 4.2 Robustness to Input Detections: The Kernighan-Lin solver obtains a solution in 88.34 seconds for a problem with more than one million edges.This reports practical runtime for the multicut optimization procedure.
- 4.3 Results on MOT16: On MOT16, the method achieves the second-best MOTA, only 0.1 point below the best reported result.Qualitative results include crowded scenes, irregular camera motion, occlusions, and a rapidly turning bus-mounted camera.