Detecção automática de planos em nuvens de pontos não-estruturados usando paralelismo dinâmico em CUDA

Abstract

A detecção de regiões planares em nuvem de pontos é um problema recorrente em visão computacional com as mais diversas aplicações práticas, como a calibração automática de câmeras, o reconhecimento de estruturas em cenas 3D, engenharia reversa e realidade aumentada. O algoritmo de detecção de regiões planares em nuvem de pontos não-organizadas estudado neste trabalho (LIMBERGER; OLIVEIRA, 2015) é uma forma eficiente de resolver este problema em complexidade O(NlogN). O método consiste em três etapas: (1) Subdivisão da nuvem de pontos em regiões aproximadamente coplanares, utilizando uma octree; (2) Esquema de votação para cada nodo definido nesta octree, acumulando os votos em um acumulador esférico; e (3) Detecção de picos no acumulador esférico, definindo as regiões planares de maior importância. Este trabalho explora o paralelismo de GPUs para tentar melhorar o desempenho do algoritmo definido utilizando a arquitetura CUDA, criada pela NVIDIA, com foco no uso de sua função de Paralelismo Dinâmico. Foram propostas duas abordagens para geração da octree, uma puramente em GPU utilizando o Paralelismo Dinâmico e outra híbrida intercalando processamento entre CPU e GPU, e uma abordagem para a etapa de votação aproveitando o paralelismo nas dimensões do acumulador esférico. Nos resultados das abordagens de octree foram observadas as dificuldades da utilização de paralelismo em GPU quando existe uma necessidade alta de sincronismo e a indispensabilidade de estruturas de dados melhores adaptadas a arquitetura CUDA. Já na abordagem de votação foi observado ganho de desempenho para nuvens de até um milhão de pontos.

Detection of planar regions in point clouds is a recurring problem in computer vision with various practical applications like automatic cameras calibration, structures recognition in 3D scenes, reverse engineering and augmented reality. The algorithm for detection of planar regions in unorganized point clouds studied in this work (LIMBERGER; OLIVEIRA, 2015) presents a very efficient way of solving this problem in complexity of O(NlogN). The method consists in three stages: (1) A point cloud subdivision in approximately planar regions, using an octree; (2) A voting scheme for every node defined in the octree, accumulating the votes in a spherical accumulator; and (3) A peak detection in the spherical accumulator, finding the most important planar regions. This work explores the GPU parallelism with the goal to improve the algorithm performance using the CUDA architecture, created by NVIDIA, with focus in its feature of Dynamic Parallelism. Two approaches for the octree generation are proposed, one exclusively on the GPU using the CUDA’s Dynamic Parallelism and a second hybrid approach, interleaving between CPU and GPU. Also an approach for the voting procedure is presented, taking advantage of the dimensions of the spherical accumulator. In the results of both the octree approaches is observed the difficulties in the use of parallelism in GPU when there is a high need for synchronism and the necessity of structures better adapted to the CUDA architecture. However, in the voting approach is observed a performance gain for clouds up to a million points.