Trabalho de Formatura

Complex Network Spectrum Signature - Um novo descritor de formas

Black Bar

Projeto

Meu nome é Rodrigo Zerbini e esta página é dedicada ao meu Trabalho de Formatura, realizado durante o curso de Bacharelado em Ciência da Computação no Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP).

Este trabalho será sobre recuperação de imagens baseada em conteúdo (CBIR: Content-based image retrieval). O supervisor é o professor doutor Paulo Miranda.

Tema


Estudo e implementação de um moderno sistema de recuperação de imagens baseado em conteúdo que utiliza redes complexas e teoria espectral de grafos.

Resumo


Recuperação de imagens baseada em conteúdo é uma técnica de busca de imagens em bancos de dados [4]. Para realizar esta busca, o sistema recebe uma imagem como input e retorna imagens similares como output. O fato do sistema ser baseado em conteúdo significa que ele utiliza exclusivamente informações contidas na própria imagem, descartando o uso de qualquer outro dado associado à mesma, como tags ou descrições.

Diversas características da imagem podem ser utilizadas para a busca, como cor, textura e forma. Utilizar a forma de um objeto para reconhecimento de objetos e recuperação de imagens é um importante tópico na área de visão computacional e ainda uma tarefa bastante complexa [6]. Dentro deste contexto, o desafio está em desenvolver descritores de formas e medidas de similaridades com alta acurácia. Algumas aplicações destes descritores são, por exemplo, correspondência de imagens, classificação de forma e reconhecimento de caracteres [7].

Em 2015, três pesquisadores do Rio Grande do Sul propuseram um novo método descritor de formas [5]. O nome dado a este método foi Complex Network Spectrum Signature (CNSS).

Como o próprio nome sugere, ele é baseado em redes complexas e teoria espectral de grafos. O CNSS cria, para cada imagem, uma rede de pixels interconectados para o qual um vetor característico é calculado. A comparação entre os vetores característicos, os quais resumem as principais características da forma do objeto, é feita por meio de uma função de distância. Quanto menor a distância entre dois vetores característicos, mais as imagens são similares.

O CNSS, além de apresentar um alto grau de precisão nas bases testadas, é bastante rápido quando comparado com outros métodos: sua função de distância tem complexidade linear. O método Height Functions, por exemplo, é utilizado para reconhecimento de contornos e tem função de distância com complexidade cúbica, o que inviabiliza sua aplicação em bases maiores [8]. Percebe-se assim a importância do CNSS, sendo possível compará-lo ao estado da arte. Contudo, seu potencial ainda não foi inteiramente explorado, uma vez que ele foi aplicado somente a imagens com um único contorno.

Logo, o objetivo de estudo deste trabalho é primeiramente implementar e testar o método e, em seguida, otimizá-lo e estender seu alcance para outros tipos de imagens.

Objetivos

  • Implementação do método CNSS em C;
  • Atingir um nível de desempenho similar ao dos autores na aplicação do método às bases MPEG-7 (disponível em [1]) e leaves database (disponível em [2]);
  • Testar variações do método para verificar se há melhora na acurácia em outras bases, como por exemplo mnist, uma base de dígitos escritos à mão [3].
    • Mpeg7
    Fig. 1 - Amostras da base MPEG-7

    Cronograma de atividades

    Tarefas Mar Abr Mai Jun Jul Ago Set Out Nov
    Revisão Bibliográfica
    Implementação do vetor característico
    Implementação da função distância e métricas de avaliação
    Testes
    Melhorias e modificações
    Escrita da monografia

    Apreciação pessoal e crítica

    Desafios e frustrações

    O principal desafio enfrentado foi conseguir conciliar a realização desse trabalho com dois empregos e ainda ter algum tempo para a vida pessoal. A parte final de produção da monografia também foi bastante trabalhosa, porém muito interessante pois permitiu apronfundar meus conhecimentos em LaTeX. Na minha opinião, a maior frustração foi não alcançar a mesma precisão que os pesquisadores criadores do CNSS obtiveram. Além disso, como não foi possível ter acesso ao código-fonte no momento, outra frustração foi não conseguir identificar a razão da diferença entre os graus de precisão.

    Disciplinas Relevantes

    As disciplinas da graduação mais relevantes para a produção deste trabalho foram as seguintes:

    Referências

    [1] http://www.dabi.temple.edu/~shape/MPEG7/dataset.html (Acesso em: 4 abr. 2016)

    [2] http://fractal.ifsc.usp.br/dataset/ShapeCN.php (Acesso em: 4 abr. 2016)

    [3] http://yann.lecun.com/exdb/mnist/ (Acesso em: 4 abr. 2016)

    [4] https://en.wikipedia.org/wiki/Content-based_image_retrieval (Acesso em: 4 abr. 2016)

    [5] OLIVEIRA, A. B. de; SILVA, P. R. da; BARONE, D. A. C. A novel 2D shape signature method based on complex network spectrum. Pattern Recognition Letters, 63 (2015) 43-49.

    [6] SHU, X.; WU, X-J. A novel contour descriptor for 2D shape matching and its application to image retrieval. Image and Vision Computing, 29 (2011) 286-294.

    [7] AMANATIADIS, A.; KABURLASOS, V. G.; GASTERATOS, A.; PAPADAKIS, S. E. Evaluation of shape descriptors for shape-based image retrieval. IET Image Processing, 5 (2011) 493-499.

    [8] WANG, J.; BAI, X.; YOU, X.; LIU, W.; LATECKI, L. J. Shape matching and classification using height functions. Pattern Recognition Letters, 33 (2012) 134-143.