uma proposta de melhoria no processo de recuperação de imagens

UMA PROPOSTA DE MELHORIA NO PROCESSO DE RECUPERAÇÃO DE
IMAGENS DIGITAIS COM BASE NA DISTRIBUIÇÃO DE
CARACTERÍSTICAS DE BAIXO NÍVEL EM SUAS REGIÕES UTILIZANDO
ÍNDICE INVERTIDO
Patrícia Aparecida Proença1
RESUMO
Considerando a indexação de características de baixo nível de região de imagens
digitais mapeadas para um índice invertido este trabalho busca melhorias no
desempenho do processamento de consultas e ganho na precisão no conjunto de
imagens recuperadas em grandes bases de dados. O índice invertido, análogo ao
utilizado em recuperação textual, é aqui adaptado para recuperação de imagens
baseado em conteúdo. O conceito de termo da recuperação textual é utilizado no
trabalho como características de regiões de imagens para a indexação.
Experimentos mostram ganho da qualidade usando duas coleções de imagens
digitais.
Palavras-Chaves: Índice Invertido, Recuperação de Imagens, CBIR.
1
INTRODUÇÃO
Nos últimos anos, o crescimento do número de imagens produzidas em meio
digital foi imenso, sendo que o custo de processamento e armazenamento desse
tipo de imagem decresceu consideravelmente. Diante de uma grande quantidade de
imagens, muitas vezes o usuário encontra dificuldades em localizar imagens específicas,
surge então a necessidade crescente por melhores algoritmos de busca, métodos de
indexação e técnicas de classificação de imagens digitais.
1
Professora do Curso de Sistemas de Informação da Faculdade Atenas – Paracatu - MG
Dentre os métodos para facilitar busca de imagens, pode-se citar o método de
indexação das imagens por meio de palavras-chaves que descrevam as imagens [6].
Porém, este método é dispendioso em termos de tempo gasto com as descrições, pois
estas precisam ser inseridas manualmente. Em alguns casos são extraídas
automaticamente por meio de algoritmos complicados, ineficientes e imprecisos em
relação à classificação das imagens, pois a descrição pode ser subjetiva [3].
Outro método muito utilizado é o de busca de imagens baseado no contexto do
documento em que a imagem está inserida, processo utilizado pela máquina de busca
Google [8]. O sistema procura em arquivos de hipertexto com imagens que possuam a
palavra chave. O problema deste método é que as imagens inseridas nos hipertextos
não necessariamente correspondam ao texto.
Atualmente tem crescido a busca de imagens pelo próprio conteúdo denominado
CBIR (Recuperação de Imagens Baseada no Conteúdo). O objetivo desse método é
encontrar imagens relevantes conforme a necessidade do usuário, usando de
características visuais extraídas automaticamente das imagens. Nesse método, diferente
dos anteriores, a consulta é feita por meio de uma imagem exemplo e não um
termo ou palavra-chave.
O conjunto de características extraídas de uma imagem varia em número e
especificidade dependendo do domínio de aplicação envolvido. Para melhorar o
desempenho da recuperação, indexação multidimensional é aplicada [16].
Atualmente, diferentes estruturas vêm sendo propostas, mas estruturas da
família R-tree são mais utilizadas em CBIR [16] e [15]. Por exemplo, Titan aplica a Rtree[4], QBIC utiliza a R*-tree, o sistema SRSI é baseado na SR-tree[11] e [5] com R*tree e M-tree.
Com o objetivo de melhorar significativamente o desempenho e o tempo de
recuperação de imagens por conteúdo em grandes coleções como a Web, sem
perda da precisão, paradigmas e técnicas de recuperação textual têm sido
estudadas para utilização na recuperação de imagens. Em [8] e [9] é apresentado uma
proposta de adaptação do CBIR, para a utilização do paradigma existente no campo de
recuperação de informação textual denominado índice invertido.
O objetivo deste trabalho é estender o trabalho [8] e [9] contribuindo na qualidade
e quantidade dos termos utilizados na indexação por meio das regiões das imagens, e
aplicá-lo dentro do ambiente de recuperação por conteúdo para grandes coleções,
visando não somente o ganho de desempenho no processamento das consultas,
mas também ganho na precisão no conjunto de imagens recuperadas.
O trabalho está estruturado da seguinte forma: na Seção 2 é feita uma
revisão bibliográfica de temas importantes relacionados à recuperação textual e à
recuperação baseada em conteúdo. Na Seção 3, é descrito o sistema de [8] e [9]
e o sistema desenvolvido ao longo deste trabalho. Na Seção 4 são apresentados
os resultados experimentais obtidos. Na Seção 5 apresenta-se as conclusões e trabalhos
futuros.
2 REVISÃO BIBLIOGRÁFICA
2.1 RECUPERAÇÃO DE IMAGENS BASEADA EM CONTEÚDO
As pesquisas na área de Recuperação de Imagens levaram à construção de
sistemas cujas consultas deixaram de ser relativas a textos descritos em algum
momento, e passaram a ser por similaridades existentes entre as imagens. Este
paradigma para recuperação, denominado CBIR, utiliza a descrição do conteúdo
de imagens para indexá-las e manipulá-las [3]. Por meio de algoritmos automáticos de
processamento de imagens, são criados vetores de características que representam
propriedades das imagens. Desta maneira, o sistema pode recuperar imagens
semelhantes à fornecida como exemplo pelo usuário (imagem consulta).
Os atributos visuais mais utilizados na recuperação, como mencionados
anteriormente, são: cor, forma e textura.
A cor é uma das características visuais mais utilizadas na recuperação de imagens
e possui um papel bastante significativo na indexação e recuperação. Isso porque,
segundo [11], o atributo cor proporciona, na tarefa de separação de background, um
processo relativamente robusto, independente do tamanho e orientação da imagem.
A vantagem deste método baseado em conteúdo está na possibilidade de
um processo de recuperação automático, em oposição ao esforço necessário para
classificar ou anotar as imagens nas outras abordagens. Entretanto, a escolha da
imagem de consulta que melhor representa o que o usuário deseja buscar é uma tarefa
difícil, uma vez que o usuário precisa traduzir conceitos (idéias) em características de
baixo nível.
O cálculo da similaridade é uma outra desvantagem do CBIR. As imagens
são representadas como vetores de características em um espaço vetorial n-dimensional
e as semelhanças estão associadas à menor distância Euclidiana entre a imagem
de consulta com todas as imagens do banco de dados. Basicamente essa
recuperação é demasiadamente cara e lenta para grandes coleções de imagens como a
Web.
O projeto QBIC (Query by Image Content) da IBM [10], o VisualSEEK [14] e
o ImageRover [13] realizam buscas por conteúdo. Outros exemplos incluem o
PicHunter [15] e o Blobworld [2].
2.2 RECUPERAÇÃO TEXTUAL
A primeira solução sistemática para o problema de recuperação de
informação em uma grande coleção de dados foi desenvolvida há cerca de 4000
anos, por bibliotecários, que passaram a organizar os livros catalogando-os por
autor e título Uma das soluções que surgiram no século XVI, a construção dos índices,
vêm sendo utilizada atualmente. Contudo agora são construídos automaticamente.
Existem várias estruturas de índice, porém a mais empregada é a estrutura de
arquivos invertidos [12].
Os arquivos invertidos são estruturas de dados que permitem encontrar de
forma rápida quais documentos de uma coleção possuem um dado termo, [12].
Essa estrutura é composta por dois elementos: (i) o vocabulário - que consiste no
conjunto de todas as palavras diferentes que ocorrem na coleção; (ii) e as listas
invertidas – que são listas contendo todos os documentos da coleção nos quais surge um
dado termo. A construção e a manutenção dos arquivos invertidos correspondem a
uma etapa de pré-processamento que demanda alto custo computacional. Porém esses
custos são amortizados, à medida que as consultas são submetidas ao sistema.
As listas invertidas podem conter, além dos documentos em que ocorre o
termo, outras informações que sejam úteis à máquina de busca, como por
exemplo, a freqüência do termo no documento. Esse valor é chamado na literatura
[1] de Term-Frequency (tf).
Um arquivo invertido é construído por meio do processamento de cada
documento da coleção. Este processamento é chamado indexação e é responsável por
identificar todos os termos existentes na coleção, inserindo-os no vocabulário
juntamente com o ponteiro para a lista invertida, [12].
Quando uma consulta contendo mais de um termo é submetida a um
sistema de recuperação de informação, o processo de busca é responsável por
localizar a lista invertida para cada termo da consulta. Dependendo dos
operadores booleanos utilizados na formulação da consulta, a resposta será gerada
mediante a interseção ou união dos conjuntos de documentos existentes em cada lista,
sendo esse um processo rápido.
Devido a esse rápido tempo de resposta obtido na técnica de busca textual,
estudos vêm sendo feitos para a utilização da técnica textual em recuperação de
imagens baseada em conteúdo, pois esta por sua vez, utilizando similaridade
baseada na distância euclidiana, percorre todo o banco de imagens para o calculo da
similaridade, o que demasia um grande custo com processamento e tempo de resposta.
3 PROPOSTA DE CBIR BASEADO EM ÍNDICE E REGIÕES
3.1 CBIR - ÍNDICE
Em [8] e [9] é proposto uma adaptação do CBIR, para que possa ser
utilizado o paradigma existente no campo de recuperação de informação textual
denominado índice invertido. Segundo [1] o uso do índice invertido em
recuperação textual tem resultado em ganho na velocidade de recuperação de
documentos sem perda de qualidade na recuperação.
Em [8] é apresentado um sistema de recuperação baseado em conteúdo, que
utiliza técnicas textuais para indexação e cálculo da similaridade em recuperação
de imagens. Os termos utilizados na recuperação textual são palavras presentes
nos arquivos textuais. Na recuperação por conteúdo um termo é definido como sendo
uma faixa de valores extraídos da imagem com base em característica de baixo
nível, especificamente momentos de cor. Este caracteriza as imagens em termos
da distribuição das cores nos pixels da imagem. São normalmente dados por três
medidas estatísticas: média, desvio padrão e obliqüidade. Os momentos de cor
podem ser derivados do espaço de cor HSV correspondendo aos canais matiz,
saturação e intensidade.
Em resumo, em [8] as imagens foram convertidas do espaço de cor RGB
para o espaço de cor HSV. Então, foram calculados os três momentos acima para cada
canal H, S e V. Com isto, o vetor de característica da imagem tem nove
posições distribuídas conforme Tabela 1. O sistema indexa as imagens com os
valores encontrados para cada canal de cor HSV e calcula a similaridade baseada no
cosseno entre os vetores. Essa abordagem possibilitou melhoria no desempenho
do processamento
das
consultas
sem
perda
significativa
na
qualidade
da
recuperação quando comparada com a busca por distância euclidiana.
Tabela 1 – Descrição do vetor de característica resultante da extração de
característica da imagem usando os três momentos de cor do espaço HSV, [8].
3.2 SISTEMA CBIR-ÍNDICE-PARTICIONADO
A partir do sistema CBIR-Índice, descrito na seção 3.1, foi implementado um
sistema que particiona as imagens em regiões e atribui os termos da Tabela 1 a
cada região das imagens, construindo um vetor contendo todos os termos encontrados
em todas as regiões
obtidas.
Pois,
segundo
[3],
a
quantidade
de
termos
relacionados às imagens contribuem na precisão da recuperação, pois podem
descrever de forma mais completa o conteúdo de uma imagem.
Afim de melhor expressar o objetivo do trabalho proposto, considere o
esquema da Figura 1. Utilizando o sitema CBIR-Índice, o vetor de termos da
imagem exemplo seria formado conforme a Fig. 2. Com a metodologia proposta
neste trabalho, após particionada a imagem exemplo em duas partes, foram obtidas
duas regiões, ilustradas na Fig. 3. O particionamento utilizado no trabalho consiste em
dividir as imagens em partes de tamanhos iguais. Após foi aplicada a proposta de
[8] em cada região e os vetores de cada região foram juntados, obtendo o vetor
ilustrado na Fig. 3.
4 RESULTADOS EXPERIMENTAIS
As coleções utilizadas nos experimentos foram a BD-160 e a Corel-1000.
Primeiramente foi utilizada a base de treinamento, BD-160. Posteriormente foi
realizado outros experimentos em uma coleção de teste, Corel-1000.
A primeira é um subconjunto da segunda, ambas contendo imagens com resolução
256x384 pixels. As coleções são compostas por categorias, ambas com 10 categorias
(África, Praia, Edifício, Ônibus, Dinossauro, Elefante, Flor, Comida, Cavalo e
Montanha), sendo a BD-160 com 16 imagens em cada categoria e a Corel-1000
contendo 100 imagens por categoria.
No trabalho foram considerados quatro tamanhos diferentes das partições. A
primeira, as imagens foram particionadas em duas partes de tamanhos iguais, a
segunda em quatro partes, a terceira em oito e a quarta em desesseis partes.
Para avaliarmos a qualidade da recuperação utilizaremos à medida de desempenho
Precisão (P). A medida consiste na consiste na fração entre o número de
imagens relevantes recuperadas, sobre o número total de imagens recuperadas.
Para calcular a medida da precisão baseou-se em uma estatística encontrada
em [7]. Foi constatado que os usuários navegam na grande maioria das vezes
até a terceira página de resultados. Assim, calculou-se a Precisão em quatro posições
(P0, P5, P10 e P20). Onde P0, significa calcular a precisão na posição do
ranking onde encontra a primeira imagem relevante, com exceção da imagem de
consulta. P5 é o cálculo da precisão na quinta posição do ranking, analogamente
P10 e P20 são a décima e vigésima respectivamente.
Uma imagem da coleção é considera relevante à imagem de consulta se
ambas pertencerem a mesma classe. Esta definição de relevância por classe, foi
adotada, a fim de evitar um dos maiores problemas na análise de resultados em
CBIR, a subjetividade humana. Pois considera-se que as imagens em ambas as coleções
foram corretamente classificadas.
As tabelas abaixo mostram os valores encontrados das precisões P0, P5, P10 e
P20 do sistema CBIR-Índice e CBIR-Índice-Particionado, relativo a média de 8
consultas de cada classe, juntamente com o valor médio da precisão de 80 consultas da
coleção.
Para avaliar o ganho obtido em relação ao sistema CBIR-Índice, foi
calculado o ganho relativo, posicionado na última linha de cada tabela com os valores
do sistema CBIR-Índice-Particionamento.
Tabela 2. Precisão média obtida no sistema CBIR-Índice. Coleção BD-160.
Tabela 3. Precisão média obtida no sistema CBIR-Índice-Particionado, utilizando duas
partições. Coleção BD-160.
Tabela 4. Precisão média obtida no sistema CBIR-Índice-Particionado, utilizando quatro
partições. Coleção BD-160.
Tabela 5. Precisão média obtida no sistema CBIR-Índice-Particionado, utilizando oito
partições. Coleção BD-160.
Tabela 6. Precisão média obtida no sistema CBIR-Índice-Particionado, utilizando desesseis
partições. Coleção BD-160.
Tabela 7. Precisão média obtida no sistema CBIR-Índice e CBIR-Índice-Particionado,
utilizando oito partições. Coleção Corel-1000.
Nesta seção verificou-se que o método de recuperação de imagens proposto
neste trabalho produziu bons resultados, que quando comparados com CBIR-Índice.
Com os resultados obtidos da coleção de treinamento, BD-160, pode-se notar que
a qualidade de recuperação do sistema proposto é superior ao sistema CBIR-Índice. E
os resultados da coleção de testes, Corel-1000, se mantiveram similar ao da coleção
de treinamento.
Na coleção teste, o melhor resultado para o P0 e P20 foi utilizando a
imagem dividida em duas partes. Já para P5 e P10 os melhores resultados foi com oito
partes.
Na
coleção
de
treinamento
P0 permaneceu
com
melhores resultados
utilizando duas partes, P5 com quatro partes e P10 e P20 com oito partes. Em
geral, o número de partes com valor igual a oito obteve melhores resultados.
A Tabela 7 ilustra os resultados obtidos na coleção de utilizando oito partições.
Na última linha encontra-se o ganho relativo do CBIR-Índice-Particionado em relação
ao CBIR-Índice.
5 CONCLUSÕES E TRABALHOS FUTUROS
Verificou-se que o método de recuperação de imagens proposto neste
trabalho produziu bons resultados, que quando comparados com os resultados da
proposta de [8] e [9].
Como
trabalhos
futuros, pretendemos
aumentar
o tamanho
do
vetor
trabalhando com outras características de baixo nível como textura e forma, para
obtermos uma melhor medida de precisão. Além disso, atribuir pesos em cada
faixa, para proporcionar uma melhor discriminação entre as faixas presentes em
cada imagem.
Outro objetivo é o estudo das técnicas de indexação multidimensional
utilizadas na recuperação de imagens e a possibilidade de aplicação dessas técnicas na
construção dos índices baseado em estatísticas sobre as características das imagens.
REFERÊNCIAS BIBLIOGRÁFICAS
1.
Baeza, R.; Ribeiro-Neto, B.:
ACM/Addison-Wesley, (1999).
Modern
information
retrieval.
2.
Carson, C., B. S. G. H. M. J. Blobworld: Image segmentation
using expectation-maximization and its application to image querying.
IEEE Computer.
3.
Datta, R.; Joshi, D.; Li, J.; Wang, J. Z. Image Retrieval: Ideas,
Influences, and Trends of the New Age. ACM Transactions on
Computing Surveys, Vol. 40, No. 2, April 2008.
4.
Google.
http://www.google.com.br/intl/pt-BR/help/faq_images.html.
Último acesso: 13/11/2008.
5.
Jing, F.; Li, M.; Zhang, H.-J.; Zhang, B.: “An Effective RegionBased Image Retrieval Framework”, ACM, 2002.
6.
Lew, M. S.: Principles of Visual Information Retrieval. Springer, 2001.
7.
Manning, C., Raghavan, P., and Schütze, H. (2007). An
Introduction to information Retrieval. Cambridge University Press,
Cambridge, England.
8.
Matos, T. ; Silva, I. : Zorzo, C. ; Proença, P.: Distribuição de
características de baixo nível em imagens digitais. CLEI, 2008.
9.
Matos, T. ; Silva, I. : Zorzo, C. ; Proença, P.: Índice Invertido para
Recuperação de Imagens Baseada em Conteúdo. CNMAC, 2008.
10.
Niblack, C. W., Barber, R., Equitz, W., Flickner, M. D., Glasman,
E. H., Petkovic, D., Yanker, P., Faloutsos, C., and Taubin, G.
(1993). The qbic project: Querying images by content using color,
texture, and shape. In Poceedings of the SPIE Conference on
Storage and Retrieval for Image and Video Databases 2-3, February, San
Jose, CA,, pages 173–187.
11.
Rui, Yong; Huang, Thomas S.; Chang, Shih_Fu. Image Retrieval:
Past, Present and Future. International Symposium on Multimedia
Information
Processing.
Disponível
em:
http://citeseer.ist.psu.edu/192987.html. Último acesso: 30/08/2008.
12.
Santos, K.: Dependência entre Termos no Modelo Vetorial, 2003.
Dissertação de Mestrado, Universidade Federal de Uberlândia 2003.
13.
Sclaroff, S., T. T. L. M. (1997). Imagerover: A content-based image
browser for the world wide web. Technical Report, Boston University.
14.
Smith, J. R., C. S.-F. (1996). Visualseek: a fully automated
content-based image query system. In Proceedings of the fourth ACM
international conference on Multimedia.
15. Valle, E.; Cord, M.; Philipp-Foliguet, S.: “High-Dimensional Descriptor
Indexing for Large Multimedia Databases”, ACM, 2008.
16. Wu , L.; Bretschneider , T. : “Comparative Analysis of the Efficiency
of R-tree Based Indexing Strategies for Information Retrieval”, IKE 2004.