Métodos baseados em grafos consistem em uma poderosa forma de representação e abstração de dados que proporcionam, dentre outras vantagens, representar relações topológicas, visualizar estruturas, representar grupos de dados com formatos distintos, bem como, fornecer medidas alternativas para caracterizar os dados. Esse tipo de abordagem tem sido cada vez mais considerada para solucionar problemas de aprendizado de máquina, principalmente no aprendizado não supervisionado, como agrupamento de dados, e mais recentemente, no aprendizado semissupervisionado. No aprendizado supervisionado, por outro lado, o uso de algoritmos baseados em grafos ainda tem sido pouco explorado na literatura. Este trabalho apresenta um algoritmo não paramétrico baseado em grafos para problemas de classificação com distribuição estacionária, bem como sua extensão para problemas que apresentam distribuição não estacionária. O algoritmo desenvolvido baseia-se em dois conceitos, a saber, 1) em uma estrutura chamada grafo K-associado ótimo, que representa o conjunto de treinamento como um grafo esparso e dividido em componentes; e 2) na medida de pureza de cada componente, que utiliza a estrutura do grafo para determinar o nível de mistura local dos dados em relação às suas classes. O trabalho também considera problemas de classificação que apresentam alteração na distribuição de novos dados. Este problema caracteriza a mudança de conceito e degrada o desempenho do classificador. De modo que, para manter bom desempenho, é necessário que o classificador continue aprendendo durante a fase de aplicação, por exemplo, por meio de aprendizado incremental. Resultados experimentais sugerem que ambas as abordagens apresentam vantagens na classificação de dados em relação aos algoritmos testados / Graph-based methods consist in a powerful form for data representation and abstraction which provides, among others advantages, representing topological relations, visualizing structures, representing groups of data with distinct formats, as well as, supplying alternative measures to characterize data. Such approach has been each time more considered to solve machine learning related problems, mainly concerning unsupervised learning, like clustering, and recently, semi-supervised learning. However, graph-based solutions for supervised learning tasks still remain underexplored in literature. This work presents a non-parametric graph-based algorithm suitable for classification problems with stationary distribution, as well as its extension to cope with problems of non-stationary distributed data. The developed algorithm relies on the following concepts, 1) a graph structure called optimal K-associated graph, which represents the training set as a sparse graph separated into components; and 2) the purity measure for each component, which uses the graph structure to determine local data mixture level in relation to their classes. This work also considers classification problems that exhibit modification on distribution of data flow. This problem qualifies concept drift and worsens any static classifier performance. Hence, in order to maintain accuracy performance, it is necessary for the classifier to keep learning during application phase, for example, by implementing incremental learning. Experimental results, concerning both algorithms, suggest that they had presented advantages over the tested algorithms on data classification tasks

Métodos baseados em grafos consistem em uma poderosa forma de representação e abstração de dados que proporcionam, dentre outras vantagens, representar relações topológicas, visualizar estruturas, representar grupos de dados com formatos distintos, bem como, fornecer medidas alternativas para caracterizar os dados. Esse tipo de abordagem tem sido cada vez mais considerada para solucionar problemas de aprendizado de máquina, principalmente no aprendizado não supervisionado, como agrupamento de dados, e mais recentemente, no aprendizado semissupervisionado. No aprendizado supervisionado, por outro lado, o uso de algoritmos baseados em grafos ainda tem sido pouco explorado na literatura. Este trabalho apresenta um algoritmo não paramétrico baseado em grafos para problemas de classificação com distribuição estacionária, bem como sua extensão para problemas que apresentam distribuição não estacionária. O algoritmo desenvolvido baseia-se em dois conceitos, a saber, 1) em uma estrutura chamada grafo K-associado ótimo, que representa o conjunto de treinamento como um grafo esparso e dividido em componentes; e 2) na medida de pureza de cada componente, que utiliza a estrutura do grafo para determinar o nível de mistura local dos dados em relação às suas classes. O trabalho também considera problemas de classificação que apresentam alteração na distribuição de novos dados. Este problema caracteriza a mudança de conceito e degrada o desempenho do classificador. De modo que, para manter bom desempenho, é necessário que o classificador continue aprendendo durante a fase de aplicação, por exemplo, por meio de aprendizado incremental. Resultados experimentais sugerem que ambas as abordagens apresentam vantagens na classificação de dados em relação aos algoritmos testados / Graph-based methods consist in a powerful form for data representation and abstraction which provides, among others advantages, representing topological relations, visualizing structures, representing groups of data with distinct formats, as well as, supplying alternative measures to characterize data. Such approach has been each time more considered to solve machine learning related problems, mainly concerning unsupervised learning, like clustering, and recently, semi-supervised learning. However, graph-based solutions for supervised learning tasks still remain underexplored in literature. This work presents a non-parametric graph-based algorithm suitable for classification problems with stationary distribution, as well as its extension to cope with problems of non-stationary distributed data. The developed algorithm relies on the following concepts, 1) a graph structure called optimal K-associated graph, which represents the training set as a sparse graph separated into components; and 2) the purity measure for each component, which uses the graph structure to determine local data mixture level in relation to their classes. This work also considers classification problems that exhibit modification on distribution of data flow. This problem qualifies concept drift and worsens any static classifier performance. Hence, in order to maintain accuracy performance, it is necessary for the classifier to keep learning during application phase, for example, by implementing incremental learning. Experimental results, concerning both algorithms, suggest that they had presented advantages over the tested algorithms on data classification tasks

