Fast and robust Earth Mover's Distances
Authors:
Top Cited Papers
- 1 September 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 460-467
Abstract
We present a new algorithm for a robust family of Earth Mover's Distances - EMDs with thresholded ground distances. The algorithm transforms the flow-network of the EMD so that the number of edges is reduced by an order of magnitude. As a result, we compute the EMD by an order of magnitude faster than the original algorithm, which makes it possible to compute the EMD on large histograms and databases. In addition, we show that EMDs with thresholded ground distances have many desirable properties. First, they correspond to the way humans perceive distances. Second, they are robust to outlier noise and quantization effects. Third, they are metrics. Finally, experimental results on image retrieval show that thresholding the ground distance of the EMD improves both accuracy and speed.Keywords
This publication has 27 references indexed in Scilit:
- Approximate earth mover’s distance in linear time2008
- The CIEDE2000 color-difference formula: Implementation notes, supplementary test data, and mathematical observationsColor Research & Application, 2004
- Fast contour matching using approximate Earth mover's distance2004
- Edge, junction, and corner detection using color distributionsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- SIMPLIcity: semantics-sensitive integrated matching for picture librariesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Toward a Universal Law of Generalization for Psychological ScienceScience, 1987
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Bipartite graph matching for points on a line or a circleJournal of Algorithms, 1986
- A distance metric for multidimensional histogramsComputer Vision, Graphics, and Image Processing, 1985
- Generalized texture representation and metricComputer Vision, Graphics, and Image Processing, 1983