Multi-target tracking using higher-order motion models.

摘要

Multi-target tracking is a significant and challenging problem. In its general form it is known to be NP-hard, and many approximate sub-optimal solution methods have been proposed to make the problem tractable. To select the best possible trajectories in a given video sequence, a cost function is used to assign costs to the potential candidates. Most recent approaches use only unary costs and pairwise costs between observations in two consecutive frames. Higher-order costs incorporating track smoothness constraints over three or more frames, such as constant velocity, can improve the performance of a tracker, but with added computational complexity. Our motivation is to leverage this information while keeping the computation time comparable to existing methods. For this purpose, we provide two different algorithms.;The first algorithm solves for partial trajectories (known as tracklets) over overlapping windows of three frames, and merges consistent overlapping tracklets to form longer tracks. In the case of inconsistency, a larger window of frames is used to resolve the conflict. A final step of merging disjoint tracklets using a min-cost network flow algorithm is carried out to handle long term occlusion in the sequence.;The second approach directly creates a network flow graph using potential correspondences in consecutive frames as the nodes. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. Therefore, we propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that are solvable by min-cost flow, and that progressively improve toward a high-quality solution to our original optimization problem.;We present quantitative experimental results demonstrating the superiority of our proposed algorithms over current state-of-the-art. We conclude the thesis with a discussion of the contributions of this work, and possible directions for future work.