Sacola de grafos: definição, implementação e validação em tarefas de classificação

Author(s)

Fernanda Brandão Silva

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2014-05-16

Examining board members

Ricardo da Silva Torres; Anderson de Rezende Rocha; Luciano da Fontoura Costa

• Advisor: Ricardo da Silva Torres

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 (AU)

• FAPESP's process: 12/16172-2 - The Use of Graphs for Coding the Spatial Distribution of Visual Words and their use for Searching and Classification of Images in Large Collections
• Grantee: Fernanda Brandão Silva
• Support Opportunities: Scholarships in Brazil - Master