Skip to main content
Warning: You are using the test version of PyPI. This is a pre-production deployment of Warehouse. Changes made here affect the production instance of TestPyPI (testpypi.python.org).
Help us improve Python packaging - Donate today!

A Python wrapper for Ofir Pele and Michael Werman's implementation of the Earth Mover's Distance.

Project Description

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

To install the latest release:

pip install pyemd

Before opening an issue related to installation, please try to install PyEMD in a fresh, empty Python 3 virtual environment and check that the problem persists.

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 type np.float64 of length N.
  • second_histogram (np.ndarray): A 1D array of np.float64 of length N.
  • distance_matrix (np.ndarray): A 2D array of np.float64, of size at least N × N. This defines the underlying metric, or ground distance, by giving the pairwise distances between the histogram bins. 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.

emd_with_flow()

emd_with_flow(first_histogram, second_histogram, distance_matrix,
              extra_mass_penalty=-1.0)

Arguments are the same as for emd().


emd_samples()

emd_samples(first_array, second_array,
            extra_mass_penalty=DEFAULT_EXTRA_MASS_PENALTY,
            distance='euclidean',
            normalized=True,
            bins='auto',
            range=None)

Arguments:

  • first_array (Iterable): A 1D array of samples used to generate a histogram.
  • second_array (Iterable): A 1D array of samples used to generate a histogram.

Keyword Arguments:

  • extra_mass_penalty (float): Same as for emd(). 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 by np.histogram(). Defaults to ‘auto’, which gives the maximum of the ‘sturges’ and ‘fd’ estimators.
  • distance_matrix (string or function): A string or function implementing a metric on a 1D np.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, 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.
  • range (tuple(int, int)): The lower and upper range of the bins, passed to numpy.histogram(). Defaults to the range of the union of first_array and second_array`.` Note: if the given range is not a superset of the default range, no warning will be given.

Limitations and Caveats

  • distance_matrix is assumed to represent a metric; there is no check to ensure that this is true. See the documentation in pyemd/lib/emd_hat.hpp for more information.
  • The flow matrix does not contain the flows to/from the extra mass bin.
  • 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 with double (Cython converts np.float64 to double). If there’s demand, I can add support for other types.

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 suite
  • build Generate and compile the Cython extension
  • clean: Remove the compiled Cython extension
  • default: Run build

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, “A linear time histogram metric for improved SIFT matching,” in 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}
}

Ofir Pele and Michael Werman, “Fast and robust earth mover’s distances,” in 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}
}

Release History

History Node

0.5.1rc1

This version
History Node

0.5.0

History Node

0.5.0rc2

History Node

0.5.0rc1

History Node

0.4.4

History Node

0.4.3

History Node

0.4.2

History Node

0.4.2a2

History Node

0.4.2a1

History Node

0.4.0

History Node

0.3.0

History Node

0.2.2

History Node

0.2.1

History Node

0.2.0

Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, Size & Hash SHA256 Hash Help File Type Python Version Upload Date
pyemd-0.5.0-cp36-cp36m-macosx_10_13_x86_64.whl
(81.1 kB) Copy SHA256 Hash SHA256
Wheel cp36 Jan 22, 2018
pyemd-0.5.0.tar.gz
(91.0 kB) Copy SHA256 Hash SHA256
Source None Jan 22, 2018

Supported By

Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Google Google Cloud Servers DreamHost DreamHost Log Hosting