Installation

To install the latest release:

pip install pyemd

To install the latest development version:

pip install “git+https://github.com/wmayner/pyemd@develop#egg=pyemd”

Usage

Use PyEMD like so:

>>> from pyemd import emd
>>> import numpy as np
>>> first_signature = np.array([0.0, 1.0])
>>> second_signature = np.array([5.0, 3.0])
>>> distance_matrix = np.array([[0.0, 0.5], [0.5, 0.0]])
>>> emd(first_signature, second_signature, distance_matrix)
3.5

API

emd(first_signature, second_signature, distance_matrix)

• first_signature: A 1-dimensional numpy array of np.float, of size N.

• second_signature: A 1-dimensional numpy array of np.float, of size N.

• distance_matrix: A 2-dimensional array of np.float, of size NxN. Must be symmetric and represent a metric.

Limitations and Caveats

• distance_matrix must be symmetric.

• distance_matrix is assumed to represent a true metric. This must be enforced by the caller. See the documentation in pyemd/lib/emd_hat.hpp.

• The signatures and distance matrix must be numpy arrays of np.float. The original C++ template function can accept any numerical C++ type, but this wrapper only instantiates the template with double (Cython converts np.float to double). If there’s demand, I can add support for other types.

• The original C++ functions have optional parameters extra_mass_penalty and F (for flows); this wrapper does not expose those parameters. See the documentation in pyemd/lib/emd_hat.hpp.

Contributing

To help develop PyEMD, fork the project on GitHub and install the requirements with pip.

The Makefile defines some tasks to help with development:

• buildcython: compiles the Cython code into C++ and then builds the C++ into a Python extension

• runtests: builds everything and then runs the unit tests

• clean: removes the compiled C++

Credit

• All credit for the actual algorithm and implementation goes to Ofir Pele and Michael Werman. See the relevant paper.

• Thanks to the Cython devlopers for making this kind of wrapper relatively easy to write.

@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}
}

@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}
}