Minimization of the @math norm, which can be viewed as approximately solving the non-convex least median estimation problem, is a powerful method for outlier removal and hence robust regression. However, current techniques for solving the problem at the heart of @math norm minimization are slow, and therefore cannot scale to large problems. A new method for the minimization of the @math norm is presented here, which provides a speedup of multiple orders of magnitude for data with high dimension. This method, termed Fast @math Minimization, allows robust regression to be applied to a class of problems which were previously inaccessible. It is shown how the @math norm minimization problem can be broken up into smaller sub-problems, which can then be solved extremely efficiently. Experimental results demonstrate the radical reduction in computation time, along with robustness against large numbers of outliers in a few model-fitting problems.
We investigate the use of the L∞ cost function in geometric vision problems. This cost function measures the maximum of a set of model-fitting errors, rather than the sumof-squares, or L2 cost function that is commonly used (in least-squares fitting). We investigate its use in two problems; multiview triangulation and motion recovery from omnidirectionalcameras, though the results may also apply to other related problems. It is shown that for these problems the L∞ cost function is significantly simpler than the L2 cost. In particular L∞ minimization involvesfinding the minimum of a cost function with a single local (and hence global)minimumon a convexparameter domain. Theproblem may be recast as a constrained minimization problem and solved using commonly available software. The optimal solution was reliably achieved on problems of small dimension. In this paper we consider the problem of outlier removal for large scale multiview reconstruction problems. An efficient and very popular method for this task is RANSAC. However, as RANSAC only works on a subset of the images, mismatches in longer point tracks may go undetected. To deal with this problem we would like to have, as a post processing step to RANSAC, a method that works on the entire (or a larger) part of the sequence. In this paper we consider two algorithms for doing this. The first one is related to a method by Sim & Hartley where a quasiconvex problem is solved repeatedly and the error residuals with the largest error is removed. Instead of solving a quasiconvex problem in each step we show that it is enough to solve a single LP or SOCP which yields a significant speedup. Using duality we show that the same theoretical result holds for our method. The second algorithm is a faster version of the first, and it is related to the popular method of L 1 -optimization. While it is faster and works very well in practice, there is no theoretical guarantee of success. We show that these two methods are related through duality, and evaluate the methods on a number of data sets with promising results.1