Métodos adaptativos de segmentação aplicados à recuperação de imagens por conteúdo por André Guilherme Ribeiro Balan - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

Servic

¸o de Pós-Graduac

¸˜

ao do ICMC-USP

Data de Depósito: 22 de março de 2007

Assinatura :

Métodos adaptativos de segmentaç˜

ao aplicados à

recuperaç˜

ao de imagens por conteúdo1

André Guilherme Ribeiro Balan

Orientadora: Profa Dra Agma Juci Machado Traina

Tese apresentada ao Instituto de Ciências Matemáticas e de Com-

putaç˜

ao - ICMC-USP, como parte dos requisitos para obtenç˜

ao do

t´ıtulo de Doutor em Ciências de Computaç˜

ao e Matemática Com-

putacional.

USP - S˜

ao Carlos

Março de 2007

1Apoio financeiro FAPESP, processo 03/01769-4

à minha irm˜

a Ana Carolina

Agradecimentos

À minha orientadora Profa Dra Agma J. M. Traina, por contribuir efetivamente na re-

alizaç˜

ao deste trabalho, por me ensinar atenciosamente, e por me incentivar em todos os

momentos. Principalmente, por acreditar em mim e ter me dado a excelente oportunidade

de trabalhar ao seu lado;

Aos meus pais, Ana e Antônio, por me ensinarem o caminho da determinaç˜

ao e perse-

verança desde o in´ıcio. Por serem a minha maior referência da palavra amor. Por serem o

meu apoio mais constante. Por serem meus heróis;

À minha namorada Elaine, agradeço todo carinho e dedicaç˜

ao. Por acompanhar meu

trabalho e estar comigo em todos os momentos, n˜

ao importando a distância.

Aos professores Christos Faloutsos e Eric Xing, pela orientaç˜

ao e grande apoio na rea-

lizaç˜

ao do estágio na Carnegie Mellon University, pelas caronas aos finais de tarde e pelo

imenso companheirismo;

Aos amigos José Fernando (Junior), Jia Yu (Tim), David e tia Aggie, que fizeram espe-

cialmente parte do excelente per´ıodo nos Estados Unidos;

Ao Dr. David Araújo e ao professor Dr. Paulo M. A. Marques pelas reuni˜

oes em Ribeir˜

ao

Preto que originaram diversas idéias para este trabalho, por disponibilizarem as imagens

médicas utilizadas nos experimentos e por auxiliarem na validaç˜

ao dos resultados;

Ao professor Dr. Caetano Traina Junior pela ajuda na revis˜

ao dos trabalhos e por estar

sempre disposto a ajudar;

A todos os amigos do Grupo de Bases de Dados e Imagens (GBDI), especialmente à

Mônica, Marcela, Camila, e ao Humberto, que gentilmente auxiliaram na revis˜

ao deste do-

cumento;

Aos meus primos José Ricardo e Eduardo, sempre sol´ıcitos e companheiros;

A todos os meus amigos do ICMC-USP e da cidade de Mococa, pela amizade e compa-

nheirismo;

À Fapesp, Fundaç˜

ao de Amparo à Pesquisa, pelo apoio financeiro.

Resumo

A possibilidade de armazenamento de imagens no formato digital favoreceu a evoluç˜

ao de

diversos ramos de atividades, especialmente as áreas de pesquisa e cl´ınica médica. Ao mesmo

tempo, o volume crescente de imagens armazenadas deu origem a um problema de relevância

e complexidade consideráveis: a Recuperaç˜

ao de Imagens Baseada em Conteúdo, que, em

outras palavras, diz respeito à capacidade de um sistema de armazenamento processar

operaç˜

oes de consulta de imagens a partir de caracter´ısticas visuais, extra´ıdas automati-

camente por meio de métodos computacionais.

Das principais quest˜

oes que constituem este problema, amplamente conhecido pelo termo

CBIR - Content-Based Image Retrieval, fazem parte as seguintes: Como interpretar ou re-

presentar matematicamente o conteúdo de uma imagem? Quais medidas que podem carac-

terizar adequadamente este conteúdo? Como recuperar imagens de um grande repositório

utilizando o conteúdo extra´ıdo? Como estabelecer um critério matemático de similaridade

entre estas imagens?

O trabalho desenvolvido e apresentado nesta tese busca, exatamente, responder perguntas

deste tipo, especialmente para os dom´ınios de imagens médicas e da biologia genética, onde

a demanda por sistemas computacionais que incorporam técnicas CBIR é consideravelmente

alta por diversos motivos. Motivos que v˜

ao desde a necessidade de se buscar informaç˜

ao

visual que estava até ent˜

ao inacess´ıvel pela falta de anotaç˜

oes textuais, até o interesse em

poder contar com aux´ılio computacional confiável para a importante tarefa de diagnóstico

cl´ınico.

Neste trabalho s˜

ao propostos métodos e soluç˜

oes inovadoras para o problema de seg-

mentaç˜

ao e extraç˜

ao de caracter´ısticas de imagens médicas e imagens de padr˜

oes espaciais

de express˜

ao genética. A segmentaç˜

ao é o processo de delimitaç˜

ao automático de regi˜

oes

de interesse da imagem que possibilita uma caracterizaç˜

ao bem mais coerente do conteúdo

visual, comparado com as tradicionais técnicas de caracterizaç˜

ao global e direta da imagem.

Partindo desta idéia, as técnicas de extraç˜

ao de caracter´ısticas desenvolvidas neste trabalho

empregam métodos adaptativos de segmentaç˜

ao de imagens e alcançam resultados excelentes

na tarefa de recuperaç˜

ao baseada em conteúdo.

i

Abstract

Storing images in digital format has supported the evolution of several branches of activities,

specially the research area and medical clinic. At the same time, the increasing volume of

stored images has originated a topic of considerable relevance and complexity: the Content-

Based Imagem Retrieval, which, in other works, is related to the ability of a computational

system in processing image queries based on visual features automatically extracted by

computational methods.

Among the main questions that constitute this issue, widely known as CBIR, are these:

How to mathematically express image content? What measures can suitably characterize

this content? How to retrieve images from a large dataset employing the extracted content?

How to establish a mathematical criterion of similarity among the imagens?

The work developed and presented in this thesis aims at answering questions like those,

especially for the medical images domain and genetical biology, where the demand for com-

putational systems that embody CBIR techniques is considerably high for several reasons.

Reasons that range from the need for retrieving visual information that was until then

inaccessible due to the lack of textual annotations, until the interest in having liable com-

putational support for the important task of clinical diagnosis.

In this work are proposed innovative methods and solutions for the problem of image

segmentation and feature extraction of medical images and images of gene expression pat-

