Direct least absolute deviation fitting of ellipses (Q782223)

Summary: 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 \(\ell_1\) algebraic distance is presented. Unlike the conventional \(\ell_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 \(\ell_1\) optimization problem, according to which the computational burden is significantly reduced. Furthermore, two classes of \(\ell_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 \(\ell_2\) counterpart and outperforms some of the state-of-the-art algorithms for both Gaussian and non-Gaussian artifacts.