Minimal solvers for fundamental and essential matrix

[john-maidbot]

Hello,
I've been reading through this repo in order to get more familiar with the inner workings of the project.

While reading, I noticed that your essential and fundamental matrix solvers are both using the 8 point method. However, 5 and 7 point solvers exist for the essential and fundamental matrix, respectively. Have you considered using these? I'm curious if there is a motivation to choose the 8 point methods.

Thanks for your time!

[ymd-stella]

Good idea. I expect that fewer points will perform better when using RANSAC.

[john-maidbot]

Thanks!

For the essential matrix, I think algorithm 2 from this paper would be a great choice for slam b/c it is very fast and intuitive/readable (whereas Nister and li/Hartley's algorithms are complex and challenging to read once coded )
https://arxiv.org/abs/1007.1432

I would like to test this against the current essential_solver, and put up a PR if it ends up being a worthwhile improvement. Would that be ok? Id also be happy to look into alternate solvers if you have suggestions.

[jjd9]

Hello,

I wanted to give an update since this is taking a little longer than I expected.

I have implemented the minimal essential solver. Sadly the iterative method I linked did not work very well 😅 I think my implementation may have had some numerical stability issues since it did not reliably pass the unit tests. I opted to instead use the 5 point method from Stewenius et al. and that consistently passes the unit tests.

I also tweaked the homography solver. it was using 8 points, but you only need 4 points to find a homography. This allows the RANSAC for loop to sift through outliers ~2x as fast. This also passes the unit tests.

I did not mess with the fundamental or pnp solvers at this time.

The last thing I need to do is some experimentation to compare these new methods with what was there already. I think the main things to check would be runtime and robustness to outliers.

• run RANSAC with 8pt essential solver and 5 pt essential solver and verify they are on par in terms of speed
• run RANSAC with 8pt essential solver and 5 pt essential solver with more and more outliers and see at what point they break. Ideally the 5 pt method is will break later on that the 8 pt one on average.

w.r.t. the homography solver, idk if this requires experimentation as I dont see any reason to doubt it will be faster. It is identical to the old code but I just changed 8 to 4 and added a check for degeneracy (e.g. if a sample of 4 points is all collinear).

Once I get that done, I will put up a PR for review.

Also apologies, I accidentally started this discussion with my work github without realizing it 🤦 I am planning to contribute in a personal capacity. So I will use my personal github account (this one) going forward.

[jjd9]

associated PR for this idea: #558