The Earth Mover's Distance: Lower Bounds and Invariance Under Translation

Published 1 October 1997

Scott Cohen, Leonidas Guibas

Citations38

TL;DR

This report presents some fast to compute lower bounds on the EMD which may allow a system to avoid exact, more expensive EMD computations during query processing.

Abstract

The Earth Mover&apos;s Distance (EMD) between two nite distributions of weight is proportional to the minimum amount ofwork 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 e ectiveness 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 nd a

Keywords

Computer Science

A metric for distributions with applications to image databases

1,743 Citations2002Yossi Rubner, Carlo Tomasi +1 more

This paper uses the Earth Mover's Distance to exhibit the structure of color-distribution and texture spaces by means of Multi-Dimensional Scaling displays, and proposes a novel approach to the problem of navigating through a collection of color images, which leads to a new paradigm for image database search.

Mathematical ProgrammingA note on Fermat's problem

329 Citations1973Harold W. Kuhn

This note calls attention to the work of Weiszfeld in 1937, who may have been the first to propose an iterative algorithm for the General Fermat Problem.

Mathematical ProgrammingOpen questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem

102 Citations1989R. Chandrasekaran, Arie Tamir

It is demonstrated that Kuhn's convergence theorem is not always correct and it is conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points.

Computational GeometryThe upper bound theorem for polytopes: an easy proof of its asymptotic version

93 Citations1995Raimund Seidel

A proof of the asymptotic version of the famous upper bound theorem: A convex d-polytope with n facets (or, dually, with n vertices) has O(n [ d 2 ]) faces, when d is constant.

Mathematical ProgrammingLocal convergence in Fermat's problem

85 Citations1974I. Norman Katz

It is shown that although convergence is global, the rapidity of convergence depends strongly upon whether or not  is a destination, and locally convergence is always linear with upper and lower asymptotic convergence boundsλ andλ′.

Annals of Operations ResearchA note on the Weber location problem

44 Citations1992Zvi Drezner

An accelerated Weiszfeld procedure is investigated which increases the step size and a formula is found that empirically produces the fastest convergence rate, and an estimate for the optimal cost is derived.

Discrete & Computational GeometryA bound on local minima of arrangements that implies the upper bound theorem

27 Citations1993Kenneth L. Clarkson

The Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope inEd withn facets.

View PDF

Lecture notes in computer scienceThe centroid of points with approximate weights

23 Citations1995Marshall Bern, David Eppstein +4 more

It is proved that the locus of the centroid of S is a convex polytope, the projection of a zonotope in ℝd+1, and complexity bounds and algorithms are derived for the construction of these “centroid polytopes”.