Numerically Stable Direct Least Squares Fitting of Ellipses

Abstract

This paper presents a numerically stable non-iterative algorithm for fitting an ellipse to a set of data points. The approach is based on a least squares minimization and it guarantees an ellipse-specific solution even for scattered or noisy data. The optimal solution is computed directly, no iterations are required. This leads to a simple, stable and robust fitting method which can be easily implemented. The proposed algorithm has no computational ambiguity and it is able to fit more than 100,000 points in a second. Keywords: ellipses, fitting, least squares, eigenvectors INTRODUCTION One of basic tasks in pattern recognition and computer vision is a fitting of geometric primitives to a set of points (see [Duda73] for a summary). The use of primitive models allows reduction and simplification of data and, consequently, faster and simpler processing. A very important primitive is an ellipse, which, being a perspective projection of a circle, is exploited in many applications of ...