18
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Is yi not the value of the same bin as xi but in the comparator distribution, rather than a second bin? $\endgroup$ – ReneBt May 31 '18 at 5:23
7
$\begingroup$

@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 http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382016000100023. Also see https://stats.stackexchange.com/search?q=%22chisquare+distance%22 for some other relevant posts on this site.

$\endgroup$
  • $\begingroup$ Can I ask why your last equation is called chisquare distance? Is it distributed as such? Can you provide a derivation please, or a link to one? I cannot seem to find one. $\endgroup$ – LeastSquaresWonderer Aug 3 '18 at 17:20
  • 1
    $\begingroup$ See my edits above. $\endgroup$ – kjetil b halvorsen Aug 3 '18 at 20:33
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You might want to expand on this answer a little bit, to explain how the other two might be used to calculate histogram similarities. Note that you can add math typesetting in Latex to your answer by using dollar signs: $x$ produces $x$ for instance. $\endgroup$ – Silverfish Apr 27 '16 at 8:20
  • 2
    $\begingroup$ You need to explain in what sense the third is symmetric in $x$ and $y$ as it does not look that way. $\endgroup$ – mdewey Apr 27 '16 at 8:33
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I have a hard time seeing how this is an answer to any of the questions. Can you elaborate? $\endgroup$ – The Laconic May 31 '18 at 0:14
  • $\begingroup$ This will give (in percentage, as requested) how different one histogram is from a full histogram. If you calculate this equation from both histograms we will know the difference from one to another as this one used for triangulation. $\endgroup$ – Carlos Barcellos Jun 9 '18 at 14:33

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.