This Master s thesis proposes a non-assisted procedural method for 3D canyons scenes generation based on techniques of computer graphics, computer vision and graph search algorithm. In order to define all the features to be reproduced in our scenes, we have analyzed several images of real canyons and have categorized them in two canyon features models: a recursive and an ordinary one. The proposed approach manipulates a heightmap, created using Perlin noise, in order to imitate the geological features formation previously analyzed. Several parametrizations are used to guide and constraint the generation of terrains, canyons features, course of river, plain areas, soft slope regions, cliffs and plateaus. This work also uses the Mean Shift algorithm as mechanism of segmentation to define regions of interest. A binary mask, with plain areas, is defined based on a threshold operation by a given data set provided by the Mean Shift algorithm. Thereafter a connected-component labeling algorithm is executed using the previously binary mask. This algorithm finds all plains centroids. Right after that, the Dijkstra s algorithm is performed in order to connect all plain areas, creating a valid path between the centroids. The Dijkstra s algorithm is executed again to define the river s course. Finally, a Gaussian smoothing operation is applied to interpolate the soft slope regions. The combination of all those techniques produces as a result automatically generated feature-rich canyons. / Esta dissertação propõe um método procedural não assistido, baseado em técnicas de computação gráfica, visão computacional e busca em grafos, para a geração de cenários 3D de cânions com foco em jogos digitais. Para definir as características a serem reproduzidas, foram analisadas diversas imagens de cânions reais chegando-se em dois modelos, um comum e outro recursivo. A abordagem proposta manipula um reticulado gerado com ruído de Perlin, moldando assim as características inerentes a essa formação geológica. São levadas em conta as diversas parametrizações necessárias para permitir que o algoritmo construa cânions com curso de rio, áreas de planícies, regiões de encosta suave, estruturas de penhascos e, por fim, planaltos nas regiões mais altas. Para atingir o resultado final, o trabalho utiliza o algoritmo Mean Shift como mecanismo de segmentação, definindo dados e regiões de interesse. Munido dos dados do algoritmo de clusterizacao, é definido um limiar para a criação de uma máscara binária com a definição das planícies. Em um segundo momento, um algoritmo de rotulação de componentes conectados é executado, extraindo-se os centróides de cada planície. Por sua vez, o algoritmo de Dijkstra encaixa-se na definição de rotas que conectam estas planícies. O algoritmo de Dijkstra é, então, executado novamente, tendo por base uma função de custo de inclinação, para definir o curso do rio. Por fim, uma filtragem espacial baseada em um filtro Gaussiano é aplicada para interpolar as regiões de encostas de declive suave. A combinação dessas técnicas gera terrenos com grande variabilidade e com as características inerentes à formação geológica de cânions.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:24:27Z No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:29:29Z (GMT) No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-30T14:29:29Z (GMT). No. of bitstreams: 2 Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-08-08 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / This paper presents a Graphics Processing Unit (GPU) based parallels implementations for the All Pairs Shortest Paths and Transitive Closure problems in graph. The implementations are based on the main sequential algorithms and takes full advantage of the highly multithreaded architecture of current manycore GPUs. Our solutions reduces the communication between CPU and GPU, improves the Streaming Multiprocessors (SMs) utilization, and makes intensive use of coalesced memory access to optimize graph data access. The advantages of the proposed implementations are demonstrated for several graphs randomly generated using the widely known graph library GTgraph. Graphs containing thousands of vertices and different edges densities, varying from sparse to complete graphs, were generated and used in the experiments. Our results confirm that GPU implementations can be competitive even for graph algorithms whose memory accesses and work distribution are both irregular and data-dependent. Keywords / Este trabalho apresenta implementações paralelas baseadas em Graphics Processing Unit (GPU) para os problemas da identificação dos caminhos mínimos entre todos os pares de vértices e do fecho transitivo em um grafo. As implementações são baseadas nos principais algoritmos sequenciais e tiram o máximo proveito da arquitetura multithreaded das GPUs atuais. Nossa solução reduz a comunicação entre a Central Processing Unit (CPU) e a GPU, melhora a utilização dos Streaming Multiprocessors (SMs) e faz um uso intensivo de acesso aglutinado em memória para otimizar o acesso de dados do grafo. As vantagens dessas implementações propostas são demonstradas por vários grafos gerados aleatoriamente utilizando a ferramenta GTgraph. Grafos contendo milhares de vértices foram gerados e utilizados nos experimentos. Nossos resultados confirmam que implementações baseadas em GPU podem ser viáveis mesmo para algoritmos de grafos cujo acessos à memória e distribuição de trabalho são irregulares e causam dependência de dados.

University, Diss., 2004--Saarbrücken.

