Orientador: Jorge Stolfi [Orientador] / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação. / Made available in DSpace on 2018-08-10T07:43:58Z (GMT). No. of bitstreams: 1 Montagner_ArnaldoJovanini_D.pdf: 2204093 bytes, checksum: 4c9c86ca0312f3b5507e1daa8c6553db (MD5) Previous issue date: 2007 / Resumo: Mapas são subdivisões de espaços topológicos em regiões simples, e triangulações são um tipo específico de mapa em que cada elemento é um simplexo (aresta, triângulo, tetraedro, etc). Neste trabalho, tratamos o problema de representação da topologia de triangulações e mapas de dimensão arbitrária. Estudamos a utilização de uma representação baseada em grafos de arestas coloridas, já utilizada como ferramenta teórica, mas nunca empregada em aplicações práticas. A principal limitação desta representação é a relativa inflexibilidade imposta sobre a manipulação da topologia. Há porém grandes vantagens em sua utilização, como a simplicidade de representação e a generalidade. Este trabalho consiste na especificação teórica de uma estrutura de dados baseada nestes grafos coloridos e de operações topológicas para construção e manipulação da estrutura. A utilização desta estrutura é ilustrada através de algoritmos para resolução de problemas em geometria computacional / Abstract: Maps are subdivisions of topological spaces into simple regions, and triangulations are a specific kind of map wherein each element is a simplex (edge, triangle, tetrahedron, etc). In this work, we analyze the problem of representing the topology of triangulations and maps with arbitrary dimension. We study a representation based on edge-colored graphs, already used as theoretical tool, but never employed in practical applications. The main limitation of this representation is the relative inexibility imposed on the manipulation of topology. There are, though, great advantages in its use, as its simplicity and generality. This work consists in the theoretic specification of a data structure based on these colored graphs and of topological operators to build and manipulate the structure.The use of this structure is illustrated by algorithms for computational geometry problems / Doutorado / Computação Grafica / Mestre em Ciência da Computação

