The Earth Mover's Distance: Lower Bounds and Invariance Under Translation
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1997
- Accession Number
- ADA358270
Entities
People
- Leonidas J. Guibas
- Scott Cohen
Organizations
- Stanford University