[Solved]: distance between histograms

Problem Detail: 

I have 2 histograms that represent the height of characters in 2 images. example:

• 1 **
• 2 ****
• 3 ****
• .
• .
• .
• 100 ******

For these 2 histograms I compute the peaks. And To check if these 2 images are similar I compute the interseciton between the indices of the 2 images. Example: For image 1 the indices of the peaks are 1, 10 and 13 for image 2 the indices of the peals are 1,10, 14. Image1 Inter Image1 = 2 So these images are similar.

But I feel that the intersection is not enough. I think that i should also use the size of the buckets of the histograms peaks.

Is there a way to use to both of them to measure the similarity in 1 function So that I can have a stable similarity function?

Asked By : Hani Gotc

Answered By : Nicholas Mancuso

If you normalize your histograms you then have an empirical pmf. There are numerous methods to calculate distances of pmfs, such as Kullback-Leibler and Jensen-Shannon divergences. If the base-set of the histograms are exactly the same then KL divergence will work fine. If they intersect, but are not exactly the same, then JS divergence will work instead.

Be careful as KL divergence is non-symmetric. That is, given two pmfs $P$ and $Q$, $\text{D}_{\text{KL}}(P||Q)$ may not be equal to $\text{D}_{\text{KL}}(Q||P)$. On the other hand $\text{D}_{\text{JS}}$ is symmetric, but still not a metric.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12846