《2016 Global Optimization through Rotation Space Search》.pdf

Int J Comput Vis (2009) 82: 64–79 DOI 10.1007/s11263-008-0186-9 Global Optimization through Rotation Space Search Richard I. Hartley · Fredrik Kahl Received: 26 April 2008 / Accepted: 9 October 2008 / Published online: 7 January 2009 © Springer Science+Business Media, LLC 2009 Abstract This paper introduces a new algorithmic tech- 1 Introduction nique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and- In this paper, we will consider L∞ optimization problems bound search over rotation space, which is used in this pa- related to one-view or two-view geometry; in particular we per to determine camera orientation. By searching over all will focus on two problems, the pose problem and the rel- possible rotations, problems can be reduced to known fixed- ative pose problem. Optimal (minimum cost) solutions will rotation problems for which optimal solutions have been be given to these problems under the geometrically mean- previously given. In particular, a method is developed for the ingful L∞ cost function. Although these problems have estimation of the essential matrix, giving the first guaranteed been well studied in the past, no previous solutions have claimed optimality under any sort of meaningful geometric optimal algorithm for estimating the relative pose using a error model. cost function based on reprojection errors. Recently convex The pose problem is as follows. Given a set of 3D points optimization techniques have been shown to provide optimal