Direct Least Absolute Deviation Fitting of Ellipses

Abstract EN

Scattered data from edge detection usually involve undesired noise which seriously affects the accuracy of ellipse fitting.

In order to alleviate this kind of degradation, a method of direct least absolute deviation ellipse fitting by minimizing the ℓ1 algebraic distance is presented.

Unlike the conventional ℓ2 estimators which tend to produce a satisfied performance on ideal and Gaussian noise data, while do a poor job for non-Gaussian outliers, the proposed method shows very competitive results for non-Gaussian noise.

In addition, an efficient numerical algorithm based on the split Bregman iteration is developed to solve the resulting ℓ1 optimization problem, according to which the computational burden is significantly reduced.

Furthermore, two classes of ℓ2 solutions are introduced as the initial guess, and the selection of algorithm parameters is studied in detail; thus, it does not suffer from the convergence issues due to poor initialization which is a common drawback existing in iterative-based approaches.

Numerical experiments reveal that the proposed method is superior to its ℓ2 counterpart and outperforms some of the state-of-the-art algorithms for both Gaussian and non-Gaussian artifacts.