Yossi Rubner, Carlo Tomasi and Leonidas Guibas,
A Metric for Distributions with Applications to Image
Databases,
In Proceedings of the International Conference on Computer Vision (ICCV'98),
Bombay, India, January 1998.
Yossi Rubner, Carlo Tomasi and Leonidas Guibas,
A Metric for Distributions with Applications to Image
Databases,
In Proceedings of the International Conference on Computer Vision (ICCV'98),
Bombay, India, January 1998.We introduce a new distance between two distributions that we call the Earth Mover's Distance (EMD), which reflects the minimal amount of work which 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-DimensionalScaling 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.