Multi-Target Tracking in Multiple Non-Overlapping Cameras using Fast-Constrained Dominant Sets

In this paper, a unified three-layer hierarchical approach for solving tracking problems in a multiple non-overlapping cameras setting is proposed. Given a video and a set of detections (obtained by any person detector), we first solve within-camera tracking employing the first two layers of our framework and, then, in the third layer, we solve across-camera tracking by associating tracks of the same person in all cameras in a simultaneous fashion. To best serve our purpose, we propose Fast-Constrained Dominant Set Clustering (FCDSC), a novel method that is an order of magnitude faster than constrained dominant sets clustering technique. FCDSC is employed to solve both within- and across-camera tracking tasks. We first build a graph where nodes of the graph represent short-tracklets, tracklets and tracks in the first, second and third layer of the framework, respectively. The edge weight depicts the similarity between nodes. FCDSC takes as an input a constraint set, a subset of nodes from the graph which one wants the extracted cluster to include. Given a constraint set, FCDSC generates compact cluster selecting nodes from the graph which are highly similar to each other and with elements in the constraint set. The approach is based on a parametrized family of quadratic programs that generalizes the standard quadratic optimization problem. In addition to having a unified framework that simultaneously solves within- and across-camera tracking, the third layer helps to link broken tracks of the same person occurring during within-camera tracking. We have tested this approach on a very large and challenging dataset (namely, MOTchallenge DukeMTMC) and show that the proposed framework outperforms the current state of the art. Even though the main focus of this paper is on multi-target tracking in non-overlapping cameras, proposed approach can also be applied to solve video-based person re-identification problem. We show that when the re-identification problem is formulated as a clustering problem, FCDSC can be used in conjunction with state-of-the-art video-based re-identification algorithms, to increase their already good performances. Our experiments demonstrate the general applicability of the proposed framework for non-overlapping across-camera tracking and person re-identification tasks.