A New Robust Operator for Computer Vision: Theoretical Analysis

Charles V. Stewart

Department of Computer Science

Rensselaer Polytechnic Institute

Troy, New York 12180--3590

stewart@cs.rpi.edu

Abstract

MINPRAN, a new robust operator, finds good fits in data sets where more than 50% of the points are outliers. Unlike other techniques that handle large outlier percentages, MINPRAN does not rely on a known error bound for the good data. Instead it assumes that the bad data are randomly (uniformly) distributed within the dynamic range of the sensor. Based on this, MINPRAN uses random sampling to search for the fit and the number of inliers to the fit that are least likely to have occurred randomly. It runs in time , where is the number of random samples and is the number of data points. We demonstrate analytically that MINPRAN distinguishes good fits from fits to random data, and that MINPRAN finds accurate fits and nearly the correct number of inliers, regardless of the percentage of true inliers. MINPRAN's properties are confirmed experimentally on synthetic data and compare favorably to least median of squares. Related work applies MINPRAN to complex range and intensity data [TR93-24] .