Repositório RCAAP

Um importante problema na área de reconhecimento de padrões é o reconhecimento de textos manuscritos. O problema de reconhecimento de expressões matemáticas manuscritas é um caso particular, que vem sendo tratado por décadas. Esse problema é considerado desafiador devido à grande quantidade de possíveis tipos de símbolos, às variações intrínsecas da escrita, e ao complexo arranjo bidimensional dos símbolos na expressão. Neste trabalho adotamos o problema de reconhecimento de símbolos matemáticos manuscritos para realizar um estudo empírico sobre o comportamento de classificadores multi-classes. Examinamos métodos básicos de aprendizado para classificação multi-classe, especialmente as abordagens um-contra-todos e todos-contra-todos de decomposição de um problema multi-classe em problemas de classificação binária. Para decompor o problema em subproblemas menores, propomos também uma abordagem que utiliza uma árvore de decisão para dividir hierarquicamente o conjunto de dados, de modo que cada subconjunto resultante corresponda a um problema mais simples de classificação. Esses métodos são examinados usando-se como classificador base os modelos de classificação vizinhos-mais-próximos e máquinas de suporte vetorial (usando a abordagem um-contra-todos para combinar os classificadores binários). Para classificação, os símbolos são representados por um conjunto de características conhecido na literatura por HBF49 e que foi proposto recentemente especificamente para problemas de reconhecimento de símbolos on-line. Experimentos foram realizados para avaliar a acurácia dos classificadores, o desempenho dos classificadores para número crescente de classes, tempos de treinamento e teste, e uso de diferentes sub-conjuntos de características. Este trabalho inclui uma descrição dos fundamentos utilizados, detalhes do pré-processamento e extração de características para representação dos símbolos, e uma exposição e discussão sobre o estudo empírico realizado. Os dados adicionais que foram coletados para os experimentos serão publicamente disponibilizados.

Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura.

Árvore de componentes é uma representação completa de imagens que utiliza componentes conexos dos conjuntos de níveis de uma imagem e a relação de inclusão entre esses componentes. Essas informações possibilitam diversas aplicações em processamento de imagens e visão computacional, e.g. filtros conexos, segmentação, extração de características entre outras. Aplicações que utilizam árvore de componentes geralmente computam atributos que descrevem os componentes conexos representados pelos nós da árvore. Entre esses atributos estão a área, o perímetro e o número de Euler, que podem ser utilizados diretamente ou indiretamente (para o cálculo de outros atributos). Os \"bit-quads\" são padrões de tamanho 2x2 binários que são agrupados em determinados conjuntos e contados em imagens binárias. Embora o uso de \"bit-quads\" resulte em um método rápido para calcular atributos em imagens binárias, o mesmo não ocorre para o cálculo de atributos dos nós de uma árvore de componentes, porque os padrões contados em um nó podem se repetir nos conjuntos de níveis da imagem e serem contados mais de uma vez. A literatura recente propõe uma adaptação dos bit-quads para o cálculo incremental e eficiente do número de buracos na árvore de componentes. Essa adaptação utiliza o fato de cada nó da árvore de componentes representar um único componente conexo e uma das definições do número de Euler para o cálculo do número de buracos. Embora essa adaptação possa calcular o número de Euler, os outros atributos (área e perímetro) não podem ser computados. Neste trabalho é apresentada uma extensão dessa adaptação de bit-quads que permite a contagem de todos os agrupamentos de bit-quads de maneira incremental e eficiente na árvore de componentes. De forma que o método proposto possa calcular todos os atributos que podem ser obtidos pelos bit-quads (além do número de buracos) em imagens binárias na árvore de componentes de maneira incremental.

