Global optimization through searching rotation space and optimal estimation of the essential matrix

This paper extends the set of problems for which a global solution can be found using modern optimization methods. In particular, the method is applied to estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose under a geometric cost function, in this case, the L-infinity cost function. Convex optimization techniques has been shown to provide optimal solutions to many of the common problems in stucture from motion. However, they do not apply to problems involving rotations. In this paper, we introduce a search method that allows such problems to be solved optimally. Apart from the essential matrix, the algorithm is applied to the camera pose problem, providing an optimal algorithm.