Histogram Chi-Square Distance Metric (Bug #2199)

Added by Nathaniel Quillin over 12 years ago. Updated about 10 years ago.

Status:Cancelled Start date:2012-07-25
Priority:Normal Due date:
Assignee:Steven Puttemans % Done:

0%
Category:documentation
Target version:3.0
Affected version:branch 'master' (3.0-dev) Operating System:Any
Difficulty: HW Platform:Any
Pull request:

Description

The Chi-Sqaure formula looks to be incorrect. I believe it should be SUM - H2)^2 / (H1 + H2) ).

Add: "+ H2"

http://docs.opencv.org/modules/imgproc/doc/histograms.html?highlight=histogram#double cvCompareHist(const CvHistogram* hist1, const CvHistogram* hist2, int method)

History

#1
Updated by Robert Witkowski over 12 years ago

Nathaniel Quillin wrote:

The Chi-Sqaure formula looks to be incorrect. I believe it should be SUM - H2)^2 / (H1 + H2) ).

Add: "+ H2"

http://docs.opencv.org/modules/imgproc/doc/histograms.html?highlight=histogram#double cvCompareHist(const CvHistogram* hist1, const CvHistogram* hist2, int method)

in some papers as this one (shape context, hist-comparison) there is also a factor 0.5 included, see URL:
http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/belongie-pami02.pdf

#2
Updated by Robert Witkowski over 12 years ago

Robert Witkowski wrote:

Nathaniel Quillin wrote:

The Chi-Sqaure formula looks to be incorrect. I believe it should be SUM - H2)^2 / (H1 + H2) ).

Add: "+ H2"

http://docs.opencv.org/modules/imgproc/doc/histograms.html?highlight=histogram#double cvCompareHist(const CvHistogram* hist1, const CvHistogram* hist2, int method)

in some papers as this one (shape context, hist-comparison) there is also a factor 0.5 included, see URL:
http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/belongie-pami02.pdf

ps: i've just checked that the '+ H2' is correctly implemented, already (see cvhistogram.cpp, google). ONLY THE DOCUMENTACION IS WRONG. in cvhistogram.cpp you can see that the variable b is calculated using in your notation b = H1 + H2 (here b = ptr1[i] + ptr2[i]):

case CV_COMP_CHISQR:
for( i = 0; i < total; i++ ) {
double a = ptr1[i] - ptr2[i];
double b = ptr1[i] + ptr2[i];
if( b != 0 )
result += a*a/b;
}
break;

#3
Updated by Vadim Pisarevsky over 12 years ago

thanks for the report!
looks like there are different opinions on how the formula should look like. We now use the formula from Wikipedia.
See also #1263

  • Assignee set to Vadim Pisarevsky
  • Status changed from Open to Cancelled

#4
Updated by Ming-Ming Cheng almost 11 years ago

Both documentation and implementation is wrong currently. The Chi-Sqaure distance, as documented in the famous paper ( http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/belongie-pami02.pdf ), should be

Could someone help to update the code in Histogram.cpp from
@
if( method == CV_COMP_CHISQR ) {
for( j = 0; j < len; j++ ) {
double a = h1[j] - h2[j];
double b = h1[j];
if( fabs(b) > DBL_EPSILON )
result += a*a/b;
}
}
@

to

@
if( method == CV_COMP_CHISQR ) {
for( j = 0; j < len; j++ ) {
double a = h1[j] - h2[j];
double b = h1[j] + h2[j];
if( fabs(b) > DBL_EPSILON )
result += 0.5*a*a/b;
}
}
@

I didn't find the one mentioned in "... the formula from Wikipedia.". Could someone post a link and we should correct that one as well.

  • Assignee deleted (Vadim Pisarevsky)
  • Target version changed from 2.4.3 to 3.0
  • Status changed from Cancelled to Incomplete

#5
Updated by Jewel James over 10 years ago

hey,

i have been using this method. id like to help. il refer with my professors,come to a conclusion and add back. im new to the procedure -> git and contributions. Should i get assigned or something?

#6
Updated by Steven Puttemans about 10 years ago

  • Status changed from Incomplete to Open
  • Assignee set to Steven Puttemans
  • HW Platform set to Any
  • Operating System set to Any
  • Pull request set to https://github.com/Itseez/opencv/pull/3725
  • Affected version set to branch 'master' (3.0-dev)

#7
Updated by Steven Puttemans about 10 years ago

It seems that this one has been discussed over and over

Hi @StevenPuttemans! I remember there was a long story about these formulas (maybe party reflected in code.opencv.org bugtracker, e-mail conversation, github patches etc.) and in the end we decided to have CV_COMP_CHISQR and CV_COMP_CHISQR_ALT that reflect both common cases. Now this patch tries to start it all over again. I suggest to retain it as is, or at least make some steps forward, not make another circle

So basically we decided to close it down.

  • Status changed from Open to Cancelled
  • Pull request deleted (https://github.com/Itseez/opencv/pull/3725)

Also available in: Atom PDF