ALGORITMOS PARA PROCESSAMENTO DE IMAGENS E VISÃO COMPUTACIONAL PARA ARQUITETURAS PARALELAS EM PLACAS GRÁFICAS

Diversas tarefas de Visão Computacional (VC) são formadas por operações aritméticas, replicadas sobre grandes volumes de dados. Esta caracterização descreve também as qualidades desejadas ao considerar uma aplicação qualquer como boa candidata a usufruir do crescente poder de processamento do hardware gráfico. Esta tese formula um conjunto de algoritmos de VC sobre representações do conteúdo visual em baixo nível, para serem processados em GPU. Dando suporte às propostas, são apresentadas uma visão geral das GPUs e de padrões de programação paralelos, os quais oferecem blocos construtores para tarefas de visão. Neste sentido, propomos uma definição formal para o padrão de Redução Múltipla e analisamos seu desempenho segundo diferentes fatores de redução e variações para seus arranjos. Apresentamos duas propostas para extração de informações no espaço da imagem em GPU: a MOCT descreve a localização de objetos identificáveis por suas cores em vídeos naturais, enquanto o operador de Redução Regional Múltipla Paralela (MRR) distribui a computação de operadores definidos sobre diferentes regiões de interesse. Como aplicação do MRR, descrevemos a construção em GPU de um Diagrama Centroidal de Voronoi baseado no algoritmo de Lloyd. Tratamos do conteúdo visual em aglomerados de pixels, mais especificamente, em Quadtrees de regiões. Introduzimos a QuadN4tree, um modelo para representação de quadtrees que permite a navegação através do sistema de vizinhança das folhas e alcança custos ótimos no levantamento do conjunto de vizinhas de uma folha. Em seguida, propomos uma aceleração para aplicações baseadas em minimização de energia via corte de grafo, introduzindo uma etapa de pré-processamento que agrupa pixels similares em folhas de uma quadtree, com o objetivo de reduzir o tamanho do grafo sobre o qual o corte mínimo é encontrado. O método proposto é aplicado ao problema de segmentação de imagens naturais com iluminação ativa. Algumas contribuições desta tese, descrevendo formulações paralelas a dados, foram publicadas nos artigos incluídos nos apêndices.Arithmetically intensive operations, replicated over huge data sets (usually image pixels or scanned data), are an important part of many Computer Vision (CV) tasks, making them good candidates for taking advantage of the processing power of contemporary graphics processing units (GPUs). This thesis formulates a set of CV algorithms that use low level representations of visual content and are tailored for running on GPUs. A general view of GPUs and parallel programming patterns that offers interesting building blocks for CV tasks provides the necessary background for the algorithms. We also propose a formal definition for the Multiple Reduction pattern and evaluate its efficiency according to different reduction factors and layouts. We present two techniques for extracting data from the image space using the GPU: MOCT, a technique for tracking a set of objects identified by their colors from natural videos, and MRR, a technique for distributing the evaluation of a set of operators defined over different regions of interest within an image. As a MRR application we describe a Centroidal Voronoi Diagram construction based on Lloyds algorithm but entirely computed using GPU resources. We also deal with visual content representations as pixel agglomerations, more specifically, as Regional Quadtrees. We introduce the QuadN4tree: a new model for representing quadtree leaves that allows navigation through their neighborhood systems and achieves an optimal cost for the retrieval of neighbor sets. We also propose modifying the setup for CV applications based on energy minimization via graph cuts, introducing a preprocessing step that groups similar pixels into regional quadtree leaves. This modification aims to reduce the size of the graph for which a minimum cut is to be found. We apply our proposed method to the problem of natural image segmentation by active illumination. Published papers detailing some contributions of this dissertation are included as appendixes. They present data-parallel formulations for the CV tasks we describe