UNIVERSIDADE FEDERAL DE SA˜O CARLOS
CENTRO DE CIEˆNCIAS EXATAS E DE TECNOLOGIA
PROGRAMA DE PO´S-GRADUAC¸A˜O EM CIEˆNCIA DA COMPUTAC¸A˜O
USO DE MU´LTIPLOS DESCRITORES COM
CONDIC¸O˜ES DE CONTORNO E
VISUALIZAC¸A˜O HIERA´RQUICA EM CBIR
LUIZ GUSTAVO DOS SANTOS REAL
ORIENTADOR: PROFA. DRA. MARCELA XAVIER RIBEIRO
Sa˜o Carlos – SP
Marc¸o/2017
UNIVERSIDADE FEDERAL DE SA˜O CARLOS
CENTRO DE CIEˆNCIAS EXATAS E DE TECNOLOGIA
PROGRAMA DE PO´S-GRADUAC¸A˜O EM CIEˆNCIA DA COMPUTAC¸A˜O
USO DE MU´LTIPLOS DESCRITORES COM
CONDIC¸O˜ES DE CONTORNO E
VISUALIZAC¸A˜O HIERA´RQUICA EM CBIR
LUIZ GUSTAVO DOS SANTOS REAL
Dissertac¸a˜o apresentada ao Programa de Po´s-
Graduac¸a˜o em Cieˆncia da Computac¸a˜o da Univer-
sidade Federal de Sa˜o Carlos, como parte dos requi-
sitos para a obtenc¸a˜o do tı´tulo de Mestre em Cieˆncia
da Computac¸a˜o, a´rea de concentrac¸a˜o: Banco de Da-
dos.
Orientador: Profa. Dra. Marcela Xavier Ribeiro
Sa˜o Carlos – SP
Marc¸o/2017

