Greedy Batch-Based Minimum-Cost Flows for Tracking Multiple Objects

Xinchao Wang, Bin Fan, Shiyu Chang, Zhangyang Wang, Xianming Liu, Dacheng Tao, Thomas S. Huang

Research output: Contribution to journalArticlepeer-review


Minimum-cost flow algorithms have recently achieved state-of-the-art results in multi-object tracking. However, they rely on the whole image sequence as input. When deployed in real-time applications or in distributed settings, these algorithms first operate on short batches of frames and then stitch the results into full trajectories. This decoupled strategy is prone to errors because the batch-based tracking errors may propagate to the final trajectories and cannot be corrected by other batches. In this paper, we propose a greedy batch-based minimum-cost flow approach for tracking multiple objects. Unlike existing approaches that conduct batch-based tracking and stitching sequentially, we optimize consecutive batches jointly so that the tracking results on one batch may benefit the results on the other. Specifically, we apply a generalized minimum-cost flows (MCF) algorithm on each batch and generate a set of conflicting trajectories. These trajectories comprise the ones with high probabilities, but also those with low probabilities potentially missed by detectors and trackers. We then apply the generalized MCF again to obtain the optimal matching between trajectories from consecutive batches. Our proposed approach is simple, effective, and does not require training. We demonstrate the power of our approach on data sets of different scenarios.

Original languageEnglish (US)
Article number7967835
Pages (from-to)4765-4776
Number of pages12
JournalIEEE Transactions on Image Processing
Issue number10
StatePublished - Oct 2017


  • Multi-object tracking
  • batch processing
  • graph transformation
  • minimum-cost flows

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Greedy Batch-Based Minimum-Cost Flows for Tracking Multiple Objects'. Together they form a unique fingerprint.

Cite this