terns. Segmentation is the process that enables a more coherent representation of image’s

visual content than that provided by traditional methods of global and direct represen-

tation. Grounded in such idea, the feature extraction techniques developed in this work

employ adaptive image segmentation methods, and achieve excellent results on the task of

Content-Based Image Retrieval.

iii

Sumário

1

Introduç˜

ao

1

1.1

Motivaç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Objetivos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Principais contribuiç˜

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Organizaç˜

ao da tese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2

Recuperaç˜

ao de Imagens Baseada em Conteúdo

7

2.1

Tópicos em CBIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2

Extraç˜

ao de caracter´ısticas . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.3

RBIR - Recuperaç˜

ao de imagens baseada em regi˜

ao . . . . . . . . . . . . . .

13

2.4

Avaliaç˜

ao de similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.4.1

Funç˜

oes de distâncias de Minkowski (fam´ılia Lp) . . . . . . . . . . . .

14

2.4.2

Funç˜

ao de distância Cosseno . . . . . . . . . . . . . . . . . . . . . . .

14

2.4.3

Intersecç˜

ao de histograma . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4.4

Distância quadrática . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4.5

Distância Mahalanobis . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.5

Consultas por similaridade em espaços vetoriais . . . . . . . . . . . . . . . .

16

2.5.1

Consulta por raio de abrangência (range query) . . . . . . . . . . . .

16

2.5.2

Consulta aos k vizinhos mais próximos (kNN query) . . . . . . . . . .

17

2.6

Avaliaç˜

ao de eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.6.1

Gráficos de Precis˜

ao versus Revocaç˜

ao . . . . . . . . . . . . . . . . .

18

2.7

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3

Técnicas de extraç˜

ao de caracter´ısticas de imagens

23

3.1

Assinaturas de forma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.1.1

Funç˜

ao distância do centróide . . . . . . . . . . . . . . . . . . . . . .

23

3.1.2

Funç˜

ao posiç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2

Descritores de Fourier

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.1

Transformada de Fourier . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.2

Obtenç˜

ao do descritores . . . . . . . . . . . . . . . . . . . . . . . . .

26

v

3.3

Momentos de Zernike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.4

Matrizes de co-ocorrência . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.5

Análise da transformada de Fourier . . . . . . . . . . . . . . . . . . . . . . .

31

3.6

Análise da transformada de Wavelet . . . . . . . . . . . . . . . . . . . . . . .

31

3.6.1

Transformada de Wavelet

. . . . . . . . . . . . . . . . . . . . . . . .

33

3.6.2

Medidas da transformada de Wavelet . . . . . . . . . . . . . . . . . .

34

3.7

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4

Segmentaç˜

ao de imagens

37

4.1

Limiarizaç˜

ao (Thresholding) . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.2

Métodos baseados na detecç˜

ao de bordas . . . . . . . . . . . . . . . . . . . .

39

4.2.1

Algoritmos de Enlace (Edge Linking) . . . . . . . . . . . . . . . . . .

40

4.2.2

Modelos de contorno ativo - Snakes . . . . . . . . . . . . . . . . . . .

42

4.3

Métodos baseados em regi˜

oes

. . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.3.1

Watersheds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.4

Métodos baseados em Textura . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.5

Método de segmentaç˜

ao EM/MPM . . . . . . . . . . . . . . . . . . . . . . .

49

4.5.1

Modelos das Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.5.2

Abordagem MPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

4.5.3

Algoritmo EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.5.4

Algoritmo EM/MPM . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.6

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5

Extraç˜

ao de caracter´ısticas de imagens médicas 2D de ressonância magnética 59

5.1

Método proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

5.1.1

Segmentaç˜

ao de imagens . . . . . . . . . . . . . . . . . . . . . . . . .

60

5.1.2

Caracterizaç˜

ao da imagem . . . . . . . . . . . . . . . . . . . . . . . .

62

5.1.3

Funç˜

ao de distância . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

5.2

Experimentos e resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.2.1

Avaliaç˜

ao quantitativa . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.2.2

Avaliaç˜

ao qualitativa . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

5.3

Tempo de processamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

5.4

Consideraç˜

oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

6

Sistema FEMine - CBIR para padr˜

oes de express˜

ao genética

77

6.1

Motivaç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

6.2

Descriç˜

ao do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.3

Trabalhos correlatos e contribuiç˜

ao do projeto . . . . . . . . . . . . . . . . .

80

6.4

Processamento das imagens

. . . . . . . . . . . . . . . . . . . . . . . . . . .

82

6.4.1

Identificaç˜

ao dos embri˜

oes . . . . . . . . . . . . . . . . . . . . . . . .

82

vi

6.4.2

Isolando o embri˜

ao principal . . . . . . . . . . . . . . . . . . . . . . .

84

6.4.3

Alinhamento (registro) das imagens . . . . . . . . . . . . . . . . . . .

90

6.4.4

Etapas finais na preparaç˜

ao de imagens . . . . . . . . . . . . . . . . .

92

6.5

Extraç˜

ao de caracter´ısticas da imagem . . . . . . . . . . . . . . . . . . . . .

93

6.5.1

Análise dos Componentes Principais - PCA

. . . . . . . . . . . . . .

94

6.5.2

Vetor de caracter´ısticas proposto

. . . . . . . . . . . . . . . . . . . .

95

6.6

Experimentos e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

6.6.1

Processamento das imagens . . . . . . . . . . . . . . . . . . . . . . .

96

6.6.2

Cálculo dos Eigen-Embryos

. . . . . . . . . . . . . . . . . . . . . . .

97

6.6.3

Cálculo dos vetores de caracter´ısticas . . . . . . . . . . . . . . . . . .

99

6.6.4

Recuperaç˜

ao de imagens por conteúdo

. . . . . . . . . . . . . . . . .

99

6.7

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7

Método HEAD - the Human Encephalon Automatic Delimiter

105

7.1

Vis˜

ao geral do método HEAD . . . . . . . . . . . . . . . . . . . . . . . . . . 106

7.2

Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

7.2.1

Métodos baseados em regi˜

ao . . . . . . . . . . . . . . . . . . . . . . . 107

7.2.2

Métodos baseados em bordas

. . . . . . . . . . . . . . . . . . . . . . 108

7.3

O método HEAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

7.3.1

Algoritmo de particionamento de histograma . . . . . . . . . . . . . . 109

7.3.2

Remoç˜

ao do plano de fundo background . . . . . . . . . . . . . . . . . 111

7.3.3

Delimitaç˜

ao do encéfalo

. . . . . . . . . . . . . . . . . . . . . . . . . 113

7.4

Experimentos e resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

7.4.1

Avaliaç˜

ao quantitativa . . . . . . . . . . . . . . . . . . . . . . . . . . 122

7.4.2

Imagens Sintéticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7.4.3

Tempo de processamento . . . . . . . . . . . . . . . . . . . . . . . . . 125

7.5

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

8

Conclus˜

ao

129

8.1

Consideraç˜

oes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

8.2

Principais contribuiç˜

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

8.3

Trabalhos de extens˜

ao

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

A Teoria dos Fractais

135

B Revis˜

ao dos principais conceitos de genética

139

B.1 Análise de express˜

ao genética . . . . . . . . . . . . . . . . . . . . . . . . . . 140

B.1.1

Microarray de DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

B.1.2

Hibridizaç˜

ao in situ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Referências Bibliográficas

143

vii

Lista de Figuras

2.1

Vis˜

ao geral de um sistema CBIR. . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2

Configuraç˜

oes de um conjunto de pontos eqüidistantes para as distâncias L1,

L2 e Linfinity em um espaço bi-dimensional. . . . . . . . . . . . . . . . . . . .

15

2.3

Exemplo de uma consulta por raio de abrangência onde o conjunto resposta

contém 7 elementos sendo que O n˜

ao faz parte do resultado. . . . . . . . . .

17

2.4

Exemplo de uma consulta do tipo kNN onde o conjunto resposta contém 5

elementos sem contar o elemento de busca O.

. . . . . . . . . . . . . . . . .

18

2.5

Conjuntos referentes às medidas de precis˜

ao e revocaç˜

ao para uma determi-

nada operaç˜

ao de busca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.6

Exemplo de um gráfico de medidas Precis˜

ao versus Revocaç˜

ao para uma

operaç˜

ao de busca [1].

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1

Exemplo de matrizes de co-ocorrência. (a) imagem em tons de cinza; (b)

matriz de co-ocorrência para ângulo 0 e d = 1; (c) matriz de co-ocorrência

para ângulo 135◦ e d = 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.2

Extraç˜

ao de caracter´ısticas a partir da transformada de Fourier (espaço das

freqüências.) (a) energia ao longo de anéis; (b) energia ao longo de cunhas [2].

31

3.3

As primeiras sete wavelets de Haar. . . . . . . . . . . . . . . . . . . . . . . .

32

3.4

Decomposiç˜

ao progressiva das linhas e colunas da imagem [3]. . . . . . . . .

34

3.5

Exemplo de decomposiç˜

ao wavelet. (a) imagem original; (b) imagem decom-

posta em duas etapas a partir das wavelets de Haar; (c) configuraç˜

ao das

regi˜

oes após a decomposiç˜

ao. . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.1

Seleç˜

ao do limiar (threshold) ótimo para um histograma bimodal.

. . . . . .

39

4.2

Primeira e segunda derivada de uma amostra unidimensional de uma imagem. 40

4.3

Operadores de Sobel (a) máscara usada para computar Gy; (b) máscara usada

para computar Gx. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.4

Exemplo da utilizaç˜

ao dos operadores de Sobel. (a) imagem original; (b)

imagem gradiente

G2 + G2 . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

x

y

ix

4.5

Exemplo de segmentaç˜

ao utilizando snakes (a) imagem de ressonância magnética

do ventr´ıculo esquerdo de um coraç˜

ao humano; (b) mapa de fluxo do vetor

gradiente (Gradient Vector Flow); (c) etapas de ajuste da snake até a posiç˜

ao

de equil´ıbrio [4]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.6

Ilustraç˜

ao dos divisores de água (watersheds) e represas (catchment basins).

Vis˜

oes sob perspectiva e “vis˜

ao aérea” [5].

. . . . . . . . . . . . . . . . . . .

44

4.7

Ilustraç˜

ao do algoritmo de alagamento utilizando uma vizinhança 4-conectada

(a) imagem original; (b-e) etapas da rotulaç˜

ao. . . . . . . . . . . . . . . . . .

46

4.8

Exemplo de super-segmentaç˜

ao. (a) imagem original (gel de electroforese);

(b) imagem super-segmentada [5]. . . . . . . . . . . . . . . . . . . . . . . . .

46

4.9

Transformada de watershed a partir de marcadores. (a) marcadores da imagem

da Figura 4.8a; (b) resultado da transformada de watershed [5].

. . . . . . .

46

4.10 Exemplo de transformada de distância para uma imagem binarizada. (a)imagem

original; (b) transformada de distância. . . . . . . . . . . . . . . . . . . . . .

47

4.11 Exemplo de separaç˜

ao de part´ıculas circulares parcialmente sobrepostas. (a)

imagem binária das part´ıculas; (b) negativo do mapa de distância euclidiano;

(c) marcadores sobrepostos no mapa de distâncias (neste caso os marcadores

ao pontos de máximo local); (d) resultado da transformada de watershed.

.

48

4.12 Exemplos de texturas extra´ıdas do álbum de Brodatz [6] (a)-(d) texturas de

comportamento determin´ıstico; (e)-(h) texturas de comportamento aleatório.

49

4.13 Estruturas de vizinhanças para os campos aleatórios de Markov, considerando

o elemento central x. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.14 Conjunto de cliques. (a) vizinhança de primeira ordem; (b) cliques correspon-

dentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.15 Diagrama simplificado do processo de segmentaç˜

ao EM/MPM. . . . . . . . .

57

5.1

Exemplo de segmentaç˜

ao realizada pelo método EM/MPM. (a) imagem ori-

ginal; (b) imagem segmentada com L = 5; (c) regi˜

ao de classe 1 (fluido

cérebro-espinhal); (d) regi˜

ao de classe 2 (massa cinzenta); (e) regi˜

ao de classe

3 (massa branca); (f) regi˜

ao de classe 4 (dura, medula óssea, gordura).

. . .

63

5.2

Cálculo da dimens˜

ao fractal das regi˜

oes da Figura 5.1 . . . . . . . . . . . . .

66

5.3

Exemplo de imagem da espinha segmentada pelo método EM/MPM. (a) ima-

gem original; (b) imagem segmentada com L = 5; (c) regi˜

ao de classe 1; (d)

regi˜

ao de classe 2; (e) regi˜

ao de classe 3; (f) regi˜

ao de classe 4; (g) gráficos de

correlaç˜

ao das regi˜

oes e respectivas dimens˜

oes fractais.

. . . . . . . . . . . .

67

5.4

Vetor de caracter´ısticas das imagens - 5(L − 1) valores reais. . . . . . . . . .

67

5.5

Exemplo de consulta aos 20 vizinhos mais próximos realizada pelo sistema

desenvolvido sobre uma base de 704 imagens de variadas categorias. . . . . .

69

x

5.6

Curvas médias de precis˜

ao vs.

revocaç˜

