Non-linear least squares ellipse fitting using the genetic algorithm with applications to strain analysis

Abstract

Several methods of strain estimation require the best-fit ellipse through a set of points either for defining elliptical shapes of distorted objects, and/or for tracing the finite strain ellipse. Fitting an ellipse to scattered points by solving a least squares problem can involve a linear as well as non-linear formulation. This article outlines both approaches and their relative merits and limitations and, proposes a simple yet powerful non-linear method of solution utilizing the genetic algorithm. Algebraic methods solve the linear least squares problem, and are relatively straightforward and fast. However, depending upon the type of constraints used, different algebraic methods will yield somewhat different results. More importantly, algebraic methods have an inherent curvature bias-data corrupted by the same amount of noise will misfit unequally at different curvatures. The genetic algorithm method we propose uses geometric as opposed to algebraic fitting. This is computationally more intensive, but it provides scope for placing visually apparent constraints on ellipse parameter estimation and is free from curvature bias. Algebraic and geometric approaches are compared critically with the help of a few synthetic and natural examples for strain estimation in rocks. The genetic algorithm almost always produces results with lower misfit when dealing with noisy data and more importantly, yields closer estimates to the true values.