Hi everyone.
The earth movers distance (EMD) is a cross-bin distance that is used to compare histograms in some pattern recognition applications and may be useful for some folks here too. Figuratively speaking, the EMD calculates the minimum amount of ``work’’ needed to transform one histogram into another by moving the bin contents of the first histogram to match the bin contents of the second one.
Shirdhonkar and Jacobs [1] proposed a linear-time approximation of the EMD. Based on their work the attached files provide a corresponding implementation that should be easily usable within root. The data can be multi-dimensional, but each dimension must have a length that is a power of two (see EMD.h and EMD.cpp).
[1] Shirdhonkar, S. & Jacobs, D. Approximate earth mover’s distance in linear time Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008, 1-8
Cheers,
Jochen
Wavelet.cpp (35.1 KB)
Wavelet.h (3.24 KB)
EMD.cpp (4.32 KB)
EMD.h (828 Bytes)