A Deus, de quem prove´m todo conhecimento.
AGRADECIMENTOS
Aos colegas de trabalho da Diretoria Te´cnica de Informa´tica da Unesp - FOA (Faculdade de
Odontologia de Arac¸atuba) e aos diretores da faculdade, pelo apoio, pacieˆncia e compreensa˜o.
Aos amigos que ajudaram durante todo o processo de busca pelo tı´tulo de mestre. Em
especial ao Fla´vio por todas as maratonas de programac¸a˜o, ao Caueˆ pelas traduc¸o˜es e reviso˜es
e ao Nelson por todo o suporte.
Aos meus avo´s, pelo apoio que me deram. Eu na˜o teria conseguido sem eles. Aos meus
pais, tios e irma˜s, pelo incentivo e apoio.
Aos colegas da UFSCar, principalmente a` minha compreensiva orientadora Profa. Dra.
Marcela Xavier Ribeiro e aos docentes, discentes e demais pesquisadores ligados ao Laborato´rio
de Banco de Dados e Engenharia de Software (LABDES) e ao Grupo de Banco de Dados
(GBD).
Aos meus professores da graduac¸a˜o, em especial ao meu orientador Prof. Me. Anderson
Pazin e ao coordenador Prof. Me. Eduardo Bergamo, que tambe´m fizeram mestrado na UFSCar,
e ao meu amigo Prof. Me. Joa˜o Artur Izzo, pelo apoio, incentivo e exemplo.
A todos que de alguma forma contribuı´ram para a realizac¸a˜o deste projeto.
Tudo me e´ permitido, mas nem tudo me conve´m.
Sa˜o Paulo
RESUMO
Mu´ltiplos descritores teˆm sido testados e utilizados em sistemas de recuperac¸a˜o de imagens
por conteu´do (do ingleˆs, Content-Based Image Retrieval - CBIR). Cada descritor e´ com-
posto de um extrator de caracterı´stica associado a uma func¸a˜o de distaˆncia. Um extrator e´
em geral adequado para representar um subconjunto especı´fico de imagens em uma base.
As condic¸o˜es de contorno sa˜o informac¸o˜es utilizadas para detectar esse subconjunto. O uso
de visualizac¸a˜o em CBIR possibilita representar de uma forma picto´rica a relac¸a˜o de simila-
ridade existente entre as imagens presentes na base, melhorando o entendimento do usua´rio
sobre o funcionamento do sistema CBIR, podendo este modificar paraˆmetros para se obter
melhores resultados. E´ comprovado que o uso de mu´ltiplos descritores com condic¸o˜es de
contorno tende a melhorar a precisa˜o das consultas em CBIR, pore´m na˜o ha´ dados sobre
o impacto que o mesmo gera na visualizac¸a˜o. Este trabalho utiliza mu´ltiplos descritores
com condic¸o˜es de contorno para gerar uma visualizac¸a˜o baseada em a´rvore de similaridade
Neighbor Joining. Os experimentos demonstraram que a qualidade da visualizac¸a˜o pode
estar relacionada com a qualidade do resultado da consulta. Quanto mais precisos os resul-
tados de uma consulta, melhor e´ a organizac¸a˜o dos elementos na visualizac¸a˜o. No contexto
de a´rvore de similaridade, foi comprovado que a qualidade da a´rvore gerada acompanha o
nı´vel de precisa˜o medido na consulta.
Palavras-chave: Content-Based Image Retrieval, CBIR, Visualizac¸a˜o Hiera´rquica, A´rvore de Similari-
dade, Neighbor Joining, Mu´ltiplos Descritores, Condic¸o˜es de Contorno.
ABSTRACT
Multiple descriptors have been tested and used in Content-Based Image Retrieval (CBIR)
systems. Each descriptor consists of a feature extractor associated with a distance function.
An extractor is generally suitable for representing a specific subset of images on a base. The
boundary conditions are information used to detect this subset. The use of visualization in
CBIR enables to represent pictorially the similarity relationship between the images present
in the base, improving the user’s understanding of the CBIR system, which can modify
parameters to obtain better results. It is proven that the use of multiple descriptors with
boundary conditions tends to improve the accuracy of CBIR queries, but there is no data on
the impact that the technique generates on visualization. This work uses multiple descriptors
with boundary conditions to generate a Neighbor Joining similarity tree-based view. Tests
have shown that the quality of the visualization may be related to the quality of the query
result. The more accurate the results of a query, the better the organization of the elements
in the visualization. In the context of similarity tree, it was verified that the quality of the
generated tree follow the level of precision measured in the query.
Keywords: Content-Based Image Retrieval, CBIR, Hierarchical Visualization, Similarity Tree, Neigh-
bor Joining, Multiple Descriptors, Boundary Conditions
LISTA DE FIGURAS
2.1 Visa˜o geral de um sistema CBIR (RIBEIRO, 2008). . . . . . . . . . . . . . . . . 20
2.2 Exemplo de histograma de cor de uma imagem com 256 nı´veis de cinza (BARI-
ONI, 2006). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Exemplo de imagens (a, b, c, d) com o mesmo histograma (e) (RIBEIRO, 2008). 22
2.4 Exemplos de texturas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Gra´fico de precisa˜o e revocac¸a˜o (BAEZA-YATES; RIBEIRO-NETO, 1999). . . . . . 28
2.6 Exemplo de visualizac¸a˜o em Grid (Ca´CERES, 2010) . . . . . . . . . . . . . . . 29
2.7 Exemplo de visualizac¸a˜o em Ane´is Conceˆntricos (Ca´CERES, 2010) . . . . . . . 30
2.8 Exemplo de visualizac¸a˜o utilizando Transformac¸a˜o Geome´trica (DIAS, 2013) . 31
2.9 Exemplo de hyperbolic-tree (LAMPING; RAO; PIROLLI, 1995). . . . . . . . . . . 32
2.10 Exemplo de cone-tree (CRUZ, 2012) . . . . . . . . . . . . . . . . . . . . . . . 32
2.11 Exemplo de visualizac¸a˜o em A´rvore (DIAS, 2013) . . . . . . . . . . . . . . . . 33
2.12 A´rvore de similaridade do conjunto de 700 imagens COIL usando o algoritmo
NJ. Cada ramo apresenta um agrupamento distinto, com as imagens do mesmo
grupo igual ao espac¸o original (imagens recuperadas perto de cada ramo) (CRUZ,
2012). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.13 Comparac¸a˜o entre uma projec¸a˜o LSP e uma a´rvore NJ, para uma colec¸a˜o de
675 documentos textuais (PAIVA, 2012). . . . . . . . . . . . . . . . . . . . . . 35
2.14 Exemplo de uma a´rvore NJ para a colec¸a˜o de imagens COREL (PAIVA, 2012). . 36
2.15 Operac¸a˜o de promoc¸a˜o de no´s. Cı´rculos preenchidos representam no´s da colec¸a˜o,
e triaˆngulos representam suba´rvores (PAIVA et al., 2011). . . . . . . . . . . . . . 38
2.16 Comparac¸a˜o entre a´rvores NJ e PNJ para a colec¸a˜o COREL, destacando os no´s
virtuais e arestas (PAIVA et al., 2011). . . . . . . . . . . . . . . . . . . . . . . . 38
3.1 Visa˜o geral do me´todo proposto. . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 Exemplo implementado do me´todo desenvolvido. . . . . . . . . . . . . . . . . 43
3.3 Exemplo de parte de uma matriz de distaˆncias. . . . . . . . . . . . . . . . . . . 44
3.4 Exemplo de grid contendo o resultado de uma consulta por similaridade. . . . . 44
3.5 Exemplo de a´rvore de similaridade construı´da pelo algoritmo NJ a partir de uma
matriz de distaˆncias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6 Exemplo de imagens da Base Balan. . . . . . . . . . . . . . . . . . . . . . . . 45
3.7 Imagem 0037 da Base Balan, pertencente a` classe 5. . . . . . . . . . . . . . . . 46
3.8 Resultado das consultas da imagem 0037 da classe 5 utilizando cada descritor
individualmente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.9 Gra´fico de precisa˜o e revocac¸a˜o medidas da consulta da imagem 0037 da classe
5 utilizando cada descritor individualmente. . . . . . . . . . . . . . . . . . . . 47
3.10 Visualizac¸a˜o gerada nas consulta da imagem 0037 da classe 5 utilizando cada
descritor individualmente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.11 Gra´fico de neighborhood hit da consulta da imagem 0037 da classe 5 utilizando
cada descritor individualmente. . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.12 Me´dia de precisa˜o medida para consultas de imagens da Classe 2. . . . . . . . 50
3.13 Me´dia de precisa˜o medida para consultas de imagens da Classe 3. . . . . . . . 50
3.14 Me´dia de precisa˜o medida para consultas de imagens da Classe 5. . . . . . . . 51
3.15 Me´dia de precisa˜o medida para consultas de imagens da Classe 7. . . . . . . . 51
3.16 A´rvores geradas para consulta de imagens da classe 2. . . . . . . . . . . . . . . 52
3.17 Neighborhood Hit para uma consulta de 5 vizinhos da classe 2. . . . . . . . . . 53
3.18 Gra´fico de precisa˜o e revocac¸a˜o para quatro testes realizados com uma imagem
da classe 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.19 A´rvores geradas para consulta de imagens da classe 5. . . . . . . . . . . . . . . 55
3.20 Neighborhood Hit para uma consulta de 5 vizinhos da classe 5. . . . . . . . . . 56
3.21 Gra´fico de precisa˜o e revocac¸a˜o para quatro testes realizados com uma imagem
da classe 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
LISTA DE TABELAS
2.1 Comparac¸a˜o entre tempos de Gerac¸a˜o do Layout (segundos), considerando as
abordagens de gerac¸a˜o ra´pida de a´rvores NJ e a te´cnica de projec¸a˜o LSP (PAIVA
et al., 2011). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1 Melhor combinac¸a˜o de pesos de descritores obtida para cada classe testada. . . 49
A.1 Lista de opc¸o˜es de linha de comando para extrac¸a˜o de caracterı´sticas com jFe-
atureLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
SUMA´RIO
CAPI´TULO 1 – INTRODUC¸A˜O 15
1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Motivac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Organizac¸a˜o do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
CAPI´TULO 2 – REFERECIAL TEO´RICO 19
2.1 Considerac¸o˜es Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Recuperac¸a˜o por Conteu´do . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 CBIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Extrac¸a˜o de Caracterı´sticas . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1.1 Cor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1.2 Textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1.3 Forma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 Mu´ltiplos Descritores e Condic¸o˜es de Contorno . . . . . . . . . . . . . 24
2.3.4 Avaliac¸a˜o dos resultados de uma consulta em CBIR . . . . . . . . . . . 26
2.4 Visualizac¸a˜o de Dados e Imagens . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 Considerac¸o˜es Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Te´cnicas de Visualizac¸a˜o de Imagens . . . . . . . . . . . . . . . . . . 29
2.4.3 A´rvore de Similaridade Neighbor Joining . . . . . . . . . . . . . . . . 32
2.4.3.1 Melhorias na construc¸a˜o de a´rvores de similaridade . . . . . 37
2.5 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
CAPI´TULO 3 – TRABALHO DESENVOLVIDO 41
3.1 Considerac¸o˜es Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Visa˜o Geral do Me´todo Desenvolvido . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Experimentos e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.1 Experimento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1.1 Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 Experimento 2A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.3 Experimento 2B - Neighborhood Hit . . . . . . . . . . . . . . . . . . . 53
3.3.3.1 Teste com imagens da classe 2 . . . . . . . . . . . . . . . . 53
3.3.3.2 Teste com imagens da classe 5 . . . . . . . . . . . . . . . . 53
3.4 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
CAPI´TULO 4 – CONCLUSO˜ES E TRABALHOS FUTUROS 57
4.1 Considerac¸o˜es Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Principais Contribuic¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Considerac¸o˜es Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
REFEREˆNCIAS 60
GLOSSA´RIO 64
APEˆNDICE A – UTILIZANDO A BIBLIOTECA JFEATURELIB PARA EXTRAIR
VETORES DE CARACTERI´STICAS DE IMAGENS EM JAVA 65
A.1 Extratores de caracterı´sticas implementados . . . . . . . . . . . . . . . . . . . 65
A.2 Como utilizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
A.2.1 Extrair caracterı´sticas de va´rias classes de imagens: . . . . . . . . . . . 66
A.2.2 Opc¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
A.3 Co´digo de demonstrac¸a˜o e Wiki . . . . . . . . . . . . . . . . . . . . . . . . . 67
Capı´tulo 1
INTRODUC¸A˜O
1.1 Contexto
Sistemas de Recuperac¸a˜o de Imagens por Conteu´do (Content-Based Image Retrieval -
CBIR) permitem que sejam realizadas consultas em bases de imagens, retornando as imagens
com maior grau de similaridade em relac¸a˜o a` imagem de consulta (KUMAR et al., 2013). Essa
similaridade entre as imagens da base e a imagem de consulta e´ verificada atrave´s de carac-
terı´sticas como cor, forma e textura, que sa˜o extraı´das e armazenadas em uma estrutura conhe-
cida como vetor de caracterı´sticas (BUENO et al., 2011). Depois, uma me´trica estipulada (func¸a˜o
de distaˆncia) avalia a distaˆncia entre os vetores selecionados.
A combinac¸a˜o de um algoritmo extrator de caracterı´stica e uma func¸a˜o de distaˆncia e´ ge-
ralmente referido na literatura como descritor (TORRES et al., 2009; BARROSO et al., 2015).
Os sistemas CBIR possuem o Gap Semaˆntico (inconsisteˆncia entre a percepc¸a˜o do ser hu-
mano na avaliac¸a˜o de similaridade entre imagens comparada com a computada por sistemas
CBIR) como uma das suas principais limitac¸o˜es (LIU et al., 2007). Para diminuir o gap semaˆntico
em consultas por similaridade, o uso de combinac¸o˜es de mu´ltiplos descritores tem sido consi-
derado por demonstrar bons resultados (BARROSO et al., 2015), pois subconjuntos de imagens de
um mesmo conjunto podem ser melhor representados por caracterı´sticas diferentes.
Barroso et al. (2013) propo˜e o uso de condic¸o˜es de contorno para encontrar esses subcon-
juntos e escolher a melhor combinac¸a˜o de descritores para cada um deles. Condic¸o˜es de con-
torno sa˜o quaisquer informac¸o˜es associadas a` imagem que possam ser utilizadas para delimitar
subconjuntos de imagens.
A u´ltima etapa de um sistema CBIR e´ a visualizac¸a˜o dos resultados de uma consulta. Cada
sistema CBIR possui uma forma diferente de apresentar esses resultados (Ca´CERES, 2010).
1.2 Motivac¸a˜o 16
Um dos desafios das pesquisas conhecidas na a´rea de recuperac¸a˜o de imagens e´ exibir
grandes quantidades de imagens de maneira intuitiva para o usua´rio. Va´rios autores defendem
que uma representac¸a˜o visual auxilia a ana´lise e a identificac¸a˜o de padro˜es existentes na colec¸a˜o
de dados, permitindo que o usua´rio entenda o comportamento do espac¸o de caracterı´sticas dos
dados (CRUZ, 2012).
Uma possibilidade de visualizac¸a˜o de imagens e´ disponibiliza´-las de forma hiera´rquica
(ELER et al., 2009). Ou seja, fazer uma projec¸a˜o das imagens atrave´s da representac¸a˜o encon-
trada na fase de extrac¸a˜o de caracterı´sticas, levando-se em conta uma hierarquia estabelecida
pela similaridade entre as mesmas. Desta forma, a construc¸a˜o dessas relac¸o˜es de similaridade
pode assumir uma estrutura semelhante a` de uma a´rvore, a qual pode ser estruturada segundo
diferentes metodologias.
1.2 Motivac¸a˜o
E´ comprovado que o uso de mu´ltiplos descritores com condic¸o˜es de contorno tende a me-
lhorar a precisa˜o das consultas em CBIR (BARROSO et al., 2015), pore´m na˜o foi analisado o
impacto que esse uso gera na visualizac¸a˜o.
A qualidade da visualizac¸a˜o pode estar relacionada com a qualidade da resposta da consulta
de sistemas CBIR. Assim, a primeira hipo´tese deste trabalho e´:
Hipo´tese 1: Quanto mais precisos os resultados de uma consulta, melhor pode ser a organizac¸a˜o
das imagens na visualizac¸a˜o.
No caso da hipo´tese 1 ser verdadeira, definimos:
Hipo´tese 2: O uso de mu´ltiplos descritores com condic¸a˜o de contorno pode melhorar a
qualidade da visualizac¸a˜o hiera´rquica de imagens em CBIR, pois ja´ foi comprovado que seu
uso melhora o resultado de consultas por similaridade de imagens.
Dentre as te´cnicas de visualizac¸a˜o de imagens existentes, a visualizac¸a˜o hiera´rquica foi
escolhida em detrimento as outras te´cnicas, por exemplo, as te´cnicas baseadas em projec¸o˜es
multidimensionais, porque ate´ o momento sa˜o poucos trabalhos na literatura que tratam da
visualizac¸a˜o hiera´rquica em sistemas CBIR (CRUZ, 2012; PAIVA, 2012) e na˜o foi encontrado
nenhum trabalho que trata desse assunto aliado ao uso de mu´ltiplos descritores com condic¸o˜es
de contorno (BARROSO et al., 2013, 2015).
Ademais, a noc¸a˜o de hierarquia pode indicar as imagens mais representativas de uma classe,
o que pode ser interessante em CBIR.
1.3 Objetivos 17
1.3 Objetivos
Um dos objetivos do trabalho e´ demostrar que a qualidade da visualizac¸a˜o esta´ relacionada
com a qualidade da consulta (visualizac¸a˜o de ma´ qualidade esta´ relacionada a um resultado da
consulta de qualidade ruim; visualizac¸a˜o de boa qualidade esta´ relacionada a um resultado da
consulta tambe´m de qualidade boa).
Tambe´m espera-se demonstrar que o uso de mu´ltiplos descritores com condic¸o˜es de con-
torno melhora a qualidade da visualizac¸a˜o hiera´rquica de imagens em CBIR. O uso de combinac¸o˜es
de mu´ltiplos descritores pode representar melhor as caracterı´sticas distintas encontradas em
subconjuntos de imagens de uma base de imagens. Ja´ as condic¸o˜es de contorno sa˜o utilizadas
para encontrar esses subconjuntos e escolher a melhor combinac¸a˜o de descritores para cada um
deles.
A te´cnica de visualizac¸a˜o hiera´rquica escolhida para o trabalho e´ a Neighbor Joining (SAI-
TOU; NEI, 1987). E´ um dos me´todos mais utilizados para a construc¸a˜o de uma a´rvore filo-
gene´tica. Essa te´cnica, adaptada para a criac¸a˜o de a´rvores de similaridade, utiliza a ideia de
encontrar pares de instaˆncias mais pro´ximas em uma colec¸a˜o de dados, de modo a minimizar
o comprimento e o nu´mero de ramos da a´rvore gerada (PAIVA, 2012). Ela tem sido utilizada
no contexto de classificac¸a˜o visual de dados (ELER et al., 2008, 2009; PAIVA et al., 2011; CRUZ,
2012; PAIVA, 2012).
Ao posicionar os elementos da consulta em ramos de uma a´rvore, a similaridade e´ or-
ganizada em nı´veis, representando uma abordagem natural para a interpretac¸a˜o de graus de
similaridade.
A medida de qualidade da visualizac¸a˜o de imagens usada no trabalho e´ a neighborhood
hit (PAULOVICH et al., 2008), que mede a porcentagem de vizinhos mais pro´ximos de uma ima-
gem na visualizac¸a˜o, que pertencem a` mesma classe. A precisa˜o final representa a me´dia das
preciso˜es para cada ponto. Isso permite avaliar numericamente a separabilidade das classes
pre´-existentes no layout.
1.4 Organizac¸a˜o do Trabalho
Primeiramente, o capı´tulo 2 trata de todos os conceitos relacionados ao trabalho, como
CBIR, uso de mu´ltiplos descritores com condic¸o˜es de contorno, visualizac¸a˜o de dados e ima-
gens e Neighbor Joining. No capı´tulo 3 sa˜o apresentados alguns trabalhos relacionados ao uso
de mu´ltiplos descritores e visualizac¸a˜o hiera´rquica. O capı´tulo 4 apresenta o trabalho desenvol-
1.4 Organizac¸a˜o do Trabalho 18
vido, inclusive os experimentos realizados e seus resultados. Por u´ltimo, o capı´tulo 5 apresenta
as concluso˜es e trabalhos futuros.
Capı´tulo 2
REFERECIAL TEO´RICO
2.1 Considerac¸o˜es Iniciais
Neste capı´tulo sa˜o apresentados os principais conceitos relacionados ao projeto de mes-
trado. Primeiramente e´ introduzido o conceito de Recuperac¸a˜o por Conteu´do e aprofundado
especificamente o conceito de recuperac¸a˜o de imagens por conteu´do, expondo todas as suas
etapas, terminando com uma breve introduc¸a˜o de visualizac¸a˜o de dados e imagens. Em se-
guida e´ apresentado o conceito de Visualizac¸a˜o Hiera´rquica, utilizando a´rvore de similaridade
Neighbor Joining, me´todo utilizado neste trabalho de mestrado. Por fim, sa˜o apresentados os
Trabalhos Correlatos, que justificam a escolha do tema deste projeto.
2.2 Recuperac¸a˜o por Conteu´do
Dados complexos, que sa˜o dados que na˜o sa˜o de tipos simples (inteiro, string, etc.), sa˜o
armazenados atualmente em bancos de dados como atributos de tipo BLOB (Binary Large
Object). Estando em forma bina´ria, esses dados na˜o sa˜o interpreta´veis, necessitando de outros
atributos textuais e/ou nume´ricos para auxiliar em sua recuperac¸a˜o (BARIONI, 2006; RIBEIRO,
2008).
Para comparar dados multimı´dia, sa˜o utilizadas as caracterı´sticas extraı´das desses dados.
Esse tipo de busca, atrave´s das caracterı´sticas, e´ denominado Recuperac¸a˜o por Conteu´do (BA-
RIONI, 2006). A recuperac¸a˜o de dados complexos por conteu´do e´ utilizada para va´rios tipos de
dados, como imagens e a´udio.
2.3 CBIR 20
2.3 CBIR
Recuperac¸a˜o de imagem por conteu´do, ou CBIR, e´ uma te´cnica criada para auxiliar o
usua´rio a encontrar imagens similares a` imagem de consulta em diversos tipos de aplicac¸o˜es
multimı´dia (AKGu¨L et al., 2011; KUMAR et al., 2013).
Os sistemas CBIR realizam consultas em uma base de imagens com base no crite´rio de
semelhanc¸a. Esses sistemas envolvem um conjunto de me´todos que processam as imagens
a fim de obter a representac¸a˜o das mesmas em vetores de caracterı´sticas. Esses vetores de
caracterı´sticas sa˜o utilizados no lugar da imagem para a execuc¸a˜o de consultas (RIBEIRO, 2008).
Em geral, os sistemas CBIR envolvem o pre´-processamento da imagem, a extrac¸a˜o de ca-
racterı´sticas, te´cnicas de indexac¸a˜o e avaliac¸a˜o de similaridade entre as imagens. O resultado
de uma consulta em um sistema CBIR e´ um conjunto de imagens ordenadas de acordo com sua
similaridade a` imagem de consulta (DIAS, 2013).
A visa˜o geral com os passos executados por um sistema CBIR podem ser vistos na Figura
2.1.
Figura 2.1: Visa˜o geral de um sistema CBIR (RIBEIRO, 2008).
2.3.1 Extrac¸a˜o de Caracterı´sticas
Para que as imagens possam ser trabalhadas computacionalmente, e´ necessa´rio encontrar
uma representac¸a˜o nume´rica que sintetize o conteu´do das mesmas, levando-se em considerac¸a˜o
caracterı´sticas visuais especı´ficas, como cor, textura e forma (RIBEIRO, 2008).
2.3 CBIR 21
As imagens podem ser submetidas a um pre´-processamento (transformada, segmentac¸a˜o)
ou a extratores de caracterı´sticas, que sa˜o algoritmos que extraem as caracterı´sticas visuais da
imagem. Essas caracterı´sticas enta˜o sa˜o utilizadas para criar o vetor de caracterı´sticas (BHATT;
KANKANHALLI, 2011).
2.3.1.1 Cor
Dentre as caracterı´sticas utilizadas na recuperac¸a˜o de imagens, a cor e´ a mais conhecida,
sendo adotada desde os primeiros sistemas CBIR propostos. Uma caracterizac¸a˜o global da
imagem pode ser obtida atrave´s do agrupamento de componentes de cor de cada pixel num
histograma (AKGu¨L et al., 2011). Um histograma de cor possui informac¸o˜es do nu´mero de pixels
para cada cor (ou nı´vel de cinza) em uma imagem, podendo ser usado na comparac¸a˜o com outro
histograma de cor pela soma das diferenc¸as absolutas ou quadra´ticas do nu´mero de pixels de
cada cor (RIBEIRO, 2008). Um exemplo de histograma de cor pode ser visto na Figura 2.2.
Figura 2.2: Exemplo de histograma de cor de uma imagem com 256 nı´veis de cinza (BARIONI,
2006).
Apesar de ser simples, o histograma de cor pode elevar o custo computacional e se tornar
inadequado na indexac¸a˜o, caso tenha um grande nu´mero de cores. Ele tambe´m possui baixa
capacidade de discriminac¸a˜o, ou seja, na˜o trata as informac¸o˜es especiais dos pixels, assim,
imagens diferentes podem ter distribuic¸o˜es de cores semelhantes (BARIONI, 2006), como pode
ser observado na Figura 2.3.
Enquanto a cor e´ uma das caracterı´sticas visuais mais utilizadas para a descric¸a˜o de ima-
gens, a maioria das imagens da a´rea da sau´de sa˜o em tons de cinza. Em alguns casos a cor pode
ser utilizada no diagno´stico, como em oftalmologia, patologia e dermatologia. Entretanto, para
a maioria das imagens dessa a´rea, as caracterı´sticas de cor na˜o sa˜o u´teis (AKGu¨L et al., 2011).
2.3 CBIR 22
Figura 2.3: Exemplo de imagens (a, b, c, d) com o mesmo histograma (e) (RIBEIRO, 2008).
2.3.1.2 Textura
Textura e´ uma caracterı´stica relacionada a` organizac¸a˜o espacial dos valores de pixel de
uma regia˜o da imagem (AKGu¨L et al., 2011). Na˜o existe uma definic¸a˜o formal para textura, de
forma intuitiva este extrator fornece medidas de propriedades tais como suavidade, aspereza, e
regularidade (HUANG; DAI, 2003). Textura se refere a` repetic¸a˜o de elementos ba´sicos da imagem
chamados textels (RIBEIRO, 2008). Alguns exemplos de texturas podem ser vistos na Figura 2.4.
Figura 2.4: Exemplos de texturas.
Os me´todos utilizados para representar a textura podem ser classificados nas seguintes ca-
tegorias: estatı´sticos, sinta´ticos e hı´bridos (SONKA; HLAVAC; BOYLE, 1999).
Os me´todos estatı´sticos inclinam-se a descrever texturas pequenas. Eles caracterizam a tex-
tura calculando propriedades como contraste, granularidade, periodicidade, entre outras. Matri-
zes de co-ocorreˆncia, transformadas de Gabor e Wavelets sa˜o exemplos de me´todos estatı´sticos.
Os me´todos sinta´ticos identificam elementos e indicam a disposic¸a˜o espacial dos mesmos.
Ja´ nos me´todos hı´bridos, compostos pela combinac¸a˜o dos dois me´todos anteriores, os elemen-
2.3 CBIR 23
tos sa˜o exatamente definidos e o relacionamento espacial entre esses elementos e´ baseado em
probabilidades.
Os me´todos sinta´ticos e hı´bridos inclinam-se a descrever texturas regulares e na˜o sa˜o utili-
zados com a mesma frequeˆncia que os me´todos estatı´sticos.
Na a´rea da sau´de, os extratores baseados em textura tornam-se particularmente importantes,
ja´ que podem refletir os detalhes contidos dentro da estrutura de imagem. Por exemplo, cada
tipo de lesa˜o pode conter um conjunto de caracterı´sticas distinto (AKGu¨L et al., 2011).
2.3.1.3 Forma
Uma das possibilidades encontradas na atividade de extrac¸a˜o de caracterı´sticas e´ a extrac¸a˜o
de formas presentes em imagens. O termo forma se refere a` informac¸a˜o que se pode deduzir
diretamente de imagens e que na˜o e´ representada por cor ou textura, com bordas / contornos
(AKGu¨L et al., 2011).
Alguns me´todos para representar forma sa˜o os me´todos geome´tricos para detecc¸a˜o de borda
e os me´todos escalares. Os me´todos geome´tricos detectam o comprimento de borda, curvatura
e assinatura (sequeˆncia de distaˆncias entre pontos da borda). Os escalares detectam regia˜o,
como a´rea, excentricidade (raza˜o entre o maior e o menor eixo, por exemplo) e retangularidade
(SONKA; HLAVAC; BOYLE, 1999).
Dentre os me´todos utilizados para representar imagens com base nos contornos presentes,
esta˜o os momentos de Zernike (KHOTANZAD; HONG, 1990) e o modelo de contornos ativos
Snakes (KASS; WITKIN; TERZOPOULOS, 1988).
Segundo Barioni (2006), um aspecto importante na recuperac¸a˜o por forma e´ a escolha da
caracterı´stica a ser utilizada para delimitar as formas nas imagens. E´ comum que seja utilizada
a cor, pore´m, em imagens me´dicas a textura e´ uma caracterı´stica mais interessante.
A escolha de te´cnicas de extrac¸a˜o de caracterı´sticas esta´ relacionada com o contexto em que
um determinado conjunto de imagens esta´ inserido, possibilitando encontrar uma representac¸a˜o
nume´rica que atenda as caracterı´sticas visuais especı´ficas deste contexto (DESELAERS; KEY-
SERS; NEY, 2004, 2008).
2.3.2 Similaridade
As consultas realizadas por aplicac¸o˜es que manipulam dados complexos sa˜o, na maioria dos
casos, baseadas na noc¸a˜o de similaridade (BARIONI, 2006). No domı´nio de imagens, o conceito
2.3 CBIR 24
de similaridade e´ o mais adequado, pois o objetivo e´ encontrar imagens semelhantes e na˜o
ideˆnticas. Na a´rea me´dica, por exemplo, pode haver a necessidade de encontrar imagens com
uma lesa˜o similar a` lesa˜o presente na imagem de consulta, o que na˜o seria possı´vel utilizando
o conceito de igualdade, pois ate´ duas imagens de uma mesma lesa˜o tiradas em momentos
diferentes possuem caracterı´sticas distintas.
As medidas de similaridade de imagem geralmente avaliam a distaˆncia entre vetores de ca-
racterı´sticas. As distaˆncias mais curtas correspondem a maior similaridade e distaˆncias maiores
correspondem a maior dissimilaridade. A comparac¸a˜o entre os vetores e´ feita a partir do uso de
func¸o˜es de distaˆncia sobre os vetores de um par de elementos, retornando um valor nume´rico
que corresponde a distaˆncia entre esses dois elementos (BARROSO et al., 2013).
Algumas func¸o˜es de distaˆncia utilizadas sa˜o: a distaˆncia Manhattan, ou L1 (Equac¸a˜o 2.1),
distaˆncia Euclidiana, ou L2 (Equac¸a˜o 2.2) e a distaˆncia Canberra (Equac¸a˜o 2.3). E´ calculada a
distaˆncia (d) entre dois vetores P = (p1, p2,..., pn) e Q = (q1, q2,..., qn).
d(p,q) = ‖p−q‖=
n
∑
i=1
|pi−qi| (2.1)
d(p,q) =
√
n
∑
i=1
(pi−qi)2 (2.2)
d(p,q) =
n
∑
i=1
|pi−qi|
|pi|+ |qi| (2.3)
2.3.3 Mu´ltiplos Descritores e Condic¸o˜es de Contorno
A combinac¸a˜o de um extrator de caracterı´stica e uma func¸a˜o de distaˆncia e´ geralmente
referenciada na literatura como descritor (TORRES et al., 2009; BARROSO et al., 2013, 2015).
Um problema enfrentado por sistemas CBIR e´ o Gap Semaˆntico, que e´ a inconsisteˆncia
existente na percepc¸a˜o do ser humano na avaliac¸a˜o de similaridade entre imagens pelo sistema
(LIU et al., 2007).
Para se combater o gap semaˆntico em consultas por similaridade, o uso de combinac¸o˜es
de mu´ltiplos descritores tem sido considerado por demonstrar bons resultados (BARROSO et al.,
2015), pois subconjuntos de imagens de um mesmo conjunto podem ser melhor representados
por caracterı´sticas diferentes. Barroso et al. (2013) propo˜e o uso de condic¸o˜es de contorno
para encontrar esses subconjuntos e escolher a melhor combinac¸a˜o de descritores para cada um
2.3 CBIR 25
deles.
Condic¸o˜es de contorno em consultas por similaridade de imagens, conforme entendido por
Barroso et al. (2013), e´ qualquer informac¸a˜o associada a` imagem que possa ser utilizada para
delimitar subconjuntos de imagens. Por exemplo, para consultas contendo imagens me´dicas
as condic¸o˜es de contorno podem ser informac¸o˜es como: hipo´tese de diagno´stico, laudos ra-
diolo´gicos ou mesmo o tipo de exame.
Me´todo para combinac¸a˜o de mu´ltiplos descritores partindo do melhor descritor
Considerando as imagens x e y, e as me´tricas δ1,..., δn dos descritores a serem combinados,
definidas sobre os domı´nios dos respectivos vetores de caracterı´sticas, a composic¸a˜o da func¸a˜o
de distaˆncia para combinac¸a˜o dos descritores δc e´ dada pela Equac¸a˜o (2.4):
δc(x,y) =
n
∑
i=1
ωi ∗ δi(x,y)dmaxi (2.4)
onde ω i e´ o peso atribuı´do ao i-e´simo descritor e dmaxi representa a distaˆncia ma´xima
obtida pela comparac¸a˜o entre todos os elementos do conjunto utilizando este mesmo descritor,
que normaliza as distaˆncias entre 0 e 1.
Os algoritmos de busca exaustiva para combinac¸a˜o linear utilizados em Barroso et al. (2013)
testam todas as combinac¸o˜es possı´veis (a partir de uma quantidade determinada de possı´veis
pesos) a fim de encontrar a melhor combinac¸a˜o linear entre os descritores. O extenso espac¸o de
busca torna o processo bastante custoso computacionalmente, com um crescimento exponencial
de acordo com o nu´mero de descritores utilizados.
Essa te´cnica foi enta˜o otimizada (BARROSO et al., 2015), porpondo-se a realizac¸a˜o de combinac¸o˜es
lineares dos descritores a partir do descritor que apresente o melhor desempenho individual,
avaliado pela sua precisa˜o me´dia na fase de treinamento. Este descritor assume enta˜o o peso ω1
= 1.
Em uma fase que precede ao balanceamento sa˜o definidos os descritores candidatos que
podera˜o ser combinados. Os descritores podem ser definidos por um especialista no domı´nio
da aplicac¸a˜o. Os descritores candidatos sa˜o enta˜o ranqueados pela precisa˜o me´dia. Partindo
do descritor melhor avaliado, inicia-se a combinac¸a˜o com o segundo descritor melhor avaliado.
Considerando as imagens x e y, e as me´tricas dos descritores candidatos ordenados, δ1,..., δn,
definidas sobre os domı´nios dos respectivos vetores de caracterı´sticas, a composic¸a˜o da func¸a˜o
de distaˆncia δc1 para combinac¸a˜o do primeiro descritor com o segundo descritor e´ dada pela
Equac¸a˜o (2.5):
2.3 CBIR 26
δc1(x,y) =
δ1(x,y)
dmax1
+ω2 ∗ δ2(x,y)dmax2 (2.5)
onde ω2 e´ o peso dado ao segundo descritor e dmax1 e dmax2 representam as distaˆncias
ma´ximas encontradas pela comparac¸a˜o entre todos os elementos do conjunto utilizando o res-
pectivo descritor, utilizadas para normalizar a participac¸a˜o de cada descritor na combinac¸a˜o.
Apo´s a definic¸a˜o da melhor combinac¸a˜o entre os dois primeiros descritores, parte-se para a
combinac¸a˜o com o terceiro melhor descritor, utilizando a Equac¸a˜o (2.6):
δc2(x,y) = δc1(x,y)+ω3 ∗ δ3(x,y)dmax3 (2.6)
onde ω3 e´ o peso dado ao terceiro melhor descritor e dmax3 representa a distaˆncia ma´xima
encontrada pela comparac¸a˜o entre todos os elementos do conjunto utilizando este descritor.
Dessa forma, os descritores sa˜o combinados aos pares sequencialmente, sempre testando
os pesos do pro´ximo descritor i + 1 na combinac¸a˜o com o melhor balanceamento ja´ definido
para os i descritores anteriores, de acordo com a Equac¸a˜o (2.7):
δci(x,y) = δci−1(x,y)+ωi+1 ∗ δi(x,y)dmaxi+1 (2.7)
2.3.4 Avaliac¸a˜o dos resultados de uma consulta em CBIR
Para se avaliar se os elementos presentes no resultado de uma consulta em CBIR efeti-
vamente representam o objeto de consulta, ou seja, se sa˜o relevantes, utiliza-se as medidas
de revocac¸a˜o (recall) e precisa˜o (precision) (BAEZA-YATES; RIBEIRO-NETO, 1999). Com essas
informac¸o˜es, e´ possı´vel construir um gra´fico de precisa˜o e revocac¸a˜o (P&R).
Considere uma dada consulta, onde R seja o nu´mero total de itens relevantes existentes na
base, RR o nu´mero total de itens relevantes recuperados e IR o total de itens recuperados.
Revocac¸a˜o e´ a frac¸a˜o do conjunto de elementos relevantes (R) que foram recuperados na
consulta.
Recall =
RR
R
(2.8)
Precisa˜o e´ a frac¸a˜o do conjunto de elementos recuperados (IR) que sa˜o relevantes.
2.3 CBIR 27
Precision =
RR
IR
(2.9)
O primeiro passo para se calcular P&R e´ ordenar os elementos recuperados da base de
acordo com sua distaˆncia em relac¸a˜o ao objeto de consulta.
Como exemplo (BAEZA-YATES; RIBEIRO-NETO, 1999), considere uma determinada consulta
q onde existe na base um conjunto Rq de 10 elementos relevantes, composto da seguinte forma:
Rq = {e5,e13,e17,e20,e31,e36,e42,e47,e55,e61}
Considere que um algoritmo de busca retornou um conjunto de elementos Iq, referentes a`
consulta q, cujos elementos e suas respectivas relevaˆncias sa˜o:
1. e42• 2. e54
3. e17• 4. e15
5. e2 6. e5•
7. e25 8. e27
9. e13• 10. e52
11. e55• 12. e67
Os elementos relevantes a` consulta q esta˜o indicados com o sı´mbolo •. Analisando o con-
junto Iq dos elementos recuperados, verifica-se que o primeiro elemento (e42) e´ um dos ele-
mentos relevantes a` consulta. Neste momento, o valor de precisa˜o e´ de 100% - pois todos os
elementos analisados ate´ aqui, sa˜o relevantes a` consulta - e o valor de revocac¸a˜o e´ de 10% -
pois ate´ este ponto, apenas um elemento relevante foi recuperado dentre um conjunto de dez
elementos.
O pro´ximo elemento relevante da lista e´ o terceiro elemento (e17). Para este elemento, o
valor de precisa˜o e´ de aproximadamente 66% (dois elementos relevantes em treˆs verificados)
e o valor de revocac¸a˜o e´ de 20% (dois entre dez elementos relevantes). A ana´lise prossegue
desta maneira ate´ que todos os elementos relevantes sejam verificados. Os valores de precisa˜o
e revocac¸a˜o sa˜o descritos no gra´fico de P&R, conforme visto na Figura 2.5.
Para uma avaliac¸a˜o efetiva dos resultados obtidos por um determinado sistema CBIR, e´
necessa´rio que diversas operac¸o˜es de consulta sejam realizadas, construindo assim uma curva de
precisa˜o e revocac¸a˜o que represente a me´dia dos desempenhos das diversas consultas realizadas.
Isso geralmente e´ feito calculando-se valores de precisa˜o para nı´veis determinados de revocac¸a˜o,
como a cada intervalo de 10% de revocac¸a˜o, por exemplo.
A avaliac¸a˜o de desempenho e´ realizada observando-se as curvas obtidas. Quanto mais
pro´xima do topo do gra´fico a curva estiver, melhor sera´ o resultado da operac¸a˜o de busca.
2.4 Visualizac¸a˜o de Dados e Imagens 28
Figura 2.5: Gra´fico de precisa˜o e revocac¸a˜o (BAEZA-YATES; RIBEIRO-NETO, 1999).
Sendo assim, a curva ideal para uma consulta apresenta 100% de precisa˜o para todos os valores
de revocac¸a˜o.
2.4 Visualizac¸a˜o de Dados e Imagens
2.4.1 Considerac¸o˜es Iniciais
Segundo Cruz (2012), a visualizac¸a˜o de dados refere-se a uma representac¸a˜o gra´fica na
qual dados multidimensionais sa˜o posicionados na tela de um computador, por exemplo, a fim
de refletir suas relac¸o˜es de similaridade. Assim, esses dados podem ser analisados e reportados
atendendo a necessidades especı´ficas e suas aplicac¸o˜es.
A representac¸a˜o visual de colec¸o˜es de dados comunica claramente ao usua´rio o conteu´do in-
formacional desses dados, reduzindo o trabalho cognitivo necessa´rio para realizar diversas tare-
fas. Ale´m disso, o usua´rio se torna um agente ativo no processo de minerac¸a˜o das informac¸o˜es,
pois consegue, ale´m de visualizar as relac¸o˜es entre os dados, interagir com o layout, tendo uma
visa˜o geral, ou concentrando-se em fenoˆmenos particulares. Isso resulta em um processo explo-
rato´rio mais ra´pido e com resultados melhores, em especial quando procedimentos automa´ticos
falham (PAIVA, 2012).
A visualizac¸a˜o de grandes conjuntos de dados de imagens apresenta va´rios desafios. Um
deles e´ a identificac¸a˜o de informac¸o˜es ou conhecimento relevante na visualizac¸a˜o, permitindo a
discriminac¸a˜o dos objetos em diferentes classes ou grupos sem perder a capacidade de identifi-
car elementos na˜o facilmente agrupa´veis. Outro desafio e´ encontrar representac¸o˜es simples que
2.4 Visualizac¸a˜o de Dados e Imagens 29
sejam fie´is ao conjunto de dados completo e a`s relac¸o˜es entre eles, considerando a limitac¸a˜o
da baixa dimensionalidade dos dispositivos de apresentac¸a˜o. Neste sentido existem diversos
me´todos para representar dados multidimensionais (CRUZ, 2012). No presente trabalho sera˜o
utilizadas as estruturas baseadas em a´rvore.
2.4.2 Te´cnicas de Visualizac¸a˜o de Imagens
Neste capı´tulo sa˜o apresentadas algumas te´cnicas de visualizac¸a˜o de imagens geralmente
utilizadas em sistemas CBIR.
Grid
Esta e´ a te´cnica mais comum para a visualizac¸a˜o de resultados de consultas em sistemas
CBIR. As imagens sa˜o apresentadas de maneira matricial, levando em conta o padra˜o ocidental
(da esquerda para a direita, de cima para baixo, como na Figura 2.6) de acordo com seu grau de
relevaˆncia (Ca´CERES, 2010).
Figura 2.6: Exemplo de visualizac¸a˜o em Grid (Ca´CERES, 2010)
Ane´is Conceˆntricos
2.4 Visualizac¸a˜o de Dados e Imagens 30
Nessa te´cnica, as imagens sa˜o distribuı´das sobre uma se´rie de ane´is conceˆntricos, como
pode ser visto na Figura 2.7. Cada anel e´ o cı´rculo, definido em coordenadas polares, formado
pelo conjunto de pontos com raio r = k, onde k e´ uma constante. A constante k incrementa-se
para cada anel. Este incremento diminui a cada anel, ou seja, ane´is sucessivos estara˜o mais
pro´ximos conforme k e´ incrementado (Ca´CERES, 2010).
Figura 2.7: Exemplo de visualizac¸a˜o em Ane´is Conceˆntricos (Ca´CERES, 2010)
Transformac¸a˜o Geome´trica
A visualizac¸a˜o de dados multidimensionais atrave´s da utilizac¸a˜o de transformac¸o˜es geo-
me´tricas implica em realizar um mapeamento da informac¸a˜o em um espac¸o visual de dimen-
sionalidade inferior, mantendo, na medida do possı´vel, as relac¸o˜es de distaˆncia definidas no
espac¸o original. O subespac¸o de projec¸a˜o e´, normalmente, unidimensional, bidimensional ou
tridimensional para facilitar a compreensa˜o humana (DIAS, 2013). Um exemplo pode ser visto
na Figura 2.8.
A´rvore
Uma forma de mapeamento de dados e´ a imposic¸a˜o de uma hierarquia sobre algum relaci-
onamento significativo dos dados, como o grau da similaridade calculado sobre as coordenadas
da representac¸a˜o vetorial (CRUZ, 2012). Para se expressar dados hiera´rquicos multidimensio-
nais na visualizac¸a˜o, e´ comum utilizar a´rvores (PAIVA et al., 2011). A hierarquia apresentada em
forma de a´rvore, levando em conta o grau de similaridade, e´ chamada de “a´rvore de similari-
2.4 Visualizac¸a˜o de Dados e Imagens 31
Figura 2.8: Exemplo de visualizac¸a˜o utilizando Transformac¸a˜o Geome´trica (DIAS, 2013)
dade”.
As a´rvores teˆm uma estrutura hiera´rquica que organiza as entidades de dados por meio de
conexo˜es pai-filho. Para ser uma a´rvore cla´ssica, cada entidade filho deve ter apenas um pai e
cada filho posiciona-se “embaixo” de um ancestral comum. No qual os no´s representam objetos
e as arestas representam a ligac¸a˜o entre eles (CRUZ, 2012). Dentre as te´cnicas encontradas
para se representar hierarquia em a´rvores, destaca-se: hyperbolic-tree (LAMPING; RAO; PIROLLI,
1995), que pode ser vista na Figura 2.9, e cone-tree (ROBERTSON; MACKINLAY; CARD, 1991),
apresentada na Figura 2.10.
Uma outra abordagem encontrada na literatura para a construc¸a˜o de uma a´rvore de simila-
ridade e´ atrave´s do conceito de a´rvore filogene´tica (DIAS, 2013), utilizando o me´todo Neighbor
Joining (NJ) (SAITOU; NEI, 1987), atrave´s do ca´lculo da matriz de distaˆncia. Um exemplo dessa
te´cnica pode ser observado na Figura 2.11.
Poucos trabalhos na literatura tratam da visualizac¸a˜o hiera´rquica em sistemas CBIR (CRUZ,
2012; PAIVA, 2012). A te´cnica NJ tem sido muito utilizada no contexto de classificac¸a˜o visual
de dados (ELER et al., 2008, 2009; PAIVA et al., 2011; CRUZ, 2012; PAIVA, 2012). Por esse motivo
ela foi escolhida neste trabalho.
2.4 Visualizac¸a˜o de Dados e Imagens 32
Figura 2.9: Exemplo de hyperbolic-tree (LAMPING; RAO; PIROLLI, 1995).
Figura 2.10: Exemplo de cone-tree (CRUZ, 2012)
2.4.3 A´rvore de Similaridade Neighbor Joining
A´rvores de similaridade podem ser construı´das a partir de matrizes de distaˆncias, por meio
de algoritmos de reconstruc¸a˜o de a´rvores filogene´ticas. Essas a´rvores buscam refletir relac¸o˜es
2.4 Visualizac¸a˜o de Dados e Imagens 33
Figura 2.11: Exemplo de visualizac¸a˜o em A´rvore (DIAS, 2013)
de similaridade a partir de princı´pios de evoluc¸a˜o mı´nima - que tenta minimizar a soma dos
tamanhos de todos os no´s da a´rvore - entre os organismos vivos, codificando relac¸o˜es de ances-
tralidade entre espe´cies. Assim, em uma a´rvore filogene´tica as folhas representam os objetos
originais da matriz de distaˆncias, os no´s internos sa˜o ancestrais hipote´ticos e os ramos (arestas)
indicam a distaˆncia evolutiva entre os objetos (CRUZ, 2012). Uma ideia dessa a´rvore pode ser
vista na Figura 2.12.
Um dos me´todos mais utilizados para a construc¸a˜o de uma a´rvore filogene´tica e´ o NJ,
criado por Saitou e Nei (1987). Uma a´rvore filogene´tica tem o propo´sito de expressar relac¸o˜es
de similaridade evoluciona´ria aplicando o princı´pio da evoluc¸a˜o mı´nima (DIAS, 2013). Essa
te´cnica, adaptada para a criac¸a˜o de a´rvores de similaridade, utiliza a ideia de encontrar pares de
instaˆncias mais pro´ximas em uma colec¸a˜o de dados, de modo a minimizar o comprimento e o
nu´mero de ramos da a´rvore gerada (PAIVA, 2012).
O Algoritmo 1 apresenta as etapas do me´todo NJ. E´ gerada uma a´rvore sem raiz, represen-
tando apenas as distaˆncias entre as instaˆncias. O algoritmo recebe como entrada uma matriz de
distaˆncias (similaridade) Dnxn, com as distaˆncias entre todos os pares de instaˆncias da colec¸a˜o,
de acordo com alguma medida de similaridade, e produz uma a´rvore de similaridade com n
no´s-folha, e n-2 no´s virtuais com grau 3. Ri e´ a distaˆncia me´dia do no´ i para todos os outros
no´s em D, capturando a noc¸a˜o de mudanc¸a evoluciona´ria. Em cada passo do algoritmo, os dois
no´s mais pro´ximos em D sa˜o removidos da matriz, e substituı´dos pelo no´ virtual x, para o qual
2.4 Visualizac¸a˜o de Dados e Imagens 34
Figura 2.12: A´rvore de similaridade do conjunto de 700 imagens COIL usando o algoritmo NJ.
Cada ramo apresenta um agrupamento distinto, com as imagens do mesmo grupo igual ao espac¸o
original (imagens recuperadas perto de cada ramo) (CRUZ, 2012).
uma nova linha e´ inserida em D. As novas distaˆncias de x para todos os outros no´s restantes na
matriz e´ calculada de acordo com as fo´rmulas apresentadas no algoritmo (PAIVA, 2012).
Algoritmo 1 Neighbor Joining
Considere n = nu´mero de elementos da matriz D;
Associe cada linha i da matriz D com um no´ folha i;
repita
Selecione o par de no´s (i, j) com o mı´nimo valor de Sij;
Crie um novo no´ x que conecte os no´s i e j, com arestas de tamanhos Lix e Ljx,
respectivamente;
Adicione a linha x a D, com valores Dxk para cada coluna k 6= i, j;
Remova as linhas i e j de D;
ate´ n = 3;
Conecte os treˆs no´s restantes na a´rvore;
Sij = Dij - Ri - Rj; Ry = 1/n-2∑kDyk
Lix = 12 (Dij + Ri - Rj); Ljx = Dij - Lix; Dxk =
1
2 (Dik + Djk - Dij)
2.4 Visualizac¸a˜o de Dados e Imagens 35
O NJ, ale´m de construir a topologia no formato de uma a´rvore sem raiz, tambe´m fornece o
valor do comprimento dos ramos da a´rvore resultante. A interpretac¸a˜o permite que se analisem
os dados em grupos identificados pelos ramos externos da a´rvore. Desta forma, o algoritmo
ocupa melhor o espac¸o em uma projec¸a˜o, pois e´ possı´vel expandir o desenho da a´rvore de
forma a reduzir significativamente ou eliminar sobreposic¸o˜es (CRUZ, 2012).
A Figura 2.13 mostra um comparativo entre um layout produzido pela LSP (Least-Square
Projection) (2.13a), uma te´cnica de projec¸a˜o, e uma a´rvore de similaridade NJ (2.13b, 2.13c),
para uma colec¸a˜o de dados textuais. Esse exemplo mostra que a organizac¸a˜o das instaˆncias
em ramos e´ consistente com a organizac¸a˜o da projec¸a˜o LSP. No entanto, a a´rvore adicional-
mente estrutura os grupos em nı´veis de similaridade, e reduz consideravelmente a sobreposic¸a˜o
e confusa˜o visual. Ale´m disso, as vizinhanc¸as locais sa˜o claramente visualizadas na a´rvore, de
acordo com a matriz de similaridade.
Apo´s a construc¸a˜o de uma a´rvore NJ, um algoritmo de desenho radial de grafos pode ser
aplicado, utilizando por exemplo um procedimento simplificado de construc¸a˜o de layout base-
ado em forc¸a, como mostrado na Figura 2.13c, minimizando a sobreposic¸a˜o de no´s e permitindo
uma inspec¸a˜o da organizac¸a˜o dos ramos (PAIVA, 2012).
Figura 2.13: Comparac¸a˜o entre uma projec¸a˜o LSP e uma a´rvore NJ, para uma colec¸a˜o de 675
documentos textuais (PAIVA, 2012).
Um dos desafios das pesquisas conhecidas na a´rea de recuperac¸a˜o de imagens e´ exibir gran-
des quantidades de imagens por similaridade. Va´rios autores defendem que uma representac¸a˜o
visual auxilia a ana´lise e a identificac¸a˜o de padro˜es existentes na colec¸a˜o de dados, permitindo
que o usua´rio entenda o comportamento do espac¸o de caracterı´sticas dos dados (CRUZ, 2012).
Existem muitas aplicac¸o˜es e sistemas que sustentam a explorac¸a˜o de colec¸o˜es, em que os
usua´rios possuem acesso a uma interface visual na qual podem interagir e reconhecer simila-
2.4 Visualizac¸a˜o de Dados e Imagens 36
ridade, fazer selec¸o˜es, ampliar detalhes, recuperar informac¸o˜es, entre outras atividades. Ale´m
disso, permitem que o usua´rio tenha uma visa˜o geral de toda a colec¸a˜o de imagens, por meio
da qual se pode criar um processo de busca para recuperar uma ou va´rias imagens desejadas,
ou ainda detectar tendeˆncias e caracterı´sticas particulares que seriam extremamente difı´ceis de
serem detectadas analisando imagem a imagem. Um desses sistemas e´ proposto no trabalho de
Rafael Dias (DIAS, 2013).
A Figura 2.14 mostra um exemplo de a´rvore NJ para a colec¸a˜o de imagens COREL. Na
Figura 2.14a, as cores indicam as classes das instaˆncias. Na Figura 2.14b, as instaˆncias sa˜o
exibidas como miniaturas das imagens que representam. E´ possı´vel perceber que os ramos
organizam bem a maioria das classes da colec¸a˜o, e que quase todas as instaˆncias cujas carac-
terı´sticas na˜o expressam claramente os padro˜es de suas classes situam-se no nu´cleo da a´rvore.
Figura 2.14: Exemplo de uma a´rvore NJ para a colec¸a˜o de imagens COREL (PAIVA, 2012).
E´ importante ressaltar que a medida de distaˆncia utilizada para o ca´lculo da vizinhanc¸a na
a´rvore NJ e´ diferente daquela utilizada para as projec¸o˜es. Essas u´ltimas organizam o layout
de forma que pontos com distaˆncia Euclidiana pequena apresentam similaridade maior do que
pontos com uma distaˆncia Euclidiana grande. Para as a´rvores NJ, esse raciocı´nio na˜o e´ va´lido,
pois a proximidade no layout e´ definida pelo algoritmo de desenho da a´rvore, e na˜o possui
nenhuma relac¸a˜o com a distaˆncia Euclidiana entre um ponto e os demais. Assim, e´ possı´vel, por
exemplo, que dois pontos pertencentes a ramos diferentes, e por isso com pouca similaridade
2.4 Visualizac¸a˜o de Dados e Imagens 37
entre si, sejam posicionados pro´ximos um do outro no layout. Dessa forma, a distaˆncia entre
dois pontos a e b na a´rvore NJ foi definida como a soma dos pesos das arestas que formam o
menor caminho conectando a a b (PAIVA, 2012).
2.4.3.1 Melhorias na construc¸a˜o de a´rvores de similaridade
No trabalho de Paiva et al. (2011), sa˜o propostas duas melhorias na construc¸a˜o de a´rvores
de similaridade NJ: promoc¸a˜o de no´s e algoritmos mais ra´pidos.
Promoc¸a˜o de no´s em a´rvores NJ
Um problema com o layout produzido pela te´cnica NJ e´ o volume de pontos e arestas gerado
no espac¸o de visualizac¸a˜o. Como apresentado na sec¸a˜o 2.4.3, para n instaˆncias em uma colec¸a˜o,
(n-2) no´s virtuais sa˜o criados. Esses no´s na˜o fazem parte da colec¸a˜o, mas ocupam boa parte do
espac¸o de visualizac¸a˜o, gerando um layout poluı´do.
De modo a reduzir o nu´mero de no´s virtuais nas a´rvores NJ, foi implementada uma operac¸a˜o
determinı´stica de reescrita de grafos baseada na substituic¸a˜o de no´s virtuais por no´s da colec¸a˜o,
sempre que detectada uma configurac¸a˜o de no´s especı´fica. Essa operac¸a˜o e´ chamada de promoc¸a˜o
de no´s.
Seja uma a´rvore NJ T, na qual existe um par de no´s-folha u e v, conectados a um no´ virtual
a, e que outro no´ virtual b conecte esse no´ virtual a e um outro no´-folha w, como mostrado na
Figura 2.15a. A operac¸a˜o de promoc¸a˜o de no´s baseia-se no fato de que nenhum outro no´ e´ ta˜o
similar a w do que a (durante a construc¸a˜o de T), e por isso nenhum outro no´ e´ mais similar
de u e v do que w. Assim, a pode ser substituı´do por w e b pode ser removido sem perda no
poder representacional. A relac¸a˜o entre u, v, w e a e´ va´lida apenas para a topologia criada pelo
algoritmo NJ, na˜o tendo valor para o relacionamento induzido pela matriz de similaridade, no
caso de algum relacionamento existir.
A promoc¸a˜o de no´s pode ser formalmente definida em termos da ocorreˆncia de um padra˜o e
uma substituic¸a˜o na a´rvore, como mostra as Figuras 2.15b e 2.15c, e consiste em substituir cada
ocorreˆncia desse padra˜o, em ordem decrescente da distaˆncia do no´ a no padra˜o para o no´ que
reside no centro da a´rvore. Os pesos das arestas, durante a substituic¸a˜o, sa˜o chamados de ωr,
e sa˜o definidos de acordo com os pesos que ocorrem no padra˜o, chamados de ωp, computados
pelo algoritmo de construc¸a˜o da a´rvore. Chamando de T1, T2 e T3 os no´s que conectam a
suba´rvore ao resto da a´rvore, e´ possı´vel obter ωr(w,T1) = ωp(b,T1) + ωp(a,b)/2 + ωp(w,b) / 2
e ωr(w,Ti) = ωp(a,Ti) + ωp(a,b) / 2 + ωp(w,b) / 4, para i=2, 3. A a´rvore resultante e´ chamada
de Promoting Neighbor Joining (PNJ).
2.4 Visualizac¸a˜o de Dados e Imagens 38
Figura 2.15: Operac¸a˜o de promoc¸a˜o de no´s. Cı´rculos preenchidos representam no´s da colec¸a˜o, e
triaˆngulos representam suba´rvores (PAIVA et al., 2011).
A promoc¸a˜o de no´s permite que as capacidades de organizac¸a˜o e explorac¸a˜o das a´rvores
NJ sejam mantidas, mas reduzindo o nu´mero de no´s virtuais e consequentemente de arestas
desnecessa´rias, resultando em um layout mais limpo, que permite um acesso mais direto a`s
instaˆncias da colec¸a˜o atrave´s dos ramos da a´rvore. Nas a´rvores PNJ, a utilizac¸a˜o do espac¸o
de visualizac¸a˜o e´ mais racional, e a poluic¸a˜o visual da construc¸a˜o e´ reduzida, como pode ser
visto na Figura 2.16, que mostra uma comparac¸a˜o entre os layouts produzidos pela te´cnica NJ
original (2.16a) e PNJ (2.16b).
Figura 2.16: Comparac¸a˜o entre a´rvores NJ e PNJ para a colec¸a˜o COREL, destacando os no´s
virtuais e arestas (PAIVA et al., 2011).
Algoritmos mais ra´pidos para NJ
2.4 Visualizac¸a˜o de Dados e Imagens 39
A necessidade de se recalcular parte da matriz de distaˆncias a cada iterac¸a˜o do processo
de construc¸a˜o da a´rvore NJ, devido a` inserc¸a˜o do no´ virtual gerado na iterac¸a˜o anterior, pode
resultar em um alto custo computacional na gerac¸a˜o da a´rvore, mesmo para colec¸o˜es pequenas.
Ale´m disso, a procura pelo valor de Sij mı´nimo na matriz D, para determinar o pro´ximo par de
no´s a serem combinados, exige uma verificac¸a˜o em cada posic¸a˜o de D, resultando em O(n2),
com n igual ao nu´mero de instaˆncias.
Para amenizar tais problemas, alguns algoritmos que modificam o processo de montagem
da a´rvore foram propostos. De um modo geral, esses algoritmos utilizam duas estrate´gias, ba-
seadas em estruturas de dados especializadas, ou heurı´sticas que sacrificam a precisa˜o, e podem
ser diferenciados basicamente por algumas modificac¸o˜es direcionadas a situac¸o˜es especı´ficas.
Assim, de forma a representar essas duas estrate´gias, e verificar o impacto na velocidade de
gerac¸a˜o e na precisa˜o da a´rvore obtida, duas te´cnicas foram selecionadas, e sa˜o descritas a se-
guir. As descric¸o˜es e notac¸o˜es utilizadas sa˜o baseadas nos passos de construc¸a˜o da a´rvore NJ
apresentados no Algoritmo 1. Adicionalmente, Sij e´ denotado como Smin, para uma determinada
matriz D.
O primeiro algoritmo selecionado e´ chamado Rapid Neighbor Joining (Rapid NJ). Esse
algoritmo produz a´rvores ideˆnticas a`s produzidas pelo algoritmo original. Sua ideia baseia-se
no fato de que, na procura por Smin em determinada linha i da matriz D, atrave´s da avaliac¸a˜o
de Sij = Dij - Ri - Rj, o valor de Ri e´ fixo. Assim, o algoritmo mante´m uma matriz auxiliar,
na qual as linhas sa˜o ordenadas, e cujas ce´lulas conte´m ı´ndices para D. A procura em uma
linha ordenada i dessa matriz para assim que Sij - Ri - Rmax > Smin, para o qual Rmax e´ o valor
ma´ximo de Ri dentre todas as linhas da matriz (Rj ≤ Rmax). Um trabalho extra e´ inserido com
a ordenac¸a˜o das linhas nessa matriz auxiliar, bem como a manipulac¸a˜o de colunas removidas e
avaliac¸a˜o de Rmax. O algoritmo ainda e´ O(n3), mas os experimentos apresentados em (PAIVA et
al., 2011) mostraram que a estrate´gia diminui significantemente o nu´mero de ce´lulas visitadas,
na busca por Smin, fazendo com que ele se mostre mais eficiente do que outros algoritmos de
acelerac¸a˜o na construc¸a˜o da a´rvore.
O segundo algoritmo selecionado e´ chamado Fast Neighbor Joining (Fast NJ). Esse algo-
ritmo mante´m um conjunto com O(n) ce´lulas candidatas na matriz D. A procura por Smin e´
restrita a esse conjunto, que conte´m, inicialmente, os valores mı´nimos de Sij para cada linha i.
Quando as linhas i e j sa˜o conectadas a um no´ virtual x e removidas de D, as ce´lulas candidatas
com as quais eles contribuem sa˜o removidas e uma nova ce´lula candidata, para a nova linha x
e´ adicionada. Essa abordagem resulta em um algoritmo que na˜o produz a mesma a´rvore que
o algoritmo original de construc¸a˜o da a´rvore NJ, e que no pior caso, e´ O(n2). Os autores da
2.5 Considerac¸o˜es Finais 40
te´cnica mostraram que quando a medida de similaridade e´ pro´xima de ser aditiva, as a´rvores
produzidas sa˜o ideˆnticas a`quelas produzidas pelo algoritmo original.
A Tabela 2.1 mostra uma comparac¸a˜o entre os tempos de gerac¸a˜o dos layouts utilizando os
algoritmos NJ e NJ melhorados e a te´cnica de projec¸a˜o LSP. Te´cnicas de projec¸a˜o ra´pidas, tais
como a LSP, que e´ O(n
√
n), levam vantagem em relac¸a˜o a`s a´rvores NJ com relac¸a˜o ao tempo
de gerac¸a˜o do layout. A a´rvore Fast NJ e´ mais ra´pida do que a te´cnica de projec¸a˜o LSP, sendo
que o tempo usado para a projec¸a˜o de no´s e´ proporcionalmente pequeno.
Te´cnica COREL MEDICAL OBJECTS
A´rvoreNJ 3.0474 0.5 394.383
A´rvorePNJ 3.064 0.506 396.507
FastNJ 0.0936 0.0462 4.976
FastPNJ 0.1104 0.052 6.1
RapidNJ 2.366 0.373 261.971
RapidPNJ 2.3828 0.3788 262.178
LSP 0.7182 0.2068 61.564
Tabela 2.1: Comparac¸a˜o entre tempos de Gerac¸a˜o do Layout (segundos), considerando as aborda-
gens de gerac¸a˜o ra´pida de a´rvores NJ e a te´cnica de projec¸a˜o LSP (PAIVA et al., 2011).
2.5 Considerac¸o˜es Finais
Neste capı´tulo foram apresentados os conceitos relacionados ao trabalho. No capı´tulo 3
e´ demonstrado o uso em conjunto das te´cnicas apresentadas a fim de testar a relac¸a˜o entre a
qualidade da resposta da consulta em CBIR e a qualidade da visualizac¸a˜o gerada. Tambe´m e´
observada a qualidade da a´rvore NJ gerada com o uso de mu´ltiplos descritores com condic¸o˜es
de contorno.
Capı´tulo 3
TRABALHO DESENVOLVIDO
3.1 Considerac¸o˜es Iniciais
Neste capı´tulo e´ apresentado o me´todo desenvolvido neste projeto de mestrado, que propo˜e
o uso de mu´ltiplos descritores com condic¸o˜es de contorno para melhorar a visualizac¸a˜o de
a´rvores de similaridade NJ. Barroso et al. (2013) comprovou que o uso de condic¸o˜es de contorno
para combinar mu´ltiplos descritores resulta em melhor precisa˜o em sistemas CBIR. E´ esperado
que o uso de mu´ltiplos descritores tambe´m contribua na construc¸a˜o de a´rvores de similaridade
mais bem organizadas, melhorando a visualizac¸a˜o e o entendimento do usua´rio.
Inicialmente cada passo do me´todo proposto e´ explicado para depois serem apresentados
os experimentos realizados para avaliar se as hipo´teses sa˜o verdadeiras. Tais experimentos
consistem em comparac¸o˜es de consultas utilizando cada descritor separadamente e todos os
descritores juntos, utilizando-se o me´todo proposto por Barroso et al. (2015) para determinar o
melhor peso dos descritores. Tambe´m sa˜o analisadas as a´rvores geradas por essas consultas de
forma subjetiva e tambe´m utilizando o me´todo neighborhood hit (PAULOVICH et al., 2008), que
mede a porcentagem de vizinhos mais pro´ximos de uma imagem na visualizac¸a˜o, que pertencem
a` mesma classe. A precisa˜o final representa a me´dia das preciso˜es para cada ponto. Isso permite
avaliar numericamente a separabilidade das classes pre´-existentes no layout.
3.2 Visa˜o Geral do Me´todo Desenvolvido
Como pode ser visto na Figura 3.1, que apresenta uma visa˜o geral do me´todo desenvolvido,
o usua´rio fornece uma imagem de consulta - para obter as imagens mais similares a ela - e um
peso para os descritores. Para o me´todo proposto, o peso ideal para a condic¸a˜o de contorno
3.2 Visa˜o Geral do Me´todo Desenvolvido 42
Figura 3.1: Visa˜o geral do me´todo proposto.
da imagem de consulta deve ser obtido previamente utilizando-se a te´cnica de Barroso et al.
(2015). Neste me´todo sa˜o utilizados treˆs descritores. Cada descritor e´ formado por um extrator
de caracterı´sticas e uma func¸a˜o de distaˆncia (a similaridade entre as imagens e´ definida atrave´s
do ca´lculo da distaˆncia entre os vetores de caracterı´sticas obtidos pelo extrator). Os extratores
usados sa˜o: Haralick e distaˆncia Canberra para textura; Statistical Moments e distaˆncia Manhat-
tan (L1) para forma; e Histograma de Cinza e distaˆncia Euclidiana (L2) para cor. Um exemplo
de consulta por similaridade de imagem utilizando o me´todo proposto pode ser visualizado na
Figura 3.2, onde o usua´rio tambe´m pode definir quantas imagens (k) devem ser retornadas.
A escolha pelos descritores pode ser feita pelo especialista de domı´nio ou aleatoriamente,
apenas para fins de testes. Optou-se por utilizar, aleatoriamente, um extrator de cada tipo (tex-
tura, forma e cor) a fim de se expandir a possibilidade de melhor descrever todos os subconjun-
tos de imagens. Para escolher a func¸a˜o de distaˆncia utilizou-se como base o trabalho de Bugatti,
Traina e Traina Jr. (2008).
Em seguida, os vetores de caracterı´sticas extraı´dos da imagem de consulta sa˜o normaliza-
dos. Para isso, os valores do vetor (cada um representa uma determinada caracterı´stica) sa˜o
divididos pelo maior valor obtido de cada caracterı´stica levando em conta todas as imagens
utilizadas (consulta + base), dessa forma os valores sa˜o alterados para que fiquem entre 0 e 1.
3.2 Visa˜o Geral do Me´todo Desenvolvido 43
Figura 3.2: Exemplo implementado do me´todo desenvolvido.
Os vetores de caracterı´sticas das imagens da base ja´ normalizados sa˜o retornados e se unem
aos vetores da imagem de consulta para que seja feito o ca´lculo de similaridade. Uma medida
de similaridade e´ aplicada para obter a distaˆncia entre os vetores, que depois sa˜o utilizadas para
se obter um valor u´nico que represente as treˆs distaˆncias medidas (uma de cada descritor).
O ca´lculo de junc¸a˜o das distaˆncias pode ser visto na Equac¸a˜o 3.1. Para cada par de imagens
(i, j) soma-se o resultado do ca´lculo de cada descritor (n), de 1 a 3, que e´: o peso (wn) infor-
mado pelo usua´rio, multiplicado pela distaˆncia entre i e j obtida pelo descritor (dn(i,j)), dividido
pela maior distaˆncia medida pelo descritor (mdn). A divisa˜o pelo maior valor funciona como
normalizac¸a˜o.
distance(i, j) =
3
∑
n=1
wn ∗dn(i, j)
mdn
(3.1)
As distaˆncias finais sa˜o utilizadas para se criar uma matriz de distaˆncias (exemplificada em
3.3 Experimentos e Resultados 44
parte na Figura 3.3). O arquivo de matriz de distaˆncias (dmat file) conte´m as distaˆncias entre
todos os pares de imagens. Essa matriz e´ utilizada tanto para se obter uma classificac¸a˜o das
distaˆncias, determinando assim as imagens mais similares a` imagem de consulta para serem
exibidas ao usua´rio (exemplificado na Figura 3.4), quanto para se construir a a´rvore de simila-
ridade NJ atrave´s do algoritmo Fast Promoting Neighbor Joining (FastPNJ, exemplificada na
Figura 3.5).
Figura 3.3: Exemplo de parte de uma matriz de distaˆncias.
Figura 3.4: Exemplo de grid contendo o resultado de uma consulta por similaridade.
3.3 Experimentos e Resultados
Este capı´tulo apresenta os experimentos realizados com a implementac¸a˜o do me´todo pro-
posto para avaliar se a qualidade da visualizac¸a˜o esta´ relacionada com a qualidade da consulta
(visualizac¸a˜o de ma´ qualidade esta´ relacionada a um resultado da consulta de qualidade ruim;
visualizac¸a˜o de boa qualidade esta´ relacionada a um resultado da consulta tambe´m de qualidade
boa), apresentado no capı´tulo 3.3.1.
Tambe´m e´ avaliado se o uso de mu´ltiplos descritores com condic¸o˜es de contorno melhora a
qualidade da visualizac¸a˜o hiera´rquica de imagens em CBIR, apresentado nos capı´tulos 3.3.2 e
3.3.3.
O conjunto de imagens utilizado nesse experimento, chamado BalanRMI704, e´ composto
por 704 imagens de exames de Ressonaˆncia Magne´tica, obtidas no Hospital das Clı´nicas de
Ribeira˜o Preto da Universidade de Sa˜o Paulo (USP), divididas em 8 classes, de acordo com o
tipo de exame: Angiograma, Pe´lvis Axial, Cabec¸a Axial, Abdoˆmen Axial, Abdoˆmen Coronal,
3.3 Experimentos e Resultados 45
Figura 3.5: Exemplo de a´rvore de similaridade construı´da pelo algoritmo NJ a partir de uma
matriz de distaˆncias.
Cabec¸a Coronal, Cabec¸a Sagital e Espinha Sagital. Um exemplo de algumas imagens da base
pode ser visto na Figura 3.6.
Figura 3.6: Exemplo de imagens da Base Balan.
3.3 Experimentos e Resultados 46
3.3.1 Experimento 1
Este experimento esta´ voltado a testar a primeira hipo´tese deste trabalho de mestrado:
quanto mais precisos os resultados de uma consulta, melhor pode ser a organizac¸a˜o das imagens
na visualizac¸a˜o. Em outras palavras, avalia se existe uma correlac¸a˜o entre os dois.
Para isso, uma imagem aleato´ria e´ escolhida para se fazer consultas utilizando cada descritor
individualmente. A partir de cada consulta sa˜o obtidas duas informac¸o˜es: a precisa˜o/revocac¸a˜o
dos resultados desta consulta e o neighborhood hit da a´rvore NJ gerada.
E´ enta˜o gerado um gra´fico de precisa˜o e revocac¸a˜o com os valores obtidos das treˆs consultas
e um gra´fico de neighborhood hit das treˆs a´rvores NJ geradas. Dessa forma, podemos comparar
a qualidade da consulta e a qualidade da visualizac¸a˜o.
3.3.1.1 Testes
Leva-se em conta a imagem 0037 pertencente a` classe 5 (Cabec¸a Coronal) da base, re-
presentada na Figura 3.7. Sa˜o realizadas treˆs consultas, cada uma utilizando um descritor in-
dividual, sem alterar qualquer outro paraˆmetro. O resultado da consulta utilizando apenas o
descritor 1 (Haralick / Canberra) pode ser visto em (A) na Figura 3.8, o resultado relacionado
ao descritor 2 (Statistical Moments / Manhattan) pode ser visto em (B) e o resultado do descritor
3 (Gray Histogram / Euclidean) esta´ em (C).
Figura 3.7: Imagem 0037 da Base Balan, pertencente a` classe 5.
O gra´fico de precisa˜o e revocac¸a˜o gerado dessas treˆs consultas se segue na Figura 3.9.
Pode-se relacionar as Figuras 3.8 e 3.9. A Figura 3.8 mostra que o Descritor 1 retornou 5
imagens da mesma classe que a imagem de consulta. O Descritor 2 retornou apenas uma ima-
gem corretamente. O Descritor 3 retornou 4 das 5 imagens corretamente. Portanto, o Descritor
1 foi o mais eficiente e o Descritor 2 o menos eficiente. Esta eficieˆncia tambe´m e´ vista na Figura
3.9.
A visualizac¸a˜o gerada para cada uma das treˆs consultas deste teste pode ser consultada na
3.3 Experimentos e Resultados 47
Figura 3.8: Resultado das consultas da imagem 0037 da classe 5 utilizando cada descritor indivi-
dualmente.
Figura 3.9: Gra´fico de precisa˜o e revocac¸a˜o medidas da consulta da imagem 0037 da classe 5
utilizando cada descritor individualmente.
Figura 3.10.
O gra´fico de neighborhood hit gerado para cada visualizac¸a˜o apresentada na Figura 3.10
encontra-se na Figura 3.11.
E´ possı´vel observar uma relac¸a˜o entre precisa˜o e revocac¸a˜o medida e a me´dia de neigh-
borhood hit, ou seja, uma relac¸a˜o entre a qualidade do resultado da consulta e a qualidade da
3.3 Experimentos e Resultados 48
Figura 3.10: Visualizac¸a˜o gerada nas consulta da imagem 0037 da classe 5 utilizando cada descritor
individualmente.
Figura 3.11: Gra´fico de neighborhood hit da consulta da imagem 0037 da classe 5 utilizando cada
descritor individualmente.
visualizac¸a˜o gerada.
Para melhor visualizar esta relac¸a˜o, foram realizados outros testes com imagens aleato´rias
da base de dados, mostrando a correlac¸a˜o entre a qualidade dos resultados da consulta e a
qualidade da visualizac¸a˜o. Foi comparada a posic¸a˜o no ranking de precisa˜o e revocac¸a˜o com
a posic¸a˜o no ranking de neighborhood hit. Esse ranking e´ a ordenac¸a˜o dos descritores pela
precisa˜o me´dia obtida para cada classe.
3.3.2 Experimento 2A
Este experimento avalia o impacto da utilizac¸a˜o de mu´ltiplos descritores com condic¸o˜es de
contorno na qualidade da a´rvore de similaridade gerada.
3.3 Experimentos e Resultados 49
Dez imagens aleato´rias foram selecionadas de 4 das 8 classe da base de dados para se
calcular a me´dia de precisa˜o por classe de cada um dos 3 descritores implementados. Isso e´
necessa´rio para se obter a melhor combinac¸a˜o de descritores pelo me´todo de Barroso et al.
(2015), partindo do melhor descritor individual. As condic¸o˜es de contorno escolhidas para a
combinac¸a˜o de descritores sa˜o os tipos de exame, ou seja, a pro´pria classe das imagens.
A melhor combinac¸a˜o obtida para cada uma dessas 4 classes pode ser vista na Tabela 3.1.
Lembrando que os descritores sa˜o Haralick e distaˆncia Canberra para textura (D1), Statisti-
cal Moments e distaˆncia Manhattan (L1) para forma (D2) e Histograma de Cinza e distaˆncia
Euclidiana (L2) para cor (D3).
Classe D1 D2 D3
Classe 2 0.800000 0.000000 1.000000
Classe 3 1.000000 0.400000 0.210526
Classe 5 1.000000 0.000000 0.266667
Classe 7 1.000000 3.333333 0.307692
Tabela 3.1: Melhor combinac¸a˜o de pesos de descritores obtida para cada classe testada.
Foi constituı´do o gra´fico de precisa˜o e revocac¸a˜o utilizando a melhor combinac¸a˜o gerada
para cada descritor, como pode ser visto nos gra´ficos correspondentes a` classe 2 (Figura 3.12),
classe 3 (Figura 3.13), classe 5 (Figura 3.14) e classe 7 (Figura 3.15).
Foram realizadas dez consultas distintas para cada uma das 4 classes do experimento ante-
rior, gerando suas respectivas a´rvores de similaridade. Dessa forma, foram geradas 4 a´rvores
para cada consulta, uma correspondente a cada um dos treˆs descritores individuais e tambe´m
uma para a melhor combinac¸a˜o de descritores.
Um exemplo pode ser visto na Figura 3.16, que sa˜o as a´rvores geradas em uma das consultas
do experimento, com uma imagem da classe 2 (Cabec¸a Axial), correspondentes a` combinac¸a˜o
dos descritores e aos descritores individuais.
Na Figura 3.16, as a´rvores geradas foram analisadas subjetivamente para se tentar identificar
quais parecem ser melhor construı´das. Para isso foram levadas em conta caracterı´sticas como
proximidade de no´s de mesma classe (representados pela mesma cor), distaˆncia entre esses no´s
e tambe´m a distaˆncia entre as classes.
E´ preciso levar em conta a classe / condic¸a˜o de contorno da consulta para se analisar melhor
a organizac¸a˜o da a´rvore. Dessa forma podemos perceber duas ocorreˆncias no uso de descritores
individuais: no´s de outras classes misturadas aos no´s da classe de consulta e ramos da classe de
consulta distantes entre si. Isso na˜o ocorre no uso de mu´ltiplos descritores. Apenas um ramo
com 4 no´s da classe de consulta ficou mais distante, talvez por serem imagens mais semelhantes
3.3 Experimentos e Resultados 50
Figura 3.12: Me´dia de precisa˜o medida para consultas de imagens da Classe 2.
Figura 3.13: Me´dia de precisa˜o medida para consultas de imagens da Classe 3.
3.3 Experimentos e Resultados 51
Figura 3.14: Me´dia de precisa˜o medida para consultas de imagens da Classe 5.
Figura 3.15: Me´dia de precisa˜o medida para consultas de imagens da Classe 7.
3.3 Experimentos e Resultados 52
Figura 3.16: A´rvores geradas para consulta de imagens da classe 2.
a imagens de outra classe. Foi destacado na imagem o conjunto de no´s de classe 2 na primeira
a´rvore.
3.3 Experimentos e Resultados 53
3.3.3 Experimento 2B - Neighborhood Hit
Este experimento e´ uma extensa˜o do experimento anterior, para exemplificar o resultado em
classes diferentes. A fim de se avaliar cientificamente as a´rvores geradas, foi utilizado o me´todo
Neighborhood Hit, que mede a porcentagem de vizinhos mais pro´ximos de uma instaˆncia, no
espac¸o de visualizac¸a˜o, que pertencem a` mesma classe dessa instaˆncia.
3.3.3.1 Teste com imagens da classe 2
Neste experimento sa˜o utilizadas as quatro a´rvores do experimento anterior, de classe 2,
presentes da Figura 3.16. A partir dessas a´rvores se obteve a precisa˜o de vizinhos atrave´s do
me´todo neighborhood hit, que pode ser conferido na Figura 3.17. A Figura 3.18 demostra o
gra´fico de precisa˜o e revocac¸a˜o para as quatro consultas realizadas. Pode-se ver a correlac¸a˜o
existente entre as treˆs figuras.
Figura 3.17: Neighborhood Hit para uma consulta de 5 vizinhos da classe 2.
3.3.3.2 Teste com imagens da classe 5
Da mesma forma que foi realizado o teste anterior, foi escolhida uma imagem aleato´ria da
classe 5 (Cabec¸a Coronal) e foram geradas quatro a´rvores, modificando apenas o paraˆmetro
relacionado ao descritor. A Figura 3.19 conte´m a a´rvore gerada utilizando-se mu´ltiplos descri-
tores (A), a a´rvore gerada se utilizando apenas o descritor 1 (B), descritor 2 (C) e descritor 3
(D). Novamente foi destacado na primeira a´rvore da figura o grupo de no´s pertencentes a` classe
testada.
A Figura 3.20 apresenta o gra´fico de neighborhood hit para as quatro a´rvores indicadas na
3.4 Considerac¸o˜es Finais 54
Figura 3.18: Gra´fico de precisa˜o e revocac¸a˜o para quatro testes realizados com uma imagem da
classe 2.
Figura 3.19. Ja´ o gra´fico de precisa˜o e revocac¸a˜o das quatro consultas e´ demonstrado na Figura
3.21.
3.4 Considerac¸o˜es Finais
A ana´lise dos experimentos realizados indicam que existe uma correlac¸a˜o entre a qualidade
do resultado da consulta por similaridade de imagens e a qualidade da visualizac¸a˜o em a´rvore
de similaridade NJ gerada, pore´m e´ importante testar essa correlac¸a˜o utilizando outros tipos de
visualizac¸a˜o.
Ja´ os experimentos relacionados a combinac¸a˜o de descritores demonstram que o uso de
mu´ltiplos descritores contribui para a gerac¸a˜o de a´rvores de similaridade NJ mais organizadas,
comprovado por meio do me´todo neighborhood hit, que mede a porcentagem de vizinhos mais
pro´ximos de uma instaˆncia, no espac¸o de visualizac¸a˜o, que pertencem a` mesma classe dessa
instaˆncia.
Os gra´ficos de precisa˜o e revocac¸a˜o indicam que o uso de mu´ltiplos descritores com condic¸o˜es
de contorno ficam pro´ximos da precisa˜o medida pelo melhor descritor individual por conta do
tamanho do grupo de treinamento. E´ sugerido que se use a base toda para se obter o melhor des-
critor individual e daı´ partir para o ca´lculo da melhor combinac¸a˜o, pore´m isso se torna invia´vel
em bases grandes. Apesar disso, mesmo usando um grupo de treinamento pequeno, a te´cnica
3.4 Considerac¸o˜es Finais 55
Figura 3.19: A´rvores geradas para consulta de imagens da classe 5.
garantiu nı´veis de precisa˜o e revocac¸a˜o ta˜o bons ou melhores que o melhor descritor indivi-
dual, e mesmo nos casos de aparente empate, os gra´ficos de neighborhood hit indicam alguma
melhora na organizac¸a˜o da a´rvore NJ gerada ao se utilizar mu´ltiplos descritores.
3.4 Considerac¸o˜es Finais 56
Figura 3.20: Neighborhood Hit para uma consulta de 5 vizinhos da classe 5.
Figura 3.21: Gra´fico de precisa˜o e revocac¸a˜o para quatro testes realizados com uma imagem da
classe 5.
Capı´tulo 4
CONCLUSO˜ES E TRABALHOS FUTUROS
4.1 Considerac¸o˜es Iniciais
Sistemas de Recuperac¸a˜o de Imagens por Conteu´do (Content-Based Image Retrieval -
CBIR) permitem que sejam realizadas consultas em bases de imagens, retornando as imagens
com maior grau de similaridade em relac¸a˜o a` imagem de consulta (Ca´CERES, 2010).
A combinac¸a˜o de um algoritmo extrator de caracterı´stica e uma func¸a˜o de distaˆncia e´ ge-
ralmente referido na literatura como descritor (TORRES et al., 2009; BARROSO et al., 2015).
Os sistemas CBIR possuem o Gap Semaˆntico (inconsisteˆncia entre a percepc¸a˜o do ser hu-
mano na avaliac¸a˜o de similaridade entre imagens comparada com a computada por sistemas
CBIR) como uma das suas principais limitac¸o˜es (LIU et al., 2007). Para se combater o gap
semaˆntico em consultas por similaridade, o uso de combinac¸o˜es de mu´ltiplos descritores tem
sido considerado por demonstrar bons resultados (BARROSO et al., 2015), pois subconjuntos de
imagens de um mesmo conjunto podem ser melhor representados por caracterı´sticas diferentes.
Barroso et al. (2013) propo˜e o uso de condic¸o˜es de contorno para encontrar esses subcon-
juntos e escolher a melhor combinac¸a˜o de descritores para cada um deles. Condic¸o˜es de con-
torno sa˜o quaisquer informac¸o˜es associadas a` imagem que possam ser utilizadas para delimitar
subconjuntos de imagens.
A u´ltima etapa de um sistema CBIR e´ a visualizac¸a˜o dos resultados de uma consulta. Cada
sistema CBIR possui uma forma diferente de apresentar esses resultados (Ca´CERES, 2010). A
qualidade da visualizac¸a˜o pode estar relacionada com a qualidade da resposta da consulta de
sistemas CBIR.
Assim, a primeira hipo´tese testada neste trabalho foi a de que quanto mais precisos os
4.2 Principais Contribuic¸o˜es 58
resultados de uma consulta, melhor pode ser a organizac¸a˜o das imagens na visualizac¸a˜o. A
segunda hipo´tese experimentada neste trabalho foi a de que o uso de mu´ltiplos descritores com
condic¸a˜o de contorno pode melhorar a qualidade da visualizac¸a˜o hiera´rquica de imagens em
CBIR. As contribuic¸o˜es e ideias de trabalhos futuros relacionadas aos testes realizados com
essas duas hipo´teses do trabalho podem ser vistas a seguir.
4.2 Principais Contribuic¸o˜es
Este trabalho de mestrado demonstrou que a qualidade da visualizac¸a˜o esta´ relacionada
com a qualidade do resultado de consulta. Ou seja, quanto mais precisos os resultados de uma
consulta, melhor pode ser a organizac¸a˜o das imagens na visualizac¸a˜o.
Tambe´m foi explorada a hipo´tese de que o uso de mu´ltiplos descritores com condic¸a˜o de
contorno pode melhorar a qualidade da visualizac¸a˜o hiera´rquica de imagens em CBIR, utili-
zando o algoritmo Neihgbor Joining. Os testes demonstram que a te´cnica proposta por (BAR-
ROSO et al., 2015), apesar de representar um nı´vel de precisa˜o pro´ximo do nı´vel de precisa˜o
medido pelo melhor descritor individual, tende a melhorar a a´rvore de similaridade gerada.
A visualizac¸a˜o hiera´rquica escolhida para o trabalho, a Neighbor Joining (SAITOU; NEI,
1987), e´ um dos me´todos mais utilizados para a construc¸a˜o de uma a´rvore filogene´tica. Essa
te´cnica, adaptada para a criac¸a˜o de a´rvores de similaridade, utiliza a ideia de encontrar pares
de instaˆncias mais pro´ximas em uma colec¸a˜o de dados, de modo a minimizar o comprimento
e o nu´mero de ramos da a´rvore gerada (PAIVA, 2012). Ela tem sido utilizada no contexto de
classificac¸a˜o visual de dados (ELER et al., 2008, 2009; PAIVA et al., 2011; CRUZ, 2012; PAIVA,
2012).
Este trabalho contribui para que as te´cnicas de mu´ltiplos descritores com condic¸o˜es de
contorno e visualizac¸a˜o baseada em a´rvore de similaridade NJ possam ser mais utilizadas no
contexto de sistemas CBIR, pois demonstra que o uso da primeira melhora a qualidade da
segunda.
A medida de qualidade da visualizac¸a˜o de imagens neighborhood hit (PAULOVICH et al.,
2008) indica maior porcentagem de vizinhos mais pro´ximos de uma imagem na visualizac¸a˜o
(que pertencem a` mesma classe da imagem de consulta) ao se utilizar a te´cnica de mu´ltiplos
descritores com condic¸o˜es de contorno (BARROSO et al., 2013).
4.3 Trabalhos Futuros 59
4.3 Trabalhos Futuros
Os experimentos relacionados a hipo´tese inicial deste trabalho sobre a correlac¸a˜o de quali-
dade do resultado da consulta com a qualidade da visualizac¸a˜o gerada testou apenas a visualizac¸a˜o
baseada em a´rvore de similaridade NJ. E´ interessante testar essa correlac¸a˜o utilizando outras
te´cnicas de visualizac¸a˜o. Outro trabalho futuro interessante e´ integrar a visualizac¸a˜o NJ a` con-
sulta propriamente dita.
4.4 Considerac¸o˜es Finais
Neste capı´tulo foram apresentadas as concluso˜es deste trabalho de mestrado. Foram levan-
tadas as hipo´teses de correlac¸a˜o entre a qualidade do resultado de consulta em sistemas CBIR e
a qualidade da visualizac¸a˜o gerada nessas consultas e, tambe´m, do impacto do uso de mu´ltiplos
descritores com condic¸o˜es de contorno na visualizac¸a˜o baseada em a´rvore de similaridade NJ.
Foi relatado que experimentos realizados demonstram que a primeira hipo´tese pode ser verda-
deira, pore´m, indicou-se mais testes como trabalho futuro. Por fim, conclui-se que a segunda
hipo´tese demonstra que o uso de mu´ltiplos descritores com condic¸o˜es de contorno melhora a
qualidade da a´rvore NJ gerada na consulta por similaridade em sistemas CBIR.
REFEREˆNCIAS
AKGu¨L, C. B. et al. Content-based image retrieval in radiology: Current status and future
directions. Journal of Digital Imaging, Springer-Verlag, v. 24, n. 2, p. 208–222, 2011. ISSN
0897-1889. Disponı´vel em: <http://dx.doi.org/10.1007/s10278-010-9290-9>.
AKSOY, S.; HARALICK, R. M. Using texture in image similarity and retrieval. In: Physical
Chemistry Chemical Physics 98(9):1185–1193. [S.l.]: World Scienti, 2000. p. 129–149.
AKSOY, S.; HARALICK, R. M. Feature normalization and likelihood-based simi-
larity measures for image retrieval. Pattern Recognition Letters, v. 22, n. 5, p. 563
– 582, 2001. ISSN 0167-8655. Image/Video Indexing and Retrieval. Disponı´vel em:
<www.sciencedirect.com/science/article/pii/S0167865500001124>.
BAEZA-YATES, R. A.; RIBEIRO-NETO, B. Modern Information Retrieval. Boston, MA,
USA: Addison-Wesley Longman Publishing Co., Inc., 1999. ISBN 020139829X.
BARIONI, M. C. N. Operac¸o˜es de consulta por similaridade em grandes ba-
ses de dados complexos. Tese (Doutorado) — Instituto de Cieˆncias Matema´ticas
e de Computac¸a˜o, Universidade de Sa˜o Paulo, Sa˜o Carlos, 2006. Disponı´vel em:
<http://www.teses.usp.br/teses/disponiveis/55/55134/tde-28092006-151225/>.
BARROSO, R. F. et al. Using boundary conditions for combining multiple descriptors in
similarity based queries. In: . Progress in Pattern Recognition, Image Analysis, Computer
Vision, and Applications: 18th Iberoamerican Congress, CIARP 2013, Havana, Cuba,
November 20-23, 2013, Proceedings, Part I. Berlin, Heidelberg: Springer Berlin Heidelberg,
2013. p. 375–382. ISBN 978-3-642-41822-8.
BARROSO, R. F. et al. Speeding up the combination of multiple descriptors for different
boundary conditions. In: 2015 Latin American Computing Conference (CLEI). [S.l.: s.n.],
2015. p. 1–11.
BHATT, C.; KANKANHALLI, M. Multimedia data mining: state of the art and challenges.
Multimedia Tools and Applications, Springer US, v. 51, n. 1, p. 35–76, 2011. ISSN 1380-7501.
Disponı´vel em: <http://dx.doi.org/10.1007/s11042-010-0645-5>.
BUENO, R. et al. Using visual analysis to weight multiple signatures to discriminate complex
data. In: 2011 15th International Conference on Information Visualisation. [S.l.: s.n.], 2011. p.
282–287. ISSN 1550-6037.
BUGATTI, P. H.; TRAINA, A. J. M.; TRAINA JR., C. Assessing the best integration
between distance-function and image-feature to answer similarity queries. In: Proce-
edings of the 2008 ACM Symposium on Applied Computing. New York, NY, USA:
Refereˆncias 61
ACM, 2008. (SAC ’08), p. 1225–1230. ISBN 978-1-59593-753-7. Disponı´vel em:
<http://doi.acm.org/10.1145/1363686.1363969>.
CRUZ, L. E. F. Uma abordagem baseada em te´cnicas de visualizac¸a˜o de informac¸o˜es
para avaliac¸a˜o de caracterı´sticas de imagens e aplicac¸o˜es. Dissertac¸a˜o (Mestrado) —
Instituto de Cieˆncias Matema´ticas e de Computac¸a˜o, Universidade de Sa˜o Paulo, Sa˜o Carlos,
2012. Disponı´vel em: <http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05122012-
095421/>.
Ca´CERES, S. M. P. Te´cnicas de visualizac¸a˜o para sistemas de recuperac¸a˜o
de imagens por conteu´do. Dissertac¸a˜o (Mestrado) — Instituto de Computac¸a˜o,
Universidade Estadual de Campinas, Campinas, 2010. Disponı´vel em:
<http://www.bibliotecadigital.unicamp.br/document/?code=000779382>.
DESELAERS, T.; KEYSERS, D.; NEY, H. Features for image retrieval - a quantitative
comparison. In: In DAGM 2004, Pattern Recognition, 26th DAGM Symposium. [S.l.: s.n.],
2004. p. 228–236.
DESELAERS, T.; KEYSERS, D.; NEY, H. Features for image retrieval: An experimental
comparison. Inf. Retr., Kluwer Academic Publishers, Hingham, MA, USA, v. 11, n. 2, p.
77–107, abr. 2008. ISSN 1386-4564. Disponı´vel em: <http://dx.doi.org/10.1007/s10791-007-
9039-3>.
DIAS, R. L. Minerac¸a˜o visual de imagens aliada a consultas pelos k-vizinhos diversos mais
pro´ximos: flexibilizando e maximizando o entendimento de consultas por conteu´do de imagens.
Dissertac¸a˜o (Mestrado) — Universidade Federal de Sa˜o Carlos, Sa˜o Carlos, 2013. Disponı´vel
em: <https://repositorio.ufscar.br/handle/ufscar/557>.
ELER, D. M. et al. Multidimensional visualization to support analysis of image collections.
In: 2008 XXI Brazilian Symposium on Computer Graphics and Image Processing. [S.l.: s.n.],
2008. p. 289–296. ISSN 1530-1834.
ELER, D. M. et al. Visual analysis of image collections. The Visual Computer, v. 25, n. 10,
p. 923–937, 2009. ISSN 1432-2315. Disponı´vel em: <http://dx.doi.org/10.1007/s00371-009-
0368-7>.
ENGEL, D. et al. Structural decomposition trees. Computer Graphics Forum, Blackwell
Publishing Ltd, v. 30, n. 3, p. 921–930, 2011. ISSN 1467-8659. Disponı´vel em:
<http://dx.doi.org/10.1111/j.1467-8659.2011.01941.x>.
FEKETE, J.-D. The infovis toolkit. In: Proceedings of the IEEE Symposium on Information
Visualization. Washington, DC, USA: IEEE Computer Society, 2004. (INFOVIS ’04), p. 167–
174. ISBN 0-7803-8779-3. Disponı´vel em: <http://dx.doi.org/10.1109/INFOVIS.2004.64>.
GRAF, F. JFeatureLib v1.6.3. out. 2015. Disponı´vel em:
<http://dx.doi.org/10.5281/zenodo.31793>.
HARALICK, R. M.; SHANMUGAM, K.; DINSTEIN, I. Textural features for image
classification. IEEE Transactions on Systems, Man, and Cybernetics, SMC-3, n. 6, p. 610–621,
Nov 1973. ISSN 0018-9472.
Refereˆncias 62
HUANG, P.; DAI, S. Image retrieval by texture similarity. Pattern Recog-
nition, v. 36, n. 3, p. 665 – 679, 2003. ISSN 0031-3203. Disponı´vel em:
<www.sciencedirect.com/science/article/pii/S0031320302000833>.
KASS, M.; WITKIN, A.; TERZOPOULOS, D. Snakes: Active contour models. International
Journal of Computer Vision, v. 1, n. 4, p. 321–331, 1988. ISSN 1573-1405. Disponı´vel em:
<http://dx.doi.org/10.1007/BF00133570>.
KHOTANZAD, A.; HONG, Y. H. Invariant image recognition by zernike moments.
IEEE Trans. Pattern Anal. Mach. Intell., IEEE Computer Society, Washington,
DC, USA, v. 12, n. 5, p. 489–497, maio 1990. ISSN 0162-8828. Disponı´vel em:
<http://dx.doi.org/10.1109/34.55109>.
KUMAR, A. et al. Content-based medical image retrieval: A survey of applications to
multidimensional and multimodality data. Journal of Digital Imaging, Springer US, v. 26, n. 6,
p. 1025–1039, 2013. ISSN 0897-1889. Disponı´vel em: <http://dx.doi.org/10.1007/s10278-
013-9619-2>.
KURTZ, C. et al. A hierarchical knowledge-based approach for retrieving simi-
lar medical images described with semantic annotations. Journal of Biomedical
Informatics, v. 49, n. 0, p. 227 – 244, 2014. ISSN 1532-0464. Disponı´vel em:
<http://www.sciencedirect.com/science/article/pii/S1532046414000574>.
LAMPING, J.; RAO, R.; PIROLLI, P. A focus+context technique based on hyperbolic
geometry for visualizing large hierarchies. In: Proceedings of the SIGCHI Conference on
Human Factors in Computing Systems. New York, NY, USA: ACM Press/Addison-Wesley
Publishing Co., 1995. (CHI ’95), p. 401–408. ISBN 0-201-84705-1. Disponı´vel em:
<http://dx.doi.org/10.1145/223904.223956>.
LIU, Y. et al. A survey of content-based image retrieval with high-level semantics.
Pattern Recognition, v. 40, n. 1, p. 262 – 282, 2007. ISSN 0031-3203. Disponı´vel em:
<www.sciencedirect.com/science/article/pii/S0031320306002184>.
PAIVA, J. et al. Improved similarity trees and their application to visual data classification.
Visualization and Computer Graphics, IEEE Transactions on, v. 17, n. 12, p. 2459–2468, Dec
2011. ISSN 1077-2626.
PAIVA, J. G. d. S. Te´cnicas computacionais de apoio a` classificac¸a˜o visual de
imagens e outros dados. Tese (Doutorado) — Instituto de Cieˆncias Matema´ticas
e de Computac¸a˜o, Universidade de Sa˜o Paulo, Sa˜o Carlos, 2012. Disponı´vel em:
<http://www.teses.usp.br/teses/disponiveis/55/55134/tde-02042013-084718/>.
PAULOVICH, F. V. et al. Least square projection: A fast high-precision multidimensional
projection technique and its application to document mapping. IEEE Transactions on
Visualization and Computer Graphics, v. 14, n. 3, p. 564–575, May 2008. ISSN 1077-2626.
POCO, J. et al. A framework for exploring multidimensional data with 3d projections. In:
Proceedings of the 13th Eurographics / IEEE - VGTC Conference on Visualization. Chichester,
UK: The Eurographs Association &#38; John Wiley &#38; Sons, Ltd., 2011. (EuroVis’11), p.
1111–1120. Disponı´vel em: <http://dx.doi.org/10.1111/j.1467-8659.2011.01960.x>.
Refereˆncias 63
RAHMAN, M. et al. Multimodal biomedical image retrieval using hierarchical classification
and modality fusion. International Journal of Multimedia Information Retrieval,
Springer London, v. 2, n. 3, p. 159–173, 2013. ISSN 2192-6611. Disponı´vel em:
<http://dx.doi.org/10.1007/s13735-013-0038-4>.
RIBEIRO, M. X. Suporte a sistemas de auxı´lio ao diagno´stico e de recuperac¸a˜o de imagens por
conteu´do usando minerac¸a˜o de regras de associac¸a˜o. Tese (Doutorado) — Instituto de Cieˆncias
Matema´ticas e de Computac¸a˜o, Universidade de Sa˜o Paulo, Sa˜o Carlos, 2008. Disponı´vel em:
<http://www.teses.usp.br/teses/disponiveis/55/55134/tde-16022009-144432/>.
ROBERTSON, G. G.; MACKINLAY, J. D.; CARD, S. K. Cone trees: Animated 3d
visualizations of hierarchical information. In: Proceedings of the SIGCHI Conference on
Human Factors in Computing Systems. New York, NY, USA: ACM, 1991. (CHI ’91), p. 189–
194. ISBN 0-89791-383-3. Disponı´vel em: <http://doi.acm.org/10.1145/108844.108883>.
SAITOU, N.; NEI, M. The neighbor-joining method: a new method for reconstructing
phylogenetic trees. Molecular Biology and Evolution, v. 4, n. 4, p. 406, 1987. Disponı´vel em:
<+ http://dx.doi.org/10.1093/oxfordjournals.molbev.a040454>.
SONKA, M.; HLAVAC, V.; BOYLE, R. Image Processing, Analysis, and
Machine Vision. PWS Pub., 1999. ISBN 9780534953935. Disponı´vel em:
<https://books.google.com.br/books?id=TPRRAAAAMAAJ>.
TANBEER, S. K. et al. Efficient single-pass frequent pattern mining using a prefix-tree.
Information Sciences, v. 179, n. 5, p. 559 – 583, 2009. ISSN 0020-0255. Special Section -
Quantum Structures: Theory and Applications Workshop “Quantum Structures”. Disponı´vel
em: <http://www.sciencedirect.com/science/article/pii/S0020025508004532>.
TORRES, R. da S. et al. A genetic programming framework for content-
based image retrieval. Pattern Recognition, v. 42, n. 2, p. 283 – 292, 2009.
ISSN 0031-3203. Learning Semantics from Multimedia Content. Disponı´vel em:
<www.sciencedirect.com/science/article/pii/S0031320308001623>.
YU, Z. et al. Visual query processing for efficient image retrieval using a som-based filter-
refinement scheme. Information Sciences, v. 203, n. 0, p. 83 – 101, 2012. ISSN 0020-0255.
Disponı´vel em: <http://www.sciencedirect.com/science/article/pii/S002002551200223X>.
GLOSSA´RIO
BLOB – Binary Large Object
CBIR – Content-Based Image Retrieval
Fast NJ – Fast Neighbor Joining
Fast PNJ – Fast Promoting Neighbor Joining
LSP – Least-Square Projection
MAE – Me´todo de Acesso Espacial
MAM – Me´todo de Acesso Me´trico
NJ – Neighbor Joining
PNJ – Promoting Neighbor Joining
P&R – Precisa˜o e Revocaca˜o
Rapid NJ – Rapid Neighbor Joining
Rapid PNJ – Rapid Promoting Neighbor Joining
SGBD – Sistema Gerenciador de Banco de Dados
Apendice A
UTILIZANDO A BIBLIOTECA JFEATURELIB PARA
EXTRAIR VETORES DE CARACTERI´STICAS DE
IMAGENS EM JAVA
JFeatureLib e´ uma biblioteca livre em Java que oferece implementac¸o˜es de va´rios extratores
de caracterı´sticas de imagens e detectores de ponto / regia˜o principalmente utilizados no a´rea
de pesquisa de Visa˜o Computacional (GRAF, 2015).
A biblioteca esta´ disponı´vel atrave´s de seu projeto no GitHub, na pa´gina:
<https://github.com/locked-fg/JFeatureLib>. (Acesso em: 30/01/2017)
A.1 Extratores de caracterı´sticas implementados
•AutoColorCorrelogram
•CEDD
•Color Histogram
•FCTH
•Fuzzy Histogram
•FuzzyOpponentHistogram
•Gabor
A.2 Como utilizar 66
•Haralick Texture Features
•Histograms:
–Gray-Histogram
–RGB Histogram
–HSB Histogram
•JCD
•LumnanceLayout
•MPEG7ColorLayout
•MPEG7EdgeHistogram
•Statistical Moments (os 4 primeiros: Mean, Standard Deviation, Skewneess e Kurtosis
OpponentHistorgam)
•PHoG (Pyramid Histograms of Oriented Gradients)
•ReferenceColorSimilarity
•SURF
•SIFT
•Tamura
•Thumbnail
A.2 Como utilizar
A.2.1 Extrair caracterı´sticas de va´rias classes de imagens:
Usando a linha de comando, as caracterı´sticas podem ser extraı´das pela classe Extractor.
Exemplo:
Neste exemplo teremos imagens de duas classes (classA, classB) e vamos extrair carac-
terı´sticas de textura dessas imagens, utilizando Haralick. Os vetores de caracterı´sticas devem
ser salvos num arquivo CSV.
Passo 1: Extrair as caracterı´sticas das imagens de classA e excrever em output.csv:
A.3 Co´digo de demonstrac¸a˜o e Wiki 67
java -jar JFeatureLib.jar -D HARALICK -c classA -d /images/of/classA -o /write/output.csv
Passo 2: Extrair as caracterı´sticas das imagens de classB, omitir o cabec¸alho (-nh) e anexar
em output.csv:
java -jar JFeatureLib.jar -D HARALICK -c classB -nh -d /images/of/classB –append -o
/write/output.csv
A.2.2 Opc¸o˜es
As opc¸o˜es da classe Extractor podem ser exibidas simplesmente ao chamar a classe sem
argumentos, ou com a opc¸a˜o –help (x.x.x e´ a versa˜o da biblioteca que esta´ sendo utilizada):
java -jar JFeatureLib-x.x.x-jar-with-dependencies.jar –help
Opc¸a˜o Descric¸a˜o
–append anexa / acrescenta no arquivo de saı´da
(padra˜o: falso = sobrescrever)
–help exibe essas opc¸o˜es
–list-capabilities lista os descritores registrados e a saı´da
dos seus me´todos suportados
–threads N quantidade de threads
(padra˜o: quantidade de processadores disponı´veis)
–unpack-properties extrai as propriedades padra˜o e de logging para o direto´rio atual
-D (–descriptor) VAL usar este descritor de caracterı´sticas (ex.: SIFT)
-c VAL classe da imagem que deve ser escrita no arquivo de saı´da
-d (–src-dir) FILE direto´rio contendo as imagens
-m (–masks-dir) FILE direto´rio contendo ma´scaras
-nh omitir cabec¸alho
-o (–output-dir) FILE arquivo de saı´da (padra˜o: features.csv)
-r acessar os direto´rios recursivamente (padra˜o: na˜o)
-v exibir mensagens de debug
Tabela A.1: Lista de opc¸o˜es de linha de comando para extrac¸a˜o de caracterı´sticas com jFeatureLib
A.3 Co´digo de demonstrac¸a˜o e Wiki
Alguns co´digos de demonstrac¸a˜o podem ser encontrados em:
<https://github.com/locked-fg/JFeatureLib-Demo>. Acesso em (30/01/2017)
A wiki do projeto com mais informac¸o˜es pode ser acessada em:
<https://github.com/locked-fg/JFeatureLib/wiki>. Acesso em (30/01/2017)