Multi-target tracklet stitching through network flows

Complex track stitching problems have risen in prominence with the development of wide area persistent sensors for urban surveillance. Common approaches such as multiple hypothesis algorithms in tracking and tracklet stitching solve these problems by creating a representation of all possible data associations, then solving for the optimal data association via integer programming or suboptimal techniques. The number of data association hypotheses grows exponentially with number of objects and time, which leads to scaling issues when tracking targets in high-density environments over long periods of time. State-of-the-art multiple hypothesis approaches make tradeoffs to limit complexity, discarding potential data associations to avoid scaling problems. These approaches run the risk of eliminating the best data association hypotheses. This paper describes a novel graphical approach to data representation, called the Track Graph, which provides a compact and efficient structure for the storage of tracklet data and subsequent formulation of the tracklet stitching problem. The Track Graph implicitly represents the set of feasible tracklet stitching hypotheses, with linear scaling in time in both edges (feasible associations) and nodes (tracklets). Using the Track Graph, we pose the track-stitching problem as a min-cost flow problem, and describe polynomial-time algorithms to solve the full tracklet-to-track assignment problem, obtaining the same optimal solution as multiple hypothesis tracking algorithms. We demonstrate the efficacy of our algorithms on high density simulated scenarios.