<title>Globally optimum multiple object tracking</title>

Ismail Oner Sebe, Suya You, Ulrich NeumannProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2005 · DOI

TL;DR

This paper introduces a modified Multiple-Hypothesis Tracking (MHT) algorithm, called Combinatorial MHT (CMHT), to address the challenge of globally optimal multiple object tracking, particularly in scenarios involving occlusions. CMHT effectively models object interactions like splitting and merging, approximating a globally optimal solution in polynomial time.

What Problem Does This Paper Address?

Accurate tracking of multiple objects in video surveillance is a significant challenge. Existing algorithms often struggle with:

  • Misidentification: Confusing one object for another.
  • Occlusions: Interactions between objects, where one temporarily hides another, leading to tracking errors.
  • Computational Complexity: Achieving a globally optimal solution for object assignment is an NP-Complete problem, making it computationally infeasible for real-time applications.

This paper aims to overcome these limitations by providing a robust and efficient method for tracking multiple objects, even when they interact and occlude each other.

Methods

The core of the proposed solution is a modified Multiple-Hypothesis Tracking (MHT) algorithm, termed Combinatorial MHT (CMHT). The key innovations include:

  • Five Object States: The system defines five states for tracked objects: appear, disappear, track, split, and merge. These states comprehensively cover object lifecycle and interactions, including occlusions.
  • Resemblance Matrix: A resemblance matrix ($R$) is computed between detected objects in the current frame and previously tracked objects. This matrix quantifies the similarity between object pairs.
  • State-Likelihood Matrix: The 2D resemblance matrix is converted into a 3D state-likelihood matrix ($C$). This matrix incorporates the likelihood of each of the five states for object pairs or triplets, effectively modeling complex interactions like splitting and merging.
  • CMHT Algorithm: A modified MHT algorithm is used to solve the state-assignment problem in this 3D space. CMHT approximates a globally optimal assignment by exploring multiple hypotheses, thus avoiding local minima that can plague simpler assignment methods.
  • Polynomial Time Approximation: By using MHT, the algorithm approximates a globally optimal solution in polynomial time, making it suitable for real-time applications.
  • Finite State Machine (FSM): A FSM is used for temporal coherence, ensuring smooth transitions between object states and preventing abrupt changes.

Datasets

The paper evaluates the proposed algorithm on:

  • Synthetic sequences: Used to demonstrate tracking under perfect segmentation and controlled occlusion scenarios, serving as ground truth.
  • Real-world video sequences: Specifically, an outdoor scene with numerous occlusions, composed of 1500 RGB frames of size 360x240.

No new benchmarks were introduced; the focus was on evaluating the algorithm's performance on existing data types.

Key Insights and Ideas

  • Modeling Occlusions Explicitly: The introduction of "split" and "merge" states is crucial for handling occlusions. This proactive modeling allows the system to anticipate and manage these interactions, rather than just reacting to them.
  • 3D State-Likelihood for Assignment: Converting the 2D resemblance into a 3D state-likelihood matrix is a clever way to incorporate complex interaction information (like triplets for split/merge) into the assignment problem, enabling a more comprehensive solution.
  • MHT for Global Optimality Approximation: Leveraging MHT's ability to explore multiple hypotheses is key to approximating a globally optimal assignment without the prohibitive computational cost of exhaustive search. This is particularly important for the NP-Complete nature of the assignment problem.
  • Generality of the Approach: The method is designed to be non-model based, meaning it doesn't require prior knowledge of object shapes or types, making it applicable to a wide range of objects and scenarios.

Key Results

  • The CMHT algorithm successfully tracks multiple objects through full and semi-occlusions in both synthetic and real-world sequences.
  • The system demonstrates the ability to maintain object identities and states even after occlusions.
  • The tracker achieves an average speed of around twenty frames per second on a 2.6GHz Pentium IV computer for sequences with approximately ten objects on 360x240 RGB images.
  • The paper highlights that detection errors (e.g., due to clothing color similar to the background) are a significant source of tracking failure, rather than inherent flaws in the tracking algorithm itself.

Limitations and Future Work

  • Limited to Two Objects at a Time: The current formulation primarily handles occlusions involving at most two objects. If three or more objects occlude each other, the algorithm may drop one object.
  • Future Work:
    • Recursive Formulation: Extend the CMHT to handle occlusions involving more than two objects recursively.
  • Multiple Hypotheses for Merge State: Implement multiple hypotheses specifically for the merge state to better model scenarios like objects stopping together or one joining another's movement.
  • N-Scan Back: Incorporate an "N-scan back" approach to allow MHT to consider hypotheses over time, not just within a single frame, to resolve ambiguities that take multiple frames to clarify.
  • Learning Thresholds: Explore learning thresholds for state transitions from data rather than manually setting them.

Summary updated

Abstract

Robust and accurate tracking of multiple objects is a key challenge in video surveillance. Tracking algorithms generally suffer from either one or more of the following problems, excluding detection errors. First, objects can be incorrectly interpreted as one of the other objects in the scene. Second, interactions between objects, such as occlusions, may cause tracking errors. Third, globally-optimum tracking is hard to achieve since the combinatorial assignment problem is NP-Complete. We present a modified Multiple-Hypothesis Tracking algorithm, MHT, for globally optimum tracking of moving objects. The system defines five states for tracked objects: appear, disappear, track, split, and merge, and these states cover all the interactions of object pairs. After the detection of objects in the current frame, a resemblance matrix is computed for every object pair. We convert the two-dimensional resemblance matrix into a three-dimensional state-likelihood structure and use a MHT technique to solve the state-assignment problem in 3D. This prevents incorrect assignments due to local minima in the assignment process. Moreover, the method models occlusion cases with the split and merge states. Finally, this method approximates a globally optimum state assignment in polynomial time complexity.
BibTeX
@inproceedings{sebe2005lt,
  author = {Ismail Oner Sebe and Suya You and Ulrich Neumann},
  title = {{\<title\>Globally optimum multiple object tracking\</title\>}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2005},
  doi = {10.1117/12.603210},
}

Loading related content...

Figure