Different results for Fundamental Matrix in Matlab

Question

I am implementing stereo matching and as preprocessing I am trying to rectify images without camera calibration. I am using surf detector to detect and match features on images and try to align them. After I find all matches, I remove all that doesn't lie on the epipolar lines, using this function:

[fMatrix, epipolarInliers, status] = estimateFundamentalMatrix(...
  matchedPoints1, matchedPoints2, 'Method', 'RANSAC', ...
  'NumTrials', 10000, 'DistanceThreshold', 0.1, 'Confidence', 99.99);

inlierPoints1 = matchedPoints1(epipolarInliers, :);
inlierPoints2 = matchedPoints2(epipolarInliers, :);

figure; showMatchedFeatures(I1, I2, inlierPoints1, inlierPoints2);
legend('Inlier points in I1', 'Inlier points in I2');

Problem is, that if I run this function with the same data, I am still getting different results causing differences in resulted disparity map in each run on the same data Pulatively matched points are still the same, but inliners points differs in each run. Here you can see that some matches are different in result:

UPDATE: I thought that differences was caused by RANSAC method, but using LMedS, MSAC, I am still getting different results on the same data

Amitie

Answer 1

EDIT: Admittedly, this is only a partial answer, since I am only explaining why this is even possible with these fitting methods and not how to improve the input keypoints to avoid this problem from the start. There are problems with the distribution of your keypoint matches, as noted in the other answers, and there are ways to address that at the stage of keypoint detection. But, the reason the same input can yield different results for repeated executions of estimateFundamentalMatrix with the same pairs of keypoints is because of the following. (Again, this does not provide sound advice for improving keypoints so as to solve this problem).

The reason for different results on repeated executions, is related to the the RANSAC method (and LMedS and MSAC). They all utilize stochastic (random) sampling and are thus non-deterministic. All methods except Norm8Point operate by randomly sampling 8 pairs of points at a time for (up to) NumTrials.

But first, note that the different results you get for the same inputs are not equally suitable (they will not have the same residuals) but the search space can easily lead to any such minimum because the optimization algorithms are not deterministic. As the other answers rightly suggest, improve your keypoints and this won't be a problem, but here is why the robust fitting methods can do this and some ways to modify their behavior.

Notice the documentation for the 'NumTrials' option (ADDED NOTE: changing this is not the solution, but this does explain the behavior):

'NumTrials' — Number of random trials for finding the outliers 500 (default) | integer

Number of random trials for finding the outliers, specified as the comma-separated pair consisting of 'NumTrials' and an integer value. This parameter applies when you set the Method parameter to LMedS, RANSAC, MSAC, or LTS.

MSAC (M-estimator SAmple Consensus) is a modified RANSAC (RANdom SAmple Consensus). Deterministic algorithms for LMedS have exponential complexity and thus stochastic sampling is practically required.

Before you decide to use Norm8Point (again, not the solution), keep in mind that this method assumes NO outliers, and is thus not robust to erroneous matches. Try using more trials to stabilize the other methods (EDIT: I mean, rather than switching to Norm8Point, but if you are able to back up in your algorithms then address the the inputs -- the keypoints -- as a first line of attack). Also, to reset the random number generator, you could do rng('default') before each call to estimateFundamentalMatrix. But again, note that while this will force the same answer each run, improving your key point distribution is the better solution in general.

Buckbuckaroo

so is there any way how to make it deterministic? – Amitie

Use the Norm8Point method if you have the compute power to use all points vs. random sampling of 8 pairs of points at a time. However, this method assumes NO outliers, and is thus not robust to erroneous matches! Perhaps if you use more trials the other methods will stabilize? – Buckbuckaroo

There is one kind of silly way, particularly in C++, but you need to modify source code. The pseudo-random generator always give the same series given the same seed. So you initialize random generator not with random, but with one predefined number. – Bombycid

@Bombycid Good point. If the generator is the system-wide generator, you could do rnd('default') before each run. – Buckbuckaroo

Yeah, I can modify random generator in matlab(set own seed), but how do I know which random is "good" to get the best result? – Amitie

@MartinCh The default is a Mersenne Twister with seed 0, which is just fine. Don't try to get better results by changing the generator, but by increasing 'NumTrials'. To reset the generator, just do rnd('default') before each call to estimateFundamentalMatrix. The function estimateFundamentalMatrix>generateRandomIndices uses the system-wide generator, so this should work. – Buckbuckaroo

@Buckbuckaroo Thanks ;) I suppose, that you meant rng instead of rnd, because there is no rnd function in matlab – Amitie

Answer 2

I know its too late for your answer, but I guess it would be useful for someone in the future. Actually, the problem in your case is two fold,

• Degenerate location of features, i.e., The location of features is mostly localized (on you :P) and not well-spread throughout the image.

• These matches are sort of on the same plane. I know you would argue that your body is not planar, but comparing it to the depth of the room, it sort of is.

Mathematically, this means you are kind of extracting E (or F) from a planar surface, which always has infinite solutions. To sort this out, I would suggest using some constrain on distance between any two extracted SURF features, i.e., any two SURF features used for matching should be at least 40 or 100 pixels apart (depending on the resolution of your image).

Icono

@jhegedus What does this have to do with the answer being non-deterministic? Same input not yielding the same output is because of random sampling. The result not being stable is a different issue and to that extent this answer is useful, but it won't change the fact that you can still end up with different keypoint matches. The OP was not aware of that. Please comment on why my answer is incorrect. The question was not "how do I get the most out of keypoint matching" it was why do I get a different result each time for the same data. – Buckbuckaroo

Yes, the existence of multiple valid answers is what makes it possible for the robust fitting method to converge on different solutions, but the reason why that can even happen on repeated runs with the same inputs is because of random sampling. The advice in answer is useful to understand why this particular problem is unstable, and I agree with it completely. The OP needed to understand both issues, but wanted to know why estimateFundamentalMatrix is nondeterministic. – Buckbuckaroo

Well, it is obvious that there are differences due to RANSAC's randomness. What is not obvious is why and when these differences are significant. As the OP says, "I thought the diffs. were caused by RANSAC", because he knows that RANSAC is random. Everybody knows it who knows what the acronym stands for. So, the question is not about explaining that RANSAC is random but about explaining why the differences are significant. A very difficult question to answer indeed ! – Lello

@Buckbuckaroo I wanted Martin to understand the reason behind this problem and changing only the 'numTrials' parameter won't affect the answer, as long as some adaptive non-maximal suppression technique is used. Other proposed answers have neglected this very important consideration and thus, I thought of bringing it to the notice of future readers. – Icono

@Lello The OP clearly didn't know LMedS and MSAC worked this way too if you read the rest of that quote. For the record, I do think this answer is better than mine from a general understanding standpoint, but I don't think I was so misleading as to warrant a downvote... That's all. – Buckbuckaroo

@Icono I think your answer is excellent. Perhaps I was a bit misleading about the number of trials, but please note that I primarily called out that portion of the docs so the OP would see that all of those method are stochastic. I purposely didn't get into how to address the problem upstream of the fitting, as the question appeared to me to be asking why with the same inputs different outputs are even possible. This area of study is obviously much bigger. – Buckbuckaroo

@Lello I don't think the OP was aware there could be difference, at all, not just significant but any differences. There was no mention of the magnitude of the differences. He just said there was a difference. So it seemed like a kind of trivia question (e.g. how is this possible?) rather than a request for general guidance to improve the stability of the computed homography. To me it's more obvious that improving the inputs (the keypoint) is the preferred way to address the problem, if there really is a problem, but again there's no indication of a grossly incorrect answer – Buckbuckaroo

I see, true, @chappjc, I agree, I was a little bit perhaps too quick in reacting, sorry for the agitation. – Lello

Answer 3

Another way to get better SURF features is to set 'NumOctaves' in detectSURFFeatures(rgb2gray(I1),'NumOctaves',5); to larger values.

I am facing the same problem and this has helped (a little bit).

Lello

Good advice, but I would point out that no matter how much you tune the feature detector and extractor, eventually the wrong scene (perhaps impossible) in a video stream may come along and create problems. In that case it may still be desirable to ensure reproducible results... a challenge for any method that uses random sampling :) and how I interpreted the question. +1 nonetheless. I hope my original answer was not too misleading. Cheers. – Buckbuckaroo