This thesis examines some of the best known algorithms for solving the shortest point-to-point path problem, and evaluates their performance on real metropolitan area networks. The focus has mainly been on Dijkstra‟s algorithm and different variations of it, and the algorithms have been implemented in C# for the practical tests. The size of the networks used in this study varied between 358 and 2464 nodes, and both running time and representative operation counts were measured. The results show that many different factors besides the network size affect the running time of an algorithm, such as arc-to-node ratio, path length and network structure. The queue implementation of Dijkstra‟s algorithm showed the worst performance and suffered heavily when the problem size increased. Two techniques for increasing the performance were examined: optimizing the management of labelled nodes and reducing the search space. A bidirectional Dijkstra‟s algorithm using a binary heap to store temporarily labelled nodes combines both of these techniques, and it was the algorithm that performed best of all the tested algorithms in the practical tests. This project was initiated by Netadmin Systems i Sverige AB who needed a new path finding module for their network management system NETadmin. While this study is primarily of interest for researchers dealing with path finding problems in computer networks, it may also be useful in evaluations of path finding algorithms for road networks since the two networks share some common characteristics.

Orientador: Alexandre Xavier Falcão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T04:47:21Z (GMT). No. of bitstreams: 1 Miranda_PauloAndreVechiattode_M.pdf: 1474898 bytes, checksum: 3192aa5b0651e9bcf506aa8b6b5d5b9e (MD5) Previous issue date: 2006 / Resumo: Apesar do progresso das _ultimas duas décadas, o problema de segmentação de imagens continua sendo um dos mais difíceis desafios em análise de imagens. Mais especificamente, métodos de segmentação precisos são normalmente complexos, caros computacionalmente, dependentes de aplicação, e freqüentemente exigem interação humana. Estamos pesquisando métodos de segmentação interativa de imagens que reduzem a intervenção do usuário a simples escolha de poucos pixels na imagem. Buscamos minimizar o número de interações de forma que a automação se torne possível em algumas aplicações onde esses pixels podem ser identificados automaticamente. A metodologia adotada usa a transformada imagem floresta (IFT - Image Foresting Transform) - uma ferramenta geral para modelar, implementar e avaliar operadores de processamento de imagens baseados em conexidade. A IFT reduz o problema de processamento de imagem ao cálculo de uma floresta de caminhos de custo mínimo no grafo derivado da imagem. Nesse trabalho são apresentadas três novas técnicas de segmentação baseadas na IFT / Abstract: Despite of the progress over the last two decades, image segmentation remains one of the most difficult challenges in image analysis. More specifically, accurate segmentation methods are likely to be complex, computationally expensive, application-dependent, and often require considerable human interaction. We have investigated methods for interactive segmentation that reduce user intervention to simple selection of a few pixels in the image. We are interested in minimizing the user involvement such that automation becomes feasible for some applications where these pixels may be automatically identified. The adopted methodology uses the framework of the image foresting transform (IFT) - a general tool for the design, implementation, and evaluation of image processing operators based on connectivity. The IFT reduces image processing problems into a minimum-cost path forest problem in a graph derived from the image. In this work, we present three new segmentation methods based on the IFT / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

This masters'sthesis deals with graph theory and utilization of this theory for design and optimization of data network structures. Introduction chapter describes graph theory in general view, i.e. fundamental terms used for graph description, graph distinguishing, etc. Next part describes graph algorithms, for example a shortest path finding. After this I write about actual routing protocols where the graph algorithms are used. Last but one part deals with queuing theory and final part describes practical presentation of using graph theory for design and optimization of data network structure in Matlab programme environment.

This work focuses on path planning for an autonomous UAV to tour and cover multiple regions in the shortest time. The three challenges to be solved are - finding the right optimal order to tour the neighborhoods, determining entry and exit points to neighborhoods, and covering each neighborhood. Two approaches have been explored and compared to achieve this goal - a TSP - Greedy and TSP - Dijkstra's. Both of them use a TSP solution to determine the optimal order of touring. They also use the same back and forth motion to cover each region. However, while the first approach uses a brute force to determine the the next closest node of entry or exit, the second approach utilizes the Dijkstra's algorithm to compute all possible paths to every node in the graph, and therefore choose the shortest pairs of entry and exit for each region, that would generate the shorter path, overall. The main contribution of this work is to implement an existing algorithm to combine the touring and covering problem, and propose a new algorithm to perform the same. Empirical results comparing performances of both approaches are included. Hardware experiments are performed on a spraying hexacopter, using the TSP - Greedy approach. Unique system characteristics are studied to make conclusions about stability of the platform. Future directions are identified to improve both software and hardware performance. / Master of Science

