A fast distance between histograms

A histogram of a set with respect a measurement represents the frequency of quantified values of that measurement in the samples. Finding the distance or similarity between histograms is important in pattern classification or clustering and image retrieval. Several measures of similarity between histograms have therefore been used in computer vision and pattern recognition. Most of the distance measures in the literature (there is an interesting compilation in [1]) consider the overlap or intersection between two histograms as a function of the distance value but do not take into account the similarity in the non-overlapping parts of the two histograms. For this reason, Rubner presented in [2] a new definition of the distance measure between histograms that overcomes this problem of non-overlapping parts. Called Earth Mover’s Distance, it is defined as the minimum amount of work that must be performed to transform one histogram into another by moving distribution mass. This author used the simplex algorithm. Later, Cha presented in [1] three algorithms for obtaining the distance between one-dimensional histograms that use the Earth Mover’s Distance. These algorithms compute the distance between histograms when the type of measurements are nominal, ordinal and modulo in O(z), O(z) and O(z2), respectively, and where z the number of levels or bins. Often, for specific set measurements, only a small fraction of the bins in a histogram contains significant information, i.e. most of the bins are empty. This is more frequen