Departamento de Computación

En vision por computadora, una homografía es la matriz que transforma los puntos de un plano a otro. En este trabajo estamos interesados en la detección automática de una o más homografas, esto es, detectar autométicamente los planos presentados en una, dos o varias imgenes, pero en un ambiente con puntos típicos, atípicos y con ruido. En nuestro problema, los puntos athípicos se pueden considerar como los puntos en otros planos, porque representan diferentes distribuciones de datos (u otros conjuntos de puntos de los diversos planos) y el ruido se puede observar, como puntos sobre las imgenes que no forman parte de los planos en la escena tomada (son datos que aparecen a menudo por error de medición). Para una detección robusta (esto es, a partir de un conjunto de datos que contienen puntos atípicos y con ruido), en el estado del arte, el algoritmo estandar más conocido para resolver este problema es el algoritmo de consenso de muestra aleatoria (RANSAC, por sus siglas en inglés). En dicho algoritmo, de todo el conjunto de datos de entrada, se toma un subconjunto de ellos al azar con el fin de estimar el modelo (en nuestro problema, una holografía). Si el error del modelo es mínimo, este es aceptado y el subconjunto de los puntos implicados se denomina conjunto de consenso. El modelo se estima con algoritmos lineales estándares (que también son los mas rápidos). Aquí el problema es cuántas veces el proceso descrito debe repetirse con el fin de obtener la mejor estimación del modelo. RANSAC tiene el inconveniente de establecer de antemano el número de iteraciones en el algoritmo. En este trabajo se probaron otros dos algoritmos: uno utiliza un algoritmo genético simple aplicado en la tarea de la detección automática de holografíaas para elegir el conjunto de consenso, en lugar de utilizar muestras al azar. El segundo algoritmo realizado utiliza la meta-heurística llamada evolución diferencial, para minimizar el error entre las correspondencias de puntos del conjunto de consenso, al mismo tiempo que se maximiza el número de dichas correspondencias. Se demuestra con experimentos de simulación e imágenes reales, la ventaja de utilizar los algoritmos propuestos en esta tesis, con los que se reduce casi 6 veces, en promedio, el número de iteraciones requeridas por el algoritmo original RANSAC.

Abstract

In computer vision, a homography is the matrix that transforms the points on a plane to another plane. In this work, we are interested in the automatic detection of one or more homographies, that is, we aim to automatically detect the planes submitted into one, two or several images, but in an environment with inliers, outliers and noise. In our problem, the inliers can be considered to be the points in other planes, because they represent diferent distributions of information (or other point sets of the diverse planes) and the noise can be observed as points on the images that do not form part of the planes in the taken scene (it is information that frequently appears due to measurement errors). For a robust detection (i. e., from a set points that contains outliers and noise), the state in the art algorithm to solve this problem is called RANdom SAmple Consensus (RANSAC). In such algorithm, the entire set of input data, takes a random subset of them to estimate the model (in our problem, a homography). If the error in the model is minimal, this model is accepted and the subset of the implied points is called the consensus set. The model is estimated with standard linear algorithms (which are also the fastest). The problem is to know how many times the described process must be repeated in order to obtain the best estimation of the model. RANSAC has the disadvantage of establishing in advance the number of iterations to be performed in the algorithm. In this work, two different algorithms were tested: first, a simple genetic algorithm was applied to obtain the sample points of the consensus set. The second approach adopts the metaheuristic called diferential evolution to minimize the error between the corresponding points, while also maximizing the number of points used to calculate the homography. It is empirically shown through a series of experiments and real images, that it is advantageous to use the algorithms proposed in this thesis. Using the designed algorithms we were able to obtain a reduction of about six times, on average, the number of iterations performed, with respect to the original RANSAC algorithm.