Departamento de Computación

El problema de ajuste de elipses consiste en encontrar la mejor elipse que se ajusta a un conjunto de puntos, éste es un problema que surge en diversas áreas, por ejemplo en visión computacional, Robótica, detección de rostros, Astronomía, entre otras. En esta tesis, nosotros usamos un algoritmo genético para la detección y ajuste de múltiples elipses que están dadas implícitamente por un conjunto de datos que contiene ruido. El objetivo general es detectar rápidamente todo el conjunto de elipses, sin información adicional sobre el tamaño y forma de las elipses, o la cantidad de ruido en el conjunto de datos, pero conociendo el número de elipses y proporcionando un valor de umbral. En este trabajo, nosotros desarrollamos e investigamos - basados en un algoritmo genético estándar - tres diferentes funciones de aptitud que tenían diferentes ventajas y desventajas. A partir de los resultados numéricos, verificamos que estamos en condiciones de calcular de manera fiable y eficiente el conjunto de elipses en ciertas situaciones.

Abstract

The problem of ellipse fitting consists of finding the best fit ellipse to a set of points, it is a problem that arises in many areas, e.g. Computer Vision, Robotics, Face Detection, Astronomy, among others. In this thesis, we use a genetic algorithm for the detection and fitting of multiple ellipses which are implicitly given by a data set which contains noisy data. The overall aim is to quickly detect the entire set of ellipses, without additional information about the sizes, and shapes of the ellipses, or the amount of noise in the data set, but knowing the number of ellipses and providing a threshold value. In this work, we develop and investigate - based on a standard genetic algorithm - three different fitness functions which have different advantages and disadvantages. From numerical results we verify that we are yet able to reliably and efficiently compute the set of ellipses in certain situations.