Estudo Comparativo de Estruturas de Indexação para...

Estudo Comparativo de Descritores para Recuperação de Imagens por Conteúdo na Web

Otávio Augusto Bizetto Penattiotavio@lis.ic.unicamp.br

Ricardo da Silva Torres (orientador)rtorres@ic.unicamp.br

Instituto de Computação – UnicampMarço 2009

Roteiro

MotivaçãoRecuperação de imagens por conteúdoObjetivosCritérios de avaliaçãoEstudo teóricoFerramentaExperimentos e resultadosConclusões e trabalhos futuros

Motivação

Crescente quantidade de imagens

Conteúdo heterogêneo

Motivação

PraiaMinhas fériasVerão 2007Céu azulCéu e marIMG321.jpg

Problemas de descrições textuais

Problemas de descrições textuais

Problemas de descrições textuais

Problemas de descrições textuais

Consulta:

Resultados:

Recuperação de imagens por conteúdo

Descritor de imagensAlgoritimo para extração de característicasFunção de distância/similaridade

vetor

vetor

distância

DESCRITOR DE IMAGENS

Cálculo de Distância/Similaridade

Extração de características

Extração de características

Objetivo

Comparar descritores de imagens em um cenário Web

Processo de buscaUsuário define consultaSistema extrai vetor de características da consultaSistema compara vetor da consulta com vetores da baseSistema exibe resultados ordenados para o usuário

Critérios de Avaliação

Critérios de avaliação

Figura adaptadade [Kherfi2004]

Critérios de avaliação

Descritores

Figura adaptada de [Kherfi2004]

Critérios de avaliação

Complexidade extração de características

Coleta de dados

Algoritmo de extração

Base de vetores de

características

OFFLINE

Figura adaptadade [Kherfi2004]

Critérios de avaliação

ONLINE

Algoritmo de extração

Figura adaptada de [Kherfi2004]

Complexidade extração de características

Função de distância

Critérios de avaliação

Base de vetores de

características

ONLINE

Figura adaptada de [Kherfi2004]

Complexidade função de distância

Critérios de avaliação

Base de vetores de

características

1 vetor de características/imagem/

descritor

Figura adaptada de [Kherfi2004]

Requisitos de armazenamento

EficáciaAmbiente de validação

ComparaçõesBases de imagensMedidas de avaliação

Critérios de Avaliação

Cor28 descritores

Textura28 (2 descritores adicionados)

Forma32 (1 descritor adicionado)

Total88 descritores

Estudo Teórico

Complexidade extraçãoVisitação de um pixel da imagem

Ex: O(n), O(nlogn)

Complexidade distânciaVisitação de um elemento do vetor de características

Ex: O(vs), O(vs2)

Tamanho vetor de característicasQuantidade de valores no vetor

Estudo Teórico

Estudo TeóricoDescritores de Cor

Descritor Extração Distância Espaço (quantidade de valores)

Maioria O(n) O(vs)Dependente de quantizações

Estudo TeóricoDescritores de Cor

Descritor Bases de imagens Comparações

Maioria- Domínio restrito- Poucas imagens

Com variações deles próprios ou com GCH

Estudo TeóricoDescritores de Textura

Foram adicionados os descritores SBP e SID

Descritor Extração Distância Espaço (quantidade de valores)

Maioria O(n) O(vs)Dependente de quantizações

Estudo TeóricoDescritores de Textura

Bases de imagens Comparações

Maioria Brodatz Com Gabor

Descritor Extração Distância Espaço (quantidade de valores)

MaioriaDependente de segmentação

O(vs)Dependente dos

objetos

Outros maior que O(n) O(vs)Dependente de quantizações

Estudo Teórico

Descritores de Forma

Foi adicionado descritor Moment Invariants

Estudo Teórico

Descritores de Forma

Bases de imagens Comparações

Maioria MPEG-7Com CSS ou Moment

Invariants

MotivaçãoOrganizar e padronizar experimentos comparativos entre descritores

Ferramenta

Ferramenta

Ferramenta

Ferramenta

Ferramenta

Ferramenta

Ferramenta

