Python implementation of the paper of Wuchen Li, Ernest K. Ryu, Stanley Osher, Wotao Yin : A Parallel Method for Earth Mover's Distance, also based on the preprint version : A fast algorithm for Earth Mover's Distance based on optimal transport and L1 type Regularization by Wuchen Li, Stanley Osher, Wilfrid Gangbo.
Project done as part of the course Optimal Transport: theory, computations, statistics and ML applications taught by Marco Cuturi (Google Brain).
Authors: Ryan Boustany, Emma Sarfati
The notebook contains a detailed study of the paper and personal intepretations. It also contains some simulations, on the cat images that the authors used for their article.
The notebook might not display correctly because the file is too large. You can use Jupyter nbviewer : https://nbviewer.jupyter.org
The file emd_report.pdf is our paper with our results and problem explanation/interpretation. This paper has no ambition to replace the original one of Li et al.; we simply try to propose our own illustrations of the problem.
Link to paper 1 : https://arxiv.org/abs/1609.07092
Link to paper 2 : https://www.researchgate.net/publication/319075485_A_Parallel_Method_for_Earth_Mover%27s_Distance
Link to the authors' Matlab implementation : https://github.com/liujl11git/multilevelOT/tree/master/util
If you wish to run the notebook, you can either git clone this repo or create a copy of the Colab link of the notebook: https://colab.research.google.com/drive/1Qmc88kF_qatGaHQ8lS6yxXthQYK5LBtx?usp=sharing. Note that if you use Colab, you will need first to download the data in the /content folder, and change the paths in the notebook.