Tracking Many Objects with Many Sensors

Hanna Pasula, Stuart Russell, Michael Ostland, Yaacov RitovIJCAI 1999

Abstract

This paper presents a scalable framework for tracking multiple objects across extensive sensor networks. By transitioning from traditional pairwise appearance models to a latent "intrinsic property" approach, the authors address the computational and robustness issues inherent in large-scale data association. The method utilizes Markov Chain Monte Carlo (MCMC) for identity estimation and an online Expectation-Maximization (EM) algorithm for real-time model learning, demonstrating high accuracy even in the presence of significant sensor noise.

The Challenge of Data Association

The fundamental problem in multi-object tracking is data association—correctly identifying whether an observation at one sensor corresponds to an object previously seen elsewhere. In environments like freeway surveillance, this task is complicated by sensor noise, visual similarities between objects, and unpredictable traffic patterns.

Traditional "appearance-based" models rely on pairwise comparisons between sensors (e.g., Camera A to Camera B). However, these models are fragile; if an intermediate sensor in a chain fails or produces high-noise data, the link is broken, and the system loses the object's identity. Furthermore, the computational complexity of exact association grows exponentially with the number of sensors and objects, making it #P-complete and practically intractable for large systems.

A multi-sensor tracking scenario where vehicles move through a sequence of cameras (A, B, C).

Proposed Methodology

The authors introduce two major innovations to solve the scaling and noise problems:

1. Spatial Decomposition via Intrinsic Properties

Instead of direct sensor-to-sensor comparison, the framework models the "true" underlying properties of an object (e.g., its actual color, length, or width) as latent intrinsic variables. Observations at different cameras are treated as conditionally independent measurements of these hidden states. This allows the system to "remember" what a vehicle looks like even if an intermediate sensor provides poor data, maintaining track continuity across the entire network.

2. MCMC-based Inference and Online EM

To handle the computational complexity, the authors employ Markov Chain Monte Carlo (MCMC) to sample the most likely identity assignments. A key mechanism is the "swap" proposal: the algorithm randomly picks two vehicle trajectories and swaps their identities to see if it improves the global probability. This allows for a polynomial-time approximation of the association problem.

The MCMC swap proposal: exchanging identities between two vehicle trajectories to explore the assignment space.

Simultaneously, an Online EM algorithm uses these MCMC samples (the E-step) to update models of sensor behavior and vehicle dynamics (the M-step) in real-time as new data arrives.

Experimental Results

The study utilized the "BATmobile" freeway traffic simulator to test the framework across various network configurations, including a complex nine-camera setup.

  • Robustness to Noise: In a three-camera chain where the middle camera was intentionally noisy, the MCMC/Intrinsic property approach maintained nearly 100% accuracy. In contrast, traditional pairwise methods saw accuracy plummet to ~20% as noise increased.
  • Origin-Destination (O-D) Counts: The algorithm significantly outperformed baselines in estimating aggregate traffic statistics. Even when visual noise was high enough to obscure individual matches, the MCMC approach recovered accurate counts of vehicles traveling between specific entrances and exits.

Conclusion and Future Work

By decoupling observations through latent intrinsic properties and utilizing efficient MCMC sampling, this work provides a robust and scalable solution for multi-sensor tracking. While the current model assumes Gaussian noise and known dynamics, future work aims to validate these findings on real-world data from the Berkeley Roadwatch project and extend the framework to handle missing observations and more complex motion models.

Summary updated

BibTeX
@inproceedings{pasula1999tracking,
  author = {Hanna Pasula and Stuart Russell and Michael Ostland and Yaacov Ritov},
  title = {{Tracking Many Objects with Many Sensors}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure