Investigação de Técnicas para Extração de Características e Classificação Aplicadas à Recuperação de Imagens por Conteúdo Saulo de Tarso Oliveira Rodrigues

Investigação de Técnicas para Extração de Características e Classificação Aplicadas à Recuperação de Imagens por Conteúdo

Saulo de Tarso Oliveira RodriguesMestrando

Herman Martins GomesOrientador

Universidade Federal de Campina Grande - UFCGCentro de Engenharia Elétrica e Informática - CEEI

Coordenação de Pós-Graduação em Ciência da Computação - COPIN

Roteiro

Introdução Conceitos Fundamentais Trabalhos Relacionados Sistema Proposto Estudo Experimental Contribuições Trabalhos Futuros Referências

2

Introdução

Grande número de organizações vêm coletando e armazenando imagens, como também as adicionando massivamente à World Wide Web.– Difícil organização.

Foram identificados dois principais problemas na recuperação de imagens.– Anotações manuais.– Extração de informações.

3

Introdução

Criação da Recuperação de imagens por conteúdo (“Content-Based Image Retrieval”).– Indexação e Recuperação de imagens utilizando as suas

próprias características visuais.

Mesmo com os avanços na área de recuperação por conteúdo.– Existem algumas áreas com deficiências no contexto de

busca por conteúdo [Datta, 2006]. Internet.

4

Conceitos Fundamentais

Em particular, a maioria dos Sistemas de Recuperação de Imagens Baseada em Conteúdo (SRIBC) possuem as seguintes características em comum [Subrahmanian, 1998]:– Extração de Características;– Indexação;– Reconhecimento.

5

Conceitos Fundamentais: Extração de Características - Cor

Representação através de histogramas.

Representação através de diferentes espaços de cor;– RGB (Red, Green e Blue);– HSV (Hue, Saturation e Value);– YCbCr.

Nesta dissertação: Histogramas em diferentes espaços de cor e quantizados.

6

Fre

qü

ên

c ia

Nível de Cinza

Conceitos Fundamentais: Extração de Características - Forma

Característica diz respeito às formas dos objetos. Binarização e detectores de bordas.

Após a identificação das formas dos objetos, geralmente é necessário descrevê-las com base nas propriedades invariantes a escala, rotação e translação.– Nesta dissertação: Momentos Invariantes de Hu [Hu, 1962].

7

Nível de Cinza

Binarização Borda Detectada

Conceitos Fundamentais: Extração de Características - Textura

São mudanças na intensidade da imagem que formam determinados padrões repetitivos [Tuceryan, 1993].

Nesta dissertação: Texturas representadas através de Local Binary Patterns (LBP) [Ojala, 2002] e Wavelets de Haar e Daubechies [Wang, 1998].

8

Exemplos de texturas

Conceitos Fundamentais: Estruturas de Indexação

Após a extração das características é necessário representar essas informações de forma que seja possível uma recuperação.– Vetores de características ou estruturas de dados

multidimensionais.

As técnicas de extração de características produzem vetores de grande dimensão.– Utilização de novos métodos de indexação.

Eficiente com dados multidimensionais Eficientes na busca

9

Conceitos Fundamentais: Estruturas de Indexação

Entre os métodos existentes, pode-se destacar o GHSOM (Growing Hierarquical Self-Organizing Maps) [Rauber, 2002].– Treinamento não-supervisionado;– Criação de estrutura de árvore para indexação;– Criação de grupos dinâmicos;– Capacidade de suporte a medidas de similaridades arbitrárias.

10

Conceitos Fundamentais: Combinação de Classificadores

A combinação de classificadores é utilizada como um método para diminuir a probabilidade de erro na classificação.

Segundo Kittler [Kittler, 1998], um combinador pode melhorar o desempenho do sistema, fazendo com que as deficiências de um classificador sejam suprimidas pelo bom desempenho de outros.

Geralmente o conjunto de classificadores são organizados em uma arquitetura e uma regra de combinação.

11

Conceitos Fundamentais: Combinação de Classificadores

Quanto a arquitetura são classificados como:– Lineares

– Paralelos

– Hierárquicos

12

Classificador Classificador Classificador

Classificador

ClassificadorCombinador

Classificador

Classificador

Classificador

ClassificadorCombinador

Trabalhos Relacionados: Sistemas Existentes

Sistema Consulta Forma de Extração Medida de similaridade Indexação

QBIC Imagem Exemplo, esboço e por padrões de cor e

textura

Histograma de Cor, Texturas segundo Tamura e Momentos

invariantes

Distância Euclidiana R*-tree

NETRA Imagens Pré-definidas Histograma de cor quantizados, Wavelet de Gabor e

Transformada rápida de Fourier

Distância Euclidiana SS-tree

PicSOM Imagens Pré-definidas com refinamento