O teste de software é considerado uma atividade importante para a revelação de falhas. Apesar desta vantagem, tem sido pouco explorado no âmbito de aplicações de Realidade Virtual (RV). Dentre as lacunas existentes, a definição e automatização de critérios de teste de software para esse domínio foi identificada, uma vez que esses sistemas possuem características próprias que requerem definição ou adaptação de técnicas de teste, fazendo com que aplicações nesse domínio constituam sistemas de alta complexidade. Diante disso, o objetivo desta tese é apresentar uma abordagem denominada Virtual Reality-Requirements Specification and Testing (VR-ReST) que visa apoiar a especificação de requisitos de aplicações de RV com base na descrição de casos de uso e conceitos do domínio de RV e Grafo de Cena (GC), derivar requisitos de teste e gerar dados de teste a partir dos requisitos especificados. Além disso, é apresentado um apoio ferramental chamado de Virtual Requirements Specification and Testing (ViReST), que permite automatizá-las. A abordagem é composta por três módulos: (i) especificação dos requisitos por meio do auxílio de um modelo denominado Virtual Requirements Specification (ViReS); (ii) mapeamento dos requisitos por meio de uma linguagem semi-formal chamada Behavior Language Requirement Specification (BeLaRS) para garantir uma especificação padronizada; e (iii) geração automática dos requisitos de teste e dos dados de teste. Foi realizado um estudo de caso para avaliar a conformidade e a usabilidade da BeLaRS em auxiliar a especificação de requisitos de uma aplicação de RV. Além disso, também foi realizado um experimento para avaliar a eficácia da abordagem VR-ReST por meio da ferramenta ViReST. Usando teste de mutação neste último experimento, a abordagem VR-ReST alcançou um escore de mutação médio de 15,49% maior que o teste aleatório. Portanto, os resultados mostraram que a abordagem, bem como o apoio ferramental, podem auxiliar o projetista durante a atividade de especificação de requisitos e o testador na geração dos testes para aplicações de RV. / Software testing is considered an important activity towards fault revealing. Despite this advantage, it has been few explored within the scope of Virtual Reality (VR) applications. Among the existing gaps, the definition and automation of software testing criteria for this domain were identified, since these systems have their own characteristics that require definition or adaptation of testing techniques, making applications in this domain constitute highly complex systems. Therefore, a Virtual Reality-Requirements Specification and Testing (VR-ReST) approach is presented to perform the functional test of VR applications using Scene Graph (SG) concepts and a support tool called Virtual Requirements Specification And Testing (ViReST), which allows you to automate them. The approach is composed of three modules: (i) the first consists in specifying the requirements by means of a model called Virtual Requirements Specification (ViReS); (ii) the second involves mapping the requirements through a semi-formal language called Behavior Language Requirement Specification (BeLaRS) to ensure a standardized specification; and (iii) the third is the automatic generation of test requirements and test data. A case study was conducted to evaluate the compliance and usability of BeLaRS in assisting the requirements specification of an RV application. Also, an experiment was also carried out to evaluate the effectiveness of the VR-ReST approach using the ViReST tool. Using mutation testing in this latter experiment, the VR-ResT approach achieved a mean mutation score of 15.49% higher than the random testing. Therefore, the results showed that the approach, as well as tooling support, can assist the designer during the requirement specification activity and the tester in generating the tests for RV applications.

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. / Nesta tese, uma nova abordagem para o rastreamento de múltiplos objetos com o uso de informação estrutural é proposta. Os objetos são rastreados usando uma combinação de filtro de partículas com descrição das imagens por meio de Grafos Relacionais com Atributos (ARGs). O processo é iniciado a partir do aprendizado de um modelo de grafo estrutural probabilístico utilizando imagens anotadas. Os grafos são usados para avaliar o estado atual do rastreamento e corrigi-lo, se necessário. Desta forma, o método proposto é capaz de lidar com situações desafiadoras como movimento abrupto e perda de rastreamento devido à oclusão. A principal contribuição desta tese é a exploração do modelo estrutural aprendido. Por meio dele, a própria informação estrutural da cena é usada para guiar o processo de detecção em caso de perda do objeto. Tal abordagem difere de trabalhos anteriores, que utilizam informação estrutural apenas para avaliar o estado da cena, mas não a consideram para gerar novas hipóteses de rastreamento. A abordagem proposta é bastante flexível e pode ser aplicada em qualquer situação em que seja possível encontrar padrões de relações estruturais entre os objetos. O rastreamento de objetos pode ser utilizado para diversas aplicações práticas, tais como vigilância, análise de atividades ou navegação autônoma. Nesta tese, ele é explorado para rastrear diversos objetos em vídeos de esporte, na qual as regras do jogo criam alguns padrões estruturais entre os objetos. Além de detectar os objetos, os resultados de rastreamento também são usados como entrada para reconhecer a ação que cada jogador está realizando. Esta etapa é executada classificando um segmento da sequência de rastreamento por meio de Modelos Ocultos de Markov (HMMs). A abordagem de rastreamento proposta é testada em diversos vídeos de jogos de tênis de mesa e na base de dados ACASVA, demonstrando a capacidade do método de lidar com situações de oclusão ou cortes de câmera.

