Report Number: CS-TR-97-1597
Institution: Stanford University, Department of Computer Science
Title: The Earth Mover's Distance: Lower Bounds and Invariance under Translation
Author: Cohen, Scott
Author: Guibas, Leonidas
Date: November 1997
Abstract: The Earth Mover's Distance (EMD) between two finite distributions of weight is proportional to the minimum amount of work required to transform one distribution into the other. Current content-based retrieval work in the Stanford Vision Laboratory uses the EMD as a common framework for measuring image similarity with respect to color, texture, and shape content. In this report, we present some fast to compute lower bounds on the EMD which may allow a system to avoid exact, more expensive EMD computations during query processing. The effectiveness of the lower bounds is tested in a color-based retrieval system. In addition to the lower bound work, we also show how to compute the EMD under translation. In this problem, the points in one distribution are free to translate, and the goal is to find a translation that minimizes the EMD to the other distribution.
http://i.stanford.edu/pub/cstr/reports/cs/tr/97/1597/CS-TR-97-1597.pdf