Multiple Object Tracking Using the Shortest Path Faster Association Algorithm

Zhenghao Xi, Heping Liu, Huaping Liu, Bin YangThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces a novel algorithm for multiple object tracking in cluttered environments by formulating the problem as an integer programming problem and then efficiently solving it using the Shortest Path Faster Algorithm (SPFA). This approach achieves global optimality, improved robustness against false positives/negatives, and real-time performance compared to existing methods.

What Problem Does This Paper Address?

Tracking multiple objects in real-world scenarios is a challenging task due to issues like occlusion, illumination changes, clutter, and the presence of false positives and negatives from object detectors. Existing data association methods often struggle to find the globally optimal solution, leading to fragmented trajectories and reduced accuracy. Specifically, formulating multiple object tracking as an integer programming (IP) problem offers a path to global optimality, but solving IPs is computationally expensive (NP-complete). While some methods relax this to linear programming (LP) and use algorithms like k-shortest paths (KSP) or successive shortest path (SSP), these have their own limitations in terms of complexity or robustness. This paper aims to bridge this gap by providing a robust and efficient method for achieving globally optimal multiple object tracking.

Methods

The core of the proposed method lies in formulating the multiple object tracking problem as a min-cost network flow problem, which is then expressed as an integer linear program (ILP). The key innovation is the relaxation of this ILP to a standard linear programming (LP) problem and its efficient solution using the Shortest Path Faster Algorithm (SPFA).

Here's a breakdown of the approach:

  • Min-Cost Network Flow Formulation: The tracking problem is modeled as a directed acyclic graph (DAG) where nodes represent object locations in space-time. Edges represent the flow of objects between consecutive frames. The objective is to find a set of tracks that maximizes the probability of observing the given sequence, considering object presence probabilities and transitions.
  • Integer Linear Programming (ILP): The probabilistic formulation is translated into an ILP by introducing binary indicator variables for object movement between locations. This ILP formulation naturally handles false positives and negatives.
  • Relaxation to Linear Programming (LP): To overcome the computational burden of ILP, the problem is relaxed to a standard LP.
  • Shortest Path Faster Algorithm (SPFA): Instead of KSP or SSP, the paper proposes using SPFA to solve the relaxed LP. SPFA is chosen for its ability to handle graphs with negative edge weights (which arise from the log-probabilities) and its generally better average-case complexity (O(E)) compared to Dijkstra's algorithm (which requires non-negative weights) or Bellman-Ford (O(NE)). The authors also introduce virtual "source" and "sink" nodes to better handle object entry and exit from the scene, improving robustness against false negatives.
  • Long Sequence Processing: To manage computational load for long video sequences, the paper proposes segmenting sequences into smaller chunks (e.g., 100 frames). Temporal consistency is maintained by overlapping segments and enforcing flow conservation between them.

Datasets

The paper evaluates its method on several publicly available datasets known for their challenging tracking scenarios:

  • PETS09: Used for sequences like Multiple_flow_view1 and S2_Ll_view5.
  • CAVIAR: Used for the Threepastshop2 sequence.
  • BEHAVEDATA: Used for the Sequence3 sequence.
  • ETHMS: Used for the Seq03viewl sequence.

These datasets are chosen to cover a range of challenges including occlusion, scaling, pose variations, clutter, illumination changes, and dynamic backgrounds.

Key Insights and Ideas

  • SPFA for Global Optimality: The core insight is that SPFA, a generally efficient shortest path algorithm, can be effectively used to solve the relaxed LP formulation of the multiple object tracking problem, thereby achieving a globally optimal solution. This is a significant improvement over greedy or approximate methods.
  • Handling False Positives/Negatives Naturally: The network flow formulation, particularly with the addition of virtual source and sink nodes, inherently helps in filtering out false positives and negatives by modeling object appearance and disappearance.
  • Robustness through Network Flow: The min-cost network flow framework provides a structured way to model complex interactions between objects and their trajectories, leading to more robust tracking, especially in challenging scenarios like occlusion.
  • Efficient Long Sequence Handling: The segmentation strategy for long sequences is crucial for practical real-time applications, allowing the algorithm to process extended videos without prohibitive computational costs.

Key Results

  • Improved Robustness: The SPFA algorithm demonstrates superior robustness against false negatives and false positives compared to state-of-the-art methods like Zhang's method 2, KSP, and SSP. This is evident in qualitative results and quantitative metrics.
  • High Tracking Accuracy: The method achieves competitive or superior tracking accuracy (measured by MOTA and MOTP) across various challenging sequences.
  • Real-Time Performance: The SPFA algorithm significantly outperforms other methods in terms of run time. For a 1000-frame sequence, SPFA takes approximately 0.08 seconds, while KSP takes 20 seconds and SSP takes 0.9 seconds. This makes the algorithm suitable for real-time applications.
  • Lower Complexity: The average-case complexity of O(E) for SPFA is significantly better than the O(KN log N) of KSP/SSP, where K is the number of tracks.

Limitations and Future Work

  • Limitations:
    • The paper notes that the effectiveness of the dynamic background performance test is limited by the requirement for a relatively consistent probability distribution of the dynamic background.
  • While the method is robust, the paper acknowledges that the "occupancy problem" (handling multiple objects in the same location) can still be challenging, though SPFA performs better than other methods.
  • Future Work:
    • The authors suggest that tracking multiple types of targets with a dynamic background in real time will be the focus of their future research.

Summary updated

Abstract

To solve the persistently multiple object tracking in cluttered environments, this paper presents a novel tracking association approach based on the shortest path faster algorithm. First, the multiple object tracking is formulated as an integer programming problem of the flow network. Then we relax the integer programming to a standard linear programming problem. Therefore, the global optimum can be quickly obtained using the shortest path faster algorithm. The proposed method avoids the difficulties of integer programming, and it has a lower worst-case complexity than competing methods but better robustness and tracking accuracy in complex environments. Simulation results show that the proposed algorithm takes less time than other state-of-the-art methods and can operate in real time.
BibTeX
@article{xi2014multiple,
  author = {Zhenghao Xi and Heping Liu and Huaping Liu and Bin Yang},
  title = {{Multiple Object Tracking Using the Shortest Path Faster Association Algorithm}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/481719},
}
Figure