Universidade Federal de Campina Grande - UFCG
Centro de Engenharia Elétrica e Informática - CEEI
Coordenação de Pós-Graduação em Ciência da Computação - COPIN
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
Mestrando
Herman Martins Gomes
Orientador
2
Roteiro
 Introdução
 Conceitos Fundamentais
 Trabalhos Relacionados
 Sistema Proposto
 Estudo Experimental
 Contribuições
 Trabalhos Futuros
 Referências
3
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.
4
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.
5
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.
6
Conceitos Fundamentais: Extração de
Características - Cor
Freqüência
 Representação através de histogramas.
Nível de Cinza
 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.
7
Conceitos Fundamentais: Extração de
Características - Forma
 Característica diz respeito às formas dos objetos.
 Binarização e detectores de bordas.
Nível de Cinza
Binarização
Borda Detectada
 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].
8
Conceitos Fundamentais: Extração de
Características - Textura
 São mudanças na intensidade da imagem que
formam determinados padrões repetitivos [Tuceryan,
1993].
Exemplos de texturas
 Nesta dissertação: Texturas representadas através de
Local Binary Patterns (LBP) [Ojala, 2002] e Wavelets
de Haar e Daubechies [Wang, 1998].
9
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
10
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.
11
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.
12
Conceitos Fundamentais: Combinação
de Classificadores
 Quanto a arquitetura são classificados como:
– Lineares
Classificador
Classificador
Classificador
– Paralelos
Classificador
Classificador
Combinador
– Hierárquicos
Classificador
Classificador
Classificador
Classificador
Combinador
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
14
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
15
Sistema Proposto: Arquitetura do
Sistema
16
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.
17
Sistema Proposto: Módulo de
Classificação
18
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.
qei 

x j  Ci
mi  x j
19
Sistema Proposto: Módulo de
Combinação
 Combinação de Classificadores
– Ordenação das imagens recuperadas de forma
decrescente.
20
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:
G
 LC 
vi   1  QEg ,i   


g
 LTg 
g ,i
21
Sistema Proposto: Arquitetura do
Sistema
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.
22
Sistema Proposto: Interface com o
Usuário
23
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.
24
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.
25
Experimento 1 – Busca por Melhores
Parâmetros
Métricas de Avaliação de Classificadores
Precisão =
quantidadeDeIm agensRelevantesRecuperadas
quantidadeTotalDeIm agensRecuperadas
Cobertura =
quantidadeDeIm agensRelevantesRecuperadas
quantidadeTotalDeIm agensRelevantes
Medida-F =
2  Precisão Cobertura
Precisão Cobertura
26
Experimento 1 – Busca por Melhores
Parâmetros
Extratores
τ2
Precisão
Cobertura
Medida-F
LBP
0,05
0,191790091
0,280625
0,227855102
Wav
0,10
0,128562369
0,408125
0,195531029
HU_MOMENTS
0,10
0,093021798
0,4096875
0,151617916
HSV128
0,10
0,142346118
0,2415625
0,179133692
HSV64
0,50
0,145480311
0,3390625
0,203601898
HSV32
0,10
0,183727882
0,2365625
0,206824276
HSV16
0,10
0,199642902
0,23953125
0,21777563
RGB128
0,05
0,183070331
0,16859375
0,175534069
RGB64
0,50
0,110120024
0,241875
0,151338962
RGB32
0,10
0,172415855
0,24046875
0,20083396
RGB16
0,10
0,145861759
0,30953125
0,198284873
YCBCR128
0,10
0,176315762
0,21390625
0,193300441
YCBCR64
0,10
0,150864074
0,2621875
0,191524143
YCBCR32
0,10
0,186840728
0,26125
0,217867218
YCBCR16
0,10
0,135528171
0,2771875
0,182046467
27
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.
28
Experimento 2 – Combinação de
Classificadores
 Com a redução da quantidade de imagens, a precisão das combinações foi
superiores aos classificadores simples.
29
Experimento 2 – Combinação de
Classificadores
 Durante todo o experimento a cobertura dos classificadores combinados foi
superior aos classificadores simples.
30
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.
31
Experimento 3 – Teste com a Interface
Web e os Usuários
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
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.
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
32
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.
33
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.
34
Experimento com Usuários – Conjunto
de Imagens Fixas
 Conjunto de imagens fixas utilizadas nos testes.
RGB32
HSV16
HSV32
HSV64
RGB16
YCBCR32
RGB64
YCBCR16
YCBCR64
Com. Text.
Wavelets
Cor & Forma
HuMoments
Com. Cor
Cor, Text. e
Forma
Text. e Forma
Melhor Comb.
LBP
Cor e Text.
35
Experimento com Usuários – Conjunto
de Imagens Fixas
 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%.
36
Experimento com Usuários – Conjunto
de Imagens Fixas
 Identificação de usuários incomuns
– Média geral das precisões 23,5%.
37
Experimento com Usuários – Conjunto
de Imagens Fixas
 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.
38
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.
39
Experimento com Usuários – Única
Imagem
 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%.
40
Experimento com Usuários – Única
Imagem
 Média geral das precisões 18,5%.
41
Experimento com Usuários – Única
Imagem
 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.
42
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.
43
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.
44
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.
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.
Universidade Federal de Campina Grande - UFCG
Centro de Engenharia Elétrica e Informática - CEEI
Coordenação de Pós-Graduação em Ciência da Computação - COPIN
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
Mestrando
Herman Martins Gomes
Orientador
Tempo de processamento do
sistema
Tempo
Tempo
Tempo
Classificadores
Extrator
Classificador
Combinador
Tempo Total
RGB16
0,109354
0,695717
X
RGB32
0,109642
0,777791
X
RGB64
0,103476
0,772575
X
HSV16
0,119441
0,577365
X
HSV32
0,113153
0,736847
X
HSV64
0,110972
0,781814
X
YCbCr16
0,114826
0,623778
X
YCbCr32
0,107831
0,567676
X
YCbCr64
0,104747
0,587171
X
LBP
1,300055
0,662135
X
Wavelets
1,580270
0,098529
X
Momentos de Hu
0,139364
0,565734
X
Combinação Cor
0,323098
0,780349
1,072461
Combinação Textura
2,410962
0,556455
0,927330
Combinação Cor e Textura
2,700370
1,274722
1,687175
Combinação Cor e Forma
0,430542
1,280255
1,275038
Combinação Forma e Textura
2,519608
0,847213
1,172503
Combinação Cor, Forma e Textura
2,821672
1,596423
1,734224
Melhor Combinação
2,592550
0,384204
0,563112
0,805072
0,887433
0,876051
0,696806
0,850000
0,892786
0,738604
0,675507
0,691918
1,962190
1,678799
0,705098
2,175908
3,894747
5,662267
2,985835
4,539324
6,152319
3,539866
Vídeo Demonstrativo