Bag of graphs = definition, implementation, and validation in classification tasks
Fernanda Brandão Silva, Ricardo da Silva Torres · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2014
Atualmente, ha uma alta demanda por solucoes que possibilitem a implementacao de servicos de recuperacao e classificacao eficazes e eficientes para grande volumes de dados. Nesse contexto, diversos estudos tem investigado o uso de novas tecnicas baseadas na comparacao de estruturas locais presentes em objetos na implementacao de servicos de classificacao e recuperacao. Estruturas locais podem ser caracterizadas por diferentes tipos de relacionamentos (e.g., distribuicao espacial) entre primitivas de objetos, sendo geralmente exploradas em problemas de reconhecimento de padroes. Nessa dissertacao 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 definicao formal do modelo proposto e apresentada, assim como conceitos e regras que tornam este modelo flexivel e ajustavel a diferentes aplicacoes. Na abordagem proposta, um objeto e representado por um grafo que modela as estruturas locais existentes. Usando um dicionario pre-definido, o objeto pode ser descrito por uma representacao vetorial com a frequencia de ocorrencia de padroes locais no grafo correspondente. Neste trabalho, apresentamos dois metodos baseados no modelo proposto, a Sacola de Grafos Triviais e a Sacola de Grafos Visuais, que constroem representacoes vetoriais para imagens e grafos, respectivamente. Ambos os metodos sao validados em tarefas de classificacao. Nos avaliamos o metodo Sacola de Grafos Triviais para classificacao de grafos em quatro bases do repositorio IAM, obtendo resultados significativos em termos de acuracia e tempo de execucao. O metodo Sacola de Grafos Visuais e avaliado para classificacao de imagens nas bases Caltech-101 e Caltech-256, alcancando resultados promissores, com elevados valores de acuracia. Abstract