Improved Ellipse Fitting Algorithm with Outlier Removal

Abstract

The results of ellipse fitting can be considerably distorted by outliers in the fitted point set.To tackle this problem, three improved ellipse fitting algorithms, one of which is based on least trimmed square, and the other two on dual point removal, are proposed.The least trimmed square algorithm starts from a random sample of the original complete fitted set, and then in each iteration, new fitted set is formed by points with the least residual errors, till the process converges to an ellipse fitting a subset whose members are mostly non-outliers.Dual point removal algorithms, on the other hand, starts from the whole fitted set, removes the two points respectively with the maximal positive and the minimal negative residual errors, and halts when the number of points in the remaining set does not exceeds a user-defined threshold.The two proposed algorithms and existing methods are compared on an image base of actual accessories.Experimental results show that when the number of reserved ellipse points is relatively small, the dual removal-based algorithms present the best fitting accuracies, but are slower than the least trimmed square fitting algorithm.When the best performance with parameter tuning is concerned, however, the least trimmed square algorithm achieves a shape-location matching accuracy of 0.62 pixels and an orientation matching accuracy of 0.6°, at an average execution time of 6.5ms, outperforming other algorithms.Other advantages of the proposed algorithms include the small number of algorithm parameters, the intuitiveness of the parameters, and the insensitivity of the algorithm performance to the parameters.These experimental results provide solid evidences for the effectiveness of the proposed algorithms, especially the least trimmed square algorithm.

Keywords

• ellipse fitting|ellipse detection|least trimmed square|dual point removal|vision-based measurement