An efficient and globally optimal solution to perspective-n-line problem

This research develops an accurate and efficient method for the Perspective-n-Line (PnL) problem. The developed method addresses and solves PnL via exploiting the problem's geometry in a non-linear least squares fashion. Specifically, by representing the rotation matrix with a novel quaternion parameterization, the PnL problem is first decomposed into four independent subproblems. Then, each subproblem is reformulated as an unconstrained minimization problem, in which the Kronecker product is adopted to write the cost function in a more compact form. Finally, the Gröbner basis technique is used to solve the polynomial system derived from the first-order optimality conditions of the cost function. Moreover, a novel strategy is presented to improve the efficiency of the algorithm. It is improved by exploiting structure information embedded in the rotation parameterization to accelerate the computing of coefficient matrix of a cost function. Experiments on synthetic data and real images show that the developed method is comparable to or better than state-of-the-art methods in accuracy, but with reduced computational requirements.