Pedestrian Motion Model Using Non-Parametric Trajectory Clustering and Discrete Transition Points

Yutao Han, Rina Tse, Mark E. Campbell

TL;DR

This paper introduces a novel data-driven pedestrian motion model that captures both low-level trajectory patterns and high-level discrete decision points. By iteratively clustering trajectories and identifying transition points, the model achieves accurate online prediction of pedestrian movement and robust anomaly detection, outperforming traditional methods.

What Problem Does This Paper Address?

Predicting pedestrian behavior is crucial for various robotics applications, from surveillance and search-and-rescue to autonomous driving and personal robotics. While existing systems can track multiple pedestrians, they often lack the ability to infer deeper insights into pedestrian intent, motivations, or potential anomalies. Current data-driven models, while flexible, often struggle to capture the high-level discrete decisions pedestrians make (like choosing a path at an intersection) alongside their continuous motion. This paper aims to bridge this gap by developing a model that integrates both low-level trajectory details and high-level behavioral transitions, enabling more comprehensive reasoning and prediction.

Methods

The core of the proposed model is an iterative, non-parametric clustering algorithm that combines two key components:

  • Dirichlet Process Gaussian Processes (DPGP) for Trajectory Clustering: This technique is used to automatically discover and cluster trajectories into distinct "motion patterns." DPGP is powerful because it doesn't require pre-specifying the number of clusters, allowing the model to adapt to the complexity of the data. The GP models the velocity distribution of trajectories within a cluster. A novel weighting term is introduced to the GP likelihood to address the "planar shift problem," improving positional accuracy.
  • Hypothesis Testing for Transition Point Estimation: This method identifies "transition points" – spatial areas where pedestrians make discrete decisions, such as branching or merging paths. By comparing motion patterns, the algorithm tests for shared sub-trajectories and identifies points where these patterns diverge or converge. These transition points are then modeled using normal distributions.

These two components are integrated into an iterative process. First, DPGP clusters trajectories. Then, hypothesis testing identifies potential transition points. If transition points are found, trajectories are split into sub-trajectories, and the clustering process is repeated. This iterative refinement allows the model to discover both low-level motion patterns and high-level transition points simultaneously. Finally, transition probabilities between these states (motion patterns and transition points) are learned to form a Transition Probability Matrix (TPM).

Datasets

  • Simulated Data: Used to demonstrate the robustness of the iterative clustering algorithm to anomalous data and to visualize the model's behavior. The paper mentions adding up to 30% anomalies to a simulated dataset.
  • Duke MTMC Dataset: This dataset, containing eight annotated videos of pedestrians on the Duke University campus, is used for evaluating the model's online prediction accuracy and anomaly detection capabilities. The data was down-sampled to 2 fps.

Key Insights and Ideas

  • Bridging Low-Level and High-Level Behavior: The most significant insight is the successful integration of continuous trajectory patterns with discrete decision points. This dual-level representation provides a richer understanding of pedestrian behavior than models focusing on only one aspect.
  • Automatic Discovery of Model Complexity: The use of DPGP for clustering and hypothesis testing for transition points means the number of motion patterns and transition points is not fixed beforehand. The model automatically adapts its complexity to the data, which is a significant advantage over methods requiring manual parameter tuning for cluster counts.
  • Iterative Refinement for Robustness: The iterative nature of the clustering and transition point discovery process allows the model to refine its understanding of both motion patterns and decision points, leading to more accurate representations.
  • Online Adaptability: The model is designed for online application, meaning it can process new, incoming trajectory data in real-time to make predictions and detect anomalies without needing to retrain on the entire dataset.

Key Results

  • Prediction Accuracy: The proposed model achieved an average prediction accuracy of 95% on the Duke MTMC dataset, significantly outperforming a constant velocity baseline (39%).
  • Transition Prediction Time (TPT): The model accurately predicts the next transition point within an average of 1.1 seconds (approximately 2.2 time steps), which is fast enough for online applications.
  • Anomaly Detection: The model demonstrates high accuracy in detecting anomalous trajectories, with an average correct anomaly detection rate of 95% and a standard deviation of 3%. It can also identify which parts of a trajectory are anomalous.
  • Robustness to Anomalies: The iterative clustering algorithm showed robustness to anomalous data, with an error of only 9.1% when trained on a dataset with 30% anomalies. The presence of outliers did not significantly affect the discovery of underlying motion patterns.

Limitations and Future Work

  • Model Complexity: The most computationally intensive part of the offline model training is trajectory clustering, which has a complexity of O(N³) (reduced to O(N) with Cholesky decomposition). While feasible for implementation, this could be a bottleneck for very large datasets.
  • Online Processing Time: The online processing of each sliding window takes an average of 0.63 seconds, which is considered feasible but could potentially be further optimized for real-time applications requiring extremely low latency.
  • Future Work: The paper suggests that the developed model is a powerful tool for various applications, including mobile robot path planning and intersection autonomous driving. Further exploration of these applications and potential optimizations for even faster online processing would be logical next steps.

Summary updated

Abstract

This paper presents a pedestrian motion model that includes both low level trajectory patterns, and high level discrete transitions. The inclusion of both levels creates a more general predictive model, allowing for more meaningful prediction and reasoning about pedestrian trajectories, as compared to the current state of the art. The model uses an iterative clustering algorithm with (1) Dirichlet Process Gaussian Processes to cluster trajectories into continuous motion patterns and (2) hypothesis testing to identify discrete transitions in the data called transition points. The model iteratively splits full trajectories into sub-trajectory clusters based on transition points, where pedestrians make discrete decisions. State transition probabilities are then learned over the transition points and trajectory clusters. The model is for online prediction of motions, and detection of anomalous trajectories. The proposed model is validated on the Duke MTMC dataset to demonstrate identification of low level trajectory clusters and high level transitions, and the ability to predict pedestrian motion and detect anomalies online with high accuracy.
BibTeX
@article{han2019pedestrian,
  author = {Yutao Han and Rina Tse and Mark E. Campbell},
  title = {{Pedestrian Motion Model Using Non-Parametric Trajectory Clustering and Discrete Transition Points}},
  journal = {IEEE RA-L},
  year = {2019},
  doi = {10.1109/lra.2019.2898464},
}
Figure