Ferramenta

Medidas de avaliaçãoTempo = segundosTamanho do vetor de características = bytes ou bitsEficácia = Precision x Recall, P10, P20 e P30

4 bases de imagens2 tipos de experimentos

Experimentos

Experimentos - ResultadosETH

3280 imagens

8 categorias

todas consultas

Descritores de CorGCH

CGCH

LCH

CCV

ACC

JAC

BIC

Experimentos - Resultados

CBCColor Bitmap

CSD

CW-HSV

CW-LUV

CM

Experimentos - Resultados

Descritores de CorDescritor

Tempo extração relativo ao GCH

CGCH 0,81

GCH 1,00

LCH 1,45

Color Bitmap 2,69

BIC 5,58

CW-HSV 6,05

CM 6,31

CCV 8,18

CSD 37,13

ACC 40,89

CW-LUV 46,21

JAC 77,58

CBC 126,01

Experimentos - Resultados

Descritores de CorDescritor

Tempo distância relativo ao GCH

CM 0,65

CW-HSV 0,68

CW-LUV 0,73

Color Bitmap 0,83

CGCH 0,98

GCH 1,00

BIC 1,17

CCV 1,19

CSD 1,38

ACC 1,64

LCH 4,09

JAC 17,99

CBC 26,34

Experimentos - Resultados

Descritores de CorDescritor

Tamanho relativo do vetor em relação ao GCH

CW-HSV 0,03

CW-LUV 0,06

CM 0,19

Color Bitmap 0,24

GCH 1,00

CGCH 1,00

BIC 2,00

CCV 2,00

CSD 2,88

CBC 3,38

ACC 4,00

LCH 16,00

JAC 500,00

Experimentos - Resultados

Eficácia:

Descritores de Cor usados na base heterogênea:

BIC

CSD

ACC

Color Bitmap

GCH

Experimentos - Resultados

Experimentos - Resultados

Brodatz1776 imagens

111 categorias

todas consultas

Descritores de TexturaLBP

HTD

SASI

CCOM

Unser

QCCH

LAS

SID

Experimentos - Resultados

Experimentos - Resultados

Descritores de Textura

DescritorTempo extração relativo ao

LBP

LBP 1,00

CCOM 1,84

Unser 2,02

LAS 3,09

QCCH 13,15

SID 131,54

SASI 259,39

HTD 2949,22

Experimentos - Resultados

Descritores de Textura

DescritorTempo distância relativo ao

LBP

Unser 0,90

SID 0,92

HTD 0,92

QCCH 0,93

LAS 0,95

SASI 0,98

LBP 1,00

CCOM 1,22

Experimentos - Resultados

Descritores de Textura

DescritorTamanho relativo do vetor em

relação ao LBP

LBP 1,00

SID 1,60

Unser 3,20

QCCH 4,00

HTD 4,80

CCOM 6,20

SASI 6,40

LAS 25,60

Experimentos - Resultados

Eficácia:

Descritores de Textura usados na base heterogênea:

LAS

CCOM

LBP

Experimentos - Resultados

Experimentos - Resultados

Caltech1018677 imagens

101 categorias

1010 consultas

Descritores de FormaEOAC

Spytec

Experimentos - Resultados

Experimentos - Resultados

Descritores de Forma

DescritorTempo extração relativo ao

EOAC

Spytec 0,88

EOAC 1,00

Experimentos - Resultados

Descritores de Forma

DescritorTempo distância relativo ao

EOAC

Spytec 0,91

EOAC 1,00

Experimentos - Resultados

Descritores de Forma

DescritorTamanho relativo do vetor em

relação ao EOAC

Spytec 0,06

EOAC 1,00

Experimentos - Resultados

Eficácia:

Experimentos - ResultadosEficácia - EOAC:

Experimentos - ResultadosEficácia - EOAC:

Descritores de Forma usados na base heterogênea:

Nenhum

Experimentos - Resultados

Experimentos - Resultados

Yahoo234.828 images

não classificada

Descritores usados na base YahooBIC

CSD

ACC

Color Bitmap

GCH

LAS

CCOM

LBP

