Bag of Features: why the distance between two histograms of the same image is different than 0?

asked 2016-07-20 11:23:33 -0500

lovaj gravatar image

I'm trying to implement a Content Based Image Retrieval application for small image datasets. I'm testing it just with 1 thousands images from Caltech1001.

The approach that I'm using is the classic Bag of Features model using OpenCV using k-means and cv::SIFT detector/descriptor and HISTCMP_CHISQR_ALT as distance metric. Just for testing purpose, I tried to use as a query one image from the dataset itself, so the distance should be 0. This is the relative code:

cv::Mat vocabulary; //fill vocabulary through k-Means
cv::Mat histograms;
cv::Mat imgHistogram;
cv::Ptr<cv::DescriptorMatcher> matcher(new cv::BFMatcher);
std::unique_ptr<cv::BOWImgDescriptorExtractor> bowDE = 
     std::make_unique<cv::BOWImgDescriptorExtractor> (featureDetectorDescriptor,matcher);
std::vector<cv::KeyPoint> keyPoints;
//Compute histograms for all dataset images 
bowDE->setVocabulary(vocabulary);
for (each img in the dataset){
    featureDetectorDescriptor->detect(img, keyPoints);
    bowDE->compute(img,keyPoints,word);
    histograms.push_back(word);
}
//Compute the word of one image img FROM THE DATASET ITSELF!
featureDetectorDescriptor->detect(img, keyPoints);
bowDE->compute(img,keyPoints,imgHistogram);
double mindist = DBL_MAX;
for(int i=0;i<1000;i++){
    double dist = compareHist(imgHistogram, histograms.row(i), cv::HISTCMP_CHISQR_ALT );
    if(dist<minDist)
        minDist = dist;
}

Ok, since the query image img is contained in the database itself, the most similar returned is img itself, but minDist is different from 0! For example, for one image the distance from herself is 0.0119228.

And these are the relative histograms:

img in histogram:

[0.0059701493, 0.0089552235, 0.052238807, 0.0014925373, 0.0029850747, 0.016417911, 0.0014925373, 0.0014925373, 0.0014925373, 0.0014925373, 0.011940299, 0.0074626869, 0.0014925373, 0.0044776117, 0.0029850747, 0.0044776117, 0.011940299, 0.014925374, 0.12985075, 0.0044776117, 0.0014925373, 0.0074626869, 0, 0.0029850747, 0.0014925373, 0.013432836, 0.0074626869, 0.011940299, 0.0029850747, 0.0014925373, 0.061194029, 0.013432836, 0.0059701493, 0.0029850747, 0, 0.0014925373, 0.0074626869, 0.0014925373, 0.0059701493, 0.0029850747, 0.0029850747, 0.0029850747, 0.0059701493, 0, 0.025373135, 0.017910447, 0.0044776117, 0.0044776117, 0.0044776117, 0.0014925373, 0.0014925373, 0.0074626869, 0.010447761, 0.014925374, 0.0044776117, 0.0029850747, 0.0059701493, 0.055223882, 0.0029850747, 0, 0.0089552235, 0.0029850747, 0.0074626869, 0.0044776117, 0.0074626869, 0.0089552235, 0.0059701493, 0.0014925373, 0.020895522, 0, 0, 0.014925374, 0.019402985, 0.0029850747, 0.0044776117, 0, 0.0089552235, 0.0029850747, 0.0029850747, 0.0029850747, 0, 0.0014925373, 0.016417911, 0, 0.010447761, 0.017910447, 0.013432836, 0.0089552235, 0.0014925373, 0.011940299, 0.019402985, 0.010447761, 0.0059701493, 0.059701495, 0.031343285, 0.016417911, 0.011940299, 0.0014925373, 0.010447761, 0.0044776117]

img as query:

[0.0061349692, 0.0092024542, 0.053680979, 0.0015337423, 0.0030674846, 0.016871165, 0.0015337423, 0.0015337423, 0.0015337423, 0.0015337423, 0.010736196, 0.0076687112, 0.0015337423, 0.0046012271, 0.0030674846, 0.0046012271, 0.012269938, 0.016871165, 0.12423313, 0.0046012271, 0.0015337423, 0.0076687112, 0, 0.0030674846, 0.0015337423, 0.01380368, 0.0076687112, 0.012269938, 0.0030674846, 0, 0.06134969, 0.01380368, 0.0061349692, 0.0030674846, 0, 0.0015337423, 0 ...
(more)
edit retag flag offensive close merge delete

Comments

can it be, that the caltech images are lossily compressed, e.g. jpg ?

berak gravatar imageberak ( 2016-07-20 11:43:55 -0500 )edit

Just a guess: Is it possible that internally a Flann-Tree is somewhee used to get closest distances? This would introduce some kind of randomness as it is only an approximation to the nearest neighbour search.

FooBar gravatar imageFooBar ( 2016-07-20 15:38:10 -0500 )edit

Yes they are if I'm not wrong (cannot check now), why should that matters?

lovaj gravatar imagelovaj ( 2016-07-20 15:39:22 -0500 )edit
1

... then the histogram would change since possible other nearest cluster center (=visual word) would have been choosen for some descriptors. As flann has also in its name, it only gives you the approximate nearest neighbor.

Guanta gravatar imageGuanta ( 2016-07-20 16:15:15 -0500 )edit

Actually with my "yes" I was reffering about the .jpg. As you can see from the code I'm using cv::Ptr<cv::DescriptorMatcher> matcher(new cv::BFMatcher);

lovaj gravatar imagelovaj ( 2016-07-21 11:46:59 -0500 )edit

So no, technically there should not be any randomization (right?)

lovaj gravatar imagelovaj ( 2016-07-21 11:47:45 -0500 )edit

hmm, the jpg idea is probably a wrong turn. yes, lossy jpg compression will lead to slightly different results on different machines or programs, but not within the same prog, linked to the same jpeg lib.

berak gravatar imageberak ( 2016-07-21 12:00:00 -0500 )edit