Skip to main content

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

Project description

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.

This wrapper does not expose the full functionality of that library; it can only used be with the np.float data type, and with a symmetric distance matrix that represents a true metric. See the documentation for the original Pele and Werman library for the other options it provides.

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.

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

Project details


Download files

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

Source Distribution

pyemd-0.0.7.tar.gz (59.1 kB view details)

Uploaded Source

Built Distribution

pyemd-0.0.7-cp33-cp33m-macosx_10_9_x86_64.whl (59.7 kB view details)

Uploaded CPython 3.3mmacOS 10.9+ x86-64

File details

Details for the file pyemd-0.0.7.tar.gz.

File metadata

  • Download URL: pyemd-0.0.7.tar.gz
  • Upload date:
  • Size: 59.1 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for pyemd-0.0.7.tar.gz
Algorithm Hash digest
SHA256 70360f9729979bf171a0fd9b16318ace4af5f3c0cd523db58bb9892d103a05bc
MD5 d3b16ce03a056373862c9cb2299b3d48
BLAKE2b-256 4fc6d719791829a7a4989d8c41456f4ea835fd9726f169ed779d591b43ff7901

See more details on using hashes here.

File details

Details for the file pyemd-0.0.7-cp33-cp33m-macosx_10_9_x86_64.whl.

File metadata

File hashes

Hashes for pyemd-0.0.7-cp33-cp33m-macosx_10_9_x86_64.whl
Algorithm Hash digest
SHA256 f51e63ecf0280d9867d8a4fe38f98d73948f5a6a303875fe5131b86124fe7baf
MD5 fb27d638664a9dbae8006965264c852c
BLAKE2b-256 bd55b7dcaf8f9444a476aa82f841c38efbef7535f9c86cf48fe3eaf5c7a15950

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page