Perspective n Points problem for Pose Reconstruction

To reconstruct the object position related to the camera coordinate system, there are lots of method available to be applied. But one of the most popular way is linear perspective reconstruction. Of course it can be used to reconstruct the camera position in room CS, too. Up to the requirement.

In my case I have a object consisted of n markers, in the image "n=4", what I want is to reconstruct the position and orientation of the object related to the camera CS. And the linear PnP method is absolutely helpful for my needs. Professionally described, my problem is also called SPACE RESECTION . That is given a set of correspondences between 3D reference points and their image, determining the position and orientation of camera or object with respect to the known reference points. It's said one of the oldest and most important tasks in computer vision.

There are already numerous papers to introduce or describe the algorithms to solve this problem, specially for the one camera or single view situation. Most of them relay on either iterative methods or applying the closed-form solutions to minimal subsets of the redundant data. Definitely they have their own drawbacks and advantages respectively. But so far as I have read, the Linear N-point Camera Pose Determination method by Long Quan and Zhongdan Lan is the most proper and flexible tool to solve the pose reconstruction problem. And the mathematical model could be illustrated in image 2, the 3D object with n markers is projected onto the camera's sensor with m(m<=n) image points. And by their method the correspondence between the 3D markers and 2D points is already known. And the geometry of the object is also available like the distances between every two markers. And the camera can detect the position of those 2D image points with respect in camera CS, and the focal length of the camera we can use, too. wow, so many things, ne? And with next picture this problem can be explained better:

So what we should do is based on |AB|, |BC|, |CD|, |DA| and the parietal angles of every polyhedron's surface (with the help of focal length and position of the image points they are able to be calculated), achieve the length of the polyhedron's legs: a,b,c,d. And with the geometrical relationship of tetrahedron ABCL we can obtain the following equations:

And this system has 8 solutions. But if we eliminate the negative values we just have to face 4 choices. Using the classical Sylvester resultant, a, b or c could be expressed by a eighth degree polynomial(detailed explanation) like:

with x = a^2 ( or b^2, or c^2)

For n=4, an overconstrained system of 6 polynomials is obtained for the four unknowns a, b, c, d. And the straightforward approach is to take subsets of 3 of the four points solve the fourth degree polynomial equation for each subset of 3 points and at last every subset. For n points we have (n-1)(n-2)/2 fourth degree polynomials of type g(x)=0, and in my case n=4, so we have 3 fourth degree polynomials, written in matrix form:

And with SVD we could solve the vector t with parameterized null space as:

and for i+j = k+l, 0<=i,j,k,l<=4 we have this equation:

Substituting t from the equations we can achieve another equation:

And with the logical permutation of i+j = k+l, 0<=i,j,k,l<=4, we can obtain 7 such quadratic equations, written in matrix form:

and solved by SVD of B, we can absolutely get the solution of

so according to the equation above the vector t is able to be solved and the length of a, b, c, d are also obtained with the value t1/t0. So finally with the value of these values, the four markers' position could be uniquely determined. And based on these the location or the orientation of the object can be calculated, too. Likewise

the camera position is also able to be achieved.

Posted in: tracking technology,Virtual Reality