Our goal is to directly get the unique solution from a redundant polynomial equation system. Finding the common roots is equivalent to the determination of the zero-dimensional variety generated by the ideal . We can algebraically get a linear polynomial in generic cases and in one of the unknowns by successive application of Ritt method or pseudo division [1] of polynomials over . This can effectively be done with any computer algebra system and will directly give the unique solution of the problem for general configurations of the points. However this algebraic method is almost useless for practical situations as the successive elimination will ultimately give complicated coefficients for the final linear polynomial which compromise the numerical stability of the solution. Instead of doing it algebraically, our goal is to develope a numerical linear method which indeed gives the unique solution if it does exist.
For n points, each pair of points gives a 4th degree polynomial, we can have quadratic constraints of type on the n unknown distances , and 4th degree polynomials of type in one variable .
For n=4, we obtain three 4th degree polynomials
Let the 5-vector , this can be rewritten in matrix form:
This can be viewed as a homogeneous linear equation system in for . Since the matrix has at most rank , the singular value decomposition of is
The null space of is spanned by the right singular vectors and . Therefore we can construct a 1-dimensional solution space for , parameterized by and :
Now consider the nonlinear constraints among the components of . It can be easily checked that
Substituting from (4) in (5) gives a homogeneous quadratic equation in and :
where
We have 7 such equations for the 7 different values of modulo the interchanges of i and j or k and l:
(i,j,k,l) |
(4, 2, 3, 3) |
(4, 1, 3, 2) |
(4, 0, 3, 1) |
(4, 0, 2, 2) |
(3, 1, 2, 2) |
(3, 0, 2, 1) |
(2, 0, 1, 1) |
These 7 quadratic equations can be written in the following matrix form:
This overdetermined system can be viewed as linear in , and , and solved by SVD as the right singular vector of the smallest singular value of . It is clear that these 7 equations are linearly but not algebraically independent. The constraints are the algebraic conditions for , to be a geometric series.
Given the null vector , we solve for
After obtaining the ratio , and can be determined using one of the scalar equations of the solution (4),
Therefore is completely determined. The final x is taken to be
or the average of all these values. Since , the final positive depth is .
Hence, the pose of the calibrated camera is uniquely determined by 4 point correspondences provided that the 4 reference points together with the perspective center of the camera do not lie in a critical configuration. The unique solution can be estimated by the linear 4-point algorithm.