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.
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:
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.
I extracted the meat from the LEMON library to make the mass transport computation feasible using only 3 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. It is not multithreaded, but thread-safe.
Note that the EMD-Hat code might occasionally be faster if you are concerned with thresholded ground distances that respect triangle inequalities, since this sparsifies the flow network a lot. For a largely thresholded ground distance, I observed between a 3x speedup and 1.5x slow down on 10k nodes when using the version specialized for metrics (i.e., mathematical distances) on different tests. However, the same thresholded problem without the metric assumption runs 5x slower on 10k nodes than with no assumption using the code above. For non-thresholded ground distances, EMD-hat is orders of magnitude slower (typically, same runtime for 1k nodes with an non-thresholded EMD-hat with a metric ground distance assumption, than with 10k nodes with the code above ; 6x slower with 1k node without the metric assumption than with 10k nodes with the network simplex above). [Note: these were not tested on the same problem]
It is also orders of magnitude faster than
McDonald's reimplementation of Rubner's EMD code on 10k nodes [on the same problem] (typically, 10x slower on 3k nodes than with 10k nodes using the code above).