CoMoGCN: Coherent Motion Aware Trajectory Prediction with Graph Representation

A pioneering work for crowd interaction modeling, the Social Force Model (SFM) proposed by [Helbing and Molnar(1995)], has been applied successfully to many applications such as abnormal crowd behavior detection[Mehran et al.(2009)Mehran, Oyama, and Shah] and multi-object tracking [Pellegrini et al.(2009)Pellegrini, Ess, Schindler, and Van Gool]. However, as discussed in [Alahi et al.(2016)Alahi, Goel, Ramanathan, Robicquet, Fei-Fei, and Savarese], the social force model can model simple interactions, but fails to model complex crowd interactions. There are also other hand crafted feature based models, such as continuum dynamics [Treuille et al.(2006)Treuille, Cooper, and Popović], discrete choice [Antonini et al.(2006)Antonini, Bierlaire, and Weber] and Gaussian Process models [Wang et al.(2007)Wang, Fleet, and Hertzmann]. However, all the above methods are based on hand-crafted energy functions and specific rules, which limit their performance.

Recently, Recurrent Neural Networks (RNN), such as the Long Short Term Memory (LSTM), have achieved many successes in trajectory prediction tasks [Alahi et al.(2016)Alahi, Goel, Ramanathan, Robicquet, Fei-Fei, and Savarese, Su et al.(2017)Su, Zhu, Dong, and Zhang, Xu et al.(2018)Xu, Piao, and Gao, Zhang et al.(2019)Zhang, Ouyang, Zhang, Xue, and Zheng, Lisotto et al.(2019)Lisotto, Coscia, and Ballan, Hasan et al.(2018)Hasan, Setti, Tsesmelis, Del Bue, Galasso, and Cristani]. Alahi et al. proposed a social pooling layer to model neighboring humans [Alahi et al.(2016)Alahi, Goel, Ramanathan, Robicquet, Fei-Fei, and Savarese]. Gupta et al. proposed a pooling module, which consists of an MLP followed by max-pooling to aggregate information from all other humans [Gupta et al.(2018)Gupta, Johnson, Fei-Fei, Savarese, and Alahi]. Sadeghian et al. [Sadeghian et al.(2019)Sadeghian, Kosaraju, Sadeghian, Hirose, Rezatofighi, and Savarese] adopted a soft attention module to aggregate information across agents. More recent work uses GCNs to aggregate information by treating humans as nodes and modeling interaction through edge strength for robot navigation [Chen et al.(2020)Chen, Liu, Shi, and Liu]. Similarly, a variant of the GCN, the Graph Attention Network (GAT), has been used to model the social interactions [Kosaraju et al.(2019)Kosaraju, Sadeghian, Martín-Martín, Reid, Rezatofighi, and Savarese]. However, the use of multi-head attention in the GAT increases the number of parameters and the computational complexity of the GAT in comparison to the GCN. In this work, we integrate information across humans using GCNs, which enables our method to handle varying crowd sizes.

Most previous work only pay attention to interactions among pairs of pedestrians. However, the pedestrian trajectories are also influenced by more complex social relations between humans. Coherent motion patterns inside crowds, which encode implicit social information, have been shown to be useful in many applications, such as crowd activity recognition[Wang et al.(2008)Wang, Ma, and Grimson]. Bisagno et al. [Bisagno et al.(2018)Bisagno, Zhang, and Conci] considered intragroup interactions for trajectory predictions, but neglected intergroup interactions. Current benchmark datasets for trajectory prediction do not provide coherent motion labels.

Several works have been done in detecting coherent motions [Zhou et al.(2012)Zhou, Tang, and Wang] and measuring the collectiveness of crowds [Mei et al.(2019)Mei, Lai, Chen, and Xie]. Zhou et al. [Zhou et al.(2012)Zhou, Tang, and Wang] proposed the coherent filtering that detects invariant neighbors of every individual, and measures the velocity correlations for motion clustering. It shows good performance on collective motion benchmark and can detect coherent motions given the crowd trajectories in a short time window. In this paper, we use the coherent filtering method to label trajectory prediction datasets. In addition, we leverage DBSCAN clustering to compensate for the disadvantages of the coherent filtering method in small group detection. Based on the labels, we incorporate the coherent motion information into our model for better interaction modeling.

The goal of this work is to generate the future trajectories of all humans in a scene at the same time. The trajectory of a person $i$ is defined using $x_{rel_{i}}^{t}=(x_{i}^{t},y_{i}^{t})$ which denotes the relative position of human $i$ at time step $t$ to the position at $t-1$. Consistent with previous works [Gupta et al.(2018)Gupta, Johnson, Fei-Fei, Savarese, and Alahi, Sadeghian et al.(2019)Sadeghian, Kosaraju, Sadeghian, Hirose, Rezatofighi, and Savarese], the observed trajectory of all humans in a scene is defined as $x_{rel_{1,...,N}}^{(1:t_{obs})}$ for time steps $t=1,...t_{obs}$; the future trajectory to be predicted is defined as $x_{rel_{1,...,N}}^{(t_{obs}+1:t_{obs}+T)}$ for time step $t=t_{obs}+1,...,t_{obs}+T$, where the number of humans $N$ may change dynamically. The model aims to generate trajectories $\hat{x}_{rel_{1,...,N}}^{(t_{obs}+1:t_{obs}+T)}$ whose distribution matches that of ground truth future trajectories of all humans $x_{rel_{1,...,N}}^{(t_{obs}+1:t_{obs}+T)}$.

Figure 1 shows the overall framework of our method for trajectory prediction. Data pre-processing is applied offline to obtain the coherent motion pattern for each human. For feature extraction, we first use a single layer MLP (FC) to encode each pedestrian’s relative displacements as a fixed-length embedding. These embeddings are fed to an LSTM as shown below:

where $W_{enc}$ is the weight of FC layer, and $W_{en}$ is the weight of the encoding LSTM. On the other hand, for specific person $i$, the relative position of other humans are fed into an FC layer to obtain social information $p_{i}$ which is similar to the pooling module in Social GAN [Gupta et al.(2018)Gupta, Johnson, Fei-Fei, Savarese, and Alahi].

Then the features from all pedestrians $e_{1,...,N}$ and the interested person’s social information $p_{i}$ are concatenated together as the input to the two GCNs for intergroup and intragroup interaction aggregation:

where $A_{\text{intra}}$ and $A_{\text{inter}}$ denote the adjacency matrices as described in more detail in Section. 3.4. $W_{\text{intra}}$ and $W_{\text{inter}}$ are weight matrices. We extract the feature of node $i$ after the final graph convolutional layer as the features $V_{intra_{i}}$ and $V_{inter_{i}}$.

For coherent motion detection, we use the coherent filtering proposed by [Zhou et al.(2012)Zhou, Tang, and Wang]. The process takes the positions of humans from consecutive frames $t_{1}$ to $t_{k}$ and generates a clustering index for each human and for each frame. Humans sharing the same index are considered to have coherent motion. The process of coherent filtering mainly includes three steps: a) finding K nearest neighbors b) finding the invariant neighbors of a individual c) measuring the time-averaged velocity correlations of the invariant neighbors to the individual. Among these individual-neighbor pairs, pairs with correlation intensity above a threshold are marked as coherent pairs.

Though this method is effective for crowds with large crowd densities, it performs poorly for sparse crowds and fails to detect small groups. To compensate, we apply an extra clustering step, the DBSCAN method [Ester et al.(1996)Ester, Kriegel, Sander, Xu, et al.], for the unlabeled humans. As a density based clustering method, it relies on the distance to find the neighbors. We account for moving direction and calculate the angular distance of each pair of humans. These differences are used to classify humans into clusters.

Our hybrid labeling method improves the labeling yield and generates better labels than the coherent filtering alone. Figure 1 of the supplementary file shows examples of detection by coherent filtering on each dataset. The quantitative evaluations of the coherent filtering and of our hybrid labeling method are shown in Table 2 and 3 of the supplementary file. Figure 2 of the supplementary file shows a qualitative comparison between the coherent filtering and our method. The parameter settings are shown in Table 1 of the supplementary file.

Dealing with the large and varied numbers of humans in a scene is one of the main challenges for multi-human trajectory prediction. Previous works adopted ad-hoc solutions such as setting a maximum number of humans[Sadeghian et al.(2019)Sadeghian, Kosaraju, Sadeghian, Hirose, Rezatofighi, and Savarese]. In this work, we address this problem in a simpler and more principled way through graph representations. Nodes in the graph denote humans in the crowd. In the following, we denote the number of humans in the crowd by $N$.

We adopt a two-layer graph convolutional networks (GCNs) [Kipf and Welling(2016)] to aggregate information in crowds. To each node in the network, we associate a feature vector, which contains important information about the node. The graph convolutional layer is the main building block of GCNs. It takes input feature vectors for each node and converts them to output feature vectors for each node by integrating information both within and across nodes. We use $I$ to denote the dimension of the input feature vectors and $O$ to denote the dimension of the output feature vectors The input feature vectors of layer $l$ are represented by matrix $\mathbf{H}^{l}\in\mathbb{R}^{N\times I}$. The input feature matrix is converted to output vectors represented by a matrix $\mathbf{H}^{l+1}\in\mathbb{R}^{N\times O}$ based on the layer-wise forward rule:

$\mathbf{W}^{l}\in\mathbb{R}^{I\times O}$ is a trainable weight matrix for layer $l$. $\boldsymbol{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix of the graph, whose values determine how information from different nodes is aggregated. Each row of $\boldsymbol{A}$ is normalized to sum to one. $\sigma(\cdot)$ is Relu activation function.

The adjacency matrix reflects the connections between nodes of the graph. The vanilla GCN assumes that the qualitative influence of each human on another (as determined by $\mathbf{W}^{l}$) is the same and only the strength of that influence can be modulated (through the adjacency matrix). However, we think that the qualitative effect of humans in the crowd on a particular human’s trajectory are different, based on whether the humans are in the same group or not. A single GCN can not handle this. Thus, we propose to use two GCNs. As shown in Fig.2, for each human, we modulate the adjacency matrix by multiplication with two coherence masks which encodes the intergroup and intragroup labels. Then we obtain two adjacency matrix denoting intergroup connection ($A_{\text{inter}}$) and intragroup ($A_{\text{intra}}$) connection separately for each human by pixelwise multiplying the adjacency matrix ($A$) with the masks. We set the value in the adjacency matrix by first constructing a binary matrix denoting connections between nodes, and then normalizing each row.

By modulating the adjacency matrix of GCNs with coherent motion information, we incorporate implicit social relations into our network for better interaction modeling.

We trained the network with Adam optimizer. The mini-batch size is 64 and the learning rate is 1e-4. The models were trained for 200 epochs. The encoder encodes the relative trajectories by a single layer of MLP ($MLP_{enc}$) with dimension of 16 followed by an LSTM ($LSTM_{en}$)with a hidden dimension of 32. The embedding output from LSTM was then concatenated with the features extracted from relative position from other humans by a single MLP with dimension of 16. The concatenated features are then fed into two GCNs for feature integration. Then hidden number for two graph convolutional layer has the dimension of 72 and 8 separately. Then an MLP ($MLP_{vae}$) was used to take state of humans to create a distribution with mean and variance. Then we sample $z$ from this distribution with a dimension of 8, and fed it into an LSTM ($LSTM_{de}$)with dimension of 32 and followed by an MLP ($MLP_{dec}$)with dimension of 2 for decoding.

Following the setting in [Gupta et al.(2018)Gupta, Johnson, Fei-Fei, Savarese, and Alahi], we adopt the leave-one-out approach, i.e. train with four sets and test in the remaining set. We take trajectories with 8 time steps as observation and evaluate trajectory predictions over the next 12 time steps.

In order to better understanding the benefits of our model in capturing social interactions between humans, we visualize several examples of the generated trajectories across testing sets as shown in Fig.3.

From the four examples, we can see that the predictions of our model generally have lower variance than S-GAN, which means we can generate model in a more efficient way. Also, the examples show that our model better captures the interactions of pedestrians walking in the crowds which obtain more accurate predictions (as shown in (d)). It is clear to see that our model generates more realistic predictions avoiding collisions as shown in example (b). Besides, S-GAN tends to predict slower motion in dataset HOTEL (as shown in (c)).

For qualitative results of the ablation study, please refer to Fig. 3 in supplementary file. We can observe consistent results with the quantitative evaluation. The proposed full model make more accurate and realistic predictions.