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.
ICCV 2009 poster:
