Orientador: Rubén Augusto Romero Lázaro / Banca: Sergio Azevedo de Oliveira / Banca: Carlos Roberto Mendonça da Rocha / Resumo: Neste trabalho propõe-se uma heurística especializada para a alocação ótima de bancos de capacitores para os sistemas de distribuição radiais, cujo objetivo é minimizar os custos devido às perdas de energia, sujeitas a certas restrições operativas do sistema elétrico de distribuição. Para realizar este objetivo foram desenvolvidos os seguintes tópicos: Um algoritmo heurístico construtivo, que tem como atividade principal a alocação de bancos de capacitores nas barras com demanda de potências reativas maiores e também procura uma solução inicial de minimização de custos das perdas de energia e uma metaheurística de busca em vizinhança variável descendente. Nessa metaheurística são implementadas estruturas de vizinhança adequadas para o problema de alocação de bancos de capacitores nas barras do sistema elétrico. A heurística especializada tem um novo conceito para a alocação ótima de bancos de capacitores ao desenvolver uma ferramenta amigável e poderosa de otimização no desenvolvimento de modelos matemáticos para os problemas de programação não linear inteiro misto. A heurística especializada foi implementada em linguagem de programação Fortran 90 e foram realizadas simulações com sistemas de distribuição radial de 33, 70 e 202 barras. Os resultados foram comparados com pesquisas que realizaram testes com esses sistemas elétricos. Assim, foi verificado um bom desempenho do algoritmo, pois gera soluções de boa qualidade atendendo a todas as restrições físicas e operacionais do problema / Abstract: In this work we proposes a specialized heuristic algorithm for optimal allocation of capacitor banks in radial distribution systems, whose goal is to minimize costs due to energy losses, subject to some operational restrictions of the electric distribution system. To accomplish this goal the following subjects were developed: A constructive heuristic algorithm, which has as primary task the allocation of capacitor banks in buses with the most high-demand for reactive power and also search for an initial solution to minimize energy losses costs and a meta-heuristic which uses variable neighborhood descend search, in which we implemented appropriate neighborhood structures for the allocation problem of capacitor banks in electric system buses. The specialized heuristic uses a new concept for the optimal allocation of capacitor banks to develop a powerful and user-friendly optimization tool for the development of mathematical models for mixed integer nonlinear programming problems. The specialized heuristic was implemented in the programming language Fortran 90 and simulations were performed with radial distribution systems of 33, 70 and 202 buses. The results were compared with other research works that also tested with these electrical systems. Thus, it was verified that the algorithm has a good performance because it generates good quality solutions meeting all the physical and operational constraints of the problem / Mestre

Orientador: Roberta Spolon / Banca: Antonio Carlos Sementille / Banca: Luís Carlos Trevelin / Resumo: Na tentativa de reduzir custos aproveitando de maneira eficiente recursos computacionais, novas tecnologias e arquiteturas desenvolvidas estão conquistando grande aceitação do mercado. Uma dessas tecnologias é a Computação em Nuvem, que tenta resolver problemas como consumo energético e alocação de espaço físico em centros de dados ou grandes empresas. A nuvem é um ambiente compartilhado por diversos clientes e permite um crescimento elástico, onde novos recursos como hardware ou software, podem ser contratados ou vendidos a qualquer momento. Nesse modelo, os clientes pagam por recursos que utilizam e não por toda a arquitetura envolvida. Sendo assim, é importante determinar de forma eficiente como esses recursos são distribuídos na nuvem. Portanto, esse trabalho teve como objetivo desenvolver um algoritmo de escalonamento para nuvem que determinasse de maneira eficiente a distribuição de recursos dentro da arquitetura. Para alcançar esse objetivo, foram realizados experimentos com gestores de nuvem open-source, detectando a deficiência dos algoritmos atuais. O algoritmo desenvolvido foi comparado com o algoritmo atual do gestor OpenStack Essex, um gestor de nuvem open-source. Os resultados experimentais demonstraram que o novo algoritmo conseguiu determinar as máquinas menos sobrecarregadas da nuvem, conseguindo desse modo, distribuir a carga de processamento dentro do ambiente privado / Abstract: In an attempt to reduce costs by taking advantage of efficient computing resources, new technologies and architectures developed are gaining wide acceptance in the market. One such technology is cloud computing, which tries to solve problems like energy consumption and allocation of space in data centers or large companies. The cloud is an environment shared by multiple clients and enables elastic growth, where new features such as hardware or software, can be hired or sold at any time. In this model, customers pay for the resources they use and not for all the architecture involved. Therefore, it is important to determine how efficiently those resources are distributed in the cloud. Therefore, this study aimed to develop a scheduling algorithm for cloud efficiently determine the distribution of resources within the architecture. To achieve this goal, experiments were conducted with managers of open-source cloud, detecting the deficiency of current algorithms. This algorithm was compared with the algorithm of the OpenStack Essex manager, a manager of open-source cloud. The experimental results show that the new algorithm could determine the machines less the cloud overloaded, achieving thereby distribute the processing load within the private environment / Mestre

Orientador: Percival Bueno de Araujo / Co-orientador: Laurence Duarte Colvara / Banca: Mara Lúcia Martins Lopes / Banca: Francisco Damasceno Freitas / Banca: Walmir de Freitas Filho / Resumo: O trabalho tem como propósito principal a análise da estabilidade a pequenas perturbações em Sistemas Elétricos de Potência, que é representado pelo Modelo Sensibilidade de Potência. São analisados três sistemas teste, conhecidos na literatura como Sul-Brasileiro, simétrico de duas áreas e New England. A princípio os sistemas teste foram submetidos a um ponto de operação de modo a serem instáveis. É proposta a utilização dos Estabilizadores de Sistema de Potência e do dispositivo Thyristor Controlled Series Capacitor em conjunto com o controlador Power Oscillation Damping. Estes controladores possuem a função de inserir amortecimento adicional às oscilações de baixa frequência do Sistema Elétrico de Potência. Neste caso é necessário alocar e ajustar os parâmetros dos respectivos controladores de forma correta. As localizações dos controladores são determinadas pelos fatores de participação (Estabilizadores de Sistema de Potência) e a distância entre polo de interesse e zero da função de transferência de malha aberta do controlador Power Oscillation Damping (conjunto Thyristor Controlled Series Capacitor-Power Oscillation Damping). Para o ajuste de parâmetros dos controladores (Estabilizadores de Sistema de Potência e Power Oscillation Damping) são utilizados dois algoritmos de otimização baseados em enxame de partículas, sendo eles o Particle Swarm Optimization e de Bacterial Foraging Optimization orientado pelas formas de movimentação do Particle Swarm Optimization. A atuação dos controladores alocados e ajustados de acordo com os métodos propostos aumenta o amortecimento dos modos oscilatórios de baixa frequência dos sistemas teste. Este fato é verificado pela análise dos resultados obtidos / Abstract: This work aims to analyze small signal stability in power systems represented by the power sensitivity model. Three test systems known in the literature, such as South Brazilian, Two Symmetrical Areas and New England are analyzed. At first, the systems were submitted to an operation point to become unstable. The Power System Stabilizers and the device Thyristor Controlled Series Capacitor with the Power Oscillation Damping controller are proposed to use. These controllers insert additional damping to the low frequencies oscillations. In this case, it is necessary to allocate and adjust the parameters of the controllers correctly. The controller position is determined by the participation factors (Power System Stabilizers) and the distance between the interest pole and the zero of the open-loop transfer function of the Power Oscillation Damping Controller (Thyristor Controlled Series Capacitor-Power Oscillation Damping).Two algorithms based on the particle swarm are used to adjust the controller parameters (Power System Stabilizer and the Power Oscillation Damping), that are Particle Swarm Optimization and Bacterial Foraging Optimization oriented by the movement forms of the Particle Swarm Optimization. The actuation of the controller both allocated and adjusted according to the proposedmethod improves the low frequency oscillation damping. The results obtained confirm this conclusion / Doutor

