Fast Transport

This webpage contains several fast implementations of state-of-the-art mass transportation algorithms [to be continued]. Bug reports to be sent to nbonneel@seas.harvard.edu . These files are free under the New BSD Licence. They may however depend on open source libraries under different licenses (FFTW is GPL v2 or later, CImg.h is CeCILL-C, LEMON is Boost v1.0).
I strived to make these codes easy to compile and test, and to make them efficient (probably at the expense of readability). Please acknowledge the authors of the original papers.

Eulerian (for grids)

• Optimal Transport with Proximal Splitting
  

  I reimplemented the paper of Papadakis et al. in C++ based on their original Matlab solver (to be found on N.Papadakis' website), at least for the classical 2D euclidean mass transportation problem (the obstacle option was not tested, no smoothing, uniform grid -- started the implementation in 3D but... too long ;) ).
  I observed up to 56x speedups in single precision from the initial Matlab code, using SSE and multithreading. This is a proximal splitting solving of Benamou and Brenier's fluid dynamic formulation. The files can be found:
  • In this archive
  • or in separate files mainProximal.cpp (the main meat), sse_helpers.h (a few helpers for SSE), chrono.h (timer), + the FFTW library (for the FFT based Poisson solver), and the CImg library (convenient header, used here only to load images)
  Typical runtime: ~130/208 seconds (single/double precision) on a 256x256 image.
  
  

Lagrangian (for weighted point clouds)

• Network simplex (used in Displacement Interpolation Using Lagrangian Mass Transport )

  I extracted the meat from the LEMON library to make the mass transport computation feasible using only 2 header files that are more efficient than the original ones and that do not require the installation of LEMON. A previous version of this was used in my displacement interpolation paper albeit with the LEMON dependency. The code is now multi-threaded.

  • Now on GitHub
  
  It is orders of magnitude faster than McDonald's reimplementation of Rubner's EMD code. Ours typically take about 8 seconds to solve an OT problem between 10k bins, taking 1.6 GB of RAM.