[pt] Pesquisas na área de estrutura de dados são fundamentais para aumentar a generalidade e eficiência computacional da representacão de modelos geometricos. Neste trabalho, apresentamos duas estruturas de dados topológicas escalonáveis, uma para superfícies triânguladas, chamada CHE (Compact Half--Edge), e outra para malhas de tetraedros, chamada CHF (Compact Half--Face). Tais estruturas são compostas de diferentes níveis, que nos possibilitam alterar a quantidade de dados armazenados com objetivo de melhorar sua eficiência computacional. O uso de APIs baseadas no conceito de objeto, e de haran»ca de classes, possibilitam uma interface única para cada função em todos os níveis das estruturas. A CHE e a CHF requerem pouca memória e são simples de implementar já que substituem o uso de ponteiros pelo de contêineres genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase the generality and computational effciency of geometric models` representation. In this work, we present two new scalable topological data structures, one for triangulated surfaces, called CHE (Compact Half { Edge ), and the another for tetrahedral meshes, called CHF (Compact Half { Face ). Such structures are composed of different levels, that enable us to modify the amount of data stored with the objective to improve its computational effciency. The use of APIs based in the object concept and class inheritance, makes possible an unique interface for each function at any level. CHE and CHF requires very few memory and are simple to implement since they substitute the use of pointers by generic containeres and arithmetical rules.

Orientador: Hélio Pedrini / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:14:20Z (GMT). No. of bitstreams: 1 Silva_RicardoDutrada_D.pdf: 13549105 bytes, checksum: 3d49e5116a70a72601ba4cc3b3c85762 (MD5) Previous issue date: 2013 / Resumo: A Teoria de Morse é importante para o estudo da topologia em funções escalares como elevação de terrenos e dados provenientes de simulações físicas, a qual relaciona a topologia de uma função com seus pontos críticos. A teoria contínua foi adaptada para dados discretos através de construções como os complexos de Morse-Smale e o complexo discreto de Morse. Complexos de Morse têm sido aplicados em processamento de imagens, no entanto, ainda existem desafios envolvendo algoritmos e considerações práticas para a computação e modelagem dos complexos para imagens. Complexos de Morse podem ser usados como um meio de definir a conexão entre pontos de interesse em imagens. Normalmente, pontos de interesse são considerados como elementos independentes descritos por informação local. Tal abordagem apresenta limitações uma vez que informação local pode não ser suficiente para descrever certas regiões da imagem. Pontos de mínimo e máximo são comumente utilizados como pontos de interesse em imagens, os quais podem ser obtidos a partir dos complexos de Morse, bem como sua conectividade no espaço de imagem. Esta tese apresenta uma abordagem dirigida por algoritmos e estruturas de dados para computar o complexo de Morse discreto em imagens bidimensionais. A construção é ótima e permite fácil manipulação do complexo. Resultados teóricos e experimentais são apresentados para mostrar que o método é eficaz. Experimentos realizados incluem a computação de homologia persistente e hierarquias de complexos sobre dados de elevação de terrenos. Outra contribuição é a proposição de um operador topológico, chamado Contexto Local de Morse, computado sobre complexos de Morse, para extrair vizinhanças de pontos de interesse para explorar a informação estrutural de imagens. O contexto local de Morse é usado no desenvolvimento de um algoritmo que auxilia a redução do número de casamentos incorretos entre pontos de interesse e na obtenção de uma medida de confiança para tais correspondências. A abordagem proposta é testada em pares de imagens sintéticas e de imagens subaquáticas, para as quais métodos existentes podem obter muitas correspondências incorretas / Abstract: The Morse theory is important for studying the topology of scalar functions such as elevation of terrains and data from physical simulations, which relates the topology of a function to critical points. The smooth theory has been adapted to discrete data through constructions such as the Morse-Smale complexes and the discrete Morse complex. Morse complexes have been applied to image processing, however, there are still challenges involving algorithms and practical considerations for computation and modeling of the complexes. Morse complexes can be used as means of defining the connectedness of interest points in images. Usually, interest points are considered as independent elements described by local information. Such an approach has its limitations since local information may not suffice for describing certain image regions. Minimum and maximum points are widely used as interest points in images, which can be obtained from Morse complexes, as well as their connectivity in the image space. This thesis presents an algorithmic and data structure driven approach to computing the discrete Morse complex of 2-dimensional images. The construction is optimal and allows easy manipulation of the complex. Theoretical and applied results are presented to show the effectiveness of the method. Applied experiments include the computation of persistent homology and hierarchies of complexes over elevation terrain data. Another contribution is the proposition of a topological operator, called Local Morse Context (LMC), computed over Morse complexes, for extracting neighborhoods of interest points to explore the structural information in images. The LMC is used in the development of a matching algorithm, which helps reducing the number of incorrect matches between images and obtaining a confidence measure of whether a correspondence is correct or incorrect. The approach is tested in synthetic and challenging underwater stereo pairs of images, for which available methods may obtain many incorrect correspondences / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

[pt] A geometria diferencial descreve de maneira intuitiva os objetos suaves no espaço. Porém, com a evolução da modelagem geométrica por computador, essa ferramenta se tornou ao mesmo tempo necessária e difícil de se descrever no mundo discreto. A teoria de Morse ficou importante pela ligação que ela cria entre a topologia e a geometria diferenciais. Partindo de um ponto de vista mais combinatório, a teoria de Morse discreta de Forman liga de forma rigorosa os objetos discretos à topologia deles, abrindo essa teoria para estruturas discretas. Este trabalho propõe uma definição construtiva de funções de Morse geométricas no mundo discreto e do complexo de Morse-Smale correspondente, onde a geometria é definida como a amostragem de uma função suave nos vértices da estrutura discreta. Essa construção precisa de cálculos de homologia que se tornaram por si só uma melhoria significativa dos métodos existentes. A decomposição de Morse- Smale resultante pode ser eficientemente computada e usada para aplicações de cálculo da persistência, geração de grafos de Reeb, remoção de ruído e mais. . . / [en] Differential geometry provides an intuitive way of understanding smooth objects in the space. However, with the evolution of geometric modeling by computer, this tool became both necessary and difficult to transpose to the discrete setting. The power of Morse theory relies on the link it created between differential topology and geometry. Starting from a combinatorial point of view, Forman´s discrete Morse theory relates rigorously discrete objects to their topology, opening Morse theory to discrete structures. This work proposes a constructive definition of geometric discrete Morse functions and their corresponding discrete Morse-Smale complexes, where the geometry is defined as a smooth function sampled on the vertices of the discrete structure. This construction required some homology computations that turned out to be a significant improvement over existing methods by itself. The resulting Morse-Smale decomposition can then be efficiently computed, and used for applications to persistence computation, Reeb graph generation, noise removal. . .

[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos. Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a scalar function defined on it. This applies in both the classical theory and a discrete version of it defined by Forman in 1995. Those Morse theories permit to characterize a topological space from functions defined on it, but also to study functions based on topological constructions it implies, such as the Morse-Smale complex. While discrete Morse theory applies on general cell complexes in an entirely combinatorial manner, which makes it suitable for computation, the functions it considers are not sampling of continuous functions, but special matchings in the graph encoding the cell complex adjacencies, called Morse matchings. When using this theory to study a topological space, one looks for optimal Morse matchings, i.e. one with the smallest number of critical elements, to get highly succinct topological information about the complex. The first part of this thesis investigates the parameterized complexity of finding such optimal Morse matching. On the one hand the Erasability problem, a closely related problem to finding optimal Morse matchings, is proven to be W[P]-complete. On the other hand, an algorithm is proposed for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter tractable in the tree-width of its dual graph. When using discrete Morse theory to study a scalar function defined on the space, one looks for a Morse matching that captures the geometric information of that function. The second part of this thesis introduces a construction of Morse matchings based on stable matchings. The theoretical guarantees about the relation of such matchings to the geometry are established through surprisingly simple proofs that benefits from the local characterization of the stable matching. The construction and its guarantees work in any dimension. Finally stronger results are obtained if the function is discrete smooth on the complex, a notion defined in this thesis.