Combatendo os Pesadelos da Busca Por Conteúdo em Imagens Médicas

Combatendo os Pesadelos da Busca Por Conteúdo em Imagens Médicas Marcela X. Ribeiro, Joselene Marques, Agma J. M.Traina, Caetano Traina Jr. Grupo de Base de Dados e Imagens (GBDI) Instituto de Ciências Matemáticas e de Computação (ICMC), Universidade de São Paulo (USP) São Carlos, SP, Brasil Resumo – Os dois principais pesadelos que diminuem a qualidade da busca por conteúdo são: a) a “maldição da alta dimensionalidade”, que degrada as estruturas de índice e diminui o poder de discriminação das características extraídas das imagens e b) o “gap semântico” existente entre a representação das características de baixo nível e sua interpretação humana. Neste artigo é proposto um novo método para aumentar a precisão das buscas por conteúdo de imagens médicas que combina técnicas de mineração de regras de associação e de realimentação de relevância. Regras de associação estatísticas são usadas para selecionar as características com maior poder de discriminação das imagens lidando com o problema da maldição da alta dimensionalidade. Uma técnica eficiente de realimentação de relevância é usada para lidar com o problema do gap semântico. Experimentos mostram que o método proposto é eficaz levando a um aumento na precisão das buscas de até 100%. Palavras-chave: Busca por Conteúdo, Realimentação de Relevância, Regras de Associação. Abstract – The two main drawbacks of content based search are: a) the “high dimensionality curse” problem, which degrades index structures and lessens the discrimination power of image features and b) the “semantic gap” that exists between low level features and the human interpretation of images. This work aims at developing an efficient support to improve the precision of medical image retrieval by content, introducing an approach that comprises techniques of association rule mining and relevance feedback. Statistical association rules are used to select the most relevant features to discriminate images, tracking the dimensionality course problem. Additionally, an efficient relevance feedback technique is used to overcome the semantic gap problem. Experiments show that our approach is effective, improving the precision of the query results up to 100%. Key-words: Content-based search, Relevance Feedback, Association Rules.

1. Introdução As técnicas de recuperação de imagens baseada no conteúdo (do inglês, CBIR -Contentbased Image Retrieval-) (1) têm sido intensamente pesquisadas nos últimos anos. As técnicas de busca por conteúdo não estão restritas a informações textuais, pois elas usam informações visuais automaticamente extraídas das imagens. A informação textual é inerentemente subjetiva, porque o especialista humano pode estar em um momento mais preocupado com alguns aspectos da imagem enquanto outros aspectos não são reportados.

As técnicas de busca por conteúdo usam algoritmos de processamento de imagens para extrair características (atributos) das imagens, organizando-as em vetores de características. Os vetores de características são indexados no lugar das imagens permitindo uma recuperação eficiente das mesmas. As características quantificam propriedades visuais intrínsecas das imagens como cor, forma e textura, gerando vetores com centenas e até milhares de elementos. No entanto, o uso de um grande número de características pode ser um problema. Quando o número de características extraídas é grande, os processos de indexação, recuperação, comparação e análise se tornam muito mais

