Monday, November 19, 2012

Fast Earth Mover's Distance (EMD) implementation

As the subject of Earth Mover's distance is heating up see for instance Learning Manifolds in the Wild and Sparse Recovery for Earth Mover Distance, I came across this FastEMD algorithm implementation. From the page:

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.
Quadratic Chi (QC) - code that computes the new Quadratic Chi histogram distances (proposed at ECCV 2010) very fast.

1 comment:

Eric Tramel said...

I love how the spinning "NEW!" gifs ported over to the blog. Nice touch ;)