Harnessing Fourier Isovists and Geodesic Interaction for Long-Term Crowd Flow Prediction

1 Introduction

In the present day, more than half of the world's population resides in the built environments of urban areas, and by 2050, this proportion is expected to reach as high as 68% [DESA, 2018]. Accordingly, it is nowmore important than ever to advance the modeling of human navigation within built environments. This would directly benefit application domains such as architectural design [Turner and Penn, 2002], transportation engineering [Sewall et al., 2010], and crowd management [Bohannon, 2005], which are all crucial to maintaining people's safety on a daily basis. The failure for a built environment to do so is caused or signaled by overcrowding and can result in injuries for its occupants [Zhen et al., 2008].

∗Contact Author

In order to measure the risk of overcrowding in an environment, we use long-term crowd flow, i.e., the timeaggregated spatial distribution of footfall during a crowd's movement [Sohn et al., 2020], either computed from real trajectory data or predicted (Figure 1). Until recently, longterm crowd flow prediction (LTCFP) could only be done by first predicting the trajectories of agents in a crowd using either simulation models [Helbing and Molnar, 1995] from Computer Graphics literature or Human Trajectory Prediction (HTP) models [Alahi et al., 2016] from Computer Vision literature. This general approach does not scale well to large crowds and environments, and we later show that HTP models are fundamentally unsuitable for LTCFP (Sec. 7.1). On the contrary, CAGE [Sohn et al., 2020], the recent state-ofthe-art (SOTA) framework, directly addresses LTCFP without considering individual agents of the crowd, making it inherently scalable to large crowds (but not necessarily to large environments).

However, CAGE faces three major challenges that hinder its generalizability. (1) Its environment representation is highly lossy when encoding environments with large size or complex geometry, such as angles and curves. (2) Its predictive model is unable to make accurate predictions for such environments. (3) The only existing LTCFP dataset is unsuitable for evaluating the scalability of models to large environments [Sohn et al., 2020]. To address these challenges, we first contribute Fourier Isovists, a novel egocentric visibility representation of environments that uses additional channels to encode more spatial information at each cell. We then frame LTCFP as a super-resolution problem to exploit the extra information in Fourier Isovists and propose GeoInteractNet (GINet) to improve performance in this new framework using domain knowledge. Finally, we have generated a new synthetic crowd dataset with both real and synthetic environments to evaluate the scalability of CAGE and the proposed methodology.

2 RelatedWork

Simulation models have been developed over the past 2 decades by the Computer Graphics community. These models are typically hand-crafted to produce specific phenomena about real crowd movement, such as social interactions [Helbing and Molnar, 1995] and collision avoidance [Van Den Berg et al., 2011]. While these models are highly robust, they are only accurate with respect to real data at a high level (e.g. the rate of agent flow) since they have very few tunable parameters. In order to make long-term predictions, these models simulate each agent's movement one small step at a time. The robustness of this method has led to its adoption in application domains, but its inaccuracy and inefficiency leave much room for improvement.

On the other hand, Human Trajectory Prediction (HTP) models were introduced 5 years ago by the Computer Vision community. These models are data-driven and learn shortterm trajectory distributions based on datasets of real human trajectories [Alahi et al., 2016; Gupta et al., 2018]. In contrast to crowd simulation models, HTP models have many learnable parameters and are more accurate with respect to real data than simulation models at a low level (e.g., shortterm motion statistics) [Sohn et al., 2021]. However, successive short-term predictions from these models compound error over time [Salzmann et al., 2020], meaning that they cannot reliably make long-term predictions and are thereby inaccurate at a high level. These models are also unable to avoid collisions with other agents or obstacles in the environment despite conditioning their predictions on this very information [Sohn et al., 2021]. While HTP models show promise, they have not yet taken the place of simulation models in application domains.

These prior works are iterative and agent-centric in nature, meaning that they scale poorly to large crowds and environments. The SOTA CAGE framework showed for the first time that accurate and efficient predictions of long-term crowd flow could be made in an instantaneous and environmentcentric fashion by treating LTCFP as a vision problem and leveraging convolutional neural networks [Sohn et al., 2020]. The contributions of this work are in addressing CAGE's key limitations and advancing LTCFP, which fulfills a unique role in the analysis of crowd movement that simulation and HTP models are ill-suited to conduct due to their inaccuracy and inefficiency.

