Implementations of coverage-based image relevance ranking are described. In one implementation, an acquired image is ranked relative to a set of previously stored images based upon the conditional entropy of the acquired image. The conditional entropy may be computed after first removing overlapping pixels that are present in both the acquired image and the set of previously stored images. Once the image is assigned a relevance rank, other decisions concerning the image may be made based on the rank, such as whether to save the image, delete the image, or use it to replace a less relevant image.