# The Earth Mover's Distance, Multi-Dimensional Scaling, and Color-Based Image Retrieval

@inproceedings{Tomasi1997TheEM, title={The Earth Mover's Distance, Multi-Dimensional Scaling, and Color-Based Image Retrieval}, author={Carlo Tomasi}, year={1997} }

In this paper we present a novel approach to the problem of navigating through a database of color images. We consider the images as points in a metric space in which we wish to move around so as to locate image neighborhoods of interest, based on color information. The data base images are mapped to distributions in color space, these distributions are appropriately compressed, and then the distances between all pairs I; J of images are computed based on the work needed to rearrange the mass… Expand

#### 253 Citations

A metric for distributions with applications to image databases

- Mathematics, Computer Science
- Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271)
- 1998

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. Expand

Finding color and shape patterns in images

- Mathematics
- 1999

This thesis is devoted to the Earth Mover's Distance and its use within content-based image retrieval (CBIR). The major CBIR problem discussed is the pattern problem: Given an image and a query… Expand

Perceptual metrics for image database navigation

- Mathematics
- 1999

The increasing amount of information available in today''s world raises the need to retrieve relevant data efficiently. Unlike text-based retrieval, where keywords are successfully used to index into… Expand

Lower Bounds for Embedding the Earth Mover Distance Metric into Normed Spaces

- Mathematics
- 2005

This thesis presents a lower ounds for embedding the Earth Mover Distance (EMID) metric into norrned spaces. The EMID is a metric over two distributions where one is a mass of earth spread out in… Expand

Color-spatial image indexing and applications

- Computer Science
- 1998

The color correlogram is proposed as a generic color-spatial indexing tool to tackle various problems that arise in content-based image retrieval and video browsing and a method for hierarchical classification of images via supervised learning is proposed. Expand

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

- Mathematics
- 1997

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… Expand

Multilinearization data structure for image browsing

- Computer Science, Engineering
- Electronic Imaging
- 1998

A novel image navigator and browser is presented, built on dual-linearization data structure and intuitive presentation of image relevance and relationships, for efficient organization of the data set and fast visual browsing of the images. Expand

The Earth Mover's Distance under transformation sets

- Mathematics, Computer Science
- Proceedings of the Seventh IEEE International Conference on Computer Vision
- 1999

This work considers the problem of computing a transformation of one distribution which minimizes its EMD to another, and presents a monotonically convergent iteration which can be applied to a large class of EMD under transformation problems, although the iteration may converge to only a locally optimal transformation. Expand

Image database clustering with SVM-based class personalization

- Computer Science, Engineering
- IS&T/SPIE Electronic Imaging
- 2003

This paper presents a robust approach to organize image databases: the Adaptive Robust Competition (ARC), which relies on a non-supervised database categorization, coupled with a selection of prototypes in each resulting category. Expand

The PvS-Index: An Indexing Method for Local Image Descriptors

- Computer Science
- 2005

The PvS-Index is presented, a new approximate indexing technique for high dimensional data that provides a good evaluation time independent from the actual size of the collection and shows a performance gain of several orders of magnitude in comparison with a sequential scan through the whole data set. Expand

#### References

SHOWING 1-10 OF 11 REFERENCES

Similarity of color images

- Mathematics, Engineering
- Electronic Imaging
- 1995

Two new color indexing techniques are described, one of which is a more robust version of the commonly used color histogram indexing and the other which is an example of a new approach tocolor indexing that contains only their dominant features. Expand

A distance metric for multidimensional histograms

- Mathematics, Computer Science
- Comput. Vis. Graph. Image Process.
- 1985

The problem of finding a translation to minimize the distance between point patterns is discussed and the sum of the distances in the minimal pairing is used as the “match distance” between the histograms. Expand

Virage image search engine: an open framework for image management

- Computer Science, Engineering
- Electronic Imaging
- 1996

The Virage engine provides an open framework for developers to 'plug-in' primitives to solve specific image management problems and can be utilized to address high-level problems as well, such as automatic, unsupervised keyword assignment, or image classification. Expand

Image Retrieval and Robot Vision Research at Stanford

- Computer Science
- 1996

This work has developed a robot observer that uses motion planning and visibility graphs to stalk a moving target in an environment cluttered with obstacles and built a depth-from-focus vision system that allows a Nomadic robot to navigate for hours in a crowded environment. Expand

Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis

- Mathematics
- 1964

Multidimensional scaling is the problem of representingn objects geometrically byn points, so that the interpoint distances correspond in some sense to experimental dissimilarities between objects.… Expand

Multidimensional binary search trees used for associative searching

- Mathematics, Computer Science
- CACM
- 1975

The multidimensional binary search tree (or <italic>k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements. Expand

Color Science, Concepts and Methods. Quantitative Data and Formulas

- Engineering
- 1967

G. Wyszecki and W. S. Stiles London: John Wiley. 1967. Pp. xiv + 628. Price £11. This remarkable and unusual book is by two outstanding authorities on the science of colour: Dr. Stiles, for many… Expand

Efficient Color Histogram Indexing for Quadratic Form Distance Functions

- Mathematics, Computer Science
- IEEE Trans. Pattern Anal. Mach. Intell.
- 1995

An improved shipping container having novel locking features in the end panel and corner flaps and improved bulge resistance at the end panels from sideward bulge of the product. Expand

17(7):729{735

- July
- 1995

Stricker and Orengo, 1995 M. Stricker and M. Orengo. Similarity of color images

- SPIE Conference on Storage and Retrieval for Image and Video Databases III, v olume 2420
- 1994