ao ilustrando o comportamento na

recuperaç˜

ao de imagens de diversos vetores de caracter´ısticas, incluindo nossa

abordagem, os momentos de Zernike e histogramas de brilho da imagem. . .

72

5.7

Comparaç˜

ao do vetor de caracter´ısticas proposto para diferentes valores do

parâmetro L - o número de classes para segmentaç˜

ao da imagem.

. . . . . .

73

5.8

Curvas médias de precis˜

ao e revocaç˜

ao para cada categoria de imagens da

base experimental descrita na Tabela 5.1. . . . . . . . . . . . . . . . . . . . .

74

5.9

Exemplo de consulta kNN (k = 25). Número total de imagens relevantes: 37.

74

5.10 Exemplo de consulta kNN (k = 25). Número total de imagens relevantes: 58.

75

6.1

Diagrama de módulos do sistema FEMine. . . . . . . . . . . . . . . . . . . .

80

6.2

Vizinhança circular de 12 vizinhos definida para o filtro de variância local.

.

83

6.3

Identificaç˜

ao de embri˜

oes da Drosophila Melanogaster em imagem de ISH. (a)

imagem original com o embri˜

ao principal ao centro e um embri˜

ao sobressalente

interceptando parte de sua borda; (b) aplicaç˜

ao do filtro de variância local com

uma vizinhança circular de 12 vizinhos (Fig. 6.2); (c) limiarizaç˜

ao (threshold)

do resultado do filtro de variância; (d) resultado da aplicaç˜

ao do operador

morfológico binário de preenchimento de buracos (fill holes) e abertura binária. 83

6.4

Algoritmo de identificaç˜

ao dos embri˜

oes na imagem original. . . . . . . . . .

84

6.5

Exemplos da aplicaç˜

ao da transformada de watershed nas imagens binarizadas

dos embri˜

oes. (a,d) imagens binárias dos embri˜

oes; (b,e) mapas de distâncias

sobreposto com as respectivas regi˜

oes de máximo local; (c,f) resultados mal

sucedidos na tentativa de separaç˜

ao dos embri˜

oes (as regi˜

oes dos embri˜

oes

foram “quebradas”).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.6

Processo iterativo de determinaç˜

ao de marcadores para aplicaç˜

ao da transfor-

mada de watershed. (a) imagem original (threshold=254); (b) threshold=244;

(c) threshold=234; (d) threshold=224; (e) threshold=215 (duas regi˜

oes isoladas

que ser˜

ao os marcadores); (f) marcadores sobrepostas no mapa de distâncias

euclidianas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

6.7

Algoritmo de seleç˜

ao de marcadores para a transformada de watershed . . . .

87

6.8

Passos do algoritmo de alagamento iniciado a partir dos marcadores da Figura

6.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

6.9

Exemplos de marcadores. (a) imagem com regi˜

ao n˜

ao convexa, sem evidência

de part´ıculas conectadas; (b) marcadores (diferença do limiar final igual a

5); (c) imagem binária de embri˜

oes, com evidência de part´ıculas a serem

separadas; (d) marcadores (diferença do limiar final igual a 94). . . . . . . .

88

6.10 Algoritmo de particionamento recursivo de part´ıculas binárias conectadas . .

89

6.11 Exemplo da aplicaç˜

ao do algoritmo da particionamento recursivo para uma

imagem binária com dois embri˜

oes. . . . . . . . . . . . . . . . . . . . . . . .

89

6.12 Particionamento recursivo de uma imagem binária com três embri˜

oes. . . . .

89

xi

6.13 Registro da máscara do embri˜

ao principal utilizando uma imagem canônica.

(a) imagem alvo contendo uma elipse; (b) imagem fonte (máscara de embri˜

ao

a ser transformada); (c) diferença entre as imagens alvo e fonte antes do

registro; (d) imagem fonte ao final do processo de registro; (e) diferença entre

as imagens alvo e fonte depois do registro. . . . . . . . . . . . . . . . . . . .

91

6.14 Preparaç˜

ao das imagens para extraç˜

ao de caracter´ısticas. (a,f,k) imagens ori-

ginais; (b,g,l) embri˜

oes identificados utilizando o método descrito na seç˜

ao

6.4.1); (c,h,m) regi˜

oes dos embri˜

oes separadas utilizando o método proposto

de particionamento recursivo (seç˜

ao 6.4.2); (d,i,n) imagens registradas utili-

zando o método descrito na seç˜

ao 6.4.3; (e,j,o) imagens prontas para a extraç˜

ao

de caracter´ısticas, com a borda dos embri˜

oes levemente recortada.

. . . . .

93

6.15 Eigen-Embryos mais significativos de um conjunto de 2000 imagens de em-

bri˜

oes. A imagem de número 1 ilustra o autovetor associado ao maior au-

tovalor. As demais imagens est˜

ao dispostas em ordem decrescente de seus

respectivos autovalores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

6.16 Algoritmo para o cálculo dos Eigen-Embryos.

. . . . . . . . . . . . . . . . .

96

6.17 Exemplos de imagens da FlyBase. . . . . . . . . . . . . . . . . . . . . . . . .

97

6.18 Exemplos de imagens “ruins”, automaticamente descartadas pelo sistema FE-

Mine. (a) imagem com embri˜

ao incompleto; (b) embri˜

ao muito difuso com o

plano de fundo; (c) embri˜

ao com formato n˜

ao el´ıptico; (d) imagem onde n˜

ao

se pode dizer qual o é embri˜

ao principal. . . . . . . . . . . . . . . . . . . . .

98

6.19 Exemplo de consulta por similaridade com o sistema FEMine. . . . . . . . . 100

6.20 Exemplo de consulta por similaridade com o sistema FEMine. . . . . . . . . 101

6.21 Exemplos de grupos de consulta.

. . . . . . . . . . . . . . . . . . . . . . . . 101

6.22 Média aritmética das curvas de precis˜

ao e revocaç˜

ao de 20 operaç˜

oes de con-

sultas kNN realizadas pelo sistema FEMine. . . . . . . . . . . . . . . . . . . 102

7.1

Exemplo de particionamento utilizando a técnica proposta (Eq. 7.2). l o n´ıvel

de particionamento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

7.2

Uma comparaç˜

ao entre a técnica de particionamento de histogramas do método

HEAD e a técnica de Otsu.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 111

7.3

Determinaç˜

ao do limiar l para remoç˜

ao do plano de fundo da imagem. . . . . 112

7.4

Remoç˜

ao do plano de fundo da imagem. (a) Corte mediano da imagem origi-

nal; (b) Classificaç˜

ao inicial obtida com o limiar l (voxels com n´ıvel de cinza

maior que l s˜

ao brancos); (c) Máscara final da cabeça. . . . . . . . . . . . . . 113

