▼ A esquistossomose é uma doença que afeta 200 milhões de pessoas em todo o mundo. Apesar dos esforços para controlar esta doença através do desenvolvimento de novos medicamentos ou vacinas, até o momento o número de pessoas afetadas permanece quase inalterado. A fim de melhorar o conhecimento sobre a biologia e aspectos relacionados com o desenvolvimento do parasito, ciclo de vida e de reprodução, o que poderia conduzir à concepção de novas drogas e / ou vacinas, projetos genoma têm sido desenvolvidos para este parasito. Um grande número de genes têm sido descobertos e na era pós-genômica, alguns genes têm sido escolhidos para ser melhor caracterizado. Um gene de S. mansoni envolvido no ciclo celular e apresentando homologia com genes de outras espécies, incluíndo seres humanos, foi selecionado para ser melhor caracterizado. Este gene em Saccharomyces cerevisiae está envolvido no processo de interação com o complexo do spliceosoma. A técnica de complementação fenotípica foi escolhida para determinar se o gene de S. mansoni apresenta a mesma função que o gene de S. cerevisiae. Já foi demonstrado que a supressão deste gene é letal na levedura, por isso, decidiu-se utilizar leveduras diplóides neste trabalho. A supressão do gene nas leveduras foi realizada pela ruptura de um dos alelos através de um evento de recombinação homóloga do gene Dib1, utilizando gene marcador autoxotópico HIS3. Os mutantes foram selecionados em placas contendo os nutrientes necessários exceto histidina. Para identificar o nocaute, os clones obtidos foram analisados por PCR de colônia usando iniciadores específicos. Leveduras nocauteadas para o Dib1 e transfectadas com os plasmídeos contendo o gene Dib1 da levedura (controles positivos), e o Dimp do S. mansoni, foram utilizados para ensaios de esporulação, para verificar se o gene de S. mansoni complementa a função gênica do seu ortólogo em S. cerevisiae. Após experimento de nocaute, 111 clones de leveduras foram obtidas, 45 destas colônias foram testadas por PCR, e destas 6 foram identificados como nocauteadas. Uma destas colônias, então, foi usada para ser transfectada com os plasmídeos construídos. Nenhuma esporulação foi observada em qualquer um dos plasmídeos recombinantes (Dib1 de levedura e Dimp de S. mansoni), sugerindo que a super expressão dos genes bloqueou a esporulação da levedura. O fato das levedura não esporularem quando se utiliza ambos os genes, SmDimp e Dib1 da levedura, pode indicar que eles exerçam função semelhante, nos respectivos organismos. No entanto, novos experimentos precisam ser realizados para esclarecer definitivamente esta questão. Assim, os genes devem ser clonados em plasmídeos com promotores de expressão basal. Desta forma, Espera-se que a esporulação ocorra em níveis basais tornando possível confirmar se o gene SmDimp de S. mansoni pode complementar a função de seu ortólogo na levedura. Advisors/Committee Members: Elida Mara Leite Rabelo, Elida Mara Leite Rabelo, Monica Bucciarelli Rodriguez, Nelder de Figueiredo Gontijo.

▼ 

Tese de doutoramento em Ciências Biomédicas (Ciências Morfológicas) apresentada à Universidade de Lisboa através da Faculdade de Medicina, 2008

Protein-encoding genes are transcribed in the nucleus by RNA polymerase II as precursor RNAs that undergo extensive processing before being translocated to the cytoplasm for translation by the ribosomes. This spatial and temporal separation between RNA and protein synthesis offers an immense opportunity for regulation and quality control.When this study was initiated it was known from biochemical studies that human ß-globin (HBB) transcripts with mutations that impaired splicing or 3' end formation were unable to be exported to the cytoplasm, a phenotype identical to that seen in ß-thalassemia patients harbouring similar mutations (Antoniou et al., 1998). This result was consistent with the retention in the nucleus of incorrectly processed transcripts. Based on this initial observation we hypothesised the existence of a quality control mechanism to retain the incorrectly processed transcripts in the nucleus and proposed to elucidate the mechanism responsible for the observed retention. The first goal of this work was to determine the intranuclear localisation of the retained transcripts. To address this we used as a model system murine erythroleukemia (MEL) cells stably transfected with either wild-type or processing mutant HBB genes. The experimental approach was based on the direct visualisation of both normal and defective HBB transcripts using fluorescence in situ hybridisation and confocal microscopy. Nuclear transcripts of both wild-type and mutant HBB genes were detected only as intranuclear foci co-localising with the template gene locus. To determine the kinetics of transcript release from the site of transcription the cells were treated with the transcriptional inhibitors actinomycin D, α-amanitin and DRB. These drugs induced the rapid disappearance of nuclear foci corresponding to wild-type HBB RNA. In contrast, pre-mRNA mutants defective in either splicing or 3' end formation and which fail to be transported to the cytoplasm were retained at the site of transcription. These results indicated that the quality control mechanism responsible for the nuclear retention of incorrectly processed transcripts operates at the site of transcription and suggest that splicing and 3' end processing are rate limiting for release of mRNA from the transcription site. The next goal of this work was to determine the molecular players involved in the quality control mechanism that operates at the transcription site. Studies over the past years have indicated that there is extensive coupling between transcription, pre-mRNA processing and nuclear export of mRNA (reviewed by Bentley, 2005). One hypothesis to explain the retention of the mutant transcripts could be the absence of recruitment of proteins essential for the release and/or transport of the transcripts from the gene locus. Alternatively, the retention could be mediated by proteins that are bound to the nascent transcripts…

Advisors/Committee Members: Fonseca, M. Carmo, 1959-.

Tese de doutoramento, Ciências Biomédicas (Ciências Funcionais), Universidade de Lisboa, Faculdade de Medicina, 2012

Fundação para a Ciência e a Tecnologia (FCT, Bolsa SFRH/BD/31012/2006)

Advisors/Committee Members: Fonseca, M. Carmo, 1959-.

▼ 

Tese de doutoramento, Ciências Biomédicas (Ciências Morfológicas), Universidade de Lisboa, Faculdade de Medicina, 2010.

Inflammation was one of the first immune responses to be reported to exist and has been a focus of intensive research ever since (reviewed in Rocha e Silva, 1978; Medzhitov, 2010). During the course of an inflammatory response several components are involved, such as inflammatory inducers and mediators or different sensors that mediate the detection of a pro-inflammatory stimulus. Amongst the most studied pro-inflammatory mediators is the Interleukin-1β (IL- 1β). Interleukin-1β was one of the first Interleukins to be identified and represents one of the most important mediators of Inflammation and host responses to infection (reviewed in Dinarello, 2004). The large connection between misregulation of IL-1β release and the appearance of inflammatory diseases made this cytokine one of the “hotspots” of intensive research in the past years (reviewed in O'Neill, 2008). Nowadays, several diseases are being treated successfully using different methods that decrease IL-1β circulant levels or block its effects, such as using IL-1β receptor antagonists or by neutralizing IL-1β with monoclonal anti-IL- 1β antibodies (reviewed in Fitzgerald et al., 2005; Kalliolias et al., 2008; Lequerre et al., 2008; Martinon et al., 2009). The IL-1β secretion pathway is a “two-step” fashion mechanism, Production and Processing steps. The cytokine is produced in an inactive pro-form (pro-IL-1mainly upon activation of the nuclear factor-kB (NF-kB) transcription factor and posterior translation into protein. The second and processing step is mediated by active Caspase-1, that will give rise to its mature and secreted form (reviewed in Martinon et al., 2009). Caspase-1 is also synthesized as an inactive form that requires processing by the Inflammasome complex to become active (reviewed in Martinon et al., 2009). Upon Inflammasome formation, Caspase-1 becomes active, leading to subsequent IL-1β processing and posterior release. However, despite the increase knowledge that has been obtained during the past years, a lot still remains to be unveiled concerning the mechanisms involved in the regulation of IL-1β secretion and the effects elicited by this cytokine. Several genes involved in the regulation of IL-1β secretion were shown to be regulated by Alternative Splicing (AS), such as MyD88, IRAK2 and NOD2, among others (reviewed in Leeman et al., 2008). Moreover, the increasing number of cellular processes regulated by AS and the strong correlation between defects in Splicing and disease (reviewed in Leeman et al., 2008; Tazi et al., 2008), strongly suggest that AS may play a role in the initiation and regulation of an inflammatory response, particularly in the secretion of the pro-inflammatory cytokine IL-1β. In an attempt to identify the Splicing Factors and Regulators (SF) with a potential role in the secretion of IL-1β upon an inflammatory stimulus, we performed an RNAi-based screen. Briefly, we used a subset of the TRC…

Advisors/Committee Members: Moita, Luís Filipe Ferreira, 1973-.

▼ 

Abstract Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set of unrelated parallel machines, without preemption. Each job has a due date, weight, and, for eachmachine, an associated processing time and sequence-dependent setup time. Throughout this work,the objective function considered is to minimize the total weighted tardiness of the jobs, but otherobjectives, such as the minimization of the makespan and the minimization of the total slackness, are also discussed.Initially, this work proposes and analyses efficient implementations of several local search based heuristics to tackle the problem. Aspects such as the algorithms design and implementation aspectsare discussed. Then, the proposed heuristics are compared with other successful implementations, to highlight their advantages in terms of quality and computation time, specially for large instances.In order to measure the quality of the proposed solutions, their objective function values are compared to lower bounds of the problem. These bounds are obtained by a Non-Delayed Relax-and-Cut algorithm, based on a lagrangean relaxation of a time indexed formulation of the problem. It isalso used to develop a lagrangean heuristic, to obtain approximate solutions.To achieve maximum performance and memory saving, thus allowing to tackle large instances,the developed algorithms do not rely on third party solvers.Good solutions for instances with up to six machines and 200 jobs, and lower bounds for instan-ces with up to six machines and 80 jobs, were obtained within reasonable time. The obtained lowerbounds were particularly good for easy instances, proving the optimality of some solutions and pro-viding tight gaps for others. For more difficult instances, the obtained lower bounds were not so goodbut still significant.

Considere o problema de sequenciar um conjunto de tarefas, a serem processadas exatamente uma vez em qualquer máquina de um conjunto de máquinas não-relacionadas, sem preempção. Cada tarefa tem uma data de entrega, um peso e, para cada máquina, além de um tempo de processamento, um tempo de preparação dependente da sequência. Em todo este trabalho, o objetivo é minimizar a soma dos atrasos ponderados das tarefas, mas outros objetivos, como a minimização do makespan e da soma das folgas também são discutidos.Inicialmente, este trabalho propõe e analisa implementações eficientes de diversas heurísticas baseadas em buscas locais para abordar o problema. Fatores como o desenho e detalhes de implementação dos algoritmos são discutidos. As heurísticas propostas são então comparadas com outrasimplementações bem sucedidas, para mostrar suas vantagens em termos de qualidade e tempo de computação, principalmente para instâncias de grande porte.Para medir a qualidade das soluções, os valores de função objetivo das soluções obtidas são comparados com limites inferiores do problema. Para obter tais limites, um algoritmo Non-Delayed Relax-and-Cut é desenvolvido a partir de uma relaxação lagrangeana de uma…

Advisors/Committee Members: Geraldo Robson Mateus, Geraldo Robson Mateus, Gilberto de Miranda Junior, Marcone Jamilson Freitas Souza, Sebastián Alberto Urrutia.

▼ 

Tese de doutoramento, Ciências Biomédicas (Biologia Celular e Molecular), Universidade de Lisboa, Faculdade de Medicina, 2017

During transcription, RNA is synthesized by RNA polymerase II (RNA Pol II) using the information contained in the template DNA strand. RNA synthesis occurs inside the transcription bubble where the two strands of DNA are physically separated and the nascent transcript is hybridized to template strand through a ~8 base pair (bp) RNA-DNA hybrid. Latter, the molecular structure of the elongating RNA Pol II ensures that the nascent transcript leaves the transcription bubble physically separated from the template DNA. Therefore, it was widely believed that RNA-DNA hybrids were only transient byproducts of transcription. However, the past decade of research has shown those R-loops − RNA-DNA hybrids and a displaced single-stranded DNA−are abundant structures that play important roles in regulating gene expression and DNA recombination. Besides these physiological roles, R-loops also pose great threats to genome stability and should therefore be tightly regulated. Cells regulate the level of R-loops by employing enzymes like DNA/RNA helicases and nucleases to resolve the RNA moiety of R-loops. Additionally, various RNA processing factors are also known to prevent R-loop formation by sequestering the nascent RNA, thus preventing it from re-annealing to the template DNA. However, the signalling cascades and molecular switches that lead to the mobilization and activation of R-loop suppressors are essentially unknown. The activity of several RNA processing factors is regulated through phosphorylation, which in many cases is driven by serine/arginine protein kinases (SRPK) 1 and 2. These kinases phosphorylate the arginine-serine (RS) domain of various RNA processing factors classified as SR-proteins. Phosphorylation/de phosphorylation cycles regulate the function of SR-proteins and the timely binding to cis regulatory elements on the nascent RNA. However, the roles of both SRPK1 and SRPK2 in R-loop metabolism and genome stability have not yet been investigated. Herein, we identify a new role for RPK2 in preventing genomic instability through a mechanism involving the suppression of R-loops. We show that phosphorylation of the DEAD box helicase-DDX23 is necessary and sufficient to restore the genome stability in SRPK2-deficient cells through a process that requires its helicase activity. DDX23 is part of the spliceosomal U5 small nuclear ribonucleoprotein complex (U5 snRNP). We found that the role of DDX23 in suppressing R-loops does not require a functional U5 snRNP as depletion of either PRP8 or PRP6, core components of the U5 1 2 snRNP, does not drive genomic instability. Altogether, we found that phosphorylation of DDX23 by SRPK2 is a crucial event to maintain cellular R-loop levels, failure of which severely compromises genome integrity. Co-transcriptional R-loops impact on RNA Pol II transcription dynamics. For instance, they are involved in promoter-proximal pausing and promote efficien…

Advisors/Committee Members: Almeida, Sérgio Fernandes de, 1979-, Fonseca, M. Carmo, 1959-.

▼ 

Verificação por Equivalência é um dos componentes chave da metodologia de verificação formal atual para sistemas digitais. Ela é técnica de Verificação Formal mais utilizada atualmente pela indústria para verificação de igualdade entre duas descrições de um circuito. Diversas abordagens baseadas BDDs e SAT obtiveram um considerável sucesso nesta área. No entanto a crescente distância entre a capacidade dos resolvedores atuais e a complexidade das instâncias a serem verificadas motivam a exploração de novas alternativas, em busca de soluções melhores. Esta dissertação apresenta um núcleo inteligente para processamento distribuído de resolvedores SAT em Verificação por Equivalência. Especificamente, o núcleo proposto explora o processamento paralelo de resolvedores SAT e propõe uma nova técnica para a identificação de similaridades estruturais entre os circuitos a serem verificados. Ao final, são apresentados resultados que comprovam a eficiência da metodologia proposta.

Equivalence Checking is one the of the key components in formal verification for digital systems. It is also one of the most widely used approaches in industry for functional equivalence verification of different designs. A number of recently proposed BDD and SAT based approaches have met with considerable success in this area. However, the growing gap between the current solvers capabilities and the increasing complexity in digital designs lead to exploring alternative, better solutions. This work proposes an intelligent kernel for distributed processing of SAT solvers in Equivalence Checking. Specifically, the proposed kernel exploits a new technique for identifying structural similarities between the circuits. Finally, results of verification using the proposed methodology are presented.

Advisors/Committee Members: Claudionor Jose Nunes Coelho Junior, Claudionor Jose Nunes Coelho Junior, Ricardo dos Santos Ferreira, Antonio Otavio Fernandes, Sergio Vale Aguiar Campos.

▼ 

Esse trabalho aborda um estudo sobre o método de iluminação global conhecido como radiosidade, num esforço de obter uma implementação eficiente para determinar a mesma. A radiosidade é um método clássico e muito importante para a computação gráfica ao sintetizar imagens foto-realísticas, pois foi um dos primeiros a considerar informações de vários objetos para determinar a iluminação de uma cena. Como o método apresenta uma grande demanda de processamento, foi utilizada a GPU como forma de otimização, pois a mesma possui uma capacidade de processamento massivo considerável. Foram realizadas duas implementações distintas que utilizam-se da GPU para acelerar alguma parte ou todo o algoritmo. Como resultado, foram comparados diferentes métodos para resolver sistemas de equações lineares em ambos, GPUs e CPUs, e propusemos uma abordagem para melhorar a determinação de visibilidade da implementação relacionada à GPU.

This work consists of a study about the global illumination model known as radiosity, in an effort to achieve an efficient implementation on modern hardware. Radiosity is a classic and very important method in computer graphics. It is the first proposed method to achieve photo-realism as it considers interactions among the objects of the scene. As the method has a high processing demand, we propose the use of modern GPUs, with their massive processing capacity, in an attempt to speed up the computation. We experimented with two distinct implementations that use GPUs to accelerate part or all of the method. The first implementaion is similar to the original proposal of radiosity, and the GPUs were used to solve the simultaneous linear equations. The second implementation is derived from an extension to the original radiosity method that was designed for processing in GPUs. As results, we compared different methods to solve the simultaneous linear equations, on both GPUs and CPUs and we proposed an improvement on the GPU implementation related to the determination of visibility. Our modifications improves the quality of the output image while preserving the interactive charateristic of the method variation.

Advisors/Committee Members: Renato Antonio Celso Ferreira, Renato Antonio Celso Ferreira, Joao Luiz Elias Campos, Luiz Chaimowicz.

▼ 

A Ciência da Computação tem evoluído e alcançado diversas áreas do conhecimento tais como a biologia, a geografia, a astronomia, entre outras. Os Sistemas de Fluxo de Trabalho Científico foram criados com o objetivo de ajudar os pesquisadores dessas áreas nos seus processos de análise de dados. Esses sistemas permitem aos cientistas criar e organizar tarefas relativas aos seus experimentos; executar essas tarefas eficientemente e transparentemente em um ambiente distribuído; assim como monitorar toda a execução. Os desafios para o projeto e a implementação desses sistemas são muitos, principalmente devido às características das aplicações que geram os fluxos de trabalho científicos. Elas são consideradas aplicações intensivas em dados e processamento as quais criam uma enorme quantidade de dados durante a execução e executam por longos períodos. Desta forma, alguns dos desafios para projetar os sistemas de fluxo de trabalho científico são: armazenar, pesquisar e gerenciar grandes bases de dados distribuídas, gerenciar os dados de entrada e de saída, escalonar e monitorar a execução desses fluxos de trabalho em ambientes distribuídos, assim como tratar a ocorrência de falhas tanto de software quanto de hardware que podem acontecer durante a execução. Este trabalho investiga o uso de mecanismos que, de forma transparente, aumentem a disponibilidade de sistemas de fluxo de trabalho científico, de tal forma que o trabalho a ser refeito após uma falha no sistema seja mínimo. Esses mecanismos utilizam como base características próprias desses sistemas para a construção de um sistema de armazenamento dos dados necessários para a recuperação das aplicações após uma falha. Esse sistema provê um armazenamento assíncrono dos dados de tal forma que não há necessidade do travamento da execução das aplicações para que ele aconteça. Os resultados experimentais mostram que o sistema é capaz escalar a grandes bases de dados, e que a nossa abordagem introduz muito pouco overhead na execução das aplicações.

Scientific workflow systems provide scientists with a suite of tools and infrastructure to build data analysis applications from reusable components and execute them. The challenges to implementing workflow middleware support for scientific applications are many. Analysis oftentimes requires processing of large volumes of data through a series of simple and complex operations. To support data processing efficiently, a workflow middleware system should leverage distributed computing power and storage space (both disk and memory space) and implement optimizations for large data retrieval and scheduling of I/O and computation components. Another challenging issue is to enable fault tolerance in the middleware fabric. An analysis workflow with complex operations on large data can take long time to execute. The probability of a failure during execution should be considered. Efficient mechanisms are needed to support recovery from a failure without having to redo much of the computation already done. In this thesis, we propose and…

Advisors/Committee Members: Dorgival Olavo Guedes Neto, Wagner Meira Junior, Renato Antonio Celso Ferreira, Francisco José Silva e Silva, Renato Antonio Celso Ferreira.

▼ 

Sistemas computacionais distribuídos são uma valiosa ferramenta para distribuição e processamento de informação na solução dos mais diversos problemas. Um problema em especial é a distribuição de recursos entre máquinas de uma rede. Aplicações que usam algoritmos embaraçosamente paralelos não precisam se preocupar com essa distribuição. As demais aplicações devem se preocupar com qual nó possui uma determinada informação e qual irá executar determinada tarefa. Dependendo do tipo de aplicação essa funcionalidade deve ser pensada de forma a suportar entrada e saída dos nós da rede mas, ao mesmo tempo, produzindo o mínimo de modificações no sistema quando isso ocorre. A técnica de hash consistente possui essa funcionalidade de flexibilidade com pouca modificação do sistema. Essa idéia é utilizada nas redes baseadas em tabelas hash distribuídas (DHT). As DHTs por sua vez são a base de diversas redes par-a-par que denominadas estruturadas. As redes DHTs possuem um problema inerente de desbalanceamento de carga devido à forma como são gerados os identificadores dos nós nessas redes. Esses problemas vêm recentemente sendo estudados e diversos algoritmos para lidar com o problema de balanceamento de carga nessas redes foram desenvolvidos recentemente. Com o objetivo de organizar esse conhecimento de forma a permitir a comparação entre os diversos algoritmos, bem como servir de base para o desenvolvimento de novos, neste trabalho será descrita uma taxonomia para os algoritmos de balanceamento de carga em redes baseadas em DHTs. Foram analisados diversos trabalhos da área e todos foram classificados de acordo com a taxonomia criada.

Distributed computational systems are a valuable tool for distributing and processing information and are employed in the solution of several problems. A particular problem is the distribution of resources among peers of a network. This is not a concern for applications based on embarrassingly parallel algorithms. Many other applications, however, should be able to determine which node has a specific information or could perform a certain task. Depending on the application to be considered, this functionality should be designed to support network churn with minimum alteration in the system. This is the case of the consistent hash technique which corresponds to the main idea behind networks based on Distributed Hash Tables (DHT) that are the base of several structured peer-to-peer networks. An important issue of DHT networks is its inherent load unbalancing due to the way in which peer identifiers are created. This problem has received much attention recently and, as a consequence, several algorithms have been proposed. In order to organize all this knowledge, compare the algorithms proposed in the literature, and provide a base for the development of new strategies, we propose in this work a taxonomy for load balancing algorithms for DHT Networks. As a result of this study, we analyzed several works and classified them according to the proposed taxonomy.

Advisors/Committee Members: Renato Antonio Celso Ferreira, Dorgival Olavo Guedes Neto, Dorgival Olavo Guedes Neto, Wagner Meira Junior.

▼ Extrair informação de grandes bases de dados é um desafio das novas demandas da Ciência da Computação. Além disso, diversas técnicas de Mineração de Dados são propostas continuamente na literatura. Tais algoritmos são computacionalmente intensivos, além do fato de processarem entradas de dados muito grandes. Assim, há uma nova tendência em direção ao alto desempenho de processamento e montagem de clusters de computadores, a um custo mais razoável que os supercomputadores do passado. Essa tendência nos leva a um cenário em que o alto desempenho é alcançado por eficientes implementações de aplicações paralelas e distribuídas. O Anthill é uma solução para processamento distribuído em clusters de computadores onde um alto desempenho é obtido em execuções eficientes e escaláveis de diversos algoritmos de Mineração de Dados. Ele fornece um framework para o desenvolvimento e a execução de aplicações em ambiente distribuído, onde as aplicações devem ser decompostas em filtros que se comunicam através de streams de dados, como em um pipeline. O processo de desenvolvimento das aplicações entretanto demanda do programador decompor as aplicações, que não é o caminho natural de desenvolvimento dos programas. Este trabalho apresenta uma ferramenta de geração semi-automática de filtros a partir de uma implementação seqüencial do algoritmo. Esse processo é divido em duas etapas: a primeira é o particionamento em filtros do código seqüencial, seguido pela geração do código para cada um dos filtros identificados. Este trabalho tem como foco a segunda etapa, a geração do código. Para a primeira etapa, nós realizamos de forma semi-automática alguns passos a serem automatizados em trabalhos futuros. Esse processo determina as dependências de dados no código, e identifica os pontos de corte do mesmo. A partir deste passo, é gerado uma versão anotada do código seqüencial, contendo as informações para sua divisão em filtros. A geração dos filtros é feita a partir do código anotado. Basicamente, as anotações contêm um grafo direcionado onde os vértices representam os filtros e as arestas representam os dados que são trafegados entre os filtros. Nós implementamos um gerador de código fonte onde a entrada é um algoritmos seqüencial escrito em C e a saída são os filtros, também em C, com as extensões do Anthill. A maioria das adaptações necessárias para Anthill são geradas automaticamente por essa ferramenta. O gerador de código automático foi validado usando três aplicações de Mineração de Dados que já haviam sido implementadas no Anthill. Foram gerados de forma automática o código dos filtros Anthill a partir das versões seqüenciais. Nós avaliamos o desempenho do código gerado e observamos que o resultado é similar ao código gerado manualmente na maioria dos casos. Este é um bom resultado, dado que o custo de implementação do código seqüencial é bem menor do que a implementação paralela dos filtros para o Anthill. Também foram observadas algumas otimizações presentes na implementação manual que podem ser realizadas automaticamente pela… Advisors/Committee Members: Walfredo da Costa Cirne Filho, Renato Antonio Celso Ferreira, Renato Antonio Celso Ferreira, Dorgival Olavo Guedes Neto, Wagner Meira Junior.

▼ As veredas representam um importante e frágil ecossistema entre as comunidades aluviais do cerrado, as quais se desenvolvem sob condições específicas de geologia, geomorfologia e hidrologia. As veredas são de fato, uma vegetação complexa composta por uma sucessão de fisionomias que vão desde as gramíneas até os estratos arbóreos. As veredas são protegidas pelas leis brasileiras, mas sua extensão e condições ainda são desconhecidas. Como um ambiente úmido no contexto do semi-árido, as veredas são facilmente detectadas por dados de sensoriamento remoto, mas sua diferenciação de outras formações ribeirinhas , quando utilizados dados óticos, ainda causa certa confusão. Por ser muito sensível à umidade, radar de abertura sintética, proveniente do RADARSAT, possuem um potencial considerável para a delimitação das veredas, porém, imagens radar não são capazes de distinguir os diversos estratos fisionômicos deste ambiente, o que é possível como dados óticos. Nesta pesquisa, uma metodologia é descrita utilizando tanto dados radar, para a delimitação das veredas , através da abordagem da segmentação, quanto a classificação de dados óticos provenientes do ASTER, para a caracterização. A delimitação e classificação do ambiente de vereda sã otimizadas utilizando o conhecimento espacial prévio na construção de zonas tampão. Três algoritmos de segmentação (K-means, ISODATA e MAMSEG) foram testados em imagensde radar com parâmetros de ângulos de incidência e períodos hidrológico diferenciados, na tentativa de se escolher o melhor segmentador para os melhores parâmetros de imagem. De forma paralela, imagens ASTER foram classificadas com o intuito de se obter as diversas fisionomias inerentes às veredas. Os resultados mostram que, mesmo com valores baixos de validação, os dados RADARSAT foram suficientes para a delimitação das veredas largas e muito úmidas. Uma vez que, não há necessidade de dados de campo. Por sua vez, a classificação dos dados ASTER forneceu bons resultados para a classificação das principais fisionomias vegetais apesar de sua largura ser, muitas vezes, a um ou dois pixels de 15m. A junção destes dois produtos faz com que a carência de um seja suprida pelas vantagens dos outros aumentando a capacidade de se extrair informações sobre as veredas Advisors/Committee Members: Philippe Maillard, Cristina Helena R Rocha Augustin, Silvana Amaral Kampel, Philippe Maillard.

▼ 

Esta tese trata do problema de adquirir os modelos de uma cena a partir de imagens, onde a correspondência entre as intensidades dos pixels das imagens e as cores reais da cena não podem ser explicadas a partir de um modelo de iluminação local da interação da luz com a cena. Mais especificamente, o problema é abordado em dois casos particulares tratados em cenários distintos. No primeiro caso, têm-se cenas submersas em água turva onde a luz interage globalmente com o meio, ao qual é desenvolvida uma metodologia para extrair a geometria da cena, utilizando-se um modelo de propagação da luz na água integrado a um algoritmo de visão estéreo, recuperando o mapa de disparidades a partir de um par estéreo da cena adquirido em pontos de vista distintos. Resultados experimentais comparam favoravelmente o método proposto nesta tese a um método de estéreo denso bem estabelecido. O método permite, ainda, restaurar as imagens da cena subaquática. No segundo caso, têm-se cenas onde a luz interage globalmente com objetos com superfícies homogêneas, reflexivas e translúcidas, apresentando sombras e inter-reflexão entre objetos, ao qual é desenvolvido um método para adquirir os parâmetros de um modelo de reflectância de cada objeto da cena, resolvendo um sistema de equações fatorado obtido a partir de uma única renderização e tendo como restrições uma imagem da cena, cuja solução é mais estável e eficiente em comparação a métodos similares.

This thesis deals with the problem of acquiring the models of a scene from its images, where the correspondence between the image pixels intensities and the real colors of the scene cannot be determined using a local illumination model of the interaction of the light with the scene. More specifically, the problem is treated in two particular cases in distinct scenes. In the first case, we have the underwater scenes in muddy water where the light interacts globally with the environment, to which we developed a methodology to extract the scenes geometry, by integrating a light propagation model into a stereo vision algorithm and recovering the disparity maps from images pairs acquired from distinct viewpoints. Experimental results are compared to known methods. The method allows to restore the images of theunderwater scene. In the second case, we have a scene where the light interacts globally with objects that has homogeneous, reflexives and translucent surfaces, presenting shades and Inter-reflection between objects, to which we developed a method of recovering the reflectance parameters to each object of the scene, by solving a factorized equation system obtained using just one rendering and having as restrictions an image of the scene, whose solution is more steady and efficient in comparison to similar methods.

Advisors/Committee Members: Rodrigo Lima Carceroni, Luiz Carlos Pacheco Rodrigies Velho, Renato Cardoso Mesquita, Geraldo Robson Mateus, Rodrigo Lima Carceroni, Mario Fernando Montenegro Campos, Mario Fernando Montenegro Campos, Alexei Manso Correa Machado.

Tese de mestrado, Ciência Cognitiva, Universidade de Lisboa, Faculdade de Ciências, Faculdade de Letras, Faculdade de Medicina, Faculdade de Psicologia, 2013 Advisors/Committee Members: Almeida, Jorge, Marques, J. Frederico, 1966-.

▼ 

Este trabalho apresenta uma metodologia de desenvolvimento do controle para robôs móveis de arquitetura híbrida integrando tolerância a falhas adaptativa. A realização de tarefas críticas ou perigosas por robôs torna a tolerância a falhas um requisito fundamental. Os robôs devem ser capazes de realizar as tarefas desejadas mesmo na presença de defeitos, implementando a tolerância a falhas através do uso das redundâncias que existam em um único robô ou distribuída nas diversas competências individuais dos times cooperativos. Na concepção de robôs, principalmente no caso dos autônomos, é necessário se trabalhar com muitas restrições: o hardware não é limitado apenas pelo custo, mas também pela possibilidade de ser incorporado ao robô móvel; o consumo dos componentes limita a autonomia do sistema; a percepção e controle devem ser realizados em tempo real. Com estas várias restrições, a tolerância a falhas ideal deve maximizar a disponibilidade e confiabilidade total do sistema e permitir o uso inteligente dos recursos disponíveis em qualquer situação. O controle do robô deve se adaptar as condições ambientais, condições do hardware e do software e aos objetivos da tarefa ou missão específica que esta sendo realizada. A metodologia desenvolvida, a qual por ser automatizada, facilita o processo de síntese das políticas de adaptação e a integração destas ao controle de forma maximizar a confiabilidade ou o desempenho em função do estado global do sistema.

This work presents a novel architectural design methodology, which enables weaving fault-tolerance into hybrid architecture control frameworks. The beneficial aspects fostered by fault tolerance greatly surpass the overhead in project development. Dataflow processing paradigm is based on functions and abstract data elements, providing a simple, yet powerful, description power. The simple structure allows the inclusion of redundant information and processing elements within the control. Redundancies elicited by dataflow automatically enable alternative configurations of available functional blocks. The methodology also gives the designer the freedom to define requirements and restrictions for both control performance and reliability. A control graph contains all the information necessary to optimize the robot resources usage and also captures all the necessary adaptations for the system. This graph may be automatically generated combining the hybrid control description and the dataflow information. The thesis shows the results from a prototype of hybrid architecture for a Nomad robot. The resulting fault tolerant hybrid architecture provides real time execution of control and fault recovery. Experiments were carried out to demonstrate the gain in reliability versus the added overhead.

Advisors/Committee Members: Antonio Otavio Fernandes, Mario Fernando Montenegro Campos, Antonio Otavio Fernandes, Mario Fernando Montenegro Campos.

▼ We have been witnessing a continuous growth in the use of information technology in all areas of human knowledge in the last decades. In parallel, we may also observe an increase in the degree of interactiveness provided by computer-based systems as a consequence of either better connectivity or improved interfaces, including multimedia resources such as video, audio, or virtual reality. We may say that interactive computer systems, that is, systems with which users interact continuously, getting and providing information, become a common place in our society. From bank transactions to cell phones, we are almost always interacting with systems and even with other users through these systems. We should note that current systems allow not only human-computer interactions, but also a wide variety of user-user interactions, which are obviously richer and more complex. A significant portion of system-mediated interactions is synchronous, that is, users submit information or a request to the system and wait for a response, then submit another piece of information and the process continues. The Web, in particular the HTTP protocol, is an example of synchronous interaction. In fact, similar interaction patterns exist since the first computer systems in the 1960 s. These interactions are usually complex and intriguing. It is quite hard to determine exactly the factors that led a user to behave as observed. First because the information we have about users is sparse and variable, in terms of both the instantaneous conditions surrounding the observed behavior and his or her background. It is remarkable to note that the interactions are not isolated, but successive interactions become a loop feedback mechanism, where the user behavior affects the system behavior and vice-versa. Further, we should note that the number of users in Internet services is usually large, and they interact in an indirect fashion through the server, where their simultaneous demands may generate contention. There is strong evidence that much of the user behavior is reactive, that is, the user reacts to the instantaneous conditions at the action time. The main hypothesis of this dissertation is that the real world is reactive. This concept means that the user behavior varies according to some factors related to the server and the application being provided. The main hypothesis of this dissertation is that interactive computer-based systems has a strong reactive component. The thesis of this dissertation is to research, define, characterize, and model reactivity in interactive systems, in particular Internet-based systems. Understanding users reactivity has applicability to several scenarios, from system evaluation and simulation to system improvement, such as personalization. The main challenge is to identify what is the limit of reactivity characterization. The main motivation of this work is to understand how users interact with the system, allowing to provide services with better performance and to understand better the business applications. The… Advisors/Committee Members: Wagner Meira Junior, Wagner Meira Junior, Mohammed J. Zaki, Paulo B. Góes, Raquel Oliveira Prates, Virgilio Augusto Fernandes Almeida.

▼ 

O recente desenvolvimento das tecnologias de aquisição de dados fez com que cada vez tivessemos mais dados disponíveis para processamento, entretanto, o aumento do volume de dados disponível criou uma demanda de processamento que extrapola a capacidade de apenas um computador, dessa forma, aplicações científicas foram forçada a utilizar recursos distribuídos e compartilhados. Entretanto, a maioria das aplicações científicas existentes foram desenvolvidas seqüencialmente e não eram capazes de utilizar recursos distribuídos. Em resposta a essas necessidades foram introduzidos os sistemas de fluxo de trabalho científicos, os quais permitiram a utilização de aplicações sequênciais em ambientes distribuídos, possibilitando a exploração de grandes bases de dados. A introdução desses sistemas é baseada na observação de que aplicações científicas são construídas pela composição de múltiplos estágios de computação, como em pipelines tradicionais, que precisam ser executados em grandes coleções de dados. Dessa forma, os sistema de fluxo de trabalho permitiram que os estágios de computação da aplicação fossem mapeados em estágios de fluxos de trabalho, os quais são compartilhados entre usuários e executados em ambientes distribuídos. Neste trabalho, apresentamos um sistema de fluxo de trabalho único no sentido de que o mesmo foi especialmente desenvolvido para facilitar a execução dessas aplicações em ambientes distribuídos utilizando bancos de dados para armazenamento de dados científicos. Nosso sistema é otimizado para execução fluxos de trabalho intensivos em dados, pois nos preocupamos com as tarefas de gerenciamento de dados. Os resultados experimentais obtidos com este sistema mostram que podemos alcançar speedups próximos do linear para aplicações sofisticadas, criadas por múltiplos componentes.

The increase of the demand of computation and data have forced the scientific applications to use distributed and shared resources. The scientific workflow systems have been introduced in response to the demand of researcher from several domainsof science who need to process and analyse this increasingly larger experimental datasets. The introduction of the workflow systems is based on the observation that scientific applications are constructed by the composition of multiple computation stages as a standard pipeline that need to be executed on very large data collection. In such a way, the scientific workflow systems had allowed the computation stages to be mapped into workflow stages, which can be efficiently executed in distributed systems. In this work we present scientific workflow system that is unique in sence that it have been developed to facilitate the execution of scientific applications in distributed systems using databases to store scientifc data. Our system is optimized for data-intesive workflows, meaning that we are very concerned with data management issues. The experimental results with our system have shown that we can achieve linear speedups for fairly sophisticated application, created from multiple…

Advisors/Committee Members: Renato Antonio Celso Ferreira, Renato Antonio Celso Ferreira, Guilherme Horta Travassos, Dorgival Olavo Guedes Neto, Wagner Meira Junior.

▼ 

Este trabalho trata do Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas, para o qual devem ser desenvolvidas rotas para atender as demandas de coleta e entrega de um conjunto de consumidores. Cada consumidor deve ser atendido por uma única rota, a carga recebida é trazida de um depósito central, para onde também é levada toda a carga coletada. A capacidade dos veículos utilizados não deve ser violada em nenhum ponto das rotas. O problema é abordado de maneira heurística e exata. Inicialmente, são desenvolvidas heurísticas híbridas baseadas em idéias de diversas metaheurísticas, em especial ILS, GRASP e VND. Essas heurísticas são testadas em diversas instâncias e comparadas aos melhores resultados da literatura, obtendo resultados competitivos com os melhores algoritmos existentes. É desenvolvido um método exato Branch-and-price e, nesse contexto, são propostas novas estratégias para a resolução do subproblema, um Problema de Caminho Elementar Mínimo com Restrição de Recursos. Em experimentos computacionais, essas estratégias demonstram redução significativa no tempo computacional da resolução da Geração de Colunas. É apresentada também uma estratégia em que limites inferiores obtidos a partir da geração de colunas são utilizados no processo de decisão do branching. O algoritmo Branch-and-price é testado e comparado a um algoritmo Branch-and-cut-and-price da literatura.

This work adresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery, where routes must be devised to fulfil the pickup and delivery requests of a set of customers. Each customer must be served by only one route, the load it receives isbrought from a central depot, to where the picked-up load is also taken. The capacity of the used vehicles must not be violated at any point of the routes. Heuristics and an exact algorithm are proposed to solve the problem. Initially, we devise some heuristics based on ideas of many metaheuristics, specially ILS, GRASP, and VND. These heuristics are tested in many instances and are compared to the best results of the literature, obtaining results comparable to the best existing algorithms. Afterwards, a Branch-and-price method is developed, and in this context, we propose new strategies to the resolution of the subproblem, an Elementary Resource Constrained Shortest Path Problem. Based on computational experiments, these strategies show considerable reduction on the computational time of the Column Generation resolution. We present a strategy in which lower bounds obtained from the column generation are used in the branching process. The Branch-and-price algorithm is tested and compared to a Branch-and-cut-and-price algorithm from the literature.

Advisors/Committee Members: Geraldo Robson Mateus, Geraldo Robson Mateus, Sergio Ricardo de Souza, Alexandre Salles da Cunha, Alysson Machado Costa.

▼ 

Quasiperiodic time series are sufficiently common in natural and Physical Sciences, Engineering, Medicine and Social Sciences. The techniques available in the literature for time series are not always suitable for analyzing and modelling quasiperiodic time series, because this behavior tends to mask any other deterministic behavior, but the quasiperiodic pattern that possibly exists. However, little attention has been given to the development of specific tools to deal with this kind of time series. In the analysis, modelling and possibly forecasting of quasiperiodic time series, one of the first steps, which is of great interest, is to verify if there is some deterministic pattern in the time series apart from the quasiperiodic one. In this context, the hypothesis testing based on surrogate data is useful to shed some light in the detection of determinism (apart from the quasiperiodic behavior). The proposed of this work is to verify the presence of intra-cycle determinism in quasiperiodic time series, by means of surrogate data testing.

Séries temporais com comportamento quase-periódico são bastante comuns nas ciências naturais, exatas, engenharias, áreas social e médica. As técnicas disponíveis na literatura para séries temporais, nem sempre são adequadas para analisar e modelar séries quase-periódicas, uma vez que o comportamento quase-periódico tende a ocultar qualquer outro comportamento determinístico, além do padrão quase-periódico. Todavia, pouca atenção tem sido dada ao desenvolvimento de ferramentas específicas para lidar com esse tipo de séries. Na análise, modelagem e, possivelmente, previsão de séries temporais quase-periódicas, um dos primeiros passos de grande interesse é verificar se há algum padrão determinístico na série temporal além do comportamento quase-periódico. Neste contexto, o teste de hipóteses baseado em séries sub-rogadas vem auxiliar na detecção de determinismo subjacente ao comportamento quase-periódico. Este trabalho propõe um teste de hipóteses baseado em dados sub-rogados para verificar a presença de vínculo determinístico intra-ciclo em séries temporais quase-periódicas. Neste sentido, procurou-se avaliar as técnicas disponíveis na literatura para a geração das séries sub-rogadas. Os resultados obtidos mostram que, na presença de comportamento quase-periódico, tais técnicas nem sempre são adequadas. São discutidas algumas das dificuldades encontradas e sugeridos procedimentos alternativos, tal como a redução dos ciclos e da tendência, para a execução do teste de determinismo usando dados sub-rogados. Uma vez reduzido o ciclo da série quase-periódica, obtém-se uma série residual correspondente. O teste de hipótese baseado em séries sub-rogadas, proposto neste trabalho, consiste em gerar um conjunto de séries sub-rogadas que preservam algumas características estatísticas da série residual analisada, e destroem outras.

Advisors/Committee Members: Luis Antonio Aguirre, Eduardo Mazoni Andrade Marcal Mendes, Luis Antonio Aguirre.

▼ 

O objetivo deste trabalho é propor métodos para realizar a extração de dados em redes de nós sensores sem fio por meio da utilização de robôs móveis. A abordagem a ser apresentada representa uma alternativa aos algoritmos de roteamento em redes de sensores que tentam minimizar o custo em energia associado à transmissão de dados. Este trabalho é motivado por aplicações como, por exemplo, monitoramento do ambiente e exploração de ambientes inóspitos. Além da tarefa de extração de dados, o robô pode ser usado para deposição e recalibração de nós sensores, fusão de dados e manutenção da cobertura e conectividade da rede. Aspectos referentes à navegação do robô e exploração do ambiente também são endereçados. Foram implementados dois métodos de extração de dados: i) Método Reativo, no qual a quantidade de dados coletados pelos sensores é representada por meio de funções de potencial cujo gradiente atrai o robô e ii) Método Híbrido, que inclui em sua metodologia heurísticas para resolução do Problema do Roteamento de Veículos (VRP), onde o objetivo é distribuir um conjunto de nós clientes entre um conjunto de veículos e gerar rotas otimizadas em cada agrupamento formado. Esses dois métodos tentam minimizar variáveis como trajetória percorrida, tempo de realização da tarefa, quantidade de dados perdidos, etc. Ambos foram avaliados em um ambiente simulado com 60 nós sensores e com até 10 robôs. Ao final deste texto, resultados relativos à trajetória do robô, eficiência, perdas de dados na rede e quantidade de dados coletados pelo robô, são comparados e discutidos.

The goal of this work is to propose methods for data extraction in wireless sensor networks using mobile robots. This approach represents an alternative to the routing algorithms used in sensor networks that try to minimize energy consumption associated with data transmission. The methods developed here are motivated by applications such as environment monitoring and inhospitable environment exploration. In addition to the data extraction task, the robots can be used for node deployment and re-calibration, data fusion and coverage and connectivity repair. Aspects related to robot navigation and environment exploration are addressed as well. Two methods for data extraction were implemented: i) Reactive Method in which the data collected in the sensor node is modelled as a potential function whose gradient attracts the robot and ii) Hybrid Method, that includes heuristics for the resolution of Vehicle Routing Problem (VRP), where the objective is to distribute a set of clients among a set of vehicles and create optimized routes in every group. These methods try to minimize variables as path trajectory, total task time, data loss, robots energy, etc. Both were evaluated in a simulated environment with 60 sensor nodes and up to 10 robots. Finally, numerical results related to path trajectory, efficiency, data loss and data extracted by the robot are compared and discussed.

Advisors/Committee Members: Guilherme Augusto Silva Pereira, Mario Fernando Montenegro Campos, Mario Fernando Montenegro Campos, Guilherme Augusto Silva Pereira, Diogenes Cecilio da Silva Junior, Geraldo Robson Mateus.

▼ 

Ver o arquivo de provas fotográficas da Rádio Nacional do Rio de Janeiro é reviver a Época de Ouro do Rádio, constatar sua importância documental e crer que ações de preservação e acesso deverão ser tomadas. Por meio da investigação pautada na Ciência da Conservação desenvolvemos o diagnóstico do estado de conservação do acervo, os protocolos de gerenciamento de risco e a proposta de digitalização. Ao ampliar o acesso deste arquivo, permitimos que ele fosse revisto e reencontrado, potencializando a pesquisa teórico-prática e transformando-a em um piloto incentivador para uma política de divulgação do patrimônio cultural. Pois preservar é também comunicar, perpetuar e propagar a memória.

To see the archive of photographic proofs of Rio de Janeiros National Radio is to revive the Radios Golden Age, to ascertain its documental importance and to believe that preservation and access actions must be taken. We intend with this investigation according Conservation Science to produce the diagnosis of the collections conservation state, the risk management and to purpose the digitalization practice. When we make public the archive access we intend it was reviewed and recovered, enlarging the theoretical-practice research and becoming it as a stimulating pilot for a cultural heritage access and publicity policy. For preserving is also communicating, perpetuating and propagating memory.

Advisors/Committee Members: Luiz Antonio Cruz Souza, Luiz Antonio Cruz Souza, Yacy Ara Froner Goncalves, SOLANGE SETTE GARCIA ZUNIGA.