Planejamento em inteligência artificial é a tarefa de determinar ações que satisfaçam um dado objetivo. Nos problemas de planejamento sob incerteza, as ações podem ter efeitos probabilísticos. Esses problemas são modelados como Processos de Decisão Markovianos (Markov Decision Processes - MDPs), modelos que permitem o cálculo de soluções ótimas considerando o valor esperado de cada ação em cada estado. Contudo, resolver problemas grandes de planejamento probabilístico, i.e., com um grande número de estados e ações, é um enorme desafio. MDPs grandes podem ser reduzidos através da computação de bissimulações estocásticas, i.e., relações de equivalência sobre o conjunto de estados do MDP original. A partir das bissimulações estocásticas, que podem ser exatas ou aproximadas, é possível obter um modelo abstrato reduzido que pode ser mais fácil de resolver do que o MDP original. No entanto, para problemas de alguns domínios, a computação da bissimulação estocástica sobre todo o espaço de estados é inviável. Os algoritmos propostos neste trabalho estendem os algoritmos usados para a computação de bissimulações estocásticas para MDPs de forma que elas sejam computadas sobre o conjunto de estados alcançáveis a partir de um dado estado inicial, que pode ser muito menor do que o conjunto de estados completo. Os resultados experimentais mostram que é possível resolver problemas grandes de planejamento probabilístico com desempenho superior às técnicas conhecidas de bissimulação estocástica.

O principal critério de otimização utilizado em Processos de Decisão Markovianos (mdps) é minimizar o custo acumulado esperado. Embora esse critério de otimização seja útil, em algumas aplicações, o custo gerado por algumas execuções pode exceder um limite aceitável. Para lidar com esse problema foram propostos os Processos de Decisão Markovianos Sensíveis ao Risco (rs-mdps) cujo critério de otimização é maximizar a probabilidade do custo acumulado não ser maior que um orçamento limite definido pelo usuário, portanto garantindo que execuções custosas de um mdp ocorram com menos probabilidade. Algoritmos para rs-mdps possuem problemas de escalabilidade quando lidam com intervalos de custo amplos, uma vez que operam no espaço aumentado que enumera todos os possíveis orçamentos restantes. Neste trabalho é proposto um novo problema que é encontrar o orçamento mínimo para o qual a probabilidade de que o custo acumulado não exceda esse orçamento converge para um máximo. Para resolver esse problema são propostas duas abordagens: (i) uma melhoria no algoritmo tvi-dp (uma solução previamente proposta para rsmdps) e (ii) o primeiro algoritmo de programação dinâmica simbólica para rs-mdps que explora as independências condicionais da função de transição no espaço de estados aumentado. Os algoritmos propostos eliminam estados inválidos e adicionam uma nova condição de parada. Resultados empíricos mostram que o algoritmo rs-spudd é capaz de resolver problemas até 103 vezes maior que o algoritmo tvi-dp e é até 26.2 vezes mais rápido que tvi-dp (nas instâncias que o algoritmo tvi-dp conseguiu resolver). De fato, é mostrado que o algoritmo rs-spudd é o único que consegue resolver instâncias grandes dos domínios analisados. Outro grande desafio em rs-mdps é lidar com custos contínuos. Para resolver esse problema são definidos os rs-mdps híbridos que incluem variáveis contínuas e discretas, além do orçamento limite definido pelo usuário. É mostrado que o algoritmo de programação dinâmica simbólica (sdp), existente na literatura, pode ser usado para resolver esse tipo de mdps. Esse algoritmo foi empiricamente testado de duas maneiras diferentes: (i) comparado com os demais algoritmos propostos em um domínio em que todos são capazes de resolver e (ii) testado em um domínio que somente ele é capaz de resolver. Os resultados mostram que o algoritmo sdp para rs-mdp híbridos é capaz de resolver domínios com custos contínuos sem a necessidade de enumeração de estados, porém em troca do aumento do custo computacional.

Atualmente, muitas redes com características dinâmicas estão em funcionamento (por exemplo MANETs, DTNs, redes oportunistas, etc). Neste trabalho, estudamos um modelo para estas redes chamado de Grafos Evolutivos, que permite expressar a dinamicidade das conexões entre nós por meio de uma simples extensão da estrutura comum de grafos. Esta modelagem é utilizada no arcabouço proposto por Casteigts et al. para definir algoritmos distribuídos em redes dinâmicas, que utiliza grafos evolutivos para representar a topologia da rede e renomeação de rótulos para expressar a comunicação entre os nós. Utilizamos esta abordagem para estudar o problema da exclusão mútua distribuída em redes dinâmicas e diversos algoritmos propostos para ele, a fim de definir e validar suas condições necessárias e suficientes de conectividade em redes dinâmicas. Além da formalização de algoritmos, o modelo de grafos evolutivos também pode ser utilizado para analisar redes dinâmicas. Rastros de redes dinâmicas reais são amplamente utilizados na literatura para estudos de algoritmos pois estes geram resultados mais realísticos do que redes simuladas com padrões de movimento. A partir dos detalhes de cada conexão entre nós de um destes rastros, é possível construir um grafo evolutivo, do qual se pode extrair dados como jornadas ótimas entre nós, variação da conectividade no tempo, estabilidade, e periodicidade. Com as informações mencionadas, um pesquisador pode observar com maior precisão as características do rastro, o que facilita na escolha da rede mais apropriada para sua necessidade. Além disso, o conhecimento prévio de tais características de uma rede auxilia no estudo do comportamento de algoritmos executados sobre ela e provém uma validação para suposições geralmente feitas pelos pesquisadores. Para fornecer estas informações, desenvolvemos uma ferramenta Web que analisa rastros de redes dinâmicas e agrega os dados em um formato de fácil visualização. Descrevemos, neste trabalho, a implementação e a utilidade de todos os serviços da ferramenta.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles.

