Connected Component Model for Multi-Object Tracking

TLDR

In multi‑object tracking, exploiting temporal information across multiple frames is critical, yet directly solving the multi‑dimensional assignment (MDA) problem is NP‑hard, so most methods approximate or reduce it to a 2D assignment using only adjacent frames. This paper aims to reformulate the MDA problem by treating the relation between observation associations as an equivalence relation under spatial‑temporal constraints, enabling decomposition into independent subproblems. By constructing a connected component model (CCM) that captures these equivalence constraints, the authors efficiently solve the global MDA problem through optimization of independent data‑association subproblems. Experiments on challenging public datasets show that the CCM‑based algorithm outperforms state‑of‑the‑art approaches.

Abstract

In multi-object tracking, it is critical to explore the data associations by exploiting the temporal information from a sequence of frames rather than the information from the adjacent two frames. Since straightforwardly obtaining data associations from multi-frames is an NP-hard multi-dimensional assignment (MDA) problem, most existing methods solve this MDA problem by either developing complicated approximate algorithms, or simplifying MDA as a 2D assignment problem based upon the information extracted only from adjacent frames. In this paper, we show that the relation between associations of two observations is the equivalence relation in the data association problem, based on the spatial-temporal constraint that the trajectories of different objects must be disjoint. Therefore, the MDA problem can be equivalently divided into independent subproblems by equivalence partitioning. In contrast to existing works for solving the MDA problem, we develop a connected component model (CCM) by exploiting the constraints of the data association and the equivalence relation on the constraints. Based upon CCM, we can efficiently obtain the global solution of the MDA problem for multi-object tracking by optimizing a sequence of independent data association subproblems. Experiments on challenging public data sets demonstrate that our algorithm outperforms the state-of-the-art approaches.