3 ProblemDefinition

LTCFP is defined as the prediction of a crowd flow map Y1×n×n using the initial state of a crowd and environment X4×n×n (i.e., the crowd scenario), where both the input and output are represented as images with the same top-down orthogonal perspective of a ns × ns m2 environment and s is a fixed scale across all environments. The crowd flow map Y is computed by the log transform of a crowd's cumulative footfall while moving from its initial configuration to a shared goal position, where footfall is measured at 50 Hertz. The assumption of a shared goal makes LTCFP applicable to ingress and egress scenarios, which are of interest to application domains. The crowd scenario X = ⟨C,A,G,E⟩ contains the following channel information at each pixel (i, j): Ci,j ∈ {1} is its amount of environment Compression (initially 1), Ai,j ∈ {0, 1} is whether an Agent is occupying it, Gi,j ∈ [0, 1] is its normalized distance to the Goal, and Ei,j ∈ {0, 1} is its navigability in the Environment. In order to leverage a convolutional encoder-decoder network, the CAGE framework compresses X, which varies in spatial size with the environment, intoX′4×n′×n′ as input to the network, where n′ is fixed. 1 The network's prediction ̂Y′1×n′×n′ is then bilinearly interpolated to ̂Y1×n×n.

By fixing n′ and compressing any environment with n > n′ , the accuracy of models is inherently limited and their predictions must be upscaled to ̂Y. Our proposed changes to this framework are (1) to compress the raw input into X′d×n′×n′ | d ≥ 4 with additional channels to store more environment information and (2) to use the extra channels for predicting a super-resolution ̂Y′1×m×m, where m is a fixed value greater than n′ by a factor of 2c | c ≥ 1 (Figure 1). The proposed framework anticipates that n may be higher than n′ and compensates for it by a factor of 2c , meaning that for any environment up to 2c larger than n′ , the resolution of the prediction is not a limiting factor and the prediction must be downscaled to ̂Y. We have set n′ = 64 and m = 256 according to our dataset.

1 Matrices with fixed spatial size are denoted by ′ .

4 Crowd and Environment Representations

We propose several novel representations of X′ = ⟨C′ ,A′ ,G′ ,E′ ⟩ for predicting the crowd flow ̂Y′ and compare them to the SOTA representation. All representations share the same compression, agent, and goal channels, but encode environment information E′ differently. A′ and G′ are computed by bilinearly interpolating A and G, and each cell of C′ takes the value of n′ /n. The environment representations can be divided into three categories: image, isovist, and joint image-isovist representations.

Image Representations (BODI and CODI). Image representations encode the environment as a single-channel image. CAGE uses a binary image representation that losslessly and non-uniformly compresses rectangular regions in environments with axis-aligned geometry [Sohn et al., 2020]. However for large and complex environments it becomes equivalent to bilinearly interpolating E to E′ and thresholding each pixel at 0.5, which is highly lossy. We use this Binary One-Dimensional (BODI) representation E′ ∈ {0, 1}1×n′×n′ as the baseline. The proposed Continuous One-Dimensional (CODI) representation E′ ∈ [0, 1]1×n′×n′ is also computed by interpolating the environment, but unlike BODI, its values are not thresholded (Figure 1).

Isovist Representations (RI and FI). The proposed isovist representations E′ ∈ Rr×n′×n′ encode egocentric visibility information along a uniform grid of n′ × n′ viewpoints across the environment. At each viewpoint, a 360◦ visibility polygon (i.e., an isovist [Benedikt, 1979]) is computed and then converted into an r-dimensional feature vector along the channel dimension, where r = 60. If the viewpoint is in a non-navigable space, the isovist is represented by a zero vector. The incorporation of isovists is motivated by prior studies, which have evidenced that human navigational behavior in indoor environments is strongly correlated with isovists [Wiener et al., 2007; Wiener and Franz, 2004]. Furthermore, isovists cannot normally be learned by convolutional neural networks, because they can gather visibility information from long distances that well-exceed reasonable kernel sizes, e.g., an isovist at one end of a long hallway encodes information at the opposite end.

The Raw Isovist (RI) representation computes the isovist's feature vector using a viewpoint distance function [Zhang et al., 2002], which casts r equiangular rays (i.e., sightlines) from the viewpoint and encodes the length of each ray when it hits the contour of the isovist. This makes RI well-suited for encoding angular geometries. On the other hand, the Fourier Isovist (FI) representation computes the isovist's feature vector as the first r4 -harmonics of elliptic Fourier features [Kuhl and Giardina, 1982]. The first harmonic represents the ellipse that best fits the contour, and each subsequent harmonic represents an ellipse that rolls around the previous harmonic's ellipse, capturing increasingly fine-grained details in a multiscale manner. These elliptic features make FI well-suited for encoding curved geometries. Figure 1 shows incremental reconstructions of the first 15 harmonics for an example E. Further analysis of RI and FI can be found in the Supplementary Materials.

Joint Representations (CODIRI and CODIFI). While isovist representations can encode significantly more information than image representations, they are limited by visibility, meaning that image representations can provide key information unseen by isovists. The proposed joint imageisovist representations E′ ∈ R61×n′×n′ concatenate image and isovist representations along the channel dimension, taking advantage of their respective strengths. In particular, we favor CODI as the image part of the joint representation since it encodes more information than BODI, and we use either RI or FI for the isovist part since they are complementary to each other with respect to the geometry that they encode well. This results in the joint representations CODIRI and CODIFI, which concatenate CODI with RI and FI respectively (Figure 1).

5 Modeling

We first investigate how several existing convolutional encoder-decoder (CED) networks perform LTCFP when adapted to the proposed super-resolution framework: SegNet [Badrinarayanan et al., 2017], U-Net [Ronneberger et al., 2015], Attention U-Net [Oktay et al., 2018]. Since the these models were designed for image segmentation, we first replace the final softmax layer of each model with a 1 × 1 convolution layer followed by a sigmoid layer for regression. Then, in order for these models to predict a m× m output (m = 256) from a n′ × n′ input (n′ = 64), we add two up-convolution blocks to the decoder prior to the final layer. Each up-convolution block consists of a transposed convolution layer followed by 2 sequences of convolutional, batch normalization, and ReLU activation layers. The transposed convolution layers in these blocks use 4×4 kernels with stride = 2 and padding = 1, and all other convolution layers utilize 3 × 3 kernels with stride = 1 and padding = 1.

5.1 GeoInteractNet (GINet)

Although using additional up-convolution blocks will inherently produce higher-resolution predictions, the feature maps that the existing CED networks normally use to feed highresolution spatial information to their decoders are missing for the additional blocks, hindering the learning of finegrained details in super-resolution. Therefore, we propose GeoInteractNet (GINet), a model coupling a Multi-SCale Attention Network (M-SCAN) and a CED prediction network in parallel (Figure 2). M-SCAN first feeds X into a Geodesic Interaction Module to generate a super-resolution geodesic interaction map I ∈ R1×m×m, which approximates human interaction along the shortest paths to the goal (i.e., geodesic paths). For each individual in the crowd A, the Geodesic Interaction Module computes the geodesic path along G and encodes it as a m × m binary path image, in which pixels along the geodesic path are 1. I is then computed as the normalized sum of all path images, where values close to 1 indicate the potential for interactions between individuals.

M-SCAN then inputs I into the Attention U-Net architecture [Oktay et al., 2018]. The architecture of the prediction network parallels that of M-SCAN, but the first two encoder blocks are removed in order to accept X′ as input (Figure 2). In order to pass information from M-SCAN to the prediction network, we use a mix of attention gates [Oktay et al., 2018], unary coded gates, and ternary coded gates. The first 4 encoder blocks in the prediction network are connected to matching encoder blocks in M-SCAN through unary coded gates υ (Figure 2).

where Me is the b-channel output from M-SCAN's encoder block, W ∈ Rb×1 is a 1×1 convolution, and c ∈ {0, 1} is a hyperparameter that determines whether the gate is enabled. The output of υ is concatenated to the input of the prediction network's encoder block. The first 4 decoder blocks in the prediction network upscale their outputs Pd to match the sizes of corresponding encoder blocks Pe in the prediction network and decoder blocks Md in M-SCAN. All three blocks' outputs have b channels and are passed to a ternary coded gate τ (Figure 2).