lentos (2). Em muitas situações, muitas das características são correlacionadas, não trazendo nenhuma informação nova sobre as imagens e não aumentando a habilidade de discriminá-las. O uso de um grande número de características leva os sistemas baseados em busca por conteúdo a sofrerem com a “maldição da alta dimensionalidade” (2). Foi provado que o uso de um número elevado de características e, conseqüentemente, alta dimensionalidade dos dados leva a perda de significância de cada característica (3). Assim, para manter a capacidade de discriminação é necessário manter a dimensionalidade dos dados baixa, utilizando somente as características que melhor discriminam as imagens e descartando as demais. Em geral, os usuários de sistemas de busca por conteúdo têm diferentes percepções de similaridade entre imagens, freqüentemente sentindo-se insatisfeitos com os resultados das consultas. Isso ocorre devido à inconsistência existente entre as características de baixo nível automaticamente extraídas das imagens e a interpretação de alto nível provinda do usuário. Essa inconsistência é chamada de gap semântico. Uma das maiores dificuldades existentes na construção de sistemas de busca por conteúdo consiste no desenvolvimento de métodos de representação de imagens que se enquadram com a percepção e subjetividade humana. Uma alternativa eficaz para transpor o gap semântico é introduzir o usuário no processo de consulta, fazendo com que os mesmos interajam e indiquem o que é realmente relevante nas imagens a serem recuperadas e analisadas. Na técnica de realimentação de relevância (do inglês Relevance Feedback - RF), o usuário deve fornecer informações para quantificar a relevância das imagens retornadas pela consulta, permitindo que as consultas futuras sejam reajustadas. Estudos mostram que a técnica de RF é eficaz em resolver o problema do gap semântico (4). Neste artigo é proposto um novo método para a busca por conteúdo em imagens que lida com dois problemas críticos existentes nos sistemas de busca por conteúdo: (1) o grande número de características que leva ao problema de “maldição da alta-dimensionalidade”; (2) o problema de gap semântico existente entre a interpretação do usuário e as características de baixo nível extraídas das imagens. O primeiro problema é tratado aplicando mineração de regras de associação estatísticas para obter o conjunto de características mais relevantes para discriminar as imagens. O segundo problema é tratado usando uma técnica eficiente de realimentação de relevância que encontra as características mais relevantes para alterar a função de distância (similaridade) e o centro de

consulta. Os experimentos realizados mostram que o método proposto aumenta a precisão das buscas em até 100%. Além disso, o método é eficiente, pois diminui-se a complexidade do processamento da consulta com a redução de dimensionalidade do vetor de características. Este artigo está organizado da seguinte maneira. Na Seção 2 é apresentada a metodologia onde é detalhado o método proposto. Na seção 3 são apresentados os experimentos e os resultados alcançados. Finalmente, na Seção 4 são apresentadas às conclusões deste trabalho. 2. Metodologia 2.1. Mineração de Regras de Associação e Seleção de Características A tarefa de associação (5) é uma das atividades de mineração de dados mais exploradas. Ela foi inicialmente motivada por aplicações comercias tais como, análise de mercado, análise de cesta de compras e classificação de clientes. Entretanto, a extração de regras de associação também tem sido intensamente usada em outras aplicações, tais como sumarização e classificação de imagens. Características de baixo nível das imagens são extraídas e organizadas em vetores de características, que descrevem as imagens quantitativamente. Por isso, uma maneira adequada para extrair regras de associação envolvendo as características de imagens deve considerar os dados quantitativos (contínuos), ao invés de dados categóricos (nominais). Neste trabalho, é utilizado o algoritmo StARMiner (6) para a mineração de regras de associação estatísticas em imagens. O objetivo do algoritmo StARMiner é encontrar regras estatísticas envolvendo os atributos que melhor discriminam a imagem em suas categorias. Seja uma base de imagens médicas T, x uma categoria de imagens, Tx ∈ T o subconjunto de imagens da base da categoria x e A um atributo da imagem, as restrições de interesse usadas no algoritmo StARMiner são: 1.|µA(Tx) – µA(T-Tx)|

≥ ∆ µmin,

onde µA(Z) é a média dos valores do atributo A para o subconjunto de imagens Z; ∆ µmin é um parâmetro de entrada que indica a diferença mínima permitida entre a média dos valores de A para as imagens da categoria x e a média dos valores de A para as imagens restantes. 2. Testes de hipóteses. H0 deve ser rejeitada com confiança maior ou igual a γmin. H0: µA(Tx) = µA(T-Tx) H1: µA(Tx) ≠ µA (T-Tx)

onde γmin é um parâmetro de entrada que indica a confiança mínima com a qual a hipótese H0 deve ser rejeitada. 3. σA(Tx)

≤

σmax,

onde σA(Tx) representa o desvio padrão dos valores do atributo A para o subconjunto de imagens Tx; σmax é um parâmetro de entrada que indica o máximo de desvio padrão permitido aos valores de A para as imagens da categoria x.

