Comparing two histograms

Question

For a small project, I need to compare one image with another - to determine if the images are approximately the same or not. The images are smallish, varying from 25 to 100px across. The images are meant to be of the same picture data but are sublty different, so a simple pixel equality check won't work. Consider these two possible scenarios:

1. A security (CCTV) camera in a museum looking at an exhibit: we want to quickly see if two different video frames show the same scene, but slight differences in lighting and camera focus means they won't be identical.
2. A picture of a vector computer GUI icon rendered at 64x64 compared to the same icon rendered at 48x48 (but both images would be scaled down to 32x32 so the histograms have the same total pixel count).

I've decided to represent each image using histograms, using three 1D histograms: one for each RGB channel - it's safe for me to just use colour and to ignore texture and edge histograms (An alternative approach uses a single 3D histogram for each image, but I'm avoiding that as it adds extra complexity). Therefore I will need to compare the histograms to see how similar they are, and if the similarity measure passes some threshold value then I can say with confidence the respective images are visually the same - I would be comparing each image's corresponding channel histograms (e.g. image 1's red histogram with image 2's red histogram, then image 1's blue histogram with image 2's blue histogram, then the green histograms - so I'm not comparing image 1's red histogram with image 2's blue histogram, that would just be silly).

Let's say I have these three histograms, which represent a summary of the red RGB channel for three images (using 5 bins for 7-pixel images for simplicity):

H1            H2            H3 

  X           X                     X
  X   X       X       X             X
X X   X X     X X   X X     X X X X X
0 1 2 3 4     0 1 2 3 4     0 1 2 3 4

H1 = [ 1, 3, 0, 2, 1 ]
H2 = [ 3, 1, 0, 1, 2 ]
H3 = [ 1, 1, 1, 1, 3 ] 

Image 1 (H1) is my reference image, and I want to see if Image 2 (H2) and/or Image 3 (H3) is similar to Image 1. Note that in this example, Image 2 is similar to Image 1, but Image 3 is not.

When I did a cursory search for "histogram difference" algorithms (at least those I could understand) I found a popular approach was to just sum the differences between each bin, however this approach often fails because it weighs all bin differences the same.

To demonstrate the problem with this approach, in C# code, like this:

Int32[] image1RedHistogram = new Int32[] { 1, 3, 0, 2, 1 };
Int32[] image2RedHistogram = new Int32[] { 3, 2, 0, 1, 2 };
Int32[] image3RedHistogram = new Int32[] { 1, 1, 1, 1, 3 };

Int32 GetDifference(Int32[] x, Int32[] y) {
    Int32 sumOfDifference = 0;
    for( int i = 0; i < x.Length; i++ ) {
        sumOfDifference += Math.Abs( x[i] - y[i] );
    }
    return sumOfDifferences;
}

The output of which is:

GetDifference( image1RedHistogram, image2RedHistogram ) == 6
GetDifference( image1RedHistogram, image3RedHistogram ) == 6

This is incorrect.

Is there a way to determine the difference between two histograms that takes into account the shape of the distribution?

Solution 1

Comparing histograms is quite a subject in itself.

You've got two big classes of comparison functions : bin-to-bin comparison and cross-bin comparison.

• Bin-to-bin comparison : As you stated, standard sum of differences is quite bad. There's an improvement: the Chi-squared distance. If H1.red[0] = 0.001 and H2.red[0] = 0.011, then H2.red[0] is much more important than if H1.red[0] = 0.1 and H2.red[0] = 0.11, even though in both cases |H1.red[0] - H2.red[0]| = 0.01.
• Cross-bin comparison : A standard example called the bin-similarity matrix requires some similarity matrix M where in M(i,j) is the similarity between the bins i and j. Assume bin[i] is red. If bin[j] is dark red, then M(i,j) is large. If bin[j] is green, M(i,j) is small. Then, the distance between histograms H1 and H2 would be sqrt((H1-H2)*M*(H1-H2)). This method takes in account what you've said about "close" bins! Earth Moving Distance (EMD) is another kind of cross-bin distance.

To finish, I've got three points :

• You should read this paper on histogram distance. It's quite easy and introduces you to histogram distances. All the distances I talked about are summed up nicely in chapter 1. Honestly, the final thing described in the article is not that complex, but it's probably overkill for your case.
• Cross-bin distance is very good, but can be costly (i.e : long to compute, because it involves a matrix, thus is O(n^2)). The simplest way to circumvent the expensive cross-bin computation (and it is widely done) is to do some soft assignment : if a pixel is red, then you should fill ALL the bins that are remotely looking like red (of course, giving more weight to the closest colors). Then you can use a bin-to-bin algorithm.
• A bit more math-centric : the previous point was all about reducing a cross-bin comparison to a bin-to-bin comparison. In fact, it consists of implicitly diagonalizing the similarity matrix M. If you can diagonalize M = P'*D*P where P' is the transpose of P, then sqrt((H1-H2)'*M*(H1-H2)) = sqrt((H1-H2)'*P'*D*P*(H1-H2)) = sqrt((P(H1-H2))'*D*(P(H1-H2))). Depending on how trivial it is for you to compute P(H1-H2), this can save you computation time. Intuitively, if H1 is your original histogram, P*H1 is a soft assignment and you are using the implicit similarity matrix M = P'*Id*P.

Solution 2

I'm surprised that no one mentioned opencv implementation of the histogram comparison, and can easily handle multichannel images (grayscale, rgb, rgba, etc) of different format (uchar, float, double, etc)

Includes the Bhattacharyya distance, Chi-Square, correlation and intersection methods. You can find the

compareHist(InputArray H1, InputArray H2, int method)

function in the manual here.

Solution 3

Earth Mover's Distance (EMD) is often used for this type of histogram comparison. EMD uses a value that defines the cost in 'moving' pixels from one bin of the histogram to another, and provides the total cost in transforming a specific histogram to a target one. The farther away a bin is, the higher the cost.

In your example, moving 5 units from red[0] to red1 would cost (c*1*5) while moving 5 units from red[0] to red[10] would cost (c*10*5).

There are several implementations out there. FastEMD has code in C++, Java and Matlab. I believe OpenCV has some support as well.

There are many papers published using this technique for large image database similarity searching.

Solution 4

I find the chi-squared test to be a good place to start when comparing histograms. If you don't have the same number of entries in each histogram you have to be a bit more careful as you can't use the 'normal' expression. From memory, if you assume that the histograms have unequal numbers of entries the the chi-square test generalises to

1/(MN) SUM_i[((Mni - Nmi)^2)/(mi+ni)].

M and N are the total number of entries in each histogram, mi is the number of entries in bin i of histogram M and ni is the number of entries in bin i of histogram N.

Another test is the Kolmogorov-Smirnov test. This test looks at the maximum difference between the cumulative probability distributions of the two histograms. This is harder to implement, I think numerical recipes in C has a code snippet in C and im pretty sure its in Matlab. If you more interested in the difference is histogram shape and not so much the exact values this may be a better test also its non-parametric.

Solution 5

You basically want to look a probability distances. There are many and you have to decide which is right for your application. Lately, I've had luck with Chi-squared and Kullback-Leibler.

View more solutions

Comments

[jilles de wit]

For histograms calculated from different sizes image, normalize the histogram by dividing the value of each bin by the number of pixels in each image.

[tkerwin]

Yes, you will want to normalize the histogram by transforming it into a PMF (probability mass function).

[Michal aka Miki]

I think Chi Square distance can be outperformed by considering the measures more precisely - some publications about this 2014-2016 in Mathematics. What do you think is the situation now?

[B. Decoster]

I am pretty sure that Chi-squared can be outperformed. The situation is that domain-specific knowledge performs much better than general rule-of-thumb algorithm such as chi-square.

[Michal aka Miki]

Has anyone studied the topic about the decision making of domain-specific knowledge? - - I would really like to compare some rule-of-thumb algorithms (Odds ratio, ...) with some domain-specific knowledge etc in regression analysis etc logistic etc in ECG signals.

[B. Decoster]

Unfortunately, this is where my knowledge stops. I remember that I had to study this field because I wanted histogram of colors for computer vision. The end conclusion was that selecting an appropriate color representation (it was something else than RGB) yielded much better results than using RGB with fancy algorithms. Of course, the best was using the appropriate color representation AND fancy algorithms. Anyways, I don't know much more, sorry

[Michal aka Miki]

Color presentation is easy itself. Mathematica has superior tools for that in comparison to Matlab. CIELAB/... is great with computer vision. - - It would be great to understand how well Mathematica's colormaps of computer vision really work. There are great algorithms itself for the task in Mathematica.

[B. Decoster]

I feel that you are trivializing the subject. The color representation depends on the problem at hand, and in the same way that deep neural networks build custom descriptors that outperform hand-made descriptors, I feel that hand-made color representation such as CIELAB don't always offer optimal results.

[Stefan Reich]

I tried to implement this, but didn't find a reasonably working method. For example, if the two histograms are completely distinct, the difference returned should be some fixed value (preferably 1), right? Your formula doesn't do this. So I ended up normalizing both histograms to a sum of 1 (so M=N=1) and in the end just dividing by 2 which makes everything work like a charm. Identical histograms give a value of 0, completely distinct histograms give 1, and the function returns plausible values inbetween for somewhat similar histograms.

[Alexis Wilke]

Oooh! That makes it easy :-)