Orientador: Ricardo da Silva Torres

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Atualmente, há uma alta demanda por soluções que possibilitem a implementação de serviços de recuperação e classificação eficazes e eficientes para grande volumes de dados. Nesse contexto, diversos estudos têm investigado o uso de novas técnicas baseadas na comparação de estruturas locais...

Resumo: Atualmente, há uma alta demanda por soluções que possibilitem a implementação de serviços de recuperação e classificação eficazes e eficientes para grande volumes de dados. Nesse contexto, diversos estudos têm investigado o uso de novas técnicas baseadas na comparação de estruturas locais presentes em objetos na implementação de serviços de classificação e recuperação. Estruturas locais podem ser caracterizadas por diferentes tipos de relacionamentos (e.g., distribuição espacial) entre primitivas de objetos, sendo geralmente exploradas em problemas de reconhecimento de padrões. Nessa dissertação de mestrado, propomos a Sacola de Grafos, uma nova abordagem baseada no modelo de Sacola de Palavras Visuais, que utiliza grafos para codificar estruturas locais de um objeto. Uma definição formal do modelo proposto é apresentada, assim como conceitos e regras que tornam este modelo flexível e ajustável a diferentes aplicações. Na abordagem proposta, um objeto é representado por um grafo que modela as estruturas locais existentes. Usando um dicionário pré-definido, o objeto pode ser descrito por uma representação vetorial com a frequência de ocorrência de padrões locais no grafo correspondente. Neste trabalho, apresentamos dois métodos baseados no modelo proposto, a Sacola de Grafos Triviais e a Sacola de Grafos Visuais, que constroem representações vetoriais para imagens e grafos, respectivamente. Ambos os métodos são validados em tarefas de classificação. Nós avaliamos o método Sacola de Grafos Triviais para classificação de grafos em quatro bases do repositório IAM, obtendo resultados significativos em termos de acurácia e tempo de execução. O método Sacola de Grafos Visuais é avaliado para classificação de imagens nas bases Caltech-101 e Caltech-256, alcançando resultados promissores, com elevados valores de acurácia

Abstract: Nowadays, there is a strong interest for solutions that allow the implementation of effective and efficient retrieval and classification services associated with large volumes of data. In this context, several studies have been investigating the use of new techniques based on the...

Abstract: Nowadays, there is a strong interest for solutions that allow the implementation of effective and efficient retrieval and classification services associated with large volumes of data. In this context, several studies have been investigating the use of new techniques based on the comparison of local structures within objects in the implementation of classification and retrieval services. Local structures may be characterized by different types of relationships (e.g., spatial distribution) among object primitives, being commonly exploited in pattern recognition problems. In this dissertation, we propose the Bag of Graphs (BoG), a new approach based on the Bag-of-Words model that uses graphs for encoding local structures of a digital object. We present a formal definition of the proposed model, introducing concepts and rules that make this model flexible and adaptable for different applications. In the proposed approach, a digital object is represented by a graph that models the existing local structures. Using a pre-defined dictionary, the object is described by a vector representation with the frequency of occurrence of local patterns in the corresponding graph. In this work, we present two BoG-based methods, the Bag of Singleton Graphs (BoSG) and the Bag of Visual Graphs (BoVG), which create vector representations for graphs and images, respectively. Both methods are validated in classification tasks. We evaluate the Bag of Singleton Graphs (BoSG) for graph classification on four datasets of the IAM repository, obtaining significant results in terms of both accuracy and execution time. The method Bag of Visual Graphs (BoVG), which encodes the spatial distribution of visual words, is evaluated for image classification on the Caltech-101 and Caltech-256 datasets, achieving promising results with high accuracy scores