Orientador: Aluir Porfirio Dal Poz / Resumo: Este trabalho propõe uma solução para o problema de verificação automática da malha viária georreferenciada em imagens aéreas digitais. O método proposto baseia-se em duas etapas básicas, isto é: 1- Extração automática de rodovias georreferenciadas; e 2- Análise de consistência das rodovias extraidas. Na primeira etapa, a metodologia para a extração de rodovias baseada no algoritmo de programação dinâmica é utilizada para a extração automática das rodovias georreferenciadas. O método é inicializado a partir da projeção de pontos salientes extraidos automaticamente ao longo destas rodovias para o espaço Imagem. Estes pontos descrevem grosseiramente a forma, a posição, e a topologia das rodovias georreferenciadas. Além disso, a precisão dos pontos transformados para o espaço imagem é também estimada, o que possibilita a definição automática das janelas debusca utilizadas pelo algoritmo de programação dinâmica. A análise de consistência das rodovias extraidas baseia-se num modelo de erro que permite concluir estatisticamente se as rodovias extraidas não discrepam significativamente das correspondentes projetadas na imagem. Os resultados obtidos mostram...(Resumo completo, clicar acesso eletrônico abaixo) / Mestre

Made available in DSpace on 2014-06-11T19:23:31Z (GMT). No. of bitstreams: 0 Previous issue date: 2005Bitstream added on 2014-06-13T19:50:21Z : No. of bitstreams: 1 silva_mao_me_prud_prot.pdf: 2133151 bytes, checksum: a54be88723cd614f467fb0f56a173b46 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Este trabalho propõe uma solução para o problema de verificação automática da malha viária georreferenciada em imagens aéreas digitais. O método proposto baseia-se em duas etapas básicas, isto é: 1- Extração automática de rodovias georreferenciadas; e 2- Análise de consistência das rodovias extraidas. Na primeira etapa, a metodologia para a extração de rodovias baseada no algoritmo de programação dinâmica é utilizada para a extração automática das rodovias georreferenciadas. O método é inicializado a partir da projeção de pontos salientes extraidos automaticamente ao longo destas rodovias para o espaço Imagem. Estes pontos descrevem grosseiramente a forma, a posição, e a topologia das rodovias georreferenciadas. Além disso, a precisão dos pontos transformados para o espaço imagem é também estimada, o que possibilita a definição automática das janelas debusca utilizadas pelo algoritmo de programação dinâmica. A análise de consistência das rodovias extraidas baseia-se num modelo de erro que permite concluir estatisticamente se as rodovias extraidas não discrepam significativamente das correspondentes projetadas na imagem. Os resultados obtidos mostram...

Orientador: Aluir Porfírio Dal Poz / Coorientador: José Roberto Nogueira / Banca: Messias Meneguette Júnior / Banca: Evandro Luis Linhari Rodrigues / Resumo: Este trabalho propõe um método de extração de contornos de telhados convexos de edifícios a partir de dados de um Modelo Digital de Superfície normalizado (MDSn). A modelagem do contorno se dará através do modelo de snake balloon, onde um funcional de energia dependente de muitas variáveis será otimizado através do algoritmo de Programação Dinâmica (PD). O MDSn se mostra atrativo na aplicação de extração de contornos de telhados de edifícios, pois permite separar as regiões de edifícios da maioria das outras regiões, principalmente as mais baixas. O modelo de snake balloon pode ser interpretado como uma curva poligonal fechada que se deforma sob a ação de forças internas e externas agindo sobre o modelo. O método proposto neste trabalho utiliza algumas características apresentadas pelo MDSn para desenvolver uma estratégia de solução do problema de otimização. Uma dessas características está ligada ao fato de que os contornos de telhados de edifícios no MDSn estão associados com grandes desníveis e os pontos representativos do contorno apresentam-se sobre o edifício. Assim, para dar início ao processo de extração, bastaria colocar um único ponto semente sobre o telhado. Tal ponto se expandiria, tornando-se uma curva poligonal fechada. Até que a curva encontre o limite do telhado são necessárias várias etapas... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work proposes a method for building convex-roof contours extraction from data of a normalized Digital Surface Model (nDSM). The contour modeling will be made by the snake balloon model, where an energy functional depending on many variables will be optimized through the Dynamic Programming algorithm (DP). The nDSM proves to be attractive in the application of building roof contour extraction, as it allows separating buildings regions from mostly other regions, especially the lowest ones. The snake balloon model can be interpreted as an polygonal closed curve that deforms under the action of internal and external forces acting on the model. The method proposed in this work uses some of the features presented by nDSM in order to develop a strategy to solve an optimization problem. One of these characteristics is related to the fact that building roof contours in a nDSM are associated with large elevation differences and representative points of the contour are presented over the building. So, to start the extraction process, it would be enough to place a single seed point on the roof. The point would expand and become a polygonal closed curve. Until the curve find the edge of the roof, several expansion stages are required... (Complete abstract click electronic access below) / Mestre

Made available in DSpace on 2014-06-11T19:27:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-31Bitstream added on 2014-06-13T20:35:12Z : No. of bitstreams: 1 thomaz_dv_me_prud.pdf: 533928 bytes, checksum: dedbbd2d4b546fad0cc5523740496b61 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho propõe um método de extração de contornos de telhados convexos de edifícios a partir de dados de um Modelo Digital de Superfície normalizado (MDSn). A modelagem do contorno se dará através do modelo de snake balloon, onde um funcional de energia dependente de muitas variáveis será otimizado através do algoritmo de Programação Dinâmica (PD). O MDSn se mostra atrativo na aplicação de extração de contornos de telhados de edifícios, pois permite separar as regiões de edifícios da maioria das outras regiões, principalmente as mais baixas. O modelo de snake balloon pode ser interpretado como uma curva poligonal fechada que se deforma sob a ação de forças internas e externas agindo sobre o modelo. O método proposto neste trabalho utiliza algumas características apresentadas pelo MDSn para desenvolver uma estratégia de solução do problema de otimização. Uma dessas características está ligada ao fato de que os contornos de telhados de edifícios no MDSn estão associados com grandes desníveis e os pontos representativos do contorno apresentam-se sobre o edifício. Assim, para dar início ao processo de extração, bastaria colocar um único ponto semente sobre o telhado. Tal ponto se expandiria, tornando-se uma curva poligonal fechada. Até que a curva encontre o limite do telhado são necessárias várias etapas... / This work proposes a method for building convex-roof contours extraction from data of a normalized Digital Surface Model (nDSM). The contour modeling will be made by the snake balloon model, where an energy functional depending on many variables will be optimized through the Dynamic Programming algorithm (DP). The nDSM proves to be attractive in the application of building roof contour extraction, as it allows separating buildings regions from mostly other regions, especially the lowest ones. The snake balloon model can be interpreted as an polygonal closed curve that deforms under the action of internal and external forces acting on the model. The method proposed in this work uses some of the features presented by nDSM in order to develop a strategy to solve an optimization problem. One of these characteristics is related to the fact that building roof contours in a nDSM are associated with large elevation differences and representative points of the contour are presented over the building. So, to start the extraction process, it would be enough to place a single seed point on the roof. The point would expand and become a polygonal closed curve. Until the curve find the edge of the roof, several expansion stages are required... (Complete abstract click electronic access below)

Orientador : Prof. Dr. Marcelo Rodrigues Bessa / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Engenharia de Recursos Hídricos e Ambiental. Defesa: Curitiba, 11/05/2016 / Inclui referências : f.149-156 / Resumo: A presente dissertação propõe um método para a otimização da operação de usinas hidrelétricas com o objetivo de atender à demanda de eletricidade ao menor custo da complementação termelétrica. Faz-se uso da Programação Dinâmica Estocástica (Stochastic Dynamic Programming - SDP) e a modelagem se dá por meio de um Processo de Decisão de Markov (Markov Decision Process - MDP). O intuito é ava-liar a aplicação da SDP desenvolvida em uma linguagem de programação vetorial, o Matlab©. As usinas hidrelétricas são mantidas individuais para que suas característi-cas possam ser detalhadas, enquanto a complementação termelétrica é determina-da por uma função de custo. O MDP tem horizonte finito de sessenta meses. As va-riáveis de estado são os níveis de reservatório discretizados e as classes de vazões afluentes. As variáveis de decisão são as vazões turbináveis discretizadas. A matriz de transição do MDP calcula as probabilidades de que uma determinada classe de vazões afluentes ocorra, dadas as ocorrências das classes no mês anterior. O códi-go foi escrito de modo a usar, sempre que possível, vetores e matrizes, evitando la-ços, para potencializar as características da linguagem vetorial. São cinco as usinas hidrelétricas consideradas para o estudo de caso, todas em cascata no rio Iguaçu: dois reservatórios e três usinas a fio d'água, sendo que as usinas do rio Jordão, afluente do Iguaçu, não estão incluídas. Produzida como resultado da otimização, uma tabela de decisões é entregue a um simulador, alimentado pela série histórica. Os resultados da simulação são comparados ao simulador MSUI. O otimizador pro-posto alcançou geração média superior na cascata, deplecionando mais os reserva-tórios, especialmente o de cabeceira, e reduzindo vertimentos. Como as afluências do rio Iguaçu não são sazonais, o nível médio dos reservatórios é mantido entre 50% e 60%. Por fim, foram realizadas medidas de desempenho computacional, tan-to em velocidade de processamento como em alocação de memória. A memória tor-na-se o fator limitante com relação ao tempo computacional, mostrando que o códi-go usa a capacidade de processamento matricial para acelerar sua execução. PALAVRAS-CHAVE: programação dinâmica estocástica, otimização da operação de usinas, processos de decisão de Markov, linguagem vetorial, Rio Iguaçu. / Abstract: This dissertation proposes a method for the optimization of hydropower plants operation in order to meet demand at the lowest cost of the complementary thermoelectric production. Makes use of Stochastic Dynamic Programming - SDP and modeling is made through a Markov Decision Process - MDP. The aim is to evaluate the implementation of the SDP in the code written in a vector programming language, Matlab©. Hydroelectric plants are kept individual so that their characteris-tics can be detailed, while the thermal complementation is determined by a cost func-tion. The MDP has finite horizon of sixty months, the state variables are the discre-tized reservoir levels and the inflows classes. The decision variables are the discre-tized possible turbine flows. The MDP's transition matrix calculates the probabilities that a certain class of affluent flows occur, given that certain classes had ocurred in the previous month. The code was written to use, whenever possible, vectors and matrixes, avoiding loops in order to enhance the characteristics of the vector pro-gramming language. There are five hydroelectric plants considered for the case study, all cascaded on the Iguaçu River: two reservoirs that can regularize their out-flow, and three that cannot. The power plants of the Jordão River, Iguaçu affluent, are not included. Produced as a result of optimization, a table of decisions is given to a simulator, running the historical series. The results are compared to MSUI simula-tor. The proposed optimizer achieved higher average generation in the cascade, more depleted reservoirs, especially the first one in the cascade, and reduced spills. As the affluences of the Iguaçu River are not seasonal, the average level of the res-ervoirs is maintained between 50% and 60%. Finally, computational performance measurements were performed both in processing speed as memory allocation. The memory becomes the limiting factor prior to the computational time showing that the vectorial code uses the processing capability to accelerate its execution. KEYWORDS: stochastic dynamic programming, optimization of power plant opera-tion, Markov decision processes, vector language, Iguaçu River.

Orientador : Renato Carmo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 21/08/2017 / Inclui referências : p. 81-83 / Resumo: O problema de coloração de grafos consiste em particionar os vértices de um grafo na menor quantidade possível de conjuntos independentes. Este trabalho tem como objetivo agrupar e contextualizar alguns dos principais algoritmos para o problema de coloração de grafos, reunindo num mesmo texto informações que se encontram espalhadas pela literatura técnica sob a forma de artigos científicos. Discutimos os principais métodos apresentados na literatura para o problema de coloração de grafos, a saber, soluções baseadas em Programação Linear Inteira, Branch-and-Bound e Programação Dinâmica. Palavras-chave: Teoria dos Grafos, Coloração de Grafos, Algoritmos Exatos. / Abstract: The graph coloring problem is the problem of partitioning the vertices of a graph into the smallest possible set of independent sets. The goal of this work is to group and contextualize some of the main algorithms for the graph coloring problem, bringing into a single text information which is scattered in the technical literature in scientific papers. We discuss the main methods in the literature for the graph coloring problem, namely, solutions based on Integer Linear Programming, Branch-and-Bound and Dynamic Programming. Keywords: Graph Theory, Graph Coloring, Exact Algorithms.

Made available in DSpace on 2015-01-26T13:21:28Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-12-16Bitstream added on 2015-01-26T13:30:23Z : No. of bitstreams: 1 000799108.pdf: 3118264 bytes, checksum: 0fa28a9400a86609ab1833e453e24729 (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Este trabalho apresenta um método semiautomático para a extração de contornos de telhado de edifícios descritos por estruturas retilíneas, a partir da integração de imagens aéreas de alta resolução tomadas sobre cenas urbanas complexas e dados coletados por sistemas de varredura a LASER aerotransportados. As informações tridimensionais fornecidas pelos dados de varredura a LASER e a alta definição dos contornos de telhado nas imagens aéreas de alta resolução podem ser combinadas para possibilitar a obtenção de resultados acurados e confiáveis. O método de extração proposto é formulado em termos de um problema de otimização, no qual um modelo matemático é utilizado para representar os contornos de telhado de edifícios em um referencial do espaço-objeto. A solução para o problema resultante é obtida através da técnica de otimização global por programação dinâmica e corresponde a polígonos tridimensionais representando os contornos de telhado extraídos diretamente no espaço-objeto. O modelo matemático para os contornos de telhado é inicialmente formulado no espaço-imagem, a partir de uma função de energia snakes, e então reformulado de modo a representar os contornos de telhado no espaço-objeto, a partir da integração dos dados de varredura a LASER estruturados na forma de uma rede irregular de triângulos (TIN)... / This research presents a semi-automatic method for rectilinear building roof contours extraction, based on the integration of high resolution aerial imagery taken from dense urban scenes and light detection and ranging (LiDAR) data. 3D information derived from LiDAR data and the high roof contour delineation accuracy in the aerial imagery can be combined in order to accurately extract the building roof contours. The proposed method is organized as an optimization problem, in which a mathematical model is used to represent the building roof contours in an object-space reference frame. The global solution for the resulting problem is found by using the dynamic programming optimization technique and corresponds to 3D polygons describing the building roof contours. The mathematical model describing a building roof contour is firstly expressed in an image-space reference frame, by using a snakes energy function, and then, the resulting snakes-based mathematical model is totally reformulated in such a way to describe building roof contours directly in an object-space reference frame, by integrating the LiDAR data represented as a triangulated irregular network (TIN) structure...

Orientador: Aluir Porfirio Dal Poz / Banca: Edson Aparecido Mitishita / Banca: Raul Queiroz Feitosa / Banca: Maurício Galo / Banca: Messias Meneguette Júnior / Resumo: Este trabalho apresenta um método semiautomático para a extração de contornos de telhado de edifícios descritos por estruturas retilíneas, a partir da integração de imagens aéreas de alta resolução tomadas sobre cenas urbanas complexas e dados coletados por sistemas de varredura a LASER aerotransportados. As informações tridimensionais fornecidas pelos dados de varredura a LASER e a alta definição dos contornos de telhado nas imagens aéreas de alta resolução podem ser combinadas para possibilitar a obtenção de resultados acurados e confiáveis. O método de extração proposto é formulado em termos de um problema de otimização, no qual um modelo matemático é utilizado para representar os contornos de telhado de edifícios em um referencial do espaço-objeto. A solução para o problema resultante é obtida através da técnica de otimização global por programação dinâmica e corresponde a polígonos tridimensionais representando os contornos de telhado extraídos diretamente no espaço-objeto. O modelo matemático para os contornos de telhado é inicialmente formulado no espaço-imagem, a partir de uma função de energia snakes, e então reformulado de modo a representar os contornos de telhado no espaço-objeto, a partir da integração dos dados de varredura a LASER estruturados na forma de uma rede irregular de triângulos (TIN)... / Abstract: This research presents a semi-automatic method for rectilinear building roof contours extraction, based on the integration of high resolution aerial imagery taken from dense urban scenes and light detection and ranging (LiDAR) data. 3D information derived from LiDAR data and the high roof contour delineation accuracy in the aerial imagery can be combined in order to accurately extract the building roof contours. The proposed method is organized as an optimization problem, in which a mathematical model is used to represent the building roof contours in an object-space reference frame. The global solution for the resulting problem is found by using the dynamic programming optimization technique and corresponds to 3D polygons describing the building roof contours. The mathematical model describing a building roof contour is firstly expressed in an image-space reference frame, by using a snakes energy function, and then, the resulting snakes-based mathematical model is totally reformulated in such a way to describe building roof contours directly in an object-space reference frame, by integrating the LiDAR data represented as a triangulated irregular network (TIN) structure... / Doutor

Orientador: Maria do Socorro Nogueira Rangel / Banca: Valeriano Antunes de Oliveira / Banca: Flávio Molina da Silva / Resumo: Nessa dissertação é feito uma revisão das características gerais dos problemas de corte e empacotamento e apresentam-se duas tipologias encontradas da literatura para classificar os problemas. São estudados em detalhes três problemas: (i) o problema da mochila limitada, (ii) o problema de corte bidimensional guilhotinado 2estágios restrito, e (iii) o problema do corte de estoque bidimensional. Para o problema (i) é proposto um algoritmo de programação dinâmica adaptado de um algoritmo proposto na literatura. Esse algoritmo é a base para a proposta de duas estratégias para resolver o problema (ii). Os algoritmos desenvolvidos para o problema (ii) são então usados no processo de geração de colunas usado para resolver o problema de corte de estoque exato. Resultados de um estudo computacional realizado para avaliar o desempenho dos algoritmos propostos usando instâncias da literatura são apresentados e analisados / Abstract: In this dissertation a review of the main characteristics of the Cutting and Packing problems are presented together with a summary of two typologies proposed in the literature to classify the problems. Three problems are studied in detail: (i) the Bounded Knapsack problem, (ii) the constraint two-dimensional guillotine 2-stage cutting problem, and (iii) the two-dimensional cutting stock problem. For problem (i) we propose a dynamic programming algorithm adapted from one given in the literature. This algorithm is the basis for the proposal of two strategies to solve the problem (ii). The algorithms developed for problem (ii) are then used in the column generation process employed to solve the exact cutting stock problem. Results of a computational study conducted to evaluate the performance of the proposed algorithms using instances of the literature are presented and analyzed / Mestre

Orientador: Aluir Porfírio Dal Poz / Resumo: A aquisição de informações espaciais é uma das tarefas mais dispendiosa e morosa na implantação e na manutenção de Sistemas de informação Geográfica (SIG's). Nos últimos 30 anos, inúmeras pesquisas foram realizadas objetivando o melhoramento do tempo e custo da aquisição de dados espaciais. No que se refere a aquisição de dados espaciais a partir de imagens digitais, é possível notar que os métodos desenvolvidos até então estão mais próximos desta meta quando os respectivos níveis de automação são mais altos. Como as soluções totalmente automáticas não estão ainda no mesmo nível de confiabilidade dos métodos manuais, soluções semi-automáticas combinando a habilidade natural de operadores humanos em tarefas de reconhecimento e a capacidade de algoritmos computacionais em realizar tarefas de medidas precisas e morosas, têm sido propostas. Seguindo esta tendência, este trabalho propõe uma metodologia semi-automática para a extração de rodovias em imagens digitais de média e alta resolução baseada no algoritmo de otimização global de programação dinâmica. É importante enfatizar que os trabalhos relacionados com extração de feições através de programação dinâmica sempre usam imagens de baixa resolução, na qual as rodovias manifestam-se como estruturas lineares. Ao contrário, rodovias em imagens de média e alta resolução se manifestam como faixas alongadas. Assim, como neste caso o objetivo básico é extrair o eixo da rodovia, este trabalho propõe uma modificação na função custo usada numa metodologia preexistente baseada em programação dinâmica, permitindo que o eixo central da rodovia seja precisamente extraído pela metodologia modificada. A diferença básica entre este método modificado e o original é uma função de injunção, proposta com o objetivo de incorporar características de bordas de rodovia...(Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The acquisition of spatial information is one of most expensive and time consuming tasks in developing and maintaining Geographical Information Systems (GIS's). In the last 30 years, countless researches have been accomplished aiming at improvement of spatial data acquisition time and cost. Related to the spatial data acquisition from digital images, it is possible to notice that the methods developed until now are closer to that goal when the respective levels of automation are higher. As fully automatic solutions are not in same level of reliability of manual procedures, semi-automatic solutions combining the natural skill of humans operators in recognizing tasks and the power of computational algorithm in carrying out precise and time consuming measurement tasks, have been proposed. Following this trend, this work proposes a semi-automatic methodology for road extraction from mediumand high-resolution digital images based on the global optimization algorithm of dynamic programming. It is important to emphasize that related works on feature extraction by dynamic programming always use low-resolution images, in which roads manifest as linear structures. As opposed to this, roads in medium- and high-resolution manifest as elongated regions. Thus, as in this case the basic objective is to extract the road centerline, this work proposes a modification of cost function used in a preexisting dynamic programming approach, allowing the road centerline to be precisely extracted by the modified method. The basic difference between this modified method and the original one is the proposed constraint function embodying some road edge characteristics, as e.g. the anti-parallelism of gradient vectors at two pixels situated on opposite road edges and belonged to the same road crosssection...(Complete abstract click electronic access below) / Mestre