Why are 8 points needed to compute a fundamental matrix?

Homograpies have 8 degrees of freedom.
Fundamental matrices have 7.
Essential matrices have 5.

To the best I could find, all those matrices are obtained by using the 8 point algorithm.

I don't see why the fundamental and essential matrices can't make do with less points.

Hum, no

• A homography can be exactly fit to 4 point such that no three of them are collinear (example implementation in OpenCv).
• An essential matrix can be fit to the image of 5 non-coplanar points (implementation).
• A fundamental matrix can be fit to 7 points (implementation)

They can. As Francesco mentioned, these problems can be solved with less correspondences. What makes the difference is how we formulate the problem.

If we like a fast linear solution, then 8-points are required. For formulations using less number of points, the constraints are non-linear and typically involve either determinants or systems of polynomial equations that are solved with some form of Gröbner basis methods. These methods are typically known under the name minimal problems in computer vision and are investigated heavily by Zuzana Kukelova. For a set of related problems and proposed solutions refer to the website: http://aag.ciirc.cvut.cz/minimal/.

For the particular case of 8-point algorithm: In the 8-point algorithm we solve (in a linear fashion) for the elements of a matrix that is not necessarily a fundamental/essential matrix. In a subsequent step, we then project this matrix onto the manifold of essential matrices. This is how we obtain the end result. That stage ensures two non-linear constraints: \begin{align} \det\mathbf{E} &= 0\\ 2\mathbf{E}\mathbf{E}^{\top}\mathbf{E}-\text{tr}(\mathbf{E}\mathbf{E}^{\top})\mathbf{E} &= 0 \end{align} So not every matrix is an essential matrix and we cannot simply have $$0$$s for certain terms.

You see here that the solution to the initial linear system is subject to a different constraint which can yield a linear system. If we like to bake the actual non-linear constraints in, we can reduce the number of points to 5 (for essential) at the cost of increased complexity.

• Thanks! Why don't less points firmulate just tge same linear equations? Why aren't less than 8 enough? Mar 21 '20 at 9:11
• Updated my reply. Mar 21 '20 at 9:59
• Sorry I don't get it. In the 8 point algorithm, we are solving for [a,b,c,d,e,f,g,h,1], so why not for example just solve the same way for [a,b,c,0,e,f,0,0,1] (matrices in vec form)? Mar 21 '20 at 13:12
• I think this just creates more numerical problems. Because we then need to project the final E onto the essential manifold, but having 0s there creates a quite far matrix. The projection is not very meaningful then, right? Mar 23 '20 at 7:03
• The link don't work here
– Bob
Aug 16 '21 at 16:51