Introduction
In crowd dynamics and safety modeling, individuals are frequently treated as independent agents. However, sociological research indicates that up to 70% of individuals in a crowd are part of small social groups, such as families or friends. These groups exhibit distinct movement patterns—maintaining proximity, matching velocities, and coordinating paths—that significantly influence overall crowd flow. Accurately identifying these groups from trajectory data is crucial for realistic simulations and effective emergency planning.
Methodology: A Two-Stage Hierarchical Approach
The researchers propose a "Top-Bottom" hierarchical clustering strategy to automatically classify small groups from raw trajectory data. This approach is designed to be more efficient than traditional "bottom-up" methods, which attempt to merge individuals into groups and often suffer from high computational complexity.
1. Top-Level Coarse-Grained Clustering
The first stage employs an improved Density Peak Clustering (DPC) algorithm. DPC identifies potential group centers by looking for points with high local density that are also relatively distant from other high-density peaks. To eliminate the need for manual input regarding the number of groups, the authors integrated a greedy strategy to automatically determine the optimal number of clusters.
2. Bottom-Level Fine-Grained Clustering
Once broad clusters are established, the algorithm refines them using an improved Hausdorff mean distance metric. This metric evaluates the similarity of the entire trajectory shape over time. By considering proximity, speed, and path similarity, the algorithm confirms whether individuals within a coarse cluster truly constitute a social group.
Computational Optimization
A key innovation in this work is the reduction of mathematical overhead. While the angle of motion is a common metric for group identification, calculating it is computationally intensive. The authors demonstrated that replacing angular calculations with "distance differences at adjacent times" maintains accuracy while significantly reducing CPU load.
Experimental Validation
The model was validated using a custom UAV Campus Dataset, consisting of high-definition video of a busy intersection near a school canteen captured by an unmanned aerial vehicle. From 67 tracked pedestrians, 55 high-quality trajectories were extracted for analysis. The algorithm's performance was benchmarked against a "ground truth" established by five independent human observers.
Results and Discussion
The proposed top-bottom algorithm achieved a 93% consistency rate with human observations, markedly outperforming standard bottom-up clustering (84%) and methods based on the Fundamental Diagram (83.6%).
The algorithm showed high stability across various crowd densities. However, performance tends to degrade when density exceeds 1 person/m², as physical constraints in bottlenecks or narrow channels force all individuals into similar trajectories, making social groups indistinguishable from the general flow.
Conclusion
This research provides a robust framework for identifying social structures within crowds. By leveraging a hierarchical approach and optimizing computational metrics, the method offers a scalable solution for real-time crowd analysis. Future work will focus on automating parameter tuning and testing the algorithm in more complex, cluttered environments such as building interiors.
Summary updated