▼ 

A maioria das pesquisas feitas sobre calibração de fontes de luz pontuais baseiam-se no modelo de fontes distantes, isto é, se propõem a determinar a direção de um iluminante localizado a uma distância infinita da cena. Esse modelo é conveniente principalmente para as aplicações baseadas na iluminação solar, mas revela-se inadequado quando os iluminantes estão em uma distância relativamente próxima da cena - situação comum em ambientes fechados, onde geralmente a claridade parte de um conjunto de lâmpadas localizadas a poucos metros do observador. Este trabalho apresenta uma nova abordagem para a calibração de fontes de luz cuja principal vantagem está em considerar que as fontes pontuais são próximas (não distantes). Assim, o objetivo da calibração é recuperar não a direção, mas as coordenadas tridimensionais do ponto emissor de luz. O método proposto não faz qualquer restrição sobre as características das superfícies dos objetos, requer um conjunto mínimo de informações sobre a cena e é estatisticamente ótimo, no sentido de considerar as métricas de erro baseadas em um modelo realístico de propagação de ruídos. Em paralelo, o método também é capaz de realizar a reconstrução parcial da geometria da cena: são claculadas as coordenadas tridimensionais de alguns pontos-chave dos objetos, como extremidades e vértices. Os testes realizados, tanto com simulações em computador quanto com cenas reais, comprovam a eficácia do método mesmo na presença de ruídos significativos. Além disso, o tempo requerido para a solução de uma instância do problema - na ordem de décimos de segundo, utilizando um computador pessoal comum - sugere que o método poderá ser utilizado em aplicações de tempo real.

