Removing Outliers Using The Linfty Norm

Recently, there has been interest in solving geometric vision problems such as triangulation and camera resectioning using Linfty minimization. One key advantage of using the Linfty norm rather than the L2 norm is that the Linfty cost function has a single minimum unlike the commonly used L2 cost function which typically has multiple local minima. However, one drawback of using Linfty minimization is that it is not robust to outliers. By minimizing the Linfty norm instead of the L2 norm, we are, in essence, fitting the outliers and not the good data. Therefore, before one can perform Linfty optimization on a problem, it is first necessary to remove outliers. A popular (but generally unsound) method of removing outliers is to minimize the cost function using standard optimization techniques; then if the residual error is too great, remove the offending measurements and continue. Although this method can fail for simple L2 optimization problems, we show in this paper that for a wide class of Linfty problems it is a valid technique. It is proved that the set of measurements with greatest residual must contain at least one outlier. Thus, if we keep throwing out the measurements with greatest residual, we will eventually remove all outliers in the data. We test this hypothesis on the multiview reconstruction problem and show that even simple strategies for throwing out these maximum residual measurements are effective in removing outliers.