[en] 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.

[es] 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.