interativo

Histogramas de Cor, Momentos de Cor e Transformada de

Fourier

Distância Euclidiana SOM

VisualSEEk Esboço Histograma de cor quantizado Distância Euclidiana R-tree

WebSEEk Esboço e texto Histograma de cor quantizado Distância entre histogramas

Dados da Extração

Sistema de French Imagem exemplo Histograma de cor (para as diferentes representações da

imagem de consulta)

Distância entre histogramas

Dados extraídos de cara representação

Sistema de Barcellos Imagem exemplo Histograma de cor quantizado Distância Euclidiana Dados da Extração

Sistema de Presad Imagem exemplo Histograma de cor quantizado, Forma (Maior Eixo, Menor Eixo

e Centro de gravidade)

Diferença entre as regiões extraídas,

utilizando um limiar

Dado não informado

Sistema de Edvarden Imagem exemplo Histograma de cor quantizado Distância Euclidiana, Interseção de histograma

e distância quadrática

Dados da Extração

13

Sistema Proposto: Arquitetura do Sistema

A arquitetura macro do sistema proposto é formada por:– Interface com usuário– Robô de Busca– Extração de Características– Treinamento dos Classificadores– Classificadores– Combinação de Classificadores

No sistema proposto existe dois modos de operação distintos:– Modo de consulta – Modo de busca

14


15

Sistema Proposto: Módulo de Extração

Extração de Características– Métodos de extração:

RGB, HSV e YCbCr, com diferentes números de bins (128, 64, 32 e 16).

LBP e Wavelets. Momentos Invariantes de Hu.

16

Sistema Proposto: Módulo de Classificação

17

Sistema Proposto: Módulo de Classificação

Treinamento dos Classificadores– Treinamento das redes GHSOM (cada classificador

utilizando apenas um tipo de característica).Classificadores

– Similaridade entre características submetidas e o classificador GHSOM específico.

– Neurônios vencedores.

18

j i

i i jx C

qe m x

Sistema Proposto: Módulo de Combinação

19

Combinação de Classificadores– Ordenação das imagens recuperadas de forma

decrescente.

Sistema Proposto: Módulo de Combinação

Para a combinação, foi utilizado um método em que cada imagem recuperada recebe um voto.– Ordena as imagens através dos votos.

O cálculo do voto de cada imagem é expresso por:

20

,,1

Gg i

i g ig g

LCv QE

LT


Robô de Busca– Web Crawler: busca e indexação automática de

imagens disponíveis na World Wide Web.– Regras de download das imagens:

Tamanho mínimo de 150 x 150 pixels. Razão entre altura e largura entre 3 e 1/3. Formato JPEG.

– Indexação das características extraídas e URLs das imagens.

21

Sistema Proposto: Interface com o Usuário

22

Estudo Experimental Experimento 1 – Busca pelos melhores parâmetros dos

classificadores GHSOM.– Melhores parâmetros de treinamento para cada classificador.

Experimento 2 – Combinação de classificadores.– Experimentos objetivos.

Experimento 3 – Teste com a Interface Web e os usuários.– Experimentos subjetivos.

23

Experimento 1 – Busca por Melhores Parâmetros

Avaliação do parâmetro τ2

– Valores avaliados: 0,5; 0,1; 0,05; 0,01; 0,005; 0,001; 0,0005; 0,00001;

0,000005; 0,000001 e 0,0000001.

Banco rotulado com 800 imagens, distribuídas em 16 grupos.– aviões, vegetação, aves, garrafas, camelos, carros,

faces, flores, futebol, guitarras, casas, motocicletas, outono, planetas e pôr-do-sol.

24


Métricas de Avaliação de Classificadores

25

Cobertura = ntesgensRelevaTotalDeImaquantidade

ecuperadaselevantesRDeImagensRquantidade

Precisão = radasgensRecupeTotalDeImaquantidade

ecuperadaselevantesRDeImagensRquantidade

Medida-F = CoberturaPrecisão

CoberturaPrecisão2


26

Extratores τ2 Precisão Cobertura Medida-F

LBP 0,05 0,191790091 0,280625 0,227855102Wav 0,10 0,128562369 0,408125 0,195531029

HU_MOMENTS 0,10 0,093021798 0,4096875 0,151617916HSV128 0,10 0,142346118 0,2415625 0,179133692HSV64 0,50 0,145480311 0,3390625 0,203601898HSV32 0,10 0,183727882 0,2365625 0,206824276HSV16 0,10 0,199642902 0,23953125 0,21777563

RGB128 0,05 0,183070331 0,16859375 0,175534069RGB64 0,50 0,110120024 0,241875 0,151338962RGB32 0,10 0,172415855 0,24046875 0,20083396RGB16 0,10 0,145861759 0,30953125 0,198284873

