2
$\begingroup$

I need to implement a function (in Golang) to compare the similarity/distance of two histograms. The histograms were generated from two different images. I have searched on the internet and have found some metrics that can be used to perform this comparison, for example, Chi Square and Intersection.

Here are all the metrics and formulas that I have found:

Chi Square :

Formula:

$x^2 = \sum_{i=1}^{n}\frac{(hist1_{i} - hist2_{i})^2}{hist1_{i}}$

Corresponding code:

var sum float64
for index := 0; index < len(hist1); index++ {
    numerator := pow(hist1[index] - hist2[index])
    sum += numerator / hist1[index]
}

Where pow is a function that returns value * value.

Euclidean Distance :

Formula:

$D = \sqrt{\sum_{i=1}^{n}(hist1_{i} - hist2_{i})^2}$

Corresponding code:

var sum float64
for index := 0; index < len(hist1); index++ {
    sum += pow(hist1[index] - hist2[index])
}
sum = math.Sqrt(sum)

Normalized Euclidean Distance :

Formula:

$D = \sqrt{\sum_{i=1}^{n} \frac{(hist1_{i} - hist2_{i})^2}{n}}$

Corresponding code:

var sum float64
n := float64(len(hist1))
for index := 0; index < len(hist1); index++ {
    sum += pow(hist1[index]-hist2[index]) / n
}
sum = math.Sqrt(sum)

Intersection :

Formula:

$D = \sum_{i=1}^{n} min(hist1_{i}, hist2_{i})$

Corresponding code:

var sum float64
for index := 0; index < len(hist1); index++ {
    sum += min(hist1[index], hist2[index])
}

Where the min function returns the minimum value.

Normalized Intersection :

Formula:

$D = \frac{\sum_{i=1}^{n} min(hist1_{i}, hist2_{i})}{max(\sum_{i=1}^{n}hist1_{i},\sum_{i=1}^{n}hist2_{i})}$

Corresponding code:

var sum float64
for index := 0; index < len(hist1); index++ {
    sum += min(hist1[index], hist2[index])
}
sum = sum / max(sum(hist1), sum(hist2))

Where the sum function returns the sum of all elements in the slice and the max function returns the maximum value.

References :

  1. OpenCV Histogram Comparison: http://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/histogram_comparison/histogram_comparison.html
  2. Euclidean Distance: http://www.pbarrett.net/techpapers/euclid.pdf
  3. Histogram intersection for change detection: http://blog.datadive.net/histogram-intersection-for-change-detection/
  4. The Simplest Classifier: Histogram Comparison: https://mpatacchiola.github.io/blog/2016/11/12/the-simplest-classifier-histogram-intersection.html
  5. Histogram Intersection with two different bin sizes?: https://dsp.stackexchange.com/questions/18065/histogram-intersection-with-two-different-bin-sizes

Questions :

Now, I have some questions based on the above description:

  1. I'm not a mathematician (I'm a software developer), so can someone confirm to me if all 5 formulas are correct?
  2. Which of the 5 metrics is the best (or commonly used) to compare two histograms? (As I have read people uses commonly the Chi-Square and the Intersection, but I'm not sure).
  3. Is there some other good metric (or commonly used) to compare two histograms?
  4. As I understand: when using the Chi-Square, Euclidean Distance or Normalized Euclidean Distance, the closer to zero is the result, higher is the similarity between the histograms. In the other hand, when using the Intersection or the Normalized Intersection, higher results means higher similarity between the histograms. If it is correct, is there a way that I can invert the results from the Intersection and Normalized Intersection so it 'works' as the other metrics (closer to zero means higher similarity)? As the Normalized Intersection results range is between 0-1 it is easy to invert, but I don't know if it is possible to the Intersection metric.

Notes :

  • If someone find something wrong in the codes above, please let me know.
  • I'm sorry if I have written some bullshit on this question, as I explained I am not a mathematician so I don't have much knowledge about this.
  • Any suggestion to improve the question, the formulas or codes are welcome.
  • I'm not sure if I have used the correct tags, so please feel free to edit it.
$\endgroup$
1
$\begingroup$

From what I understand you're comparing two lists of numbers.

The Euclidian distance seems like a good method (which is equivalent to the normalized Euclidian distance, you just scale it down to $[0,1]$).

The Chi square method is quite similar to the Euclidian distance but it punishes relative difference instead of absolute :

For example, let's have : $h_1=[1,10]$ and $h_2=[2,11]$.

In this example the Euclian method will treat the difference between ($1$ and $2$) and ($10$ and $11$) the same, whereas the chi method will consider the difference between $1$ and $2$ to be more significant than the one between $10$ and $11$.

That's up to you to decide which one you prefer.

You can discard the intersections as they really have no value, as is, in your case.

Another simple metric you could use is this one :

$$d = \sum_n|h1_i-h2_i|$$

This one, and the euclidian metric, are classic metrics in mathematic. The main difference between those two is the euclidian method will punish a lot more a large difference.

As for the code, are you sure you can't fix those square by any methods ? Also, for the normalized euclidian, you might want to assign a variable to len(h1) outside the loop instead of searching for it each iteration.

EDIT : As I read deeper into your references, I think I might have overlooked the intersection method. Can you explain a little bit more what you're trying to achieve by comparing the two histograms ?

$\endgroup$
  • $\begingroup$ Thanks for the tips, I will create my own pow function to work with uint8 type and updated the question. As the histograms represent the grayscale pixels of two images I want to compare the similarity of the histograms to know how similar are the images. Just to make sure, the | symbol means "absolute value"? $\endgroup$ – KelvinS Aug 6 '17 at 0:11
  • $\begingroup$ Is each data point the greyscale value of a single pixel or is it the distribution of each scales of grey (wich would likely be of length 256)? For the code part I'm just saying because you asked but this shouldn't be a major issue, it's just kind of painful to see :p And yes indeed the | symbol means absolute value, in fact this metric is defined by the absolute value norm. $\endgroup$ – Furrane Aug 6 '17 at 0:19
  • $\begingroup$ It is the distribution of each scale of gray. The array has a fixed length of 256. Based on your question, I think I have found a bug in the code. The data type should not be uint8 because the image may have more than 255 pixels on the same scale of gray. Thanks again. $\endgroup$ – KelvinS Aug 6 '17 at 0:33
  • 1
    $\begingroup$ @KelvinS Well you have to keep in mind that all those methods take a vector (here a 256 dimension vector) and output a single scalar so there will be a significant loss in information. If we look at your examples, yes they are different (and their intersection would be very different) but what if it was the same object but one photo was just much brighter than the other ? Then all pixels would have say a +50 on the greyscale. All in all, I think each different method have pros and cons and it's a good thing you're providing the user with choices to experiment with =) $\endgroup$ – Furrane Aug 6 '17 at 4:01
  • 1
    $\begingroup$ Well you need to think of the nature of the objects you're handling right now. The Euclidian and Chi metrics take two histograms as input and output what you can call the distance between the two. Those are metrics, they mesure the distance. On the other and, the intersection method takes two histograms as input but output an histogram. You can't compare two things of different nature. $\endgroup$ – Furrane Aug 7 '17 at 13:56
0
$\begingroup$
  1. I have a doubts about your chi2 formula, since it should be h1+h2 in the denominator, because another histogram has statistical uncertainty as well. And following variance sum law, variance of difference is a sum of variances.
  2. chi2 and Kolmogorov-Smirnov (KS) tests
  3. If you want to compare bulks of distributions than KS is perfect for that.
  4. For every above mentioned statistic the only way to confirm whether two histograms are produced by similar simulations is to convert the statistic to p-value and compare it to significance level.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.