PyEMD: Fast EMD for Python
PyEMD is a Python wrapper for Ofir Pele and Michael Werman's implementation of the Earth Mover's Distance that allows it to be used with NumPy. If you use this code, please cite the papers listed at the end of this document.
Installation
pip install pyemd
Usage
>>> from pyemd import emd
>>> import numpy as np
>>> first_histogram = np.array([0.0, 1.0])
>>> second_histogram = np.array([5.0, 3.0])
>>> distance_matrix = np.array([[0.0, 0.5],
... [0.5, 0.0]])
>>> emd(first_histogram, second_histogram, distance_matrix)
3.5
You can also get the associated minimum-cost flow:
>>> from pyemd import emd_with_flow
>>> emd_with_flow(first_histogram, second_histogram, distance_matrix)
(3.5, [[0.0, 0.0], [0.0, 1.0]])
You can also calculate the EMD directly from two arrays of observations:
>>> from pyemd import emd_samples
>>> first_array = [1, 2, 3, 4]
>>> second_array = [2, 3, 4, 5]
>>> emd_samples(first_array, second_array, bins=2)
0.5
Documentation
emd()
emd(first_histogram,
second_histogram,
distance_matrix,
extra_mass_penalty=-1.0)
Arguments:
first_histogram(np.ndarray): A 1D array of typenp.float64of length N.second_histogram(np.ndarray): A 1D array ofnp.float64of length N.distance_matrix(np.ndarray): A 2D array ofnp.float64,of size at least N × N. This defines the underlying metric, or ground distance, by giving the pairwise distances between the histogram bins. NOTE: It must represent a metric; there is no warning if it doesn't.
Keyword Arguments:
extra_mass_penalty(float): The penalty for extra mass. If you want the resulting distance to be a metric, it should be at least half the diameter of the space (maximum possible distance between any two points). If you want partial matching you can set it to zero (but then the resulting distance is not guaranteed to be a metric). The default value is-1.0, which means the maximum value in the distance matrix is used.
Returns: (float) The EMD value.
emd_with_flow()
emd_with_flow(first_histogram,
second_histogram,
distance_matrix,
extra_mass_penalty=-1.0)
Arguments are the same as for emd().
Returns: (tuple(float, list(list(float)))) The EMD value and the associated minimum-cost flow.
emd_samples()
emd_samples(first_array,
second_array,
extra_mass_penalty=-1.0,
distance='euclidean',
normalized=True,
bins='auto',
range=None)
Arguments:
first_array(Iterable): An array of samples used to generate a histogram.second_array(Iterable): An array of samples used to generate a histogram.
Keyword Arguments:
extra_mass_penalty(float): Same as foremd().distance(string or function): A string or function implementing a metric on a 1Dnp.ndarray. Defaults to the Euclidean distance. Currently limited to 'euclidean' or your own function, which must take a 1D array and return a square 2D array of pairwise distances.normalized(boolean): If true (default), treat histograms as fractions of the dataset. If false, treat histograms as counts. In the latter case the EMD will vary greatly by array length.bins(int or string): The number of bins to include in the generated histogram. If a string, must be one of the bin selection algorithms accepted bynp.histogram(). Defaults to'auto', which gives the maximum of the 'sturges' and 'fd' estimators.range(tuple(int, int)): The lower and upper range of the bins, passed tonumpy.histogram(). Defaults to the range of the union offirst_arrayandsecond_array. Note: if the given range is not a superset of the default range, no warning will be given.
Returns: (float) The EMD value between the histograms of first_array and second_array.
Limitations and Caveats
emd()andemd_with_flow():- The
distance_matrixis assumed to represent a metric; there is no check to ensure that this is true. See the documentation inpyemd/lib/emd_hat.hppfor more information. - The histograms and distance matrix must be numpy arrays of type
np.float64. The original C++ template function can accept any numerical C++ type, but this wrapper only instantiates the template withdouble(Cython convertsnp.float64todouble). If there's demand, I can add support for other types.
- The
emd_with_flow():- The flow matrix does not contain the flows to/from the extra mass bin.
emd_samples():- With
numpy < 1.15.0, using the defaultbins='auto'results in an extra call tonp.histogram()to determine the bin lengths, since the NumPy bin-selectors are not exposed in the public API. For performance, you may want to set the bins yourself. Ifnumpy >= 1.15is available,np.histogram_bin_edges()is called instead, which is more efficient.
- With
Contributing
To help develop PyEMD, fork the project on GitHub and install the requirements with pip install -r requirements.txt.
The Makefile defines some tasks to help with development:
test: Run the test suitebuildGenerate and compile the Cython extensionclean: Remove the compiled Cython extensiondefault: Runbuild
Tests for different Python environments can be run with tox.
Credit
- All credit for the actual algorithm and implementation goes to Ofir Pele and Michael Werman. See the relevant paper.
- Thanks to the Cython developers for making this kind of wrapper relatively easy to write.
Please cite these papers if you use this code:
Ofir Pele and Michael Werman. Fast and robust earth mover's distances. Proc. 2009 IEEE 12th Int. Conf. on Computer Vision, Kyoto, Japan, 2009, pp. 460-467.
@INPROCEEDINGS{pele2009,
title={Fast and robust earth mover's distances},
author={Pele, Ofir and Werman, Michael},
booktitle={2009 IEEE 12th International Conference on Computer Vision},
pages={460--467},
year={2009},
month={September},
organization={IEEE}
}
Ofir Pele and Michael Werman. A linear time histogram metric for improved SIFT matching. Computer Vision - ECCV 2008, Marseille, France, 2008, pp. 495-508.
@INPROCEEDINGS{pele2008,
title={A linear time histogram metric for improved sift matching},
author={Pele, Ofir and Werman, Michael},
booktitle={Computer Vision--ECCV 2008},
pages={495--508},
year={2008},
month={October},
publisher={Springer}
}
9 Nov 8, 2022
2 Jan 30, 2022
100 Jan 1, 2023
36 Nov 4, 2022
56 Dec 23, 2022
677 Dec 25, 2022
205 Jan 5, 2023
25 Jul 20, 2022
10 Mar 22, 2022
30 Dec 6, 2022
37 Dec 6, 2022
39 Dec 10, 2022
69 Dec 10, 2022
3 Jun 9, 2021
34 Nov 26, 2022
17 Dec 17, 2022
71 Dec 30, 2022
4 Aug 24, 2022
1.3k Dec 28, 2022