Departamento de Computación

El ajuste de formas geométricas es un problema importante en Visión por Computadora que tiene aplicación en muchos campos de la ciencia y la ingeniería, principalmente en aquellos donde es necesario extraer y analizar información útil de una imagen observada, de un conjunto de imágenes o de una secuencia de éstas. Cuando se trabaja con imágenes reales es muy común encontrar puntos atípicos en ellas. Éste tipo de puntos se encuentran en total desacuerdo con el modelo presentado inicialmente, afectando considerablemente el proceso de ajuste de la forma geométrica que se desea extraer. El propósito de esta tesis es realizar un método de ajuste robusto que utilice la minimización de la suma de las distancias perpendiculares. El método debe ser capaz de extraer varias de formas geométricas (líneas, círculos, elipses, triángulos y cuadriláteros) presentes en un mismo conjunto de puntos. El método propuesto aborda un problema de ajuste no lineal que se resolvió utilizando la meta heurística llamada evolución diferencial. Se compararon los resultados obtenidos contra la heurística más representativa de la literatura (MMC + RANSAC), la cual utiliza la minimización de la mediana de las distancias cuadráticas (MMC) complementado con una técnica de muestreo aleatorio (RANSAC), con la finalidad de demostrar que se ha conseguido un algoritmo de ajuste que proporciona un punto de ruptura de más del 50 %, v.g., que es capaz de extraer las formas geométricas propuestas aún cuando el conjunto de puntos conocidos contenga más del 50% de puntos atípicos.

Abstract

The fitting of geometrical forms is an important task in Computer Vision that has applications in many fields within science and engineering, especially in those in which is necessary to extract relevant information from an observed images, a set of image or a sequence of them. When working with real images is very common to find outliers in them. These points are in total disagreement with the initial model significantly affecting the fitting of the shape that we want to extract. The aim of this thesis is to propose a robust fitting method based on the minimization of the sum of orthogonal distances. The method should be able to extract several geometric shapes (lines, circles, ellipses, triangles and quadrilaterals) present in the same set of points. The proposed method deals with a non-linear fitting problem that was solved using a metaheuristic called differential evolution. Results were compared against the most representative heuristic (LMS + RANSAC). This heuristic uses the least median of squares (LMS) supplemented with a random sampling technique (RANSAC), in order to show that we have achieved a fitting algorithm with a break point over 50 %, i.e., it can extract the proposed geometric shapes even when the known set of points contains more than 50% of outliers.