Most researches done so far about punctual light sources are based on the model of directional sources, i.e., they determine the direction of an illuminant placed in an infinite distance from the scene. This model is convenient mainly for solar-light based applications, but turns out to be inadequate when the illuminants are relatively close to the scene an indoor typical situation, where the illumination often arises from a set of lamps located a few feet from the observer. In this work we propose a novel approach for this problem. Its main advantage is to consider that the sources arent far from the scene. So, the objective is to retrieve the sources 3-D coordinates instead of its direction. The proposed method doesnt care about objects surface properties (the so-called BRDF), is based on very little knowledge about the scene, and is statistically optimal, because error metrics follows a realistic noise-propagation model. In parallel, the method is able to perform partial scene reconstruction: it retrieves the 3-D coordinates of certain points of objects, such as vertexes and tips. A series of tests were performed both with computer-generated simulations and real scenes. They prove that the method is precise even in presence of expressive noise.Besides, the average time spent to solve an instance of the problem about tenths of a…

Advisors/Committee Members: Luiz Chaimowicz, Rodrigo Lima Carceroni, Rodrigo Lima Carceroni, Mario Fernando Montenegro Campos.

▼ 

Apresentamos uma arquitetura paralela para a renderização e ciente de múltiplos pontos de vista em um cluster de GPUs. Nossa abordagem utiliza um renderizador de light _eld para reconstruir os pontos de vista desejados a partir de um conjunto de imagens da cena. Para permitir a renderização de cenas dinâmicas, geramos as amostras novamente a cada quadro ao invés de gerar um bu_er de imagens. Ao mesmo tempo, nossa paralelização permite que cada ponto de vista utilize qualquer uma das amostras geradas, evitando trabalho redundante. A e_ciência da solução foi avaliada por meio de modelos matemáticos e validada por meio de medições de speedup e e_ciência. Concluímos que a solução proposta é escalável e pode suportar renderização a taxas interativas.

We present a parallel architecture to e_ciently render multiple viewpoints on a cluster of GPUs. Our approach employs a light _eld renderer to reconstruct the desired views from a set of images of the scene. To allow the rendering of dynamic datasets, we sample the models for every frame, instead of sampling once and storing the resulting images in a bu_er. At the same time, our parallelization allows each view to use any of the generated samples, avoiding redundant work. The e_cieny of the solution was inspected through mathematical models and validated by measurements of speedup and e_ciency. We concluded that the proposed solution is scalable and can support rendering at interactive rates.

Advisors/Committee Members: Dorgival Olavo Guedes Neto, Dorgival Olavo Guedes Neto, Joao Luiz Elias Campos, Marcelo Walter.

▼ Dispositivos para aquisição e processamento de imagens podem ser encontrados em sistemas complexos de monitoração de segurança ou simples aparelhos celulares. Em certas aplicações, o tempo necessário para processar uma imagem não é tão importante quanto a qualidade das imagens processadas (por exemplo, em imagens médicas), mas em alguns casos a qualidade da imagem pode ser sacrificada em favor do tempo. Essa tese se foca nesse último caso, e propõe duas metodologias eficientes para o realce de contraste de imagens. Os métodos propostos são baseados em equalização de histograma (EH), e focam em imagens em tons de cinza e em imagens coloridas. Os métodos baseados em EH atualmente utilizados para processar imagens em tons de cinza tendem a mudar o brilho médio da imagem para o tom médio do intervalo de tons de cinza. Essa mudança não é desejavél em aplicações que visam melhorar o contraste em produtos eletrônicos utilizados pelo consumidor, onde preservar o brilho da imagem original é necessário para evitar o aparecimento de artefatos não exitentes na imagem de saída.Para corrigir esse problema, métodos de bi-equalização de histogramas para preservação do brilho e contraste de imagens foram propostos.Embora esses métodos preservem o brilho da imagem original na imagem processada com um realce significante do contraste, eles podem produzir imagens que não parecem naturais.Esse novo problema foi resolvido por uma nova técnica chamada de Multi-Equalização de histogramas, que decompõe a imagem original em várias sub-imagens, e aplica o método de EH clássico em cada uma delas. Essa metodologia realiza um realce de contraste menos intenso, de forma que a imagem processada parece mais natural . Essa tese propõe duas novas funções de discrepância para decomposição de imagens, originando dois novos métodos de Multi-EH. Além disso, uma função de custo é utilizada para determinar em quantas sub-imagens a imagem original será dividida. Através da comparação objetiva e quantitative usando uma medida de constrate, os experimentos mostraram que os métodos propostos são melhores que outros EH estudados, uma vez que eles preservam o brilho e produzem imagens com uma aparência mais natural. Em relação aos métodos para realce de contraste em imagens coloridas, essa tese propõe um método genérico e eficiente de EH baseado no espaço de cores RGB que preserva o tom (a matiz), e implementa duas instâncias desse método genérico. A primeira instância utiliza os histogramas 1D R-red, G-green e B-blue para estimar um histograma 3D RGB, que é então equalizado. A segunda instância, por sua vez, utiliza os histogramas 2D RG, RB, e GB. A EH é executada utilizando transformadas de deslocamento que preservam a tonalidade da cor, evitando o aparecimento de cores não reais. Os métodos propostos tem complexidade linear no espaço e no tempo em relação ao tamanho da imagem, e não usam nenhuma conversão de um espaço de cores para outro. As imagens produzidas foram avaliadas objetivamente, comparando os métodos propostos com outros estudados. A avaliação… Advisors/Committee Members: Laurent Najman, Arnaldo de Albuquerque Araujo, Laurent Najman, Alexei Manso Correa Machado, Jacques Facon, Ricardo da Silva Torres, Arnaldo de Albuquerque Araujo.

▼ 

São muitas as aplicações para um sistema de captura de movimento. Sistemas que registrem o movimento humano podem ser empregados em diversas áreas, como medicina, esportes, segurança e entretenimento. Embora a utilidade e os benefícios proporcionados por esses sistemas seja grande, seu uso, principalmente no Brasil, é pouco difundido. Este trabalho se integra a um esforço maior para a criação do OpenMoCap, um software brasileiro e de código aberto para a captura de movimento, utilizando câmeras e marcadores passivos. Neste trabalho, três métodos de rastreamento são empregados na tarefa de perseguir marcadores passivos para a captura óptica de movimento. Os métodos avaliados e comparados são: o filtro de Kalman, o filtro Alfa-Beta e o algoritmo CONDENSATION. Para avaliar o desempenho dos métodos foram empregados testes de robustez da perseguição e medição do custo computacional. Considerando o desempenho geral, o filtro de Kalman foi escolhido para ser empregado no sistema de captura.

There are many applications for a motion capture system. Systems that record human motion can be employed in several fields, such as medicine, sports, security and entertainment. Nevertheless the usefulness and benefits provided by these systems are many, its use is restrictedly disseminated, mainly in Brazil. This work is part of a larger effort to create the it{OpenMoCap}, a Brazilian and open source software for motion capture, which uses cameras and passive markers. In this work, three tracking methods are used in the task of tracking passive markers for optical motion capture. The methods evaluated and compared are: the Kalman filter, the Alpha-Beta filter and the CONDENSATION algorithm. To evaluate the performance of the methods the robustness of the tracking was tested and the computational cost measured. Considering the overall performance, the Kalman filter was chosen to be employed in the capture system.

Advisors/Committee Members: Arnaldo de Albuquerque Araujo, Arnaldo de Albuquerque Araujo, Alexei Manso Correa Machado, Luiz Chaimowicz.

▼ 

Wireless Sensor Network (WSN) based applications are usually event driven. An event by itself can be defined as being composed of a causal criterion and a spatiotemporal criterion. The first criterion specifies the type of event, while the second specifies the location in time and space where the event occurred. A sensor node is able to identify the first criterion easily by using its own sensing devices. The spatiotemporal criterion, on the other hand, can only be identified when the sensor nodes of a WSN have synchronized clocks and are able to determine their physical location. Time and space information is also required by a number of algorithms and protocols in WSNs such as information fusion, object tracking, energy maps, and density control. Thus, synchronization and positioning for WSN-based applications are challenging problems that need to be addressed. In this thesis, we identify that synchronization and positioning in WSNs are actually two parts of the same problem, i.e., locating the nodes in a network in time-space. Neither location without time nor time without location is complete information in these networks. The similarities between the localization and synchronization problems also suggest that they can and should be addressed as a single problem. From our perspective, time can be seen as another dimension of space. As a consequence, we need to solve a 4D positioning problem. This approach allows us to save network resources and solve both problems more efficiently. We propose three different solutions for the localization in time and space problem that are suitable for different scenarios in WSNs. These proposed solutions are called the Synapse, Lightness, and Mobilis algorithms. Our proposed algorithms not only take advantage of the additional hardware resources required by the positioning mechanism in order to improve the performance and scalability of synchronization, but also benefit from the additional communication required by the synchronization mechanism to decrease positioning errors. We also present an extensive set of experiments to evaluate the performance of our algorithms. Our results indicate that our proposed schemes are suitable for implementation in WSNs and also highlight the advantages of solving both localization and synchronization problems with a unified algorithm.

Redes de Sensores Sem Fio (RSSF) são redes basicamente guiadas por eventos. Um evento pode ser definido como sendo composto por um critério causal e um critério espaço-temporal. No primeiro caso, o tipo do evento é identificado, enquanto que no segundo, a localização no tempo e no espaço em que o evento ocorreu é especificada. Um nó sensor é capaz de identificar o primeiro critério (tipo do evento) facilmente usando os seus diversos sensores. O critério espaço-temporal, entretanto, só pode ser identificado quando os nós sensores de uma RSSF possuem relógios sincronizados e são capazes de determinar suas posições físicas. Informações de tempo e espaço são necessárias também para uma série de algoritmos e…

Advisors/Committee Members: Alejandro César Freire Orgambide, Geraldo Robson Mateus, Antonio Alfredo Ferreira Loureiro, Raquel Aparecida de Freitas Mini, Wagner Meira Junior, Eduardo Freire Nakamura, Eduardo Freire Nakamura, Antonio Alfredo Ferreira Loureiro.

▼ 

This paper describes an architecture of hardware and software that helps the development of applications of Computer Vision and Digital Image Processing in Embedded Systems, specically Smart Cameras. Smart Cameras are cameras that, in addition to image capturing, is capable of extracting application-specic information. Embedded systems are systems composed of hardware and software designed to perform specic tasks combining processing and input/output devices needed for applications. Computer Vision can be dened as the ability to rebuild, automatically, the mathematical model from one or more images of a given scene. The mathematical model, or computer graphics, is capable of providing information about the scene previously registered only in images. This is the reverse process to Computer Graphics where the computing system, from a mathematical model, generates digital images. The area of digital image processing is thus the basis for the development of any application of Computer Vision, because it is responsible for the manipulation of images that are the rst input of an application of Computer Vision. The restriction of resources inherent in the systems combined with the complexity of Embedded Computer Vision hinders the construction of applications embedded in these two contexts. The solution, proposed in this paper, is to build an architecture that helps the developer, leaving aside details of Embedded System and Computer Vision algorithms.

Este trabalho descreve uma arquitetura de hardware e software que auxilia no desenvolvimento de aplicações de Visão Computacional e Processamento Digital de Imagens em Sistemas Embutidos, especificamente Smart Cameras. Smart Cameras são câmeras que, além de capturar imagens, é capaz de extrair informações específicas para a aplicação. Sistemas Embutidos são sistemas compostos de hardware e software projetados para realizar tarefas específicas combinando processamento e dispositivos de entrada e saída necessários às aplicações. Visão Computacional pode ser definida como a capacidade de reconstruir, automaticamente, o modelo matemático a partir de uma imagem ou mais imagens de uma dada cena. O modelo matemático ou de computação gráfica é capaz de prover informações sobre a cena anteriormente registrada apenas em magens. Este é então o processo inverso à Computação Gráfica em que o sistema de computação, a partir de um modelo matemático, gera imagens digitais. A área de Processamento Digital de Imagens é, desta forma, a base para o desenvolvimento de qualquer aplicação de Visão Computacional, pois ela é responsável pela manipulação de imagens, que são o primeiro insumo de uma aplicação de Visão Computacional. A restrição de recursos inerentes aos Sistemas Embutidos aliada à complexidade de Visão Computacional dificulta a construção de aplicações inseridas nestes dois contextos. A solução, proposta neste trabalho, é construir uma arquitetura que auxilia o desenvolvedor, abstraindo detalhes do Sistema Embutido e dos algoritmos de Visão Computacional.

