A Study Of Algorithms For Fitting Multiple Ellipses

There are many methods used for ellipse fitting, e.g., direct least squares, least median of squares, Kalman filter, etc. However, all of these methods have drawback, either sensitive to noises and outliers, or unable to make an objective evaluation to the fitting results. Xia Jing proposed HEFA (hybrid ellipse fitting algorithm) to overcome these shortcomings. The HEFA is designed mainly for fitting a single ellipse. As the cases of multiple ellipses, such as multiple ellipses either disjoint or intersect to each other, or concentric and so on, are frequently encountered in application, the HEFA is needed to extend for multiple ellipse fitting.To extend the HEFA, it is required to solve the problems of detection, extraction, fitting and separation of the data concerned. For detecting and extracting the initial data, boundary tracking is first used to extract the contour of ellipses, corners at the contour are detected to get the data of an arc segment limited by a pair of corners. Then, the data is fitted using the HEFA and is deleted to separate the fitted ellipse from the original data.The concentric ellipse fitting not only needs to fit them, but also to ensure that they share the same center, same rotation angle and same ratio of long axis to short axis. To meet these requirements, this thesis proposes a novel fitting method based on the global searching technique. The constraint relation is first presented in mathematic form. Then global search starts to get the ratio between ellipses based on least squares fitting theory until the value of ratio and the parameters of the corresponding ellipses are obtained.Experimental results show that both the extended HEFA and the new method of concentric ellipse fitting can make a fast and accurate job.