Embedded 3D Reconstruction for Autonomous Driving

L'objectiu d'aquesta tesi és estudiar algoritmes de reconstrucció 3D adequats per a la conducció autònoma. Per fer-ho, necessitem implementacions i representacions ràpides de l'entorn 3D que tinguin en compte la informació geomètrica i semàntica. L'ús de paral·lelització CUDA i GPU permet aprofitar maquinari flexible i programable d'alt rendiment per complir els requisits de temps exigents. La tesi presenta tres contribucions principals. En primer lloc, descrivim la paral·lelització del conegut algorisme d'estèreo basat en el Semi-Global Matching (SGM), que estima la profunditat a partir de dues imatges estèreo. Desplegem un disseny de paral·lelització eficient que funciona a les GPU de baix consum energètic i aconsegueix un rendiment en temps real. Com a segona contribució, presentem una millora del model de representació 3D anomenat Stixel World, que representa les superfícies inclinades. L'extensió del model ajuda a representar escenes reals que fallen sota els supòsits anteriors i, mitjançant una regularització eficient del model, manté la mateixa precisió que el model anterior. També proposem una estratègia algorítmica per accelerar el procés, que redueix la quantitat de combinacions Stixel provades. Finalment, expliquem les nostres estratègies de paral·lelització per a l'algorisme de segmentació de Stixel. Proposem una estratègia de paral·lelització que s'adapti a l'arquitectura massivament paral·lela de les GPU. També estudiem les diferents tècniques d'acceleració disponibles per a Stixels i com es poden implementar de manera eficient per a aquesta arquitectura. A més, el nostre enfocament redueix la complexitat computacional de l'algorisme mitjançant la reformulació del model.El objetivo de esta tesis es estudiar algoritmos de reconstrucción 3D aptos para la conducción autónoma. Para ello, necesitamos implementaciones y representaciones rápidas del entorno 3D que tengan en cuenta la información geométrica y semántica. El uso de la paralelización de CUDA y GPU permite aprovechar el hardware de alto rendimiento flexible y programable para cumplir con los estrictos requisitos de tiempo. La tesis presenta tres contribuciones principales. Primero, describimos la paralelización del conocido algoritmo de estéreo basado en Semi-Global Matching (SGM), que estima la profundidad de dos imágenes estéreo. Implementamos un diseño de paralelización eficiente que se ejecuta sobre GPU de bajo consumo de energía y logra un rendimiento en tiempo real. Como segunda contribución, presentamos una mejora del modelo de representación 3D llamado Stixel World que da cuenta de las superficies inclinadas. La extensión del modelo ayuda a representar escenas reales que fallan bajo los supuestos anteriores y, mediante una regularización eficiente del modelo, mantiene la misma precisión del modelo anterior. También proponemos una estrategia algorítmica para acelerar el proceso, lo que reduce la cantidad de combinaciones de Stixel probadas. Finalmente, explicamos nuestras estrategias de paralelización para el algoritmo de segmentación de Stixel. Proponemos una estrategia de paralelización que se adapta a la arquitectura masivamente paralela de las GPU. También estudiamos las diferentes técnicas de aceleración disponibles para Stixels y cómo se pueden implementar de manera eficiente para esta arquitectura. Además, nuestro enfoque reduce la complejidad computacional del algoritmo al reformular el modelo.The objective of this thesis is to study 3D reconstruction algorithms suitable for autonomous driving. In order to do so, we need fast implementations and representations of the 3D environment that take into account geometric and semantic information. The use of CUDA and GPU parallelization allows to leverage flexible and programmable high performance hardware to fulfill the strong time requirements. The thesis presents three main contributions. First, we describe the parallelization of the well-known stereo matching algorithm based on Semi-Global Matching (SGM), which estimates depth from two stereo images. We deploy an efficient parallelization design that runs on top of low-energy consumption GPUs and achieves real-time performance. As our second contribution, we present an improvement of the 3D representation model called the Stixel World that accounts for slanted surfaces. The extension of the model helps representing real scenes that fail under the previous assumptions, and, by an efficient model regularization, keeps the same accuracy of the previous model. We also propose an algorithmic strategy to speed up the process, which reduces the amount of Stixel combinations tested by the dynamic programming approach. Finally, we explain our parallelization strategies for the Stixel segmentation algorithm. We propose a parallelization strategy that fits the massively parallel architecture of GPUs. We also study the different speed up techniques available for Stixels and how they can be implemented efficiently for this architecture. Additionally, our approach reduces the computational complexity of the algorithm by reformulating the measurement depth model, relying on the confidence of the depth estimation and the identification of invalid values to handle outliers