Bhattacharyya distance for histograms

Question

One of the ways to measure the similarity of two discrete probability distributions is the Bhattacharyya distance. In computer vision, for example, it is used to evaluate the degree of similarity between two histograms. However this metric treats all variables as they were isolated among each other; in other words if the histograms had 8 bins, colour values gathered in bin 8 are very close to those of bin 7 and far away from those of bin 1, but for the Bhattacharyya distance they are simply different.

Is there a metric that takes into account closeness between discrete variables?

I asked myself why in literature they don’t use a Kullback–Leibler distance for this task and I gave two answers: it is a real metric and 0-valued bins are not a problem. Are there any other reasons?

Answer 1

You could use the Earth-Movers-Distance (EMD), which takes into account a ground-distance between the bins and solves a transportation problem (basically, and hence the name: one histogram is a set of piles of earth, one a set of holes and you want to fill the holes as efficiently as possible). Afaik it is quite a standard distance comparing images in content-based image retrieval.

Answer 2

I see a couple of possibilities.

One would be to apply a measure akin to a ECDF based test, like a Kolmogorov-Smirnov - but to allow for the discreteness of the distribution (so if you do hypothesis tests, or compute standard errors, you can't take the usual continuous-distribution calculations.

Another would be to look at partitions of a chi-square statistic, as with Rayner and Best's approach (based originally on Neyman-Barton smooth tests). This uses orthogonal polynomials to partition a chisquare into linear, quadratic, etc components and then just takes the first few (e.g. six is a common choice) components. While the original full chi-square ignores ordering, the low-order partitions respect it. The first component would respond to differences in location, for example, and the second to differences in spread.