Bartsch (BARTSCH, 1993) introduziu uma teoria de índice cohomológico, conhecida como o length, para G-espaços, no qual G é um grupo de Lie compacto. Apresentamos o cálculo do length de G-espaços os quais são esferas de cohomologia e G = (Z2)k, (Zp)k ou (S1)k, k &ge; 1. Como consequências, obtemos um teorema de Borsuk-Ulam neste contexto e damos condições suficientes para a existência de aplicações G-equivariantes entre uma esfera de cohomologia e uma esfera de representação quando G = (Zp)<sup<k. Também, uma versão Bourgin-Yang do teorema de Borsuk-Ulam é apresentada. Como segunda parte desta tese, uma nova definição do grafo de Reeb R( f) de uma função suave f : MR com pontos críticos isolados, como um subcomplexo de M é dada. Para isto, um complexo 1-dimensional &Gamma; (f ) mergulhado em M e equivalente por homotopia a R( f ) é construído. Como consequência, mostramos que para toda função f sobre uma variedade com grupo fundamental finito, o grafo de Reeb de f é uma árvore. Se &pi;1(M) é um grupo abeliano, ou mais geralmente, um grupo amenable1, então R( f ) conterá no máximo um laço. Finalmente, é provado que o número de laços do grafo de Reeb de toda função sobre uma superfície Mg é estimado superiormente por g, o genus de Mg. Os resultados desta segunda parte estão publicados em (KALUBA; MARZANTOWICZ; SILVA, 2015). / Bartsch (BARTSCH, 1993) introduced a numerical cohomological index theory, known as the length, for G-spaces, where G is a compact Lie group. We present the length of G-spaces which are cohomology spheres and G = (Z2)k, (Zp)k or (S1)k, k &ge; 1. As consequences, we obtain a Borsuk-Ulam theorem in this context and we give a sucient condition for the existence of G-maps between a cohomological sphere and a representation sphere when G = (Zp)k. Also, a Bourgin-Yang version of the Borsuk-Ulam theorem is presented. As a second part of this thesis, a new definition of the Reeb graph R( f ) of a smooth function f : M &rarr; R with isolated critical points as a subcomplex of M is given. For that, a 1-dimensional complex &Gamma; ( f ) embedded into M and homotopy equivalent to R( f ) is constructed. As consequence it is shown that for every function f on a manifold with finite fundamental group, the Reeb graph of f is a tree. If &pi; 1 (M) is an abelian group, or more generally, an amenable group2, then R( f ) contais at most one loop. Finally, it is proved that the number of loops of the Reeb graph of every function on a surface Mg is estimated from above by g, the genus of Mg. The results of this second part is published in (KALUBA; MARZANTOWICZ; SILVA, 2015).

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.

Nesta tese apresentamos uma metodologia de mapeamento capaz de gerar representações em termos de grafos para sistemas biológicos de conectividade complexa. Tais sistemas são inicialmente armazenados na forma de imagens digitais e em seguida submetidos a um pré-processamento com objetivo de padronizar as imagens. As imagens pré-processadas são então utilizadas para gerar modelos tridimensionais dos sistemas de interesse. Um algoritmo de propagação de rótulos é utilizado para extrair os esqueletos dos modelos volumétricos e estes esqueletos são por fim, representados por um grafo, composto por vértices e arestas. Os vértices e arestas desse grafo armazenam propriedades do sistema original, como posição, comprimento e diâmetro, bem como as características topológicas de tais sistemas. Finalmente, os grafos resultantes são estudados através da teoria das redes complexas, dentro de um contexto específico para cada sistema. Nossos procedimentos foram aplicados com sucesso a diferentes sistemas biológicos, como artérias caríotidas, árvores arteriais, estruturas mitocondriais e poros em amostras de solo. / In the present work, we developed a mapping methodology able to build a graph representation for biological branched systems. Initially, such systems are stored as digital images and then they undergo a pre-processing in order to standardize the images. The pre-processed imagens are used to build tridimensional models of the interested systems. A label-propagation algorithm is used to extract the skeleton from the volumetric models and these skeletons are then represented by a graph, composed by nodes and edges. The nodes and edges of these graphs store properties of the original system, such as spatial position, lengths and diameter, as well as the topological features of such systems. Finally, the graphs are studied by using the complex networks theory within a specific context for each system. Our procedures were apllied sucefully to different biological systems, such as carotid artery, arterial trees, mitocondrial structure and pores in soil samples.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2015-12-04T22:45:01Z No. of bitstreams: 1 DanielGomesDeAlmeidaFilho_DISSERT.pdf: 6566932 bytes, checksum: b4e06881e4c037be6166917b5467a5e3 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2015-12-10T19:24:08Z (GMT) No. of bitstreams: 1 DanielGomesDeAlmeidaFilho_DISSERT.pdf: 6566932 bytes, checksum: b4e06881e4c037be6166917b5467a5e3 (MD5) / Made available in DSpace on 2015-12-10T19:24:08Z (GMT). No. of bitstreams: 1 DanielGomesDeAlmeidaFilho_DISSERT.pdf: 6566932 bytes, checksum: b4e06881e4c037be6166917b5467a5e3 (MD5) Previous issue date: 2014-07-22 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico - CNPq / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / Hebb prop?s que sinapses entre neur?nios que disparam de forma s?ncrona s?o fortalecidas formando assembleias de c?lulas e sequ?ncias de fase. A primeira, numa escala menor, ? um conjunto de c?lulas sincronizadas, que funcionam de forma transit?ria como um sistema fechado de processamento; a ?ltima, numa escala maior, corresponde ? ativa??o sequencial de assembleias de c?lulas neuronais capazes de representar percep??es e comportamentos. Atualmente, o registro de grandes popula??es neuronais permite a detec??o simult?nea de diversas assembleias neuronais. No ?mbito da teoria de Hebb, o pr?ximo passo l?gico ? a an?lise das sequ?ncias de fase. Neste trabalho investigamos seq??ncias de fase como padr?es de ativa??es consecutivas de assembleias, analisando a rela??o entre comportamento animal e atributos de grafos de assembleias. Foram estudados trens de disparo neuronal registrados no hipocampo e neoc?rtex de 5 ratos adultos, antes, durante e depois da explora??o de novos objetos (per?odos experimentais). Para definir um grafo de assembleia, cada assembleia correspondeu a um n?, e cada aresta correspondeu ? sequ?ncia temporal de ativa??o de n?s consecutivos. A soma da ativa??o de todas as assembleias foi proporcional ? taxa de disparo, mas a atividade de assembleias individuais n?o. O repert?rio de assembleias permaneceu est?vel ao longo dos per?odos experimentais, indicando que a experi?ncia com novos objetos n?o criou novas assembleias no rato adulto. Os atributos de grafos das assembleia, por outro lado, variaram significativamente entre os estados comportamentais e per?odos experimentais e foram distintos o suficiente para permitir a classifica??o autom?tica dos per?odos experimentais (classificador Naive Bayes; AUROCsm?ximas variaram entre 0,55 a 0,99) e estados comportamentais (vig?lia, sono de ondas lentas e sono de movimento r?pido dos olhos; AUROCs m?ximas variaram entre 0,64 e 0,98). Nossos achados refor?am a teoria Hebbiana de que as assembleias neuronais correspondem a estruturas primitivas de representa??o, quase inalteradas na maturidade, enquanto as seq??ncias de fase s?o inst?veis entre os estados comportamentais e mudam ap?s novas experi?ncias. Os resultados s?o compat?veis com um papel das sequ?ncias de fase no comportamento e cogni??o. / Hebb proposed that synapses between neurons that fire synchronously are strengthened, forming cell assemblies and phase sequences. The former, on a shorter scale, are ensembles of synchronized cells that function transiently as a closed processing system; the latter, on a larger scale, correspond to the sequential activation of cell assemblies able to represent percepts and behaviors. Nowadays, the recording of large neuronal populations allows for the detection of multiple cell assemblies. Within Hebb?s theory, the next logical step is the analysis of phase sequences. Here we detected phase sequences as consecutive assembly activation patterns, and then analyzed their graph attributes in relation to behavior. We investigated action potentials recorded from the adult rat hippocampus and neocortex before, during and after novel object exploration (experimental periods). Within assembly graphs, each assembly corresponded to a node, and each edge corresponded to the temporal sequence of consecutive node activations. The sum of all assembly activations was proportional to firing rates, but the activity of individual assemblies was not. Assembly repertoire was stable across experimental periods, suggesting that novel experience does not create new assemblies in the adult rat. Assembly graph attributes, on the other hand, varied significantly across behavioral states and experimental periods, and were separable enough to correctly classify experimental periods (Na?ve Bayes classifier; maximum AUROCs ranging from 0.55 to 0.99) and behavioral states (waking, slow wave sleep, and rapid eye movement sleep; maximum AUROCs ranging from 0.64 to 0.98). Our findings agree with Hebb?s view that neuronal assemblies correspond to primitive building blocks of representation, nearly unchanged in 10 the adult, while phase sequences are labile across behavioral states and change after novel experience. The results are compatible with a role for phase sequences in behavior and cognition

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-04-02T12:19:53Z No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-04-04T12:11:32Z (GMT) No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Made available in DSpace on 2018-04-04T12:11:32Z (GMT). No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) Previous issue date: 2018-02-23 / A World Wide Web ? uma cole??o de informa??es sempre crescente. Esta informa??o ? distribu?da entre documentos diferentes, disponibilizados atrav?s do HTTP. Mesmo que essa informa??o seja acess?vel aos usu?rios na forma de artigos de not?cias, transmiss?es de ?udio, imagens e v?deos, os agentes de software geralmente n?o podem classific?-la. A falta de informa??es sem?nticas sobre esses documentos em um formato leg?vel por m?quina geralmente faz com que a an?lise seja imprecisa. Um n?mero significativo de entidades adotaram Linked Data como uma forma de adicionar informa??es sem?nticas aos seus dados, e n?o apenas public?-lo na Web. O resultado ? uma cole??o global de dados, chamada Web of Data, que forma um grafo global, composto por declara??es no formato RDF [22] de diversas fontes, cobrindo todos os tipos de t?picos. Para encontrar informa??es espec?ficas nesses grafos, as consultas s?o realizadas come?ando em um sujeito e analisando seus predicados nas instru??es RDF. Esses predicados s?o as conex?es entre o sujeito e o objeto, e um conjunto de trilhas forma um caminho de informa??o. O uso de HTTP como mecanismo padr?o de acesso a dados e RDF como modelo de dados padr?o simplifica o acesso a dados, o que nos motiva a pesquisar alternativas na forma como esses dados s?o buscados. Uma vez que a maioria das linguagens de consulta de banco de dados de grafo est?o na classe de Linguagens Regulares, n?s propomos seguir um caminho diferente e tentar usar uma classe de gram?tica menos restritiva, chamada Gram?tica Livre de Contexto Determin?stica, para aumentar a expressividade das consultas no banco de dados em grafo. Mais especificamente, aplicando o m?todo de an?lise LR(1) para encontrar caminhos em um banco de dados de grafo RDF. O principal objetivo deste trabalho ? prover meios para se permitir a utiliza??o de t?cnicas de reconhecimento de gram?ticas livres de contexto LR(1) para fazer consultas por caminhos formados pelas etiquetas das arestas em um banco de dados RDF. Fornecendo, como um resultado, uma ferramenta que se permita atingir melhor expressividade, efici?ncia e escalabilidade nestas consultas do que o que existe atualmente. Para atingir este objetivo, n?s implementamos um algoritmo baseado nas t?cnicas de reconhecimento LR(1), usando o GSS [30] ao inv?s de uma pilha, e permitimos ao usu?rio fazer consultas com uma gram?tica livre de contexto (LR1). Tamb?m analisamos a complexidade do nosso algoritmo e executamos alguns experimentos, comparando nossa solu??o com as outras propostas na literatura, mostrando que a nossa pode ter melhor desempenho em alguns cen?rios. / The World Wide Web is an always increasing collection of information. This information is spread among different documents, which are made available by using the HTTP. Even though this information is accessible to users in the form of news articles, audio broadcasts, images and videos, software agents often cannot classify it. The lack of semantic information about these documents in a machine-readable format usually makes the analysis inaccurate. A significant number of entities have adopted Linked Data as a way to add semantic information to their data, not just publishing it on the Web. The result is a global data collection, called the Web of Data, which forms a global graph, consisting of RDF [22] statements from numerous sources, covering all sorts of topics. To find specific information in this graph, queries are performed starting at a subject and analyzing their predicates in the RDF statements. These predicates are the connections between the subject and object, and a set of traces forms an information path. The use of HTTP as a standardized data access mechanism and RDF as a standard data model simplifies the data access, but accessing heterogeneous data on distinct locations may have an increased time complexity and current query languages have a reduced query expressiveness, which motivates us to research alternatives in how this data is queried. This reduced expressiveness happens because most query languages belong to the class of Regular Languages. The main goal of this work is to use LR(1) context-free grammar processing techniques to search for context-free paths over RDF graph databases, providing, as result, a tool which allows better expressiveness, efficiency and scalability in such queries than what is proposed today. To achieve that, we implemented an algorithm based on the LR(1) parsing technique that uses the GSS [30] structure instead of a stack, and give means for the user to input queries with an LR(1) context-free grammar. Also, we analyze our algorithm?s complexity and make some experiments, comparing our solution to other proposals present in the literature and show that ours can have better performance in given scenarios.

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. / Nesta tese, uma nova abordagem para o rastreamento de múltiplos objetos com o uso de informação estrutural é proposta. Os objetos são rastreados usando uma combinação de filtro de partículas com descrição das imagens por meio de Grafos Relacionais com Atributos (ARGs). O processo é iniciado a partir do aprendizado de um modelo de grafo estrutural probabilístico utilizando imagens anotadas. Os grafos são usados para avaliar o estado atual do rastreamento e corrigi-lo, se necessário. Desta forma, o método proposto é capaz de lidar com situações desafiadoras como movimento abrupto e perda de rastreamento devido à oclusão. A principal contribuição desta tese é a exploração do modelo estrutural aprendido. Por meio dele, a própria informação estrutural da cena é usada para guiar o processo de detecção em caso de perda do objeto. Tal abordagem difere de trabalhos anteriores, que utilizam informação estrutural apenas para avaliar o estado da cena, mas não a consideram para gerar novas hipóteses de rastreamento. A abordagem proposta é bastante flexível e pode ser aplicada em qualquer situação em que seja possível encontrar padrões de relações estruturais entre os objetos. O rastreamento de objetos pode ser utilizado para diversas aplicações práticas, tais como vigilância, análise de atividades ou navegação autônoma. Nesta tese, ele é explorado para rastrear diversos objetos em vídeos de esporte, na qual as regras do jogo criam alguns padrões estruturais entre os objetos. Além de detectar os objetos, os resultados de rastreamento também são usados como entrada para reconhecer a ação que cada jogador está realizando. Esta etapa é executada classificando um segmento da sequência de rastreamento por meio de Modelos Ocultos de Markov (HMMs). A abordagem de rastreamento proposta é testada em diversos vídeos de jogos de tênis de mesa e na base de dados ACASVA, demonstrando a capacidade do método de lidar com situações de oclusão ou cortes de câmera.