Orientador: Aleardo Manacero Junior / Banca: Mário Antônio Ribeiro Dantas / Banca: Marcos Antônio Cavenagui / Resumo: A crescente necessidade por poder computacional, unida com o progresso atingido nos computadores pessoais e redes de interconexão, fez surgir diversas propostas, tais como grades computacionais, para tornar a computação de alto desempenho mais barata e acessível. Como contraponto, a maior acessibilidade aos recursos para computação de alto desempenho oferecida pelas grades, criou um universo de usuários tipicamente não especialistas em computação paralela, aumentando a demanda por ferramentas de avaliação de desempenho e de apoio ao desenvolvimento de sistemas. Visando criar uma ferramenta de simulação de grades com facilidade de uso, mesmo para usuários não especialistas em programação, vem sendo desenvolvido o simulador de grades com-putacionais iSPD ( iconic Simulator of Parallel and D istributed systems ). Como o escalonamento de tarefas é essencial na computação distribuída, o iSPD necessitava de uma interface para a especificação de escalonadores no ambiente simulado que mantivesse os conceitos de fácil modelagem. Este trabalho de pesquisa apresenta a proposta e desenvolvimento de técnicas que permitam que o usuário do iSPD modele novas políticas de escalonamento de forma automatizada e simples. Estas técnicas foram aplicadas em um novo componente capaz de interpretar algoritmos de escalonamento especificados pelo usuário adicionando-os a um banco de algoritmos pré-disponibilizados / Abstract: The increasing demand for more computing power, associated with the progress in personal computers and interconnection networks, culminated in proposals to make high performance computing cheaper and more accessible such as computer grids. The greater accessibility to resources for high performance computing offered by grids created a universe of users lacking of parallel programming expertise, increasing the demand for tools for performance evaluation and systems development support. Aiming for the development of a grid performance evaluation to ol that could be easy to use, even for people not expert in parallel programming, iSPD (iconic Simulator of Parallel and Distributed systems) has been developed. Since task scheduling in distributed systems is a critical process, iSPD needed an easy approach to specify scheduling policies for a grid. This work presents the development, and its associated results, of a set of techniques that allow the iSPD's user to model scheduling policies in an automated and simple way. These techniques were applied to a new component capable of interpreting scheduling algorithms specified by a user, adding them to a prebuilt algorithms database. Results achieved with this component show that the used approach is right / Mestre

Orientador: Fabricio Aparecido Breve / Banca: Denis Henrique Pinheiro Salvadeo / Banca: Marcos Gonçalves Quiles / Resumo: Para estudar e classificar imagens é necessário entender as subdivisões que elas apresentam. Para esta finalidade existem técnicas de segmentação de imagens, uma das tarefas de visão computacional, a qual consiste na repartição de uma imagem digital em múltiplos segmentos, regiões ou objetos, com o intuito de facilitar a análise e compreensão. Métodos de segmentação de imagens são frequentemente utilizados para localizar objetos e bordas em imagens. Para tal tarefa, frequentemente são empregados algoritmos de aprendizado de máquina; disciplina científica que trata do projeto e desenvolvimento de algoritmos que melhoram automaticamente com a experiência, imitando o comportamento de aprendizado humano. O processo de aprendizado de máquina pode ser utilizado de diferentes formas, no entanto a categoria de aprendizado semi-supervisionado foi a que melhor se adaptou à proposta deste projeto. Esta categoria representa uma mescla entre o aprendizado supervisionado e o aprendizado não-supervisionado e trabalha com ambos os dados rotulados e não rotulados em sua fase de treinamento, proporcionando o uso de características individuais e/ou por conjunto. Diante da necessidade de combinação do aprendizado semi-supervisionado com a segmentação de imagem, foram estudadas formas de se utilizar informação provenientes de imagens para alimentar o aprendizado de máquina semi-supervisionado. Como resultado deste estudo, o algoritmo de aprendizado semi-supervisionado conhecido como competição e cooperação entre partículas foi estendido para a aplicações na tarefa de segmentação interativa de imagens. Na imagem de entrada, alguns pixels são classificados pelo usuário e servem como pixels de partida para o algoritmo. Estes pontos pré-rotulados são utilizados para criar as partículas no modelo utilizado. Também foram alterados alguns parâmetros de execução e partes estruturais do algoritmo de forma a otimizar a... / Abstract: To study and classify images it is necessary to understand the subdivisions they present. For this purpose there are image segmentation techniques, one of the computer vision tasks, which consists in the distribution of a digital image into multiple segments, regions or objects, in order to facilitate analysis and understanding. Image segmentation methods are often used for locating objects in images and borders. For this task, machine learning algorithms are often employed; scientific discipline that deals with the design and development of algorithms that automatically improve with experience, imitating the human learning behavior. The machine learning process can be used in different ways, however the category that best adapted to the project proposal, which represents a blend of supervised learning and unsupervised learning, called semi-supervised learning. Such category of algorithms works with both labelled and unlabelled data in their training phase, allowing the use of individual characteristics and or per set. Given the necessity of combining semi-supervised learning with image segmentation, some means of using information delivered from image to feed the semi-supervised learning machine were studied. As a result of this study, the semi-supervised learning algorithm known as competition and cooperation among particles was extended to be applied in the interactive image segmentation task. In the input image, some pixels are classified by the user and serve as a starting pixels to the algorithm. These pre-labeled points are used to create particles in the proposed model. Also, some parameters and algorithm structures were changed to optimize the classification and means of expressing the results in order to make it more suitable for the image segmentation task / Mestre

