ACM Transactions on Graphics (Proceedings of SIGGRAPH 2019)
 
SPOT: Sliced Partial Optimal Transport

Nicolas Bonneel David Coeurjolly
Univ. Lyon - CNRS

Our technique allows to partially match point sets within an optimal transport framework. Left. In color matching applications such as that of PitiƩ et al. 2005, matching all pixels of an input image (a) seen as 3D points in an RGB space to all pixels of a target image (b) can lead to erroneous transfers (c) due to mismatched content (here, trees of the target are not present in the input, and distort colors in the output). Instead, we match the input image (a) to a subset of an enlarged target image (b), thus effectively preventing spurious colors (d). Right. Given a source 2-d or 3-d point cloud (in red) and a target one (in blue) of different sizes (e), we match them with a similarity transform. While classical iterative closest point (ICP) fails (f), our approach, called \emph{fast iterative sliced transport}, achieves robust registrations (g).


Abstract
Optimal transport research has surged in the last decade with wide applications in computer graphics. In most cases, however, it has focused on the special case of the so-called ``balanced'' optimal transport problem, that is, the problem of optimally matching positive measures of equal total mass. While this approach is suitable for handling probability distributions as their total mass is always equal to one, it precludes other applications manipulating disparate measures. Our paper proposes a fast approach to the optimal transport of constant distributions supported on point sets of different cardinality via one-dimensional slices. This leads to one-dimensional partial assignment problems akin to alignment problems encountered in genomics or text comparison. Contrary to one-dimensional balanced optimal transport that leads to a trivial linear-time algorithm, such partial optimal transport, even in 1-d, has not seen any closed-form solution nor very efficient algorithms to date. We provide the first efficient 1-d partial optimal transport solver. Along with a quasilinear time problem decomposition algorithm, it solves 1-d assignment problems consisting of up to millions of Dirac distributions within fractions of a second in parallel. We handle higher dimensional problems via a slicing approach, and further extend the popular iterative closest point algorithm using optimal transport -- an algorithm we call Fast Iterative Sliced Transport. We illustrate our method on computer graphics applications such a color transfer and point cloud registration.

 
@article{BC19,
author = {Nicolas Bonneel and David Coeurjolly},
title = {SPOT: Sliced Partial Optimal Transport},
journal = {ACM Transactions on Graphics (SIGGRAPH)},
volume = {38},
number = {4},
year = {2019},
}

Paper
PDF (27 MB)
  Paper (low res.)
PDF (2 MB)
  Presentation
PPTX (155 MB)
PDF (3.6 MB)
  Supplemental Material (proofs)
PDF (245 KB)
  Code
GIT


 
  Supplemental Video
YouTube


 
  Fast Forward !
YouTube


Acknowledgements
We thank the anonymous reviewers for their detailed feedback to improve the paper. This project was supported in part by French ANR ROOT (ANR-16-CE23-0009) and CoMeDiC (ANR-15-CE40-0006) grants.
Image credits to Flickr users Phil Whitehouse, Kirt Edblom, Steve Parker, Tim Wang, Dominic Alves, Eneko Castresana Vara, Felix Schaumburg, Neil Williamson, Ventsislava Bonina, Diego Cambiaso and freestocks.org.
Copyright by the authors, 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Graphics: http://dx.doi.org/10.1145/3306346.3323021