[pt] Reconstruir a informação 3D de uma cena é uma tarefa bastante comum em Visão Computacional. Uma das técnicas mais utilizadas para realizar esta tarefa é a correspondência por estéreo, que consiste basicamente em, dadas duas imagens referentes a uma mesma cena vista de pontos diferentes, determinar os pontos correspondentes entre essas duas imagens e armazenar essa informação em um mapa de disparidades. Até hoje diversos métodos foram propostos para resolver o problema de estéreo com esforço computacional viável e mantendo a qualidade dos resultados. Essa, entretanto, é uma tarefa bastante árdua e que difícilmente alcança resultados precisos com pouco esforço computacional. Nesse âmbito, uma técnica que tem sido muito estudada são os Cortes de Grafo (Graph Cuts), que almeja resolver o problema de minimização de energia em tempo polinomial. Nesse caso o problema de estéreo é mapeado como um problema de minimização de energia e desta forma solucionado utilizando cortes de grafo. Neste trabalho estudamos as técnicas de cortes de grafo mais recentes e eficientes e propomos um método para a determinação de correspondências entre duas imagens num contexto de multi-resolução, no qual uma pirâmide Gaussiana para as imagens é construída e a técnica de cortes de grafo é aplicada em níveis menores, otimizando a performance e obtendo resultados mais precisos através da utilização do algoritmo de expansão-alfa. São revisadas as técnicas de cortes de grafo e de multi-resolução e os resultados obtidos são apresentados e avaliados em relação a métodos semelhantes. / [en] Reconstructing the 3D information of a scene is a common task in Computer Vision. Stereo matching is one of the most investigated techniques used to perform this task, which basically consists of, given two images of a scene seen from different view points, determining corresponding pixels in these two images and store this information in a disparity map. Several methods have been proposed to solve the stereo problem keeping good performance and giving good quality results. This is however a very arduos task which hardly achieves precise results with low computational power. In this context, the Graph Cuts method has been very much considered, which aims to solve the energy minimization problem in polinomial time. In this case the stereo problem can be modelled as an energy minimization problem and, thus solved using the Graph Cuts technique. In this work we investigate the most recent and efficient Graph Cuts methods and propose a method for establishing the correspondences between two images in the context of multi-resolution, in which a Gaussian pyramid for the input images is built and the Graph Cuts methods is applied in coarser levels, optimizing the performance and getting more precise results through the use of the alfa-expansion algorithm. The Graph Cuts and multi-resolution techniques are reviewed and the results of the proposed method are presented and evaluated compared to similar methods.

[pt] Este trabalho apresenta um estudo comparativo de algumas representações em multi-resolução para linhas poligonais. São estudados as estruturas strip tree, arc tree e box tree, e suas variantes, comparando as velocidades de construção, de percorrimento (drawing), de operações de interseção e seleção (pick); e custo de armazenagem em memória. A comparação é feita usando bancos de dados cartográficos reais disponíveis na Internet. O objetivo do estudo é identificar técnicas e algoritmos adequados para exploração interativa de grandes bancos de dados cartográficos. / [en] This work presents a comparative study of some multiresolution representations for polygonal lines. We study the strip tree, the arc tree and the box tree data structures, comparing their performance for construction, drawing, intersection and selection; and memory storage costs. The comparation uses actual databases available in the Internet. The goal of this study is to identify techniques and algorithms for interactive exploration of large cartographic data bases.

[pt] Este trabalho apresenta um método para extração de malhas poligonais adaptativas em multi-resolução, a partir de objetos volumétricos. As principais aplicações da extração de malhas estão ligadas à área médica, dinâmica de fluidos, geociências, meteorologia, dentre outras. Nestas áreas os dados podem ser representados como objetos volumétricos. Nos dados volumétricos as informações estão representadas implicitamente, o que dificulta o processamento direto dos objetos que se encontram representados dentro do volume. A extração da malha visa obter uma representação explícita dos objetos, de modo a viabilizar o processamento dos mesmos. O método apresentado na tese procura extrair a malha a partir de processos de Simplicação e Refinamento. Durante a simplificação é extraída uma representação super amostrada do objeto (na mesma resolução do volume inicial), a qual é simplificada de modo a se obter uma malha base ou malha grossa, em baixa resolução, porém contendo a topologia correta do objeto. A etapa de refinamento utiliza a transformada de distâ ncia para obter uma representação da malha em multi-resolução, ou seja, a cada instante é obtida uma malha de maior resolução que vai se adaptando progressivamente à geometria do objeto. A malha final apresenta uma série de propriedades importantes, como boa razão de aspecto dos triângulos, converge para a superfície do objeto, pode ser aplicada tanto a objetos com borda quanto a objetos sem borda, pode ser aplicada tanto a superfície conexas quanto a não conexas, dentre outras. / [en] This work presents a method for extracting multiresolution adaptive polygonal meshes, from volumetric objects. Main aplications of this work are related to medical area, fluid dynamics, geosciences, metheorology and others. In these areas data may be represented as volumetric objects. Volumetric datasets are implicit representations of objects, so it s very dificult to apply directly any process to these objects. Mesh extraction obtains an explicit representation of the objetc, such that it s easier to process directly the objects. The presented method extracts the mesh from two main processes: Simplification and Refinement. The simplification step extracts a supersampled representation of the object (in the same volume resolution), and simplifies it in such a way to obtain a base mesh (or coarse mesh), in a low resolution, but containing the correct topology of the object. Refinement step uses the distance transform to obtain a multiresolution representation of the mesh, it means that at each instant it s obtained an adaptive higher resolution mesh. The final mesh presents a set of important properties, like good triangle aspect ratio, convergency to the object surface, may be applied as to objects with boundary and as to objects with multiple connected components, among others properties.

