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:
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?
Superimposing one histogram on another works well because comparisons both within and between distributions are made on a common scale. The separate histograms provide a good way of examining the distribution of values in each sample. Comparison of two (or more) distributions is easy.
You can use the Two-sample Kolmogorov–Smirnov test to compare if the distributions of the two histograms are similar. Also you can apply the one-sample Kolmogorov–Smirnov test to compare each distribution against some reference distribution (normal, exponential, ...).
If you really need to compare histograms at different sample sizes, scale them both to area 1 (i.e. to be density estimates). However, as Nick suggested in comments, there are other ways of comparing the distributions that don't require binning.
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.
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
.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 :
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
.If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With