Finding relative pose between two calibrated images is a fundamental task in computer vision. Given five point correspondences, the classical five-point methods can be used to calculate the essential matrix efficiently. For the case of <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq1-3030161.gif"/></alternatives></inline-formula> (<inline-formula><tex-math notation="LaTeX">$N > 5$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>N</mml:mi><mml:mo>></mml:mo><mml:mn>5</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="zhao-ieq2-3030161.gif"/></alternatives></inline-formula>) inlier point correspondences, which is called <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq3-3030161.gif"/></alternatives></inline-formula>-point problem, existing methods are either inefficient or prone to local minima. In this paper, we propose a certifiably globally optimal and efficient solver for the <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq4-3030161.gif"/></alternatives></inline-formula>-point problem. First we formulate the problem as a quadratically constrained quadratic program (QCQP). Then a certifiably globally optimal solution to this problem is obtained by semidefinite relaxation. This allows us to obtain certifiably globally optimal solutions to the original non-convex QCQPs in polynomial time. The theoretical guarantees of the semidefinite relaxation are also provided, including tightness and local stability. To deal with outliers, we propose a robust <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq5-3030161.gif"/></alternatives></inline-formula>-point method using M-estimators. Though global optimality cannot be guaranteed for the overall robust framework, the proposed robust <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq6-3030161.gif"/></alternatives></inline-formula>-point method can achieve good performance when the outlier ratio is not high. Extensive experiments on synthetic and real-world datasets demonstrated that our <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq7-3030161.gif"/></alternatives></inline-formula>-point method is <inline-formula><tex-math notation="LaTeX">$2\sim 3$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>2</mml:mn><mml:mo>∼</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="zhao-ieq8-3030161.gif"/></alternatives></inline-formula> orders of magnitude faster than state-of-the-art methods. Moreover, our robust <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="zhao-ieq9-3030161.gif"/></alternatives></inline-formula>-point method outperforms state-of-the-art methods in terms of robustness and accuracy.
Paper
References (72)
Scroll for more · 38 remaining