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. In this paper, we will consider L ∞ optimization problems related to one-view or two-view geometry; in particular we will focus on two problems, the pose problem and the relative pose problem. The pose problem is as follows. Given a set of 3D points with known position, and corresponding 2D image points, determine the location and pose of the camera. A little more formally: given 3D points X i and corresponding image points, v i , determine the camera matrix P such that v i = PX i for all i. An algebraic solution to this problem is given by the DLT algorithm ([3], chapter 7). The relative pose (or relative orientation) problem is to find the relative pose of two cameras, given a set of image correspondences, determined by unknown 3D points. Often the solution to this problem involves finding the positions of the 3D points as well. In other words, given image correspondences v i ↔ v i , find two camera matrices P and P , along with 3D points X i , such that v i = PX i and v i = P X i . This is the problem often solved by comput- * NICTA is funded by the Australian Government's Backing Australia's Ability initiative, in part through the Australian Research Council. ing the fundamental or essential matrix; a commonly used algorithm is the 8-point algorithm ([6] or [3], chapter 11). In the case where there is noise in the measurements, there is of course no exact solution to these problems, and generally it is considered optimal to find a solution to these problems that minimizes image error, namely the difference between the measured and modelled image points. The difference between the measured and modelled image measurements may be represented by a vector with one coordinate for each image measurement. The L 2 solution to the problem minimizes the L 2 norm of this error vector, namely the sum of squares of the image-measurement errors. The L ∞ solution, considered in this paper minimizes the L ∞ norm of the error vector, that is, it minimizes the maximum error, and is also called the minimax solution to the problem. To this point, there has been no known efficient optimal solution to these problems. Solutions have been given in [7] for the pose problem, but the solution we give here is considerably faster. No optimal solution has been reported for the relative pose problem. Optimal L ∞ solutions are given in this paper for both problems and the algorithms are efficient and fast. This paper extends the class of problems that can be solved globally with the L ∞ -norm. The class already includes problems like multiview triangulation, uncalibrated camera pose, homography estimation and structure from motion with a reference plane and more, see [4, 5] . In recent years there have been many attempts to compute globally optimal solutions for various geometric reconstruction problems. Using the L ∞ -norm framework has perhaps been the most successful one, but other approaches include [1] and [4]. The former approach applies a branch and bound algorithm to compute L 1 -and L 2 -solutions for triangulation and uncalibrated pose and the latter one uses convex approximations for a set of geometric reconstruction problems, however, with no guarantee of optimality. 1 978-1-4244-1631-8/07/$25.00 ©2007 IEEE
Then, we show how a Branch and Bound (BnB) algorithm may be formulated for the computation of optimal rotation between views REF .
Global Optimization through Searching Rotation Space and Optimal Estimation of the Essential Matrix
2007 IEEE 11th International Conference on Computer Vision
2007 IEEE 11th International Conference on Computer Vision
Computer Science