Este trabalho apresenta dois classificadores originais para sinais de voz que objetivam auxiliar profissionais da fonoaudiologia no diagnóstico de pessoas com alterações de fala. Comparamos os classificadores propostos com três técnicas conhecidas: Modelos de Markov Escondidos (HMM), bag-of-words e classificador baseado em Earth Mover\'s Distance (EMD). Utilizamos três bases de dados, sendo duas disponibilizadas pelo Departamento de Fisioterapia, Fonoaudiologia e Terapia Ocupacional (FOFITO) da Faculdade de Medicina da Universidade de São Paulo (FMUSP) que contêm gravações de crianças que têm alterações de fala que ocorrem durante o desenvolvimento da fala, e a terceira é a base pública UA-Speech que contém gravações de indíviduos adultos com disartria. O intuito deste trabalho é criar classificadores de fala capazes de distinguir um áudio sem alteração de fala de um áudio com alteração de fala. Além de estudar as técnicas conhecidas citadas anteriormente, propusemos dois classificadores baseados em Coeficientes Mel-Cepstrais (MFCC). O primeiro utiliza uma reformulação da distância DTW entre registros de fala e conjuntos de gravações sem alteração de fala, enquanto o outro combina a informação de curvas de dissimilaridades construídas a partir da comparação do registro de fala a ser classificado com as gravações de referência (sem alterações de fala).

A busca por documentos relevantes ao usuário é um problema que se torna mais custoso conforme as bases de conhecimento crescem em seu ritmo acelerado. Este problema passou a resolvido por sistemas distribuídos, devido a sua escalabilidade e tolerância a falhas. O desenvolvimento de sistemas voltados a estas enormes bases de conhecimento -- e a maior de todas, a Internet -- é uma indústria que movimenta bilhões de dólares por ano no mundo inteiro e criou gigantes. Neste trabalho, são apresentadas e discutidas estruturas de dados e arquiteturas distribuídas que tratem o problema de indexar e buscar grandes coleções de documentos em sistemas distribuídos, alcançando grande desempenho e escalabilidade. Serão também discutidos alguns dos grandes sistemas de busca da atualidade, como o Google e o Apache Solr, além do planejamento de uma grande aplicação com protótipo em desenvolvimento. Um projeto próprio de sistema de busca distribuído foi implementado, baseado no Lucene, com idéias coletadas noutros trabalhos e outras novas. Em nossos experimentos, o sistema distribuído desenvolvido neste trabalho superou o Apache Solr com um vazão 37,4\\% superior e mostrou números muito superiores a soluções não-distribuídas em hardware de custo muito superior ao nosso cluster.