Experimentos - Resultados

Experimentos - Resultados

Descritores na base Yahoo

DescritorTempo extração relativo ao

GCH

GCH 1,00

Color Bitmap 1,58

LBP 3,31

BIC 3,67

CCOM 5,51

LAS 9,82

CSD 14,65

ACC 19,23

Experimentos - Resultados

Descritores na base Yahoo

DescritorTempo distância relativo ao

GCH

LAS 0,77

LBP 0,84

Color Bitmap 0,86

GCH 1,00

BIC 1,20

CSD 1,42

ACC 1,59

CCOM 11,97

Experimentos - Resultados

Descritores na base Yahoo

DescritorTamanho relativo do vetor em

relação ao GCH

LBP 0,16

Color Bitmap 0,24

GCH 1,00

BIC 2,00

CSD 2,88

ACC 4,00

LAS 4,00

CCOM 45,86

Experimentos - Resultados

Eficácia na base Yahoo:15 usuários reais

16 imagens de consulta

Experimentos - Resultados

Eficácia na base Yahoo:Recupera os 30 primeiros resultados de cada descritor

Combina-os

Embaralha-os

Exibe-os para o usuário

Experimentos - Resultados

Eficácia na base Yahoo – média geral:

Descritor P10

BIC 0,31

ACC 0,27

GCH 0,25

LAS 0,23

CSD 0,18

Color Bitmap 0,17

LBP 0,14

CCOM 0,10

Experimentos - Resultados

Eficácia na base Yahoo – média geral:

Descritor P20

BIC 0,21

ACC 0,18

GCH 0,17

LAS 0,16

Color Bitmap 0,12

CSD 0,12

LBP 0,08

CCOM 0,05

Experimentos - Resultados

Eficácia na base Yahoo – média geral:

Descritor P30

BIC 0,17

ACC 0,15

LAS 0,13

GCH 0,13

Color Bitmap 0,10

CSD 0,09

LBP 0,06

CCOM 0,03

Experimentos - Resultados

Eficácia na base Yahoo – consulta 10:

Descritor P10

ACC 0,77

BIC 0,76

LAS 0,65

GCH 0,59

LBP 0,44

CSD 0,40

Color Bitmap 0,40

CCOM 0,20

Experimentos - Resultados

Eficácia na base Yahoo – consulta 6:

Descritor P10

LAS 0,23

LBP 0,19

GCH 0,19

CSD 0,12

CCOM 0,11

BIC 0,11

ACC 0,09

Color Bitmap 0,09

Experimentos - Resultados

Eficácia na base Yahoo – consulta 14:

Descritor P10

LAS 0,55

Color Bitmap 0,11

ACC 0,09

BIC 0,07

GCH 0,07

CSD 0,06

LBP 0,05

CCOM 0,05

Conclusões

Descritores sofrem degradação de desempenho

Descritores de cor tiveram melhor eficácia do que os descritores de textura

Influência da semântica da imagem

Influência do fundo da imagem

Conclusões - Contribuições

Comparação teórica em termos de complexidade assintótica entre 88 descritores

Comparação de grande quantidade de descritores em experimentos práticos

Comparação de descritores numa base com mais de 200 mil imagens heterogêneas

Avaliação de eficácia dos descritores por usuários reais

Desenvolvimento de uma ferramenta para comparação automatizada entre descritores

Conclusões – Trabalhos Futuros

Inclusão de novos descritores

Incorporação de novas funcionalidades à ferramenta

Implementação de um protótipo de sistema de recuperação de imagens por conteúdo na Web

Pesquisa em técnicas para combinação de descritores de imagens

Pesquisa em técnicas para combinação de descritores textuais e descritores de imagens

Publicações

Aceitos:O. A. B. Penatti and R. da S. Torres. Color descriptors for web image retrieval: A comparative study. XXI Brazilian Symposium on Computer Graphics and Image Processing, pages 163–170, Outubro. 2008.

R. da S. Torres, J. A. M. Zegarra, J. A. dos Santos, C. D. Ferreira, O. A. B. Penatti, F. A. Andaló, and J. Almeida. Recuperação de imagens: Desafios e novos rumos. Seminário Integrado de Software e Hardware (SEMISH), Julho 2008.

