# 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://cmp.felk.cvut.cz/old_pages/mini.

For the particular case of 8-point algorithm: In the 8-point algorithm we solve 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 final solution. 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? – Gulzar Mar 21 at 9:11
• Updated my reply. – Tolga Birdal Mar 21 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)? – Gulzar Mar 21 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? – Tolga Birdal Mar 23 at 7:03
• I… don't see why it won't be meaningful. If you could show where exactly the algorithm would fail if you plug in zeros, i would be very happy – Gulzar Mar 23 at 9:33