Made available in DSpace on 2014-06-11T19:24:42Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-12-16Bitstream added on 2014-06-13T19:52:21Z : No. of bitstreams: 1 silva_isr_me_botfca.pdf: 1100428 bytes, checksum: 826dc0fb9625c7e450be2699f43ec0bd (MD5) / A atual preocupação com o meio ambiente tem feito com que empresas produtoras de cana-de-açúcar invistam na mudança do sistema de colheita. Essa mudança consiste na redução da queima do canavial na pré-colheita e na utilização do corte mecanizado com cana crua. Porém, a colheita com corte mecanizado torna disponível a biomassa residual e sem as queimadas e com o maior acúmulo do palhiço sobre o solo, criamse condições favoráveis para o aparecimento de parasitas e atraso da brota da cana, comprometendo a próxima safra. Vários autores mostram a viabilidade do uso do palhiço na produção de energia. Pois, além do potencial energético desta biomassa, têm-se como vantagens as questões ambientais, a manutenção de empregos e a substituição dos recursos energéticos de fontes naturais. Mas, as grandes dificuldades ainda encontradas para aproveitamento desse resíduo para geração de energia são o grande número de maquinário envolvido no sistema de coleta deste resíduo e o alto custo que este processo demanda, principalmente o custo com transporte. O presente trabalho tem como objetivo propor aplicações de técnicas matemáticas de otimização para auxiliar o planejamento do recolhimento do palhiço da cana-de-açúcar para aproveitamento na geração de energia, estudando a melhor forma de carregamento dos fardos de palhiço, facilitando o transporte, diminuindo custos e desgastes de maquinários. Para isto, é sugerido o uso de técnicas de agricultura de precisão para mapear o palhiço enfardado, desta forma pode-se definir uma rota para recolher os fardos no campo e transportá-los para o centro de processamento. Para determinação da rota, propõe-se o uso do algoritmo de menor caminho da teoria de grafos, utilizando uma variação do algoritmo de Dijkstra. / The current concern with the environment has made sugar cane growers invest in changing their harvesting system. This change consists of the reduced burning of cane fields before harvesting and the use of mechanized cutting for raw canes. However, mechanized harvesting makes residual biomass available and, without the burning, the major accumulation of crop residue on the ground, creating favorable conditions for the emergence of parasites and delay of new shoots, affecting the next crop. Several authors show the feasibility of using crop residue for energy production. Besides the energy potential of the biomass, there are advantages for the environmental issues, preservation of jobs and the replacement of energy resources from natural sources. But the great difficulties still found in using this residue for power generation are the large number of machinery involved in the collection system of the waste and the high costs of this process, mainly transport costs. This paper aims to propose applications of mathematical optimization techniques to help plan the collection of sugar cane crop residue to be used for power generation, by studying the best way of loading bales of crop residue, making it easy to transport them, therefore reducing costs and wear on machinery. For this, we suggested the use of techniques of Precision Agriculture to map the baled crop residue, which allows you to define a route to pick up the bales in the field and transport them to the processing center. To determine the route, it is proposed to use the shortest path algorithm from graph theory, using a variation of Dijkstra's algorithm.

"At Face Value: Investigating Perception through Portraiture" is a body of work that examines how people process their perception in imagery. The Deadpan Aesthetic, photographic truth and American identity are discussed, as well as the amount of influence a photographer has in his work. Since perception is defined as an understanding of setting via the senses, I hope to challenge viewers by employing strategies to destabilize the viewer's reception of my photographs.

Cette recherche prend comme objet d’étude le portrait photographique de Rineke Dijkstra, artiste néerlandaise née en 1959. Cette recherche vise à cerner la présence ainsi qu’à déterminer le sens de l’humanisme de cette approche photographique. Une analyse de la série de portraits Beach, réalisée durant la dernière décennie du vingtième siècle, est à la base de cette argumentation. Ce mémoire s’intéresse à l’analyse du portrait et ses rapports au temps, à la culture d’une époque et à la réalité sociale d’un épisode historique. L’étude du portrait de Rineke Dijkstra, tout comme le discours de celle-ci, rend compte d’un humanisme qui s’avère insister sur la représentation de la fragilité humaine. Par une revalorisation de l’«humain», le portrait de l’artiste se distingue des démarches formelles et conceptuelles du portrait contemporain, lesquelles privilégient, entre autres, un déni de la subjectivité de l’individu portraituré. L’expérience perceptive du spectateur, face au portrait de la série Beach, montre que ce portrait renvoie l’image de l’humanité du spectateur. / This present thesis, which studies the photographic portrait of Rineke Dijkstra, Dutch artist born in 1959, supports the hypothesis and explains the presence and the meaning of humanism in this photographic approach. The in-depth analysis of the Beach portraits series, created during the last decade of the twentieth century, is the base on which the arguments are elaborated. This thesis seeks answers through the analysis of the portraits and its relations with time, culture and social reality of a historical episode. The study of Rineke Dijkstra’s portraits and of her work’s discussions reveals a humanism which seems to insist on human fragility. By valuing what is deeply human in the portrait, the artist’s work distinguishes itself from the formal and conceptual approaches of the contemporary portrait which tend to a denial of the subjectivity. The perceptive experience of the viewer facing the Beach portraits series seems to reveal that the portrait returns the image of the viewer’s humanity.