Two-Stage Outlier Elimination for Robust Curve and Surface Fitting

An outlier elimination algorithm for curve/surface fitting is proposed. This two-stage hybrid algorithm employs a proximity-based outlier detection algorithm, followed by a model-based one. First, a proximity graph is generated. Depending on the use of a hard/soft threshold of the connectivity of observations, two algorithms are developed, one graph-component-based and the other eigenspace-based. Second, a model-based algorithm, taking the classification of inliers/outliers of the first stage as its initial state, iteratively refits and retests the observations with respect to the curve/surface model until convergence. These two stages compensate for each other so that outliers of various types can be eliminated with a reasonable amount of computation. Compared to other algorithms, this hybrid algorithm considerably improves the robustness of ellipse/ellipsoid fitting for scenarios with large portions of outliers and high levels of inlier noise, as demonstrated by extensive simulations.