whereW1,W2,W3 ∈ Rb×b/2 andW4 ∈ Rb/2×1 are a 1×1 convolutions, σ1 is a ReLU activation, σ2 is a sigmoid activation, and c ∈ {0, 1} is a hyperparameter that determines whether the gate uses feature maps from the prediction network's encoder or M-SCAN's decoder. The 1-channel result of τ is duplicated to b channels, element-wise multiplied with Pe, and then concatenated to Pe as input to the next decoder block in the prediction network. The final 2 decoder blocks in the prediction network use Attention U-Net's attention gates. However, since there are not matching encoder blocks in the prediction network, the attention gates use matching decoder blocks from M-SCAN (Figure 2).

In sequential order, the unary and ternary coded gates can be hyperparameterized by a byte c ∈ {0, 1}8 , where the ith coded gate is parameterized by the bit ci. We investigate 10 variants of GINet, e.g., GINet[00001111], which disables all unary coded gates and enables all ternary coded gates.

6 Experimental Preliminaries

LTCFP is most suited for quickly assessing the risk of overcrowding in situations with large crowds and environments, meaning that training LTCFP models inherently requires ground truth data with overcrowding. There are obvious logistical and ethical concerns that prohibit the acquisition of such data with real humans at a large enough scale to use for training. Therefore, we rely on the same solution as practitioners in application domains [Ma and Yarlagadda, 2015], which is to simulate crowds using the Social Force model [Helbing and Molnar, 1995]. The same model was used by the only existing LTCFP dataset [Sohn et al., 2020], but our datasets include more varied synthetic environments, larger simulated crowds, and large real environments.

Small and Large Synthetic Environment Datasets. The 2 synthetic datasets consists of 8,000 total training and 2,400 total testing crowd scenarios with thousands of unique synthetic environments. In order to represent the variety of real environments, we have extended the procedural method from [Sohn et al., 2020] to generate 48 unique types of environments, featuring different combinations of 2 sizes (64×64 and 224×224 m2 ), 3 types of exterior shapes, 4 types of corridor arrangements, and either curved or axis-aligned geometry. The size determines whether the environment is in the small or large synthetic dataset. Each generated environment was used to simulate two crowd scenarios with a low (5%) and high (20%) chance of initializing an agent for each navigable cell in the environment, which affects the amount of overcrowding. Both scenario types tasked their crowds with navigating to a single random goal location, and after every agent reached the goal, the ground truth crowd flow map was computed.

Small and Large Real Environment Datasets. The large real dataset contains 12 floorplans of environments that vary in terms of function (e.g., railway stations, hospitals, and shopping centers) and locality (e.g., Austria, China, and Germany). Each environment was scaled to 224 × 224 m2 and used to simulate 100 crowd scenarios at 5% occupancy, yielding a total of 1,200 crowd scenarios. The small real dataset consists of 1,500 crowd scenarios produced using real human trajectories from two regions in a 64 × 64 m2 train terminal [Alahi et al., 2014], where each scenario involves at least 30 people simultaneously moving toward the same location. We do not consider this as an LTCFP dataset because its environment and crowds are too small to require LTCFP in practice. The small real dataset's crowds have tens of real humans while the other datasets have hundreds or thousands of agents. However, this dataset strikes a balance between the needs of HTP models and LTCFP models, making it useful for evaluating the whether HTP models can be used for LTCFP. Given the small number of real environments, we reserve both real datasets for testing only.

Training Protocol. Adam optimization [Kingma and Ba, 2014] was used for training U-Net, Attention U-Net, and GINet, while stochastic gradient descent was used for CAGE and SegNet (with momentum = 0.9). Prior to training, the data was shuffled, and the batch size was set to 4. All models were then trained exclusively on both synthetic datasets for 100 epochs with a learning rate of 0.01 from {0.1, 0.01, 0.001}, which performed best across models. The loss function was set to Mean Absolute Error (MAE), which performed better than Mean Squared Error and Binary CrossEntropy Loss. After training, these models were tested on the synthetic datasets and both real datasets, which were never seen during training. A machine with an Intel Core i9-9960X 3.10 GHz, 64GB RAM, and an NVIDIA GeForce RTX 2080 Ti 11GB was used for all training and testing.

Evaluation Protocol. We report the MAE between the ground truth Y and predicted crowd flow ̂Y. Crowd flow maps are visualized as heatmaps and predictions are accompanied by a difference image D = ̂Y - Y, where 0 values are white, positive values (overestimation) become increasingly red and negative values (underestimation) become increasingly blue.

