# Modeling Pedestrian Motion in Crowded Scenes Based on the Shortest Path Principle
## 1 Introduction  
Crowd motion is a common phenomenon in human society, which often appears in train stations, shopping malls, street intersections and other mass events. As shown in Figure 1, a crowd usually includes a large number of individuals, and some collective patterns appear when the individuals are moving. To another point, gatherings of so many people bring potential risks to public safety, such as stampedes, terrorist attacks and so on [1, 2]. In recent years, researchers analyzed crowd motions with computer vision technology to extract real-time information for city emergency managers [3, 4, 5]. For instance, crowd collectiveness was proposed as a quantitative indicator to measure the degree of orderliness of crowd motions [6, 7]. From another perspective, abnormal behaviors were detected from crowd motions to reveal the potential hazards for social security [8, 9]. Moreover, some studies estimated the density and distribution of crowd motions to provide guidelines for designing public places [10, 11]. Describing the motions in crowded scenes is one of the core issues of crowd motion analysis in computer vision-related fields. Tracking individuals and learning motion patterns are the two traditional topics, which describe the crowd motions at the microscopic and macroscopic levels, respectively. Tracking individuals in a crowd provides an intuitive and detailed description of crowd motion. However, due to technical difficulties, tracking individuals in dense crowds still remains a relatively unexplored problem [12]. Thus, following motion patterns gives a relatively reliable result for describing crowd motion. However, instead of the entire moving process, motion patterns just describe the rough motion tendency of individuals. To combine the advantages of the above two strategies, [PERSON] et al. proposed a mixture model of dynamic pedestrian agents (MDA) to build themotion models of pedestrians in a crowd [13]. Motion models of pedestrians have many significant applications. For example, given a motion model, a crowd's motion can be described with only a few parameters. Consequently, we can simulate the pedestrians' motions with partially observed trajectories. Additionally, the motion models can be applied to traffic flow statistics, crowd motion simulation and so on. MDA is an agent-based model that treats the pedestrians as dynamic pedestrian-agents and uses the affine transformation matrix as the control rule to drive the agent. However, a single matrix can not accurately model the complicated movements of a pedestrian. In this work, we revisit the related work in social psychology to summarize the rules governing pedestrian motions. Sociologists indicated that pedestrians always take the shortest possible paths to reach a certain destination, and we call this \"shortest path principle.\" In crowd motions, the collective wills of pedestrians reinforce the shortest path principle. The motion of a pedestrian consists of three basic elements: origin, destination, and the movement path from the origin to the destination. Based on the shortest path principle, we propose a two-part motion model to describe these basic elements of pedestrian motions. One part estimates the probability of a pedestrian reaching each candidate pair of origin and destination, and the other generates the movement path of a pedestrian between any two points in the scene. We use the trajectories of feature points obtained by the Kanade-Lucas-Tomasi (KLT) tracker as the observations of pedestrian motions. In this paper, we first build a shortest path graph according to the trajectories of feature points. Based on the shortest path principle, this graph can be used to generate the movement path of a pedestrian between any two points in the scene. Then, we quantify the shortest path principle as the shortest path likelihood. Combined with the connectivity between trajectories, we propose a generalized path likelihood to estimate the probability of the trajectory reaching each candidate pair of origin and destination.