7.5

Exemplos de histogramas de n´ıvel de cinza de imagens de cabeça (com plano

de fundo removido). (a) Histograma de uma imagem real de 256 × 256 × 160

voxels; (b) Histograma de uma imagem sintética de 181 × 217 × 182 voxels

do projeto BrainWeb (MNI). . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

xii

7.6

Determinaç˜

ao de l1 e l2, os limites da saliência MB/MC, em histograma de

uma imagem MRI real de 256 × 256 × 160 voxels. . . . . . . . . . . . . . . 115

7.7

Computaç˜

ao de l1 e l2 no histograma de uma imagem sintética do projeto

BrainWeb (MNI), de 181×217 × 182 voxels. . . . . . . . . . . . . . . . . . . 116

7.8

Classificaç˜

oes iniciais obtidas com os limiares l1 e l2. (a) Corte mediano origi-

nal da imagem utilizada no exemplo da Figura 7.6; (b) Classificaç˜

ao binária

correspondente; (c) Corte mediano original da imagem utilizada no exemplo

da Figura 7.7, (d) Classificaç˜

ao binária correspondente. . . . . . . . . . . . . 117

7.9

Seqüência de operadores morfológicos binários aplicados para se obter a máscara

final do cérebro.

(a) corte mediano da imagem original; (b) classificaç˜

ao

binária inicial obtida com base nos limiares l1 e l2; (c) eros˜

ao binária; (d)

seleç˜

ao do maior componente conexo; (e) dilataç˜

ao binária; (f) fechamento de

buracos (máscara final do cérebro). . . . . . . . . . . . . . . . . . . . . . . . 118

7.10 Resumo do método HEAD.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 119

7.11 Uma comparaç˜

ao visual do método HEAD (coluna da esquerda) e o algo-

ritmo BSE (coluna da direita). (a,b) Mapeamento 3D de erros nas máscaras

resultantes (áreas em laranja indicam as falhas); (c,d) Corte da imagem origi-

nal combinada com as máscaras resultantes; (e,f) Corte mediano da imagem

original aplicado às máscaras resultantes. . . . . . . . . . . . . . . . . . . . . 120

7.12 Comparaç˜

ao visual do método HEAD (coluna da esquerda) e do algoritmo

BSE (coluna da direita), para uma imagem ruidosa do conjunto experimen-

tal. (a,b) Vis˜

ao obl´ıqua das máscaras; (c,d) Mapeamento 3D dos erros mais

salientes (desenhados na cor laranja) dada a segmentaç˜

ao manual de um es-

pecialista; (e,f) Corte de altura aleatória da imagem original aplicada às mas-

caras de sa´ıda.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.13 Exemplos de máscaras geradas pelos métodos HEAD e BSE (imagens reais) . 123

7.14 Mosaico ilustrando a influência da diferentes taxas de ru´ıdo gaussiano em

imagens sintéticas do BrainWeb: (a) 3% (b) 5% (c) 7% (d) 9%

. . . . . . . 124

7.15 Máscaras do cérebro geradas pelo BSE (linha superior) e pelo método HEAD

(linha inferior) na segmentaç˜

ao de imagens sintéticas com diferentes intensi-

dades de ru´ıdo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

A.1 Exemplo de fractal - o Triângulo de Sierpinsky . . . . . . . . . . . . . . . . . 135

B.1 Imagens provenientes da análise de Hibridizaç˜

ao in situ (ISH) de embri˜

oes da

Drosophila Melanogaster, a mosca da fruta. . . . . . . . . . . . . . . . . . . . 142

xiii

Lista de Tabelas

3.1

Relaç˜

ao entre os tipos de funç˜

ao e respectivas transformadas de Fourier . . .

25

3.2

Propriedades da transformada de Fourier . . . . . . . . . . . . . . . . . . . .

26

5.1

Configuraç˜

ao da base de imagens preparada para experimentaç˜

ao. . . . . . .

70

5.2

Exemplos de subgrupos de imagens similares . . . . . . . . . . . . . . . . . .

71

5.3

Área sob as curvas de precis˜

ao vs. revocaç˜

ao do gráfico da Figura 5.6. . . . .

72

6.1

FlyBase - Base de imagens ISH da mosca Drosophila

. . . . . . . . . . . . .

96

6.2

Relaç˜

ao de imagens processadas com sucesso pelo módulo de processamento

de imagens FEMine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

6.3

Número de Eigen-Embryos obtidos para cada amostra de 2.000 imagens de

cada estágio de desenvolvimento.

. . . . . . . . . . . . . . . . . . . . . . . .

98

7.1

Precis˜

ao na segmentaç˜

ao de imagens cl´ınicas reais . . . . . . . . . . . . . . . 122

7.2

Eficiência na segmentaç˜

ao de imagens sintéticas - BSE

. . . . . . . . . . . . 125

7.3

Eficiência na segmentaç˜

ao de imagens sintéticas - método HEAD . . . . . . . 125

xv

Lista de abreviaturas

ACM

Association for Computing Machinery

BDGP

Berkeley Drosophila Genome Project

BSE

Brain Surface Extractor

CBIR

Content-Based Image Retrieval

CBMS

Computer-Based Medical Systems

EM

Expectation and Maximization

FEMine

Fly Embryo Miner

GMM

Gaussian Mixture Model

HC

Hospital das Cl´ınicas

HEAD

Human Encephalon Automatic Delimiter

HIS

Hospital Information System

INU

Intensity Non-Uniformity

ISH

In Situ Hybridization

KDD

Knowledge Discovery and Data Mining

kNN

k Nearest Neighbors

MNI

Montreal Neurology Institute

MPM

Maximization of the Posterior Marginals

MRF

Markov Random Fields

MRI

Magnetic Resonance Imaging

PACS

Picture Archiving and Communication System

PET

Positron Emission Tomography

PR

Precis˜

ao e Revocaç˜

ao

RBIR

Region-Based Image Retrieval

RM

Ressonância Magnética

SGBD

Sistema de Gerenciamento de Base de Dados

xvii

Cap´ıtulo

1

Introduç˜

ao

As imagens digitais têm desempenhado um papel important´ıssimo em diversas áreas da

ciência, especialmente na medicina. Elas introduzem versatilidade no processo de aquisiç˜

ao e

troca de exames médicos, e possibilitam o armazenamento de imensas quantidades de exames

que formam verdadeiras bases de conhecimento, essenciais para o estudo e aperfeiçoamento

da ciência médica. Os PACS, do inglês Picture Archiving and Communication Systems,

ao os sistemas que realizam esse armazenamento possibilitam a distribuiç˜

ao das imagens