Advisors/Committee Members: Antonio Otavio Fernandes, Antonio Otavio Fernandes, Luiz Fernando Etrusco Moreira, Arnaldo de Albuquerque Araujo, Claudionor Jose Nunes Coelho Junior.

▼ 

Nas Redes de Sensores Sem Fio os nós possuem severas restrições de energia devido ao fato de possuírem uma bateria pequena e de estarem em locais de difícil acesso para o ser humano. Por isso, essas redes necessitam de protocolos que sejam eficientes no consumo de energia. Diferente das redes tradicionais que são projetadas para acomodar uma grande variedade de aplicações, as RSSFs normalmente são projetadas considerando aplicações bem específicas. Tendo em vista a grande peculiaridade dessas aplicações, podem-se alcançar melhorias significativas de desempenho se o controle e a troca de informações entre duas ou mais camadas forem otimizados de forma que as interações entre as elas sejam mais exploradas. Essa técnica é denominada projeto integrado e tem recebido muita atenção por parte dos pesquisadores da área de RSSFs nos últimos anos. A abordagem integrada de protocolos torna possível uma forte interação entre duas ou mais camadas na pilha de protocolos e possibilita também o compartilhamento de informações em tempo de execução. O objetivo deste trabalho é analisar o desempenho de um projeto integrado de protocolos para viabilizar a adaptação do duty cycle em função do tráfego na rede. Assim, propõe-se o algoritmo para a camada de enlace SMAC-DDC (Sensor-MAC with Dynamic Duty Cycle) que se beneficia das informações advindas da camada de rede para ajustar a duração do duty cycle dos nós sensores com o objetivo de reduzir o consumo de energia e melhorar a coleta dos dados. Resultados de simulações mostram que é possível reduzir a latência e o consumo de energia de uma rede sem comprometer a taxa de entrega de dados ao nó sink.

In Wireless Sensor Networks, the nodes have severe energy constraints due to the fact of having a small battery and being located in places of difficult access for humans. Therefore, these networks need protocols that are efficient regarding energy consumption. Unlike the traditional networks that are designed to accommodate a wide variety of applications, WSNs are usually designed considering very specific applications. Taking into account the great peculiarity of these applications, you can achieve significant improvements in performance if the control and sharing of information among two or more layers are optimized so that the interactions between them are better exploited. This technique is named cross-layer design and has received much attention from researchers in the area of WSNs in recent years. The cross-layer approach enables a strong interaction between two or more layers in the protocols stack and allows the sharing of information at runtime. The objective of this work is to analyze the performance of a cross-layer design to facilitate the adjustment of the duty cycle depending on the network traffic. Thus, it is proposed the algorithm for the link layer SMAC-DDC (Sensor-MAC with Dynamic Duty Cycle) that receives the information from the network layer to adjust the length of the duty cycle of sensor nodes with the objective of reducing the energy consumption and improve data…

Advisors/Committee Members: Raquel Aparecida de Freitas Mini, Antonio Alfredo Ferreira Loureiro, Raquel Aparecida de Freitas Mini, Antonio Alfredo Ferreira Loureiro, Luiz Henrique Andrade Correa, Geraldo Robson Mateus.

▼ 

Nessa dissertação, introduzimos um novo modelo e algoritmo para minimizar o consumo de energia em Redes de Sensores Sem Fio (RSSFs) com sorvedouro móvel. Os problemas de agrupamento e roteamento são tratados de forma integrada, respeitando as restrições de número de saltos e de comprimento máximo da rota do nó sorvedouro. Uma formulação de Programação Inteira é apresentada, cujo objetivo é minimizar o custo das árvores, as quais definem a organização hierárquica dos nós sensores em agrupamentos. Como a energia gasta com comunicação é a principal responsável pelo consumo de energia em RSSFs, o custo das árvores representa a quantidade de energia necessária para transmitir dados em cada enlace de comunicação. A resolução exata do modelo através de um algoritmo de Branch-and-bound (BB) é custosa, computacionalmente falando, para aplicações em RSSFs, já que a organização da rede tem que ser feita de forma rápida para não comprometer seu funcionamento. Dessa forma, apresentamos uma heurística que encontra, em tempo razoável para aplicações em RSSFs, soluções viáveis para o problema proposto. Testes computacionais extensivos foram feitos para avaliar o impacto da heurística proposta, bem como uma versão da mesma para RSSFs com mais de um sorvedouro móvel. Os resultados de simulação não apenas comprovam que a utilização de sorvedouros móveis representa uma grande economia de energia para RSSFs, como também mostram que nossa abordagem leva a melhoras significativas no gasto de energia, tempo de vida operacional e parâmetros de Qualidade de Serviço (QoS) para RSSFs.

In this work, we introduce a new network topology model and algorithms to minimize the energy consumption in Wireless Sensor Networks (WSNs) with mobile sinks. On the one hand, the proposed optimization problem explicitly minimizes the energy consumption rates due to message forwarding. On the other hand, it also attempts to keep message delay rates at low levels by imposing a maximum distance to be traveled by each mobile sink. Inaddition to all that, our approach also differs from most studies in the literature since the clustering and routing problems are dealt jointly. To the best of our knowledge, the Combinatorial Optimization Problem that arises when all these features are considered together has never been studied before. We present a Mixed Integer Programming formulation for the problem based on network flows and various heuristics to quickly find feasible integer solutions. Our computational experiments indicated that the proposed heuristics works pretty well in practice. We also implemented a simulation framework which embeds the proposed heuristics to validate the network topology introduced here. The simulation results show that our approach leads to significant improvements for all Quality of Service parameters in WSN like energy consumption, network lifetime, among others.

Advisors/Committee Members: Geraldo Robson Mateus, Alexandre Salles da Cunha, Alexandre Salles da Cunha, Geraldo Robson Mateus, Jose Marcos Silva Nogueira, Mauricio Cardoso de Souza.

▼ 

O presente trabalho propõe um arcabouço para determinação e segmentação de mudanças em nuvens de pontos 3D de forma eficiente. Inicialmente, é efetuada uma simplificação nesses pontos, gerando uma representação em árvore que busca preservar as características relevantes da nuvem por meio da estimação da variação da superfície. Além disso, é utilizada uma combinação de Modelos de Misturas Gaussianas (GMM) e da métrica de distância Earth Mover s Distance (EMD), por meio de uma técnica gulosa. Ela permite detectar o que é mudança em um dado local, a partir de leituras prévias do sensor, e segmentar as mudanças detectadas. Para recuperação de forma 3D são propostos dois métodos. Primeiramente, um novo método para recuperação de formas básicas é desenvolvido, no espaço das Gaussianas. Esse método é limitado a um conjunto de primitivas geométricas que incluem planos, esferas e cilindros. Esse método é comparado, ao longo do trabalho, com uma abordagem no espaço Euclidiano utilizando Random Sampling Consensus (RANSAC). Uma segunda abordagem utiliza superquádricas, visando dar uma maior expressividade à representação de forma 3D. Este trabalho utiliza uma abordagem multi-escala com o paradigma split-and-merge, que busca ultrapassar mínimos locais da segmentação fornecida pela GMM, bem como dar maior eficiência ao método como um todo. Resultados experimentais utilizando dados simulados e reais foram obtidos para avaliar a eficácia do método de simplificação utilizado, assim como da abordagem de detecção de mudança. O método para recuperação de formas básicas mostrou-se melhor que o método utilizando o espaço Euclidiano, em termos de custo computacional e exatidão, porém, apresenta algumas restrições que são contornadas pelo uso de superquádricas.

This work proposes a framework to efficiently detect and segment changes in 3D point clouds. Initially, we simplify the point cloud which generates a tree representation in order to preserve the relevant characteristics using surface variation as the key constraint. Then, a combined approach using Gaussian Mixture Models (GMM) and the Earth Mover s Distance (EMD) is proposed, together with a greedy technique. It detects what has changed in a given locale from a previous sensor reading and segments the detected novelty. The 3D shape retrieval is achieved using two different approaches. The first approach is a new method that we developed which directly retrieves the detected shape in the Gaussian space. It uses a limited set or geometric primitives including planes, spheres and cylinders. This method is compared with another one that operates in the Euclidean space using Random Sampling Consensus (RANSAC). The second approach uses superquadric models due to their good expressiveness in representing more generalized three dimensional shapes. In order to achieve a good level of efficiency and to overcome the limitations of GMM segmentation, a multi-scale approach using the split-and-merge paradigm was devised and successfully implemented. Experimental results in both real and…

Advisors/Committee Members: Mario Fernando Montenegro Campos, Mario Fernando Montenegro Campos, Jorge Manuel Miranda Dias, Silvia S.c. Botelho, Luiz Chaimowicz.