Estudo Comparativo de Estruturas de Indexação para Recuperaçãoffaria/ia1s2015/class18/cbir_penatti2009.pdf · descritores textuais e descritores de imagens. Publicações Aceitos:

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

Otávio Augusto Bizetto [email protected]

Ricardo da Silva Torres (orientador)[email protected]

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




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]


Descritores

Figura adaptada de [Kherfi2004]


Complexidade extração de características

Coleta de dados

Algoritmo de extração

Base de vetores de

características

OFFLINE

Figura adaptadade [Kherfi2004]


ONLINE

Algoritmo de extração


Complexidade extração de características

Função de distância


Base de vetores de

características

ONLINE


Complexidade função de distância


Base de vetores de

características

1 vetor de características/imagem/

descritor


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


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


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

Estudo TeóricoDescritores de Textura

Bases de imagens Comparações

Maioria Brodatz Com Gabor


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


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


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



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



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


Eficácia:

Descritores de Cor usados na base heterogênea:

BIC

CSD

ACC

Color Bitmap

GCH



Brodatz1776 imagens

111 categorias

todas consultas

Descritores de TexturaLBP

HTD

SASI

CCOM

Unser

QCCH

LAS

SID



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



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



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


Eficácia:

Descritores de Textura usados na base heterogênea:

LAS

CCOM

LBP



Caltech1018677 imagens

101 categorias

1010 consultas

Descritores de FormaEOAC

Spytec





EOAC

Spytec 0,88

EOAC 1,00




EOAC

Spytec 0,91

EOAC 1,00




relação ao EOAC

Spytec 0,06

EOAC 1,00


Eficácia:

Experimentos - ResultadosEficácia - EOAC:

Experimentos - ResultadosEficácia - EOAC:

Descritores de Forma usados na base heterogênea:

Nenhum



Yahoo234.828 images

não classificada

Descritores usados na base YahooBIC

CSD

ACC

Color Bitmap

GCH

LAS

CCOM

LBP



Descritores na base Yahoo


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




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




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


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

16 imagens de consulta


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

Combina-os

Embaralha-os

Exibe-os para o usuário


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



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



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


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



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



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







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



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



Descritor Configuração

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

Spytec 16 coeficientes, L2



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



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



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

Spytec O(n) O(vs) F



Usuário P10

Otimista 0,25

Pessimista 0,04



Usuário P10

Otimista 0,58

Pessimista 0,20

Documents

Estudo Comparativo de Estruturas de Indexação para Recuperaçãoffaria/ia1s2015/class18/cbir_penatti2009.pdf · descritores textuais e descritores de imagens. Publicações Aceitos: