BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-97-1597
       ENTRY:: November 07, 1997
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: The Earth Mover's Distance: Lower Bounds and Invariance under
               Translation
        TYPE:: Technical Report
      AUTHOR:: Cohen, Scott
      AUTHOR:: Guibas, Leonidas
        DATE:: November 1997
       PAGES:: 44
    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.
       NOTES:: [Adminitrivia V1/Prg/19971107]
         END:: STAN//CS-TR-97-1597