médicas em terminais locais ou remotos de um hospital ou centro médico. Introduzidos no

in´ıcio da década de 80 [7], os PACS expandiram as possibilidades do sistema convencional de

armazenamento de exames em filme, viabilizando, principalmente, a educaç˜

ao e o diagnóstico

à distância, muito importantes para o aux´ılio às regi˜

oes mais remotas.

Nas últimas décadas, os equipamentos de coleta de exames no formato digital se torna-

ram extremamente populares e passaram a interagir diretamente com os PACS. Praticamente

todas as modalidades de exame por imagem foram adaptadas a este esquema, incluindo a ul-

trasonografia, ressonância magnética, tomografia computadorizada, radiografia, mamografia,

endoscopia, tomografia por emiss˜

ao de positrons (PET), entre outras. Além disso, muitos

centros médicos ainda realizam a digitalizaç˜

ao dos filmes convencionais para integrar um

único sistema de armazenamento digital. As informaç˜

oes e histórico hospitalar dos pacientes

ao gerenciados pelos Sistemas de Informaç˜

ao Hospitalares (HIS) que também possuem um

canal de comunicaç˜

ao com os PACS.

A Genética é também uma ciência cuja introduç˜

ao das imagens digitais vem permitindo

seu avanço em diversos aspectos. A corrida pelo mapeamento dos genomas, incluindo o

genoma humano, iniciou-se na década de 80 e durou quase 20 anos. Esta fase gerou um

imenso volume de informaç˜

ao em diversos formatos, incluindo seqüências genéticas e imagens

de mapeamento espacial e temporal dos incontáveis genes. Tais imagens s˜

ao denominadas

“imagens de express˜

ao genética” e revelam, principalmente, quais genes est˜

ao por trás do

desenvolvimento dos diversos órg˜

aos e tecidos de um determinado organismo.

1

2

Cap´ıtulo 1

1.1

Motivaç˜

ao

O crescente volume de imagens digitais que s˜

ao adquiridas nos centros médicos e em muitas

atividades de pesquisa deu origem a um desafio que vai além do problema do armazenamento.

A organizaç˜

ao dos dados e a possibilidade de acessá-los em um determinado momento s˜

ao ele-

mentos fundamentais para os Sistemas de Gerenciamento de Bases de Dados, ou SGBD. Para

informaç˜

oes textuais, a criaç˜

ao de ´ındices é uma tarefa relativamente simples e proporciona

uma forma eficiente de recuperaç˜

ao dos dados. As imagens digitais, entretanto, constituem

dados complexos cujo conteúdo pode ser interpretado de diversas maneiras. Neste contexto,

diversas quest˜

oes podem ser levantadas, como por exemplo: Como interpretar ou represen-

tar o conteúdo de uma imagem? Quais medidas que podem caracterizar adequadamente

este conteúdo? Como recuperar imagens de um grande repositório utilizando o conteúdo

extra´ıdo? Como estabelecer um critério de similaridade entre estas imagens?

Estas e outras quest˜

oes constituem o ramo de pesquisa computacional comumente conhe-

cido por CBIR (Content Based Image Retrieval), ou Recuperaç˜

ao de Imagens por Conteúdo,

que é o tema principal deste trabalho de pesquisa. A importância deste tema está no fato de

que estabelecer um relacionamento entre as imagens a partir de seu conteúdo é a chave para

se extrair informaç˜

ao relevante do repositório. Um médico diante de um exame, por exem-

plo, pode querer consultar outros exames parecidos com a intenç˜

ao de reforçar o seu parecer

cl´ınico sobre um caso em análise. Em um hospital-escola, os alunos de medicina podem

recuperar imagens similares de diversos pacientes visando compreender o padr˜

ao de uma

determinada doença. Em um banco de imagens de express˜

ao genética é poss´ıvel descobrir

quais genes de um organismo s˜

ao correlacionados.

O principal desafio em CBIR consiste no desenvolvimento de técnicas computacionais

eficientes para mapeamento automático do conteúdo da imagem em um conjunto/vetor de

caracter´ısticas compacto que possibilite estabelecer a similaridade entre as imagens. Diver-

sas aplicaç˜

oes podem ser derivadas com base em determinado conjunto de caracter´ısticas,

incluindo a classificaç˜

ao e o agrupamento das imagens, com o objetivo de se revelar padr˜

oes

relevantes dentro do repositório. Uma aplicaç˜

ao que merece destaque, e é de grande inte-

resse no meio cl´ınico, é a que envolve as operaç˜

oes de consultas por imagens similares [8, 9].

Em tais operaç˜

oes, um usuário que acessa o banco de imagens a partir de um terminal de

consultas apresenta uma imagem de referência para que sejam localizadas as imagens mais

semelhantes. Esse é o tipo de busca que o médico usualmente faz ao comparar mentalmente

o caso que possui nas m˜

aos com o conhecimento armazenado em seu cérebro durante anos de

experiência. Por exemplo, dada uma imagem de Raio-X de tórax de um paciente deseja-se

encontrar as N imagens do repositório que s˜

ao mais semelhantes a ela, segundo um critério

de semelhança.

As técnicas que possibilitam a recuperaç˜

ao de imagens similares têm sido foco de estudo

de um crescente número de pesquisas e demandam a integraç˜

ao de conhecimento das áreas

de processamento de imagens, aprendizado de máquina, bases de dados, entre outras. Os

Introduç˜

ao

3

PACS comerciais permitem recuperar as imagens de exames médicos apenas a partir de

chaves textuais e numéricas, isto é, processam consultas do tipo “retorne os exames de Raio-

X de tórax do paciente José da Silva”. Com o aperfeiçoamento de técnicas CBIR dedicadas

à área médica os PACS poder˜

ao estender suas funcionalidades de recuperaç˜

ao de imagens

passando a ser n˜

ao apenas um sistema de armazenamento e transmiss˜

ao de imagens, mas uma

ferramenta importante para os médicos no apoio ao diagnóstico e também como instrumento

de ensino para radiologia [10, 11].

1.2

Objetivos

O objetivo principal deste trabalho é o estudo e desenvolvimento de técnicas de extraç˜

ao

de caracter´ısticas e segmentaç˜

ao de imagens nos dom´ınios de contexto cl´ınico/médico e da

biologia genética, buscando responder quest˜

oes relacionadas com a desafiadora área de Recu-

peraç˜

ao de Imagens por Conteúdo. Mais especificamente, neste trabalho, a segmentaç˜

ao da

imagem é considerada uma etapa fundamental na interpretaç˜

ao e representaç˜

ao da imagem,

pois ela permite a extraç˜

ao de caracter´ısticas de regi˜

oes de interesse da imagem, ao contrário

dos métodos que buscam uma representaç˜

ao global e direta da mesma, que é inadequada

para a maior parte dos dom´ınios.

1.3

Principais contribuiç˜

oes

O trabalho desenvolvido e apresentado nesta tese traz os seguintes resultados como principais

contribuiç˜

oes para a área de CBIR:

• Uma nova técnica de extraç˜

ao de caracter´ısticas de imagens cl´ınicas de ressonância

magnética para realizaç˜

ao de consultas por similaridade em sistemas CBIR. O ponto

principal desta abordagem é a proposta de um vetor de caracter´ısticas compacto, de ta-

manho fixo e altamente eficaz em consultas por similaridade de imagens. Este vetor de

caracter´ısticas agrupa medidas relevantes de regi˜

oes da imagem que correspondem aos

diversos tecidos da parte do corpo examinada. Isto é poss´ıvel devido à utilizaç˜

ao de um

método adequado de segmentaç˜

ao de imagens, que combina a técnica de agrupamento

EM Expectation Maximization com o modelo espacial de Markov. Neste trabalho o

método foi melhorado para fornecer uma convergência mais rápida do processo de seg-

mentaç˜

ao. Em relaç˜

ao às caracter´ısticas propostas, destaca-se a utilizaç˜

ao da Dimens˜

ao

Fractal, uma medida que possibilita com um único valor numérico, diferenciar regi˜

oes

de formato linear, planares e puntiformes. O novo extrator de caracter´ısticas proposto

é apresentado em detalhes no Cap´ıtulo 5 incluindo os respectivos experimentos e re-

sultados obtidos. Um artigo publicado e apresentado no CBMS’2005 [12] sintetiza a

técnica proposta.

4

Cap´ıtulo 1

• Um sistema para segmentaç˜

ao e extraç˜

ao de caracter´ısticas de imagens de padr˜

oes

de express˜

ao genética contidos em imagens embrionárias da Drosophila Melanogaster,

popularmente conhecida como “mosca da fruta”. O sistema, denominado FEMine

(Fly Embryo Miner), apresenta três módulos principais: um módulo de processamento

automático das imagens que é responsável pela identificaç˜

ao, separaç˜

ao e registros dos

embri˜

oes; um módulo de extraç˜

ao de caracter´ısticas para representaç˜

ao do conteúdo

visual dos padr˜

oes de express˜

ao genética e um módulo de interface para realizaç˜

ao de

consultas de imagens por similaridade. Além de representar uma soluç˜

ao completa e

inovadora para o um problema de grande relevância na área da biologia genética, o

sistema FEMine inclui técnicas inovadoras por si só, como é o caso de uma nova técnica

de separaç˜

ao de part´ıculas sobrepostas em imagens binárias baseada nos conceitos da

técnica de watershed e na seleç˜

ao automática de marcadores das part´ıculas. Para

extraç˜

ao de caracter´ısticas das imagens o sistema FEMine introduz os Eigen-Embryos,

um novo espaço de caracter´ısticas para os padr˜

oes de express˜

ao que permite a realizaç˜

ao

eficiente de consultas por similaridade. O sistema FEMine é apresentado em detalhes

no Cap´ıtulo 6, incluindo os respectivos experimentos e resultados obtidos. Um artigo

publicado e apresentado no ACM KDD’2006 [13] sintetiza o sistema proposto.

• Um novo método para segmentaç˜

ao de imagens 3D de exames de cabeça. O método,

denominado HEAD - the Human Encephalon Automatic Delimiter, é uma soluç˜

ao efi-

ciente para o problema de delimitaç˜

ao automática do cérebro em exames cl´ınicos. Ele

combina técnicas da área de morfologia matemática e, especialmente, introduz uma

nova abordagem de particionamento automático de histogramas que se sobressai entre

conceituados métodos conhecidos na literatura, incluindo os métodos de Otsu e Rosen-

feld. Esta técnica é aplicada diretamente no problema de segmentaç˜

ao para encontrar

os limites de n´ıveis de cinza dos tecidos do cérebro. O método HEAD foi desenvolvido

visando a extraç˜

ao de caracter´ısticas de mais alto n´ıvel das imagens médicas, incluindo

a volumetria de tecidos do cérebro, medidas de simetria, e determinaç˜

ao de proprieda-

des das estruturas anatômicas mais importantes no contexto médico. Em CBIR, esta

é uma aplicaç˜

ao de grande importância pois está relacionada diretamente com um dos

maiores problemas da área: o conhecido gap semântico. Um artigo [14] aceito recen-

temente para publicaç˜

ao no CBMS’2007, sintetiza o método HEAD, enquanto outro

artigo submetido [15] apresenta o método com mais detalhes. Neste documento, o

método HEAD, incluindo os respectivos experimentos realizados e resultados obtidos,

é apresentado no Cap´ıtulo 7.

1.4

Organizaç˜

ao da tese

Em resumo, este documento é organizado da seguinte maneira:

Introduç˜

ao

5

• Cap´ıtulo 2 - apresenta os principais conceitos relacionados à área de recuperaç˜

ao de

imagens por conteúdo (CBIR), envolvendo, principalmente aspectos relacionados com

a extraç˜

ao de caracter´ısticas da imagem, medidas de similaridade em espaços métricos

e avaliaç˜

ao de desempenho.

• Cap´ıtulo 3 - apresenta em detalhes alguns dos principais métodos de extraç˜

ao de ca-

racter´ısticas de imagens baseados em textura e forma, que est˜

ao mais relacionados ao

trabalho desenvolvido e apresentado nesta tese, incluindo os descritores de Fourier, os

momentos de Zernike, e as medidas das transformadas bi-dimensionais de Wavelets e

Fourier.

• Cap´ıtulo 4 - apresenta os principais conceitos relacionados à segmentaç˜

ao de imagens

e descreve alguns dos principais técnicas da literatura, incluindo os métodos cujos

conceitos s˜

ao utilizados no desenvolvimento deste trabalho, especialmente o método

EM/MPM e a segmentaç˜

ao pela transformada de watershed.

• Cap´ıtulo 5 - apresenta a proposta e desenvolvimento do novo extrator de caracter´ısticas

de imagens médicas de ressonância magnética que combina o método de segmentaç˜

ao

EM/MPM e a extraç˜

ao de medidas de regi˜

oes relacionadas aos diferentes tecidos da

parte do corpo examinada.

• Cap´ıtulo 6 - apresenta a proposta e desenvolvimento do sistema FEMine, para pro-

cessamento e extraç˜

ao de caracter´ısticas de imagens de padr˜

oes espaciais de express˜

ao

genética.

• Cap´ıtulo 7 - apresenta a proposta e desenvolvimento do método HEAD, para seg-

mentaç˜