O algoritmo StARMiner identifica as características com alto poder de discriminação, pois elas apresentam um comportamento particular e uniforme em imagens de uma dada categoria. Isso é importante por que as características que apresentam um comportamento uniforme para todas as imagens da base, independentemente da categoria, não contribuem para discriminá-las e devem ser eliminadas. 2.2 Técnica de Realimentação de Relevância As técnicas de realimentação de relevância (Relevance Feedback RF) usam o conhecimento dos usuários a respeito do que eles entendem como relevante e irrelevante, considerando suas percepções de similaridade. Por incluir a subjetividade humana no processo de recuperação, as técnicas de RF empregam o conhecimento do especialista para aumentar a aplicabilidade de sistemas de busca por conteúdo, enquanto lidam com o gap semântico. Durante os ciclos de RF, é solicitado que os usuários dêem notas às imagens de acordo com sua relevância para uma determinada consulta. Essas notas são mapeadas para pesos que aumentam/diminuem a contribuição dos atributos mais/menos influentes de acordo com a visão do usuário. Esses pesos são atualizados durante as iterações de RF. Neste artigo, a técnica de realimentação de relevância chamada MPP-RF (Multiple Point Projection - Relevance Feedback) (7) é empregada para aumentar a precisão dos resultados das consultas. A técnica MPP combina a garantia do aumento da precisão de uma consulta dada pelos exemplos positivos, com o poder da mudança da consulta dada pelas imagens negativas. Além disso, esta técnica se beneficia da movimentação do centro de consulta e do uso de múltiplos centros de consultas, considerando os objetos relevantes retornados pela consulta original. Quando o usuário requisita a execução de uma consulta q por similaridade, os resultados inicias de q são usados na MPP-RF para processar uma nova consulta centrada em cada objeto selecionado como relevante (Ri) pelo usuário. Um objeto adicional chamado phantom é gerado através da média ponderada dos pesos

dos objetos relevantes e irrelevantes, estabelecidos pelo usuário na primeira iteração. Uma consulta adicional é executada considerando o phantom como centro da mesma. Assim, se existir r objetos selecionados como relevantes, irá existir r + 1 centros de consultas, que são correspondentes aos objetos relevantes e ao phantom. Depois de obter os novos r + 1 centros de consulta, a consulta original é reexecutada para esses novos centros e os resultados intermediários são organizados da seguinte maneira. Seja O ={O1, ...,Oi, ...,On} a união dos conjuntos de respostas retornados para as r+1 consultas. Uma nova distância é computada considerando os pesos de relevância definidos pelo usuário durante a iteração de RF e a distância original de cada objeto relevante Ri (incluindo o phantom) para o centro de busca inicial Cstart. O peso máximo é atribuído ao objeto phantom. Os objetos com os menores valores da nova distância são retornados como o resultado da consulta. A Equação 1 é usada para calcular a nova distância d’:

⎡ ∑i disti ⎤⎥ weight i ⎢ + d ′ = d ij ⋅ ⎢ ∑ weight dist i ⎥ i ⎢⎣ i ⎥⎦

(1)

onde d’ é a nova distancia calculada para o objeto Oij ∈ Oi, dij é a distância do objeto Oij para o objeto de centro de consulta de Oi, weighti referese ao pesos dos objetos relevantes, disti é a distância entre o objeto relevante centro de Oi e o centro de consulta Cstart, disti é a distância entre o objeto relevante centro de Oi e o centro de consulta Cstart. A Figura 1 resume esta técnica.

Figura 1: Etapas da técnica MPP-RF

2.3 Maximizando a Precisão das Buscas por Conteúdo O método proposto lida com dois problemas inerentes de sistemas de busca por conteúdo: a alta dimensionalidade dos vetores de características e o gap semântico. O primeiro problema é tratado através da seleção das características mais relevantes usando a mineração de regras de associação, e o segundo problema é tratado através do emprego da

técnica de realimentação de relevância MPP-RF. O método proposto é ilustrado na Figura 2 e ele é aplicado nas três etapas discutidas a seguir.

