Solved – Bhattacharyya distance for histograms

bhattacharyyadistancedistance-functionshistogramkullback-leibler

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?

Best Answer

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.

Related Solutions

Solved – Bhattacharyya distance for three histograms

Find similarity between RGB values separately, like I did.

float CTracker::calculate_similarity_colour (BlobPast* prev_blob, PositionArrays* curr_blob, int k)
{
    float total_red = 0;
    float total_blue = 0;
    float total_green = 0;
    float similarity = 0;
    float S_D_R = 0;
    float S_D_G = 0;
    float S_D_B = 0;

    for (int i = 0; i < 256; i++)
    {
        if ((prev_blob->colour_red[i] != NULL ) &&  (curr_blob->colours[i].colour_red != NULL))
        {
            S_D_R = sqrt (abs(  (prev_blob->colour_red[i]) *  (curr_blob->colours[k].colour_red[i])));
            total_red       = total_red + S_D_R;

            S_D_G = sqrt( abs (  ( prev_blob->colour_green[i]) *  (curr_blob->colours[k].colour_green[i])));
            total_green     = total_green + S_D_G;

            S_D_B  = sqrt( abs(  (prev_blob->colour_blue[i]) *   (curr_blob->colours[k].colour_blue[i])));
            total_blue = total_blue + S_D_B;
        }
    }

    similarity = (0.4 * total_red) + (0.3 * total_green) + (0.3 * total_blue);
    return similarity;
}

//Note the reason my similarity would be between 0-1 is I divided each each histograms each value by total number of pixels (i.e., normalizing)

Solved – Comparing two word distributions

You could use a customization of the Min-Hash algorithm. The problem then falls down to comparing hash-values of your distributions by their Hamming-Distance.

You start by seeding your random number generator (PRG) with $c$.
You draw $n$ samples from the first distribution $p_A$
You seed your PRG again with $c$
you sample $n$ words from your other distribution $q_A$.
You compare both samples by means of the Hamming-Distance. (i.e 500 our of 700 samples agree --> smilarity of 0.7)

If all words $a$ from your distributions $p_A(a)$ would have the same propability $p_A(a) = \frac{1}{|A|}$ the process would exactly result in Min-Hash. And Min-Hash is an approximation to the Jaccard Similarity of both sets of words. However, by enlarging $n$ you are able to get the exact value of the Jaccard-Index for $n \rightarrow \infty$.

With this scheme you can assign arbitrary probabilities to your words and nontheless are able to get a similarity score.

Anyhow, the process is not that simple, because typically the Alias Method of Vose is used to draw samples from discrete distributions. Then the drawn samples are not independent from each other (because sampling can use up a variable number of random numbers depending on $p_A(x)$), which is bad when comparing numbers by Hamming Distance later.

Hence, you are required to reseed after every drawn sample with a number $c+i$ where $i$ grows up to $n$.

Best Answer

Related Solutions

Solved – Bhattacharyya distance for three histograms

Solved – Comparing two word distributions

Related Question