Comparing two histograms using Chi-Square distance

Question

I want to compare two images of faces. I calculated their LBP-histograms. So now I need to compare these two histograms and get something that will tell how much these histograms are equal (0 - 100%).

There are many ways of solving this task, but authors of LBP method emphasize (Face Description with Local Binary Patterns: Application to Face Recognition. 2004) that Chi-Square distance perfoms better than Histogram intersection and Log-likelihood statistic.

Authors also show a formula of Chi-Square distance:

$$ \sum_{i=1}^{n} \cfrac{(x_i - y_i)^2} {(x_i + y_i)} $$

Where $n$ is a number of bins, $x_i$ is a value of first bin, $y_i$ is a value of second bin.

In some researches (for example The Quadratic-Chi Histogram Distance Family) I saw that the formula of Chi-Square distance is:

$$ \cfrac{1}{2}\sum_{i=1}^{n} \cfrac{(x_i - y_i)^2} {(x_i + y_i)} $$

And there http://www.itl.nist.gov/div898/handbook/eda/section3/eda35f.htm I see that formula of Chi-Square distance is:

$$ \sum_{i=1}^{n} \cfrac{(x_i - y_i)^2} {y_i} $$

I stuck with it. I have several questions:

1. What expression should I use?
2. How should I interpret a result of difference? I know that difference that is equal to 0 means that both histograms are equal, but how can I know when both histograms are totally different? Do I need to use a Chi-Square table for it? Or do I need to use a threshold? Basically I want to map difference to percents.
3. Why these three expressions are different?

Answer 1

@Silverfish asked for an expansion of the answer by PolatAlemdar, which was not given, so I will try to expand on it here.

Why the name chisquare distance? The chisquare test for contingency tables is based on $$ \chi^2 = \sum_{\text{cells}} \frac{(O_i-E_i)^2}{E_i} $$ so the idea is to keep this form and use it as a distance measure. This gives the third formula of the OP, with $x_i$ interpreted as observation and $y_i$ as expectation, which explains PolatAlemdar's comment "It is used in discrete probability distributions", as for instance in goodness of fit testing. This third form is not a distance function, as it is asymmetric in the variables $x$ and $y$. For histogram comparison, we will want a distance function which is symmetric in $x$ and $y$, and the two first forms give this. The difference between them is only a constant factor $\frac12$, which is unimportant as long as you just chooses one form consistently (though the version with extra factor $\frac12$ is better if you want to compare with the asymmetric form). Note the similarity in these formulas with squared euclidean distance, that is not coincidence, chisquare distance is a kind of weighted euclidean distance. For that reason, the formulas in the OP is usually put under a root sign to get distances. In the following we follow this.

Chisquare distance is used also in correspondence analysis. To see the relationship to the form used there, let $x_{ij}$ be the cells of a contingency table with $R$ rows and $C$ columns. Denote the row totals be $x_{+j}=\sum_i x_{ij}$ and the column totals by $x_{i+}=\sum_j x_{ij}$. The the chisquare distance between rows $l,k$ is given by $$ \chi^2(l,k) = \sqrt{\sum_j \frac1{x_{+j}}\left(\frac{x_{lj}}{x_{l+}}-\frac{x_{kj}}{x_{k+}} \right)^2 } $$ For the case with only two rows (the two histograms) these recovers the OP's first formula (modulo the root sign).

EDIT

Answering to question in comments below: A book with long discussions of the chisquare distance is "CORRESPONDENCE ANALYSIS in PRACTICE (Second Edition)" by Michael Greenacre (Chapman & Hall). It is a well established name, coming from its similarity to chisquare as used with contingency tables. What distribution does it have? I have never studied that, but probably (under some conditions ...) it would have some chisquare distribution, approximately. Proofs should be similar to what is done with contingency tables, most literature about correspondence analysis does not go into distribution theory. A paper having some, maybe relevant such theory is ALTERNATIVE METHODS TO MULTIPLE CORRESPONDENCE ANALYSIS IN RECONSTRUCTING THE RELEVANT INFORMATION IN A BURT'S TABLE. Also see this other posts for some other relevant posts on this site.

Answer 2

I found this link to be quite useful: http://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/histogram_comparison/histogram_comparison.html

I am not quite sure why, but OpenCV uses the 3rd formula you list for Chi-Square histogram comparison.

In terms of meaning, I am not sure any measurement algorithm is going to give you a bounded range, like 0% to 100%. In other words, you can tell for sure that two images are the same: a correlation value of 1.0 or a chi-square value of 0.0; but it's tough to set a limit on how different are two images: imagine comparing a completely white image vs a completely black image, the numerical value would be either Infinity or maybe Not-a-Number.

Answer 3

In fact you can use whatever you believe is correct for your case. The last one is different. It is used in discrete probability distributions, as the last one will be symmetric if you swap $x$ and $y$.

The other two are used in calculating histogram similarities.

Answer 4

As OP requested, the value in percentage (for equation 1):

$p = \frac{\chi * S * 100}{N}$

Where: $p$ is the percentage of difference (0..100). $\chi$ is the result of equation 1. $N$ is the number of bins in histogram. $S$ is the maximum possible value in the bin.

Complemented as requested:

Calculating this equation one can have the percentage of difference from a full histogram. Calculating this for both histograms and then subtracting one from another, one can have the difference in percentage.