Let me start with the definition of the problem. We know the reference points of 3D coordinates in the world coordinate system and the 2D coordinates of the corresponding image projection points.

In EPnP scheme, the camera coordinates of reference points are expressed as the weighted sum of control points, and then the problem is transformed into the solution of camera coordinates of these four control points. For non-planar cases, four non-planar control points are needed, while for planar cases, only three are needed.

The marked point is in the world coordinate system.

The marked point is in the camera coordinate system.

All,, and are not homogeneous coordinates.

How to choose control points will be discussed later. Suppose we have selected four control points.

EPnP also adopts this similar representation method, and uses the weighted sum of four control points to represent the reference point. In the world coordinate system, we can get:

Then the reference point in the camera coordinate system can be written as:

Why do you need 4 control points?

Assuming that three control points meet the requirements, then

A * * * has three unknowns and four equations. When the number of equations is greater than the number of unknowns, it is called overdetermined equation. There is only a solution in the sense of least squares. That is to say, in general, there is no solution that completely satisfies the four equations.

How to solve it?

Theoretically, the choice of control points is not too particular, as long as it is reversible. However, the author found in the experiment that the stability of the algorithm will increase when one of the reference points is set as the center of mass. This is meaningful to some extent, because the use of the center of mass makes the data normalized in the coordinate system.

First calculate the first control point:

The other three points are calculated by PCA, and the covariance matrix is calculated first:

So, the covariance matrix is.

Remember that the eigenvalue is and the corresponding eigenvector is, then the remaining three control points can be determined according to the following formula:

Let the known camera internal parameter matrix be 2D projection on the image coordinate system, then

Two linear equations can be obtained from the above:

The matrix obtained by taking the coefficients of the formula together is the coordinates of the control points in the camera coordinate system.

It can be obtained after finishing.

Obviously in the right null space, or, it can be expressed as:

The right singular vector can be obtained by singular value decomposition of m, but it takes a long time. At present, SVD scheme with the lowest time complexity is.

Might as well change our thinking, we can solve it faster by solving the eigenvector corresponding to the eigenvalue of 0. Computing matrix is the most time-consuming step in EPnP, and its time complexity is.

In the camera coordinate system, for the i-th control point,

Next, it is to seek answers.

According to the quantity, there are different ways to solve the problem. Is the dimension of matrix null space. Through the simulation experiment, the author found that it is related to the focal length of the camera.

Fill a loophole

It can be observed that all singular values tend to zero from the fifth order. Because there is some noise during the experiment, it is not zero strictly.

The vertical axis of the two graphs represents the proportion based on 300 groups of experiments.

Left: Gaussian noise is added to the same picture, and the horizontal axis represents different number of point pairs.

Right: Six pairs of matching points are fixed on the same picture. The horizontal axis represent different degrees of Gaussian noise.

Basically, the evaluation rate is higher.

I still can't understand the original text. Fill in this hole later.

The author of EPnP suggests only considering the situation. After confirmation, we can solve it through the following constraints:

The above formula means that the external parameters of the camera only describe the transformation of the coordinate system and will not change the distance between points. By, we can get:

For four control points, we can get an equation like this. Next, according to the different values of, solve.

A * * * has 1 unknowns, which can be directly calculated.

A * * * has three unknowns.

Write the above formula, because the unknown number is less than the number of equations, and solve it with pseudo-inverse:

A * * * has six unknowns and six equations. inversion

A * * * has 10 unknowns, but only six equations. Here we find a problem, and we only have these four unknowns. Note that this is a linear term. But after the formula is expanded, it is full of quadratic terms.

This paper adopts re-linearization, and the specific steps are as follows:

The author does not suggest directly selecting values, but calculates all four values and chooses the value with the smallest re-projection error.

Where is the 2D distance of homogeneous point.

The specific process can be seen in my other article: ICP algorithm.

To use EPnP in practice, the number of matching points should be greater than 15.