Orientador: Antonio Carlos Sementille / Coorientador: Silvio Ricardo Rodrigues Sanches / Banca: João Paulo Papa / Banca: Valdinei Freire da Silva / Resumo: Vários algoritmos de segmentação de vídeo em duas camadas, para a extração de elementos de interesse em primeiro plano (normalmente pessoas) em ambientes não controlados, vem sendo propostos, para diversas aplicações como sistemas de Realidade Aumentada, video chats, ou para a compressão de vídeos. Para analisar a qualidade dos vídeos gerados pelos algoritmos de segmentação, diversos métodos os comparam com seus respectivos ground truths, que consistem em referências da melhor segmentação possível de um vídeo. Muitas vezes esse ground truth é obtido de forma manual, ou seja, o usuário pode ter que segmentar cada quadro (frame) do vídeo. Naturalmente este processo é trabalhoso, demorado e muitas vezes não é realizado para todos os quadros que constituem o vídeo. Devido a isto, também, muitas vezes o ground truth possui baixa resolução e curta duração. Estes aspectos podem constituir um problema quanto à eficácia da utilização do próprio ground truth no processo de avaliação da qualidade da segmentação. Neste contexto, o presente projeto teve como principal enfoque o desenvolvimento de um método semiautomático para a geração de ground truths de vídeos, utilizando informações de profundidade, visando a minimização da interação do usuário, o processo de implementação deste método na forma de uma ferramenta que combina etapas automáticas e interativas, assim como os resultados obtidos são comparados a outros trabalhos presentes na literatura / Abstract: Several bilayer video segmentation algorithms, for the extraction of elements of interest in the foreground (usually people) in uncontrolled environments, have been proposed for various applications such as Augmented Reality systems, video chats or for video compression. To analyze the quality of the videos generated by the segmentation algorithms, different methods compare them with their ground truths, which consist of references of the best possible segmentation of a video. Usually this ground truth is obtained manually, so the user may have to segment each frame of the video. Of course this process is laborious, time consuming and frequently not performed for all frames of the video. Because of this, the ground truth, usually, has low resolution and short duration. These aspects can be an issue to the effectiveness of using these ground truths in the segmentation quality evaluation process. In this context, this project had as its main focus the development of a semi-automatic method for the generation of ground truths of videos, using depth information, in order to minimize the user interaction, the implementation process of this method as a tool that combines automatic and interactive steps, and the results, that are compared to other studies in literature / Mestre