para descartar imagens irrelevantes do resultado da consulta. 3. Resultados Para avaliar o método proposto, foi empregada uma técnica bastante conhecida baseada nos gráficos de precisão e revocação (Precision and Recall - P&R) obtidos a partir dos resultados das consultas por conteúdo de imagens. As medidas de precisão e revocação são definidas como:

precisão = Figura 2: Método proposto para maximizar a precisão das buscas por conteúdo

Etapa 1: Extração de Características Na Etapa 1, características de baixo nível de textura, forma e cor são automaticamente extraídas das imagens. Os vetores de características são indexados no lugar das imagens para que o processo de indexação e recuperação seja rápido e eficiente. Etapa 2: Seleção de Características As características das imagens consistem em vetores de alta dimensionalidade, que tornam os processos de indexação e recuperação muito lentos, além de diminuírem a precisão das consultas. Na Etapa 2, o algoritmo StARMiner é aplicado para processar o conjunto de características obtidos na Etapa 1, usando o conhecimento prévio da classe de cada imagem. O algoritmo StARMiner encontra regras de associações estatísticas envolvendo as características das imagens. As características mais relevantes para discriminar as imagens fazem parte das regras mineradas com maiores valores de confiança. Essas características são usadas para reconstruir os vetores de características. Etapa 3: Maximizando a satisfação do usuário com técnicas de realimentação de relevância Na Etapa 3, a técnica de realimentação de relevância MPP-RF é aplicada para aumentar a precisão das buscas por conteúdo em imagens médicas. Quando o usuário requisita uma consulta, o ciclo de RF (realimentação de relevância) começa. Durante o ciclo de RF, é solicitado que o usuário dê notas às imagens recuperadas de acordo com sua relevância em relação à consulta requisitada. Essas notas são mapeadas para pesos. A informação de relevância fornecida irá ser usada para ajustar a contribuição dos atributos de acordo com a percepção do usuário. Tal informação também é utilizada para definir novos centros de consulta e

TRS TS

revocação =

TRS TR

onde, TR é o total de imagens relevantes na base de dados, TRS é o total de imagens relevantes retornadas na consulta, TS é o total de imagens no resultado da consulta. Considerando o tamanho da base de dados, consultas aos k vizinhos mais próximos (do inglês k-NN, k-nearest neighbor) são aplicadas à base de dados. Uma consulta k-NN é uma consulta por similaridade executada comparando os vetores de características através de uma função de distância que quantifica o quão perto (ou similar) cada par de vetores estão. Um exemplo de consulta k-NN é: “dada a imagem de raio-X do senhor José (centro de consulta), encontre na base as 5 imagens mais parecidas com ela”. Uma maneira direta de analisar as curvas de precisão e revocação é comparar a altura das curvas: quanto mais perto a curva estiver do topo do gráfico melhor a técnica de busca empregada. Nos experimentos foram executadas séries de consultas k-NN, considerando k como o tamanho da base de dados e escolhendo os centros de consulta randomicamente. As imagens no resultado da consulta foram ordenadas por sua similaridade com o centro da consulta. Primeiro foram computados os gráficos sem o uso da técnica de realimentação de relevância: (a) usando o vetor de característica obtido na Etapa 1 e (b) usando o vetor de característica reduzido obtido na Etapa 2. O mesmo processo foi repetido usando a técnica de realimentação de relevância. Experimento 1 – A base de dados Mamografia A base de dados Mamografia consiste de 89 imagens que são regiões de interesse de massas tumorais tiradas de mamografias colhidas em um hospital universitário. As imagens são classificadas como tendo tumor benigno ou maligno. Os tipos de tumores estão fortemente relacionados com a forma das imagens: massas benignas apresentam contornos lisos e bem definidos, enquanto nos tumores malignos os contornos se espalham sobre o tecido da mama.

