Fast Earth Mover's Distance (EMD) Code
(C++ and Matlab and Java wrappers)


The code efficiently computes the Earth Mover's Distance (EMD) between two histograms or sparse histograms (signatures). The EMD is also known as Mallows, 1st Wasserstein, Monge-Kantorovich, Match and Transporatation distances. The approach was described in the paper:
"Fast and Robust Earth Mover's Distances" [ ].
EMD-HAT (a better definition of EMD for non-normalized histograms) was presented in the paper:
"A Linear Time Histogram Metric for Improved SIFT Matching" [ ].
One of the demos (demo_FastEMD4) includes a C++ implementation of the CIEDE2000 color distance. The CIEDE2000 C++ code is an adaption of Prof. Gaurav Sharma's Matlab code (used with permission). Other demos include comparison of David Lowe's SIFT descriptors, simple 1d histogram comparison and grayscale image comparison.
NEW ! Quadratic Chi (QC) - code that computes the new Quadratic Chi histogram distances (proposed at ECCV 2010) very fast. NEW !


To get an email when a new version of FastEMD is published, subscribe to FastEMD Google group.
Note: I'm working on faster algorithms and better interface.
Email:


To get started download the zip file and read the README.txt file, or simply start looking at the demo_FastEMD#.m files.

  FastEMD-3.zip     17.5.2012 (added non-symmetric ground distance and non-equal sized histograms versions)
  FastEMD-2.2.zip     15.3.2012 (windows compiled java library added)
  FastEMD-2.1.zip     9.2.2011 (license changed to BSD)
  FastEMD-2.zip     31.1.2010
  FastEMD-1.1.zip   29.7.2009
  FastEMD-1.zip     26.7.2009

  Pure Java port by Telmo Menezes

ICCV 2009 poster: