Lifted Edges as Connectivity Priors for Multicut and Disjoint Paths

Our study of lifted multicut concentrates on partial LMC represented by labeling of a subset of (lifted) edges.Given partial labeling, some NP-hard problems arise.
The main focus of the talk is LDP problem. We prove that this problem is NP-hard and propose an optimal integer linear programming (ILP) solver. The solver uses linear inequalities that produce a high-quality LP relaxation. LDP is a convenient model for multiple object tracking(MOT) because DP naturally leads to trajectories of objects and lifted edges help to prevent id switches and re-identify persons. Our tracker using the optimal LDP solver was a leading tracker on three benchmarks of the MOT challenge MOT15/16/17, improving significantly overstate-of-the-art at the time of its publication. In order to solve even larger instances of a challenging dataset MOT20, we introduce an approximate LDP solver based on Lagrange decomposition. The new tracker achieved on all the four standard MOT benchmarks performance comparable or better than state-of-the-art methods (at the time of publication).