Graph-based Spatial Transformer with Memory Replay for Multi-future Pedestrian Trajectory Prediction

Given a series of scene semantic segmentation maps $S=S_{1},S_{2},\ldots,S_{T_{obs}}$ and positions $X=(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{T_{obs}},y_{T_{obs}})$ of a pedestrian for time $1:T_{obs}$, our model aims to predict multiple possible future trajectories where the $i$th prediction of a pedestrian is denoted as $\hat{Y^{i}}=(\hat{x}^{i}_{t},\hat{y}^{i}_{t})$ for time $t=T_{obs+1}:T_{pred}$ by learning and inferring $P(\hat{Y}|S,X)$.

Fig. 2 shows the overall structure of our proposed model. Our model takes the observed trajectory $X$ and scene segmentation $S$ for video frames in the observation period as inputs. A multi-scale graph is constructed, which is a two-dimensional grid where the areas of the grid cells change with different scales. Each grid cell contains a sub-area of the scene segmentation and trajectory information. The inputs processed by the multi-scale graph are passed into an encoder-decoder network to generate future trajectories. The encoder encodes the motion pattern of pedestrians as well as the scene feature over time. The decoder consists of two main components: a multi-scale graph-based spatial transformer and a trajectory smoothing algorithm which is named “Memory Replay”. The spatial transformer processes the information and makes prediction of the next step. Memory Replay smooths the prediction by reading and writing in a memory graph that contains the overall temporal information of the decoded trajectory. At each time step, the decoder generates a probability distribution of locations at the next time step using these two components, followed by a convolutional LSTM cell [43]. The most probable locations that we select at each time is determined by the diverse beam search [21].

We formulate a video frame as a graph $\mathcal{G}(V,E)$ with a set of nodes $V$ and edges $E$. Specifically, we use a 2D regular grid with $|V|$ grid cells to split a frame into multiple areas, where each area can be considered a node $v\in V$ that connects to adjacent nodes with an undirected edge $e\in E$. Each grid cell can establish connections to the horizontal, vertical and diagonal neighbors. Inspired by the idea of feature pyramid [26, 24], we design the graph in different scales to process spatial information in multiple levels. There are two scales of grids which are the same as those in [24], and subsequently, the number of nodes can be $36\times 18$ and $18\times 9$.

Our implementation differs from feature pyramid where we change the amount of features included in a node instead of resizing the whole image (video frame). Nodes in the larger scale have less but finer features, and nodes in the smaller scale have more but coarser features. By learning on the multi-scale graph, our model can be more adaptive to different levels of information and make comprehensive decisions based on surrounding areas of a pedestrian.

Inspired by recent studies [32, 24], we propose two types of trajectory encoder: graph encoder and location encoder. In each graph scale, the graph encoder encodes the node level feature which is the index of the grid cell where the current location belongs to, and the location encoder record the specific coordinate which is the offset from the center of the area covered by the node. These two encoded hidden states are passed into the decoder separately.

In contrast to recent approaches [11, 36, 1] that model the motion of all pedestrians in a scene to enrich the spatial features, we utilize convolutional LSTM [43] to encode both spatial and temporal features simultaneously:

which denote the hidden states of graph encoder and location encoder at the graph scale $\mathcal{G}$ at time $t$, respectively. Since the subsequent process in the encoder and decoder all operates in the same way on these two hidden states, we denote both hidden states collectively as $H^{\mathcal{G}}_{t}$. To embed the pedestrian location $(x_{t},y_{t})$ for the graph encoder in graph scale $\mathcal{G}$ at time $t$, we adapt one-hot encoding multiplied by the scene segmentation:

where the idx$()$ function converts the coordinate to the index of the grid cell in $\mathcal{G}$. Then, the one-hot function projects the indexed cell onto the corresponding position on the graph. For the location encoder, we further calculate the offset from the center of the indexed cell:

where $C()$ function obtains the center coordinate of the indexed cell. The offset $(x^{\prime^{\mathcal{G}}}_{t},y^{\prime^{\mathcal{G}}}_{t})$ can be calculated by subtracting such center coordinate from the real coordinate $(x_{t},y_{t})$. We denote this offset coordinate as $l^{\mathcal{G}}_{t}$.

We keep the hidden state $H^{\mathcal{G}}_{T_{obs}}$ at time $T_{obs}$ after finishing encoding. And following [24], we also calculate an average of semantic segmentation map $\bar{S^{\mathcal{G}}}=\frac{1}{T_{obs}}\sum^{T_{obs}}_{t=1}S^{\mathcal{G}}_{t}$ and construct the hidden state to be passed into the decoder under graph scale $\mathcal{G}$ as:

where $||$ is concatenation. The scene segmentation map provides the pedestrians with awareness of the content and location for each object in the scene, which facilitates modeling of human-to-scene interactions.

Although RNN models are commonly used for addressing sequence prediction tasks [14], they have limitations in collecting nearby information of a person. Recently, [20, 52] have made some progress on trajectory prediction by exploiting attention mechanism spatially and temporally. [14] has employed GAT to model human-to-human relationship. However, compared to the crowded scenes in the ETH [30] and UCY [19] datasets, most scenes in the VIRAT/ActEV and Forking Paths datasets [2, 24] have much fewer pedestrians, whereas the spatial interaction with scene objects is also important.

Therefore, we design a graph-based spatial transformer to effectively model the relationship between both human-to-scene and human-to-human with the help of scene semantic segmentation features. The transformer takes the graph structured encoded hidden states $H^{\mathcal{G}}_{T_{obs}}$ from Eq. (5) as input node states. We use an attention mechanism to generate messages for all node pairs and aggregate them by the graph structure. The transformer will finally produce a group of updated node states that indicates the possible locations for the next time step.

To extract the interactions between the pedestrian and neighboring areas, we first generate an attention message:

where $M^{\mathcal{G}}_{Attn}$ is a matrix containing messages between all pairs of nodes in the graph scale $\mathcal{G}$. We learn a query matrix $f^{\mathcal{G}}_{Q}$, key matrix $f^{\mathcal{G}}_{K}$ and value matrix $f^{\mathcal{G}}_{V}$ from the graph structured hidden state $H^{\mathcal{G}}_{T_{obs}}$. Inspired by GAT, we concatenate the query matrix and the transpose of key matrix to create an entry for calculating attention value of each node pair $v_{i}$ and $v_{j}$. Then, we assign an importance value to each entry by conducting an element-wise multiplication between the concatenated matrix and the value matrix and add bias $\vec{b^{\mathcal{G}}}$. We denote the message from node $v_{j}$ to node $v_{i}$ as $M^{\mathcal{G}}_{Attn[i\leftarrow j]}$.

The spatial transformer adapts both advantages of self-attention mechanism and graph structure so that a pedestrian can attach different importance on the neighboring areas. However, distant objects (e.g., people, vehicles, obstacles) also provide essential spatial context in trajectory planning. Therefore, we also calculate a similarity score between each node pair $v^{\mathcal{G}}_{i}$ and $v^{\mathcal{G}}_{j}$ as a global message:

where $M^{\mathcal{G}}_{global[i\leftarrow j]}$ estimates the distance between features of node $v_{i}$ and $v_{j}$ in the hidden space. Finally, we obtain the total message passed from node $v_{j}$ to node $v_{i}$ by summing these two types of messages together:

where $\oplus$ is element-wise addition. The total message includes both unique information from neighboring nodes and similarity estimation from a global view.

Our spatial transformer can encourage the model to focus more on the most probable areas but neglects to take into account the temporal consistency. In the decoder, decoded hidden states from the transformer at time step $t$ is heavily based on the decoded states at $t-1$. However, the locations at the current time is also influenced by the hidden states at all previous time steps. In other words, if we only consider the computations based on the most recent time step, our predictions sometimes deviate from the originally intended destinations implied by the hidden states further before. To address this issue, we propose a trajectory smoothing algorithm “Memory Replay” that utilizes a memory graph $G(V)$ to dynamically record the decoded temporal information of a trajectory, where $|V|$ is the same as the number of nodes in the hidden state graph scale $\mathcal{G}$. Memory Replay operates on the edge weights calculated by the transformer. At each time step, the memory graph $G$ carries the smoothed edge weights of all node pairs (including a node to itself) in the past decoding time steps and decreases the weights of edges that point to the temporally inconsistent locations.

The processing steps are shown in Algorithm 1. Before decoding, we initialize the memory graph to all zeros. During each time step in decoding, we first pass the hidden state at the previous time into our spatial transformer to calculate the edge weights $e^{\mathcal{G}}$ for each node by Eq. (9) (Line 5). Then, we smooth the value of $e^{\mathcal{G}}$ by element-wise addition with $G$ (Line 6). $G$ is populated with the smoothed $e^{\mathcal{G}}$ at every time step (Line 7) to ensure that it includes the most recent decoded states. The hidden state at the current time is calculated by combining the updated node states based on the smoothed edge weights and the hidden state at the previous time in Eq. (10), as well as the output at the previous time (observed trajectory when the time is $T_{obs}$) in Eq. (12) (Line 9). Finally, we generate the output at the current time based on the new hidden state by Eq. (11) (Line 10). Therefore, the memory graph can record the newest edge weights at each time step, where the edge weights are smoothed by the memory graph at the previous time step. Memory Replay effects in such a recursive manner.

Following [24], we split our training as a classification task (graph encoder stream) and regression task (location encoder stream). We consider the ground truth output for each graph scale $\mathcal{G}$ at each time $t$ as $P^{\mathcal{G}}_{i}(t)$ and the duration for loss calculation as $T_{1:loss}$. We use cross-entropy loss for the graph encoder stream:

In addition, inspired by [36], we propose exponential smooth $L1$ loss for the location encoder stream:

where we define a penalty term $e^{\frac{T_{loss}-t+1}{\mu}}$ to guide the model focus more on the predictions at earlier time steps as the quality of earlier trajectories can greatly affect the later ones. The hyperparameter $\mu$ is used to control the strength of the penalty term.

To benefit from the multi-scale graph, we refer to multi-scale discriminators [41] and sum the loss calculated in both scales Scales $\in[36\times 18,18\times 9]$:

and $L$ is used to optimize the training in both scales.

We refer to [21, 24] utilizing diverse beam search to generate multiple trajectories in the graph encoder stream. At time $t-1$ in the graph scale $\mathcal{G}$, we obtain a set of $K$ decoded trajectories with their conditional logarithmic probabilities denoted as ${C^{\mathcal{G},k}_{1},C^{\mathcal{G},k}_{2}\ldots C^{\mathcal{G},k}_{t-1}}$ where $k\in[1,K]$ and $K$ is the beam size. Given the probability $\hat{P}^{\mathcal{G},k}_{t}$ inferred by the model at time $t$, we calculate the new logarithmic probability of the graph node $i$ in the beam $k$ as:

where $i\in\mathcal{G}$ and $k\in[1,K]$. $\gamma(i)$ is the diversity rate. In total, we need to calculate $|V|\times K$ such probabilities for all nodes and beams, where $|V|$ is the number of nodes. Finally, we select top $K$ of them as the predictions. For the location encoder stream, we apply the offset values to the predicted nodes to obtain the precise coordinates.

Although minADE_K and minFDE_K can evaluate the displacement between prediction and ground truth, they ignore the diversity of prediction distribution. As illustrated in Fig. 3, there are 5 ground truth trajectories and 8 predicted trajectories. However, according to the definitions of minADE_K and minFDE_K, only 2 predictions are included in the evaluation, which are the closest prediction for each ground truth. We consider this an incomprehensive prediction, where several ground truth trajectories share the same predicted trajectory. Ideally, we expect to have 5 distinct predictions corresponding to 5 ground truth trajectories. In addition, Yuan et al. [46] developed Average Self Distance (ASD) and Final Self Distance (FSD) to evaluate the diversity of prediction distribution by calculating the $L2$ distance between each prediction with its nearest prediction. However, diversity of prediction that calculated by ASD and FSD fails to consider the number of predicted trajectories that lie in the distribution of ground truth.

To evaluate the comprehensiveness of prediction distribution, we define PTU as:

where $|\hat{p}_{i}|$ denotes the number of predictions used while evaluating with minADE_K and minFDE_K and $\left|Y_{i}\right|$ denotes the number of ground truth trajectories in a data sample. We sum such percentage for all $N$ data samples then average it. Under the same result of minADE_K and minFDE_K, a larger PTU represents a more comprehensive prediction.

We use the same data processing method as [11] and, following [24], we apply the pre-trained scene segmentation model [6] to obtain scene segmentation features. We utilize a single convolutional LSTM layer for both the encoder and decoder; and aggregate features of one-hop neighbors in our graph-based transformer. We set the learning rate as 0.3 with decay value of 0.95 and weight decay of 0.001, which are the same as [24]. We embed the graph features with an embedding size of 32 and the hidden state sizes for both the encoder and decoder are 256. For hyperparameters $\alpha$ and $\beta$ in total loss, we set $\alpha=1.0$ and $\beta=0.2$; and $\mu$ in our exponential smooth $L1$ loss is 10. We only apply such exponential loss on single-future prediction as it will affect the diversity of multi-future prediction through experiments. In order to align with [24], we also generate $K=20$ most possible predictions for each data sample in multi-future prediction.