Estágio realizado no INESC e orientado pelo Eng.º Paulo Jorge da Rocha e Eng.º Silva Sá Marques / Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2008

Dissertation submitted for obtain the degree of Doctor, at the Cranfield Institute of Technology

Dissertação apresentada para obtenção do grau de Doutor, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Prof. Doutor Aurélio de Castro Campilho

Dissertação apresentada para obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Prof. Dr. Eugénio da Costa Oliveira

El color y la textura son dos estímulos visuales importantes para la interpretación de las imágenes. La definición de descriptores computacionales que combinan estas dos características es aún un problema abierto. La dificultad se deriva esencialmente de la propia naturaleza de ambas, mientras que la textura es una propiedad de una región, el color es una propiedad de un punto.Hasta ahora se han utilizado tres los tipos de aproximaciones para la combinación, (a) se describe la textura directamente en cada uno de los canales color, (b) se describen textura y color por separado y se combinan al final, y (c) la combinación se realiza con técnicas de aprendizaje automático. Considerando que este problema se resuelve en el sistema visual humano en niveles muy tempranos, en esta tesis se propone estudiar el problema a partir de la implementación directa de una teoría perceptual, la teoría de los textons, y explorar así su extensión a color.Puesto que la teoría de los textons se basa en la descripción de la textura a partir de las densidades de los atributos locales, esto se adapta perfectamente al marco de trabajo de los descriptores holísticos (bag-of-words). Se han estudiado diversos descriptores basados en diferentes espacios de textons, y diferentes representaciones de las imágenes. Asimismo se ha estudiado la viabilidad de estos descriptores en una representación conceptual de nivel intermedio.Los descriptores propuestos han demostrado ser muy eficientes en aplicaciones de recuperación y clasificación de imágenes, presentando ventajas en la generación de vocabularios. Los vocabularios se obtienen cuantificando directamente espacios de baja dimensión y la perceptualidad de estos espacios permite asociar semántica de bajo nivel a las palabras visuales. El estudio de los resultados permite concluir que si bien la aproximación holística es muy eficiente, la introducción de co-ocurrencia espacial de las propiedades de forma y color de los blobs de la imagen es un elemento clave para su combinación, hecho que no contradice las evidencias en percepción. / Colour and texture are important visual cues for image understanding. The definition of computational descriptors that combine both features is still an open problem. The difficulty is essentially due to the inherent nature of both cues, while texture is a property of a region, colour is a property of a point.Since now three approaches have been used for combining cues, (a) texture is directly described in each one of the colour channels, (b) texture and colour are described separately and combined in a latter step, and (c) the combination is done using machine learning techniques. Considering that this issue is solved at early stages of the human visual system, in this work we propose to study the problem using a direct implementation of a perceptual theory, the texton theory, and to explore its extension to colour.Since texton theory is based on the description of texture by the densities of local attributes, this matches perfectly with an holistic framework where descriptors are based on bag-of-words. Some descriptors based on different textons spaces and different image representations have been studied. Furthermore, the feasibility of these descriptors has also been studied for intermediate levels of image representation.The proposed descriptors have proved high efficiency in retrieval and image classification. They also present some advantages in vocabulary generation. The quantification is done directly on low-dimensional spaces, whose perceptual properties allow low-level semantic associations to the visual words. The results make us to conclude that although the performance of holistic approaches is high, the introduction of spatial co-ocurrence of blob properties, shape and colour, is a key element for their combination. This conclusion agrees with perceptual evidences.

Orientador: Rubén Augusto Romero Lázaro / Banca: Marina Lavorato de Oliveira / Banca: Carlos Roberto Mendonca Rocha / Resumo: Por se tratar de uma tarefa complexa, as instituições passaram a recorrer a diversas metaheurísticas no intuito de resolver um problema árduo e complexo que é a elaboração de grade horária. No Brasil, com o advento do desenvolvimento da microinformática a partir da década de 90, do século XX, esse problema foi tratado com o uso de ferramentas de programação linear e métodos matemáticos baseados em otimização clássica. Posteriormente, passou a ser executado pelas universidades públicas e privadas a partir de propostas computacionais, desenvolvidas para a resolução desse tipo de problema, usando técnicas fundamentadas no uso de metaheurísticas. O presente trabalho visa projetar e implementar computacionalmente um algoritmo tipo VNS (do inglês Variable Neighborhood Search) para resolver o problema de programação de horários em ambientes universitários; realizar uma análise teórica e experimental do desempenho do algoritmo VNS e discutir a aplicação desse algoritmo na otimização de outros problemas da família de problemas do tipo timetabling. Para isso foi desenvolvido um algoritmo de busca em vizinhança variável para resolver um tipo de problema da família timetabling em ambientes universitários. / Abstract: Building of timetables is a hard work to accomplish due to its complexity, so that institutions started to make use of several Metaheuristics for solving timetabling problems. In Brazil, the development of Computer Science from the Nineties, within the late 20th century, allowed to handle this kind of problem with Linear Programming Tools and Mathematical Methods based upon Classical Optimization Techniques. Afterwards, the same task was carried out by private and public universities using computational proposals based upon Metaheuristics. The aim of this work is to project and implement VNS algorithm computationally to solve timetabling problems in university environments; to provide a theoretical and experimental analysis of the VNS algorithm performance and discuss its application in order to optimize any other type of timetabling family problems. Thus, an algorithm of variable neighborhood search was developed for solving problems of timetabling family in university environments. / Mestre