YCBCR128 0,10 0,176315762 0,21390625 0,193300441YCBCR64 0,10 0,150864074 0,2621875 0,191524143YCBCR32 0,10 0,186840728 0,26125 0,217867218YCBCR16 0,10 0,135528171 0,2771875 0,182046467

Experimento 2 – Combinação de Classificadores

Comparação entre os classificadores simples e combinados.– RGB com 32 bins, HSV com 16 bins, YCbCr com 32

bins, Wavelets, LBP e Momentos Invariantes de Hu.– Redução da quantidade de imagens recuperadas:

400, 300, 200, 100, 90, 80, 70, 60, 50, 45, 40, 35, 30, 25, 20, 15, 10 e 5.

– Os classificadores foram combinados de forma dois a dois, três a três, quatro a quatro, cinco a cinco e seis a seis.

27


28

Com a redução da quantidade de imagens, a precisão das combinações foi superiores aos classificadores simples.


29

Durante todo o experimento a cobertura dos classificadores combinados foi superior aos classificadores simples.

Experimento 3 – Teste com a Interface Web e os Usuários

Teste utilizando o sistema proposto.

Banco de imagens com aproximadamente 64.000 URLs de imagens.

Experimento 3 foi subdividido em três partes:– Imagens aleatórias;– Conjunto de imagens fixas;– Única imagem.

30

Experimento 3 – Teste com a Interface Web e os Usuários

Extratores τ2

LBP 0,0005000

WAV 0,0000010

HUMOMENTS 0,0000050

HSV64 0,0000100

HSV32 0,0000001

HSV16 0,0000010

RGB64 0,0000050

RGB32 0,0000010

RGB16 0,0000500

YCBCR64 0,0001000

YCBCR32 0,0000500

YCBCR16 0,0001000

31

• HSV com 16 bins;• HSV com 32 bins;• HSV com 64 bins;• RGB com 16 bins;• RGB com 32 bins;• RGB com 64 bins;• YCbCr com 16 bins;• YCbCr com 32 bins;• YCbCr com 64 bins;• LBP;• Wavelets;• Momentos Invariantes de Hu;• Combinação de Cor;• Combinação de Textura;• Combinação de Cor e Textura;• Combinação de Cor e Forma;• Combinação de Textura e Forma;• Combinação de Cor, Textura e Forma.

Experimento com Usuários – Imagens Aleatórias

Foram selecionados 25 usuários.

Download da imagem para utilizar como consulta.

Os melhores resultados foram:– Combinação de Cor com 36,2%.– Combinação de Forma e Textura com 35,0%.

Problema para identificação dos usuários incomuns.– Imagens diferentes para cada usuário.

32

Experimento com Usuários – Conjunto de Imagens Fixas

Definição de nova metodologia de testes.– Testes configurados automaticamente, transparência para

o usuário.– Tentativa de identificar possíveis usuários incomuns.– Foram utilizados 35 usuários.

Em adição aos classificadores utilizados, foi testada a Melhor Combinação.– RGB com 32 bins, HSV com 16 bins, LBP e Wavelets.

33


Conjunto de imagens fixas utilizadas nos testes.

34

HSV16

HSV32 HSV64 RGB16

RGB32

RGB64 YCBCR16

YCBCR32

YCBCR64 LBP

Wavelets HuMoments Com. Cor

Com. Text. Cor e Text.

Cor & Forma

Text. e Forma

Cor, Text. e Forma

Melhor Comb.


35

As melhores precisões foram obtidas para as combinações.– Melhor Combinação (RGB32, HSV16 , LBP e Wavelets)

obteve 48,0%.– Combinação de Cor e Textura obteve 39,1%.– Combinação de Cor obteve 38,9%.

Alguns classificadores simples se destacaram.– YCbCr com 16 bins obteve 35,7%.– HSV com 16 bins obteve 32,0%.


Identificação de usuários incomuns– Média geral das precisões 23,5%.

36


Precisões dos classificadores sem os usuários incomuns .– Aumento na precisão dos melhores classificadores.

Melhor Combinação, aumento de 48,0% para 48,8%.

– Redução na precisão dos piores classificadores. HSV com 64 bins, diminuiu de 5,1% para 3,2%.

A retirada dos usuários incomuns contribui para destacar os melhores classificadores.

37

Experimento com Usuários – Única Imagem

Uma única imagem selecionada foi utilizada para todos os testes.

Os mesmo 35 usuários do experimento anterior. Os usuários incomuns também foram identificados.

38


Dos classificadores testados, os que obtiveram melhores resultados foram:– Melhor Combinação obteve 27,7%.– Combinação de Cor e Textura obteve 25,4%.– YCbCr com 32 bins obteve 25,4%.

39


Média geral das precisões 18,5%.

40


Após a retirada dos usuários incomuns.– Redução do número de usuários incomuns.– Redução na precisão dos classificadores, mas os melhores

classificadores obtiveram destaque.– Os melhores classificadores foram:

Combinação de Cor e Textura, YCbCr com 32 bins e Melhor Combinação.

– Possivelmente os resultados dos classificadores podem ter sido influenciados pela escolha da imagem de consulta.

41

Contribuições Foi desenvolvido um novo método de combinação de classificadores GHSOM.

– Avaliados através de testes objetivos e subjetivos.

Foi desenvolvido um sistema de recuperação por conteúdo.– Banco de dados dinâmico.

Foram realizadas investigações sobre:– Extração de características;– Indexação;

Publicações– Workshop de Teses e Dissertações (SIBGRAPI 2007).– Poster aceito para publicação no SIBGRAPI 2008.– Escrita de artigo em andamento para submissão ao JBCS.

42

Trabalhos Futuros Estudar novos métodos de extração de características.

Estudar novos métodos de indexação e classificação.

Incorporar estratégias de processamento distribuído aos diferentes módulos do sistema.

Desenvolver uma interface que permita feedback dos usuários.

Automatizar a criação das redes GHSOM (a medida que a base de dados cresce) .

Investigar método para eliminar URLs de imagens inválidas.

43

Referências Bibliográficas [Datta, 2006] R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: Ideas,

influences, and trends of the new age. ACM Computing Surveys, pages 1–60, 2006.

[Hu, 1962] M.K Hu. Visual pattern recognition by moment invariants. Information Theory, IEEE Transactions on, 8(2):179–187, 1962.

[Huang, 1997] Y. Rui, T. S. Huang, and S. F. Chang. Image retrieval: Past, present, and future. In International Symposium on Multimedia Information Processing, pages 2–16, 1997.

[Kittler, 1998] J. Kittler, M. Hatef, RPW Duin, and J. Matas. On combining classifiers. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 20(3):226–239, 1998.

44

Referências Bibliográficas [Ojala, 2002] T. Ojala, M. Pietikainen, and T. Maenpaa. Multiresolution grayscale

and rotation invariant texture classification with local binary patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7):971–987, 2002.

[Rauber, 2002] A. Rauber, D. Merkl, and M. Dittenbach. The growing hierarchical selforganizing map: exploratory analysis of high-dimensional data. Neural Networks, IEEE Transactions on, 13(6):1331–1341, 2002.

[Subrahmanian, 1998] V. S. Subrahmanian. Principles of multimedia database systems. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998.

[Tuceryan, 1993] M. Tuceryan and A. K. Jain. Texture analysis. Handbook of Pattern Recognition and Computer Vision, pages 235–276, 1993.

[Wang, 1998] J. Z. Wang, G.Wiederhold, O. Firschein, and S. XinWei. Content-based image indexing and searching using Daubechies’ wavelets. International Journal on Digital Libraries, 1(4):311–328, 1998.

Investigação de Técnicas para Extração de Características e Classificação Aplicadas à Recuperação de Imagens por Conteúdo

Saulo de Tarso Oliveira RodriguesMestrando

Herman Martins GomesOrientador

Universidade Federal de Campina Grande - UFCGCentro de Engenharia Elétrica e Informática - CEEI

Coordenação de Pós-Graduação em Ciência da Computação - COPIN

Tempo de processamento do sistema

ClassificadoresTempo Extrator

Tempo Classificador

Tempo Combinador Tempo Total

RGB16 0,109354 0,695717 X 0,805072RGB32 0,109642 0,777791 X 0,887433RGB64 0,103476 0,772575 X 0,876051HSV16 0,119441 0,577365 X 0,696806HSV32 0,113153 0,736847 X 0,850000HSV64 0,110972 0,781814 X 0,892786YCbCr16 0,114826 0,623778 X 0,738604YCbCr32 0,107831 0,567676 X 0,675507YCbCr64 0,104747 0,587171 X 0,691918LBP 1,300055 0,662135 X 1,962190Wavelets 1,580270 0,098529 X 1,678799Momentos de Hu 0,139364 0,565734 X 0,705098Combinação Cor 0,323098 0,780349 1,072461 2,175908Combinação Textura 2,410962 0,556455 0,927330 3,894747Combinação Cor e Textura 2,700370 1,274722 1,687175 5,662267Combinação Cor e Forma 0,430542 1,280255 1,275038 2,985835Combinação Forma e Textura 2,519608 0,847213 1,172503 4,539324Combinação Cor, Forma e Textura 2,821672 1,596423 1,734224 6,152319Melhor Combinação 2,592550 0,384204 0,563112 3,539866

Vídeo Demonstrativo

Documents

Investigação de Técnicas para Extração de Características e Classificação Aplicadas à Recuperação de Imagens por Conteúdo Saulo de Tarso Oliveira Rodrigues