Video surveillance and multimedia forensics: an application to trajectory analysis

Simone Calderara, Andrea Prati, Rita CucchiaraMiFor@MM 2009 · DOI

TL;DR

This paper introduces a novel multimedia forensics tool that combines advanced video surveillance with trajectory analysis to automatically extract and compare people's movement patterns. By modeling trajectories as sequences of spatial positions or angular directions, the system enables efficient searching and clustering of large video archives, significantly aiding investigations.

What Problem Does This Paper Address?

Investigating crime scenes often involves sifting through vast amounts of video data, a process that is time-consuming and labor-intensive. Traditional digital forensics relies heavily on manual intervention and specialized tools for tasks like facial recognition. However, there's a growing need for automated methods to analyze human behavior within video streams, particularly for identifying patterns and anomalies. This paper addresses the challenge of efficiently searching and understanding complex human movement in surveillance footage by developing a robust trajectory analysis framework that can be integrated into multimedia forensic workflows.

Methods

The core of this work lies in modeling and comparing people's trajectories extracted from multi-camera surveillance systems. The authors propose two primary representations for trajectories:

  • Spatial Model: Trajectories are represented as sequences of 2D coordinates (x, y) projected onto the ground plane. To handle noise and minor inaccuracies in tracking, each data point is modeled by a Gaussian distribution centered on its coordinates. This creates an "envelope" around the trajectory, providing some invariance to small spatial shifts. The trajectory is then represented as a sequence of these Gaussian symbols.
  • Angular Model (Shape Analysis): Trajectories are converted into sequences of angles representing the direction of movement between consecutive points. This representation focuses on the "shape" of the trajectory, independent of its absolute location. The von Mises distribution, a circular statistical model, is used to represent these angles, and a mixture of von Mises distributions is employed to capture multi-modal directional behaviors.

For comparing these symbolic trajectory representations, the authors adapt techniques from bioinformatics, specifically the global alignment algorithm (Needleman-Wunsch). This algorithm allows for inexact matching, accounting for variations in trajectory length, small temporal shifts, and partial similarities. A Bhattacharyya coefficient is used to measure the similarity between individual spatial Gaussian distributions or angular von Mises distributions, which then informs the symbol-to-symbol similarity score used in the alignment.

Finally, the system employs a k-medoids clustering algorithm to group similar trajectories. This algorithm identifies representative "medoids" for each cluster, allowing for efficient representation of common behaviors and reducing the computational cost of querying large datasets. An iterative merging strategy is used to automatically determine the optimal number of clusters.

Datasets

The paper mentions using a training set of 900 trajectories acquired during an ordinary working day from a two-camera setup on their campus. This dataset was used for learning the most frequent behaviors and for clustering. No new benchmark datasets were introduced.

Key Insights and Ideas

  • Trajectory as a Rich Forensic Feature: Movement patterns (trajectories) are highly informative for forensic analysis, revealing not just where someone went but potentially how they moved, which can indicate intent or behavior.
  • Bridging Surveillance and Forensics: The paper effectively bridges the gap between real-time surveillance needs (detecting specific events) and forensic requirements (detailed analysis and searching of historical data).
  • Robustness through Statistical Modeling: Using Gaussian and von Mises distributions makes the trajectory representation robust to noise and inaccuracies inherent in video tracking systems.
  • Bioinformatics for Trajectory Comparison: Adapting sequence alignment algorithms from bioinformatics provides a powerful and principled way to compare trajectories, even when they are not perfectly identical.
  • Clustering for Efficient Querying: K-medoids clustering transforms a potentially overwhelming one-to-many comparison problem into a more manageable one-to-few comparison against cluster prototypes, significantly speeding up queries.

Key Results

The paper demonstrates the system's ability to:

  • Cluster trajectories based on both spatial location and shape, revealing common movement patterns in a surveillance scenario.
  • Visualize frequent behaviors, showing how the system can synthesize complex video data into understandable patterns.
  • Facilitate forensic queries by allowing users to search for trajectories based on shape and then filter by location, as illustrated in Figure 4. This enables retrieving specific people snapshots and trajectory information relevant to an investigation.

Quantitative results (e.g., specific accuracy metrics or speedup figures) are not explicitly detailed in the provided text, but the qualitative results and the proposed framework highlight the potential for significant improvements in investigation efficiency.

Limitations and Future Work

  • Choice of 'k' in Clustering: The authors acknowledge that the choice of the number of clusters ('k') is a limitation of k-means/k-medoids. They propose an iterative merging strategy to address this, but it's an area that could be further explored.
  • Computational Complexity: While dynamic programming is used to reduce complexity, the global alignment algorithm can still be computationally intensive for very long trajectories.
  • Future Work: The authors suggest that more information could be incorporated into the model to extend the range of possible queries. This could include integrating other types of data or developing more sophisticated similarity measures. The potential for extending this to real-time anomaly detection based on deviations from learned frequent behaviors is also implied.

Summary updated

BibTeX
@inproceedings{calderara2009video,
  author = {Simone Calderara and Andrea Prati and Rita Cucchiara},
  title = {{Video surveillance and multimedia forensics: an application to trajectory analysis}},
  booktitle = {MiFor@MM},
  year = {2009},
  doi = {10.1145/1631081.1631085},
}
Figure