Made available in DSpace on 2014-06-11T19:23:31Z (GMT). No. of bitstreams: 0 Previous issue date: 2002-08-30Bitstream added on 2014-06-13T20:30:18Z : No. of bitstreams: 1 castro_alp_me_prud.pdf: 5444410 bytes, checksum: 7e68cc5dce3b24fd2a1e82437186ffef (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O posicionamento através do GPS alterou profundamente a metodologia geodésica nas últimas décadas. Atualmente, as aplicações dessa técnica espacial não se limita à determinação das coordenadas geodésicas como ocorria no posicionamento clássico. O posicionamento por GPS, combinado com um modelo geoidal, proporciona a altitude ortométrica, com a precisão suficiente para várias aplicações cotidianas (mapeamento, distribuição de água, saneamento básico, irrigação, planejamento urbano, etc). Isto significa que, nessas aplicações, já é possível substituir o nivelamento tradicional pelo nivelamento por satélite com a simplicidade oferecida pelo GPS. Os objetivos principais deste trabalho, em síntese, são os seguintes: determinar a altitude ortométrica num conjunto de Referências de Nível combinando o posicionamento por GPS com um modelo geoidal do Estado de São Paulo; avaliar o nivelamento através do GPS, comparando as altitudes determinadas com as conhecidas nesses pontos; e definir estratégias para adequar o nivelamento por satélite às aplicações cotidianas. A metodologia proposta consiste em avaliar o nivelamento realizado com o GPS, por meio da análise estatística das discrepâncias entre as altitudes ortométricas determinada e conhecida em cada ponto; e definir estratégias de observação e processamento de dados GPS visando essas aplicações. Os resultados obtidos neste trabalho mostram que é possível realizar o nivelamento por satélite utilizando receptores GPS equipados com antenas de duas freqüências ou mesmo de uma freqüência e bases de comprimento até 250 km. Assim, o usuário possui alternativa para substituir o nivelamento convencional pelo nivelamento por satélite, com os benefícios da simplicidade operacional, da rapidez e do baixo custo que o GPS oferece. / The GPS positioning has deeply modified the geodetic methodology in the last decades. Currently, the applications of this space technique are not limited to the determination of the geodetic coordinates as it happened in classical positioning. The GPS positioning, combined with a geoidal model, provides the orthometric heights, with the enough precision for some daily applications (mapping, water distribution, basic sanitation, irrigation, urban planning, etc). In these applications, it is already possible to substitute the traditional levelling by the satellite levelling with the simplicity allowed by the GPS. The main objectives of this work are the following: to determine the orthometric heights in a set of leveling benchmarks by combining the GPS positioning and a gravimetric geoidal model in São Paulo state; to evaluate the GPS levelling, by comparing the obtained orthométric heights with the known ones at these points; and to define strategies to applay the satellite levelling to the daily applications. The proposed methodology consists in evaluating the GPS levelling through the statistical analysis of the discrepancies between the determined orthometric heights and the known one at each point; and to recomend strategies for observation and data processing. The results obtained in this work show that, for many applications, the GPS levelling can be accomplished, by using GPS receivers equipped with two frequencies, or even one frequency antennas, for baselines up to 250 km. So the user has an alternative to substitute the conventional levelling by the satellite levelling, with the benefits of operational simplicity, the little time consuming, and the low cost enabled by using GPS.

Made available in DSpace on 2014-06-11T19:23:38Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-12-20Bitstream added on 2014-06-13T19:29:57Z : No. of bitstreams: 1 maziero_vf_me_ilha.pdf: 2130225 bytes, checksum: 3cf6fd4784a5f3c4531fa30c66f2d85d (MD5) / O presente trabalho teve como objetivo o desenvolvimento e teste de um protótipo de um programa computacional para simulação de plantas térmica e de potência, com os principais recursos de programas comerciais existentes, com baixo custo e com interface gráfica mais amigável. O referido programa foi denominado TPPS (abreviação de Thermal Power Plant Software), tendo sido desenvolvido na linguagem object pascal, utilizando a IDE do DELPHI e a biblioteca FLUIDPROP, na qual constam os componentes para cálculo das propriedades termodinâmicas envolvidas. Para tanto, inicialmente é apresentada uma breve descrição de alguns programas computacionais disponíveis no mercado que comumente são utilizados no meio acadêmico sendo que, dentre eles, foram escolhidos três (Cycle-Tempo, EES e IPSEpro) para efeito comparativo dos resultados das simulações com o programa desenvolvido, tendo como base duas plantas básicas, uma de geração e outra de cogeração de energia. Foi utilizada uma metodologia de simulação que consiste na avaliação dos processos, dos dados e do resultado dos cálculos obtidos. Para tanto, foram consideradas as hipóteses de regime permanente; variações das energias cinéticas e potencial são desprezadas em virtude de se desejar apenas um simples comparativo de valores das propriedades termodinâmicas calculadas; processos adiabáticos em todos os equipamentos que fazem parte dos ciclos, exceto para trocadores de calor, para os quais um parâmetro de eficiência define a quantidade de calor transferida ao meio. Os resultados obtidos foram bastante satisfatórios, tendo em vista que não houve discrepâncias entre os resultados obtidos por cada um dos programas, mostrando que a ferramenta desenvolvida, em sua primeira versão, atende os requisitos a que se propôs. Por fim, são apresentados resultados de uma simulação de uma planta de cogeração mais complexa, através do TPPS / This study aimed to develop and test a prototype of a computer program for simulation of thermal and power plants, with the main sources of existing commercial programs, with low cost and friendlier graphical interface. The program was denominated TPPS (abbreviation for Thermal Power Plant Software), and has been developed in Object Pascal language, using the Delphi IDE and FLUIDPROP library, which contains the components for calculating the thermodynamic properties involved. Therefore, initially presents a brief description of some computational programs available that are commonly utilized in the academic environment and among them, three were chosen (Cycle-Time, EES and IPSEpro) for comparison of the simulation results with the program developed, based on two basic plants, one of power generation and the other one of cogeneration. The simulation methodology consists of the evaluation of the processes, data and results obtained from the calculations. Therefore, it was considered the hypothesis of steady state and the variations of kinetic and potential energies were neglected because just a simple comparison of calculated values of thermodynamic properties; adiabatic processes in all devices of the cycles, except for heat exchangers, for which an efficiency parameter defines the amount of heat transferred to the environment. The results were quite satisfactory, considering that there were no discrepancies between the results obtained by each one of the programs, showing that the first version of the software developed meets the proposed requirements. Finally, results of simulation of a more complex cogeneration plant through the TPPS are presented

Made available in DSpace on 2013-08-07T18:42:58Z (GMT). No. of bitstreams: 1 000419188-Texto+Completo-0.pdf: 2389705 bytes, checksum: 7142723f44a1f3c5a063142bb2c8760b (MD5) Previous issue date: 2009 / To supply the ever-increasing need for processing power, the embedded software project includes the utilization of several processors along with complex communication infrastructures (as hierarchycal buses and networks-on-a-chip). There is an increasing need for a greater number of functionalities inside a single system. In this scenario, issues related to energy consumption estimations become important in the embedded electronic systems project. This way, the multi-processor embedded systems workflow needs tools to generate performance and energy consumption estimations during all development cycle, in order to verify if the project building process conforms to its specification. The performance, as the energy consumption of a system have to be evaluated as soon as possible in the workflow. Analytical methods are proposed to allow performance and energy estimations in a fast way, avoiding prohibitive simulation times. In analytical methods the system is modeled as a series of properties and abstract models are used to calculate the system performance. Although analytical methods are faster than simulation ones, their modelling is more complex. Along with this fact, the high abstraction level in which the system is represented becomes unfeasible due to the high increase in states necessary to represent such systems, which is the case of more recent embedded systems. This way, better approaches in simulation based methods become very interesting, and a study in this field is presented in this work. / Para atender a uma cresente demanda por desempenho de processamento, o projeto de sistemas embarcados inclui a utilização de diversos processadores além de infra-estruturas de comunicação complexas (por exemplo, barramentos hierárquicos e redes intra-chip). Há uma crescente demanda por um número cada vez maior de funcionalidades contidas em um único sistema. Neste cenário, questões relacionadas a estimativas de consumo de energia ganham importância no projeto de sistemas eletrônicos embarcados. Dessa forma, o fluxo de projeto de sistemas embarcados multi-processados necessita de ferramentas para a geração de estimativas de desempenho e consumo de energia durante todo o ciclo de desenvolvimento, de forma a verificar se o caminho de construção do projeto condiz com a especificação do mesmo. O desempenho, assim como o consumo de energia de um determinado sistema precisam ser avaliadados o mais cedo possível no fluxo de projeto. Métodos analíticos são propostos para que estimativas de desempenho e de consumo de energia possam ser realizadas de maneira rápida, evitando tempos proibitivos de simulação. Nos métodos analíticos o sistema é modelado como uma série de propriedades e modelos abstratos são utilizados para o cálculo do desempenho do sistema. Apesar de métodos analíticos serem mais rápidos que métodos baseados em simulação a modelagem do sistema é mais complexa. Além disso, devido ao alto nível de abstração em que o sistema é representado, seu uso em sistemas grandes e complexos se torna inviável devido a explosão de estados necessários para a representação sistêmica destes, que é o caso de recentes projetos de sistemas embarcados. Dessa forma, melhorias nos métodos baseados em simulação tornam-se bastante pertinentes, e um estudo dessa área é apresentado nesse trabalho.

Made available in DSpace on 2013-08-07T18:43:00Z (GMT). No. of bitstreams: 1 000425483-Texto+Completo-0.pdf: 1217247 bytes, checksum: 2d1bad79b7e96a9d75748adf3146bedd (MD5) Previous issue date: 2010 / Molecular dynamics systems are defined by the position and energy of their component particles, as well as by the interactions among these. Such systems can be simulated through mathematical methods like the computation of electrostatic forces based on the Coulomb Law. Predicting the states through which such system evolves by computing the interaction of each particle with its neighbors is a computationally costly task, even for a small number of particles. Thus, it can only be beneficial to apply specific techniques for accelerating these computations. While some studies propose the use of new algorithms, others advocate the use of specific processors or custom designed hardware, the later being the technique employed in this Dissertation. This work describes the design and prototyping of a hardware architecture that has the potential to accelerate an application based on the computation of electrostatic forces among non-bonded particles. A special emphasis is given to the aspects of integration between the accelerating hardware and the modified target application, the PMEMD (Particle Mesh Ewald Molecular Dynamics) software, part of the AMBER (Assisted Model Building with Energy Refinement) platform. The costliest computations of PMEMD were identified and moved to an FPGA hardware implementation, creating a custom coprocessor – PMEMD-HW. The choice for reconfigurable hardware is due, among other reasons, to the ease with which it enables the evolution of the design towards the target acceleration. The main contribution of this work is the mastering of the technology to design and analyze hardware coprocessors that target the acceleration of applications in Biology and Biophysics. A working prototype is available, using a commercial hardware prototyping platform. The proof-of-concept implementation demonstrates the viability of successfully using the proposed techniques. / Sistemas de dinâmica molecular são definidos pela posição e energia das partículas que o compõe, assim como pelas interações entre estas. Tais sistemas podem ser simu-lados através de métodos matemáticos como o cálculo de forças eletrostáticas baseadas na Lei de Coulomb. Computar os estados através dos quais um sistema destes evolui, avaliando a interação de cada partícula, é tarefa computacionalmente dispendiosa, mes-mo para um número pequeno de partículas. Portanto, podem-se obter benefícios ao se aplicar técnicas específicas para acelerar tais computações. Enquanto alguns estudos propõem o uso de algoritmos diferenciados, existem os que empregam processadores especiais ou hardware personalizado, a técnica abordada nesta Dissertação. Descreve-se aqui o projeto e a prototipação de uma arquitetura de hardware com potencial para acelerar uma aplicação que computa forças eletrostáticas entre partículas não ligadas. Dá-se ênfase especificamente aos aspectos da integração entre o hardware e a aplicação-alvo empregada neste projeto, o programa PMEMD (Particle Mesh Ewald Molecular Dynamics), parte da plataforma AMBER (Assisted Model Building with Energy Refinement). Os cálculos mais onerosos deste programa foram identificados e movidos para uma implementação de hardware em FPGA, criando um co-processador específico – o PMEMD-HW. A escolha de um hardware reconfigurável se deve, entre outros motivos, à facilidade de fazer evoluir o processo de projeto e obter a aceleração almejada. A principal contribuição deste trabalho é o domínio da tecnologia de uso de co-processadores de hardware para acelerar aplicações nas áreas de Biologia e Biofísica. Um protótipo funcional está disponível, utilizando uma plataforma comercial de prototipa-ção de hardware. Esta prova de conceito demonstra a viabilidade de usar com sucesso as técnicas desenvolvidas.