Globally Optimal Camera Orientation Estimation from Line Correspondences by BnB algorithm

Abstract

This letter is concerned with the problem of estimating camera orientation from a set of 2D/3D line correspondences, which is a major part of the Perspective-n-Line (PnL) problem. There are some cases that usually occur in real applications for PnL: the input line correspondences are corrupted by mismatches (a.k.a. outlier correspondences). The RANdom SAmple Consensus (RANSAC) algorithm is the de facto standard for solving outlier-contaminated PnL problems. However, RANSAC is a non-deterministic algorithm, which means that it produces a reasonable result only with a certain probability. Therefore, a PnL algorithm that could obtain a certifiably optimal solution from outlier-contaminated data is a matter of priority for some safety-critical applications. In this letter, we take a big step towards this goal by investigating globally optimal camera orientation estimation algorithms. Firstly, we decouple the rotation and translation estimation of a PnL problem by considering the geometrical property of the PnL problem. The Branch-and-Bound (BnB) algorithm is applied and it globally searches the entire rotation space to obtain the optimal camera orientation. To investigate the performance of our method, we tested the proposed algorithm on both synthetic and real data, and the results show that our algorithms can obtain the optimal camera orientation and are more robust than several state-of-the-art PnL methods.