[pt] Visualização de grandes terrenos é um assunto desafiador em computação gráfica. O número de polígonos necessário para representar fielmente a geometria de um terreno pode ser muito alto para ser processado em tempo real. Para resolver tal problema, utiliza-se um algoritmo de multi- resolução, que envia para o processador gráfico (GPU) somente os polígonos mais importantes, sem que haja uma perda na qualidade visual. A quantidade de dados é um outro grande problema, pois facilmente excede a quantidade de memória RAM do computador. Desta forma, um sistema de gerenciamento de dados que não estão em memória principal também é necessário. Este trabalho propõe uma solução simples e escalável para visualizar a geometria de grandes terrenos baseada em três pontos chaves: uma estrutura de dados para representar o terreno em multi-resolução; um sistema eficiente de visualização; e um sistema de paginação e predição dos dados. A estrutura de dados utilizada, assim como em outros trabalhos similares, é a quadtree. Esta escolha justifica-se pela simplicidade, além da eficiência e baixo consumo de memória de uma implementação em vetor. Cada nó da quadtree representa um ladrilho do terreno. A implementação é dividida em duas linhas de execução (threads), uma para gerenciamento dos ladrilhos e outra para visualização. A linha de execução de gerenciamento de ladrilhos é responsável por carregar/remover ladrilhos para/da memória. Esta linha de execução utiliza um mecanismo de predição de movimento da câmera para carregar ladrilhos que possam ser utilizados em um futuro próximo, e remover ladrilhos que provavelmente não serão necessários. A linha de execução de visualização é responsável por visualizar o terreno, fazendo cálculo do erro projetado, eliminando ladrilhos não visíveis e balanceando a estrutura de quadtree para eliminar buracos ou vértices T na superfície do terreno. A visualização pode ser feita de duas formas distintas: baseada no erro máximo tolerado ou na quantidade máxima de polígonos a ser processado. / [en] The visualization of large terrains is a challenging Computer Graphics issue. The number of polygons required to faithfully represent a terrain`s geometry can be too high for real-time visualization. To solve this problem, a multiresolution algorithm is used to feed the graphics processor only with the most important polygons, without visual quality loss. The amount of data is another important problem, as it can easily exceed a computer`s RAM. Thus, a system to manage out-of-core data is also required. The present work proposes a simple and scalable solution to visualize the geometry of large terrains based on three key points: a data structure to represent the terrain in multi-resolution, an efficient visualization system and a data paging and prediction system. Similarly to other works, the system uses a quadtree data structure due to its simplicity, along with the efficiency and the low memory use of an array-based implementation. Each node of the quadtree represents a tile of the terrain. The implementation is divided in two threads, one to manage the tiles and the other for visualization. The tile-management thread is responsible for loading/unloading tiles into/from the memory. This thread uses a camera-movement prediction mechanism to load tiles that can be used in the near future and to remove tiles that probably will not be necessary. The visualization thread is responsible for viewing the terrain, computing the projected error, eliminating tiles that are not visible and balancing the quadtree structure in order to eliminate cracks or T-vertices on the terrain`s surface. The visualization can be made by means of a fidelity-based or a budget-based approach.

[pt] Atualmente, diversas áreas de Computação Gráfica necessitam processar uma grande quantidade de dados. Para visualizar em tempo-real esses dados é necessário lidar com dois tipos de problema. O primeiro está relacionado com o pouco tempo destinado para realizar os cálculos no processo de síntese de imagem. O segundo problema surge da capacidade limitada de armazenamento dos dispositivos de alta velocidade, como memórias RAM e de textura. Para resolver o primeiro problema, este trabalho utilizou a técnica de multi-resolução para representar os dados gráficos. A representação em multi-resolução permite que a quantidade de dados processada durante a visualização seja praticamente constante. O segundo problema foi resolvido a partir de um sistema de gerenciamento de memória preditivo baseado no modelo de memória virtual. Este trabalho propõe uma arquitetura que permite que qualquer tipo de dispositivo de armazenamento seja inserido. Os dispositivos estão organizados em seqüência. O funcionamento do sistema consiste em reservar um espaço de memória em cada dispositivo e gerenciar esse espaço de forma otimizada. O sistema de predição tem a finalidade de carregar antecipadamente os dados que serão provavelmente utilizados pela aplicação num futuro próximo. Este trabalho propõe um algoritmo de predição adaptativo específico para o problema de visualização. Este algoritmo explora as informações sobre as variações dos parâmetros da câmera e as informações sobre a taxa de transferência de dados, que são usadas para decidir o que deve ser carregado. As informações dos parâmetros da câmera ajudam a determinar os dados que possivelmente serão utilizados pela aplicação. A informação da taxa de transmissão é utilizada para decidir qual o nível de resolução desses dados que devem ser carregados antecipadamente para os dispositivos de alta velocidade. O sistema de gerenciamento de memória preditivo foi testado em aplicações de visualização de imagens de satélite e panoramas virtuais,em tempo-real. / [en] Nowadays, many areas of computer graphics need to process a huge amount of data. In order to visualize the data in realtime time, it is necessary to solve two different problems. The first problem is the limited time available to perform rendering. The second one arises from the restricted capacity of storage high-speed memories, like RAM and texture memories. In order to solve the first problem, this work has used multi-resolution techniques. The multi-resolution representation allows the application to work with a constant amount of data during the rendering process. The second problem has been solved by a predictive management memory system based on the virtual memory model. This work proposes an architecture that allows any storage device to be incorporated in the system. Devices are organized sequentially. The heart of the system consists in allocating an area of memory for each device and managing this space optimally. The predictive system aims to load in advance. The data that will probably be used by the application in the near future. This work proposes a specific adaptative prediction algorithm for the visualization problem. This algorithm exploits the information about the camera parameter variations as well as the data transfer rate, in order to decide what should be loaded. The camera parameters are used to determine which data will possibly be used by the application. The transfer rate is used to decide which resolution level of the data should be loaded to the high- speed devices, in advance. The predictive memory management system has been tested for real-time visualization of satellite images and virtual panoramas.

[pt] Atualmente, as malhas de simulação do fluxo em reservatórios naturais de petróleo (RNPs) são modelos compostos por centenas de milhares de células hexaédricas, cada uma podendo ser decomposta em 12 triângulos, de modo que a visualização interativa dessas malhas, através das estações gráficas atuais, ainda não é factível. À medida que os computadores e as placas gráficas aumentam sua capacidade de processamento, as malhas de simulação também crescem. A solução para esse tipo de problema passa, normalmente, por técnicas de aceleração, dentre as quais está a multi-resolução (MR). Ocorre, entretanto, que os modelos de multi-resolução atualmente conhecidos não são aplicáveis às malhas de simulação de RNPs, devido aos requisitos específicos da área, tais como a preservação do modelo de células hexaédricas e a descontinuidade entre células. Na realidade, as técnicas de multi-resolução tendem a enfocar a Visualização Realista, enquanto o problema de RNPs é de Visualização Científica, para a qual ainda não existem soluções genéricas. Esta dissertação propõe um modelo de MR específico para o problema de visualização das malhas de simulação em RNPs, no qual a partição descontínua do espaço, a semântica baseada em células hexaédricas e as características de visualização do problema são pontos considerados. O modelo proposto permite uma construção eficiente da estrutura de MR, a partir da qual, em tempo real, são extraídas malhas adaptativas dependentes: (a) do erro geométrico da aproximação, (b) da câmera e (c) do número desejado de polígonos na malha. Além disso, o modelo permite a utilização conjunta de outra técnica de aceleração, o descarte, possibilitando o descarte hierárquico de regiões da malha que estão fora do volume de visão. O modelo proposto foi implementado em um sistema que permitiu uma extensa bateria de testes, cujos resultados permitiram traçar algumas conclusões e recomendações. / [en] Current flow-simulation meshes of natural oil reservoirs (NOR) are composed of hundreds of thousands of hexahedral cells. The visualization of the geometry of these cells superimposed with color attributes to represent properties and flow results requires the rendering of an unstructured mesh of millions of triangles. Current graphics hardware does not allow for an interactive visualization of such meshes. As computers and graphics boards increase their processing capacity, simulation meshes also grow and the solution to the rendering problem usually includes acceleration techniques, one of which is multi-resolution (MR). However, currently known MR models are not applicable to NOR simulation meshes due to this field`s specific requirements, such as the preservation of the hexahedral- cell model and discontinuities among cells. In fact, MR techniques tend to focus on Realistic Visualization, while the NOR problem is one of Scientific Visualization, for which generic solutions still do not exist. The present work proposes a specific MR model for the visualization problem concerning NOR simulation meshes, in which discontinuous space partition, hexahedral-cell-based semantics and the problem`s visualization characteristics are taken into account. The proposed model allows an efficient construction of a MR structure, from which, in real time, adaptive meshes can be extracted that depend on: (a) the geometric error approximation, (b) the view, and (c) the polygon budget. This model can also be used combined with another acceleration technique, frustum culling, which allows for the hierarchical elimination of regions in the mesh that are out of the view volume. The proposed model was implemented in a system on which extensive testing was performed, providing results that allowed us to draw some conclusions and recommendations.