Orientador: Eduardo Alves do Valle Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T08:10:33Z (GMT). No. of bitstreams: 1 Silva_EliezerdeSouzada_M.pdf: 2350845 bytes, checksum: dd31928bd19312563101a08caea74d63 (MD5) Previous issue date: 2014 / Resumo: A crescente disponibilidade de conteúdo multimídia é um desafio para a pesquisa em Recuperação de Informação. Usuários querem não apenas ter acesso aos documentos multimídia, mas também obter semântica destes documentos, de modo que a capacidade de encontrar um conteúdo específico em grandes coleções de documentos textuais e não textuais é fundamental. Nessas grandes escalas, sistemas de informação multimídia de recuperação devem contar com a capacidade de executar a busca por semelhança de forma eficiente. No entanto, documentos multimídia são muitas vezes representados por descritores multimídia representados por vetores de alta dimensionalidade, ou por outras representações complexas em espaços métricos. Fornecer a possibilidade de uma busca por similaridade eficiente para esse tipo de dados é extremamente desafiador. Neste projeto, vamos explorar uma das famílias mais citado de soluções para a busca de similaridade, o Hashing Sensível à Localidade (LSH - Locality-sensitive Hashing em inglês), que se baseia na criação de funções de hash que atribuem, com maior probabilidade, a mesma chave para os dados que são semelhantes. O LSH está disponível apenas para um punhado funções de distância, mas, quando disponíveis, verificou-se ser extremamente eficiente para arquiteturas com custo de acesso uniforme aos dados. A maioria das funções LSH existentes são restritas a espaços vetoriais. Propomos dois métodos novos para o LSH, generalizando-o para espaços métricos quaisquer utilizando particionamento métrico (centróides aleatórios e k-medoids). Apresentamos uma comparação com os métodos LSH bem estabelecidos em espaços vetoriais e com os últimos concorrentes novos métodos para espaços métricos. Desenvolvemos uma modelagem teórica do comportamento probalístico dos algoritmos propostos e demonstramos algumas relações e limitantes para a probabilidade de colisão de hash. Dentre os algoritmos propostos para generelizar LSH para espaços métricos, esse desenvolvimento teórico é novo. Embora o problema seja muito desafiador, nossos resultados demonstram que ela pode ser atacado com sucesso. Esta dissertação apresentará os desenvolvimentos do método, a formulação teórica e a discussão experimental dos métodos propostos / Abstract: The increasing availability of multimedia content poses a challenge for information retrieval researchers. Users want not only have access to multimedia documents, but also make sense of them --- the ability of finding specific content in extremely large collections of textual and non-textual documents is paramount. At such large scales, Multimedia Information Retrieval systems must rely on the ability to perform search by similarity efficiently. However, Multimedia Documents are often represented by high-dimensional feature vectors, or by other complex representations in metric spaces. Providing efficient similarity search for that kind of data is extremely challenging. In this project, we explore one of the most cited family of solutions for similarity search, the Locality-Sensitive Hashing (LSH), which is based upon the creation of hashing functions which assign, with higher probability, the same key for data that are similar. LSH is available only for a handful distance functions, but, where available, it has been found to be extremely efficient for architectures with uniform access cost to the data. Most existing LSH functions are restricted to vector spaces. We propose two novel LSH methods (VoronoiLSH and VoronoiPlex LSH) for generic metric spaces based on metric hyperplane partitioning (random centroids and K-medoids). We present a comparison with well-established LSH methods in vector spaces and with recent competing new methods for metric spaces. We develop a theoretical probabilistic modeling of the behavior of the proposed algorithms and show some relations and bounds for the probability of hash collision. Among the algorithms proposed for generalizing LSH for metric spaces, this theoretical development is new. Although the problem is very challenging, our results demonstrate that it can be successfully tackled. This dissertation will present the developments of the method, theoretical and experimental discussion and reasoning of the methods performance / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Flávio Ferrari Aragon / Banca: Adriano Wagner Ballarin / Banca: Luís Fernando Nicolosi Bravin / Banca: Rui Vieira de Moraes / Banca: Sandra Fiorelli de Almeida P. Simeão / Resumo: Nas Ciências Agronômicas, encontram-se várias situações em que são observadas diversas variáveis respostas nas parcelas ou unidades experimentais. Nestas situações, um caso de interesse prático à experimentação agronômica é o que considera a construção de regiões de similaridade entre as parcelas para a discriminação entre os grupos experimentais e ou para a classificação de novas unidades experimentais em uma dessas regiões. Os métodos de classificação ou discriminação exigem, para sua utilização prática, uma quantidade considerável de retenção de informação da estrutura de variabilidade dos dados e, principalmente, alta fidedignidade e competência nas alocações de novos indivíduos nos grupos, mostradas nas distribuições corretas destes indivíduos. Existem vários procedimentos para medir o grau de decisão correta (acurácia) das informações fornecidas pelos métodos classificatórios. Praticamente, a totalidade deles utilizam a probabilidade de classificação errônea como o indicador de qualidade, sendo alguns destes freqüentistas (probabilidade estimada pela freqüência relativa de ocorrências - métodos não paramétricos) e outros baseados nas funções densidade de probabilidade das populações (métodos paramétricos). A principal diferença entre esses procedimentos é a conceituação dada ao cálculo da probabilidade de classificação errônea. Pretende-se, no presente estudo, apresentar alguns procedimentos para estimar estas probabilidades, desenvolver um software para a obtenção das estimativas considerando a distância generalizada de Mahalanobis como o procedimento relativo à da função densidade de probabilidade para populações com distribuição multinormal . Este software será de acesso livre e de fácil manuseio para pesquisadores de áreas aplicadas, completado com o manual do usuário e com um exemplo de aplicação envolvendo divergência genética de girassol. / Abstract: In the Agronomical Sciences, mainly in studies involving biomass production and rational use of energy, there are several situations in which several variable answers in the parts or experimental units are observed. In these situations, a case of practical interest to the agronomical experimentation is that one which considers the construction of similarity regions among parts and or the classification of new experimental units. The classification methods demand, for their utilization, a considerable quantity for utilization of their information retention of data and, mostly, high fidelity and competence in the new individual allocations. There are several procedures to measure accuracy degree of the information supplied by the discrimination method. Practically all of them use the miss-classification probability (erroneous classification) like the quality indicator. The main difference among these evaluation methods is the characterization of the miss-classification probability. Therefore, the aim is to present some estimate procedures of the missclassification probabilities involving repetition frequency and distribution methods and to develop a software to obtain their estimate, which is accessible and easy handling for researchers of applied areas, complementing the study with user's manual and examples in the rational energy application and biomass energy. / Doutor

Orientador: Mauricio Ferreira Magalhães / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T10:39:34Z (GMT). No. of bitstreams: 1 EsteveRothenberg_ChristianRodolfo_D.pdf: 14213626 bytes, checksum: 46a6a812d056a078c8a7fe49c80ce0ff (MD5) Previous issue date: 2010 / Resumo: Esta tese introduz um novo conceito para as redes de conteúdo denominado compact forwarding. Este conceito traduz-se na utilização de técnicas probabilísticas no plano de encaminhamento onde o espaço de identificação não é mais relacionado a um host final, mas sim, à identificação de conteúdo(s). A essência do conceito originou-se de uma questão básica, qual seja, onde deve ser colocado o estado associado ao encaminhamento do pacote? Nos elementos de rede ou no cabeçalho do pacote? A tese propõe duas soluções que representam estes extremos, SPSwitch, na qual o estado é colocado nos elementos de rede e, LIPSIN, onde o estado é colocado no cabeçalho do pacote. O denominador comum a essas soluções consiste na utilização de técnicas probabilísticas inspiradas no Bloom filter como elemento base das decisões de encaminhamento. A utilização de estruturas de dados derivadas do Bloom filter traz um custo adicional necessário à minimização dos erros associados à utilização de uma estrutura probabilística. A tese contribui com várias técnicas para redução desses erros incluindo a análise dos custos associados. Cenários de aplicação são apresentados para validação das propostas discutidas no trabalho / Abstract: This thesis introduces the concept of compact forwarding in the field of content-oriented networks. The main idea behind this concept is taking a probabilistic approach to the problem of packet forwarding in networks centered on content identifiers rather than traditional host addresses. The fundamental question explored is where to place the packet forwarding state, in network nodes or in packet headers? Solutions for both extremes are proposed. In the SPSwitch, approximate forwarding state is kept in network nodes. In LIPSIN, the state is carried in the packets themselves. Both approaches are based on probabilistic packet forwarding functions inspired by the Bloom filter data structure. The approximate forwarding state comes at the cost of additional considerations due to the effects of one-sided error-prone data structures. The thesis contributes with a series of techniques to mitigate the false positive errors. The proposed compact forwarding methods are experimentally validated in several practical networking scenarios / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Alexandre Xavier Falcão / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T00:40:22Z (GMT). No. of bitstreams: 1 Miranda_PauloAndreVechiattode_D.pdf: 2915697 bytes, checksum: 45d7bf96dd5d6d6a8042a30dcbb51278 (MD5) Previous issue date: 2009 / Resumo: Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação (e.g., objetos e fundo). A segmentação de imagem é um dos problemas mais fundamentais e desafiadores em processamento de imagem e vis¿ao computacional. O problema da segmentação representa um desafio técnico importante na computação devido 'a dificuldade da máquina em extrair informações globais sobre os objetos nas imagens (e.g., forma e textura) contando apenas com informações locais (e.g., brilho e cor) dos pixels. Segmentação de imagens envolve o reconhecimento de objetos e o delineamento. O reconhecimento é representado por tarefas cognitivas que determinam a localização aproximada de um objeto desejado em uma determinada imagem (detecção de objeto),e identificam um objeto desejado de entre uma lista de objetos candidatos (classificação de objeto). Já o delineamento consiste em definir de forma precisa a extensão espacial do objeto de interesse. No entanto, métodos de segmentação efetivos devem explorar essas tarefas de forma sinérgica. Esse tema constitui o foco central deste trabalho que apresenta soluções interativas e automáticas para segmentação. A automação é obtida mediante o uso de modelos discretos que são criados por aprendizado supervisionado. Esses modelos empregam reconhecimento e delineamento de uma maneira fortemente acoplada pelo conceito de Clouds. Estes modelos são demonstrados no âmbito da neurologia para a segmentação automática do cérebro (sem o tronco cerebral), do cerebelo, e de cada hemisfério cerebral a partir de imagens de ressonância magnética. Estas estruturas estão ligadas em várias partes, o que impõe sérios desafios para a segmentação. Os resultados indicam que estes modelos são ferramentas rápidas e precisas para eliminar as intervenções do usuário ou, pelo menos, reduzi-las para simples correções, no contexto da segmentação de imagens do cérebro. / Abstract: Segmenting an image consists of partitioning it into regions relevant for a given application (e.g., objects and background). The image segmentation is one of the most fundamental and challenging problems in image processing and computer vision. The segmentation problem represents a significant technical challenge in computer science because of the difficulty of the machine in extracting global informations about the objects in the images (e.g., shape and texture) counting only with local information (e.g., brightness and color) of the pixels. Image segmentation involves object recognition and delineation. Recognition is represented by cognitive tasks that determine the approximate location of a desired object in a given image (object detection), and identify a desired object among candidate ones (object classification), while delineation consists in defining the exact spatial extent of the object. Effective segmentation methods should exploit these tasks in a synergistic way. This topic forms the central focus of this work that presents solutions for interactive and automatic segmentation. The automation is achieved through the use of discrete models that are created by supervised learning. These models employ recognition and delineation in a tightly coupled manner by the concept of Clouds. We demonstrate their usefulness in the automatic MR-image segmentation of the brain (without the brain stem), the cerebellum, and each brain hemisphere. These structures are connected in several parts, imposing serious challenges for segmentation. The results indicate that these models are fast and accurate tools to eliminate user's intervention or, at least, reduce it to simple corrections, in the context of brain image segmentation. / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Manufatura Aditiva, também conhecida por Impressão 3D, é um processo baseado na sobreposição de camadas para produzir um objeto físico. Os dados para a produção desse objeto vêm de um modelo geométrico tridimensional, geralmente representado por uma malha de triângulos. Um dos principais procedimentos no processo de produção é fatiar a malha triangular e gerar uma série de contornos, os quais representam as camadas do objeto. Há diversas estratégicas para fatiar malhas triangulares, porém, a maior parte dos trabalhos na literatura foca-se em problemas como a qualidade do modelo, melhorias específicas no processo de fatiamento e uso de memória; poucos trabalhos, no entanto, abordam o problema por uma perspectiva de complexidade algorítmica. Algoritmos propostos atualmente para este problema executam em tempo O(n² + k²) ou O(n² + nlognk); o algoritmo proposto nesta dissertação possui complexidade O(nk) para uma entrada com n triângulos e k planos e, com K é o número médio de planos que cortam cada triângulo nesta entrada específica. O algoritmo proposto, chamado de Fatiamento por Estocada (FE) é comparado teórica e experimentalmente com alguns dos métodos conhecidos na literatura e os resultados mostram melhora considerável em tempo de execução. / Additive Manufacturing, also known as 3D printing, is a process based on the addition of sucessive layers in order to build a physical object. The data for building this object come from geometric 3D model, usually represented by a triangle mesh. One of the main procedures in this process is to slice the triangle mesh and output a sequence of contours, representing each one of the layers of the object. There are many strategies for slicing meshes, however, most of the current literature is concerned with ad hoc issues such as the quality of the model, specific improvements in the slicing process and memory usage, whereas few of them address the problem from an algorithmic complecity perspective. While current algorithms for this problem ruin in O(n² + k²) or O(n² + nlognk), the proposed algorithm runs in O(nk), for a given input with n triangles, k planes and where k is the average number of slices cutting each triangle in this specific input. This is asymptotically the best that can be achieved under certain fairly common assumptions. The proposed algorithm, called here Slicing by Stabbing (SS), was compared both theoretically and experimentally against known methods in the literature and the results show considerable improvement in execution time.

