O objetivo deste trabalho é identificar regiões urbanas homogêneas por meio da aplicação de duas vertentes da análise espacial: a estatística espacial e uma estratégia de modelagem espacial baseada na comparação de informações oriundas de diferentes entidades espaciais, em níveis diversos de informação. Um método baseado em fluxos de viagens seria a melhor alternativa para o problema em questão, mas não há dados disponíveis para sua aplicação no Brasil. Em virtude disso, o método aqui apresentado identifica regiões que podem ser consideradas como uniformes em relação a uma variável a partir de técnicas de análise exploratória de dados espaciais, como por exemplo, o gráfico e o mapa de Moran. Em um estudo de caso para o estado de São Paulo, analisando-se as distribuições espaciais dos valores da densidade populacional por meio de sua representação em mapas temáticos classificados segundo os quadrantes do gráfico de Moran (ou box map), esse indicador permite caracterizar razoavelmente bem as regiões urbanas homogêneas existentes (inclusive as oficiais). Entretanto, ao tentar representar o seu comportamento em uma análise temporal por meio de modelos, o indicador populacional não foi capaz de descrever esse comportamento e, conseqüentemente, não serviu para elaborar estratégias de previsão para o futuro. Por outro lado, ao combinar essas informações com um indicador que representa a oferta de transportes, os resultados obtidos permitiram observar o alto desempenho dos modelos, dada a forte influência recíproca entre uso e ocupação do solo e oferta de transportes. Ao permitir a identificação de padrões e a projeção de tendências, este tipo de análise pode ser útil para o planejamento urbano e regional, tanto no contexto estudado como em uma visão mais abrangente. / The objective of this work is to identify homogeneous urban regions through the application of two branches of spatial analysis: spatial statistics and a modeling strategy based on the comparison of information from different spatial entities and at distinct levels. A commuting-based approach would be the best alternative in that case, but there is no data available for its application in Brazil. Thus, the method presented here identifies uniform regions regarding a particular variable through exploratory spatial data analysis techniques, such as the Moran scatter plot and box maps. In a case study carried out in the state of São Paulo, in which the spatial distribution of the values of population density was analyzed through the representation in box maps, a reasonable identification of the existing homogeneous urban regions (including the official ones) was performed. However, the models based only on the population density distribution did not perform well for analyses through time and therefore they were not adequate for forecasting strategies. In contrast, when combining population density information with an indicator of transportation supply the performance of the models was noticeably improved, what was likely caused by the strong reciprocal influence between land use and transportation supply. As a conclusion, the method developed in this work shall be useful for urban and regional planning at different scales, given its potential for patterns recognition and trends forecasting.

Este trabalho aborda a utilização do método de Lattice Boltzmann como ferramenta de simulação para a área de dinâmica de fluidos. Além disso, apresenta o programa LBSim desenvolvido durante o período de pesquisa, construído para ser flexível e extensível (através do emprego de técnicas de orientação a objetos) e com uma interface gráfica mais amigável do que outros projetos semelhantes. Como resultado deste trabalho, o software LBSim implementa uma série de módulos diferentes que utilizam o método de Lattice Boltzmann como base, permitindo a simulação de casos monofásico, multifásico, multicomponente, com suporte à gravidade, meios porosos, difusão, transferência de calor e paredes deslizantes. / This work approaches the use of the Lattice Boltzmann method as a simulation tool for the fluid dynamics area. Beyond that, it presents the LBSim software, developed during the period of the research and built to be flexible and extensible (through the application of techniques of the object oriented paradigm) and with a graphical interface more friendly than other similar projects. As a result of this work, the LBSim software implements a series of different modules that uses the Lattice Boltzmann method as a base, allowing the simulations of the following cases: monophase, multiphase, multicomponent, with support of gravity, porous media, diffusion, heat transfer and moving walls.