Orientador: Fabrício Aparecido Breve / Banca: Moacir Antonelli Ponti / Banca: Daniel Carlos Guimarães Pedronette / Resumo: As pesquisas realizadas para o Sequenciamento de Genomas, Proteômica, Sistemas Biológicos, Diagnósticos Médicos, entre outros, geram uma grande quantidade de dados, fazendo necessário o apoio de soluções computacionais para a análise e interpretação desses dados. A utilização de técnicas de Aprendizado de Máquina, para a extração de conhecimentos úteis dessas grandes quantidades de dados, tem sido amplamente discutida entre pesquisadores da Biologia e da Computação. O processo para se rotular todos os dados gerados pelas pesquisas biológicas, assim como em outras áreas, é difícil, caro e/ou demorado. Assim, buscar maneiras de se atingir uma grande acurácia com poucos dados rotulados torna-se uma tarefa importante e desafiadora. Nesse sentido, o Aprendizado SemiSupervisionado mostra-se como uma opção importante uma vez que utiliza dados rotulados e não rotulados para o treinamento, sendo uma categoria intermediária entre o Aprendizado Supervisionado e o Não Supervisionado. Diversas abordagens para algoritmos de Aprendizado Semi-Supervisionado são encontradas na literatura. Dentre elas, destacam-se os métodos baseados em grafos, que representam os dados de entrada como nós de um grafo cuja estrutura é utilizada para propagar informações de rótulos dos nós rotulados para os demais nós. Destaca-se ainda que a abordagem baseada em grafos possui uma grande fundamentação matemática e computacional. Nesse contexto, este trabalho apresenta uma análise comparativa de alguns algoritmos semi-supervisionados, baseados em grafos, quando aplicados a dados biológicos relacionados aos campos de estudos da Proteômica e Transcriptômica. Adicionalmente, o trabalho propõe um novo dataset com dados reais oriundos de pesquisas biológicas com o transcriptoma de formigas da espécie Mycocepurus goeldii. Alguns experimentos realizados com os algoritmos semi-supervisionados são apresentados, levando em consideração sua... / Abstract: Research conducted for the sequencing of genomes, Proteomics, Systems Biology, Medical Diagnostics, among others, generate a lot of data, making it necessary the support of computing solutions for the analysis and interpretation of such data. The possibility of using machine learning techniques to extract useful knowledge of these large amounts of data has been widely discussed among researchers of Biology and Computer Science. The process of labeling all data generated by biological research, as well as in other areas, is difficult, costly and / or time consuming. Thus, searching ways to achieve a high accuracy with few labeled data is an important and challenging task. Accordingly, the Semi-Supervised Learning shows up as an important option since it uses both labeled and unlabeled data for training, being an intermediate category between the Supervised and Unsupervised Learning. Several approaches to semi-supervised learning algorithms are found in the literature. Among them, the highlights are the graph-based methods, which represent the input data as nodes in a graph, which structure is used to propagate label information from labeled nodes to the other nodes. It is also noteworthy that the graph-based approach has a great mathematical and computational validity. In this context, this paper presents a comparative analysis of some semi-supervised algorithms based on graphs, when applied to biological data analysis related to the field of proteomics and transcriptomics studies. In addition, the paper proposes a new dataset with actual data from biological research with the transcriptome of the Mycocepurus goeldii species of ants. Some experiments performed with semi-supervised algorithms are presented, considering its efficacy when compared with a few supervised methods / Mestre

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2011. / Submitted by Alaíde Gonçalves dos Santos (alaide@unb.br) on 2012-09-12T15:24:40Z No. of bitstreams: 1 2011_MateusdeCastroPolastro.pdf: 1716533 bytes, checksum: b92d102e804b048afaec7bfeb5cccac8 (MD5) / Approved for entry into archive by Leandro Silva Borges(leandroborges@bce.unb.br) on 2012-09-18T18:12:22Z (GMT) No. of bitstreams: 1 2011_MateusdeCastroPolastro.pdf: 1716533 bytes, checksum: b92d102e804b048afaec7bfeb5cccac8 (MD5) / Made available in DSpace on 2012-09-18T18:12:22Z (GMT). No. of bitstreams: 1 2011_MateusdeCastroPolastro.pdf: 1716533 bytes, checksum: b92d102e804b048afaec7bfeb5cccac8 (MD5) / A facilidade de armazenamento e troca de documentos no formato digital, juntamente com a redução dos custos de equipamentos de impressão e digitalização de documentos, vem aumentando a necessidade de utilização na Informática Forense de programas para busca aproximada de palavras-chaves em textos originados por reconhecimento ótico de caracteres (OCR – Optical Character Recognition). Porém, as ferramentas que levam em conta os erros de OCR ainda não são totalmente satisfatórias, principalmente devido aos vários tipos de degradação comumente encontradas em documentos digitalizados. Neste trabalho, um algoritmo para busca de palavras-chaves em textos gerados a partir de OCR, baseado em programação dinâmica e na utilização de matrizes de substituição de aminoácidos, é descrito e implementado. Os resultados mostraram que o algoritmo proposto superou, principalmente em textos contendo maior número de erros, o algoritmo de distância de edição de Levenshtein, utilizado nas principais ferramentas para esse fim. Além disso, um estudo detalhado de como os erros de OCR afetam a recuperação da informação, a partir de degradações em imagem, é proposto. _______________________________________________________________________________________ ABSTRACT / The ease of storing and exchanging documents in digital format, along with cost reduction of printing and scanning equipments, has increased the need for use in Computer Forensics of programs to conduct approximate keyword search in texts generated by optical character recognition (OCR). However, tools that take into account the OCR errors are not yet fully satisfactory, mainly due to the various types of degradation commonly found in scanned documents. In this work, an algorithm to search for keywords in text generated by OCR, based on dynamic programming and on the use of amino acid substitution matrices, is described and implemented. The results showed that the proposed algorithm outperformed, especially in texts containing more errors, the Levenshtein edit distance algorithm, the most widely used by the tools for this purpose. In addition, a detailed study of how OCR errors affect the information retrieval, under several image degradations, is proposed.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2009. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-06-06T14:24:38Z No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2011-06-06T14:25:37Z (GMT) No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Made available in DSpace on 2011-06-06T14:25:37Z (GMT). No. of bitstreams: 1 2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5) / Os Modelos Ocultos de Markov (HMM - Hidden Markov Models) constituem uma poderosa ferramenta para mapeamento e organização de proteínas, uma vez que permitem reconhecer estruturas altamente representativas e unidades funcionais dentro das cadeias de aminoácidos que as conformam. O Viterbi é um dos principais algoritmos para comparação e identificação de proteínas (sequências de aminoácidos) baseados em HMM, e é implementado dentro do software livre HMMER [1][2], muito utilizado na comunidade científica. Nos últimos anos, devido ao crescimento exponencial das bases de dados que armazenam proteínas, surge a necessidade de acelerar a execução do software para reduzir os tempos de processamento dos algoritmos de comparação. Neste trabalho de mestrado, é realizada a aceleração do software HMMER para alinhamento de sequências biológicas através da implementação de um acelerador em hardware. O acelerador proposto utiliza um novo algoritmo chamado de Algoritmo das Divergências, o qual permite ao sistema completo (Hardware+Software) economizar uma grande quantidade de cálculos para gerar os alinhamentos de proteínas. O Hardware produz a medida de similaridade da proteína com o modelo HMM e os índices inicial e final da porção de interesse da sequência de aminoácidos como uma primeira etapa de filtragem. Isto, quando gerado pelo acelerador, significa uma economia de processamento adicional para o software, o qual tem que reprocessar dita região para gerar o alinhamento da sequência com o profileHMM, e contribui com a aceleração da execução do algoritmo. O Acelerador atinge ganhos de até 182x quando comparado com o software não acelerado. Além disso, o trabalho propõe uma nova medida para a comparação do desempenho e realiza medições exatas acerca da aceleração atingida ao integrar o acelerador ao fluxo de execução do software. _______________________________________________________________________________ ABSTRACT / Hidden Markov Models are a powerful tool for protein organization and identification because they allow identifying and classifying highly representative structures and functional units inside the amino acid chains that form them. The Viterbi algorithm is one of the most used algorithms in protein comparison and identification using Hidden Markov Models, and is implemented inside the open source software HMMER [1][2], which is widely used among the scientific community. Due to the exponential growth in the size of protein databases in the past years, the necessity to accelerate software execution to reduce comparison and search times rose. In this master thesis, a hardware accelerator is implemented in VHDL in order to reduce those processing times in the protein comparison and search processes. The implemented accelerator uses a new algorithm which enables the system (Hardware+Software) to economize processing time by reducing the number of calculations needed to perform a comparison. The accelerator not only produces the similarity score for a sequence when compared against a profileHMM but also produces the parameters to limit the region of the Dynamic Programming Matrices that must be reprocessed to generate the alignment. The implemented accelerator produces a maximum gain of up to 182 times when compared to unaccelerated software. A new performance measurement strategy is introduced in this work, which not only takes into account the acceleration achieved by the hardware, but also the post-processing stages that follows hardware made comparisons.

