# 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] .