Global Optimization to Fundamental Matrix Estimation

Perspective fundamental matrix estimation from point correspondences is one of the most essential tasks in computer vision. The result by minimizing an algebraic error is usually highly biased and very sensitive to noise. In contrast, the geometric reprojection error, also known as the 'gold standard', is statistically optimal, but hard to minimize. The Sampson error and the Point-to-Epipolar-Line distance (P2ELD) are more tractable, but still highly nonconvex. 

Our objective is to develop a global optimization method for the Sampson error and P2ELD minimization by using branch-and-bound techniques, and figure out whether existing local search methods suffer from local minimum or not. We take full advantage of the problem structure so as to solve the problem with reasonable computation cost. Systematic performance evaluation also provides us some guidelines in choosing a proper algorithm to best balance between efficiency and accuracy. 

The branch-and-bound technique is a general global optimization technique for nonconvex optimization problem. Due to its exponential complexity, however, it is usually intractable for a practical problem, except that the problem structure is carefully investigated and properly utilized. The following figure illustrates the basic idea of branch-and-bound in 1D case.

We have noted that the Sampson error and the P2ELD arsing from fundamental matrix estimation assume a special rational fractional structure, which enables us to branch in a fixed 9D hyper space, irrespective of the number of point correspondences. Each relaxation subproblem in the bounding process is a second order cone program, which could be easily and efficiently solved by using an off-the-shelf interior point solver. 

Interval Contraction
Tight variable bounds are essential for the efficiency of a branch-and-bound based algorithm. Unfortunately, for fundamental matrix estimation, the initial variable bounds are derived from the plain 9-parameter parameterization with a unit norm constraint accounting for absolute scale ambiguity. We introduce a variable interval contraction technique, so as to shrink the interval as much as possible by using the best upper bound in a bounding step. 

Through systematic evaluation, we have empirically found that existing local optimization algorithms indeed suffer from local optimum or even divergence, when starting from the solution of the popular eight point algorithm. The following figure illustrate the non-global-optimal solutions from existing extended fundamental numerical scheme (EFNS) and constrained  Levenberg-Marquette (CLM) algorithms for one image pair from the Dinosaur sequence.