Journal
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
Volume 22, Issue 8, Pages 1539-1558Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0218001408006880
Keywords
Multidimensional histogram; earth movers' distance; cross-bin distance
Categories
Funding
- CICYT
- CICYT [DPI2007-614452]
- European Community Union [IST-045062]
- [CSD2007-00018]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available