Manufatura Aditiva, também conhecida por Impressão 3D, é um processo baseado na sobreposição de camadas para produzir um objeto físico. Os dados para a produção desse objeto vêm de um modelo geométrico tridimensional, geralmente representado por uma malha de triângulos. Um dos principais procedimentos no processo de produção é fatiar a malha triangular e gerar uma série de contornos, os quais representam as camadas do objeto. Há diversas estratégicas para fatiar malhas triangulares, porém, a maior parte dos trabalhos na literatura foca-se em problemas como a qualidade do modelo, melhorias específicas no processo de fatiamento e uso de memória; poucos trabalhos, no entanto, abordam o problema por uma perspectiva de complexidade algorítmica. Algoritmos propostos atualmente para este problema executam em tempo O(n² + k²) ou O(n² + nlognk); o algoritmo proposto nesta dissertação possui complexidade O(nk) para uma entrada com n triângulos e k planos e, com K é o número médio de planos que cortam cada triângulo nesta entrada específica. O algoritmo proposto, chamado de Fatiamento por Estocada (FE) é comparado teórica e experimentalmente com alguns dos métodos conhecidos na literatura e os resultados mostram melhora considerável em tempo de execução. / Additive Manufacturing, also known as 3D printing, is a process based on the addition of sucessive layers in order to build a physical object. The data for building this object come from geometric 3D model, usually represented by a triangle mesh. One of the main procedures in this process is to slice the triangle mesh and output a sequence of contours, representing each one of the layers of the object. There are many strategies for slicing meshes, however, most of the current literature is concerned with ad hoc issues such as the quality of the model, specific improvements in the slicing process and memory usage, whereas few of them address the problem from an algorithmic complecity perspective. While current algorithms for this problem ruin in O(n² + k²) or O(n² + nlognk), the proposed algorithm runs in O(nk), for a given input with n triangles, k planes and where k is the average number of slices cutting each triangle in this specific input. This is asymptotically the best that can be achieved under certain fairly common assumptions. The proposed algorithm, called here Slicing by Stabbing (SS), was compared both theoretically and experimentally against known methods in the literature and the results show considerable improvement in execution time.