Na Etapa 1, momentos de Zernike (8) são extraídos da base Mamografia, que providenciam um modelo matemático preciso que capturam a informação global de forma das imagens. Para cada imagem, os primeiros 255 momentos de Zernike são extraídos, gerando vetores de características com 255 elementos. Na Etapa 2, os valores dos vetores de características obtidos na Etapa 1 foram normalizados e o algoritmo StARMiner foi aplicado selecionando um conjunto de 38 características relevantes, alcançando uma redução de 85% no número de características usadas para representar as imagens. Um exemplo de regra obtida usando o algoritmo StARMiner é: tumor maligno Æ 7º. Momento de Zernike, indicando a importância do 7º. Momento de Zernike na discriminação dos tumores malignos. Para avaliar o impacto do número de iterações de RF na precisão das consultas, a Etapa 3 foi executada em várias configurações. As três configurações mais representativas são mostradas na Figura 3.

selecionadas pelo algoritmo StARMiner é maior do que a precisão obtida usando o conjunto inicial de 255 características. Esses resultados evidenciam que a maldição da alta dimensionalidade realmente prejudica os resultados das consultas. •

A precisão obtida usando a técnica MPP-RF melhora a precisão das consultas em até 70% (Figura 4(a,d)). Esses resultados mostram que a técnica proposta MPP-RF é eficiente em melhorar a precisão dos resultados das consultas por conteúdo.

•

Os valores mais altos de precisão são obtidos usando o método proposto que combina o algoritmo StARMiner com a técnica MPP-RF. Esses resultados confirmam que o método proposto é efetivo em aumentar a precisão das consultas nos sistemas de busca por conteúdo.

Experimento Heterogênea

2

–

A

base

de

dados

A base de dados Heterogênea consiste de 210 imagens médicas classificadas em oito categorias: Angiograma; RM Bacia Axial, RM Cabeça Axial, RM Cabeça Sagital, RM Cabeça Coronal, RM Abdômen Coronal, RM Abdômen Axial e RM Coluna Sagital. A Etapa 1 foi executada extraindo características de textura das imagens previamente segmentadas em 5 regiões por uma variação do método EM/MPM. Esse procedimento gera um vetor bastante compacto de 30 características por imagens. Na Etapa 2, o algoritmo StARMiner é aplicado sobre a base Heterogênea selecionando um total de 21 características, reduzindo em 30% o tamanho do vetor de características original usado para representar as imagens.

Figura 3. Gráficos de Precisão e Revocação obtidos usando o conjunto inicial de 255 características e o conjunto de 38 características selecionado pelo algoritmo StARMiner para diferentes configurações. (a) Usando 1 iteração de RF, o usuário selecionando 10 exemplos positivos (relevantes) e 5 negativos (irrelevantes); (b) Usando 1 iteração de RF, o usuário selecionando 5 exemplos positivos e 5 exemplos negativos; (c) Usando 3 iterações de RF o usuário selecionando 5 exemplos positivos e 5 exemplos negativos; (d) Usando 5 iterações de RF o usuário selecionando 5 exemplos positivos e 5 exemplos negativos

Analisando os gráficos da Figura 3, conclui-se que: •

A redução de dimensionalidade obtida na Etapa 2 acarreta um importante ganho de precisão. Com ou sem RF, a precisão obtida usando o conjunto de 38 características

A Etapa 3 foi executada usando três e cinco iterações de RF, tendo o usuário selecionado 5 imagens como relevantes (positivas) e 5 imagens como irrelevantes (negativas). Com intuito de comparar os vetores de características e processar as consultas k-NN, os gráficos de precisão e revocação apresentados na Figura 5 foram construídos usando a função de distância Euclidiana ponderada. Para 5 iterações de RF, o ganho de precisão chega a 100% quando o valor da revocação é 0.8 (ver Figura 4). A Figura 5 mostra os resultados do processamento de uma consulta k-NN (k=10), sobre o centro de busca apresentado na borda superior esquerda da tela da Figura 5(a). A Figura 5(a) mostra os resultados usando o vetor de 30 características originais antes de um ciclo de RF, enquanto a Figura 5(b) apresenta os resultados antes de um ciclo de RF usando as 21

características selecionadas. A Figura 5(c) mostra os resultados usando o vetor de 30 características originais após um ciclo de RF, enquanto a Figura 5(d) mostra os resultados após um ciclo de RF usando as 21 características selecionadas. A maior precisão foi obtida usando o método proposto (Figura 5(d)) onde a maioria das imagens retornadas são da mesma categoria do centro de consulta.

experimentos realizados mostraram que o método proposto é efetivo em aumentar a precisão das consultas por conteúdo em imagens, contribuindo para reduzir o gap semântico e alcançando um aumento de aproximadamente 100% na precisão das consultas. Agradecimentos Ao apoio financeiro fornecido pela FAPESP e CNPq.

Referências 1. Müller H, Michoux N, Bandon D, Geissbuhler A. A Review of Content-based Image Retrieval Systems in Medical Applications-Clinical Benefits and Future Directions. International Journal of Medical Informatics 2004;73(1):1-23. Figura 4. Gráficos de precisão e revocação obtidos usando o conjunto de 30 características (original) e o conjunto de 21 características selecionados pelo algoritmo StARMiner, usando 3 iterações de RF (esquerda) e usando 5 iterações de RF (direita).

2. Aggarwal CC. On the Effects of Dimensionality Reduction on High Dimensional Similarity Search. In: ACM PODS 2001; 2001 May 21-23, 2001; Santa Barbara, CA: ACM Press; 2001. 3. Beyer K, Godstein J, Ramakrishnan R, Shaft U. When is "Nearest Neighbor" Meaningful? In: Beeri C, Buneman P, editors. International Conference on Database Theory (ICDT); 1999 January 10-12, 1999; Jerusalem, Israel: Springer Verlag; 1999. p. 217-235. 4. Lin H-C, Chiu C-Y, Yang S-N. Finding textures by textual descriptions, visual examples,and relevance feedbacks. Pattern Recognition Letters 2003;Sect. 2255–2267. 5. Agrawal R, Imielinski T, Swami AN. Mining Association Rules between Sets of Items in Large Databases. In: Buneman P, Jajodia S, editors. ACM SIGMOD International Conference on Management of Data; 1993 May 26-28, 1993; Washington, D.C.: ACM Press; 1993. p. 207-216.

Figura 5: Resultados de consultas kNN (k=10). Resultados obtidos anteriormente a uma iteração de RF (a) usando as 30 características originais e (b) usando as 21 características selecionadas. Resultados obtidos após um ciclo de RF (c) usando as 30 características originais e (b) usando as 21 características selecionadas.

4. Discussões e Conclusões Neste artigo foi proposto um novo método para aumentar a precisão de buscas por conteúdo em imagens médicas, ajudando a solucionar dois problemas críticos de sistemas de busca por conteúdo: a alta dimensionalidade dos vetores de características e o gap semântico. O primeiro problema foi tratado usando mineração de regras de associação estatísticas para seleção dos atributos mais relevantes das imagens, conseqüentemente reduzindo a dimensionalidade dos vetores de características. O segundo problema foi tratado usando uma técnica eficiente de realimentação de relevância chamada (MPPRF) que usa o conhecimento do usuário para aumentar a precisão das buscas. Os

6. Ribeiro MX, Balan AGR, Felipe JC, Traina AJM, Traina Jr. C. Mining Statistical Association Rules to Select the Most Relevant Medical Image Features. In: First International Workshop on Mining Complex Data (IEEE MCD'05); 2005 November 2005; Houston, USA: IEEE Computer Society; 2005. p. 91-98. 7. Traina A, Marques J, Traina C. Fighting the Semantic Gap on CBIR Systems through New Relevance Feedback Techniques. In: 19th IEEE Intl. Symposium on Computer-Based Medical Systems CBMS; 2006; Salt Lake City, Utah, USA.: IEEE Computer Society; 2006. p. 1-6. 8. Khotanzad A, Hong YH. Invariant Image Recognition by Zernike Moments. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 1990;12(5):489-497. Contato {mxavier, joselene,agma,caetano}@icmc.usp.br; ICMC-USP, Caixa-Postal: 668, São Carlos-SP, (16) 3373-9674