Submetidos:J. Almeida, A. Rocha, O. Penatti, R. da S. Torres, and S. Goldenstein. Image retrieval using semantic information regions. Multimedia Tools And Applications.

O. Penatti and R. da S. Torres. A comparative study of texture descriptors for content-based image retrieval. IEEE International Conference on Image Processing, 2009.

Agradecimentos

FAPESP (Processo 2006/59525-1)

CNPqCAPESFAPESP/Microsoft ResearchUFAMICLISProf. Ricardo da Silva Torres

Experimentos - Resultados

Eficácia na base Yahoo – consulta 1:

Experimentos - Resultados

Eficácia na base Yahoo – consulta 2:

Experimentos - Resultados

Eficácia na base Yahoo – consulta 3:

Banco de dados

Ferramenta

Evaluation Measure

Descriptor

Experiment Time

Distance

Experiment User

Evaluation

Image Database Experiment

Configuração Descritores

Descritores de CorDescritor Configuração

GCH 64 bins, L1

CGCH 64 bins, L1

LCH grade 4x4, 64 bins, L1

CCV 128 bins, L1

ACC 64 bins, 4 distâncias, L1

JAC 64 bins cor, 5 bins outras, 4 distâncias, L1

BIC 128 bins, dLog

CBC 6 valores por região, IRM

Color Bitmap 100 blocos, Hamming

CSD 184 bins, L1

CW-HSV 64 bins, Hamming

CW-LUV 128 bins, Hamming

CM 6 momentos

Configuração Descritores

Descritores de Textura

Descritor Configuração

LBP P=8, R=1, L1

HTD 4 escalas, 6 orientações

SASI 3 janelas, 4 direções

CCOM 216 bins, distância=1

Unser 256 níveis de cinza, 4 ângulos, dist=1.5, 8 informações, L1

QCCH 40 valores, L1

LAS 256 bins (4 bins por canal), L1

SID 2 escalas, 4 orientações

Configuração Descritores

Descritores de Forma

Descritor Configuração

EOAC 72 ângulos, 4 distâncias, Sobel, L1

Spytec 16 coeficientes, L2

Estudo TeóricoDescritores de Cor

Descritor Extração Distância Espaço (quantidade de valores)

GCH O(n) O(vs) Q

CGCH O(n) O(vs) Q

LCH O(n) O(vs) Q*QC

Color Bitmap O(n) O(vs) 3*m bits + 6

BIC O(n) O(vs) Q*2

CW-HSV O(n) O(vs) 63 bits

CW-LUV O(n) O(vs) 127 bits

CM O(n)+O(Q2*QM) O(vs) QM*2

CCV O(n) O(vs) Q*2

CSD O(n) O(vs) entre 32 e 184 bins

ACC O(n) O(vs) Q*QD

JAC O(n) O(vs) QC*QG*QR*QT*QD

CBC O(nlogn)O(Q1*Q2*log(Q1*Q

2))QR*6

Estudo Teórico

Descritores de Textura

Descritor Extração Distância Espaço (quantidade de valores)

LBP O(n) O(vs) P+2

CCOM O(n) O(vs) Q2*D*2

Unser O(n) ND QA*(QG*2)*2

LAS O(n) O(vs) Q

QCCH O(n) O(vs) T

SASI O(S*L*n) O(vs)2*QO*SUM(|

´(tamJanela[i]/4)`|+1)

HTD O(nlogn) O(vs) S*K*2

SID O(nlogn) O(vs) S*K*2

Estudo Teórico

Descritores de Forma

Descritor Extração Distância Espaço (quantidade de valores)

EOAC O(n) O(vs) QA*QD

Spytec O(n) O(vs) F

Experimentos - Resultados

Eficácia na base Yahoo – consulta 6:

Usuário P10

Otimista 0,25

Pessimista 0,04

Experimentos - Resultados

Eficácia na base Yahoo – consulta 10:

Usuário P10

Otimista 0,58

Pessimista 0,20