DeepEMD: A Transformer-based Fast Estimation of the Earth Mover's
  Distance
Atul Kumar Sinha Francois Fleuret
The Earth Mover's Distance (EMD) is the measure of choice between point
clouds. However the computational cost to compute it makes it prohibitive as a
training loss, and the standard approach is to use a surrogate such as the
Chamfer distance. We propose an attention-based model to compute an accurate
approximation of the EMD that can be used as a training loss for generative
models. To get the necessary accurate estimation of the gradients we train our
model to explicitly compute the matching between point clouds instead of EMD
itself. We cast this new objective as the estimation of an attention matrix
that approximates the ground truth matching matrix. Experiments show that this
model provides an accurate estimate of the EMD and its gradient with a wall
clock speed-up of more than two orders of magnitude with respect to the exact
Hungarian matching algorithm and one order of magnitude with respect to the
standard approximate Sinkhorn algorithm, allowing in particular to train a
point cloud VAE with the EMD itself. Extensive evaluation show the remarkable
behaviour of this model when operating out-of-distribution, a key requirement
for a distance surrogate. Finally, the model generalizes very well to point
clouds during inference several times larger than during training.