7 Experiments

In this section, we report the results of three experiments to determine (1) whether a SOTA HTP model can perform LTCFP, (2) howwell the proposed representations, the superresolution framework, and GINet perform against the SOTA CAGE framework, and (3) which variant of the proposed GINet model is best.

7.1 LTCFP using Human Trajectory Prediction (HTP)

Recently, an evaluation of SOTA HTP models showed that the predicted trajectories of pedestrians often collide with each other and move through obstacles [Sohn et al., 2021]. HTP models are often able to ignore these issues, because they are evaluated on the basis of the minimum error across k shortterm samples. However, these issues become exacerbated when HTP models are adapted to LTCFP, which forces them to commit to one sample and use it as input for the subsequent prediction.

We have evaluated Trajectron++ (T++) [Salzmann et al., 2020], a SOTA HTP model, according to this method (with k = 1) on the Small Real dataset. After training on 1,500

crowd scenarios, Trajectron++ was primed with real input trajectories and made to predict ∼38 seconds into the future, i.e., the average duration of a trajectory in the dataset. The resulting trajectories for all agents were then converted into a crowd flow map and compared with predictions made by the CAGE framework. The qualitative results in the Supplementary Materials show that trajectories almost completely ignore the obstacles in the environment despite making its predictions conditioned on the environment. We have also masked the crowd flow map with the environment map to boost its performance, but the quantitative results in Table 1 indicate that even with masking, Trajectron++ performs significantly worse than both CAGE (the baseline) and all other LTCFP models on a dataset of real crowds in a small real environment (which is normally suitable for HTP). Although Attention U-Net outperforms GINet, the Small Real dataset is not a proper LTCFP dataset, meaning that it should be ignored when evaluating GINet with other LTCFP models.

7.2 Model and Representation Comparison

Table 2 compares the CAGE framework, CED networks adapted to the proposed super-resolution framework, and GINet after training on all input representations, where BODI is the SOTA baseline. For each model, the table reports the best input representation, the MAE for that input, the MAE when using BODI, and the percent improvement in MAE from BODI to the best input representation. Across all models from CAGE to GINet, we find that BODI is rarely the best representation and that joint representations (CODIRI and CODIFI) often lead to better MAE. The average percent improvement that the best input has over BODI across all models and datasets is ∼14.1%. Between different models using their best representations, it appears that the CAGE framework performs worse on every dataset than all proposed models by a substantial margin. On the other hand, the GINet[11110000] variant shows the best MAE across all LTCFP datasets (which excludes the Small Real dataset). Its MAE on the Large Real dataset never seen during testing is ∼51.6% lower than the next best model, and its MAE on the Large Synthetic dataset is ∼30.8% lower than the next best model, which clearly indicates that GINet scales well to large and complex environments. Figure 3 visualizes predictions made for each dataset. The full evaluation of each input representation and qualitative results have been provided in the Supplementary Materials.

7.3 GINet Variant Comparison

GINet[11110000] was chosen for comparison with other models after an ablation study was conducted over GINet variants using CODIFI. Table 3 shows the MAE for each variant. In general, it appears that having all coded gates enabled is worse than having them all disabled. This does not include the final two attention gates, which are enough to greatly improve performance on large datasets compared to adapted CED networks (see GINet[00000000]). It also appears that the geodesic interaction map serves better as attention than solely as input with X′ , because GINet[11110000] performs better than GINet[11000000]. Interestingly, GINet sees the most benefit from repeatedly receiving multi-scale geodesic interaction maps as input to its encoder blocks.

8 Conclusion

In this work, we have proposed (1) novel input representations using egocentric visibility information, which improve both the SOTA and several more performant models, (2) a super-resolution framework, which shows that CED networks for image classification can be repurposed for LTCFP and perform much better than the SOTA, (3) GINet, which shows that geodesic interaction is the key to improving LTCFP, and (4) a dataset of real and synthetic environments and crowds that is far more suitable for evaluating the scalability of models to large and complex environment than the only existing LTCFP dataset.

Acknowledgements

The research was supported in part by NSF awards: IIS1703883, IIS-1955404, IIS-1955365, RETTL-2119265, and EAGER-2122119. This material is based upon work supported by the U.S. Department of Homeland Security under Grant Award Number 22STESE00001 01 01.