| Name | pyemd JSON |
| Version |
0.5.1
JSON |
| download |
| home_page | http://github.com/wmayner/pyemd |
| Summary | A Python wrapper for Ofir Pele and Michael Werman's implementation of the Earth Mover's Distance. |
| upload_time | 2018-01-29 04:13:45 |
| maintainer | |
| docs_url | None |
| author | Will Mayner |
| requires_python | |
| license | MIT |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
None
|
| Travis-CI |
|
| coveralls test coverage |
No coveralls.
|
.. image:: https://img.shields.io/travis/wmayner/pyemd/develop.svg?style=flat-square&maxAge=3600
:target: https://travis-ci.org/wmayner/pyemd
.. image:: https://img.shields.io/pypi/pyversions/pyemd.svg?style=flat-square&maxAge=86400
:target: https://wiki.python.org/moin/Python2orPython3
:alt: Python versions badge
PyEMD: Fast EMD for Python
==========================
PyEMD is a Python wrapper for `Ofir Pele and Michael Werman's implementation
<http://ofirpele.droppages.com/>`_ of the `Earth Mover's
Distance <http://en.wikipedia.org/wiki/Earth_mover%27s_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
------------
.. code:: bash
pip install pyemd
Usage
-----
.. code:: python
>>> 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:
.. code:: python
>>> 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:
.. code:: python
>>> 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()
~~~~~
.. code:: python
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.
*Returns:* *(float)* The EMD value.
----
emd_with_flow()
~~~~~~~~~~~~~~~
.. code:: python
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()
~~~~~~~~~~~~~
.. code:: python
emd_samples(first_array,
second_array,
extra_mass_penalty=-1.0,
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()``.
- ``distance`` *(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 (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
by ``np.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
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.
*Returns:* *(float)* The EMD value between the histograms of ``first_array`` and
``second_array``.
----
Limitations and Caveats
-----------------------
- ``emd()`` and ``emd_with_flow()``:
- The ``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 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.
- ``emd_with_flow()``:
- The flow matrix does not contain the flows to/from the extra mass bin.
- ``emd_samples()``:
- Using the default ``bins='auto'`` results in an extra call to
``np.histogram()`` to determine the bin lengths, since `the NumPy
bin-selectors are not exposed in the public API
<https://github.com/numpy/numpy/issues/10183>`_. For performance, you may
want to set the bins yourself.
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
<http://www.ariel.ac.il/sites/ofirpele/>`_ and `Michael Werman
<http://www.cs.huji.ac.il/~werman/>`_. See the `relevant paper
<http://www.seas.upenn.edu/~ofirpele/publications/ICCV2009.pdf>`_.
- 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. *Computer Vision - ECCV 2008*, Marseille, France, 2008, pp. 495-508.
.. code-block:: latex
@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. *Proc.
2009 IEEE 12th Int. Conf. on Computer Vision*, Kyoto, Japan, 2009, pp. 460-467.
.. code-block:: latex
@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}
}
Raw data
{
"_id": null,
"home_page": "http://github.com/wmayner/pyemd",
"name": "pyemd",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "",
"author": "Will Mayner",
"author_email": "wmayner@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/c0/c5/7fea8e7a71cd026b30ed3c40e4c5ea13a173e28f8855da17e25271e8f545/pyemd-0.5.1.tar.gz",
"platform": "",
"description": ".. image:: https://img.shields.io/travis/wmayner/pyemd/develop.svg?style=flat-square&maxAge=3600\n :target: https://travis-ci.org/wmayner/pyemd\n.. image:: https://img.shields.io/pypi/pyversions/pyemd.svg?style=flat-square&maxAge=86400\n :target: https://wiki.python.org/moin/Python2orPython3\n :alt: Python versions badge\n\nPyEMD: Fast EMD for Python\n==========================\n\nPyEMD is a Python wrapper for `Ofir Pele and Michael Werman's implementation\n<http://ofirpele.droppages.com/>`_ of the `Earth Mover's\nDistance <http://en.wikipedia.org/wiki/Earth_mover%27s_distance>`_ that allows\nit to be used with NumPy. **If you use this code, please cite the papers listed\nat the end of this document.**\n\n\nInstallation\n------------\n\n.. code:: bash\n\n pip install pyemd\n\n\nUsage\n-----\n\n.. code:: python\n\n >>> from pyemd import emd\n >>> import numpy as np\n >>> first_histogram = np.array([0.0, 1.0])\n >>> second_histogram = np.array([5.0, 3.0])\n >>> distance_matrix = np.array([[0.0, 0.5],\n ... [0.5, 0.0]])\n >>> emd(first_histogram, second_histogram, distance_matrix)\n 3.5\n\nYou can also get the associated minimum-cost flow:\n\n.. code:: python\n\n >>> from pyemd import emd_with_flow\n >>> emd_with_flow(first_histogram, second_histogram, distance_matrix)\n (3.5, [[0.0, 0.0], [0.0, 1.0]])\n\nYou can also calculate the EMD directly from two arrays of observations:\n\n.. code:: python\n\n >>> from pyemd import emd_samples\n >>> first_array = [1, 2, 3, 4]\n >>> second_array = [2, 3, 4, 5]\n >>> emd_samples(first_array, second_array, bins=2)\n 0.5\n\nDocumentation\n-------------\n\nemd()\n~~~~~\n\n.. code:: python\n\n emd(first_histogram,\n second_histogram,\n distance_matrix,\n extra_mass_penalty=-1.0)\n\n*Arguments:*\n\n- ``first_histogram`` *(np.ndarray)*: A 1D array of type ``np.float64`` of\n length *N*.\n- ``second_histogram`` *(np.ndarray)*: A 1D array of ``np.float64`` of length\n *N*.\n- ``distance_matrix`` *(np.ndarray)*: A 2D array of ``np.float64,`` of size at\n least *N* \u00d7 *N*. This defines the underlying metric, or ground distance, by\n giving the pairwise distances between the histogram bins. It must represent a\n metric; there is no warning if it doesn't.\n\n*Keyword Arguments:*\n\n- ``extra_mass_penalty`` *(float)*: The penalty for extra mass. If you want the\n resulting distance to be a metric, it should be at least half the diameter of\n the space (maximum possible distance between any two points). If you want\n partial matching you can set it to zero (but then the resulting distance is\n not guaranteed to be a metric). The default value is ``-1.0``, which means the\n maximum value in the distance matrix is used.\n\n*Returns:* *(float)* The EMD value.\n\n----\n\nemd_with_flow()\n~~~~~~~~~~~~~~~\n\n.. code:: python\n\n emd_with_flow(first_histogram,\n second_histogram,\n distance_matrix,\n extra_mass_penalty=-1.0)\n\nArguments are the same as for ``emd()``.\n\n*Returns:* *(tuple(float, list(list(float))))* The EMD value and the associated\nminimum-cost flow.\n\n----\n\nemd_samples()\n~~~~~~~~~~~~~\n\n.. code:: python\n\n emd_samples(first_array,\n second_array,\n extra_mass_penalty=-1.0,\n distance='euclidean',\n normalized=True,\n bins='auto',\n range=None)\n\n*Arguments:*\n\n- ``first_array`` *(Iterable)*: A 1D array of samples used to generate a\n histogram.\n- ``second_array`` *(Iterable)*: A 1D array of samples used to generate a\n histogram.\n\n*Keyword Arguments:*\n\n- ``extra_mass_penalty`` *(float)*: Same as for ``emd()``.\n- ``distance`` *(string or function)*: A string or function implementing\n a metric on a 1D ``np.ndarray``. Defaults to the Euclidean distance. Currently\n limited to 'euclidean' or your own function, which must take a 1D array and\n return a square 2D array of pairwise distances.\n- ``normalized`` (*boolean*): If true (default), treat histograms as fractions\n of the dataset. If false, treat histograms as counts. In the latter case the\n EMD will vary greatly by array length.\n- ``bins`` *(int or string)*: The number of bins to include in the generated\n histogram. If a string, must be one of the bin selection algorithms accepted\n by ``np.histogram()``. Defaults to ``'auto'``, which gives the maximum of the\n 'sturges' and 'fd' estimators.\n- ``range`` *(tuple(int, int))*: The lower and upper range of the bins, passed\n to ``numpy.histogram()``. Defaults to the range of the union of\n ``first_array`` and ``second_array``. Note: if the given range is not a\n superset of the default range, no warning will be given.\n\n*Returns:* *(float)* The EMD value between the histograms of ``first_array`` and\n``second_array``.\n\n----\n\nLimitations and Caveats\n-----------------------\n\n- ``emd()`` and ``emd_with_flow()``:\n\n - The ``distance_matrix`` is assumed to represent a metric; there is no check\n to ensure that this is true. See the documentation in\n ``pyemd/lib/emd_hat.hpp`` for more information.\n - The histograms and distance matrix must be numpy arrays of type\n ``np.float64``. The original C++ template function can accept any numerical\n C++ type, but this wrapper only instantiates the template with ``double``\n (Cython converts ``np.float64`` to ``double``). If there's demand, I can add\n support for other types.\n\n- ``emd_with_flow()``:\n\n - The flow matrix does not contain the flows to/from the extra mass bin.\n\n- ``emd_samples()``:\n\n - Using the default ``bins='auto'`` results in an extra call to\n ``np.histogram()`` to determine the bin lengths, since `the NumPy\n bin-selectors are not exposed in the public API\n <https://github.com/numpy/numpy/issues/10183>`_. For performance, you may\n want to set the bins yourself.\n\n\nContributing\n------------\n\nTo help develop PyEMD, fork the project on GitHub and install the requirements\nwith ``pip install -r requirements.txt``.\n\nThe ``Makefile`` defines some tasks to help with development:\n\n- ``test``: Run the test suite\n- ``build`` Generate and compile the Cython extension\n- ``clean``: Remove the compiled Cython extension\n- ``default``: Run ``build``\n\nTests for different Python environments can be run with ``tox``.\n\n\nCredit\n------\n\n- All credit for the actual algorithm and implementation goes to `Ofir Pele\n <http://www.ariel.ac.il/sites/ofirpele/>`_ and `Michael Werman\n <http://www.cs.huji.ac.il/~werman/>`_. See the `relevant paper\n <http://www.seas.upenn.edu/~ofirpele/publications/ICCV2009.pdf>`_.\n- Thanks to the Cython developers for making this kind of wrapper relatively\n easy to write.\n\nPlease cite these papers if you use this code:\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nOfir Pele and Michael Werman. A linear time histogram metric for improved SIFT\nmatching. *Computer Vision - ECCV 2008*, Marseille, France, 2008, pp. 495-508.\n\n.. code-block:: latex\n\n @INPROCEEDINGS{pele2008,\n title={A linear time histogram metric for improved sift matching},\n author={Pele, Ofir and Werman, Michael},\n booktitle={Computer Vision--ECCV 2008},\n pages={495--508},\n year={2008},\n month={October},\n publisher={Springer}\n }\n\nOfir Pele and Michael Werman. Fast and robust earth mover's distances. *Proc.\n2009 IEEE 12th Int. Conf. on Computer Vision*, Kyoto, Japan, 2009, pp. 460-467.\n\n.. code-block:: latex\n\n @INPROCEEDINGS{pele2009,\n title={Fast and robust earth mover's distances},\n author={Pele, Ofir and Werman, Michael},\n booktitle={2009 IEEE 12th International Conference on Computer Vision},\n pages={460--467},\n year={2009},\n month={September},\n organization={IEEE}\n }\n\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "A Python wrapper for Ofir Pele and Michael Werman's implementation of the Earth Mover's Distance.",
"version": "0.5.1",
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"md5": "6c04da115770c80861722e83dc8b275c",
"sha256": "15750113757ace54a03d2efef7bbc2c5a4782cba30555e7fd401bcafcfa0ecb2"
},
"downloads": -1,
"filename": "pyemd-0.5.1-cp36-cp36m-macosx_10_13_x86_64.whl",
"has_sig": true,
"md5_digest": "6c04da115770c80861722e83dc8b275c",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": null,
"size": 81337,
"upload_time": "2018-01-29T04:13:43",
"upload_time_iso_8601": "2018-01-29T04:13:43.184150Z",
"url": "https://files.pythonhosted.org/packages/b8/b1/713de7261a0062ce41c4e2caaa16fe033890fd961b70d637c20951a1c7cf/pyemd-0.5.1-cp36-cp36m-macosx_10_13_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "7338811006fe8726ce71b11bd3dae7e6",
"sha256": "fc81c2116f8573e559dfbb8d73e03d9f73c22d0770559f406516984302e07e70"
},
"downloads": -1,
"filename": "pyemd-0.5.1.tar.gz",
"has_sig": true,
"md5_digest": "7338811006fe8726ce71b11bd3dae7e6",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 91498,
"upload_time": "2018-01-29T04:13:45",
"upload_time_iso_8601": "2018-01-29T04:13:45.996825Z",
"url": "https://files.pythonhosted.org/packages/c0/c5/7fea8e7a71cd026b30ed3c40e4c5ea13a173e28f8855da17e25271e8f545/pyemd-0.5.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2018-01-29 04:13:45",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "wmayner",
"github_project": "pyemd",
"travis_ci": true,
"coveralls": false,
"github_actions": false,
"requirements": [
{
"name": null,
"specs": []
}
],
"test_requirements": [
{
"name": "pytest",
"specs": []
},
{
"name": "tox",
"specs": []
}
],
"tox": true,
"lcname": "pyemd"
}