Dissertação (mestrado)—Universidade de Brasília, Intituto de Ciências Exatas, Departamento de Ciência da Computação, 2013. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-10-22T15:20:13Z No. of bitstreams: 1 2013_IvoSocratesMoraesOliveira.pdf: 6931125 bytes, checksum: b450c9c7809a3a328b4c6d6fe6e13d6b (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-10-22T15:50:56Z (GMT) No. of bitstreams: 1 2013_IvoSocratesMoraesOliveira.pdf: 6931125 bytes, checksum: b450c9c7809a3a328b4c6d6fe6e13d6b (MD5) / Made available in DSpace on 2013-10-22T15:50:56Z (GMT). No. of bitstreams: 1 2013_IvoSocratesMoraesOliveira.pdf: 6931125 bytes, checksum: b450c9c7809a3a328b4c6d6fe6e13d6b (MD5) / A monitoração eletrônica baseada em vídeo digital tem se tornado chave para a eficácia de diversas atividades, pois permite a identificação eficiente de anomalias no local monitorado, a identificação de indivíduos suspeitos e o esclarecimento de fatos, entre outras atividades. Portanto, surge a necessidade de algoritmos de rastreamento visual de baixa complexidade, que visa oferecer a capacidade de identificação da trajetória de indivíduos em sistemas de monitoração eletrônica em ambientes restritos. Esses algoritmos podem permitir uma compactação diferenciada em uma região de interesse, permitindo melhor desempenho na maioria dos padrões de codificação de vídeo, como o High Efficiency Video Coding (HEVC). Este trabalho propõe um algoritmo de rastreamento que utiliza o método de Otimização por Enxame de Partículas (PSO - Particle Swarm Optimization) com uma função de custo calculada por uma Função Discriminante Linear (LDF - Linear Discriminant Function), que utiliza histograma RGB (Red, Green and Blue) dos blocos de cada partícula para caracterização do objeto alvo. De forma sucinta, o algoritmo desenvolvido realiza, após o segundo quadro capturado, a detecção do objeto alvo, através da estimação de movimento e obtenção do fluxo óptico. Este processo é realizado para o treinamento da função de custo do método de PSO. Como mencionado anteriormente, a função de custo foi desenvolvida utilizando Funções Discriminantes Lineares, que são treinadas com base em histogramas RGB de blocos sobre o quadro atual de cada partícula para a caracterização do objeto alvo. A partir das características são formadas duas classes a alvo e a não alvo. Logo em seguida, é chamado um novo quadro que terá o alvo rastreado através do método de PSO, que se baseia em três elementos essenciais, a inércia, melhor posição local e melhor posição global. Estes elementos são utilizados para atualizar o deslocamento do enxame e, consequentemente, acompanhar o alvo. As atualizações da melhor posição local e melhor posição global são definidas pela avaliação da proximidade obtida entre o valor atual e o centroide da classe alvo obtido durante o treinamento. Através dos testes do foram identificadas as seguintes características do algoritmo proposto: rápida convergência, pois foram obtidos bons resultados no algoritmo com poucas iterações no método de PSO; baixo custo computacional, se comparado com métodos determinísticos comuns, pois realiza uma quantidade menor de operações; capacidade de tratar oclusões que não superam um quarto (1/4) da resolução do vídeo e capacidade satisfatória de rastreamento de objeto com movimentos arbitrários e abruptos. ______________________________________________________________________________ ABSTRACT / Electronic monitoring-based on digital video has become a key element to the effectiveness of several activities, such as an efficient identification of anomalies in the monitored environment, the identification of suspects and clarification of facts, among others. Therefore, the need of visual tracking algorithms with low computational complexity that allow identification of the subjects' trajectory in electronic monitoring systems has increase. These algorithms can al-low differential coding in different image regions, allowing better performance in most video coding standard, as the High Efficiency Video Coding (HEVC). In this work it is propose an algorithm that uses Particle Swarm Optimization (PSO), as tracking method, along with a cost function calculated by a Linear Discriminant Functions (LDF) which utilizes RGB (Red, Green and Blue) histogram of image blocks for each particle to characterize the target object. Succinctly, the developed algorithmdetects the target object through motion estimation and obtains the optical flow after the second captured frame. This process is performed for training of the cost function for the PSO method. As mentioned before the cost function is implemented using Linear Discriminant Functions, which are train based on RGB histograms of blocks about the current frame of each particle to characterize of the target object. The characteristics are divided into two classes target and non-target. Then, for the new frame the object will be tracked by the PSO method, which is based on three key elements: inertia, local best position and global best position. These elements are used to update the displacement of the swarm and consequently track the target. Updates to the global best position and local best position are de ned through an evaluation of the proximity obtained between the current value and the centroid of a target class obtained during training. Through empirically test the following features of the proposed algorithm were identi ed: fast convergence, due to appropriate results obtained with few it-erations; low computational cost, when compared to common deterministic methods, because it signi cantly reduces the amount of operations; an ability to treat occlusions which do not exceed one-quarter (1/4) of the resolution of the video frame and satisfactory object tracking capability in objects with arbitrary and abrupt movements.