Bug report

[yaqding]

Thank you for your awasome Lib, but I have found a bug. Sometimes the number of iterations does not update. For example, when kProbNonInlierSample = 1, i.e. the inlier_ratios is very small, kLogDenominator will be zero.

https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L125 https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L155

[tsattler]

@yaqding Should these lines handle the corner cases? https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L115-L120

[yaqding]

@yaqding Should these lines handle the corner cases?

https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L115-L120

https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L122-L125

I think the problem is in these lines. For example, if inlier_ratio = 0.001 for the 8-point algorithm in the first several iterations, due to the round-off error, kLogDenominator would be 0, and then the number of required iterations would not be updated.

Edit: I have set the min iterations to 10, and sometimes the RANSAC break after 10 iterations.

[tsattler]

I don't think this behavior leads to problems in practice: If the inlier ratio is small enough such that kLogDenominator gets close to 0, then the number of iteration becomes extremely large. In practice, the number of iterations will be much higher than the maximum number of iterations that is typically used to keep RANSAC's run-time reasonable. In that sense, the function does what it is supposed to do and not update the number of iterations that are required.

On the other side, if your inlier ratio is really high, i.e., close to 1, you want to run more than 1-3 iterations to better handle noise on your data points. As such, the function does what is supposed to and returns min_iterations.

[yaqding]

Thanks for you answer. Maybe I didn't make it clear. I was evaluating 2-point solver and 8-point solver. So I set the min iterations to 10. However, for the 8-point solver, sample 10 times may not give a good model, and then kLogDenominator becomes 0. In this case, the max number of iterations does not update. https://github.com/tsattler/RansacLib/blob/7cc3decf7584386798b49d054669d77487a52670/RansacLib/utils.h#L127-L131 It's strange that the max number of iterations maintains 10, and RANSAC breaks after 10 iterations for the 8-point solver. This rarely happens since the inlier ratio of my data is about 25%.

[tsattler]

I don't think I understand the problem. kLogDenominator becomes 0 if the inlier ratio is close to 0. In this case, num_iters should be a very large number. As a result, the number of iterations should default to max_num_iterations_ (which should be set large enough since RANSAC will never go beyond it). The only issue that I could see is that there is some double overflow.

[yaqding]

numFrame13
keypoints 2:1000
total matches:1000
good matches:1000
 num_iters =-inf
 num_iters =-inf
 num_iters =2.07398e+16
 num_iters =2.71109e+14
 num_iters =1.17892e+11
 num_iters =321833
 num_iters =23483
 num_iters =19099
 num_iters =13691
 num_iters =13691
   ... LOMSAC found 368 inliers in 10000 iterations with an inlier ratio of 0.368
Total time taken: 0.837326s
numFrame14
keypoints 2:1001
total matches:1000
good matches:1000
 num_iters =-inf
 num_iters =-inf
 num_iters =-inf
   ... LOMSAC found 12 inliers in 10 iterations with an inlier ratio of 0.012
Total time taken: 0.006482s
numFrame15
keypoints 2:1001
total matches:1001
good matches:1001
 num_iters =-inf
 num_iters =-inf
   ... LOMSAC found 20 inliers in 10 iterations with an inlier ratio of 0.01998
Total time taken: 0.006874s
Total time taken: 0.749829s

These results are based on a VO dataset. The inlier ratio is ~30%. Sometimes, in the first several iterations of the 8-point solver, the estimated model does not give any inlers, and kLogDenominator becomes 0. Then num_iters is -inf, and num_req_iterations = max(min_iterations, -inf) = 10.

[tsattler]

Okay, I think I see the issue now.

I just pushed a potential fix. When you have time, could you check whether you still get this behavior?

[yaqding]

Thanks for your update! https://github.com/tsattler/RansacLib/blob/eab897006f0fff4d93653afd620acf11b5be18d3/RansacLib/utils.h#L155-L160 I think there is a small issue. Since log(kProbNonInlierSample) is negative, max(std::log(kProbNonInlierSample), numeric_limits<double>::min()) should be min(std::log(kProbNonInlierSample), -numeric_limits<double>::min()). On the other hand, to avoid kLogNumerator / kLogDenominator overflow, it might be better to use, e.g., min(std::log(kProbNonInlierSample), -1e-10). And https://github.com/tsattler/RansacLib/blob/eab897006f0fff4d93653afd620acf11b5be18d3/RansacLib/utils.h#L125 also needs a fix.

Thanks again for your awesome Lib! Now it works perfectly for me.

[tsattler]

I think a better solution is this (which I just pushed):

https://github.com/tsattler/RansacLib/blob/edd5edfedabeca4e66bce3be5f5b60bac1407547/RansacLib/utils.h#L124-L130

The idea is to directly return max_iterations if the inlier ratio is so small that RANSAC would require an unreasonable amount of iterations (1e+13 or higher).

Could you check whether this works in your setting? Thank you very much!

[yaqding]

Thanks! It works well.

[tsattler]

Thank you very much for raising the issue. I will close this now since the problem seems to be resolved.