A FAST APPROXIMATION OF THE EARTH-MOVERS DISTANCE BETWEEN MULTIDIMENSIONAL HISTOGRAMS
Francesc Serratosa, Gerard Sanromà · International Journal of Pattern Recognition and Artificial Intelligence · 2008
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(z3), z being the total number of bins. The worst-case complexity of EMD- g f is O(z2), although the obtained average computational cost in the experiments is near O(m2), 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.