RCAAP Repository

In this thesis we propose a novel approach for tracking multiple objects using structural information. The objects are tracked by combining particle filter and frame description with Attributed Relational Graphs (ARGs). We start by learning a structural probabilistic model graph from annotated images. The graphs are then used to evaluate the current tracking state and to correct it, if necessary. By doing so, the proposed method is able to deal with challenging situations such as abrupt motion and tracking loss due to occlusion. The main contribution of this thesis is the exploration of the learned probabilistic structural model. By using it, the structural information of the scene itself is used to guide the object detection process in case of tracking loss. This approach differs from previous works, that use structural information only to evaluate the scene, but do not consider it to generate new tracking hypotheses. The proposed approach is very flexible and it can be applied to any situation in which it is possible to find structural relation patterns between the objects. Object tracking may be used in many practical applications, such as surveillance, activity analysis or autonomous navigation. In this thesis, we explore it to track multiple objects in sports videos, where the rules of the game create some structural patterns between the objects. Besides detecting the objects, the tracking results are also used as an input for recognizing the action each player is performing. This step is performed by classifying a segment of the tracking sequence using Hidden Markov Models (HMMs). The proposed tracking method is tested on several videos of table tennis matches and on the ACASVA dataset, showing that the method is able to continue tracking the objects even after occlusion or when there is a camera cut.

A rápida evolução tecnológica tem expandido constantemente as fronteiras das aplicações de diversas áreas na vida das pessoas. A aplicação de sistemas de recomendação é um exemplo que se beneficiou com essa evolução e que hoje é aplicado em muitos contextos novos, como em museus. Diversos estudos se propuseram a gerar um sistema de recomendação para enfrentar a típica dificuldade de sobrecarga de informação, que costuma ser experimentada pelos visitantes desses lugares. Mas esses sistemas, em sua maioria, não exploraram as capacidades tecnológicas hoje disponíveis ou não foram testados em ambientes reais de utilização. Esta pesquisa busca atender essas oportunidades com a concepção de um sistema de recomendação híbrido baseado em informações de contexto e no método de recomendação collaborative filtering. O sistema também é avaliado em ambiente produtivo com usuários reais, em vez de experimentos controlados. O sistema proposto gera rotas personalizadas de visitação com o objetivo de maximizar a satisfação do usuário ao mesmo tempo em que minimiza a distância do percurso da visita. Esta pesquisa realizou uma das maiores avaliações de um sistema de recomendação já divulgadas, contando com a participação de um número expressivo de visitantes reais em um museu de São Paulo. Seu desempenho foi aferido em relação à acurácia e satisfação do usuário. As avaliações foram feitas em duas etapas, sendo que a segunda foi realizada com um sistema com melhorias baseadas nos resultados da primeira etapa. Mesmo com todas as variabilidades naturais de um ambiente produtivo, os resultados indicaram que o sistema obteve altos níveis de acurácia e satisfação do usuário com as recomendações de itens e as rotas propostas. Verificou-se também uma tendência de melhora na acurácia das recomendações, tanto da primeira para a segunda etapa, quanto com o aumento da base de dados gerados pelos usuários.

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros.

