# An Accurate, Efficient, and Stable Perspective-n-Point Algorithm in 3D Space
### A Non-Iterative Approach to Optimally Solving PnP Problems  
Table 1 shows that scholars have used non-iterative methods to optimally solve the PnP problem in order to overcome the shortcomings of the iterative method. Firstly, the imaging model undergoes parameterization, simplification, and deformation to construct non-linear equations that can be used for optimization. Then, the Grobner technique (Figure 1) is adopted to solve the non-linear equations (see [20; 21] in detailed steps of Grobner tool), and the required pose parameters are obtained. The first non-iterative PnP algorithm is the EPnP algorithm [13], which takes four spatial virtual points as reference points and uses these four points to represent the reference points in the rest of the space, and, finally, obtains the pose information through optimization. The EPnP algorithm requires less computational time, compared with the iterative method. However, the linear method it uses leads to unsatisfactory computational accuracy and poor stability when there is noise and to fewer spatial redundant points. The DLS algorithm [14], also a non-iterative method, first introduces the CGR (Cayley-Gibbs-Rodriguez) parameterized rotation matrix, and uses the matrix decomposition technique to process the rotation matrix. The processed rotation matrix parameterizes the translation vector through the relation derivation of the imaging model equation, leaving only three unknown parameters in the whole solution process. Finally, the pose estimation problem is transformed into an unconstrained square minimization problem by constructing a cost function. The introduction of the CGR parameterized rotation matrix and the application of the matrix decomposition technique in the solution process may incur singular value and complex computation, which greatly affects the accuracy, speed, and stability of the final solution pose. Among the non-iterative methods, the RPnP algorithm [15], which is different to the DLS algorithm, can be generally regarded as a phased solution method. First, the PnP problem is transformed into the P3P problem, that is, the spatial reference points are divided into groups of three, so as to obtain polynomial sets with the highest order of fourth. Then, the fourth-order polynomial sets, also non-linear equations, are transformed into linear equations through the linearization technique. Finally, the required pose parameters are obtained by solving the polynomial sets. The whole solution process of RPnP, though being a progressive and cohesive strategy, introduces linearization technology and adopts the non-global optimization method, which explains its fast computational speed, but less favorable stability and accuracy. In addition, some PnP algorithms not only absorb the advantages of iterative methods, but also overcome their proneness to local optimum, including the ASPnP algorithm [16] and the OPnP [17] algorithm. Both of the aforementioned algorithms introduce the quaternion to represent the rotation matrix, express the translation matrix by the quaternion parameters through the imaging model equation, and directly construct the objective function for global optimization by means of such mathematical skills as rewriting the matrix form and introducing new variables. What merits attention, is that the method employs the Grobner technique, instead of the Gauss-Newton method commonly used in the iterative method, to avoid local optimum when solving the third-order polynomial sets of the objective function. Nevertheless, the above two PnP algorithms construct a large elimination template matrix when using the Grobner technique, which increases computational burden. Some scholars have made continuous efforts to improve existing PnP algorithms. For example, [PERSON] et al. proposed the UPnP in 2014 [18], and [PERSON] proposed the opt-DLS [19] PnP algorithm in 2015, both of which improved the OPnP algorithm. Specifically, the UPnP algorithm applies to PnP problems under the perspective imaging model and those under the General Camera Model.