X Workshop de Teses e Dissertações em Banco de Dados
Análise comparativa de técnicas para armazenagem de dados
passı́veis de consultas por similaridade ∗
Pedro Lopes de Souza1 ,
Prof. Dr. Caetano Traina Júnior1
1
Pós-Graduação em Ciências de Computação e Matemática Computacional
Instituto de Ciências Matemáticas e de Computação (ICMC)
Universidade de São Paulo (USP)
São Carlos, SP, Brasil
{desouza, caetano}@icmc.usp.br
Nı́vel: Mestrado
Ano de ingresso no programa: 2010
Exame de qualificação: Março de 2011
Época esperada de conclusão: Março de 2012
Resumo. A complexidade dos dados armazenados em grandes bases de dados
aumenta cada vez mais, criando a necessidade de novas operações de consulta. Uma classe de operações que tem apresentado interesse crescente são
as chamadas Consultas por Similaridade, sendo as mais conhecidas e utilizadas as consultas por abrangência (Range query – Rq) e aos k-vizinhos mais
próximos (k-Nearest Neighbors – k-NN). Até recentemente, essas consultas não
dispunham de algoritmos suficientemente robustos e eficientes para que elas
pudessem ser incorporadas aos Sistemas de Gerenciamento de Bases de Dados (SGBD). Essa situação esta mudando, e já é possı́vel conceber cenários
onde consultas por similaridade sejam integradas ao SGBD. O GBdI-ICMCUSP vem desenvolvendo um protótipo inicial de um interpretador para uma
extensão da Linguagem SQL que incorpora comandos para expressar e executar condições de consulta por similaridade associadas às demais condições
tradicionais. No entanto, esse protótipo tem indicado que diferentes maneiras
de armazenar os dados a serem pesquisados por similaridade pode levar a velocidades de resposta muito diferentes. Este projeto visa dar continuidade ao
desenvolvimento desse protótipo, investigando técnicas e algoritmos de armazenagem de dados, especialmente imagens, visando aumentar o escopo do suporte
que pode ser dado em ambientes práticos reais a consultas por similaridade sobre esses dados em SGBD Relacionais.
Palavras-chave: Base de dados relacionais, sistema de arquivos, estruturas de
armazenamento, imagens médicas, consultas por similaridade.
∗
Os autores agradecem o apoio financeiro das seguintes agências de fomento à pesquisa do Brasil:
CNPq, CAPES e FAPESP.
69
X Workshop de Teses e Dissertações em Banco de Dados
1. Introdução
Inicialmente, os Sistemas de Gerenciamento de Bases de Dados Relacionais (SGBDRs)
foram desenvolvidos para suportar o armazenamento e a recuperação apenas de dados
numéricos ou textuais curtos, os chamados dados tradicionais ou simples. Entretanto,
a informação moderna não é, na maioria dos casos, representada por um dado tradicional. Ela pode ser representada por novos tipos de estruturas, tais como as informações
de natureza multimı́dia ou conjuntos de dados tradicionais, as séries temporais e dados
geográficos por exemplo. Os SGBDRs modernos precisaram incorporar tais dados complexos (como são chamados) e por isso surgiu a necessidade de desenvolver novas técnicas
para permitir o armazenamento e a recuperação desses objetos de forma eficiente.
Uma técnica empregada é a busca baseada nas consultas por similaridade. Estas
procuram, em um conjunto de dados, os elementos que, segundo algum critério de similaridade, sejam os mais “parecidos” a um determinado elemento. Uma área de vasta
aplicação é a saúde, onde um conjunto diverso de imagens e metadados é produzido por
diferentes equipamentos médicos, sendo necessário atender a diversos profissionais da
saúde [Azevedo Marques e Salomão 2009] em que se compara por similaridade séries de
sinais e imagens digitais de exames.
Neste contexto, questiona-se a relevância de utilizar o sistema de arquivos ou o
SGBDR para armazenar os dados complexos, mais precisamente as imagens médicas.
Este projeto de mestrado tem como objetivo desenvolver um conjunto finito de protótipos
envolvendo o armazenamento de imagens e metadados em sistemas de arquivos e bancos
de dados, avaliando o impacto que essas arquiteturas causam nas consultas por similaridade em imagens médicas. Para isso, será realizado um estudo de casos no protótipo
SImilarity Retrievel ENgine (SIREN) [Barioni 2006], modificando sua estrutura de armazenagem para trabalhar em diversas arquiteturas de armazenamento.
O restante deste artigo está estruturado em mais cinco seções. A Seção 2 descreve
o SIREN. A Seção 3 sintetiza os fundamentos e trabalhos correlatos. A Seção 4 e 5
descrevem a proposta e as atividades em andamento respectivamente. O artigo é concluı́do
na Seção 6 com as considerações finais e trabalhos futuros.
2. SIREN
O SIREN foi implementado para validar a adequação da proposta de extensão da linguagem SQL padrão para permitir a realização de consultas por similaridade. O protótipo
implementa um serviço entre um SGBDR convencional e os programas de aplicação. Este
serviço intercepta todo comando SQL enviado por uma aplicação, tratando as construções
sintáticas relacionadas às operações por similaridade [Barioni 2006].
O SIREN implementa um tipo de dado adicional aos tradicionais denominado
StillImage. Esse novo tipo de dado permite armazenar imagens e associá-las com diversos extratores e funções de distância. As consultas são agilizadas através da indexação
em métodos de acesso métricos. O SIREN suporta consultas por abrangência (Rq) e kvizinhos mais próximos (k-NN). O Rq retorna os elementos dentro de um certo limiar e o
k-NN retorna os k elemetos mais próximos do elemento de consulta. Uma consulta que
retorna as 5 imagens mais próximas utilizando uma métrica de textura na extensão de
SQL implementada pelo SIREN é a seguinte:
70
X Workshop de Teses e Dissertações em Banco de Dados
SELECT E.Id, E.Imagem
FROM Exame E
WHERE E.Foto NEAR ’C:\exemplo.jpq’
BY Textura STOP AFTER 5
Após identificar o tipo de consulta por similaridade e seus parâmetros, o interpretador informa ao indexador os extratores de caracterı́sticas da métrica especificada, a
função de distância e a estrutura de ı́ndice a serem utilizados na execução do comando. O
indexador retorna os identificadores das imagens que compõe o resultado final. O interpretador reescreve a consulta para SQL padrão que será interpretado pelo SGBDR.
3. Fundamentação e trabalhos correlatos
Em todo o mundo, os centros médicos organizam seus sistemas de informação para
que o fluxo de dados ocorra de forma consistente [Azevedo Marques e Salomão 2009]
[Petra Welter e Günther 2009]. No setor radiológico, os Sistemas de Informações Hospitalares (Hospital Information System – HIS) correspondem ao sistema de informação
mais geral e são responsáveis por auxiliar computacionalmente os procedimentos operacionais de um hospital, processando informações administrativas e relativas a pacientes
(exames e procedimentos médicos realizados). O sistema de informação intermediário
corresponde aos Sistemas de Informações Radiológicas (Radiology Information System
– RIS) e são responsáveis por controlar os processos básicos e de rotina do ambiente radiológico, manutenção da base de dados dos pacientes, geração de laudos e relatórios,
agendamento e geração de procedimentos. O sistema de informação mais especı́fico corresponde aos Sistemas de Comunicação e Arquivamento de Imagens (Picture Archiving
and Communication System – PACS), responsáveis pelo armazenamento, gerenciamento
e disponibilização das imagens médicas.
Atualmente existem vários sistemas disponı́veis para a manipulação de imagens
em geral que poderiam ser especializados para imagens médicas. Dentre os mais populares pode-se citar o QBIC, Virage, Photobook, Chabot, VisualSeek, SurfImage e Netra
[Rui et al. 1999]. Esses sistemas utilizam caracterı́sticas intrı́nsecas da imagem e metadados associados a ela para a extração de caracterı́sticas utilizadas nos cálculos de similaridade. Contudo esses sistemas precisam ser adaptados para se adequar a área médica, pois
suas métricas precisam garantir resultados precisos quando especializados em as imagens
médicas [Bhagat e Atique 2011].
Os sistemas voltados para consultas por similaridade em imagens médicas
utilizam o PACS como repositório de imagens e aplicam as extrações de caracterı́sticas no padrão DICOM (Digital Imaging and Communications in Medicine)
[Azevedo Marques e Salomão 2009]. Este padrão trata de diversos aspectos além da
imagem, incluindo o formato das imagens e o protocolo para a criação, acesso e principalmente a transmissão das imagens entre equipamentos e instituições. Em geral as
aplicações se apóiam em frameworks que suportam a manipulação de dados complexos,
tais como o Oracle Multimı́dia e PANDA [Bhagat e Atique 2011].
4. Proposta
Devido a complexidade de recursos e formas de armazenamento, nem toda a funcionalidade do PACS pode ser substituı́da pelo SGBD. Além disso, sendo um sistema proprietário, um PACS somente trabalha com as imagens que estão na estrutura de arquivos
71
X Workshop de Teses e Dissertações em Banco de Dados
que ele controla. Assim, não é possı́vel prescindir de um PACS em uma ambiente de
informatização hospitalar. Por outro lado, as imagens são mantidas num PACS independentemente uma das outras, de maneira que elas são requisitadas diretamente por seu
identificador unı́voco, registrado na realização do exame para que possam ser recuperadas posteriormente. Portanto mantê-las apenas no PACS dificulta e degrada muito as
consultas por conteúdo, seja sobre as imagens, seja sobre os dados de seus cabeçalhos.
A solução que vem sendo adotada é extrair o cabeçalho DICOM e replicálo na base de dados, guardando somente o endereço do arquivo contendo a imagem
no sistema de arquivos do PACS para recuperá-la [Guld et al. 2007, Stoian et al. 2008,
Kobayashi et al. 2009]. Estender essa abordagem ao SIREN implica em guardar o
cabeçalho também na base de dados. No entanto, essa abordagem torna o sistema muito
frágil quanto à consistência entre o que é mantido na base e os arquivos de imagens, uma
vez que uma imagem pode ser processada e/ou modificada no sistema de arquivos sem
que seja feita a atualização correspondente na base de dados. A Figura 1 ilustra como
ocorre atualmente o fluxo de dados entre os sistemas.
Figura 1. Uma consulta por similaridade requer uma base com os vetores de
caracterı́sticas e demais dados extraı́dos do DICOM. Os sistemas processam a
consulta com os dados do SGBD, acessando as imagens escolhidas no PACS.
A abordagem atual adotada pelo SIREN é manter todo o conjunto de dados, inclusive as imagens, dentro do SGBD. As tabelas definidas pelo usuário que contenham
objetos do tipo StillImage são modificadas pelos interpretador de comandos quando instanciadas. Cada atributo StillImage é substituı́do por uma referência a uma tabela controlada pelo SIREN. Cada referência possui um identificador, o atributo BLOB que armazena
a imagem e o conjunto de atributos que armazenam as caracterı́sticas extraı́das pelos extratores utilizados em cada métrica associada ao tipo StillImage. Esta reorganização de
tabelas é transparente ao usuário, pois as consultas são realizadas sobre as tabelas originalmente definidas pelo usuário como ilustra o exemplo na Seção 2.
Neste projeto, pretende-se avaliar mais precisamente o impacto das duas abordagens, e buscar medidas que possam ser adotadas para aliviar os problemas de cada uma.
Espera-se que este estudo permita identificar a influência da arquitetura do SGBDR, seus
mecanismos de otimização e consistência, sobre a eficiência nas consultas por similaridade. As atividades estão concentradas na definição das arquiteturas de armazenamento;
72
X Workshop de Teses e Dissertações em Banco de Dados
realização de consultas por similaridade e avaliação e comparação dos desempenhos. Os
métodos de avaliação das propostas irão comparar o tempo, consistência e escalabilidade
das consultas realizadas em cada arquitetura, utilizando o conjunto de dados fornecidos
pelo Hospital das Clı́nicas da Faculdade de Medicina de Ribeirão Preto (HCFMRP).
5. Atividades em andamento
As atividades em andamento estão concentradas no estudo, definição e implementação
das arquiteturas de armazenamento.
Foram propostas três arquiteturas para armazenar os dados no SIREN. Todos os
cenários dividem os dados em três grupos: o grupo das tabelas definidas pelo usuário, o
grupo das tabelas com os vetores de caracterı́sticas extraı́das da imagem, e o grupo de
repositório de imagens. A tabela de usuário possui todos os atributos tradicionais associados à imagem e para cada tipo StillImage existe referências para os outros dois grupos
de dados. A tabela com os vetores de caracterı́sticas possui a referência ao StillImage e
o vetor de caracterı́stica extraı́dos da imagem pela métrica definida na tabela de usuário.
O repositório possui a referência ao StillImage e armazena as imagens. O grupo de repositório de imagens é detalhado a seguir para cada cenário de arquitetura (Figura 2).
Figura 2. Arquiteturas propostas. (a) Imagens por atributo e (b) Imagens globais,
ambos dentro do SGBDR; (c) Imagens globais dentro do sistema de arquivos.
O primeiro cenário, Figura 2(a), armazena as imagens dentro do SGBDR por atributo StillImage. Para cada StillImage instanciado, a imagem correspondente é armazenada no banco. Isso permite que uma mesma imagem seja armazenada mais de uma vez.
Isto ocorre, por exemplo, quando se aplica diferentes métricas para a mesma imagem.
O segundo cenário, Figura 2(b), busca reduzir o volume de imagens armazenadas
causado pelo primeiro cenário. Logo, diferentes instâncias do StillImage podem referenciar a mesma imagem. No entanto, é necessário um número maior de referências com as
tabelas de atributo e usuário, fortalecendo a correlação entre os atributos.
Já o terceiro cenário, Figura 2(c) busca simular a situação atual dos sistemas de
consultas por similaridades que utilizam o PACS. Todas as imagens estão no sistema de
arquivos e são referênciadas conforme os vetores de caracterı́sticas relacionados a cada
imagem.
73
X Workshop de Teses e Dissertações em Banco de Dados
O SGBDR utilizado para implementar as arquiteturas é o Oracle Database 11g e
as imagens inseridas no formato BLOB. Os sistema de arquivos é o NTFS e o conjunto de
imagens é formado por 800 imagens de exames de tomografia computadorizada, divididas
em quatro classes com 200 imagens cada: crânio axial, crânio coronal, crânio sagital e
espinha sagital. As imagens foram fornecidas pelo setor radiológico do HCFMRP.
6. Considerações finais e próximas atividades
Os sistemas de apoio a área médica tem atraı́do bastante interesse devido ao grande volume de dados produzidos, processados e armazenados nos setores hospitalares. Contudo
o sistema PACS utilizado para o armazenamento dos dados não viabiliza consultas por
similaridade. Desta forna, os centros de pesquisa o utilizam para acessar as imagens
mas processam grande parte da consulta em aplicativos especı́ficos que usam repositórios
próprios. Este projeto de mestrado concentra-se em responder o questionamento que diz
respeito a avaliar técnicas de armazenagem das imagens internamente a base de dados,
por meio de um estudo de casos envolvendo diferentes cenários na plataforma SIREN.
As próximas atividades a serem realizadas envolvem o término da implementação
dos cenários e aplicação de consultas por similaridade, utilizando uma mesma base de
dados real obtida em pesquisa colaborativa com o HCFMRP. As consultas irão emular as
consultas reais realizadas pelos profissionais de saúde. Isso implica em consultas mais
elaboradas, pois envolvem atributos tradicionais e complexos. A complexidade das consultas afetam diretamente os acessos a disco, podendo apresentar comportamentos diferentes dependendo do repositório de imagens. Por fim, a validação será realizada conforme o tempo, consistência e escalabilidade das consultas realizadas em cada cenário.
Referências
Azevedo Marques, P. M. D. e Salomão, S. C. (2009). PACS : Sistemas de Arquivamento
e Distribuição de Imagens. Rev Bras Fis Med, 3(1):131–139.
Barioni, M. C. N. (2006). SIREN : A Similarity Retrieval Engine for Complex Data.
InterMedia, pages 1155–1158.
Bhagat, A. P. e Atique, M. (2011). Medical image retrieval, indexing and enhancement
techniques: a survey. In ICCCS’11, pages 387–390. ACM.
Guld, M. O., Thies, C., Fischer, B., e Lehmann, T. M. (2007). A generic concept for the
implementation of medical image retrieval systems. IJMI, 76:252–259.
Kobayashi, L. O. M., Furuie, S. S., e Barreto, P. S. L. M. (2009). Providing integrity and
authenticity in DICOM images: a novel approach. IEEE TITB, 13:582–589.
Petra Welter, Thomas M. Deserno, B. F. B. B. W. B. O. e Günther, R. W. (2009). Integration of cbir in radiological routine in accordance with ihe. 7264(1):726404.
Rui, Y., Huang, T. S., e Chang, S.-F. (1999). Image retrieval: Current techniques, promising directions, and open issues. JVCIR, 10(1):39–62.
Stoian, A., Ivan, R., Stoian, I., e Marichescu, A. (2008). Current trends in medical imaging acquisition and communication. In AQTR ’08, pages 94–99. IEEE.
74