Visual odometry and mapping using stereo vision and registration algorithms

Abstract

Esta tesis propone un sistema completo de odometría visual utilizando únicamente Visión por Computador y análisis estéreo. El documento aborda el problema de localización analizando tres de sus pasos fundamentales: comienza con las etapas iniciales del análisis estéreo, continúa analizando la fase de refinamiento y finaliza con la fase de odometría visual propiamente dicha. De esta manera, el resultado de la tesis es un sistema formado por tres propuestas novedosas para los tres bloques que forman un sistema de localización mediante Visión por Computador. En primer lugar, el documento realiza un análisis del estado del arte global, cuyo objetivo es ofrecer una visión general del problema, mostrar qué diferentes aproximaciones existen para resolver ciertos problemas y citar los sistemas y algoritmos más importantes encontrados en la literatura. Durante este estudio, se incluye el análisis de las técnicas de Simultaneous Location and Mapping (SLAM) debido a su íntima relación con los sistemas de odometría visual. Más allá de ser una simple descripción del estado del arte, se realiza un análisis y clasificación detallado de las diferentes soluciones encontradas, describiendo similitudes y diferencias en los pasos que sigue cada una de ellas. Como resultado se obtienen varias tablas en las que se resume qué pasos siguen y qué técnicas utilizan los algoritmos más importantes de la literatura. El documento continúa proponiendo un marco multiresolución de minimización de energía para el problema de correspondencia estéreo. Este marco aborda el problema del cálculo de disparidades utilizando diferentes resoluciones al comienzo y al final del algoritmo. Iniciar la estimación estéreo con un par de imágenes de alta resolución es muy positivo para obtener una alta definición en el campo de las disparidades, pero aumenta el tamaño del problema. Por el contrario, si deseamos disminuir el tamaño del problema y se decide disminuir la resolución inicial del par estéreo, la definición en la dimensión de las disparidades quedará restringida. Para solucionar este problema, se propone un algoritmo que admita como entrada imágenes de alta resolución, y obtenga como salida imágenes de resolución reducida pero manteniendo la definición en la dimensión de las disparidades como si fuesen de alta resolución. Se demuestra la importante disminución de la complejidad del problema comparado con el caso clásico de cálculo estéreo con imágenes de alta resolución. El análisis se realiza utilizando técnicas estéreo globales basadas en Modelos Aleatorios de Markov (MRF). Después del análisis estéreo, se propone una forma innovadora de abordar el problema del refinamiento de los mapas de disparidades obtenidos previamente. Para ello, se propone utilizar un algoritmo genético como optimizador de una función de energía representativa de la calidad de las correspondencias. Desde este punto de vista, la solución es similar a otras formas de optimización propuestas en la literatura para minimizar MRFs. A pesar de no garantizar un mínimo global, la utilización de algoritmos genéticos abre la posibilidad de utilizar cualquier tipo de función de energía sin restricciones. Ésta característica es una aportación importante comparada con el resto de algoritmos del estado del arte, que están limitados a ciertas funciones de energía. A lo largo del documento se proponen diferentes operadores genéticos adaptados al problema de análisis estéreo, se proponen diferentes funciones de energía y se comparan entre ellas. Además, se describe su implementación en una unidad gráfica de proceso (GPU) para aprovechar su naturaleza paralelizable y se muestran los beneficios que se pueden obtener en su tiempo de ejecución. Finalmente se propone un algoritmo de odometría visual diseñado para modelar escenas no estáticas. Basándose en algoritmos clásicos de registrado de nubes de puntos como el Iterative Closest Points (ICP), el algoritmo presentado realiza una clasificación de los puntos en tres dimensiones según su coherencia después de una transformación (rotación más traslación). De esta forma, utilizando un sistema de votación se detectan cuáles son las transformaciones más recurrentes y se clasifican los grupos de puntos en consecuencia. Esto permite detectar y eliminar elementos en movimiento para una estimación más precisa del movimiento de la cámara. Esto distingue al algoritmo frente a la gran mayoría de los existentes en el estado del arte, que contemplan los objetos en movimiento como outliers y es quizá la aportación más importante del algoritmo. Además, esta eliminación abre la posibilidad de calcular mapas de entorno incluyendo únicamente elementos estáticos evitando así el efecto sombra. Por último se analiza el rendimiento de los algoritmos clásicos de registrado como el ICP con nubes de puntos poco precisas como las obtenidas mediante algoritmos estéreo.

This thesis proposes a complete visual odometry system using only Computer Vision techniques and stereo analysis. The document addresses the pose estimation problem studying three of its fundamental steps: begins with the early stereo analysis stages, continues with the refinement phase and finally finishes with the analysis of the visual odometry algorithm itself. Therefore, the result of this thesis is a complete system constituted from three novel algorithms for the three stages that forms Computer Vision pose estimation system. Firstly, the document globally analyses the state of the art of pose estimation algorithms with the aim of offering a general view of the problem, shows the different existing approaches for solving certain problems and cites the most important sys- tems and algorithms found in the literature. This analysis includes the Simultaneous Location and Mapping (SLAM) techniques given that they are closely related to the visual odometry systems. However, it is not a mere state of the art description. It also realizes a detailed taxonomy and classification of the different solutions found, describing their differences and similarities for each of their steps. As a result, various tables resuming the steps and techniques of the most important algorithms in the literature are obtained. The document continues proposing a multiresolution energy minimization framework for the stereo correspondence problem. This framework deals with the problem of estimating the disparities using different image resolutions at the beginning and the end of the algorithm. Using high resolution images as stereo pairs is very adequate for obtaining also a high definition in the disparity dimension. However, this configuration leads to an important increment of the problem’s size. On the contrary, if the size of the problem is meant to be reduced and a decimation of the input stereo pair is performed, then the disparity resolution is also decimated, which leads to bad disparity estimations. In order to solve this problem, an algorithm using high resolution stereo images as input and obtaining lower resolution disparity maps but maintaining the original depth resolution is proposed. The document shows the important reduction of the problem’s size compared to classical high resolution stereo pair inputs. For this analysis, global algorithms based on Markov Random Fields (MRF) are used. After the stereo analysis, a novel disparity map refinement process is proposed. A genetic algorithm is used for minimizing an energy function modeling the stereo correspondence fitness. This approach is similar to other techniques found in the literature, in the sense that an energy function based on an MRF is meant to be minimized. In spite of finding a global minimum is not guaranteed, the utilization of genetic algorithms gives the opportunity of using any kind of energy function without any restriction. This characteristic is an important contribution compared to most algorithms found in the literature, given that they are usually restricted to some forms of energy functions. During the document, the most important genetic operators are adapted to the stereo matching problem. Moreover, different energy functions dealing with occlusions are proposed and compared. A Graphics Processing Unit (GPU) implementation using CUDA is also explained in detail, in order to demonstrate the parallel nature of the algorithm and the performance boost that could be obtained using these hardware units. Finally, a visual odometry algorithm capable of dealing with non-static scenes is proposed. Based on classic point-cloud registering algorithms found in the literature such as Iterative Closest Points (ICP), the proposed algorithm performs a three dimensional point classification based on its coherence after certain transformations (translation and rotation). That way, using a voting system, the most frequent transformations are detected and points are classified forming groups that fulfill rigid bodies constraints. This classification permits to eliminate moving objects from the scene and perform a better camera motion estimation. This classification distinguishes this algorithm from others in the literature and is probably the most important contribution along this final odometry step. Besides, these objects removal enables to map the scene including only the static environment, avoiding the shadow effect. Finally, the accuracy of the classic point-cloud registering algorithms using clouds obtained from stereo algorithms is analyzed.