Orientador: Sônia Maria Gomes, Jorge Stolfi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T12:39:30Z (GMT). No. of bitstreams: 1 Castro_DouglasAzevedo_D.pdf: 8872633 bytes, checksum: a17b2761789c6a831631ac143fdf5ca7 (MD5) Previous issue date: 2011 / Resumo: O objetivo desta tese é desenvolver algoritmos baseados em malhas e bases funcionais inovadoras usando técnicas de multiescala para aproximação de funções e resolução de problemas de equações diferenciais. Para certas classes de problemas, é possível incrementar a eficiência dos algoritmos de multiescala usando bases adaptativas, associadas a malhas construídas de forma a se ajustarem com o fenômeno a ser modelado. Nesta abordagem, em cada nível da hierarquia, os detalhes entre a aproximação desse nível e a aproximação definida no próximo nível menos refinado pode ser usada como indicador de regiões que necessitam de mais ou menos refinamento. Desta forma, em regiões onde a solução é suave, basta utilizar os elementos dos níveis menos refinados da hierarquia, enquanto que o maior refinamento é feito apenas onde a solução tiver variações bruscas. Consideramos dois tipos de formulações para representações multiescala, dependendo das bases adotadas: splines diádicos e wavelets. A primeira abordagem considera espaços aproximantes por funções splines sobre uma hierarquia de malhas cuja resolução depende do nível. A outra abordagem considera ferramentas da analise wavelet para representações em multirresolução de médias celulares. O enfoque está no desenvolvimento de algoritmos baseados em dados amostrais d-dimensionais em malhas diádicas que são armazenados em uma estrutura de árvore binária. A adaptatividade ocorre quando o refinamento é interrompido em algumas regiões do domínio, onde os detalhes entre dois níveis consecutivos são suficientemente pequenos. Um importante aspecto deste tipo de representação é que a mesma estrutura de dados é usada em qualquer dimensão, além de facilitar o acesso aos dados nela armezenados. Utilizamos as técnicas desenvolvidas na construção de um método adaptativo de volumes finitos em malhas diádicas para a solução de problemas diferenciais. Analisamos o desempenho do método adaptativo em termos da compressão de memória e tempo de CPU em comparação com os resultados do esquema de referência em malha uniforme no nível mais refinado. Neste sentido, comprovamos a eficiência do método adaptativo, que foi avaliada levando-se em consideração os efeitos da escolha de diferentes tipos de fluxo numérico e dos parâmetros de truncamento / Abstract: The goal of this thesis is to develop algorithms based on innovative meshes and functional bases using multiscale techniques for function approximation and solution of differential equation problems. For certain classes of problems, one can increase the efficiency of multiscale algorithms using hierarchical adaptive bases, associated to meshes whose resolution varies according to the local features of the phenomenon to be modeled. In this approach, at each level of the hierarchy the details-differences between the approximation for that level and that of the next coarser level-can be used as indicators of regions that need more or less refinement. In this way, in regions where the solution is smooth, it suffices to use elements of the less refined levels of the hierarchy, while the maximum refinement is used only where the solution has sharp variations. We consider two classes of formulations for multiscale representations, depending on the bases used: dyadic splines and wavelets. The first approach uses approximation spaces consisting of spline functions defined over a mesh hierarchy whose resolution depends on the level. The other approach uses tools from wavelet analysis for multiresolu-tion representations of cell averages. The focus is on the development of algorithms based on sampled d-dimensional data on dyadic meshes which are stored in a binary tree structures. The adaptivity happens when the refinement is interrupted in certain regions of the domain, where the details between two consecutive levels are sufficiently small. This representation greatly simplifies the access to the data and it can be used in any dimension. We use these techniques to build an adaptive finite volume method on dyadic grids for the solution of differential problems. We analyze the performance of the method in terms of memory compression and CPU time, comparing it with the reference scheme (which uses a uniform mesh at the maximum refinement level). In these tests, we confirmed the efficiency of the adaptive method for various numeric flow formulas and various choices of the thresholding parameters / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada