A Compressible Earth Mover's Distance (CEMD) better matches how humans perceive distance between distributions. Earth and holes are able to be compressed when moving from the earth to the holes thus minimizing the distance and improving the quality of image comparison. CEMD is utilized in a number of implementations, for instance, content based image retrieval, color query and other applications in multimedia. Another implementation includes using CEMD with a content recognition system for indexing occurrences of objects within an audio/video content data stream which processes the stream of data to generate a content index database corresponding to the content stream. CEMD is usable with in a variety of systems to assist in image recognition.