Learning to Solve Hard Minimal Problems

We present an approach to solving hard geometric optimization problems in the RANSAC framework. The hard minimal problems arise from relaxing the original geometric optimization problem into a minimal problem with many spurious solutions. Our approach avoids computing large numbers of spurious solutions. We design a learning strategy for selecting a starting problem-solution pair that can be numerically continued to the problem and the solution of interest. We demonstrate our approach by developing a RANSAC solver for the problem of computing the relative pose of three calibrated cameras, via a minimal relaxation using four points in each view. On average, we can solve a single problem in under 70 µs. We also benchmark and study our engineering choices on the very familiar problem of computing the relative pose of two calibrated cameras, via the minimal case of five points in two views. Motivation Many geometrical problems are optimization problems that have only one optimal solution. Minimal problems, however, often have many additional spurious solutions. The optimal solution is typically real, satisfies inequality constraints, and fits well all data. Such constraints, however, can not be used by methods of nonlinear algebra [13, 65] which have no ability to bypass finding (or incurring the cost of finding) all solutions of polynomial systems. RANSAC [23, 53] approximates the optimal solution to a geometrical problem by computing candidate solutions from data samples and picking a solution with maximal data support. This is done by iterating over the samples in an outer loop and over the solutions of a minimal problem for each sample in an inner loop. To find a single solution for a data sample in the inner loop, the state-of-the-art "solve & pick" approach first computes all solutions of a minimal problem and then picks the optimal solutions by removing nonreal solutions, using inequalities, and evaluating the support. Optimization in the inner loop may be very costly when there are many spurious solutions to the minimal problem. Fig. 1 compares the standard "solve & pick" approach with our "pick & solve" approach that learns, for a given data sample, how to first pick a promising starting point and then (ideally) continue it to a meaningful solution.