A metric for distributions with applications to image databases

TLDR

The Earth Mover’s Distance is a special case of the transportation problem from linear optimization, for which efficient algorithms exist. The paper introduces the Earth Mover’s Distance and applies it to image databases, using it to map color and texture spaces and to propose a new image‑search paradigm. EMD measures the minimal work to transform one distribution into another, allows partial matching, and is visualized via Multi‑Dimensional Scaling to analyze color‑distribution and texture spaces. When distributions have equal mass, EMD is a true metric with computable lower bounds, and the proposed navigation method yields a new paradigm for image‑database search.

Abstract

We introduce a new distance between two distributions that we call the Earth Mover's Distance (EMD), which reflects the minimal amount of work that must be performed to transform one distribution into the other by moving "distribution mass" around. This is a special case of the transportation problem from linear optimization, for which efficient algorithms are available. The EMD also allows for partial matching. When used to compare distributions that have the same overall mass, the EMD is a true metric, and has easy-to-compute lower bounds. In this paper we focus on applications to image databases, especially color and texture. We use the EMD to exhibit the structure of color-distribution and texture spaces by means of Multi-Dimensional Scaling displays. We also propose a novel approach to the problem of navigating through a collection of color images, which leads to a new paradigm for image database search.