Continued reductions in the prices of mass storage and widespread access to computer networks, especially the Internet, have given a large number of users access to vast amounts of information. Much of this information is pictorial, often ordinary images stored in digital form. Yet the tools available for organizing, browsing, and interrogating such image data have not kept pace with the volume of information made available. This research develops a novel way of summarizing and indexing images and other pictorial data based on their appearance, and more specifically on their color, shape, and texture content. These descriptors, called image signatures, are uniform, compact, flexible, robust, and intuitive. The notion of the Earth-Mover's Distance between signatures is introduced and used to give a metric structure to the image space. This metric structure, together with additional geometric information, is then exploited to provide efficient nearest-neighbor search algorithms, as well as to compute distance-preserving embeddings of the image space, or portions thereof, into a low-dimensional Euclidean space. Such embeddings, obtained using multi-dimensional scaling, allow the user to visualize intuitively both local image neighborhoods of interest, or the entire image space at once. The user is able to navigate around the image space intuitively, with a sense of continuity and comprehensiveness, unlike current systems which typically present fragments of the data-base in a disconnected fashion. These tools then enable a novel metaphor for exploring image data- bases, making it more akin to the familiar browsing of a library or a bookstore.
