A FAST APPROXIMATION OF THE EARTH-MOVERS DISTANCE BETWEEN MULTIDIMENSIONAL HISTOGRAMS

We present an efficient algorithm for computing a sub-optimal Earth Movers' Distance (EMD) between multidimensional histograms called EMD-g(f), which is not limited to any type of measurement. Some algorithms that find a cross-bin distance between histograms have been proposed in the literature. Nevertheless, most of this research has been applied on 1D-histograms or on nD-histograms but with limited types of measurements. The EMD is a cross-bin distance between nD-histograms with any ground distance. Experimental validation shows that it obtains good retrieval results although the main drawback of this method is its cubic computational cost, O(z(3)), z being the total number of bins. The worst-case complexity of EMD-g(f) is O(z(2)), although the obtained average computational cost in the experiments is near O(m(2)), where m represents the number of bins per dimension, which is clearly lower than the computational cost of the EMD algorithm. Moreover, the experiments using real data show similar retrieval results.