Skip to content
SPOT: Sliced Partial Optimal Transport
C++ C
Branch: master
Clone or download
Latest commit a4f7698 Sep 24, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data README Aug 21, 2019
CImg.h Initial commit. Apr 25, 2019
FIST.vcxproj project file update + simpler sum8 Aug 21, 2019
LICENSE.txt license Apr 25, 2019
Makefile thread Sep 2, 2019
Makefile.osx thread Sep 2, 2019
Point.h license Apr 25, 2019
README.md Update README.md Sep 24, 2019
UnbalancedSliced.cpp project file update + simpler sum8 Aug 21, 2019
UnbalancedSliced.h thread Sep 2, 2019
colorTransfer.vcxproj project file update + simpler sum8 Aug 21, 2019
mainColorTransfer.cpp project file update + simpler sum8 Aug 21, 2019
mainFIST.cpp color Aug 21, 2019
slice.sln project file update + simpler sum8 Aug 21, 2019
sse_helpers.h license Apr 25, 2019
stb_image.h WIP Aug 21, 2019
stb_image_write.h WIP Aug 21, 2019

README.md

SPOT: Sliced Partial Optimal Transport

Nicolas Bonneel and David Coeurjolly

Univ. Lyon, CNRS

Demonstration code.

See mainFIST.cpp, this example demonstrates the fast iterative sliced transport (fist) of two random pointsets in dimension three. The FIST executable outputs the transformation (translation, rotation and scaling) to apply to the first point set to match (in the sense of the sliced optimal transport) the second one.

mainColorTransfer.cpp is an example of color transfer between an image and a larger one (see data/). The result is given in outtransfer.png.

Build

  • Linux:

      make  
      ./FIST
      ./colorTransfer
    
  • MacOS (require external OpenMP when using Apple Clang, e.g. brew install libomp):

      make -f Makefile.osx
      ./FIST
      ./colorTransfer
    
  • Windows: use the Visual Studio Project.

Citation

@article{bonneel19SPOT,
    author = "Bonneel, Nicolas and Coeurjolly, David",
    title = "Sliced Partial Optimal Transport",
    journal = "{ACM} Transactions on Graphics (Proceedings of SIGGRAPH)",
    year = "2019",
    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.",
    volume = "38",
    number = "4",
    month = "jul"
}

License

  Copyright (c) 2019 CNRS
  Nicolas Bonneel <nicolas.bonneel@liris.cnrs.fr>
  David Coeurjolly <david.coeurjolly@liris.cnrs.fr>

  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIEDi
  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
You can’t perform that action at this time.