ao de imagens 3D de exames de cabeça para extraç˜

ao de medidas e carac-

ter´ısticas do cérebro.

• Cap´ıtulo 8 - apresenta as consideraç˜

oes finais, um resumo das principais contribuiç˜

oes

deste trabalho e as propostas de trabalhos de extens˜

ao.

• Apêndice A - apresenta uma breve revis˜

ao dos conceitos da teoria dos Fractais empre-

gados na realizaç˜

ao deste trabalho.

• Apêndice B - apresenta uma revis˜

ao dos principais conceitos de genética e dos métodos

utilizados para obtenç˜

ao das imagens de padr˜

oes espaciais de express˜

ao genética.

Cap´ıtulo

2

Recuperaç˜

ao de Imagens Baseada em

Conteúdo

A recuperaç˜

ao de imagens por conteúdo (CBIR) é um ramo da Ciência da Computaç˜

ao que

aborda tecnologias e métodos voltados para organizaç˜

ao de grandes repositórios de imagens

digitais por meio do conteúdo visual. Deste modo, qualquer técnica desde uma funç˜

ao de

similaridade de imagem até um sistema robusto de anotaç˜

ao automática de imagens s˜

ao focos

de estudo em CBIR. Muitas outras áreas da computaç˜

ao est˜

ao estreitamente ligadas com

CBIR proporcionando uma integraç˜

ao que resulta em diversos estudos cient´ıficos [16]. Os

principais exemplos s˜

ao a vis˜

ao computacional, aprendizado de máquina, interaç˜

ao usuário-

computador, bases de dados, mineraç˜

ao de dados, teoria da informaç˜

ao, estat´ıstica, entre

outras.

A década de 90 é considerada a etapa inicial dos estudos envolvendo CBIR. Grande parte

do trabalho desenvolvido nesta fase foi discutido e apresentado na revis˜

ao (survey) de Smeul-

ders et al. [17], que tem sido uma importante referência para trabalhos mais atuais. Outras

revis˜

oes bastante abrangentes também trazem um panorama do estado da arte em CBIR até

o ano de 2000 [18, 19, 20]. Outros trabalhos de revis˜

ao também se concentram em tópicos de

CBIR mais espec´ıficos, como a realimentaç˜

ao por relevância (relevance feedback) [21, 22], re-

conhecimento de faces [23] e CBIR para imagens médicas [24]. Outro trabalho de revis˜

ao em

CBIR desenvolvido por Datta et al. [25], aborda trabalhos mais recentes em CBIR na década

atual até o ano de 2006, além de discutir os principais desafios em aberto e perspectivas de

pesquisa para os próximos anos.

Neste Cap´ıtulo é apresentada uma vis˜

ao geral da área de recuperaç˜

ao de imagens por

conteúdo sendo abordados os aspectos de pesquisa mais relevantes, incluindo a extraç˜

ao de

caracter´ısticas de baixo n´ıvel da imagem, medidas de similaridade e principais métodos de

validaç˜

ao para sistemas CBIR.

7

8

Cap´ıtulo 2

2.1

Tópicos em CBIR

A metodologia em CBIR, pela própria natureza da tarefa que se prop˜

oe a realizar, está

focalizada em dois problemas intr´ınsecos:

1. Como descrever matematicamente uma imagem?

2. Como inferir a similaridade entre duas imagens baseado em suas representaç˜

oes ma-

temáticas?

O primeiro problema surge porque a representaç˜

ao original de uma imagem, essencial-

mente uma matriz de pixels, n˜

ao agrega nenhum significado que possa corresponder dire-

tamente à nossa percepç˜

ao visual. Na perspectiva de projeto dos sistemas CBIR, a repre-

sentaç˜

ao matemática da imagem pode ser vista como a “assinatura da imagem”, ou um

conjunto de caracter´ısticas que refletem diversas propriedades da imagem. Neste caso, a

imagem passa a ser um ponto no espaço definido pelas suas caracter´ısticas. O segundo pro-

blema mencionado está relacionado diretamente com a métrica de distância entre os pontos

adotada para o novo espaço da imagem.

Neste contexto, os principais tópicos em CBIR podem ser listados da seguinte maneira:

• Extraç˜

ao de caracter´ısticas da imagem (feature extraction) - As caracter´ısticas

mais elementares das imagens s˜

ao aquelas que possibilitam o próprio sistema de vis˜

ao

humana identificar e, posteriormente classificar em n´ıvel semântico, os objetos de uma

determinada cena. S˜

ao elas: a cor, a textura e a forma, que s˜

ao medidas denominadas

primitivas ou de baixo n´ıvel [26]. Tais caracter´ısticas podem ser extra´ıdas automatica-

mente ou semi-automaticamente através de um processo computacional. Um ou mais

tipos de caracter´ısticas podem ser agrupados para formar um conjunto que descreva

adequadamente as imagens de um repositório espec´ıfico;

• Definiç˜

ao de funç˜

oes de distância - Uma vez extra´ıdas as caracter´ısticas da ima-

gem, a operaç˜

ao que possibilita inferir o n´ıvel de semelhança entre duas imagens do

repositório é baseada em uma funç˜

ao de distância. É importante definir uma métrica

adequada ao conjunto de caracter´ısticas proposto, para que a inferência de similaridade

entre as imagens possa corresponder o mais próximo poss´ıvel à similaridade que seria

definida por um usuário do sistema;

• Indexaç˜

ao das caracter´ısticas - Para facilitar e agilizar as operaç˜

oes de consultas e

pesquisas é necessário criar ´ındices de imagens e organizá-los em estruturas de dados

apropriadas. Como estruturas mais utilizadas para se armazenar tais ´ındices destacam-

se as árvores k-d (k-d trees) [27], as Slim-trees [28, 29], a fam´ılia de árvores R (R

trees) [30], árvores R*[31] e as quadtrees [32].

Recuperaç˜

ao de Imagens Baseada em Conteúdo

9

• Interface com o usuário - Basicamente, a interaç˜

ao do sistema com o usuário é feita

por meio de um interpretador de consultas e um navegador que possibilite visualizar

os resultados. Funcionalidades comuns dispon´ıveis na interface de um sistema CBIR

incluem: a consulta por imagens similares dada uma imagem de referência, consultas

a partir da seleç˜

ao direta de caracter´ısticas, realimentaç˜

ao de relevância e refinamento

de consultas.

Um sistema CBIR padr˜

ao é constitu´ıdo por módulos que integram técnicas desses quatro

tópicos descritos. A Figura 2.1 apresenta uma vis˜

ao geral de como esses módulos devem

interagir para possibilitar, por exemplo, a consultas de imagens similares dada uma “imagem

de referência”.

Offline

Extração de Características