Resumen

Uno de los problemas clásicos del área de Visión por Computadora es la reconstrucción tridimensional métrica a partir de imágenes adquiridas por una cámara sin calibración previa. Este problema involucra, específicamente, los siguientes pasos:(1) la triangulación, (2) la calibración de la cámara y (3) la estimación de los parámetros de orientación y posición de la cámara. El paso (1), la triangulación, tiene por objetivo encontrar la posición de un punto en el espacio a partir de la intersección de dos líneas que parten de la correspondencia de puntos en dos imágenes. Con la presencia de ruido, es muy probable que esta intersección no ocurra. En tal caso es necesario encontrar la mejor aproximación. Este problema es crítico en las reconstrucciones afín y proyectiva, donde no hay definida una métrica. En esta tesis se planteó la triangulación como un problema de optimización multi-objetivo, el cual se resolvió mediante un algoritmo evolutivo llamado NSGA-II. La transformación a un problema multi-objetivo permitió obtener mejores resultados en comparación con los mejores métodos reportados.

Los pasos (2) y (3) consisten en encontrar los parámetros de la cámara (parámetros de calibración, orientación y posición) a partir de un conjunto de correspondencias de puntos extraídas de dos o más imágenes. Sin embargo, existen superficies y configuraciones de la cámara conocidas como críticas donde se ha demostrado que es imposible extraer los parámetros de la cámara al usar, solamente, correspondencias de puntos. En esta tesis se proponen tres soluciones que plantean a la calibración de la cámara, a la estimación de los parámetros de orientación y posición, y al cálculo de los puntos tridimensionales (triangulación), como un problema de optimización, con base en el modelo de la cámara oscura, y emplean un algoritmo evolutivo llamado evolución diferencial para su resolución. Al emplear, directamente, el modelo de la cámara oscura es posible encontrar los parámetros de la cámara y obtener la reconstrucción tridimensional, aún en la configuración crítica de translación pura y en superficies críticas (puntos que yacen sobre un mismo plano).

Otro problema importante dentro del área de Visión por Computadora, consiste en obtener la elipse que mejor se ajuste a un conjunto de puntos dado. Los algoritmos que resuelven este problema sólo minimizan el cuadrado de la distancia euclidiana entre la cónica y los puntos mediante métodos de gradiente, aunque no siempre convergen a la solución óptima. En esta tesis se planteó el ajuste de puntos a una elipse como un problema de optimización, el cual fue resuelto mediante un algoritmo genético y la evolución diferencial. Esta solución tiene la flexibilidad de minimizar la distancia euclidiana o su cuadrado. Al emplear la distancia euclidiana se les da mayor peso a los puntos más cercanos, a diferencia de su cuadrado, en el cual se da mayor peso a los puntos más lejanos como se observa en los resultados.

A classic problem for Computer Vision is the three-dimensional metric reconstruction from two uncalibrated views. This problem entails the following steps: (1) triangulation, (2) camera calibration and (3) estimation of orientation and position parameters of each view. Step (1), triangulation, consists of finding the position of a point in real space as the intersection of two rays given by their corresponding images. When noise is present, the intersection of two rays may not be detected, in which case it is necessary to find the best approximation to the meet point. This problem is critical in affine and projective reconstruction, since no metric is present. In this thesis, we have proposed a solution that transforms the triangulation problem into multi-objective optimization problem, which was solved using an evolutionary algorithm called NSGA-II. The treatment as a multi-objective problem has been able to obtain better results compared with the best reported methods.

Steps (2) and (3) consist on estimating the camera parameters (calibration, orientation and position parameters) using a set of corresponding points extracted from two or more images. However, there are critical surfaces and critical camera configurations where it is not possible to recover these parameters using just the set of corresponding points. In this thesis we have proposed three solutions dealing with the camera calibration, the estimation of the orientation and position parameters of each view, and the calculation of the three-dimensional points (triangulation), all of them were merged into a general optimization problem based on the pinhole camera model and solved with an evolutionary algorithm, called differential evolution. This makes possible to estimate the camera parameters and obtaining thus the three-dimensional isometric reconstruction, even on critical camera configuration (pure translation) and critical surfaces (points lie on the same plane).

We also applied successfully evolutionary algorithms within another Computer Vision problem: ellipse fitting. The problem consists of finding the best ellipse fitting a set of given points. The current algorithms minimize the square of Euclidean distance between the conic and the set of given points through gradient methods. However, such methods do not always converge to the optimal solution. In this thesis our approach based on genetic algorithm and differential evolution were successful, minimizing the Euclidean distance or its square. With the Euclidean distance, the nearest points get greater weight, instead the squared Euclidean distance gives greater weights to distant points.