Multi-target Tracking Using Higher-order Motion Models

Open Access
Butt, Asad Anwar
Graduate Program:
Computer Science and Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
June 20, 2013
Committee Members:
  • Robert Collins, Committee Chair
  • Yanxi Liu, Committee Member
  • Jesse Louis Barlow, Committee Member
  • Necdet S Aybat, Committee Member
  • multi-target tracking
  • graphical models
  • higher-order models
  • motion models
  • min-cost network flow
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.