A Plataforma Lattes é, hoje, a principal base de currículos dos pesquisadores brasileiros. Os currículos da Plataforma Lattes armazenam de forma padronizada dados profissionais, acadêmicos, de produções bibliográficas e outras informações dos pesquisadores. Através de uma base de Currículos Lattes, podem ser gerados vários tipos de relatórios consolidados. As ferramentas existentes da Plataforma Lattes não são capazes de detectar alguns problemas que aparecem na geração dos relatórios consolidados como duplicidades de citações ou produções bibliográficas classificadas de maneiras distintas por cada autor, gerando um número total de publicações errado. Esse problema faz com que os relatórios gerados necessitem ser revistos pelos pesquisadores e essas falhas deste processo são a principal inspiração deste projeto. Neste trabalho, utilizamos como fonte de informações currículos da Plataforma Lattes para popular uma ontologia e utilizá-la principalmente como uma base de dados a ser consultada para geração de relatórios. Analisamos todo o processo de extração de informações a partir de arquivos HTML e seu posterior processamento para inserí-las corretamente dentro da ontologia, de acordo com sua semântica. Com a ontologia corretamente populada, mostramos também algumas consultas que podem ser realizadas e fazemos uma análise dos métodos e abordagens utilizadas em todo processo, comentando seus pontos fracos e fortes, visando detalhar todas as dificuldades existentes no processo de população (instanciação) automática de uma ontologia.

Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences.

A comparação de sequências finitas é uma ferramenta que é utilizada para a solução de problemas em várias áreas. Comparamos sequências inferindo quais são as operações de edição de substituição, inserção e remoção de símbolos que transformam uma sequência em uma outra. As matrizes de pontuação são estruturas largamente utilizadas e que definem um custo para cada tipo de operação de edição. Uma matriz de pontuação G é indexada pelos símbolos do alfabeto. A entrada de G na linha A, coluna B mede o custo da operação de edição para substituir o símbolo A pelo símbolo B. As matrizes de pontuação induzem funções que atribuem uma pontuação para um conjunto de operações de edição. Algumas dessas funções para a comparação de duas e de várias sequências são estudadas nesta tese. Quando cada símbolo de cada sequência é editado exatamente uma vez para transformar uma sequência em outra, o conjunto de operações de edição pode ser representado por uma estrutura conhecida por alinhamento. Descrevemos uma estrutura para representar o conjunto de operações de edição que não pode ser representado por um alinhamento convencional e descrevemos um algoritmo para encontrar a pontuação de uma sequência ótima de operações de edição usando um algoritmo conhecido para encontrar a pontuação de um alinhamento convencional ótimo. Considerando três diferentes funções induzidas de pontuação, caracterizamos, para cada uma delas, a classe das matrizes para as quais as funções induzidas de pontuação são métricas nas sequências. Dadas duas matrizes de pontuação G e G\', dizemos que elas são equivalentes para uma dada função que é induzida por uma matriz de pontuação e que avalia a qualidade de um alinhamento se, para quaisquer dois alinhamentos A e B, vale o seguinte: o alinhamento A é ``melhor\'\' do que o alinhamento B considerando a matriz G se e somente se A é ``melhor\'\' do que o alinhamento B considerando a matriz G\'. Neste trabalho, determinamos condições necessárias e suficientes para que duas matrizes de pontuação sejam equivalentes. Finalmente, definimos três novos critérios para pontuar alinhamentos de várias sequências. Todos os critérios consideram o comprimento do alinhamento além das operações de edição por ele representadas. Para cada um dos critérios definidos,propomos um algoritmo e o problema de decisão correspondente mostramos ser NP-completo.

Image segmentation refers to the process of partitioning an image into meaningful regions of interest (objects) by assigning distinct labels to their composing pixels. Images are usually composed of multiple objects with distinctive features, thus requiring distinct high-level priors for their appropriate modeling. In order to obtain a good segmentation result, the segmentation method must attend all the individual priors of each object, as well as capture their inclusion/exclusion relations. However, many existing classical approaches do not include any form of structural information together with different high-level priors for each object into a single energy optimization. Consequently, they may be inappropriate in this context. We propose a novel efficient seed-based method for the multiple object segmentation of images based on graphs, named Hierarchical Layered Oriented Image Foresting Transform (HLOIFT). It uses a tree of the relations between the image objects, being each object represented by a node. Each tree node may contain different individual high-level priors and defines a weighted digraph, named as layer. The layer graphs are then integrated into a hierarchical graph, considering the hierarchical relations of inclusion and exclusion. A single energy optimization is performed in the hierarchical layered weighted digraph leading to globally optimal results satisfying all the high-level priors. The experimental evaluations of HLOIFT and its extensions, on medical, natural and synthetic images, indicate promising results comparable to the state-of-the-art methods, but with lower computational complexity. Compared to hierarchical segmentation by the min cut/max-flow algorithm, our approach is less restrictive, leading to globally optimal results in more general scenarios, and has a better running time.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional.

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.