Trajectory Pattern Identification and Anomaly Detection of Pedestrian Flows Based on Visual Clustering

Li Li, Christopher LeckieIIP 2016 · DOI

TL;DR

This paper introduces a novel visual clustering approach using contour maps and the iVAT algorithm to analyze pedestrian flow patterns. By transforming origin-destination matrices into dissimilarity matrices, the method effectively identifies both normal and anomalous pedestrian movement patterns and time periods without requiring manual parameter tuning.

What Problem Does This Paper Address?

Understanding pedestrian movement is crucial for managing public spaces, ensuring safety, and detecting unusual events. Analyzing massive trajectory datasets presents a significant challenge, particularly in identifying subtle patterns and anomalies. Existing methods often focus on individual trajectories or require extensive parameter tuning, making them less adaptable to complex, real-world scenarios. This paper aims to address this by providing a visual, parameter-free method to identify dominant pedestrian flows, cluster related areas, and detect abnormal time periods based on their movement patterns.

Methods

The core of this paper lies in its innovative application of visual clustering techniques. The authors propose:

  • Contour Maps for Visualization: Origin-destination (OD) flow matrices are visualized using contour maps. This technique helps to represent the distribution of pedestrian movement between different areas, making it easier to grasp complex flow patterns than raw numerical data.
  • iVAT Algorithm for Clustering: The improved Visual Assessment of cluster Tendency (iVAT) algorithm is employed to visually cluster areas based on their pedestrian flow relationships. iVAT works by reordering a dissimilarity matrix to reveal clusters as dark blocks along the diagonal, allowing for visual identification of groups of related areas or time periods.
  • Dissimilarity Matrix Transformation: To use iVAT, the OD flow matrix (which can be asymmetric) is first transformed into a symmetric matrix and then into a dissimilarity matrix. This transformation quantifies the "difference" in flow patterns between areas or time periods, which is then fed into the iVAT algorithm.
  • Anomaly Detection: By applying iVAT to a dissimilarity matrix of time periods, anomalous periods are identified as those that appear as singleton dark blocks, significantly differing from larger clusters of normal activity.

Datasets

The primary dataset used for evaluation is the Edinburgh informatics forum database. This dataset contains trajectory data from approximately 90,000 observed pedestrian movements over 118 days. The authors also use synthetic datasets to illustrate the effectiveness of their contour map and iVAT-based clustering methods.

Key Insights and Ideas

  • Visualizing the Unseen: Contour maps provide an intuitive way to visualize complex OD flow matrices, revealing patterns that might be missed in raw data.
  • Parameter-Free Clustering: The iVAT algorithm, when applied to the transformed dissimilarity matrices, offers a powerful, unsupervised, and parameter-free approach to clustering, simplifying the analysis process.
  • Holistic Pattern Analysis: Instead of focusing on individual trajectories, the method analyzes the overall flow patterns between areas, providing a more comprehensive understanding of pedestrian behavior.
  • Detecting Anomalies Through Deviation: Anomalies are identified not by predefined rules, but by their visual deviation from established normal patterns within the iVAT clustering output.

Key Results

The paper demonstrates the effectiveness of its proposed methods through:

  • Synthetic Case Studies: The iVAT algorithm successfully clustered related areas in synthetic scenarios, showing its ability to group areas with similar flow characteristics.
  • Real-World Data Analysis: Applying the method to the Edinburgh informatics forum dataset allowed for the identification of related areas and the clustering of time periods. For instance, the analysis of daily flow matrices revealed distinct clusters for weekdays and weekends.
  • Anomaly Identification: The method successfully identified anomalous Sundays in the Edinburgh dataset, highlighting specific days with significantly different pedestrian flow distributions compared to the average. The contour maps of these anomalous days showed distinct patterns of high and low traffic areas.

Limitations and Future Work

The authors acknowledge the following limitations and suggest future research directions:

  • Scalability: The method's scalability on extremely large datasets needs further investigation.
  • Data Stream Analysis: Modifying the proposed method to handle real-time data streams is a promising avenue for future work.

Summary updated

BibTeX
@inproceedings{li2016trajectory,
  author = {Li Li and Christopher Leckie},
  title = {{Trajectory Pattern Identification and Anomaly Detection of Pedestrian Flows Based on Visual Clustering}},
  booktitle = {IIP},
  year = {2016},
  doi = {10.1007/978-3-319-48390-0\_13},
}
Figure