Recentemente surgiram dispositivos sensores de profundidade capazes de capturar textura e geometria de uma cena em tempo real. Com isso, diversas técnicas de Visão Computacional, que antes eram aplicadas apenas a texturas, agora são passíveis de uma reformulação, visando o uso também da geometria. Ao mesmo tempo em que tais algoritmos, tirando vantagem dessa nova tecnologia, podem ser acelerados ou tornarem-se mais robustos, surgem igualmente diversos novos desafios e problemas interessantes a serem enfrentados. Como exemplo desses dispositivos podemos citar o do Projeto Vídeo 4D, do IMPA, e o Kinect (TM), da Microsoft. Esses equipamentos fornecem imagens que vêm sendo chamadas de RGBD, fazendo referência aos três canais de cores e ao canal adicional de profundidade (com a letra \'D\' vindo do termo depth, profundidade em inglês). A pesquisa descrita nesta tese apresenta uma nova abordagem não-supervisionada para a estimação de movimento a partir de vídeos compostos por imagens RGBD. Esse é um passo intermediário necessário para a identificação de componentes rígidos de um objeto articulado. Nosso método faz uso da técnica de casamento inexato (homomorfismo) entre grafos para encontrar grupos de pixels (blocos) que se movem para um mesmo sentido em quadros consecutivos de um vídeo. Com o intuito de escolher o melhor casamento para cada bloco, é minimizada uma função custo que leva em conta distâncias tanto no espaço de cores RGB quanto no XYZ (espaço tridimensional do mundo). A contribuição metodológica consiste justamente na manipulação dos dados de profundidade fornecidos pelos novos dispositivos de captura, de modo que tais dados passem a integrar o vetor de características que representa cada bloco nos grafos a serem casados. Nosso método não usa quadros de referência para inicialização e é aplicável a qualquer vídeo que contenha movimento paramétrico por partes. Para blocos cujas dimensões causem uma relativa diminuição na resolução das imagens, nossa aplicação roda em tempo real. Para validar a metodologia proposta, são apresentados resultados envolvendo diversas classes de objetos com diferentes tipos de movimento, tais como vídeos de pessoas caminhando, os movimento de um braço e um casal de dançarinos de samba de gafieira. Também são apresentados os avanços obtidos na modelagem de um sistema de vídeo 4D orientado a objetos, o qual norteia o desenvolvimento de diversas aplicações a serem desenvolvidas na continuação deste trabalho.

Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação.

A área de sistemas multiagentes é um promissor domínio tecnológico para uso em performances musicais interativas. Em trabalhos recentes, essa tecnologia vem sendo utilizada para resolver problemas musicais de escopo específico e alcance limitado, como a detecção de pulsação, a simulação de instrumentos e o acompanhamento musical automático. Neste trabalho, apresentamos uma taxonomia desses sistemas multiagentes musicais e uma arquitetura e implementação de um arcabouço computacional que generaliza os trabalhos anteriores e aborda problemas usuais como a sincronização em tempo real, a comunicação sonora e a mobilidade espacial dos agentes. Através do arcabouço, um usuário pode desenvolver um sistema multiagente musical focado em suas necessidades musicais, enquanto deixa grande parte dos problemas técnicos a cargo do arcabouço. Para validar o arcabouço, implementamos e discutimos dois estudos de caso que exploram diversos aspectos de um sistema multiagente musical, como a comunicação simbólica, a troca de áudio digital, o uso de trajetórias espaciais, a simulação acústica e conceitos de vida artificial, como códigos genéticos e reprodução, demonstrando a usabilidade do arcabouço em uma grande variedade de aplicações musicais.

Em 2009, N. Heninger e H. Shacham apresentaram um algoritmo de reconstrução que permite recuperar a chave secreta sk do criptossistema RSA básico em tempo polinomial tendo em forma aleatória 27 % dos seus bits. Sabemos que podemos obter uma versão com erros (bits modicados) da chave secreta RSA graças aos ataques cold boot. O algoritmo apresentado por Heninger-Shacham corrige esses erros fazendo uso das relações matemáticas que existe entre as chaves pública e secreta do criptossistema RSA básico. O objetivo deste trabalho é estudar esse algoritmo para implementar e analisar seu análogo para o criptossistema RSA multi-primo. Os resultados obtidos mostram que para reconstruir a chave secreta sk do criptossistema RSA u-primos é preciso ter uma fração de bits corretos maior a 2 - 2^((u+2)/(2u+1)), mostrando assim que a segurança oferecida pelo criptossistema RSA multi-primo (u>/ 3) é maior com relação ao criptossistema RSA básico (u = 2).

Concerns about reducing energy consumption in the sector of Information and Communication Technology has increasingly motivated the transition of traditional services to the clouds. In this context, Network Functions Virtualization (NFV) emerges as a solution to migrate various network functions, from dedicated hardware devices to a virtual environment based on commodity hardware. With this virtualization, in addition to the promise of increasing energy efficiency, it is expected to reduce the financial cost and increase the flexibility and scalability of the networks. In this research, it is proposed the development of algorithms based on three metaheuristics (Standard Hill-Climbing, Simulated Annealing, and Memetic Algorithm) to schedule network functions in cloud data centers, observing not only the capacities and energy consumption of the computers where the functions will be executed but also of the network and switches that connect these computers. Comparing the algorithms proposed in relation to the Best Fit algorithm found in the literature, the one based on Simulated Annealing saved 55.44% of energy consumption in a datacenter with Three-tier topology and the one based on memetic algorithm saved 49.18% of energy consumption in a data center with Fat-Tree topology. To allow the reproduction of all the experiments carried out in this research, the codes developed are publicly available as free software

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo.

Two tasks that software engineers constantly perform are writing code that is easy to evolve and maintain, and detecting poorly written pieces of code. For the former, software engineers commonly rely on well-known software architecture styles, such as Model-View-Controller (MVC). To the latter, they rely on code metrics and code smell detection approaches. However, up to now, these code metrics and code smell approaches do not take into account underlying architectureall classes are assessed as if they were the same. In practice, software developers know that classes differ in terms of responsibilities and implementation, and thus, we expect these classes to present different levels of coupling, cohesion, and complexity. As an example, in an MVC system, Controllers are responsible for the flow between the Model and the View, and Models are responsible for representing the systems business concepts. Thus, in this thesis, we evaluate the impact of architectural roles within a system architecture on code metrics and code smells. We performed an empirical analysis in 120 open source systems, and interviewed and surveyed more than 50 software developers. Our findings show that each architectural role has a different code metric values distribution, which is a likely consequence of their specific responsibilities. Thus, we propose SATT, an approach that provides specific thresholds for architectural roles that are significantly different from others in terms of code smells. We also show that classes that play a specific architectural role contain specific code smells, which developers perceive as problems, and can impact class\' change- and defect-proneness. Based on our findings, we suggest that developers understand the responsibilities of each architectural role in their system architecture, so that code metrics and code smells techniques can provide more accurate feedback.

Composição de serviços é um tópico que tem atraído cada vez mais o interesse por parte de pesquisadores na área de sistemas distribuídos. Além disso, o interesse por ambientes baseados em nuvem tem crescido significativamente conforme o seu uso aumenta e se firma como um importante modelo de negócios. Coreografias são formas de composições de serviços em que não há pontos centrais de falha; a responsabilidade da sua execução é distribuída entre os vários serviços componentes. Devido à natureza distribuída do fluxo de informações e dados de controle, o cumprimento de \\textit{Service Level Agreements} (SLAs) depende estritamente do monitoramento da Qualidade de Serviços (QoS), recursos virtuais da nuvem e mecanismos de reconfiguração dinâmica, capazes de automaticamente adaptar composições a mudanças de estado no sistema. Nesta dissertação, abordamos o estudo do gerenciamento de QoS em coreografias de serviços. Para isso desenvolvemos um sistema de middleware capaz de implantar e gerenciar o QoS de composições. Este teve seu desempenho avaliado utilizando o serviço Amazon EC2. Os resultados da avaliação mostram que com pouco esforço por parte dos desenvolvedores de composições, é possível cumprir o SLA de composições dentro do esperado utilizando escalabilidade horizontal ou vertical provida pelo middleware automaticamente. Adicionalmente, a nossa proposta traz economias em relação ao custo de implantação pois diminui a quantidade de recursos subutilizados.

The motivation that originated this work was the desire to create an invasion team sports simulator capable of applying user defined strategies to guide the behavior of the agents in the simulation. With this objective in mind we created a formal strategy model to describe complex team behavior and developed methods of using that model to calculate collective plans. We defined both the strategy model and the planning methods in a broad manner that can be applied in many different domains. Then we defined a basketball simulation domain and implemented our methodology to develop a simulator. We also present a control system architecture that is compatible with our proposed planner and show how we implemented it to create the basketball simulator. The formal strategy model we developed can be used to represent team behavior, analyze real world events and create simulations. We developed a strategy design tool that allows the end user to create and visualize team strategies for basketball. Finally, we developed a system that interprets the user generated strategies and creates a basketball match simulation of the described behavior. We also proposed a methodology for the development of simulation systems involving multiple intelligent agents. Our recommended control system architecture separates the many layers of control, which simplifies the development process and results in a naturally expansible system. In this thesis we have provided a novel approach to collective behavior simulation utilizing user input as a guide to the strategy planning. Both the theory and methods developed have been tested through the implementation of a basketball simulator and the results were satisfactory. We believe this is a seminal work that will lead to many interesting developments, both in the realm of sports and in broader domains.

As organizações precisam trocar informações de forma simples e eficiente, com custos tão baixos quanto possível. Essas informações às vezes são apresentadas na forma de documentos com formato e conteúdos pré-definidos. Esses documentos podem ser equivalentes ou quase equivalentes, porém bastantes distintos em diferentes organizações. Numa mesma organização, os documentos podem ser diferentes em contextos históricos. O propósito deste trabalho é facilitar a distribuição dos documentos, superando o problema dos formatos com os quais foram criados. O objetivo é possibilitar a interoperabilidade de documentos e atingir a portabilidade simples e confiável de documentos através da reutilização de formatos e conteúdos, em diferentes combinações plausíveis. Propomos, usar ontologias como solução ao problema da falta de interoperabilidade nas implementações de formatos de documentos. Como prova de conceito consideramos a portabilidade entre os formatos padrão ODF(Open Document Format) e (Office Open XML).

Neste trabalho apresentamos um modelo para ambientes inteligentes baseado em organizações de agentes, onde interações entre entidades são associadas a espaços físicos, pessoas carregam dispositivos e se movimentam entre diferentes espaços físicos e cada espaço físico contém definições de interações (comportamentos definidos por normas) próprias do seu contexto. São definidos três componentes deste modelo: (1) modelo conceitual, (2) linguagem de especificação e (3) ambiente de execução. A separação do modelo nestes três componentes traz como principais conseqüências: (1) a ativação de um ambiente inteligente é feita através de um mecanismo de alto nível, (2) a especificação de um ambiente inteligente é independente do domínio de aplicação e (3) as especificações podem ser executadas em mecanismos diferentes de execução.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas.

O reconhecimento de texto manuscrito continua sendo um problema em aberto, objeto de intensa pesquisa na área de aprendizado de máquina. Neste projeto focamos numa categoria específica de problema nesta área, a leitura automática de planilhas de xadrez. Planilhas de xadrez contém anotações de lances de jogos escritos à mão pelos próprios jogadores num formato chamado de notação algébrica. Em comparação com um texto tradicional em linguagem natural, planilhas de xadrez são formulários de formato fixo, seu conteúdo textual é restrito a um vocabulário reduzido e a escrita em geral não é totalmente cursiva. Mesmo assim, elas ainda apresentam uma alta variabilidade de estilos de escrita à mão, tornando a sua leitura um problema suficientemente complexo. O objetivo deste trabalho é o treinamento ponta a ponta de uma rede neural para a leitura destas planilhas, em cenários com uma quantidade limitada de dados. A rede neural deverá receber a imagem de uma planilha e produzir em sua saída a sequência de lances que estão escritos na planilha. Além do reconhecimento da escrita propriamente, a rede deverá aprender a ordem correta de leitura. Por se tratar de um problema para o qual não encontramos trabalhos na literatura da área, o método utilizado consistiu na criação de um conjunto de dados e uma ampla investigação experimental utilizando uma rede neural recorrente com mecanismo de atenção. Identificamos três subtarefas subjacentes ao problema: (1) o aprendizado do modelo de linguagem, relacionado com a previsibilidade dos lances, (2) o alinhamento entre a entrada e a saída, e (3) o reconhecimento da escrita propriamente. Constatamos que essas tarefas possuem distintos graus de dificuldade e que existem alguns fatores que são críticos no aprendizado delas. Mais do que isso, constatamos também que uma combinação adequada desses fatores é fundamental para um treinamento ponta a ponta bem sucedido. Um modelo básico foi avaliado quanto ao reconhecimento dos 16 primeiros lances e alcançou acurácia de 65,78% em termos de lances corretamente reconhecidos.

JamSession foi proposto como uma plataforma para mediar e coordenar, por meio de protocolos de interação baseados em conhecimento, recursos computacionais existentes com o objetivo de compor novos serviços e desenvolver aplicações inovadoras. Entre as principais características da plataforma estão sua base formal e declarativa para permitir análise e verificação formal dos protocolos, alta performance e foco na usabilidade. A plataforma pode ser utilizada, por exemplo, na construção de ambientes inteligentes e no aprimoramento dos serviços de governo eletrônico, onde o JamSession pode atuar mediando a interação entre sistemas oferecidos por órgãos públicos visando a ampliação dos serviços oferecidos. O objetivo deste trabalho é o desenvolvimento da plataforma JamSession e sua aplicação em problemas concretos de integração e coordenação. Entre as aplicações consideradas para validar a plataforma desenvolvida estão a integração de workflows interorganizacionais e a demonstração do uso da plataforma na construção de ambientes virtuais interativos.

Esta dissertação tem por objetivo apresentar as licenças de software livre mais importantes, sob a luz dos seus principais aspectos jurídicos e da inter-compatibilidade, de forma a auxiliar pessoas envolvidas no desenvolvimento de software a compreender as implicações destas licenças ao fazer uso delas em seus projetos. A dissertação contextualiza as licenças, tanto no tocante à legislação brasileira, quanto no que diz respeito às restrições de licenciamento, de forma a viabilizar a análise de compatibilidade que se segue. Casos de projetos proeminentes de software livre cujo desenvolvimento foi afetado pelas implicações mencionadas ilustram a investigação, que é complementada por uma análise de ferramentas e metodologias existentes que auxiliam na gestão dos aspectos de licenciamento.

Sistemas criptográficos como o RSA e o Diffie-Hellman sobre Curvas Elípticas (DHCE) têm fundamento em problemas computacionais considerados difíceis, por exemplo, o problema do logaritmo (PLD) e o problema da fatoração de inteiros (PFI). Diversos trabalhos têm relacionado a segurança desses sistemas com os problemas subjacentes. Também é investigada a segurança do LSB (bit menos significativo) da chave secreta no DHCE (no RSA é o LSB da mensagem) com relação à segurança de toda a chave. Nesses trabalhos são apresentados algoritmos que conseguem inverter os sistemas criptográficos citados fazendo uso de oráculos que predizem o LSB. Nesta dissertação, fazemos a implementação de dois desses algoritmos. Identificamos parâmetros críticos e mudamos a amostragem do formato original. Com essa mudança na amostragem conseguimos uma melhora significativa nos tempos de execução. Um dos algoritmos (ACGS), para valores práticos do RSA, era mais lento que a solução para o PFI, com nosso resultado passou a ser mais veloz. Ainda, mostramos como provas teóricas podem não definir de maneira precisa o tempo de execução de um algoritmo.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado.