Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Técnicas e Aplicações deRecuperação de Imagens por
Conteúdo
Agma Juci Machado TrainaCaetano Traina Jr.
Grupo de Bases de Dados e ImagensDepartamento de Ciências de ComputaçãoUniversidade de São Paulo - São Carlos
http://www.icmc.usp.br/~caetanohttp://www.icmc.usp.br/~agma
P Introdução
P Motivação
P Imagens e Características
P Organização dos Dados< Indexação de Imagens
P Consultas por Similaridade
P Conclusões
Conteúdo
P Grande volume de dados complexos gerados pelos sistemascomputacionais atuais< Imagens, vídeo, áudio, hipertexto, séries temporais, cadeias de DNA
P Utilizá-los de modo proveitoso e recuperá-loss de modo rápido e natural é uma das necessidades para efetuar a análise de taisdados,
P Dados Complexos são naturalmente comparados por semelhança(similaridade), diferentemente dos dados simples.< 35 < 50< ‘Piracicaba’ < ‘São Carlos’
Introdução
?
P Recuperação de imagens baseada em conteúdo– Content-Based Image Retrieval - CBIR
< Recuperação baseada em: conteúdo X descrição– “Retorne a imagem de João da Silva”– “Retorne a imagem de João da Silva obtida em 25/09/2004 ” – “Retorne as 5 imagens mais semelhantes à imagem de João da Silva”
P Busca por similaridade– Similarity search
< Duas imagens são semelhantes, nunca iguais (se for igual é a mesma!)
< O que é similaridade ?– Critérios de similaridade– Características a serem comparadas– Métricas para comparação
Coleções de imagens (Tamanho Crescente)
Introdução
IntroduçãoRecuperação por Conteúdo vs. Recuperação por Descrição
Descrições feitaspelos especialistas
Processo nãoautomático
Descrições obtidasdas diretamentedas imagens
Processo automáticoou semi-automático
ImagensDescriçõesFeatures
Consultas convencionais: chaves textuaisConsultas por conteúdo: chaves imagens
P Processamento de coleções de imagens– Cada imagem é analisada individualmente utilizando técnicas e algoritmos
processamento de imagens;
< Organização da coleção para recuperação rápida;< Pré-processamento de cada imagem durante a armazenagem;< Recuperação eficiente durante as consultas.
Coleções de imagens
Motivação
Módulos
Recuperação de Imagens por Conteúdo (CBIR)
Motor deRecuperação
Extratores deCaracterísticas
Armazenamento eMétodos de Acesso
Métodos deInteração (GUI)
Cálculos de Similaridade (funções de distância)
SimilaridadeIntuição (1)
Intuição (2)
Similaridade
P Similaridade entre dados multimídia é medida sobrecaracterísticas extraídas dos mesmos< histogramas, momentos invariantes, transformadas (Fourier, Wavelets,
etc), análise das componentes principais (PCA), assinaturas...
P Procura-se extrair as informações que o analista humano utilizano processo de comparação entre esses dados< Imagens: cores, forma, textura, relacionamento entre objetos< Vídeo: diferença entre frames< Áudio: frequência e altura do comprimento de onda
P Essas características são utilizadas para a comparação entre osdados multimídia.
Similaridade entre dados Complexos
P Introdução
P Motivação
P Imagens e Características
P Organização dos Dados< Indexação de Imagens
P Consultas por Similaridade
P Conclusões
Conteúdo
Exemplo: imagens
Extração de Características
ClassificaçãoExtração deCaracterísticasSegmentação
Vetor deCaracterísticas
ImagemObjeto
ImagemOriginal
x1
x2
...xn
“Círculo”
“Elipse”
Tipo deObjeto
P Características de imagens:< Valores Numéricos ou categóricos que descrevem as características das
imagens< Características comumente usadas: cor, textura, forma e relacionamento
entre objetos da imagem
P DESAFIO 1 - a partir da imagem original, definir um vetor decaracterísticas que:< descreva com fidelidade o conteúdo semântico da mesma,< aceite a aplicação de uma medida de similaridade (função de distância),< Possa ser usada em uma estrutura de indexação,
P DESAFIO 2 - Manter um número pequeno de características:< “Maldição da Alta Dimensionalidade”!
Desafio
Extração de Características
P Existe um relacionamento forte entre< Características das Imagens e Função de Distância
P Especialista no domínio deve indicar/especificar/propor Funçãode Distância mais apropriada para o tipo de imagens
P Funções de distância usuais - Família Lp
Comparação por Similaridade
Funções de distância
P Dados 2 vetores (tuplas) x=(x1, x2,..., xn) e y=(y1, y2,..., yn)
Distância Euclideana: < L2= (j|xi - yi|
2)1/2
Medir dissimilaridade
Funções de distância
O que fazer quando não há dimensãodefinida para o conjunto de dados?
x=(x1, x2,..., xn) e y=(y1, y2,..., yk) com k�n
Conceitos Relacionados
Níveis de Abstração -Semântico vs. Sintático
Nível 1: Pixels da imagem
Nível 2: Procurar bordas,linhas, curvas e regiões
Nível 3 - Combinar einterpretar os atributos donível 2
Nível 4: Mapeamento humano,relacionamento entre os objetos donível 3
Sintático
Semântico
(Computador)
(Especialista)
P Gap semântico: perda da informação real da imagem , que não épreservada/capturada pelas características (algoritmos deProcessamento de Imagens) e a expectativa de informação totaldesejada pelo usuário.< Principal problema referente a aceitação de CBIR
P Utilizar CBIR em aplicações mais específicas!< Recuperação segundo determinado aspecto (somente cor, ou textura, ou
forma).
Considerações
Gap Semântico
P Medida de eficácia do Método de Recuperação.< Dado um conjunto de dados (sobre o qual serão feitas as consultas), define-se:< TR - nº Total de objetos Relevantes (nº de imagens pertencentes a mesma classe
que a imagem de consulta)
< TRO - nº Total de objetos Relevantes recuperados na consulta< TO - nº Total de objetos recuperados na consulta (independente da classe a
que pertencem)
Precisão e Revocação
Análise dos Resultados
TR -ObjetosRelevantes
TO -Total deObjetos Obtidos
TRO - TotalRelevantes Obtidos
Análise dos ResultadosPrecisão e Revocação
TR -ObjetosRelevantes
TO -Total deObjetos Obtidos
TRO - TotalRelevantes Obtidos
P Precisão: indica a proporção de objetos relevantes emrelação ao total de objetos recuperados Precision= TRO
TO
P Revocação: indica a proporção de objetos relevantesrecuperados em relação ao total de objetos relevantes
Recall = TRO TR
Exemplo
Precisão e Revocação
Conceitos Relacionados
Exemplo
Extração de Características - Histograma
Extração de Características - Histograma
Exemplo: características de baixo nível de imagens
Histogramas
CorHistogramas
- rápido de obter- baixo poder discriminativo
mais de uma imagempode corresponder aomesmo histograma!
(a)
(d)(c)
(b) (e)
Cores
Histograma de cores
Solução: usar mais de umacaracterística
Exemplo: características de baixo nível de imagens
Extratores de características
Textura
Padrão visual em que elementos gráficos semelhantes se
repetem em densidade variável.
Padrão visual em que elementos gráficos semelhantes se
repetem em densidade variável.
Exemplo: características de baixo nível de imagens
Extratores de Características
FormaLocaliza objetos usando algoritmos de detecção de bordasLocaliza objetos usando algoritmos de detecção de bordas
Processamento pesadoProcessamento pesado
Requer o pré-processamento da imagem e redução
de ruído antes da segmentação
Requer o pré-processamento da imagem e redução
de ruído antes da segmentação
originaloriginal segmentadasegmentada
Processo de seleção de características
Extratores de características
A comparação de imagens é custosa e toma tempoUma filtragem inicial pode reduzir o número de comparações
Histogramas L primeiro passo
Textura e forma: operações custosas, que depende do domínio da
aplicação L passos posteriores
P Características de baixo nível: histogramas de intensidade (niveiscinza);
P Vetores de características: aproximação linear por partes dohistograma;
P Extração de características: extração do histograma,normalização, aproximação linear por partes;
P Função de Distância: diferença da integral entre as aproximaçõeslineares por partes.
Um exemplo: histogramas métricos para exames medicos
Extração de características
Um exemplo: histogramas metricos para exames medicos
Extração de características
Em histogramas tradicionais, existe um bin para cada cor (ou intensidadede cinza)
Todos os ‘bins’ têm a mesma largura
Extração de características
0,25
0,20
0,15
0,1
0,05
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Transforma ‘bins’ em ‘buckets’
Aproximação do histograma
0,25
0,20
0,15
0,1
0,05
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
P Invariante à rotação, translação e escala;
P Invariante à mudanças lineares de brilho;
P Explora as correlações existentes entre bins vizinhos (de maneiraespecífica, imagem por imagem).
Propriedades do histograma métrico
P A distância MD( ) entre dois histogramas métricos é a área nãosobreposta entre ambos.
Definindo a função de distância métrica forpara Histogramas Métricos
Buckets
Histogramamétrico A
Histogramamétrico B
Tempo para responder a 50 consultas sobre dados indexados em uma Slim-tree
Histogramas métricos melhoram a resposta aconsultas
0
0.5
1
1.5
2
2.5
3
3.5
4
0 2 4 6 8 10 12 14 16
Total time for answering 50 queries MRHead500
OriginalsMetrics
k=DatabaseP ercentage
0
50
100
150
200
250
300
350
400
450
500
0 2 4 6 8 10 12 14 16
Total time for answering 50 queries:
MRVarious4247
OriginalsMetrics
k=DatabaseP ercentage
P Três abordagens principais:< Estatística: distribuição dos níveis de cor dos pixels e seu inter-
relacionamento< Estrutural: arranjo espacial de primitivas regulares< Espectral: aplicação e análise de transformadas
P Abordagem estatística:< mais utilizada< bons resultados< custo computacional reduzido
Característica: Textura
P Basicamente um algoritmo de otimização
P Objetivo é “minimizar o número esperado de pixels classificadoserradamente”
P Métodos Estocásticos
Permite a representação de comportamento aleatório das texturas< (Presente na maior parte das imagens)
P Demanda um número pequeno de parâmetros)
Métodos Estocásticos
Característica: Textura
EM/MPM
Cadeias Aleatórias de Markov
EM/MPM
Imagem a serSegmentada
.
..
21
3
L
.
..
21
3
L
.
..
21
3
L
Número declasses
Mapa declassificação(iniciala leatório)
.
..
21
3
L
(m1, s21)
(m3, s23)
(mL, s2L)
.
..
21
3
L
.
..
21
3
L
(m1, s21)
(m3, s23)
(mL, s2L)
(m1, s21)
(m3, s23)
(mL, s2L)
Features decada classe(inicializadasaleatoriamente)
NovaClassificaçãoé realizada
Algoritmo MPM
Features dasClasses sãoatualizadas
Algoritmo EM
Segmentação Automática
Característica: Textura
2
background
Classes ( 2)
1
2
34
5
Classes ( 5)
1
background
P Da imagem segmentada por textura, obtem-se característicasrelevantes:< Centro de massa< Tamanho< Dispersão< Média< Variância< Dimensão Fractal
Característica: Textura
2
34
5
Classes (5)
1
5 regions
Consultando os Vizinhos mais Próximos
27 Imagens testetipo
Consultando os Vizinhos mais Próximos
36 Imagens testetipo
Consultando os Vizinhos mais Próximos
9 Imagens teste tipo
Análise por Precisão e Revocação
P Indica o inter-relacionamento entre um pixel e seus vizinhos,considerando < direção (2) de posicionamento do vizinho< Distância (d) de posicionamento do vizinho
P O tamanho da matriz é dado pelo número de níves de intensidadenos quais a imagem é analisada< Ex. Imagem de 256x256 pixels com 16 níveis de cinza.< Matrizes de co-ocorrência serão de 16x16 elementos. Uma matriz para
cada direção e distância
P São extraídas medidas da matriz de co-ocorrência, queconstituirão as features das imagens.
Matrizes de Co-ocorrência
Característica: Textura
P A literatura traz inúmeros métodos de extração de característicasutilizando a forma de objetos presentes na imagem< Momentos de Zernike, Métodos baseados em curvatura, coeficientes de
Fourier, etc.< Dependem fortemente do domínio das imagens.< Os descritores de forma podem ser compostos no vetor de características
das imagens.
Característica: Forma
P Introdução
P Motivação
P Imagens e Características
P Organização dos Dados< Indexação de Imagens
P Consultas por Similaridade
P Conclusões
Conteúdo
P Organizar informação para acesso eficiente remete-nos aoconceito de ordenação,
P Algoritmos de ordenação de dados (vetores):< Classifição direta, classificação binária,‘bubble’-sort, shellsort, quicksort,
... Inserção de novos dados demanda movimentação dos itens
P Árvores:< Heapsort, árvore binária, ...
Estabelecendo ordem na informação
Organização de Dados
Ordenação utilizando Árvore Binária
Dados Simples
150, 100, 20, 10, 21, 130, 195, 170, 200
100
150
20
10 21
195
130 170 200
Percorrendo a árvore em in-ordem:10, 20, 21, 100, 130, 150, 170, 195, 200
P Por que utilizar árvores?< Não há necessidade de relocação entre os dados para novas inserções< Diminui o número de acessos aos dados para consultas/inserções
– Menor número de acessos a disco se a árvore estiver balanceada
< Para n items de dados– Média de log(n) (altura da árvore) acessos para encontrar um item na árvore
Árvores para Indexação
Ordenação utilizando Árvore Binária
Estruturas de Dados
10, 20, 21,100, 130, 150, 170, 195, 200
100
150
20
10
21
195
130
170
200
Árvore degenerada # busca sequencial
P Árvores B e sua variante (B+):< estão presentes em todos os gerenciadores de banco de dados comerciais< Oracle, Sybase, etc.
Árvore Balanceada: Árvore B - B-tree
Estruturas de Dados
493 506 511451 472 406 412380 382
395 430 480
P Árvores B e sua variantes (B+ todos os items estão nas folhas) < Não há sobreposição entre as chaves de acesso< Para um conjunto de dados com n items, o acesso a qualquer um deles é
O(logk(n)) onde k=número de entradas por nó # A árvore é mantida
balanceada< Permite a organização de dados em memória secundária
– Os nós da árvore armazenam um número de items de dados adequado aocupar um registro em disco.
Árvore B
Estruturas de Dados
P No princípio os dados eram números e textos...
P E evoluíram para armazenar dados espaciais...< Desenvolvimento dos Sistemas de Informação Geográficos (SIGs)
– Mapas de cidades, estados e regiões passaram a integrar o universo de dados. – Consultas por vizinhança e região são solicitadas
– “Quais são as ruas que interceptam a Avenida Copacabana no seu primeiroquilômetro?
– “Quais são os estados limítrofes ao norte de São Paulo?”
Evolução histórica - dados e estruturas
Exemplos de consultas
Dados Espaciais
Point Query Window Query
Region Query Adjacency Query
Dados Espaciais
R-tree
Um objeto espacialR8
R9
R10
R11
R12
R13
R14
R15
R16
R17
R18
R19
R3 R5
R4R1
R2
R6
R7
Legenda:Regiões representadas no primeiro nívelRegiões representadas no segundo nívelRegiões representadas no terceiro nível
R17 R18 R19R13 R14 R15 R16R11 R12R8 R9 R10
R3 R4 R5 R6 R7
R1 R2
Ponteiros para os atributos não espaciais dos objetos
P Chaves podem colidir
P Atributos das relações podem ser separados em espaciais x não-espaciais
P Informação espacial:< Regiões no espaço: Método de acesso Espacial - SAM< Pontos no espaço: Método de acesso Pontual - PAM
Dados Espaciais
ISAM
IPAM
(x,y)<(xi,yi), (xf,yf)>
P Relações com k-atributos podem ser associadas a pontos numespaço k-dimensional
P Exemplo: Salário={Nome, salário, tempo_serviço}
Espaço k-dimensional
Dados Multidimensinais
Tempo de serviço
P Exemplo: Salário={Nome, salário, tempo_serviço, idade}
Espaço k-dimensional
Dados Multidimensinais
Tempo de serviço
P Exemplo: Salário={Nome, salário, tempo_serviço, idade, num_empregos_anteriores, horas_extra, ....}
Espaço k-dimensional
Dados Multidimensinais
Tempo de serviço
Famílias de Estruturas Espaciais
[Gaede_98]
P No princípio os dados eram números e textos...
P Evoluíram para armazenar dados espaciais...
P E daí para dados multimídia !
dados e estruturas
Evolução histórica
P Introdução
P Motivação
P Imagens e Características
P Organização dos Dados
P Consultas por Similaridade
P Conclusões
Conteúdo
P Dados complexos e usualmente volumosos< Imagens< Áudio< Vídeo< Séries temporais< Dados genéticos (cadeias de DNA)< Impressões digitais
Evolução dos equipamentos computacionais
Dados multimídia
OscilogramaDeslocamento
Tempo
P Para esses dados não há relação de ordem < Dadas duas imagens, qual é a “menor” entre elas?
P Porém, é possível explicitar o quanto são semelhantes (oudiferentes).
P É preciso definir uma função que indique a distância entre asimagens< Função distância " dissimilaridade entre as imagens (ou qualquer dado multimídia)
Dados multimídia
Indexação
< > ?
P Base de imagens com faces de pessoas:< Ex. “Encontre as faces que são parecidas com a do Cid Moreira”
P Base de imagens médicas< Ex. “Dado o exame de Raio-X do paciente J. Silva, encontre os 5 exames
mais parecidos com o exame original”< Ex. “Encontre todos os exames que diferem em até 10 unidades do exame
original indicado”
Exemplos
P Existem dois tipos fundamentais de consultas por similaridade:< Ambas baseadas em um objeto de referência (centro da consulta)
P Consultas por vizinhança (ou k-Nearest Neighbors):Dado um valor inteiro k, obtenha os k elementos do conjunto dedados que são os mais similares ao objeto central da consulta.
P Consulta por abrangência (ou Range queries):Dado um grau de similaridade (raio), obtenha todos os objetos noconjunto de dados que sejam similares ao objeto central daconsulta até esse grau dado.
Consultas por similaridade fundamentais
Em uma base de imagens:
“Encontre as 3 imagens mais similares à imagem do Raio-X de João Silva”
Consultas por vizinhança
Consultas por similaridade fundamentais
Em uma base de imagens:
“Encontre as imagens que diferem em até rq unidades da imagem do Raio-Xde João Silva”
Consultas por Abrangência
Consultas por similaridade fundamentais
rq
P Espaço métrico é um par: M=(O,d)< Onde, O é o domínio de característica de objetos d é uma distância métrica.
P Propriedades da distância d : • simetria: d(x,y) = d(y,x); • não-negatividade: 0 < d(x,y) < 4 , x �y e d(x,x) = 0 •desigualdade triangular: d(x,y) # d(x,z) + d(z,y)
Conceitos Básicos
Espaços Métricos
x
z
y
P Não há atributos geométricos ou de posição< formas e posições (sul, norte, etc.)
P Mesmo para dados espaciais, diferentes funções distânciadefinem formatos diferentes de nós. Por exemplo:
Conceitos básicos
Espaços Métricos
L2=Euclidian
r L1=Manhatan
L0=LInfinity
P Considere o conjunto de palavras de um dicionário
P Distância LEdit = mínima contagem do número de caracteresinseridos, removidos ou substituídos para transformar umapalavra em outra< Ledit(“casa”, “cada”)= 1< Ledit(“queijo”, “quero”)= 2
P Qual é o formato do nó para a função de distância entre palavrasLEdit ???
P
Exemplos
Espaços Métricos
Slim-tree
Estrutura de Acesso Métrica
Respondendo a uma consulta pontual
Consultando uma Slim-tree
U
#
>X
X
Respondendo a uma consulta pontual
Consultando uma Slim-tree
X
U
U
Respondendo a uma consulta por abrangência
Consultando uma Slim-tree
RqRq
Região 3Região 2 Região 1
Poda se:d(sRep, sq)+rq < d(sRep, si) (Região 1)d(sRep, sq)- rq > d(sRep, si) (Região 3)
U
X
Construindo uma Slim-tree
A
BC
D
E FG
HI
J
KL
MN
OP
Q
Construindo uma Slim-tree
A
BC
D
E FG
HI
J
KL
MN
OP
Q
H
GA
A
BJI
B
K L GH M N Q O PIJE A D F CB
LEK
OC P
M D
N
F Q
BJI
E D F C
H
GA
M D
NBJ
IBJ
IBJ
I
F Q
A
LEK
BJI
H
GA
M D
N
B
OC P
F Q
CRaiz
Nósintermediários
Folhas
P Executa-se uma navegação em profundidade (consulta pontual)para decidir em qual nó ele deve ser inserido, usando:< Algoritmo Choose-subtree< Algoritmo Split-node< Quebra de nós Bottom-up (assegura o balanceamento da árvore)
Inserindo um objeto
Construindo uma Slim-tree
Inserindo um objeto
Construindo uma Slim-tree
Inserindo um objeto: ChooseSubTree
Construindo uma Slim-tree
Choose SubTree :
Random
minDist
minOccup
n=19n=14
Inserindo um objeto: SplitNode
Construindo uma Slim-tree
Inserindo um objeto: SplitNode
Construindo uma Slim-tree
Dois passos: - Escolhe 2 objetos para serem o
centro de dois nós
- Distribui os objetos restantesentre os 2 novos nós
Inserindo um objeto: SplitNode
Construindo uma Slim-tree
Algoritmos de Splitting:
# Random Select + Minimum Radius-O©)
# Minimum R1+R2 (minMax) -O(C3)
R1
R2
# Cluster based: Minimal SpanningTree (MST) - O(C2 log C)
Inserindo um objeto: SplitNode usando o MST
Construindo uma Slim-tree
Inserindo um objeto: SplitNode usando o MST
Construindo uma Slim-tree
P Os conceitos de area”, “volume”, etc. não se aplicam,
P Então como medir a sobreposição ?
Em espaços métricos:
Redução da sobreposição entre nós
( ‘Contar’ o número de objetos naintersecção de dois nós (ou em duassub-árvores). Isto é, contar quantosobjetos são cobertos em cada nó pormais de um nó <representante, raio>.
Dois nós
Redução da sobreposição entre nós
n=14 n=13
10 objetos naintersecção
Overlap=10
14+13
Fat-factor
Redução da sobreposição entre nós
Definição: Seja T uma árvore métrica com alturaH e M nós. Seja N o número de objetosindexados. Então, o fat-factor dessa árvore é:
Ic - # nós acessados para responder a uma consulta pontual
0 #fat(T) #10 para a árvore ideal1 para a pior árvore possível
Fat-factor
Redução da sobreposição entre nós
n=6 n=7fat(T)=0
n=6 n=7fat(T)=0
n=6 n=7 fat(T)=0.15
n=6
n=7
fat(T)=1.0
Algoritmo Slim-down
Redução da sobreposição entre nós
Exemplo: Triângulo de Sierpinsky
Redução da sobreposição entre nós
Sierpinsky - N=9,841
-2000
0
2000
4000
6000
8000
10000
12000
-2000 0 2000 4000 6000 8000 10000 12000
Exemplo: Triângulo de Sierpinsky - Antes e Depois
Redução da sobreposição entre nós
Fat-factor=0.04 Fat-factor=0.02
-2000
0
2000
4000
6000
8000
10000
12000
-2000 0 2000 4000 6000 8000 10000 12000
-2000
0
2000
4000
6000
8000
10000
12000
-2000 0 2000 4000 6000 8000 10000 12000
Conjuntos de Dados para testes
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Uniform2D - N=10,000 Sierpinsky - N=9,841 MGCounty - N=15,559
. . .harmonicharmonicaharmoniousharmonyharnessHaroldharpharpoon. . .
EnglishWords - N=25,143
d1
d3
d2d4d6d5
FaceIT - N =1,056
0 1 15
Eigenfaces - N=11,900
Slim-tree vs M-treeChoose SubTree : minOccup
Experimentos: Query performance # Acessos a disco (em média) vs Raio : range queries
1
10
100
1000
0.0001 0.001 0.01 0.1 1
Sierpinsky dataset
radius1
10
100
1000
0.0001 0.001 0.01 0.1 1
MGCounty dataset
radius
10
100
1000
0.0001 0.001 0.01 0.1 1
Eigenfaces dataset
radius
1
10
100
1000
0.0001 0.001 0.01 0.1 1
Uniform10k dataset
radius
10
100
1000
0.01 0.1 1
FaceIt dataset
radius
100
1000
0 5 10 15 20 25
EnglishWords dataset
radius
Slim-Tree (min-max)
M-tree (min-max)
Slim-tree : # acessos Disco (em média) vs raio -Range queries
ExperimentosAlgoritmos de Splitting: minMax vs MST
1
10
100
1000
0.0001 0.001 0.01 0.1 1
Slim-tree, Sierpinsky dataset
radius
10
100
0.0001 0.001 0.01 0.1 1
Slim-tree, FaceIt dataset
radius
(a) (b)
minMaxMST
minMax vs MSTSlim-tree : # acessos Disco (em média) vs raio -Range queries
Algorithmo Slim-down
10
100
0.0001 0.001 0.01 0.1 1
Slim-tree, FaceIt dataset
radius
MST (without slimming down)MST (with slimming down)
10
100
0.0001 0.001 0.01 0.1 1
Slim-tree, FaceIt dataset
radius
minMax (without slimming down)MinMax (with slimming down)
Melhoria de até 70% para range queries
Algoritmo Slim-down
100
1000
0 5 10 15 20 25
EnglishWordsd ataset
radii
1
10
100
1000
0.0001 0.001 0.01 0.1 1
Eigenfacesd ataset
radii
10
100
1000
0.01 0.1 1
FaceItd ataset
radii
1
10
100
1000
0.0001 0.001 0.01 0.1 1
Uniform10kd ataset
radii
M-tree (min-max)
Slim-Tree (min-max sem Slim-down)Slim-Tree (min-max com Slimming down)
Tempo (segundos)
minMax e MST
build range queries slim-down fat-factor
0
20
40
60
80
100
120
Sierpinsky
build range queries slim-down fat-factor
0
20
40
60
80
100
Uniform
build range queries slim-down fat-factor
0
50
100
150
200
MGCounty
build range queries slim-down fat-factor
0
500
1000
1500
2000
English Words
build range queries slim-down fat-factor
0
10
20
30
40
50
60
70
Eigenfaces
build range queries slim-down fat-factor
0
0.1
0.2
0.3
0.4
0.5
FaceIt©
# minMax #MST
P Até 60 vezes mais rápida para inserção (mantém mesmodesempenho para consultas)
P Até 70% mais rapidez para responder consultas com o algoritmo‘Slim-down’
P ‘Fat factor’, permite quantificar a sobreposição de nós emestruturas métricas.
Estrutura de indexação Slim-tree
Resultados dos experimentos
P Auxiliar a entender a organização da informação na estrutura
P Localizar os aglomerados (clusters)
P Localizar os elementos de exceção (outliers)
P Permitir visualizar a distribuição de distâncias entre os objetosdo conjunto de dados< Importante para dados não dimensionais!
P Algoritmo base para executar a visualização< FastMap proposto por Christos Faloutsos e David LinHttp://www.cs.cmu.edu/~christos
Visualizando os Dados indexados
Histogramas de imagens (500 objetos)
Exemplos
Histogramas de imagens (500 objetos)
Exemplos
Objects
Leaf nodes
Index nodes
Conjunto de palavras: Dicionário língua Inglesa
Exemplos
b)a)
P Introdução
P Motivação
P Imagens e Características
P Organização dos Dados
P Consultas por Similaridade
P Conclusões
Conteúdo
P Indexação e recuperação de imagens por conteúdo é um processoque demanda interação de especialistas de várias áreas daComputação:< Bases de Dados, Processamento de Imagens, Reconhecimento de
Padrões, Inteligência Artificial, Interação Usuário-Computador
P Especialista no domínio de Análise de Imagens– Área Médica (radiologistas)
P Combinação entre CBIR e técnicas baseadas em descrições(atlas) auxiliam a redução do gap semântico
P Área de pesquisa de ponta L Muito a ser pesquisado
Conclusões
P H. Müller, N. Michoux, D. Bandon, and A. Geissbuhler, "A Review ofContent-based Image Retrieval Systems in Medical Applications––ClinicalBenefits and Future Directions," International Journal of MedicalInformatics, Vol. 73, No. 1, February 2004, pp. 1-23.
P K. Vu, K. A. Hua, and W. Tavanapong, "Image Retrieval Based on Regionsof Interest," IEEE Transactions on Knowledge and Data Engineering(TKDE), Vol. 15, No. 4, July/August 2003, pp. 1045-1049.
P A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain,"Content-Based Image Retrieval at the End of the Early Years," IEEETransactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 12,December 2000, pp. 1349-1380.
P T. Tuytelaars and L. J. V. Gool, "Content-based Image Retrieval Based onLocal Affinely Invariant Regions," Proc. Third International Conference onVisual Information and Information Systems -VISUAL'99, Amsterdam, TheNetherlands, June 2-4, 1999, pp. 493-500.
P A. Kak and C. Pavlopoulou, "Content-based image retrieval from largemedical databases," Proc. First International Symposium on 3D DataProcessing Visualization and Transmission, June 19-21 2002, pp. 138 -147.
Referências
Agma Traina Caetano Traina Jr.
http://www.icmc.usp.br/~agma
/~caetano