OpenCV different output results using a BruteForceMatcher over two different runtimes with same input

Intro : First and as an introduction, i am quite "proud" to ask my first question on StackOverflow. I hope I'll be able to help other people as much as they help me.

Context : 开发者_StackOverflow社区I am developping an application that searches for features in an image using a SURF algorithm. I compute the keypoints and I extract the descriptors with SURF. Then, I use a bruteforce matcher based on euclidian distance to match descriptors of image 1 with image 2. Here is the problem, i don't get the same results with 2 different runs of the program (using the same image, should I precise :p).

Outputs : Here are the outputs,

1st runtime on the 20 first matches out of 3620

0:  0   89  0.292352
1:  1   997 0.186256
2:  2   1531    0.25669
3:  3   2761    0.24148
4:  4   2116    0.286187
5:  5   2996    0.201048
6:  6   3109    0.266272
7:  7   2537    0.17112
8:  8   2743    0.211974
9:  9   2880    0.208735
10: 10  2167    0.269716
11: 11  2431    0.164508
12: 12  1474    0.281442
13: 13  1867    0.161129
14: 14  329 0.18388
15: 15  1580    0.229825
16: 16  1275    0.254946
17: 17  1749    0.203006
18: 18  305 0.221724
19: 19  1501    0.224663
20: 20  917 0.20708

2nd runtime on the 20 first matches out of 3620

0:  0   1455    0.25669
1:  1   963 0.186256
2:  2   3008    0.150252
3:  3   2936    0.24148
4:  4   2172    0.286187
5:  5   2708    0.211974
6:  6   730 0.185199
7:  7   3128    0.266272
8:  8   750 0.181001
9:  9   2272    0.17112
10: 10  2842    0.208735
11: 11  55  0.229677
12: 12  2430    0.269716
13: 13  2360    0.164508
14: 14  1497    0.229825
15: 15  2443    0.254148
16: 16  1784    0.161129
17: 17  1209    0.254946
18: 18  311 0.18388
19: 19  944 0.228939
20: 20  533 0.221724

Code : Here is a part of the code i use

SurfFeatureDetector detector(400);
vector<KeyPoint> keypoints1, keypoints2;
detector.detect(img1, keypoints1);
detector.detect(img2, keypoints2);

SurfDescriptorExtractor extractor;
Mat descriptors1, descriptors2;
extractor.compute(img1, keypoints1, descriptors1);
extractor.compute(img2, keypoints2, descriptors2);

vector<DMatch> filteredMatches;
matching(descriptors1,descriptors2,filteredMatches,1);

Here is the matching function

void crossCheckMatching( const Mat& descriptors1, const Mat& descriptors2,
                     vector<DMatch>& filteredMatches12, int knn=1 )
{
    BruteForceMatcher<L2<float>> matcher;
    filteredMatches12.clear();
    vector<vector<DMatch> > matches12, matches21;

    matcher.knnMatch( descriptors1, descriptors2, matches12, knn );
    matcher.knnMatch( descriptors2, descriptors1, matches21, knn );

    debug_writeMatches("D:/jmartel/exec2-log.txt",matches12);
    ...
}

Conclusions : The SURF algorithm gives "realistic" outputs, it is partly proved by the same number of detected keypoints over 2 runtimes with the same 2 images. The BruteForceMatcher gives me really strange output, it is proved by the log file, and with the image i can output which clearly shows it does not match in the same way over two runtimes.

I also implemented all this code on GPU and my observations are similar. However, SURF provides more point on GPU (with the same parameters).

If we look carefully to the points, some distances are exactly similar, which can be possible but strange (even if the descriptors between the 2 set of points can be equal...). It's the example of the couple

  (runtime 1) 1: 1 997 0.186256
/ (runtime 2) 1:1 963 0.186256 

or even stranger

  (runtime 1) 14: 14  329 0.18388
/ (runtime 2) 18: 18  311 0.18388

The OpenCV2.0 Doc does not say anything particularly interesting from what i read. See BruteForceMatcher C++ Documentation for OpenCV2.1 here

If you have any explanation, or anything i could change in the code, I'll be glad. Thanks for your help.

Julien,

Could you check the order of the featuers? If you have multiple CPUs, the code may run parallel so the features are not in the same order (for each time).

Could you be a little bit more specific, even if it runs in parallel why should the algorithm give different outputs ?

But what you tell me is that the outputs I gave as examples are not relevant as there is a parallel execution, it could explain why the distance in certain cases are exactly similar => 2 runtimes = 2 same pair of descriptors with 2 different runtime index of processing = 2 different order of outputs... However, there is still the problem that it doesn't give the same Image result... i see different pairs are linked why should it be changed because of parallelism ? Isn't there something else ?

If differences are really small then using float vs. double can make a difference.

Your non-determinism might arise from use of pointer addresses as hash keys, even though this is just a guess.