O desenvolvimento das cidades freqüentemente propicia o aparecimento de empreendimentos de grande porte que, juntamente com o aumento da população e dos veículos, causam impactos nos sistemas de transportes. Dado que há fortes indícios que a localização e o porte destes empreendimentos, aqui denominados de pólos geradores de viagens (ou PGVs), seja influenciado pela presença de outros PGVs, o objetivo deste trabalho foi avaliar esta hipótese em uma cidade média brasileira, através de duas vertentes da análise espacial: a estatística espacial e a modelagem espacial baseada na comparação de informações oriundas de diferentes entidades espaciais. Foram utilizados conceitos de análise exploratória de dados espaciais, tais como o índice e o diagrama de espalhamento de Moran, para a delimitação de regiões similares, divididas de modo a indicar pontos de associação espacial, em relação a uma variável analisada. Em seguida, a modelagem espacial foi feita com uma adaptação da técnica de cellular automata, usando redes neurais artificiais. Dois modelos foram propostos e aplicados em um estudo de caso na cidade de Campinas, São Paulo, com base em diferentes variáveis. No primeiro modelo, somente variáveis representativas da ocupação comercial foram consideradas, enquanto que, no segundo modelo, foram introduzidas também variáveis caracterizando a infra-estrutura viária. Os resultados permitem observar um bom desempenho dos modelos, em particular na fase de validação. As projeções futuras obtidas com os modelos, no entanto, não parecem caracterizar adequadamente o surgimento, que seria naturalmente esperado, de novos pólos comerciais ao redor dos shopping centers estudados. Essa limitação foi surpreendentemente mais evidente no caso do modelo com variáveis de infra-estrutura viária. / The development of cities often leads to the development of large business areas. Those areas, together with the growth of population and vehicles figures in the entire urban area, produce several impacts in the transportation systems. Given the evidences that the location and size of new trip generators (TG\'s) may be strongly influenced by existing TG\'s, the objective of this study was to evaluate that hypothesis in a brazilian medium-sized city. Two branches of spatial analysis were explored in the present study while dealing with different sources of spatial information. They were: spatial statistics and spatial modeling. Firstly, concepts of exploratory spatial data analyses (ESDA), like Moran\'s I index and scatterplot, were used to characterize regions of similar behavior in terms of particular variables. Secondly, spatial modeling was carried out using cellular automata concepts and artificial neural networks. Two models were proposed and applied in a case study carried out in the city Campinas, São Paulo, based on different variables. In the first model, only variables representing commercial land use were considered, while in the second model variables representing the transportation infrastructure supply were also added. The results found indicate a good performance of the models, particularly in the validation process. Their future projections, however, are apparently not able to represent the development of new commercial activities that would be naturally expected around the shopping malls investigated. Although that limitation was observed in both models, it was surprisingly more evident in the case of the model with variables of transportation infrastructure.

O objetivo deste trabalho é identificar regiões urbanas homogêneas por meio da aplicação de duas vertentes da análise espacial: a estatística espacial e uma estratégia de modelagem espacial baseada na comparação de informações oriundas de diferentes entidades espaciais, em níveis diversos de informação. Um método baseado em fluxos de viagens seria a melhor alternativa para o problema em questão, mas não há dados disponíveis para sua aplicação no Brasil. Em virtude disso, o método aqui apresentado identifica regiões que podem ser consideradas como uniformes em relação a uma variável a partir de técnicas de análise exploratória de dados espaciais, como por exemplo, o gráfico e o mapa de Moran. Em um estudo de caso para o estado de São Paulo, analisando-se as distribuições espaciais dos valores da densidade populacional por meio de sua representação em mapas temáticos classificados segundo os quadrantes do gráfico de Moran (ou box map), esse indicador permite caracterizar razoavelmente bem as regiões urbanas homogêneas existentes (inclusive as oficiais). Entretanto, ao tentar representar o seu comportamento em uma análise temporal por meio de modelos, o indicador populacional não foi capaz de descrever esse comportamento e, conseqüentemente, não serviu para elaborar estratégias de previsão para o futuro. Por outro lado, ao combinar essas informações com um indicador que representa a oferta de transportes, os resultados obtidos permitiram observar o alto desempenho dos modelos, dada a forte influência recíproca entre uso e ocupação do solo e oferta de transportes. Ao permitir a identificação de padrões e a projeção de tendências, este tipo de análise pode ser útil para o planejamento urbano e regional, tanto no contexto estudado como em uma visão mais abrangente. / The objective of this work is to identify homogeneous urban regions through the application of two branches of spatial analysis: spatial statistics and a modeling strategy based on the comparison of information from different spatial entities and at distinct levels. A commuting-based approach would be the best alternative in that case, but there is no data available for its application in Brazil. Thus, the method presented here identifies uniform regions regarding a particular variable through exploratory spatial data analysis techniques, such as the Moran scatter plot and box maps. In a case study carried out in the state of São Paulo, in which the spatial distribution of the values of population density was analyzed through the representation in box maps, a reasonable identification of the existing homogeneous urban regions (including the official ones) was performed. However, the models based only on the population density distribution did not perform well for analyses through time and therefore they were not adequate for forecasting strategies. In contrast, when combining population density information with an indicator of transportation supply the performance of the models was noticeably improved, what was likely caused by the strong reciprocal influence between land use and transportation supply. As a conclusion, the method developed in this work shall be useful for urban and regional planning at different scales, given its potential for patterns recognition and trends forecasting.

O desenvolvimento das cidades freqüentemente propicia o aparecimento de empreendimentos de grande porte que, juntamente com o aumento da população e dos veículos, causam impactos nos sistemas de transportes. Dado que há fortes indícios que a localização e o porte destes empreendimentos, aqui denominados de pólos geradores de viagens (ou PGVs), seja influenciado pela presença de outros PGVs, o objetivo deste trabalho foi avaliar esta hipótese em uma cidade média brasileira, através de duas vertentes da análise espacial: a estatística espacial e a modelagem espacial baseada na comparação de informações oriundas de diferentes entidades espaciais. Foram utilizados conceitos de análise exploratória de dados espaciais, tais como o índice e o diagrama de espalhamento de Moran, para a delimitação de regiões similares, divididas de modo a indicar pontos de associação espacial, em relação a uma variável analisada. Em seguida, a modelagem espacial foi feita com uma adaptação da técnica de cellular automata, usando redes neurais artificiais. Dois modelos foram propostos e aplicados em um estudo de caso na cidade de Campinas, São Paulo, com base em diferentes variáveis. No primeiro modelo, somente variáveis representativas da ocupação comercial foram consideradas, enquanto que, no segundo modelo, foram introduzidas também variáveis caracterizando a infra-estrutura viária. Os resultados permitem observar um bom desempenho dos modelos, em particular na fase de validação. As projeções futuras obtidas com os modelos, no entanto, não parecem caracterizar adequadamente o surgimento, que seria naturalmente esperado, de novos pólos comerciais ao redor dos shopping centers estudados. Essa limitação foi surpreendentemente mais evidente no caso do modelo com variáveis de infra-estrutura viária. / The development of cities often leads to the development of large business areas. Those areas, together with the growth of population and vehicles figures in the entire urban area, produce several impacts in the transportation systems. Given the evidences that the location and size of new trip generators (TG\'s) may be strongly influenced by existing TG\'s, the objective of this study was to evaluate that hypothesis in a brazilian medium-sized city. Two branches of spatial analysis were explored in the present study while dealing with different sources of spatial information. They were: spatial statistics and spatial modeling. Firstly, concepts of exploratory spatial data analyses (ESDA), like Moran\'s I index and scatterplot, were used to characterize regions of similar behavior in terms of particular variables. Secondly, spatial modeling was carried out using cellular automata concepts and artificial neural networks. Two models were proposed and applied in a case study carried out in the city Campinas, São Paulo, based on different variables. In the first model, only variables representing commercial land use were considered, while in the second model variables representing the transportation infrastructure supply were also added. The results found indicate a good performance of the models, particularly in the validation process. Their future projections, however, are apparently not able to represent the development of new commercial activities that would be naturally expected around the shopping malls investigated. Although that limitation was observed in both models, it was surprisingly more evident in the case of the model with variables of transportation infrastructure.

Nesta tese, é discutida a possibilidade de se representar as variações sistêmicas das transições do uso e ocupação do solo, nos períodos compreendidos entre antes e após a construção dos equipamentos públicos denominados de centros educacionais unificados (CEUs). Foram elaborados modelos dinâmicos de simulação, baseados no paradigma de autômatos celulares, e aplicados na área de influência de 10 unidades deste equipamento, observando-se um raio de influência de 2 km. As unidades foram implantadas, em sua maioria, na periferia do município de São Paulo, Brasil. A pesquisa foi feita entre os anos 2000 e 2010, recorte temporal de maior implantação das estruturas, sendo que o recorte abrange as fases de projeto e apresenta avaliações das unidades implantadas. Para a parametrização das simulações de transição do uso e ocupação do solo urbano, foi utilizado o método bayesiano de pesos de evidência. Os resultados foram conclusivos sobre a relação dos centros educacionais unificados com a modificação de padrões e tendências de variação do uso e ocupação do solo no entorno das unidades estudadas. Houve um aumento de 35% nas probabilidades de transição entre as diferentes classes de uso do solo, indicando uma maior dinâmica de modificações após a construção dos centros educacionais unificados. Ainda no período posterior à implantação desta infraestrutura, foi identificada uma intensificação nas transições entre as classes de uso residencial, áreas urbanas vagas e assentamentos urbanos precários, em processos formais e informais de expansão urbana que estão diretamente relacionados com a condição inicial de uso e ocupação do entorno de cada unidade. Foi possível constatar uma explícita diferenciação espacial do processo de urbanização na área de influência de várias unidades, com a análise contínua da formação das manchas de transição das classes de uso em relação às faixas de distância aos CEUs. Nas unidades construídas em áreas com maior vulnerabilidade e precariedade das ocupações, a expansão urbana tende a ser informal e a ultrapassar os limites imobiliários formais, como no caso do CEU Paz, que concentrou o crescimento dos assentamentos urbanos precários nas áreas íngremes e mais próximas à Serra da Cantareira, em uma taxa anual 27% maior no período pós-implantação. A análise da variação da tendência de uso e ocupação entre os períodos de análise possibilitou comparar todas as unidades estudadas, demonstrando que não existe um caráter regional no padrão de modificação, mas sim uma grande heterogeneidade na organização espacial, em conformidade com os padrões da periferia de São Paulo. Por fim, foi possível observar que nem todas as classes de uso sofreram alteração na tendência entre os períodos, fato que confirma que a influência dos CEUs pode variar conforme o contexto de implantação. / In this thesis, a proposal for modelling land use dynamics is conceived, comprising periods immediately before and after the implementation of the so-called unified educational centers (or centros educacionais unificados - CEUs, in Portuguese). Cellular automaton-based models were applied to assess the influence of CEUs in land use change within circular catchment areas of a two-kilometer radius surrounding them. Most of these social infrastructure equipments were implemented at the periphery of São Paulo city, Brazil. The research was carried out between 2000 and 2010, period of intensive implementation of such social equipments. This time span covers the project phases and presents evaluations of the implemented units. For discretizing continuous variables and running the simulations, we used the Bayesian weights of evidence method. The results were conclusive on the relation between the unified educational centers with changes in land use variation patterns and trends around the studied units. There was a 35% increase in the possibilities of transition among the different land use classes, indicating a greater dynamic of change after the unified educational centers construction. Also, in the period after the implementation of this infrastructure, it was identified an intensification in the transitions among the classes of formal residential use, vacant urban plots and informal urban settlements, in formal and informal processes of urban expansion that are directly related to the initial condition of use and occupation found in the surroundings of each unit. It was possible to observe an explicit spatial differentiation of the urbanization process in the catchment area of several units, by means of the continuous analysis of the land use patches formation in relation to the distance ranges to CEUs. In the units built in areas with greater vulnerability and precarious occupations, urban expansion tends to be informal and invade the formal occupation limits, as in the case of CEU Paz, which concentrated the growth of precarious urban settlements in steep areascloser to the Cantareira Ridge, at a 27% higher yearly rate in the second period, i.e. after the CEU Paz construction. The trend variation analysis between the periods made it possible to compare all the studied units, demonstrating that there is no regional character in the modification pattern, but rather a great heterogeneity in the spatial organization, in accordance with patterns found at the periphery of São Paulo. Finally, it was possible to observe that not all land use classes suffered transition trend changes between the periods, confirming that the influence of the unified educational centers may vary according to the local context.

Title: Interactive Processing of Volumetric Data Author: Jan Kolomazník Department: Department of Software and Computer Science Education Supervisor: RNDr. Josef Pelikán, Department of Software and Computer Science Education Abstract: Interactive visualization and segmentation of volumetric data are quite lim- ited due to the increased complexity of the task and size of the input data in comparison to two-dimensional processing. A special interactive segmentation workflow is presented, based on minimal graph-cut search. The overall execution time was lowered by implementing all the computational steps on GPU, which required a design of massively parallel algorithms (using thousands of threads). To lower the computational burden even further the graph is constructed over the image subregions com- puted by parallel watershed transformation. As a suitable formalism for a range of massively parallel algorithms was chosen cellular automata. A set of cellular automata extensions was defined, which allows efficient mapping and computation on GPU. Several variants of parallel watershed transformation are then defined in the form of cellular automaton. A novel form of 2D transfer function was presented, to improve direct volume visualization of the input data, suited for discriminating image features by their shape and...

Neste trabalho demonstramos que padrões e aleatoriedade estão intimamente relacionados, ao contrário do que intuitivamente é considerado como campos opostos. Esta abordagem visa dois propósitos: por um lado, obter vantagens das propriedades caóticas para medir pseudo-aleatoriedade, e por outro lado, extrair padrões de diagramas espaço-tempo como método de reconhecimento de padrões. Este trabalho centrou-se em dois métodos relacionados com sistemas complexos, como sistemas dinâmicos de tempo discreto, redes complexas, autômatos celulares (AC) e suas combinações. O primeiro método foi explorar as propriedades das profundezas do caos como fonte de pseudo-aleatoriedade a partir de sistemas dinâmicos caóticos, como o mapa logístico e o mapa da tenda. Observamos que os padrões desaparecem e a pseudo-aleatoriedade é aumentada pela remoção de k dígitos à direita da vírgula dos pontos de uma órbita original de um mapa caótico. Portanto, foi encontrada uma fonte caótica interessante para obter geradores de números de pseudo-aleatórios (PRNGs) parametrizada por k. Um segundo método foi proposto com base na incorporação de autômatos celulares na topologia de rede, também chamada de rede-autômato, visando caracterizar as redes a partir da dinâmica espaço-temporal intrínseca dessas redes. Quatro problemas de grande demanda foram explorados, tais como (i) identificar redes sociais online; (ii) identificar organismos de diferentes domínios da vida através de suas redes metabólicas; (iii) classificar padrões de distribuição de estômatos variando de acordo com diferentes condições ambientais; e (iv) o problema de identificação de autoria. Finalmente, essa mesma abordagem foi utilizada para analisar as sequências de números pseudo-aleatórios gerados pelo padrão ouro do k-mapa logístico no contexto do reconhecimento de padrões. A abordagem proposta permitiu explorar padrões e pseudoaleatoriedade extraídos de uma miríade de sistemas com resultados bem-sucedidos em termos de acerto e boa pseudo-aleatoriedade. Além disso, este trabalho trouxe consigo progressos significativos em aplicações de reconhecimento de padrões do mundo real de um amplo ramo de campos como criptografia, criptoanálise, biologia e ciência dos dados. / In this work, we demonstrate that patterns and randomness are close related, contrary to what intuitively is considered as opposite fields. We aimed for a pattern recognition approach that aims for two purposes: (i) to take advantages from the chaotic properties as a source of pseudo-randomness in order to measure pseudo-randomness and (ii) to extract patterns from spatio-temporal diagrams obtained from complex systems models as a pattern recognition method. This work has focused on different complex systems such as discrete dynamical systems, complex networks, cellular automata (CA), and their combinations. The first method was to explore the chaotic properties in a deep-zoom manner as a source of pseudo-randomness from chaotic dynamical systems such as the logistic map and the tent map. We observed that the patterns vanish and therefore pseudo-randomness is increased by removing k right digits from the original orbit sequences. Therefore, we found an interesting chaotic source to obtain pseudo-randomness number generators (PRNGs). A second method was proposed based on the embedding of cellular automata (CA) over a network topology, also called network automata, aiming to characterize networks from the intrinsic spatio-temporal dynamics of these networks. Various on-demand problems were explored such as (i) identifying online social networks; (ii) identifying organisms from distinct domains of life through their metabolic networks; (iii) classifying stomata distribution patterns varying according to different environmental conditions; and (iv) the authorship identification problem. Finally, this same approach was used to analyze the sequences of pseudo-random numbers generated by the gold standard k-logistic map in the context of pattern recognition. So far, the proposed pattern recognition approach based on non-linear systems allowed us to explored patterns and pseudo-randomness extracted from a myriad of systems with successful results in terms of accuracy and good pseudorandomness. The proposed method has made significant progress in real-world pattern recognition applications from a wide branch of fields such as Cryptography, Cryptanalysis, Biology and Data Science.

Nesta dissertação foram estudados alguns modelos vetoriais que pretendem modelar e descrever alguns aspectos de sistemas sociais e de sua organização cultural. Partimos do modelo de Axelrod, um processo estocástico definido em uma rede, e introduzimos uma pequena alteração no modelo que desencadeou mudanças qualitativas interessantes, especialmente o surgimento de uma tensão superficial, que leva ao aparecimento de estados metaestáveis e de regiões culturais mais fixamente localizadas no espaço. Através da ótica da mecânica estatística e de extensas simulações computacionais, exploramos alguns dos aspectos que julgamos mais importantes na caracterização desse rico modelo. / Axelrod\'s model for cultural dissemination is a discrete vector representation for modeling social and cultural systems. In this work we have studied it and other related models, and a subtle change in the model\'s rule was proposed. Our slight alterations to the model yielded significant qualitative changes, specifically the emergence of surface tension, driving the system to metastable states. Using concepts from statistical mechanics and extensive numerical simulations, we explored some of the aspects that better describe the rich model devised, such as its transient and stationary behaviour.

The new Field Programmable Gate Array (FPGA) technologies and their structures have opened up new approaches to logic design and synthesis. The main feature of an FPGA is an array of logic blocks surrounded by a programmable interconnection structure. Cellular FPGAs are a special class of FPGAs which are distinguished by their fine granularity and their emphasis on local cell interconnects. While these characteristics call for specialized synthesis tools, the availability of logic gates other than Boolean AND, OR and NOT in these architectures opens up new possibilities for synthesis. Among the possible realizations of Boolean functions, XOR logic is shown to be more compact than AND/OR and also highly testable. In this dissertation, the concept of structural regularity and the advantages of XOR logic are used to investigate various synthesis approaches to cellular FPGAs, which up to now have been mostly nonexistent. Universal XOR Canonical Forms, Two-level AND/XOR, restricted factorization, as well as various Directed Acyclic Graph structures are among the proposed approaches. In addition, a new comprehensive methodology for the investigation of all possible XOR canonical forms is introduced. Additionally, a new compact class of XOR-based Decision Diagrams for the representation of Boolean functions, called Kronecker Functional Decision Diagrams (KFDD), is presented. It is shown that for the standard, hard, benchmark examples, KFDDs are on average 35% more compact than Binary Decision Diagrams, with some reductions of up to 75% being observed.