# RCP: Recurrent Closest Point for Scene Flow Estimation on 3D Point Clouds

Xiaodong Gu1 Chengzhou Tang2 Weihao Yuan1 Zuozhuo Dai1 Siyu Zhu1 Ping Tan12
1Alibaba Group 2Simon Fraser University

###### Abstract

3D motion estimation including scene flow and point cloud registration has
drawn increasing interest. Inspired by 2D flow estimation, recent methods
employ deep neural networks to construct the cost volume for estimating
accurate 3D flow. However, these methods are limited by the fact that it is
difficult to define a search window on point clouds because of the irregular
data structure. In this paper, we avoid this irregularity by a simple yet
effective method. We decompose the problem into two interlaced stages, where
the 3D flows are optimized point-wisely at the first stage and then globally
regularized in a recurrent network at the second stage. Therefore, the
recurrent network only receives the regular point-wise information as the
input. In the experiments, we evaluate the proposed method on both the 3D
scene flow estimation and the point cloud registration task. For 3D scene flow
estimation, we make comparisons on the widely used FlyingThings3D [32] and
KITTI [33] datasets. For point cloud registration, we follow previous works
and evaluate the data pairs with large pose and partially overlapping from
ModelNet40 [65]. The results show that our method outperforms the previous
method and achieves a new state-of-the-art performance on both 3D scene flow
estimation and point cloud registration, which demonstrates the superiority of
the proposed zero-order method on irregular point cloud data. Our source code
is available at https://github.com/gxd1994/RCP.

iter=0

iter=3

iter=7

iter=14

Figure 1: Visualization of the results on the KITTI scene flow dataset. With
the increasing number of alternate optimizations, the source point cloud (in
green) is gradually aligned with the target point cloud (in blue).

##  1 Introduction

Motion estimation is a fundamental building block for numerous applications
such as robotics, augmented reality and autonomous driving. The low-level
motion cues can serve other higher-level tasks such as object detection and
action recognition. Given a pair or a sequence of images, we can estimate 2D
flow fields from optical flow estimation by either classic variational methods
or modern deep learning methods [25, 51, 52].

Different from the scene flow methods that extend 2D optical flow to
stereoscopic or RGB-D image sequences [24, 21], increasing attention has been
paid to the direct 3D flow estimation on point clouds recently, which has
several advantages over image based methods for a variety of applications. For
example, one of the most prominent benefits is that it avoids the image sensor
readings and the additional computation of depth from images for autonomous
driving, which enables low-latency 3D flow estimation for a high-speed driving
vehicle. While for augmented reality, especially for AR glasses, the 3D flow
estimation on point clouds enables the computation distribution on the cloud
server because it saves much more transmission bandwidth than images. It also
protects the privacy of the surrounding people by not using images.

Therefore, some learning based methods [61, 30, 18, 2, 27] utilizes the recent
advances made for high-level tasks and customize the scene flow estimation
specifically for point clouds. These methods predict the 3D flow vectors from
cost-volumes, where similarity costs between 3D points from two point cloud
sets are measured. However, different from the cost-volumes in 2D optical flow
that search a fixed regular neighborhood around a pixel in consecutive images
[25, 51, 52], it is impossible to define such a search window on point clouds
because of the irregular data structure. Therefore, previous works like [30,
64, 27, 18], they designed some complicated layers to measure the point-to-
patch cost or patch-to-patch cost.

In this paper, we avoid this irregularity by a simple and effective method. We
decompose the problem into two interlaced stages, where the 3D flows are
optimized point-wisely at the first stage and then globally regularized in a
recurrent network at the second stage. Therefore, the recurrent network only
receives the regular point-wise information as the input. Besides the scene
flow estimation, our method also enables another important motion estimation
task that registers two point clouds with the different 6-DOF pose. Since we
only measure the point-to-point costs, we avoid the discretization of the 6DOF
solution space, which is difficult because the rotation vector and the
translation vector are two different variables that have different scales and
ranges.

To evaluate the proposed method, we conduct experiments on both the 3D scene
flow estimation and the point cloud registration. For 3D scene flow
estimation, we made comparisons on the widely used FlyingThings3D [32] and
KITTI [33] benchmark. For point cloud registration, we follow the previous
works and generate data pairs with large pose and partially overlapping from
ModelNet40 [65]. We have achieved state-of-the-art results on both 3D scene
flow estimation and point cloud registration, which demonstrate the
superiority of the proposed zero-order method on irregular point cloud data.

##  2 Related work

#### Point Cloud Networks.

Prior to the emergency of neural networks, various hand-crafted 3D feature
descriptors have been proposed based on the heuristic knowledge [20]. These
descriptors usually accumulate measurements to histograms based on the spatial
coordinates [14, 26, 54] or the geometry attributes [6, 44]. Other works such
as PFH [43] and FPFH [42] have been proposed the descriptors which are
rotation-invariant. Traditional features, however, are designed by hand and
cannot be too complicated. More recently, more methods have begun to employ
the deep neural networks to learn the features. 3DMatch [70] utilizes a
contrastive loss to train a descriptor with 3D convolutional neural networks,
but the voxelization leads to a loss of feature quality. To solve this, PPFNet
[10] uses the PointNet [38] to directly learn the point cloud features. Also,
the salient keypoints are detected to describe the point clouds [28, 68]. In
this work, we use PointNet++ [39] to extract the point cloud features
considering its strong feature representation ability.

#### 3D Flow Estimation on Point Clouds.

The task of scene flow estimation is first introduced in [59] and then
developed from images [24, 21] to point clouds [11, 57, 56]. [11] formulates
the scene flow estimation problem as an energy minimization problem. [57]
constructs occupancy grids and filters the background before the energy
minimization and then refine the results with filtering after. An encoding
network is introduced in a following up work to learn features from the
occupancy grid [56].

Recently, more methods use deep neural networks for 3D flow estimation [61,
30, 18, 2, 27, 64]. A network that learns hierarchical features of point
clouds and flow embeddings representing point motions is designed in FlowNet3D
[30]. A bilateral convolutional layer which projects the point cloud to the
permutohedral lattice is proposed in HPLFlowNet [18]. PointPWC-Net [64]
proposes a learnable cost volume layer along with upsample and warping layers
to build a coarse-to-fine deep network to efficiently handle point cloud. FLOT
[37] uses optimal transport tools to estimate the scene flow without using
multiscale analysis. Recent works [52, 29, 34, 19] get promising results by
using the model unrolling method, FlowStep3D [27] adopts GRU[7] to iteratively
refine the scene flow and show excellent results. However, all the above
methods need to define the cost volume, which is difficult to design
considering the irregularity of the point clouds. In contrast, we avoid this
irregularity by optimizing the cost point-wisely and sending the regular
point-wise information to a recurrent network.

Figure 2: Overview of our framework. We first extract the point cloud features
by a shared PointNet++ [39] backbone, followed by the sinkhorn algorithm [48]
to get the initialized results from feature matching. Then, we decompose the
problem into two sub-problems and utilize the proposed point-wise optimization
and recurrent regularization modules to estimate either the 3D scene flow or
the transformation.

#### Point Cloud Registration.

The task of point cloud registration is to find the spatial transformation
between two point clouds. Traditional methods are mainly based on the
iterative closest point (ICP)[3, 47] and its variants[48, 55, 67, 16, 40, 36,
41]. Recent works learn deep neural networks for point cloud registration and
can be divided into two streams. One stream[71, 8, 17, 12, 35, 1, 23] studies
how to leverage better point cloud feature presentation in off-the-shelf
optimization. PointNetLK[1] defines a feature-metric distance between point
clouds, which is measured by the features from PointNet[38], and unrolls the
classical Lucas & Kanade (LK) algorithm into a recurrent network to minimize
this distance.

Another stream[46, 62, 31, 63, 15, 23] studies the optimization process
itself, which usually makes the optimization algorithm differentiable and
incorporate it into a deep learning pipeline. To improve the robustness
against noise, PCRNet[46] proposes a framework which estimates the pose with a
deep MLP network instead of the traditional LK algorithm. Deep Closest
Point[62] proposes an end-to-end pipeline with a point cloud embedding
network, an attention-based matching module, and a differentiable singular
value decomposition (SVD) layer to estimate the spatial transformation. RPM
[17] and RPMNet [69] use Sinkhorn normalization [48] to handle outliers and
partial visibility. To further decrease the sensibility to outlier points,
RGM[15] develops a deep graph matching network which considers both the local
geometry of each point and its structure and topology in a larger range so
that more correspondences can be found. Inspired by RAFT [52], we use a
recurrent network directly to estimate the residual of the transformation to
find more high-quality correspondences.

##  3 Method

###  3.1 Overview

Given two point clouds
$\mathcal{P}=\\{{\bm{p}}_{1},{\bm{p}}_{2},\cdots{\bm{p}}_{M}\\}$ and
$\mathcal{Q}=\\{{\bm{q}}_{1},{\bm{q}}_{2},\cdots{\bm{q}}_{N}\\}$, where
$\mathcal{P}$ and $\mathcal{Q}$ do not necessarily have the same number of
points or have any exact correspondence between their points, our goal is to
estimate the transformation $\mathcal{X}$ between them, which can be either a
set of point-wise 3D flow vectors
$\\{{\bm{x}}_{1},{\bm{x}}_{2},\cdots{\bm{x}}_{M}\\}$ for a dynamic scene or a
6-DOF transformation $\\{{\bm{Q}},{\bm{T}}\\}$ for a rigid scene, where
${\bm{Q}}$ is the rotation quaternion and ${\bm{T}}$ is the 3D translation
vector. As shown in Fig. 2, we first extract the feature of each 3D point in
$\mathcal{P}$ and $\mathcal{Q}$ by a shared PointNet++ [39] in Sec. 3.2, and
then estimate the initial transformation $\mathcal{X}_{0}$ via the sinkhorn
[37, 45, 9, 48] based feature matching. Then the initial solution
$\mathcal{X}^{0}$ is further updated by minimizing the following objective
function:

$E(\mathcal{X})=D_{\mathcal{P},\mathcal{Q}}(\mathcal{X})+R(\mathcal{X}),$ (1)

where the data term $D_{\mathcal{P},\mathcal{Q}}$ measures the feature
distance between $\mathcal{P}$ and $\mathcal{Q}$ under a transformation
$\mathcal{X}$, and the regularization term $R(\mathcal{X})$ measures the
object-aware smoothness of $\mathcal{X}$ itself,  _i.e_., neighboring points
on the same object should have similar flow vectors.

However, optimizing Eq. (1) directly is difficult, and one of the major
reasons is that a transformed point ${\bm{p}}_{m}+{\bm{x}}_{m}$ does not
exactly correspond to any point ${\bm{q}}_{n}$ in $\mathcal{Q}$, so the
feature distance between ${\bm{p}}_{m}$ and ${\bm{p}}_{m}+{\bm{x}}_{m}$ is
invalid, and the data term $D_{\mathcal{P},\mathcal{Q}}$ is non-differentiable
respect to the transformation $\mathcal{X}$. Inspired by the quadratic
relaxation in previous works [50], we introduce an auxiliary transformation
$\mathcal{Z}$ and convert Eq. (1) into:

$E(\mathcal{X},\mathcal{Z})=D_{\mathcal{P},\mathcal{Q}}(\mathcal{Z})+R(\mathcal{X})+\|\mathcal{Z}-\mathcal{X}\|^{2}_{2}.$
(2)

The auxiliary variable $\mathcal{Z}$ decouples the data term and the
regularization term, so they can be optimized separately. Meanwhile, the
additional term $\|\mathcal{Z}-\mathcal{X}\|^{2}_{2}$ enforces $\mathcal{Z}$
and $\mathcal{X}$ close to each other through the optimization process. The
$\mathcal{Z}$ and the $\mathcal{X}$ are updated interlacedly as:

$\displaystyle\mathcal{Z}^{k}=\operatorname*{arg\,min}_{\mathcal{Z}}D_{\mathcal{P},\mathcal{Q}}(\mathcal{Z})+\|\mathcal{Z}-\mathcal{X}^{k-1}\|^{2}_{2},$
(3)
$\displaystyle\mathcal{X}^{k}=\operatorname*{arg\,min}_{\mathcal{X}}\|\mathcal{Z}^{k}-\mathcal{X}\|^{2}_{2}+R(\mathcal{X}).$
(4)

where $k$ represents the $k$-th iteration. At each iteration, we first solve
$\mathcal{Z}^{k}$ via the point-wise optimization in Sec. 3.3 and then
$\mathcal{X}^{k}$ via the recurrent regularization implicitly in Sec. 3.4.

###  3.2 Feature Extraction

First, we extract features that are used through the sinkhorn feature matching
[48], point-wise optimization of Eq. (3) as well as the recurrent
regularization of Eq. (4). We use PointNet++ [39] to extract features for each
3D point, and denote ${\bm{f}}_{\mathcal{P}}(\cdot)$ and
${\bm{f}}_{\mathcal{Q}}(\cdot)$ as the feature extraction operation on
$\mathcal{P}$ and $\mathcal{Q}$ respectively. PointNet++ [39] designs the
$set\\_conv$ layer which includes the sample layer, the group layer and the
PointNet [38] layer. The sample layers subsample the point clouds into $1/4$
of the original number by using iterative farthest point sampling. The group
layer groups the $k$-nearest neighbor ($k=32$) points around each point and
then uses max-pooling for feature aggregation.

Cost

EPE3D

Figure 3: Curves of the cost and EPE3D error with respect to the iterations on
the Flyingthigs3D dataset. As the alternate optimization progresses, the cost
drops step by step, while the EPE3d error is decreased gradually.

###  3.3 Point-wise Optimization

Given the solution
$\mathcal{X}^{k-1}=\\{{\bm{x}}_{{1}}^{k-1},{\bm{x}}_{{2}}^{k-1},\cdots{\bm{x}}_{M}^{k-1}\\}$
from the previous iteration, we first minimize Eq. (3) point-wisely to update
$\mathcal{Z}^{k}$. The auxiliary transformation
$\mathcal{Z}^{k}=\\{{\bm{z}}_{{1}}^{k-1},{\bm{z}}_{{2}}^{k-1},\cdots{\bm{z}}_{M}^{k-1}\\}$
contains the auxiliary flow vectors for each point in $\mathcal{P}$. An
auxiliary flow vector ${\bm{z}}_{m}^{k}$ minimizes both the feature distance
between ${\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})$ and
${\bm{f}}_{\mathcal{Q}}({\bm{p}}_{m}+{\bm{z}}^{k}_{m})$ as well as the
euclidean distance between ${\bm{z}}_{m}^{k}$ and ${\bm{x}}_{m}^{k-1}$:

${\bm{z}}_{m}^{k}=\operatorname*{arg\,min}_{{\bm{z}}}\|{\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})-{\bm{f}}_{\mathcal{Q}}({\bm{p}}_{m}+{\bm{z}})\|+\|{\bm{z}}-{\bm{x}}_{m}^{k-1}\|.$
(5)

However, ${\bm{p}}_{m}+{\bm{z}}$ usually does not exactly correspond to any
point ${\bm{q}}_{n}$ in $\mathcal{Q}$, so we use
${\bm{u}}_{n}={\bm{q}}_{n}-{\bm{p}}_{m}$ as a candidate for ${\bm{z}}_{m}^{k}$
and search for the best ${\bm{q}}_{n}$ within a local neighborhood $\Omega$
around ${\bm{p}}_{m}+{\bm{x}}_{m}^{k-1}$. This winer-take-all selection is
further softened as a bilateral interpolation:

$\footnotesize{\bm{z}}_{m}^{k}=\frac{1}{W}\sum_{{\bm{q}}_{n}\in\Omega}\exp(-\frac{\|{\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})-{\bm{f}}_{\mathcal{Q}}({\bm{q}}_{n})\|}{\sigma_{{\bm{f}}}}-\frac{\|{\bm{u}}_{n}-{\bm{x}}_{m}^{k-1}\|}{\sigma_{{\bm{u}}}}){\bm{u}}_{n},$
(6)

where $W$ is the normalization term that sum all the bilateral weights.
Empirically, the reversed distance
$-(\|{\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})-{\bm{f}}_{\mathcal{Q}}({\bm{q}}_{n})\|)/\sigma_{{\bm{f}}})$
and $-(\|{\bm{u}}_{n}-{\bm{x}}_{m}^{k-1}\|)/\sigma_{{\bm{u}}}$ can be further
replaced with cosine similarity for better performance, which converts Eq. (6)
into:

${\bm{z}}_{m}^{k}=\sum_{{\bm{q}}_{n}\in\Omega}\mathrm{softmax}({\bm{g}}^{\top}_{m}{\bm{g}}_{n}){\bm{u}}_{n},$
(7)

where ${\bm{g}}_{m}$ concatenates ${\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})$ and
the positional encoding of ${\bm{p}}_{m}+{\bm{x}}_{m}^{k-1}$, while
${\bm{g}}_{n}$ concatenates ${\bm{f}}_{\mathcal{Q}}({\bm{q}}_{n})$ and the
positional encoding of ${\bm{q}}_{n}$. Eq. (7) is similar to the attention
[58] mechanism, but uses the same feature operator for the key and the
queries.

For point cloud registration, two additional steps are required. First, before
Eq. (7), the point-wise flow vector ${\bm{x}}_{m}^{k-1}$ is calculated by the
difference between ${\bm{p}}_{m}$ and its corresponding projection transformed
by $\mathcal{X}^{k-1}=\\{{\bm{Q}}^{k-1},{\bm{T}}^{k-1}\\}$. Second, after
${\bm{z}}_{m}^{k}$ is estimated, the auxiliary 6-DOF transformation
$\mathcal{Z}^{k}$ is computed via the PnP algorithm [13] from the auxiliary 3D
flow vectors ${\bm{z}}_{1\cdots M}^{k}$.

Figure 4: Details of point-wise optimization module. The positional encoder
and the MLPs-attention blocks are both composed of two fully-connected layers.
The parameters of these two blocks for point cloud $\mathcal{P}$ and
$\mathcal{Q}$ are shared. The residual block is to obtain the position
residual of currently estimated points and their neighborhood points.

###  3.4 Recurrent Regularization

Given the auxiliary transformation $\mathcal{Z}^{k}$ from the last section, we
further implicitly regularize $\mathcal{Z}^{k}$ into $\mathcal{X}^{k}$ by a
recurrent network. The recurrent network receives previous iteration’s hidden
state ${\bm{h}}_{k-1}$ and the current iteration information
${\bm{v}}_{k}=[{\bm{f}}_{\mathcal{P}}({\bm{p}}_{m})-{\bm{f}}_{\mathcal{Q}}({\bm{p}}_{m}+{\bm{x}}_{m}^{k-1}),{\bm{z}}_{m}^{k}]$
as the inputs, where ${\bm{f}}_{\mathcal{Q}}({\bm{p}}_{m}+{\bm{x}}_{m}^{k-1})$
is interpolated similarly to Eq. (7). Then an updated hidden state
${\bm{h}}_{k}$ is produced from a recurrent unit such as GRU [7] as follows:

$\displaystyle{\bm{w}}_{k}$
$\displaystyle=\sigma(set\\_conv_{\bm{w}}([{\bm{h}}_{k-1},{\bm{v}}_{k}])),$
(8) $\displaystyle{\bm{r}}_{k}$
$\displaystyle=\sigma(set\\_conv_{\bm{r}}([{\bm{h}}_{k-1},{\bm{v}}_{k}])),$
$\displaystyle\tilde{{\bm{h}}}_{k}$
$\displaystyle=\tanh(set\\_conv_{\bm{h}}([{\bm{r}}_{k}\odot{\bm{h}}_{k-1},{\bm{v}}_{k}])),$
$\displaystyle{\bm{h}}_{k}$
$\displaystyle=(1-{\bm{w}}_{k})\odot{\bm{h}}_{k-1}+{\bm{w}}_{k}\odot\tilde{{\bm{h}}}_{k},$

where $\odot$ is the element-wise product, $[\cdot,\cdot]$ is a concatenation
and $\sigma(\cdot)$ is the sigmoid activation function. To initialize the
first iteration’s hidden state ${\bm{h}}_{0}$, we set
$\mathcal{Z}^{1}=\mathcal{X}_{0}$ and pass ${\bm{v}}_{1}$ through two
$set\\_conv$ layers.

After the new hidden state ${\bm{h}}_{k}$ has been produced, we use a
transformation predictor consisting of two $set\\_conv$ layers to estimate the
residual $\Delta\mathcal{Z}^{k}$ between $\mathcal{Z}^{k}$ and the regularized
transformation $\mathcal{X}^{k}$, and update the transformation as
$\mathcal{X}^{k}=\mathcal{Z}^{k}+\Delta\mathcal{Z}^{k}$. For point cloud
registration, we additionally max-pool the hidden state ${\bm{h}}_{k}$ overall
points, and predict the residual 6-DOF transformation $\Delta\mathcal{Z}^{k}$
from the max-pooled feature vector, and update the transformation in $SE(3)$
manifold as $\mathcal{X}^{k}=\Delta\mathcal{Z}^{k}\otimes\mathcal{Z}^{k}$.

##  4 Training Loss

Similar to previous methods [64, 27], our networks can be trained in either a
supervised way or a self-supervised way.

###  4.1 Supervised Training

In the training of the scene flow network, given the ground truth 3D flow
vectors$\\{{\bm{x}}^{*}_{{\bm{p}}_{i}}\\}$ at each point ${\bm{p}}_{i}$, the
$L_{1}$ loss is adopted as:

$\mathcal{L}_{flow}=\frac{1}{M}\sum_{i}\|\hat{{\bm{x}}}_{{\bm{p}}_{i}}-{\bm{x}}^{*}_{{\bm{p}}_{i}}\|,$
(9)

where $\\{\hat{{\bm{x}}}_{{\bm{p}}_{i}}\\}$ is the predicted flow from the
recurrent regularization in the last iteration.

In the training of the point cloud registration network, we first transform
the source point cloud $\mathcal{P}$ with the ground-truth transformation
$\\{{\bm{Q}}^{*},{\bm{T}}^{*}\\}$ and the predicted transformation
$\hat{{\bm{Q}}},\hat{{\bm{T}}}$ respectively, and then compute the difference
between the transformed point clouds as:

$\mathcal{L}_{register}=\frac{1}{M}\sum_{i}\|(\hat{{\bm{Q}}}\cdot{\bm{p}}_{i}+\hat{{\bm{T}}})-({\bm{Q}}^{*}\cdot{\bm{p}}_{i}+{\bm{T}}^{*})\|.$
(10)

###  4.2 Self-supervised Training

The ground truth 3D flow is expensive, so the network needs to utilize the
geometric priors as supervision when there is no access to the ground truth.
Following previous work [64], our self-supervised loss for scene flow is
composed of three terms: Chamfer distance, Smoothness regularization, and
Laplacian regularization [60, 49].

#### Chamfer Term

The Chamfer distance enforces the source point cloud $\mathcal{P}$ to move
close to the target point cloud $\mathcal{Q}$ with the mutual closest points
as:

$\displaystyle\mathcal{L}_{C}=$
$\displaystyle\sum_{{\bm{p}}_{i}\in\mathcal{P}^{\prime}}\min_{{\bm{q}}_{j}\in\mathcal{Q}}\|{\bm{p}}_{i}-{\bm{q}}_{j}\|_{2}^{2}+\sum_{{\bm{q}}_{j}\in\mathcal{Q}}\min_{{\bm{p}}_{i}\in\mathcal{P}^{\prime}}\|{\bm{q}}_{j}-{\bm{p}}_{i}\|_{2}^{2},$
(11)

where $\mathcal{P}^{\prime}$ is transformed from $\mathcal{P}$ by the
predicted 3D flow vectors.

#### Smoothness Term

The smoothness constraint encourages the adjacent points to have similar 3D
flow predictions as:

$\mathcal{L}_{S}=\sum_{i}\frac{1}{|L({\bm{p}}_{i})|}\sum_{{\bm{p}}_{j}\in
L({\bm{p}}_{i})}||\hat{{\bm{x}}}_{{\bm{p}}_{j}}-\hat{{\bm{x}}}_{{\bm{p}}_{i}}||_{2}^{2},$
(12)

where $L({\bm{p}}_{i})$ is the local neighbor region of ${\bm{p}}_{i}$, and
$|L({\bm{p}}_{i})|$ it the number of points in this local region.

#### Laplacian Term

The Laplacian coordinate vector approximates the local shape and curvature
around a point ${\bm{p}}_{i}$ as:

$\delta_{i}=\sum_{i}\frac{1}{|L({\bm{p}}_{i})|}\sum_{{\bm{p}}_{j}\in
L({\bm{p}}_{i})}({\bm{p}}_{j}-{\bm{p}}_{i}).$ (13)

Ideally, the transformed point cloud $\mathcal{P}^{\prime}$ should have the
same Laplacian coordinate with the target point cloud $\mathcal{Q}$. So we
adopt a regularization term based on the Laplacian coordinate similar to [64],
as:

$\mathcal{L}_{R}=\sum_{{\bm{p}}_{i}^{\prime}\in\mathcal{P}^{\prime}}\|\delta({\bm{p}}_{i}^{\prime})-\delta({\bm{q}}_{inter})\|_{2}^{2},$
(14)

where $\delta({\bm{q}}_{inter})$ is the interpolated Laplacian coordinate from
point cloud $Q$ at the same position as ${\bm{p}}_{i}^{\prime}$.

In summary, the self-supervised loss for the scene flow is defined as the
weighted sum of these three terms, as:

$\mathcal{L}_{selflow}=\alpha_{1}\mathcal{L}_{C}+\alpha_{2}\mathcal{L}_{S}+\alpha_{3}\mathcal{L}_{R}.$
(15)

Datasets | Method | Sup. | EPE3D$\downarrow$ | Acc3DS$\uparrow$ | AccDR$\uparrow$ | Outliers3D$\downarrow$
---|---|---|---|---|---|---
FlyingThings3D | ICP[4] | Self | $0.4062$ | $0.1614$ | $0.3038$ | $0.8796$
Ego-motion[53] | Self | $0.1696$ | $0.2532$ | $0.5501$ | $0.8046$
PointPWC-Net[64] | Self | $0.1246$ | $0.3068$ | $0.6552$ | $0.7032$
FlowStep3D[27] | Self | $0.0852$ | $0.5363$ | $0.8262$ | $0.4198$
Ours | Self | $\mathbf{0.0765}$ | $\mathbf{0.5858}$ | $\mathbf{0.8602}$ | $\mathbf{0.4142}$
FlowNet3D[30] | Full | $0.1136$ | $0.4125$ | $0.7706$ | $0.6016$
HPLFlowNet[18] | Full | $0.0804$ | $0.6144$ | $0.8555$ | $0.4287$
PointPWC-Net[64] | Full | $0.0588$ | $0.7379$ | $0.9276$ | $0.3424$
FLOT[37] | Full | $0.0520$ | $0.7320$ | $0.9270$ | $0.3570$
FlowStep3D [27] | Full | $0.0455$ | $0.8162$ | $0.9614$ | $0.2165$
| Ours | Full | $\mathbf{0.0403}$ | $\mathbf{0.8567}$ | $\mathbf{0.9635}$ | $\mathbf{0.1976}$
KITTI | ICP[4] | Self | $0.5181$ | $0.0669$ | $0.1667$ | $0.8712$
Ego-motion[53] | Self | $0.4154$ | $0.2209$ | $0.3721$ | $0.8096$
PointPWC-Net[64] | Self | $0.2549$ | $0.2379$ | $0.4957$ | $0.6863$
FlowStep3D[27] | Self | $0.1021$ | $0.7080$ | $0.8394$ | $0.2456$
Ours | Self | $\mathbf{0.0763}$ | $\mathbf{0.7856}$ | $\mathbf{0.8921}$ | $\mathbf{0.1849}$
FlowNet3D[30] | Full | $0.1767$ | $0.3738$ | $0.6677$ | $0.5271$
HPLFlowNet[18] | Full | $0.1169$ | $0.4783$ | $0.7776$ | $0.4103$
PointPWC-Net[64] | Full | $0.0694$ | $0.7281$ | $0.8884$ | $0.2648$
FLOT[37] | Full | $0.0560$ | $0.7550$ | $0.9080$ | $0.2420$
FlowStep3D [27] | Full | $0.0546$ | $0.8051$ | $0.9254$ | $0.1492$
| Ours | Full | $\mathbf{0.0481}$ | $\mathbf{0.8491}$ | $\mathbf{0.9448}$ | $\mathbf{0.1228}$
Table 1: Evaluation results on the FlyingThings3D [32] and KITTI [33]
datasets. “Self" denotes training under the self-supervised setting while
“Full" denotes under the supervised setting. All methods are only trained on
FlyingThings3D [32]. In default setting, we set the iteration number to 7 and
14 for FlyingThings3D [32] and KITTI [33], respectively.

##  5 Experiments

###  5.1 3D Flow Estimation

#### Dataset

To make a fair comparison, we follow previous works [30, 64, 37, 27] to
evaluate all participating methods on FlyingThings3D [32] and KITTI [33] for
3D flow estimation. The FlyingThings3D is a synthetic dataset that is rendered
from scenes with multiple randomly sampled moving objects from the ShapeNet[5]
dataset. It contains around 32k stereo images with ground truth disparity and
optical flow maps. To use it for 3D flow estimation, we post-process it as in
[64] into 19640 training pairs and 3824 testing pairs of point clouds, and
each point cloud contains 8192 3D points on average. Similarly, the KITTI
scene flow dataset [33] is also originally designed to evaluate the image
based methods. We follow [64] and post-process it into 142 testing pairs
_only_ for evaluation.

#### Training Details

We train and evaluate our method with both the self-supervised and the
supervised setting as described in Sec.4. To speed up the training, we adopt a
two-stage training strategy: first, we set the batch size to 8 on 4 GTX 2080Ti
GPUs, and alternate between the Eq. (7) and the Eq. (LABEL:equ:recurrent) for
3 times. The learning rate adopts the step decay strategy, where the initial
learning rate is set to 1e-3 and then halved every 25 epochs, and 90 epochs
were trained in total; second, we fine-tune the trained model from the first
stage, but iterate more times and train for fewer epochs. We reduce the batch
size to 4 to enable 7 iterations of Eq. (7) and Eq. (LABEL:equ:recurrent). The
initial learning rate is also reduced to 1.25e-4 and then decayed every 5
epochs, and the model is trained for 10 epochs.

#### Quantitative Comparisons

We follow previous works [30, 64, 37, 27] to use the following metrics for
evaluation:

  1. $\bullet$

EPE3D (m): $\sum||F_{pred}-F_{gt}||_{2}/N$ average distance error of all
predicted values

  2. $\bullet$

Acc3DS: the percentage of points which statisfied
$||F_{pred}-F_{gt}||_{2}<0.05m$ or $||F_{pred}-F_{gt}||_{2}/F_{gt}<5\%$

  3. $\bullet$

Acc3DR: the percentage of points which statisfied
$||F_{pred}-F_{gt}||_{2}<0.1m$ or $||F_{pred}-F_{gt}||_{2}/F_{gt}<10\%$

  4. $\bullet$

Outliers3D: the percentage of points which statisfied
$||F_{pred}-F_{gt}||_{2}>0.3m$ or $||F_{pred}-F_{gt}||_{2}/F_{gt}>10\%$.

As shown in Tab. 1, we have achieved state-of-the-art results for both self-
supervised and supervised setting. Specifically, we performs better than the
other methods by a large margin on the KITTI dataset, which demonstrates the
superiority of our formulation in Eq. (7).

Method | MAE(R) | MAE(t) | Error(R) | Error(t)
---|---|---|---|---
ICP[4] | $13.719$ | $0.132$ | $27.250$ | $0.280$
RPM[17] | $9.771$ | $0.092$ | $19.551$ | $0.212$
FGR[71] | $19.266$ | $0.090$ | $30.839$ | $0.192$
PointNetLK[1] | $15.931$ | $0.142$ | $29.725$ | $0.297$
DCP-v2[62] | $6.380$ | $0.083$ | $12.607$ | $0.169$
TEASER++[66] | $4.138$ | $0.020$ | $7.144$ | $0.041$
RPMNet[69] | $0.893$ | $0.0087$ | $1.712$ | $0.018$
Ours | $\mathbf{0.845}$ | $\mathbf{0.0077}$ | $\mathbf{1.665}$ | $\mathbf{0.016}$

Table 2: Evaluation results on ModelNet40 [65] on partially visible setting
with Gaussian noise.

PC1 and PC2

PC1+GT and PC2

PC1+Pred and PC2

Error

Figure 5: Qualitative results on the KITTI [33] scene flow dataset. Iterations | KITTI | FlyingThings3D
---|---|---
EPE3D$\downarrow$ | Acc3DS$\uparrow$ | AccDR$\uparrow$ | Outliers3D$\downarrow$ | EPE3D$\downarrow$ | Acc3DS$\uparrow$ | AccDR$\uparrow$ | Outliers3D$\downarrow$
0 | $0.1696$ | $0.2744$ | $0.5967$ | $0.5671$ | $0.1277$ | $0.1809$ | $0.6127$ | $0.7428$
3 | $0.0660$ | $0.7513$ | $0.8877$ | $0.1893$ | $0.0460$ | $0.80720$ | $0.9517$ | $0.2476$
7 | $0.0570$ | $0.7979$ | $0.9154$ | $0.1566$ | $0.0403$ | $0.8567$ | $0.9635$ | $0.1976$
10 | $0.0521$ | $0.8245$ | $0.9299$ | $0.1385$ | $0.0409$ | $0.8532$ | $0.9631$ | $0.2035$
14 | $0.0481$ | $0.8491$ | $0.9448$ | $0.1228$ | $0.0429$ | $0.8368$ | $0.9606$ | $0.2227$
Table 3: Ablation studies of iterations.

Input

iter=0

iter=1

iter=3

iter=9

iter=14

Figure 6: Visualization of different iterations. As the number of iterations
increases, two point clouds from KITTI[33] scene flow dataset are gradually
aligned together.

###  5.2 Point Cloud Registration

#### Dataset

We follow previous methods [69] to evaluate on the ModelNet40 [65] dataset
which contains 40 object categories of CAD models. Each CAD model is sampled
into 2048 points and normalized into a unit sphere as in [69]. In order to
generate training pairs with ground-truth rigid transformations, we follow
RPMNet[69] to first synthetic transformation and then transform an existing
source point cloud to the target point cloud. The transformation is
synthesized by randomly sampling the rotation vector between
$[0^{\circ},45^{\circ}]$ and the translation vector between $[-0.5,0.5]$. To
simulate the condition of partial-to-partial registration, $30\%$ of the
points are further removed according to a random direction [69]. We use the
first 20 categories for training and validation and the remained 20 categories
for evaluation.

#### Training Details

Compared with the FlyingThings3D, the ModelNet40 is a relatively small scale
dataset, so we train our model for point cloud registration in a single stage,
where the batch size is 8 on each GPU, and alternate between the Eq. (7) and
the Eq. (LABEL:equ:recurrent) for 7 times. The learning rate also adopts the
same decay strategy as above and is decayed every 100 epochs, while the model
is trained 600 epochs.

#### Quantitative Comparisons

The quantitative comparisons follow previous works and use both the isotropic
metrics $Error(R)$ and $Error(t)$ [69] as well as the anisotropic metric
$MAE(R)$ and $MAE(t)$ [62]:

  1. $\bullet$

$Error(R)$: $arcos\frac{tr({R_{gt}}^{-1}R_{pred}-1)}{2}$

  2. $\bullet$

$Error(t)$: $||R_{gt}^{-1}t-t_{gt}||_{2}$

  3. $\bullet$

$MAE(R)$: $||Euler(R_{gt})-Euler(R_{pred})||_{1}$

  4. $\bullet$

$MAE(t)$: $||R_{gt}^{-1}t-t_{gt}||_{1}$.

As shown in Tab. 2, our method outperforms previous methods on both isotropic
metrics and anisotropic metrics.

###  5.3 Ablation Studies

In order to further analyze the effectiveness of each component, we conduct
ablation studies on 3D flow estimation and evaluate different variations of
our model.

#### Point-wise Optimization

The first question is whether we need to further update the transformation
after the recurrent regularization, _i.e_., can we remove the point-wise
optimization Eq. (7) and only preserve the recurrent regularization Eq.
(LABEL:equ:recurrent) to answer this question, we exclude Eq. (7) for both
training and inference, which performs significantly worse as shown in the
first row of Tab. 4 and indicate that the point-wise optimization is
necessary. We also explore different alternative options for point-wise
optimization. First, we only optimize the feature metric distance and do not
constrain the difference between the auxiliary variable $\mathcal{Z}$ and
$\mathcal{X}$. As shown in the second row of Tab. 4, the result is even worse
than not using Eq. (7), which is because the feature distance only is
ambiguous in some regions such as planar areas. Second, we use Eq. (5)
directly instead of the soften version Eq. (7). We train the model with Gumbel
Softmax and inference with argmax. The Gumbel Softmax performs worse than the
soften version in Eq. (7), which is because the gradient back-propagated by
the Eq. (7) is less noisy for training. Additionally, we also evaluate Eq. (6)
using bilateral weight, which performs worse than Eq. (7). Therefore, we use
Eq. (7) as the default setting to minimize Eq. (5) point-wisely.

Point-wise Optimization |  EPE3D$\downarrow$ |  Acc3DS$\uparrow$ |  AccDR$\uparrow$ |  Outliers3D$\downarrow$
---|---|---|---|---
W/O | $0.0514$ | $0.7612$ | $0.9308$ | $0.2880$
Feature Only | $0.0445$ | $0.8327$ | $0.9614$ | $0.2318$
Gumbel Softmax | $0.0451$ | $0.8262$ | $0.9604$ | $0.2370$
Bilateral Weight | $0.0441$ | $0.8361$ | $0.9555$ | $0.2305$
Ours | $0.0403$ | $0.8567$ | $0.9635$ | $0.1976$

Table 4: Ablation studies of point-wise optimization module. We show some
alternative ways.

#### Recurrent Regularization

The second question is whether we need to solve Eq. (4) with a recurrent
network, _i.e_., can we use standard point convolution? We replace the GRU [7]
block with three $set\\_conv$ [39] layers to keep similar model parameters for
fair comparison, which increases the EPE3D from $0.0405$ to $0.0491$ as shown
in Tab. 5. It indicates that the historical information passed by the
recurrent unit regularizes the solution better. We also replace the GRU [7]
unit with LSTM [22], which has slight improvement in Tab. 5. Therefore, we use
GRU [7] as our default recurrent unit because of its simpler formulation.

Recurrent Reg. |  EPE3D$\downarrow$ |  Acc3DS$\uparrow$ |  AccDR$\uparrow$ |  Outliers3D$\downarrow$
---|---|---|---|---
Set_Conv [39] | $0.0491$ | $0.7682$ | $0.9408$ | $0.2823$
GRU [7] | $0.0403$ | $0.8567$ | $0.9635$ | $0.1976$
LSTM [22] | $0.0402$ | $0.8578$ | $0.9642$ | $0.1991$

Table 5: Ablation studies of recurrent regularization module. We use GRU [7]
as our default recurrent unit because of the simple formulation.

#### Number of Iterations:

During training, the final iteration number of Eq. (7) and Eq.
(LABEL:equ:recurrent) is 7. While during inference, we vary the iteration
number from 3 to 14 to investigate how the performance changes along with the
iteration number. As shown in Tab. 3, for the KITTI [33] dataset, all the
metrics are gradually improved along with the increasing iteration number.
However, for the FlyingThings3D[32] dataset, the performance reaches the peak
when the iteration number is exactly the same as training, and gradually
degrades afterward. It is because FlyingThings3D [32] is more challenging
because of its larger motion and more complicated occlusion than KITTI [33].
Therefore, we set the iteration number to 7 for Flyingthings3D [32] and 14 for
KITTI [33] as the default setting.

##  6 Conclusion

We propose a recurrent framework for the 3D motion estimation. To address the
irregularity of the point cloud, we optimize the 3D flows on a point-wise
cost. Then a recurrent network globally regularize the flow to output an
accurate 3D motion estimation. We generalize our method to both the 3D scene
flow estimation task and the point cloud registration task. The experiments
demonstrate that our method outperforms previous methods and achieves a new
state-of-the-art performance across all metrics.

## References

  * [1] Yasuhiro Aoki, Hunter Goforth, Rangaprasad Arun Srivatsan, and Simon Lucey.  PointNetLK: Robust & efficient point cloud registration using pointnet.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 7163–7172, 2019.
  * [2] A. Behl, Despoina Paschalidou, S. Donné, and A. Geiger.  Pointflownet: Learning representations for rigid motion estimation from point clouds.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 7954–7963, 2019.
  * [3] Paul J Besl and Neil D McKay.  Method for registration of 3-d shapes.  In Sensor fusion IV: control paradigms and data structures, volume 1611, pages 586–606. International Society for Optics and Photonics, 1992\.
  * [4] Paul J. Besl and Neil D. McKay.  A method for registration of 3-d shapes.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 14(2):239–256, 1992.
  * [5] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al.  Shapenet: An information-rich 3d model repository.  arXiv preprint arXiv:1512.03012, 2015.
  * [6] Hui Chen and Bir Bhanu.  3D free-form object recognition in range images using local surface patches.  Pattern Recognition Letters, 28(10):1252–1262, 2007.
  * [7] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  arXiv preprint arXiv:1406.1078, 2014.
  * [8] Haili Chui and Anand Rangarajan.  A feature registration framework using mixture models.  In IEEE Workshop on Mathematical Methods in Biomedical Image Analysis. MMBIA-2000 (Cat. No. PR00737), pages 190–197. IEEE, 2000.
  * [9] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [10] Haowen Deng, Tolga Birdal, and Slobodan Ilic.  PPFNet: Global context aware local features for robust 3D point matching.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [11] Ayush Dewan, Tim Caselitz, Gian Diego Tipaldi, and Wolfram Burgard.  Rigid scene flow for 3d lidar scans.  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1765–1770. IEEE, 2016.
  * [12] Zhen Dong, Bisheng Yang, Yuan Liu, Fuxun Liang, Bijun Li, and Yufu Zang.  A novel binary shape context for 3d local surface description.  ISPRS Journal of Photogrammetry and Remote Sensing, 130:431–452, 2017.
  * [13] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 24(6):381–395, 1981.
  * [14] Andrea Frome, Daniel Huber, Ravi Kolluri, Thomas Bülow, and Jitendra Malik.  Recognizing objects in range data using regional point descriptors.  In European Conference on Computer Vision (ECCV), pages 224–237. Springer, 2004.
  * [15] Kexue Fu, Shaolei Liu, Xiaoyuan Luo, and Manning Wang.  Robust point cloud registration framework based on deep graph matching.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8893–8902, 2021.
  * [16] Guy Godin, Marc Rioux, and Rejean Baribeau.  Three-dimensional registration using range and intensity information.  In Sabry F. El-Hakim, editor, Videometrics III, volume 2350, pages 279 – 290. International Society for Optics and Photonics, SPIE, 1994.
  * [17] Steven Gold, Anand Rangarajan, Chien-Ping Lu, Suguna Pappu, and Eric Mjolsness.  New algorithms for 2d and 3d point matching: pose estimation and correspondence.  Pattern recognition, 31(8):1019–1031, 1998.
  * [18] Xiuye Gu, Y. Wang, Chongruo Wu, Y. Lee, and Panqu Wang.  Hplflownet: Hierarchical permutohedral lattice flownet for scene flow estimation on large-scale point clouds.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3249–3258, 2019.
  * [19] Xiaodong Gu, Weihao Yuan, Zuozhuo Dai, Chengzhou Tang, Siyu Zhu, and Ping Tan.  Dro: Deep recurrent optimizer for structure-from-motion.  arXiv preprint arXiv:2103.13201, 2021.
  * [20] Yulan Guo, Mohammed Bennamoun, Ferdous Sohel, Min Lu, Jianwei Wan, and Ngai Ming Kwok.  A comprehensive performance evaluation of 3D local feature descriptors.  International Journal of Computer Vision, 116(1):66–89, 2016.
  * [21] S. Hadfield and R. Bowden.  Kinecting the dots: Particle based scene flow from depth sensors.  In 2011 International Conference on Computer Vision, pages 2290–2295, 2011.
  * [22] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [23] Shengyu Huang, Zan Gojcic, Mikhail Usvyatsov, Andreas Wieser, and Konrad Schindler.  Predator: Registration of 3d point clouds with low overlap.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4267–4276, 2021.
  * [24] F. Huguet and F. Devernay.  A variational method for scene flow estimation from stereo sequences.  In 2007 IEEE 11th International Conference on Computer Vision, pages 1–7, 2007.
  * [25] Eddy Ilg, Nikolaus Mayer, Tonmoy Saikia, Margret Keuper, Alexey Dosovitskiy, and Thomas Brox.  Flownet 2.0: Evolution of optical flow estimation with deep networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2462–2470, 2017.
  * [26] Andrew E Johnson and Martial Hebert.  Using spin images for efficient object recognition in cluttered 3d scenes.  IEEE Transactions on pattern analysis and machine intelligence, 21(5):433–449, 1999.
  * [27] Yair Kittenplon, Yonina C Eldar, and Dan Raviv.  Flowstep3d: Model unrolling for self-supervised scene flow estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4114–4123, 2021.
  * [28] Jiaxin Li and Gim Hee Lee.  USIP: Unsupervised stable interest point detection from 3d point clouds.  In International Conference on Computer Vision (ICCV), 2019.
  * [29] Y. Li, M. Tofighi, V. Monga, and Y. C. Eldar.  An algorithm unrolling approach to deep image deblurring.  In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7675–7679, 2019.
  * [30] Xingyu Liu, Charles R Qi, and Leonidas J Guibas.  Flownet3d: Learning scene flow in 3d point clouds.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 529–537, 2019.
  * [31] Weixin Lu, Guowei Wan, Yao Zhou, Xiangyu Fu, Pengfei Yuan, and Shiyu Song.  DeepICP: An end-to-end deep neural network for 3D point cloud registration.  In International Conference on Computer Vision (ICCV), 2019.
  * [32] Nikolaus Mayer, Eddy Ilg, Philip Hausser, Philipp Fischer, Daniel Cremers, Alexey Dosovitskiy, and Thomas Brox.  A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [33] Moritz Menze, Christian Heipke, and Andreas Geiger.  Joint 3d estimation of vehicles and scene flow.  In Proc. of the ISPRS Workshop on Image Sequence Analysis (ISA), 2015.
  * [34] Vishal Monga, Yuelong Li, and Yonina C Eldar.  Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing.  arXiv preprint arXiv:1912.10557, 2019.
  * [35] Yue Pan, Bisheng Yang, Fuxun Liang, and Zhen Dong.  Iterative global similarity points: A robust coarse-to-fine integration solution for pairwise 3d point cloud registration.  In 2018 International Conference on 3D Vision (3DV), pages 180–189. IEEE, 2018.
  * [36] François Pomerleau, Francis Colas, and Roland Siegwart.  A review of point cloud registration algorithms for mobile robotics.  Foundations and Trends in Robotics, 4(1):1–104, 2015.
  * [37] Gilles Puy, Alexandre Boulch, and Renaud Marlet.  Flot: Scene flow on point clouds guided by optimal transport.  In European conference on computer vision, pages 527–544. Springer, 2020.
  * [38] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652–660, 2017.
  * [39] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  In Advances in neural information processing systems, pages 5099–5108, 2017.
  * [40] Szymon Rusinkiewicz.  A symmetric objective function for icp.  ACM Transactions on Graphics (TOG), 38(4):1–7, 2019.
  * [41] Szymon Rusinkiewicz and Marc Levoy.  Efficient variants of the icp algorithm.  In Proceedings third international conference on 3-D digital imaging and modeling, pages 145–152. IEEE, 2001.
  * [42] Radu Bogdan Rusu, Nico Blodow, and Michael Beetz.  Fast point feature histograms (FPFH) for 3D registration.  In IEEE International Conference on Robotics and Automation (ICRA), pages 3212–3217, 2009.
  * [43] Radu Bogdan Rusu, Nico Blodow, Zoltan Csaba Marton, and Michael Beetz.  Aligning point cloud views using persistent feature histograms.  In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3384–3391, 2008.
  * [44] Samuele Salti, Federico Tombari, and Luigi Di Stefano.  Shot: Unique signatures of histograms for surface and texture description.  Computer Vision and Image Understanding, 125:251–264, 2014.
  * [45] Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  Superglue: Learning feature matching with graph neural networks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4938–4947, 2020.
  * [46] Vinit Sarode, Xueqian Li, Hunter Goforth, Yasuhiro Aoki, Rangaprasad Arun Srivatsan, Simon Lucey, and Howie Choset.  PCRNet: Point cloud registration network using pointnet encoding.  In International Conference on Computer Vision (ICCV), 2019.
  * [47] Aleksandr Segal, Dirk Haehnel, and Sebastian Thrun.  Generalized-icp.  In Robotics: science and systems, volume 2, page 435. Seattle, WA, 2009.
  * [48] Richard Sinkhorn.  A relationship between arbitrary positive matrices and doubly stochastic matrices.  The annals of mathematical statistics, 35(2):876–879, 1964.
  * [49] Olga Sorkine.  Laplacian Mesh Processing.  In Yiorgos Chrysanthou and Marcus Magnor, editors, Eurographics 2005 - State of the Art Reports. The Eurographics Association, 2005.
  * [50] Frank Steinbrücker, Thomas Pock, and Daniel Cremers.  Large displacement optical flow computation withoutwarping.  In 2009 IEEE 12th International Conference on Computer Vision, pages 1609–1614. IEEE, 2009.
  * [51] Deqing Sun, Xiaodong Yang, Ming-Yu Liu, and Jan Kautz.  Pwc-net: Cnns for optical flow using pyramid, warping, and cost volume.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8934–8943, 2018.
  * [52] Zachary Teed and Jia Deng.  Raft: Recurrent all-pairs field transforms for optical flow.  In European conference on computer vision, pages 402–419. Springer, 2020.
  * [53] Ivan Tishchenko, Sandro Lombardi, Martin R Oswald, and Marc Pollefeys.  Self-supervised learning of non-rigid residual flow and ego-motion.  In 2020 International Conference on 3D Vision (3DV), pages 150–159. IEEE, 2020.
  * [54] Federico Tombari, Samuele Salti, and Luigi Di Stefano.  Unique shape context for 3D data description.  In ACM Workshop on 3D Object Retrieval, 3DOR ’10, pages 57–62. ACM, 2010.
  * [55] Yanghai Tsin and Takeo Kanade.  A correlation-based approach to robust point set registration.  In European Conference on Computer Vision (ECCV), pages 558–569. Springer, 2004.
  * [56] Arash K Ushani and Ryan M Eustice.  Feature learning for scene flow estimation from lidar.  In Conference on Robot Learning, pages 283–292. PMLR, 2018.
  * [57] Arash K Ushani, Ryan W Wolcott, Jeffrey M Walls, and Ryan M Eustice.  A learning approach for real-time temporal scene flow estimation from lidar data.  In Proceedings of the IEEE International Conference on Robotics and Automation, pages 5666–5673. IEEE, 2017.
  * [58] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [59] Sundar Vedula, Simon Baker, Peter Rander, Robert Collins, and Takeo Kanade.  Three-dimensional scene flow.  In Proceedings of the International Conference on Computer Vision, volume 2, pages 722–729. IEEE, 1999.
  * [60] Nanyang Wang, Yinda Zhang, Zhuwen Li, Yanwei Fu, Wei Liu, and Yu-Gang Jiang.  Pixel2mesh: Generating 3d mesh models from single rgb images.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 52–67, 2018.
  * [61] Shenlong Wang, Simon Suo, Wei-Chiu Ma, Andrei Pokrovsky, and Raquel Urtasun.  Deep parametric continuous convolutional neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2589–2597, 2018.
  * [62] Yue Wang and Justin M. Solomon.  Deep closest point: Learning representations for point cloud registration.  In International Conference on Computer Vision (ICCV), 2019.
  * [63] Yue Wang and Justin M Solomon.  Prnet: Self-supervised learning for partial-to-partial registration.  In Advances in Neural Information Processing Systems 32, pages 8814–8826. Curran Associates, Inc., 2019.
  * [64] Wenxuan Wu, Zhi Yuan Wang, Zhuwen Li, Wei Liu, and Li Fuxin.  Pointpwc-net: Cost volume on point clouds for (self-) supervised scene flow estimation.  In European conference on computer vision, pages 88–107. Springer, 2020.
  * [65] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3D ShapeNets: A deep representation for volumetric shapes.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1912–1920, 2015.
  * [66] Heng Yang, Jingnan Shi, and Luca Carlone.  Teaser: Fast and certifiable point cloud registration.  IEEE Transactions on Robotics, 37(2):314–333, 2020.
  * [67] Jiaolong Yang, Hongdong Li, Dylan Campbell, and Yunde Jia.  Go-ICP: A globally optimal solution to 3D ICP point-set registration.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 38(11):2241–2254, 2015.
  * [68] Zi Jian Yew and Gim Hee Lee.  3DFeat-Net: Weakly supervised local 3D features for point cloud registration.  In European Conference on Computer Vision (ECCV). Springer, 2018\.
  * [69] Zi Jian Yew and Gim Hee Lee.  Rpm-net: Robust point matching using learned features.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11824–11833, 2020.
  * [70] Andy Zeng, Shuran Song, Matthias Nießner, Matthew Fisher, Jianxiong Xiao, and Thomas Funkhouser.  3DMatch: Learning local geometric descriptors from RGB-D reconstructions.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 199–208, 2017.
  * [71] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun.  Fast global registration.  In European Conference on Computer Vision, pages 766–782. Springer, 2016.


# DICE: Diverse Diffusion Model with Scoring for Trajectory Prediction

Younwoo Choi1, Ray Coden Mercurius2, Soheil Mohamad Alizadeh Shabestary2, Amir
Rasouli2 1 University of Toronto. Work done while at Huawei.
<EMAIL_ADDRESS>Ark Laboratory, Huawei, Canada.
<EMAIL_ADDRESS>
###### Abstract

Road user trajectory prediction in dynamic environments is a challenging but
crucial task for various applications, such as autonomous driving. One of the
main challenges in this domain is the multimodal nature of future trajectories
stemming from the unknown yet diverse intentions of the agents. Diffusion
models have shown to be very effective in capturing such stochasticity in
prediction tasks. However, these models involve many computationally expensive
denoising steps and sampling operations that make them a less desirable option
for real-time safety-critical applications. To this end, we present a novel
framework that leverages diffusion models for predicting future trajectories
in a computationally efficient manner. To minimize the computational
bottlenecks in iterative sampling, we employ an efficient sampling mechanism
that allows us to maximize the number of sampled trajectories for improved
accuracy while maintaining inference time in real time. Moreover, we propose a
scoring mechanism to select the most plausible trajectories by assigning
relative ranks. We show the effectiveness of our approach by conducting
empirical evaluations on common pedestrian (UCY/ETH) and autonomous driving
(nuScenes) benchmark datasets on which our model achieves state-of-the-art
performance on several subsets and metrics.

##  I Introduction

Accurate prediction of road user behavior is prerequisite to safe motion
planning in autonomous driving systems. One of the key challenges in
trajectory prediction is the probabilistic and multimodal nature of road
users’ behaviors. To model such uncertainty, many approaches have been
proposed, such as Generative Adversarial Networks (GANs) [7, 11, 17, 47],
Conditional Variational Autoencoder (CVAE) [5, 21, 25, 28, 44], anchor-based
proposal networks [51], or target (intention) prediction networks [6, 62, 15].
However, these methods are not without challenges, encompassing issues, such
as unstable training, artificial dynamics within predicted trajectories, and
reliance on hand-crafted heuristics that lack generalizability.

Diffusion models have recently gained popularity as powerful tools for various
generative tasks in machine learning [41, 43, 18, 56]. These models learn the
process of transforming informative data into Gaussian noise and how to
reversely generate meaningful output from noisy data. Although effective,
diffusion models impose high computational costs due to successive denoising
and sampling operations making their performance limited for real-time
applications, such as trajectory prediction.

To this end, we propose a novel computationally efficient diffusion-based
model for road user trajectory prediction. Our approach benefits from the
efficient sampling method, Denoising Diffusion Implicit Models (DDIM) [46]
resulting in $20\times$ computational speed-up, allowing us to oversample from
trajectory distributions in order to maximize the diversity and coverage of
predicted trajectories, while maintaining the inference speed well below
existing approaches. To select the most likely trajectory candidates, we
propose a novel scoring network that assigns relative rankings in conjunction
with a non-maximum suppression operation in order to downsample the
trajectories into the final prediction set. To highlight the effectiveness of
our approach, we conduct extensive empirical studies on common trajectory
prediction benchmark datasets, UCY/ETH [26, 10] and nuScenes [3], and show our
model achieves state-of-the-art performance on some subsets and metrics while
maintaining real-time inference time.

##  II Related Work

###  II-A Trajectory Prediction

Trajectory prediction is modeled as a sequence prediction problem where the
future of the agents is predicted based on their observed history and
potentially available contextual information. In the pedestrian prediction
domain, one of the key challenges is to model the interactions among
pedestrians for better estimates of their future behavior. These methods
include, spatial pooling of representations [1], graph architectures [20, 21,
34, 44, 48, 58], attention mechanisms [12, 24, 42, 53, 60], and in egocentric
setting, semantic scene reasoning [39, 38]. In the context of autonomous
driving, it is also important to model agent-to-map interactions. For this
purpose, models rely on environment representations in the form of drivable
areas [36, 2], rasterized maps [44, 14], point-clouds [57], and
computationally efficient vectorized representations in conjunction with graph
neural networks [13, 15], or transformers [64, 35] for generating holistic
representations of the scenes and interactions.

Another main challenge in trajectory prediction is to capture the uncertainty
and multi-modality in the agent’s behaviour. To address this problem, a
category of models resort to explicitly predicting the goal (intentions or
target) of agents and predict future trajectories conditional on those goals,
which are typically defined using heuristic methods, which limit the
generalizability of these approaches [62, 15]. Other methods, such as
Generative Adversarial Networks (GANs) [7, 11, 17, 47] and Conditional
Variational Autoencoders (CVAEs) [5, 21, 25, 28, 44] implicitly capture
agents’ intentions. These methods introduce latent variables that are randomly
sampled from a simple distribution to produce complex and multi-modal
distributions for the predicted trajectories. However, existing generative
models suffer from limitations, such as mode collapse, unstable training, or
the generation of unrealistic trajectories [50, 63], highlighting the need for
more robust and accurate models.

###  II-B Denoising Diffusion Models

Denoising Diffusion Probabilistic Models (DDPM) [19], commonly referred to as
diffusion models have gained popularity various generative tasks such as image
[41, 43], audio [23], video [18, 56], and 3D point cloud generation [31].
These models simulate a diffusion process motivated by non-equilibrium
thermodynamics, where a parameterized Markov chain is learned to gradually
transition from a noisy initial state to a specific data distribution. More
recently, diffusion methods have been adopted in trajectory generation and
prediction tasks [16, 22, 40]. The approach in [16] models the indeterminacy
of human behaviour using a transformer-based trajectory denoising module to
capture complex temporal dependencies across trajectories. The authors of [40]
introduce a model for generating realistic pedestrian trajectories that can be
controlled to meet user-defined goals by implementing a guided diffusion
model. MotionDiffuser introduced in [22] creates a diffusion framework for
multi-agent joint prediction with optional attractor and repeller guidance
functions to enforce compliance with prior knowledge, such as agent intention
and accident avoidance.

Although diffusion-based models have proven effective, there exist critical
shortcomings to their adoption in practice. For instance, the inference time
of these models is highly computationally expensive due to an iterative
denoising algorithm that requires a large number of forward passes. For
example, MotionDiffuser’s inference latency is 408.5ms (32 diffusion steps)
compared to the conventional prediction models, such as HiVT’s [64] with 69ms
latency. This characteristic makes diffusion models a less desirable option
for real-time safety-critical applications, such as autonomous driving. To
speed-up prediction inference time, Leapfrog Diffusion Model (LED) [32] is
proposed that learns to skip a large number of denoising steps in order to
accelerate inference speed. However, LED is only effective when dealing with
small dimensional trajectory data without any complex contextual encoding. To
address this shortcoming, in the proposed approach we focus on improving
efficiency at the sampling stage providing a more general framework for
different data representation.

Contributions of this paper are threefold: 1) We propose a novel diffusion-
based model for trajectory prediction that relies on efficient sampling
operation for over-sampling trajectories and a novel scoring mechanism for
relatively ranking them to produce final prediction set; 2) we conduct
empirical evaluation by comparing the proposed approach to the past arts and
highlight the effectiveness of our approach in both pedestrian and autonomous
driving prediction domains; 3) We conduct ablation studies on the effect of
proposed scoring scheme and oversampling on the accuracy of prediction and
inference time.

Figure 1: Overview of the proposed framework. During training of decoder
$\bm{\epsilon}_{\theta}$, encoder $f_{\xi}$ encodes the history and the map
into a feature embedding. Using diffusion step $\eta$, the feature embedding,
and noisy $\mathbf{y}_{(\eta)}$, decoder $\bm{\epsilon}_{\theta}$ generates
noise $\epsilon$ to noise clean $\mathbf{y}_{(0)}$ into $\mathbf{y}_{(\eta)}$.
In the second stage, scoring network $g_{\phi}$ takes $M$ generated
trajectories $\hat{\bm{\tau}}_{j}$ using efficient DDIM sampling method along
with the feature embedding from the encoder. A non-maximum suppression
algorithm is applied to trajectories sorted in descending order based on their
predicted scores, from which final $K$ trajectories are selected.

##  III Methodology

###  III-A Problem Formulation

We represent the future trajectory of an agent $i$,
$\bm{\tau}^{i}_{future}=[\bm{p}_{t+1}^{i},\ldots,\bm{p}_{t+T_{f}}^{i}]$ over
$T_{f}$ time steps where $\bm{p}^{i}\in\mathbb{R}^{2}$ is the 2D coordinates
of the agent. Similarly, the agent’s trajectory over the last $T_{p}$ time
steps is
$\bm{\tau}^{i}_{past}=[\bm{p}_{t-T_{p}+1}^{i},\ldots,\bm{p}_{t}^{i}]$. Here,
the objective is to learn distribution $p(\tau_{future}^{i}|\tau_{past}^{i})$.

###  III-B Architecture

An overview of the proposed framework is illustrated in Figure 1. Our model
consists of an input layer containing trajectory history and lane information
(if map information is available); An encoder inspired by [64] that encoded
interactions between agents and agents and road lanes (if map is available); A
decoder based on [16] comprised of multiple transformer layers. The decoder is
trained to generate meaningful trajectories from noisy data conditioned on the
scene context and used iteratively in each step of the denoising; And lastly,
an attention-based scorer ranks the generated trajectories. In the following
subsections, we describe the key components of the proposed model.

###  III-C Data Processing

Inspired by [64], we use translation- and rotation-invariant scene
representation vectors by converting absolute positions to relative positions
and rotating them according to the heading angle of each agent denoted by
$\theta^{i}$ at the current timestamp $t$. We convert the trajectory
coordinates into displacements, and rotate them so that all agents have the
same heading at time step zero. Each trajectory is represented as
$\mathbf{x}^{i}=[0,\mathbf{R}_{i}^{T}(\bm{p}_{t-T_{p}+2}^{i}-\bm{p}_{t-T_{p}+1}^{i}),\ldots,\mathbf{R}_{i}^{T}(\bm{p}_{t}^{i}-\bm{p}_{t-1}^{i})]$,
where $\mathbf{R}_{i}\in\mathbb{R}^{2\times 2}$ is the rotation matrix
parameterized by $\theta^{i}$.
$\mathbf{X}=[\mathbf{x}^{1},\ldots,\mathbf{x}^{N}]\in\mathbb{R}^{N\times
T_{p}\times 2}$ is the set of agents’ observations, where $N$ denotes the
number of agents in a scene. Using this representation makes the model robust
to both translation and rotation and consequently requires less training data
as no rotation-augmented data is needed as in the case of other methods.
Contrary to the standard approach in the literature, we also convert future
trajectories $\bm{\tau}^{i}_{future}$ to the displacement of relative
positions rotated and centered at the last point of the history, that is
$\mathbf{y}^{i}=[\mathbf{R}_{i}^{T}(\bm{p}_{t+1}^{i}-\bm{p}_{t}^{i}),\ldots,\mathbf{R}_{i}^{T}(\bm{p}_{t+T_{f}}^{i}-\bm{p}_{t+T_{f}-1}^{i})]$.

###  III-D Conditional Diffusion Model for Trajectory Prediction

The forward diffusion process is a Markov chain that gradually adds Gaussian
noise to a sample drawn from the data distribution, $\mathbf{y}_{(0)}\sim
q(\mathbf{y})$, iteratively for $H$ times, in order to produce progressively
noisier samples. The approximate posterior distribution is given by,

$q(\mathbf{y}_{(1:H)}|\mathbf{y}_{(0)})=\prod^{H}_{\eta=1}q(\mathbf{y}_{(\eta)}|\mathbf{y}_{(\eta-1)})$
$None$
$q(\mathbf{y}_{(\eta)}|\mathbf{y}_{(\eta-1)})=\mathcal{N}(\mathbf{y}_{(\eta)};\sqrt{1-\beta_{\eta}}\mathbf{y}_{(\eta-1)},\beta_{\eta}\mathbf{I})$
$None$

where $H$ denotes the total number of diffusion steps and $\beta_{\eta}$ is a
uniformly increasing variance to control the level of noise. By setting
$\alpha_{\eta}=1-\beta_{\eta}$ and
$\bar{a}_{\eta}=\prod^{\eta}_{s=1}\alpha_{s}$, we get,

$q(\mathbf{y}_{(\eta)}|\mathbf{y}_{(0)})=\mathcal{N}(\mathbf{y}_{(\eta)};\sqrt{\bar{\alpha}}_{\eta}\mathbf{y}_{(0)},(1-\bar{\alpha}_{\eta})\mathbf{I})$
$None$

Here, if $H$ is large enough,
$q(\mathbf{y}_{(H)})\sim\mathcal{N}(\mathbf{y}_{(H)};\bm{0},\mathbf{I})$,
where $\mathcal{N}$ is a normal distribution.

For future trajectory prediction, we apply the reverse diffusion process by
reducing noise from trajectories sampled under the noise distribution. The
initial noisy trajectory is sampled from a normal distribution
$\mathcal{N}(\mathbf{y}_{(H)};\bm{0},\mathbf{I})$, and then it is iteratively
run through conditioned denoising transition
$p_{\theta}(\mathbf{y}_{(\eta-1)}|\mathbf{y}_{(\eta)},\bm{C})$ parameterized
by $\theta$ for $H$ steps. Here, $\bm{C}\in\mathbb{R}^{d_{c}}$ denotes a
feature embedding with the dimension of $d_{c}$. representing the scene
context, learned by encoder $f_{\xi}$ parameterized by $\xi$. Formally, the
process is as follows,

$p_{\theta}(\mathbf{y}_{(0:H)})=p(\mathbf{y}_{(H)})\prod^{H}_{\eta=1}p_{\theta}(\mathbf{y}_{(\eta-1)}|\mathbf{y}_{(\eta)})$
$None$

At each step $\eta$, we have

$p_{\theta}(\mathbf{y}_{(\eta-1)}|\mathbf{y}_{(\eta)},\bm{C})=\mathcal{N}(\mathbf{y}_{(\eta-1)};\bm{\mu}_{\theta}(\mathbf{y}_{(\eta)},\eta,\bm{C}),\bm{\Sigma}_{(\eta)})$
$None$

where $p(\mathbf{y}_{(H)})=\mathcal{N}(\mathbf{y}_{(H)};\bm{0},\mathbf{I})$
and $\bm{\Sigma}_{(\eta)}$ is a fixed variance scheduler,
$\beta_{(\eta)}\mathbf{I}$.

###  III-E Scoring Network

Generative models, such as CVAEs [45] and diffusion models [19] are capable of
producing multiple outputs by sampling from an underlying distribution.
Specifically, CVAEs repeatedly sample a latent variable from a prior
distribution for decoding. Diffusion models generate multiple outputs by
repeatedly sampling independent noise
$\mathbf{y}_{(H)}\sim\mathcal{N}(\bm{0},\mathbf{I})$ $M$ times and denoising
them resulting in a wide range of varied outputs with complex distributions.
With a large number of samples, one can accurately approximate the
distribution parameterized by the models. However, in practice, for
efficiency, a smaller set of $K$ predictions are used to characterize the
performance of the models. Therefore, we require a downsampling (or selection)
mechanism to select the most plausible $K$ predictions.

Our goal is to select $K$ most plausible trajectories among $M$ denoised
samples given the feature embedding $\bm{C}$, where $K<<M$. We achieve this by
training scoring network $g_{\phi}(\cdot)$, parameterized by $\phi$. The
scoring network takes $M$ denoised samples and encoder’s embedding $\bm{C}$ as
input and outputs a score for each of $M$ trajectories conditioned on $\bm{C}$
and the rest of $M-1$ trajectories. For this purpose, we first concatenate
each trajectory with feature embedding $\bm{C}$,
$\bm{s}_{j}=\hat{\bm{\tau}}_{j}\oplus\bm{C}$ for $j=1,\ldots,M$, where
$\hat{\bm{\tau}}_{j}$ is predicted trajectory converted from the $j$th
denoised sample $\hat{\mathbf{y}}_{(0)}^{j}$. We define the matrix
$\bm{S}=[\bm{s}_{1},...,\bm{s}_{M}]\in\mathbb{R}^{M\times(T_{f}+d_{c})}$,
which is then fed into a multi-head self-attention block [52],

$\bm{Q}_{i}=\bm{S}\bm{W}^{Q}_{i},\bm{K}_{i}=\bm{S}\bm{W}^{K}_{i},\bm{V}_{i}=\bm{S}\bm{W}^{V}_{i}$
$None$
$\text{Attn}_{i}(\bm{S})=\text{softmax}(\frac{1}{\sqrt{d_{k}}}\bm{Q}_{i}\bm{K}^{T}_{i})\bm{V}_{i}$
$None$
$\text{MHA}(\bm{S})=\text{Concat}(\text{Attn}_{1}(\bm{S}),\ldots,\text{Attn}_{h}(\bm{S}))\bm{W}^{O}$
$None$

where $h$ is the number of attention heads,
$\bm{W}^{Q}_{i},\bm{W}^{K}_{i},\bm{W}^{V}_{i}\in\mathbb{R}^{(T_{f}+d_{c})\times
d_{k}}$ for $i=1,\ldots,h$, $d_{c}$ and $d_{k}$ are the dimensions of the
feature embedding and attention, respectively, and
$\bm{W}^{O}\in\mathbb{R}^{h\cdot d_{k}\times d}$ are the learnable parameters
of the multi-head attention module. Next, we apply an MLP layer with residual
connection followed by downsampling $d$ to a 1-dimensional score:

$\hat{\bm{S}}=g_{\phi}(\bm{S})=(\text{MHA}(\bm{S})+\text{MLP}(\text{MHA}(\bm{S})))\bm{W}^{down}$
$None$

where $\bm{W}^{down}\in\mathbb{R}^{d\times 1}$ is a trainable parameter
matrix. Finally, we have predicted relative raw scores
$\hat{\bm{S}}\in\mathbb{R}^{{}^{M}}$ conditioned on a scene. The scores are
normalized using a softmax operation.

###  III-F Training

As shown in Figure 1, the training process consists of two stages. First, we
train denoising module $p_{\theta}$ and encoder $f_{\xi}$, and in the second
stage, we train scoring network $g_{\phi}$ with frozen $p_{\theta}$ and
$f_{\xi}$.

Diffusion The model is optimized by maximizing the log-likelihood of the
predicted trajectories given the ground truth $\mathbb{E}[\log
p_{\theta}(\mathbf{y}_{(0)})]$. Since the exact log-likelihood is intractable,
we follow the standard Evidence Lower Bound (ELBO) maximization method and
minimize the KL Divergence,

$\mathcal{L}=\mathbb{E}_{q,\eta}[D_{KL}(q(\mathbf{y}_{(\eta-1)}|\mathbf{y}_{(\eta)},\mathbf{y}_{(0)})||p_{\theta}(\mathbf{y}_{(\eta-1)}|\mathbf{y}_{(\eta)},\bm{C}))]$
$=\mathbb{E}_{q,\eta}[D_{KL}(\mathcal{N}(\mathbf{y}_{(\eta-1)};\bm{\mu}_{q},\bm{\Sigma}_{q}(\eta)||\mathcal{N}(\mathbf{y}_{(\eta-1)};\bm{\mu}_{\theta},\bm{\Sigma}_{(\eta)}))]$
$=\mathbb{E}_{q,\eta}[||\bm{\mu}_{\theta}-\bm{\mu}_{q}||_{2}^{2}]$ $None$

By utilizing the reparameterization trick, the corresponding optimization
problem becomes [19]:

$\mathcal{L}_{MSE}(\theta,\xi)=\mathbb{E}_{\bm{\epsilon}_{(0)},\mathbf{y}_{(0)},\eta}||\bm{\epsilon}_{(0)}-\hat{\bm{\epsilon}}_{(\theta,\xi)}(\mathbf{y}_{(\eta)},\eta,\bm{C})||$
$None$

where $\bm{\epsilon}_{(0)}\sim\mathcal{N}(\bm{0},\mathbf{I})$,
$\mathbf{y}_{(\eta)}=\sqrt{\bar{\alpha_{\eta}}}\mathbf{y}_{(0)}+\sqrt{1-\bar{\alpha}_{\eta}}\bm{\epsilon}_{(0)}$.
In other words, denoising module $\hat{\bm{\epsilon}}_{(\theta,\xi)}$ learns
to predict the source noise
$\bm{\epsilon}_{(0)}\sim\mathcal{N}(\bm{\epsilon};\bm{0},\mathbf{I})$ that
noises $\mathbf{y}_{(0)}$ to $\mathbf{{y}_{(\eta)}}$.

Scorer We use cross-entropy loss between the predicted scores
$\text{softmax}(\hat{\bm{S}})$ and scores calculated using the ground truth
future trajectories $\bm{\tau}_{future}$ and the predicted future trajectories
$\\{\hat{\bm{\tau}}_{j}\\}_{j=1}^{M}$. A combination of Average Displacement
Error (ADE) and final Displacement Error (FDE) is used to calculate the
scores,

$\psi_{j}=ADE(\bm{\tau}_{future},\hat{\bm{\tau}}_{j})+\lambda
FDE(\bm{\tau}_{future},\hat{\bm{\tau}}_{j})$ $None$

where $\psi_{j}$ represents the closeness of $j$th predicted trajectory to the
ground truth trajectory, and $\lambda$ balances how metrics ADE and FDE affect
the score. $\Psi\in\mathbb{R}^{M}$ denotes the matrix of $M$ ground truth
scores (i.e., $j$th element of $\Psi$ is $\psi_{j}$). We use a cross-entropy
loss to train the scoring network,

$\mathcal{L}_{scorer}=\mathcal{L}_{CE}(\text{softmax}(\hat{\bm{S}}),\Psi)$
$None$

###  III-G Inference

As shown in Figure 1, inference is a two-stage process: we first oversample
$M$ trajectories and denoise them using the denoising module, and then we
select the top plausible trajectories.

Diffusion We begin by sampling $M$ independent Gaussian noises
$\\{\mathbf{y}_{(H)}^{j}:\mathbf{y}_{(H)}\sim\mathcal{N}(\bm{0},\mathbf{I})\\}_{j=1}^{M}$.
Next, we denoise each $\mathbf{y}_{(H)}^{j}$ through reverse process
$p_{\theta}$. During the reverse process, DDPM [19] sampling technique
repeatedly denoises $\mathbf{y}_{(H)}$ to $\mathbf{y}_{(0)}$ by using equation
below for $H$ steps,

$\mathbf{y}_{(\eta-1)}=\frac{1}{\sqrt{\alpha_{\eta}}}(\mathbf{y}_{\eta}-\frac{\beta_{\eta}}{\sqrt{1-\bar{\alpha_{\eta}}}}\hat{\bm{\epsilon}}_{(\theta,\xi)}(\mathbf{y}_{(\eta)},\eta,\bm{C}))+\sqrt{\beta_{\eta}}\bm{z}$
$None$

where $\bm{z}\sim\mathcal{N}(\bm{0},\mathbf{I})$. The downside of the DDPM
sampling is that it requires $H$ denoising steps in order to generate a
sample, which is time-consuming and computationally expensive, especially when
$H$ is large (usually $H>100$). To mitigate this issue, we use the DDIM [46]
sampling technique and skip every $\gamma$ step in the reverse process, in
which we only iterate $\frac{H}{\gamma}$ steps leading to more efficient and
faster operation compared DDPM by a factor of $\gamma$,

$\mathbf{y}_{(\eta-1)}=\sqrt{\bar{\alpha}_{(\eta-1)}}(\frac{\mathbf{y}_{(\eta)}-\sqrt{1-\bar{\alpha}_{(\eta)}}\hat{\bm{\epsilon}}_{(\theta,\xi)}(\mathbf{y}_{(\eta)},\eta,\bm{C})}{\sqrt{\bar{\alpha}_{(\eta)}}})$
$+\sqrt{1-\bar{\alpha}_{(\eta-1)}}\hat{\bm{\epsilon}}_{(\theta,\xi)}(\mathbf{y}_{(\eta)},\eta,\bm{C})$
$None$

Scoring and selection Using the scoring network, we select $K$ out of $M$
oversampled trajectories that are generated by the diffusion model. We first
convert predicted displacements,
$\hat{\mathbf{y}}_{(0)}=[\hat{\mathbf{y}}_{t+1},\ldots,\hat{\mathbf{y}}_{t+T_{f}}]$
back to relative positions $\hat{\bm{\tau}}$:

$\hat{\bm{\tau}}_{future}=[\hat{\bm{p}}_{t+1},\ldots,\hat{\bm{p}}_{t+T_{f}}]$
$None$
$\hat{\bm{p}}_{t+j}=\sum_{i^{\prime}=0}^{j}(\mathbf{R}^{-1})^{T}\hat{\bm{y}}_{t+i^{\prime}}$
$None$

where $\mathbf{R}^{-1}$ is the reverse of the rotation matrix used in the
preprocessing. Following [62], given the scores, we ensure diversity and
sufficient multi-modal coverage by applying a non-maximum suppression
operation. For this, we sort the trajectories according to their scores,
starting with the highest one. If it is greater than the optimized distance
threshold $\omega$ from all previously selected trajectories, we select it. We
continue until we have $K$ trajectories.

TABLE I: Quantitative results on the UCY/ETH benchmark.
$\text{minADE}_{20}$/$\text{minFDE}_{20}$ are reported. Bold numbers indicate
the best performance for each metric, underline indicates the second best
performance for each metric. ∗ indicates that the initial results in the paper
are not fairly measured due to the leakage of future paths. We refer to [27]
for the corrected results.

Method | ETH | Hotel | Univ | Zara1 | Zara2 | Avg
---|---|---|---|---|---|---
SocialGAN [17] | 0.81/1.52 | 0.72/1.61 | 0.60/1.26 | 0.34/0.69 | 0.42/0.84 | 0.58/1.18
SoPhie [42] | 0.70/1.43 | 0.76/1.67 | 0.54/1.24 | 0.30/0.63 | 0.38/0.78 | 0.54/1.15
Social-STGCNN [34] | 0.64/1.11 | 0.49/0.85 | 0.44/0.79 | 0.34/0.53 | 0.30/0.48 | 0.44/0.75
Trajectron++∗ [44] | 0.67/1.18 |  0.18/0.28 |  0.30/0.54 | 0.25/0.41 |  0.18/0.32 | 0.32/0.55
GroupNet [54] |  0.46/0.73 |  0.15/0.25 |  0.26/0.49 |  0.21/0.39 |  0.17/0.33 |  0.25/0.44
MID (Diffusion)∗ [16] | 0.54/0.82 | 0.20/0.31 |  0.30/0.57 | 0.27/0.46 | 0.20/0.37 | 0.30/0.51
DICE (ours) |  0.24/0.34 |  0.18/0.23 | 0.52/0.61 | 0.24/0.37 | 0.20/0.30 |  0.26/0.35

##  IV Experiments

###  IV-A Experimental Setup

Datasets. We evaluate the proposed model on both pedestrian and autonomous
driving prediction benchmarks. For the former, we report on UCY/ETH [26, 10],
which consists of real pedestrian trajectories at five different locations
captured at 2.5 Hz, ETH and HOTEL from ETH dataset, and UNIV, ZARA1, and ZARA2
are from UCY dataset. Following previous works, we use the leave-one-out
approach with four sets for training and the remaining set for testing [32,
55]. For autonomous driving, we  nuScenes [3], a large-scale real-world
autonomous driving dataset, which contains 1000 scenes from Boston and
Singapore annotated at 2 Hz. nuScenes provides 2 seconds of history with HD
maps and requires 6 seconds of future trajectory to be predicted. Models. We
compare our method against state-of-the-art algorithms on each benchmark. Note
that we omit the recent LED [32] from the pedestrian benchmark since we were
unable to validate the results using the official published code and
procedures and no explanations were provided by the authors regarding the
discrepancy. We refer to our model as DICE (Diverse dIffusion with sCoring for
prEdiction).

Metrics We adopt the standard evaluation metrics including the minimum
average/final displacement error over the top $K$ predictions
($\text{minADE}_{K}$/$\text{minFDE}_{K}$) on UCY/ETH benchmark. For nuScenes,
we also report on miss rate ($\text{MR}_{K}$) which is the percentage of
scenarios where the final points of the $k$ predicted trajectories are more
than 2 meters away from the final point of the ground truth trajectory.

Implementation Details We train our denoising module for 80 epochs and the
scoring network for 20 epochs, using AdamW [29] optimizer with a learning rate
of $5\times 10^{-4}$, batch size of 32, and a dropout rate of 0.1. For
training the denoising module, we use $H=200$ diffusion steps. When sampling
using DDIM [46], we skip over every $\gamma=20$ steps, resulting in only 10
denoising steps to generate each independent trajectory. For training the
scoring network, we set the distance metric control weight in
$\mathcal{L}_{scorer}$ to be $\lambda=1.5$. Our denoiser consists of 5
transformer layers. All attention modules have $h=4$ heads with 128 hidden
dimensions. We set the distance threshold to $\omega=8$ (meters) for the non-
maximum suppression operation in inference. All experiments are done on a
Tesla V100 GPU.

###  IV-B Comparison to SOTA on Pedestrian Benchmark

Table I shows the results for $\text{minADE}_{20}$/$\text{minFDE}_{20}$ of
models evaluated on UCY/ETH. We can see that the proposed model achieves SOTA
performance on 4 out of 5 subsets on minFDE metrics and overall best
performance by a significant margin on ETH by improving approx. $50\%$ on both
metrics. On average across all subsets, our model is best on minFDE by
improving up to $20\%$ compared to GroupNet while achieving second best on
minADE with a small margin. Such a performance gain is due to our model
successfully producing a diverse prediction set that captures a wide range of
multi-modal intentions.

###  IV-C Qualitative Results

Figure 2: Visualization of generated trajectories from DDIM sampling at each
diffusion step $\eta^{\prime}$. The plots in the last two columns show the
generated trajectories after scoring and after applying the selection
algorithm respectively. Lighter colours reflect higher scores.

Figure 2 illustrates the reverse process of our model on a subset of scenes
from the UCY/ETH dataset. $\eta^{\prime}=\frac{\eta}{\gamma}$ denotes the
diffusion steps taken by DDIM sampling, where DDPM sampling steps being
$H=200$ and the number of steps skipped being $\gamma=20$, which results in
the total diffusion steps taken by DDIM sampling being $10$. We plot $M=100$
generated trajectories after being scored, and $K=20$ final selected. The last
column in Figure 2 shows that the selected trajectories using the scoring
network are very diverse, but also more dense around the ground truth
trajectory.

###  IV-D Comparison to SOTA on Autonomous Driving Benchmark

TABLE II: Quantitative results on the nuScenes benchmark. Bold numbers
indicate the best performance for each metric, underline indicates the second
best performance for each metric.

Method | $\text{minADE}_{5}$ | $\text{minADE}_{10}$ | $\text{minFDE}_{1}$ | $\text{minFDE}_{5}$ | $\text{minFDE}_{10}$ | $\text{MR}_{5}$ | $\text{MR}_{10}$
---|---|---|---|---|---|---|---
CoverNet [37] | 1.96 | 1.48 | 9.26 | - | - | 0.67 | -
Trajectron++ [44] | 1.88 | 1.51 | 9.52 | - | - | 0.70 | 0.57
AgentFormer [59] | 1.86 | 1.45 | - | 3.89 | 2.86 | - | -
SG-Net [61] | 1.86 | 1.40 | 9.25 | - | - | 0.67 | 0.52
MHA-JAM [33] | 1.81 | 1.24 | 8.57 | 3.72 | 2.21 | 0.59 | 0.46
CXX [30] | 1.63 | 1.29 | - | - | - | 0.69 | 0.60
P2T [8] | 1.45 | 1.16 | 10.45 | - | - | 0.64 | 0.46
GOHOME [14] | 1.42 | 1.15 | 6.99 | - | - | 0.57 | 0.47
PGP [9] | 1.30 | 1.00 | 7.17 | - | - | 0.61 | 0.37
DICE (ours) (w/o scoring) | 2.03 | 1.68 | 8.90 | 3.83 | 2.80 | 0.55 | 0.40
DICE (ours) (w/ scoring) | 1.76 | 1.44 | 7.74 | 3.70 | 2.67 | 0.53 | 0.34

To further highlight the effectiveness of the proposed model, we evaluate our
approach on the nuScenes autonomous driving benchmark. We report the results
for $\text{minADE}_{K}$, $\text{minFDE}_{K}$, $\text{MR}_{K}$, for $K=1,5,10$.
The results are summarized in Table II. Here, we can see that our method is
particularly effective in predicting endpoints (targets) as it achieves an
improvement of up to $9\%$ on miss rate while ranking first and second on
$\text{minFDE}_{5}$ and $\text{minFDE}_{10}$, respectively. Again, this
confirms the ability of our prediction set to capture intention points. This
should be noted that in the autonomous driving domain, more emphasis is often
given to final error, variations of which are used for ranking of prediction
models in more recent benchmarks, such as [4, 49]. In terms of minADE our
model lags behind, which can be due to the tendency of the model to generate
more low curvature trajectories, hence, causing higher average error in
driving scenes as they may contain turns.

###  IV-E Ablation Studies

TABLE III: Ablation study on post-processing of trajectory selection method.
Results are reported using $\text{minADE}_{20}$/$\text{minFDE}_{20}$ on
UCY/ETH.

| Random | Clustering | Scoring+NMS
---|---|---|---
ETH | 0.27/0.42 |  0.24/0.35 |  0.24/0.34
Hotel | 0.20/0.28 | 0.19/0.25 |  0.18/0.23
Univ | 0.46/0.52 |  0.45/0.52 | 0.52/0.61
Zara1 | 0.26/0.42 |  0.24/0.37 |  0.24/0.37
Zara2 | 0.23/0.40 | 0.22/0.36 |  0.20/0.30
AVG | 0.28/0.41 | 0.27/0.37 |  0.26/0.35

Effect of the scoring network. We evaluate the effect of oversampling and then
undersampling trajectories with our scoring model and non-maximum suppression
by comparing against 2 baselines. These encompass randomly generating $K$
trajectories directly from our denoiser, and an intelligent post-processing
selection algorithm implemented in [22] and partially inspired from [51]. Let
$\hat{T}_{1:K}=\\{\hat{\bm{\tau}}_{future}^{j}\\}_{j=1}^{K}$ be the selected
$K$ predicted trajectories, and
$\hat{T}_{1:M}=\\{\hat{\bm{\tau}}_{future}^{j}\\}_{j=1}^{M}$ be the
oversampled set of $M$ trajectories. We attempt to select $\hat{T}_{1:K}$ so
that the maximum number of elements in $\hat{T}_{1:M}$ lie within distance $r$
of any of the $\hat{T}_{1:K}$ elements.

$\hat{T}_{1:K}=\mathop{\mathrm{argmax}}_{\hat{T}_{1:K}}\sum_{j=1}^{M}\;\mathop{\mathrm{max}}_{\hat{T}_{i}\in\hat{T}_{1:K}}\>\mathbb{I}\,(\,dist(\hat{T}_{i},\hat{T}_{j})<r)$

where $dist(.)$ is the distance function for which we use ADE, and $r$ is an
adjustable threshold. We approximate our solution in a greedy fashion,
iteratively adding one trajectory to $\hat{T}_{1:K}$ until we have $K$
trajectories. The trajectory we select at each step is the one that maximizes
the above argmax objective when added to the current set.

As shown in Table III, selecting trajectories using the scoring network with
non-maximum suppression achieves the best results, with on average $7\%/15\%$
improvement on $\text{minADE}_{20}$/$\text{minFDE}_{20}$ compared to the case
where we randomly sample $20$ trajectories directly from the denoiser. It also
performs up to $4\%/5\%$ better than our post-processing selection baseline.
The scoring network, however, negatively affects the performance on the Univ
subset. We hypothesize that the substantially smaller size of the train set
compared to the test set for Univ may have lead to underfitting.

Figure 3: Ablation study on number of denoising Steps and oversampling size
(M). Metrics are $\text{minADE}_{20}$/$\text{minFDE}_{20}$/latency(ms) and
reported on ETH. Colors indicate better (green) and worse (red) values and are
assigned columnwise for each metric and normalized across both tables.

Steps vs sampling We study the effect of the number of steps and samples on
accuracy and latency. The results are illustrated in Figure 3. On the left, as
one would expect, increasing the number of denoising steps improves the
performance, although only minFDE metric. This, however, comes at a
significant cost of increasing the latency by as much as 19 times. On the
other hand, as shown in the table on the right, we can see that much better
improvement can be achieved by simply increasing the number of samples.
Increasing the number of samples by five-fold, only increases latency by
$15\%$ while improving the performance by up to $21\%$. This highlights the
effectiveness of oversampling and the proposed scoring method to improve
accuracy.

##  V Conclusion

We presented a novel model for road user trajectory prediction, leveraging the
capabilities of diffusion models. Our approach benefited from an efficient
sampling approach resulting in significant speed-up. This allows our model to
oversample trajectory distributions to better capture the space of
possibilities. Furthermore, we proposed a scoring network that ranks the
sampled trajectories in order to select the most plausible ones. We conducted
extensive evaluations on the pedestrian and autonomous driving benchmark
datasets and showed that our model achieves state-of-the-art performance on a
number of subsets and metrics, in particular minFDE and MR. In addition, we
conducted ablative studies to highlight the effectiveness of the proposed
scoring scheme and oversampling on boosting the accuracy of predictions.

## References

  * [1] A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, L. Fei-Fei, and S. Savarese, “Social LSTM: Human trajectory prediction in crowded spaces,” in _CVPR_ , 2016.
  * [2] E. Amirloo, A. Rasouli, P. Lakner, M. Rohani, and J. Luo, “LatentFormer: Multi-agent transformer-based interaction modeling and trajectory prediction,” _arXiv:2203.01880_ , 2022.
  * [3] H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong, Q. Xu, A. Krishnan, Y. Pan, G. Baldan, and O. Beijbom, “nuScenes: A multimodal dataset for autonomous driving,” in _CVPR_ , 2020.
  * [4] M.-F. Chang, J. Lambert, P. Sangkloy, J. Singh, S. Bak, A. Hartnett, D. Wang, P. Carr, S. Lucey, D. Ramanan _et al._ , “Argoverse: 3D tracking and forecasting with rich maps,” in _CVPR_ , 2019.
  * [5] G. Chen, J. Li, N. Zhou, L. Ren, and J. Lu, “Personalized trajectory prediction via distribution discrimination,” in _ICCV_ , 2021.
  * [6] C. Choi, S. Malla, A. Patil, and J. H. Choi, “DROGON: A trajectory prediction model based on intention-conditioned behavior reasoning,” in _CoRL_ , 2021.
  * [7] P. Dendorfer, S. Elflein, and L. Leal-Taixé, “MG-GAN: A multi-generator model preventing out-of-distribution samples in pedestrian trajectory prediction,” in _ICCV_ , 2021.
  * [8] N. Deo and M. M. Trivedi, “Trajectory forecasts in unknown environments conditioned on grid-based plans,” _arXiv:2001.00735_ , 2020.
  * [9] N. Deo, E. M. Wolff, and O. Beijbom, “Multimodal trajectory prediction conditioned on lane-graph traversals,” in _CoRL_ , 2022.
  * [10] A. Ess, B. Leibe, and L. Van Gool, “Depth and appearance for mobile scene analysis,” in _ICCV_ , 2007.
  * [11] L. Fang, Q. Jiang, J. Shi, and B. Zhou, “Tpnet: Trajectory proposal network for motion prediction,” in _CVPR_ , 2020.
  * [12] T. Fernando, S. Denman, S. Sridharan, and C. Fookes, “Soft+ hardwired attention: An lstm framework for human trajectory prediction and abnormal event detection,” _Neural Networks_ , vol. 108, pp. 466–478, 2018.
  * [13] J. Gao, C. Sun, H. Zhao, Y. Shen, D. Anguelov, C. Li, and C. Schmid, “VectorNet: Encoding hd maps and agent dynamics from vectorized representation,” in _CVPR_ , 2020.
  * [14] T. Gilles, S. Sabatini, D. Tsishkou, B. Stanciulescu, and F. Moutarde, “GOHOME: Graph-oriented heatmap output for future motion estimation,” in _ICRA_ , 2022.
  * [15] J. Gu, C. Sun, and H. Zhao, “DenseTNT: End-to-end trajectory prediction from dense goal sets,” in _ICCV_ , 2021.
  * [16] T. Gu, G. Chen, J. Li, C. Lin, Y. Rao, J. Zhou, and J. Lu, “Stochastic trajectory prediction via motion indeterminacy diffusion,” in _CVPR_ , 2022\.
  * [17] A. Gupta, J. Johnson, L. Fei-Fei, S. Savarese, and A. Alahi, “Social GAN: Socially acceptable trajectories with generative adversarial networks,” in _CVPR_ , 2018.
  * [18] J. Ho, W. Chan, C. Saharia, J. Whang, R. Gao, A. Gritsenko, D. P. Kingma, B. Poole, M. Norouzi, D. J. Fleet _et al._ , “Imagen video: High definition video generation with diffusion models,” _arXiv:2210.02303_ , 2022\.
  * [19] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” in _NeurIPS_ , 2020.
  * [20] Y. Huang, H. Bi, Z. Li, T. Mao, and Z. Wang, “STGAT: Modeling spatial-temporal interactions for human trajectory prediction,” in _ICCV_ , 2019.
  * [21] B. Ivanovic and M. Pavone, “The Trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs,” in _ICCV_ , 2019\.
  * [22] C. M. Jiang, A. Cornman, C. Park, B. Sapp, Y. Zhou, and D. Anguelov, “MotionDiffuser: Controllable multi-agent motion prediction using diffusion,” in _CVPR_ , 2023.
  * [23] Z. Kong, W. Ping, J. Huang, K. Zhao, and B. Catanzaro, “Diffwave: A versatile diffusion model for audio synthesis,” _arXiv:2009.09761_ , 2020.
  * [24] V. Kosaraju, A. Sadeghian, R. Martín-Martín, I. Reid, S. H. Rezatofighi, and S. Savarese, “Social-BiGAT: Multimodal trajectory forecasting using bicycle-gan and graph attention networks,” in _NeurIPS_ , 2019.
  * [25] N. Lee, W. Choi, P. Vernaza, C. B. Choy, P. H. S. Torr, and M. Chandraker, “DESIRE: Distant future prediction in dynamic scenes with interacting agents,” in _CVPR_ , 2017.
  * [26] A. Lerner, Y. Chrysanthou, and D. Lischinski, “Crowds by example,” _Computer Graphics Forum_ , vol. 26, no. 3, pp. 655–664, 2007.
  * [27] Y. Liu, Z. Ye, B. Li, and L. Yao, “Uncertainty-aware pedestrian trajectory prediction via distributional diffusion,” _ArXiv_ , 2023.
  * [28] Y. Liu, Q. Yan, and A. Alahi, “Social NCE: Contrastive learning of socially-aware motion representations,” in _ICCV_ , 2021.
  * [29] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” _arXiv:1711.05101_ , 2017.
  * [30] C. Luo, L. Sun, D. Dabiri, and A. Yuille, “Probabilistic multi-modal trajectory prediction with lane attention for autonomous vehicles,” in _IROS_ , 2020.
  * [31] S. Luo and W. Hu, “Diffusion probabilistic models for 3d point cloud generation,” in _CVPR_ , 2021.
  * [32] W. Mao, C. Xu, Q. Zhu, S. Chen, and Y. Wang, “Leapfrog diffusion model for stochastic trajectory prediction,” in _CVPR_ , 2023.
  * [33] K. Messaoud, N. Deo, M. M. Trivedi, and F. Nashashibi, “Trajectory prediction for autonomous driving based on multi-head attention with joint agent-map representation,” in _IV_ , 2021.
  * [34] A. Mohamed, K. Qian, M. Elhoseiny, and C. Claudel, “Social-STGCNN: A social spatio-temporal graph convolutional neural network for human trajectory prediction,” in _CVPR_ , 2020.
  * [35] N. Nayakanti, R. Al-Rfou, A. Zhou, K. Goel, K. S. Refaat, and B. Sapp, “Wayformer: Motion forecasting via simple & efficient attention networks,” in _ICRA_ , 2023.
  * [36] S. H. Park, G. Lee, J. Seo, M. Bhat, M. Kang, J. Francis, A. Jadhav, P. P. Liang, and L.-P. Morency, “Diverse and admissible trajectory forecasting through multimodal context understanding,” in _ECCV_ , 2020.
  * [37] T. Phan-Minh, E. C. Grigore, F. A. Boulton, O. Beijbom, and E. M. Wolff, “CoverNet: Multimodal behavior prediction using trajectory sets,” in _CVPR_ , 2020.
  * [38] A. Rasouli and I. Kotseruba, “Pedformer: Pedestrian behavior prediction via cross-modal attention modulation and gated multitask learning,” in _ICRA_ , 2023.
  * [39] A. Rasouli, M. Rohani, and J. Luo, “Bifold and semantic reasoning for pedestrian behavior prediction,” in _ICCV_ , 2021.
  * [40] D. Rempe, Z. Luo, X. B. Peng, Y. Yuan, K. Kitani, K. Kreis, S. Fidler, and O. Litany, “Trace and pace: Controllable pedestrian animation via guided trajectory diffusion,” in _CVPR_ , 2023.
  * [41] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer, “High-resolution image synthesis with latent diffusion models,” in _CVPR_ , 2022.
  * [42] A. Sadeghian, V. Kosaraju, A. Sadeghian, N. Hirose, S. H. Rezatofighi, and S. Savarese, “SoPhie: An attentive gan for predicting paths compliant to social and physical constraints,” in _CVPR_ , 2019.
  * [43] C. Saharia, W. Chan, S. Saxena, L. Li, J. Whang, E. L. Denton, K. Ghasemipour, R. Gontijo Lopes, B. Karagol Ayan, T. Salimans _et al._ , “Photorealistic text-to-image diffusion models with deep language understanding,” in _NeurIPS_ , 2022.
  * [44] T. Salzmann, B. Ivanovic, P. Chakravarty, and M. Pavone, “Trajectron++: Dynamically-feasible trajectory forecasting with heterogeneous data,” in _ECCV_ , 2020.
  * [45] K. Sohn, H. Lee, and X. Yan, “Learning structured output representation using deep conditional generative models,” in _NIPS_ , 2015.
  * [46] J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” _arXiv:2010.02502_ , 2020.
  * [47] H. Sun, Z. Zhao, and Z. He, “Reciprocal learning networks for human trajectory prediction,” in _CVPR_ , 2020.
  * [48] J. Sun, Q. Jiang, and C. Lu, “Recursive social behavior graph for trajectory prediction,” in _CVPR_ , 2020.
  * [49] P. Sun, H. Kretzschmar, X. Dotiwalla, A. Chouard, V. Patnaik, P. Tsui, J. Guo, Y. Zhou, Y. Chai, B. Caine _et al._ , “Scalability in perception for autonomous driving: Waymo open dataset,” in _CVPR_ , 2020.
  * [50] H. Thanh-Tung and T. Tran, “On catastrophic forgetting in generative adversarial networks,” _arXiv:1807.04015_ , 2018.
  * [51] B. Varadarajan, A. Hefny, A. Srivastava, K. S. Refaat, N. Nayakanti, A. Cornman, K. Chen, B. Douillard, C. P. Lam, D. Anguelov, and B. Sapp, “MultiPath++: Efficient information fusion and trajectory aggregation for behavior prediction,” in _ICRA_ , 2022.
  * [52] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NeurIPS_ , 2017.
  * [53] A. Vemula, K. Muelling, and J. Oh, “Social attention: Modeling attention in human crowds,” in _ICRA_ , 2018.
  * [54] C. Xu, M. Li, Z. Ni, Y. Zhang, and S. Chen, “GroupNet: Multiscale hypergraph neural networks for trajectory prediction with relational reasoning,” in _CVPR_ , 2022.
  * [55] C. Xu, W. Mao, W. Zhang, and S. Chen, “Remember intentions: Retrospective-memory-based trajectory prediction,” in _CVPR_ , 2022.
  * [56] R. Yang, P. Srivastava, and S. Mandt, “Diffusion probabilistic modeling for video generation,” _arXiv:2203.09481_ , 2022.
  * [57] M. Ye, T. Cao, and Q. Chen, “TPCN: Temporal point cloud networks for motion forecasting,” in _CVPR_ , 2021.
  * [58] C. Yu, X. Ma, J. Ren, H. Zhao, and S. Yi, “Spatio-temporal graph transformer networks for pedestrian trajectory prediction,” in _ECCV_ , 2020.
  * [59] Y. Yuan, X. Weng, Y. Ou, and K. Kitani, “AgentFormer: Agent-aware transformers for socio-temporal multi-agent forecasting,” in _ICCV_ , 2021\.
  * [60] P. Zhang, W. Ouyang, P. Zhang, J. Xue, and N. Zheng, “SR-LSTM: State refinement for lstm towards pedestrian trajectory prediction,” in _CVPR_ , 2019.
  * [61] Z. Zhang, Y. Wu, J. Zhou, S. Duan, H. Zhao, and R. Wang, “SG-Net: Syntax-guided machine reading comprehension,” in _AAAI_ , 2020.
  * [62] H. Zhao, J. Gao, T. Lan, C. Sun, B. Sapp, B. Varadarajan, Y. Shen, Y. Shen, Y. Chai, C. Schmid, C. Li, and D. Anguelov, “TNT: Target-driven trajectory prediction,” in _CoRL_ , 2021.
  * [63] S. Zhao, J. Song, and S. Ermon, “Towards deeper understanding of variational autoencoding models,” _arXiv:1702.08658_ , 2017.
  * [64] Z. Zhou, L. Ye, J. Wang, K. Wu, and K. Lu, “HiVT: Hierarchical vector transformer for multi-agent motion prediction,” in _CVPR_ , 2022.