Global Optimization through Rotation Space Search

被引:173
作者
Hartley, Richard I. [1 ,3 ]
Kahl, Fredrik [2 ]
机构
[1] Australian Natl Univ, Canberra, ACT, Australia
[2] Lund Univ, Ctr Math Sci, Lund, Sweden
[3] Natl ICT Australia, Canberra, ACT, Australia
基金
澳大利亚研究理事会;
关键词
Essential matrix; Branch-and-bound algorithm; Global optimization; MULTIPLE-VIEW GEOMETRY;
D O I
10.1007/s11263-008-0186-9
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper introduces a new algorithmic technique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and-bound search over rotation space, which is used in this paper to determine camera orientation. By searching over all possible rotations, problems can be reduced to known fixed-rotation problems for which optimal solutions have been previously given. In particular, a method is developed for the estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose using a cost function based on reprojection errors. Recently convex optimization techniques have been shown to provide optimal solutions to many of the common problems in structure from motion. However, they do not apply to problems involving rotations. The search method described in this paper 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. The approach has been implemented and tested on a number of both synthetically generated and real data sets with good performance.
引用
收藏
页码:64 / 79
页数:16
相关论文
共 16 条
[1]   Implementation techniques for geometric branch-and-bound matching methods [J].
Breuel, TM .
COMPUTER VISION AND IMAGE UNDERSTANDING, 2003, 90 (03) :258-294
[2]  
Hartley R, 2004, PROC CVPR IEEE, P504
[3]  
HARTLEY R, 2007, P INT C COMP VIS OCT
[4]  
Hartley R., 2003, Multiple view geometry in computer vision
[5]  
Hartley R, 2007, LECT NOTES COMPUT SC, V4843, P13
[6]  
Kahl F, 2005, IEEE I CONF COMP VIS, P1002
[7]   Multiple-view geometry under the L∞-norm [J].
Kahl, Fredrik ;
Hartley, Richard .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2008, 30 (09) :1603-1617
[8]   Practical global optimization for multiview geometry [J].
Kahl, Fredrik ;
Agarwal, Sameer ;
Chandraker, Manmohan Krishna ;
Kriegman, David ;
Belongie, Serge .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2008, 79 (03) :271-284
[9]   Globally optimal estimates for geometric reconstruction problems [J].
Kahl, Fredrik ;
Henrion, Didier .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2007, 74 (01) :3-15
[10]   Quasiconvex optimization for robust geometric reconstruction [J].
Ke, Qifa ;
Kanade, Takeo .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2007, 29 (10) :1834-1847