Os grandes centros médicos e hospitais de todo o mundo têm procurado integrar as informações de seus pacientes incluindo os exames de imagens efetuados (tomografia computadorizada, tomografia por ressonância magnética, ultrasson, medicina nuclear, etc.). Um sistema que integra as imagens junto às informações tradicionais é chamado de Sistema de Arquivamento e Comunicação de Imagens (Picture Archive and Communication System - PACS). Os sistemas PACS comerciais associam as imagens de exames às informações de pacientes através de chaves de consultas textuais e numéricas, não suportando consultas baseadas no conteúdo pictórico das imagens. Entretanto, muitas vezes o médico gostaria de recuperar as imagens armazenadas que fossem semelhantes (similares) a uma determinada imagem de consulta. Por exemplo, seja a consulta: "encontre as 10 imagens mais semelhantes à imagem Raio-X-tórax do Jõao da Silva". Ao responder a consultas desse tipo, o sistema permite que o médico relembre casos ocorridos anteriormente. Além disso, o conhecimento já gerado de exames e tratamentos anteriores pode ser recuperado mais rapidamente do que utilizando apenas a memória humana ou um sistema não automático de recuperação de informações. Um sistema com a capacidade de recuperar imagens utilizando o seu conteúdo pictórico é uma ferramenta valiosa para o auxílio ao diagnóstico médico. Esta tese apresenta a arquitetura de um PACS atualmente em desenvolvimento. Este sistema está sendo denominado mini-PACS. Tal sistema necessita da integração de três sistemas, a saber: - Um Sistema de Processamento de Imagens (SPI), o qual é responsável pela leitura e pré-processamento das imagens que são recebidas de diferentes dispositivos e possuem diferentes formatos. O SPI extrai as características relevantes das imagens, as quais serão utilizadas para a sua indexação e recuperação por conteúdo. - Um Sistema de Gerenciamento de Bases de Dados e Imagens (SGBDI), que permite a armazenagem e a recuperação de imagens baseada em seu conteúdo. O SGBDI utiliza uma estrutura métrica, a Slim-tree, que indexa as imagens através das características extraídas pelo SPI e possibilita responder consultas por similaridade. - Um Servidor de Web (SW), que disponibiliza o acesso às informações através da internet. A construção do Servidor de Web encontra-se fora do escopo do desenvolvimento desta tese. Porém, testes iniciais sobre a transferência e comunicação de imagens utilizando um servidor e aplicativos Java foram desenvolvidos para avaliar o comportamento do sistema. Entre as principais contribuições deste trabalho encontra-se um novo método de extração de características de imagens chamado histograma métrico. Os histogramas métricos permitem comparar imagens de diferentes tamanhos e mapeadas em faixas de quantização diferentes (se a alteração de brilho for linear). O tempo de resposta às consultas por similaridade utilizando histogramas métricos é, em média, 5 vezes menor do que o tempo de resposta utilizando histogramas tradicionais. Para permitir a indexação das imagens utilizando a Slim-tree foi necessário desenvolver uma nova função de distância métrica. Tal função de distância utiliza a diferença entre as áreas das curvas do histograma métrico. A construção da árvore de indexação utilizando os histogramas métricos chega a ser 10 vezes mais rápida do que com os histogramas tradicionais. As inovações e aperfeiçoamentos oriundos deste trabalho estão sendo integrados ao mini-PACS. Este sistema vem sendo desenvolvido de forma conjunta entre o Grupo de Bases de Dados e Imagens (GDBI) do Instituto de Ciências Matemáticas e de Computação da USP e o Centro de Ciências de Imagens e Física Médica (CCIFM) da Faculdade de Medicina de Ribeirão Preto da USP.

Os grandes centros médicos e hospitais de todo o mundo têm procurado integrar as informações de seus pacientes incluindo os exames de imagens efetuados (tomografia computadorizada, tomografia por ressonância magnética, ultrasson, medicina nuclear, etc.). Um sistema que integra as imagens junto às informações tradicionais é chamado de Sistema de Arquivamento e Comunicação de Imagens (Picture Archive and Communication System - PACS). Os sistemas PACS comerciais associam as imagens de exames às informações de pacientes através de chaves de consultas textuais e numéricas, não suportando consultas baseadas no conteúdo pictórico das imagens. Entretanto, muitas vezes o médico gostaria de recuperar as imagens armazenadas que fossem semelhantes (similares) a uma determinada imagem de consulta. Por exemplo, seja a consulta: "encontre as 10 imagens mais semelhantes à imagem Raio-X-tórax do Jõao da Silva". Ao responder a consultas desse tipo, o sistema permite que o médico relembre casos ocorridos anteriormente. Além disso, o conhecimento já gerado de exames e tratamentos anteriores pode ser recuperado mais rapidamente do que utilizando apenas a memória humana ou um sistema não automático de recuperação de informações. Um sistema com a capacidade de recuperar imagens utilizando o seu conteúdo pictórico é uma ferramenta valiosa para o auxílio ao diagnóstico médico. Esta tese apresenta a arquitetura de um PACS atualmente em desenvolvimento. Este sistema está sendo denominado mini-PACS. Tal sistema necessita da integração de três sistemas, a saber: - Um Sistema de Processamento de Imagens (SPI), o qual é responsável pela leitura e pré-processamento das imagens que são recebidas de diferentes dispositivos e possuem diferentes formatos. O SPI extrai as características relevantes das imagens, as quais serão utilizadas para a sua indexação e recuperação por conteúdo. - Um Sistema de Gerenciamento de Bases de Dados e Imagens (SGBDI), que permite a armazenagem e a recuperação de imagens baseada em seu conteúdo. O SGBDI utiliza uma estrutura métrica, a Slim-tree, que indexa as imagens através das características extraídas pelo SPI e possibilita responder consultas por similaridade. - Um Servidor de Web (SW), que disponibiliza o acesso às informações através da internet. A construção do Servidor de Web encontra-se fora do escopo do desenvolvimento desta tese. Porém, testes iniciais sobre a transferência e comunicação de imagens utilizando um servidor e aplicativos Java foram desenvolvidos para avaliar o comportamento do sistema. Entre as principais contribuições deste trabalho encontra-se um novo método de extração de características de imagens chamado histograma métrico. Os histogramas métricos permitem comparar imagens de diferentes tamanhos e mapeadas em faixas de quantização diferentes (se a alteração de brilho for linear). O tempo de resposta às consultas por similaridade utilizando histogramas métricos é, em média, 5 vezes menor do que o tempo de resposta utilizando histogramas tradicionais. Para permitir a indexação das imagens utilizando a Slim-tree foi necessário desenvolver uma nova função de distância métrica. Tal função de distância utiliza a diferença entre as áreas das curvas do histograma métrico. A construção da árvore de indexação utilizando os histogramas métricos chega a ser 10 vezes mais rápida do que com os histogramas tradicionais. As inovações e aperfeiçoamentos oriundos deste trabalho estão sendo integrados ao mini-PACS. Este sistema vem sendo desenvolvido de forma conjunta entre o Grupo de Bases de Dados e Imagens (GDBI) do Instituto de Ciências Matemáticas e de Computação da USP e o Centro de Ciências de Imagens e Física Médica (CCIFM) da Faculdade de Medicina de Ribeirão Preto da USP.

O grau de similaridade entre elementos de dados é o fator primordial para a recuperação de informações em Sistemas Gerenciadores de Bases de Dados que manipulam dados complexos, como seqüências genéticas, séries temporais e dados multimídia (imagens, áudios, vídeos, textos longos). Para responder a essas consultas em um tempo reduzido, faz-se necessário utilizar métodos que usam métricas para avaliar a similaridade entre os elementos. Esses métodos são conhecidos como Métodos de Acesso Métricos. Dentre os mais conhecidos na literatura estão a M-tree e a Slim-tree. Existem duas maneiras de executar as operações de construção de índices em qualquer método de acesso: inserindo elemento a elemento ou usando a operação de carga-rápida (bulk-loading). O primeiro tipo de construção é comum e necessário para todo tipo de método de indexação dinâmico. Já as operações de carga-rápida são utilizadas para conjuntos de dados maiores, como por exemplo, na recuperação de backups em bases de dados ou na criação posterior de índices. Nessas situações, a inserção individual tende a ser mais demorada. Realizar uma carga-rápida possibilita a construção de índices com melhor eficiência e em menor tempo, pois há a disponibilidade de todos os dados no instante da criação da estrutura de índices, possibilitando explorar as propriedades do conjunto como um todo. Os Sistemas Gerenciadores de Base de Dados oferecem operações de carga-rápida dos dados nos métodos tradicionais, as quais devem ser supridas também nos Métodos de Acesso Métricos. Neste trabalho, são apresentadas três abordagens, uma técnica para carga-rápida dos dados em Métodos de Acesso Métricos e foi desenvolvido um algoritmo baseado nessa técnica para construir uma Slim-tree. Este é o primeiro algoritmo de carga-rápida baseada em amostragem que sempre produz uma Slim-tree válida, portanto é o primeiro descrito na literatura que pode ser incluído em um Sistema Gerenciador de Base de Dados. Os experimentos descritos neste trabalho mostram que o algoritmo proposto mantém bom agrupamento dos dados e supera o desempenho dos métodos de inserção seqüencial levando em conta tanto o desempenho de construção quanto à eficiência para realizar consultas / The similarity degree between data elements is the primordial factor for information retrieval in databases that handle complex data, such as genetic sequences, time series and multimedia objects (long images, audio, videos, texts). To answer these queries in a reduced time, it is necessary methods that use metrics to evaluate the similarity between elements. These methods are known as Metric Access Methods. The most known Metric Access Methods in the literature are the M-tree and the Slim-tree. There are two ways to build index in any access method: inserting element one by one or using the bulk-load operation. The first build type is very common and required for all kinds of dynamic access methods. The bulk-load operations are used for bigger datasets, as for example, in the recovery of backups and re-creation of database indexes. In these situations, the individual insertion takes much time. The bulk-load operation makes it possible to construct indexes more efficiently and faster, because it has the availability of the whole data when the index structure are created, and thus, it is possible to explore the properties of the whole set. Database Management Systems offer bulk-load operations for the traditional methods, so it is important that they can be also supplied for Metric Access Methods. This work presents three bulk-loading approaches and it proposes a technique to bulk-load data into Metric Access Methods. An algorithm based on this technique was developed to construct a Slim-tree. This is the first bulk-load algorithm based on sampling that always produces a valid Slim-tree, therefore is the first one described in literature that can be enclosed in a Database Management System. The experiments show that this algorithm keeps good clustering of data and in such a way that it surpasses the performance of sequential insertion, taking into account the construction performance and the efficiency to perform queries

O grau de similaridade entre elementos de dados é o fator primordial para a recuperação de informações em Sistemas Gerenciadores de Bases de Dados que manipulam dados complexos, como seqüências genéticas, séries temporais e dados multimídia (imagens, áudios, vídeos, textos longos). Para responder a essas consultas em um tempo reduzido, faz-se necessário utilizar métodos que usam métricas para avaliar a similaridade entre os elementos. Esses métodos são conhecidos como Métodos de Acesso Métricos. Dentre os mais conhecidos na literatura estão a M-tree e a Slim-tree. Existem duas maneiras de executar as operações de construção de índices em qualquer método de acesso: inserindo elemento a elemento ou usando a operação de carga-rápida (bulk-loading). O primeiro tipo de construção é comum e necessário para todo tipo de método de indexação dinâmico. Já as operações de carga-rápida são utilizadas para conjuntos de dados maiores, como por exemplo, na recuperação de backups em bases de dados ou na criação posterior de índices. Nessas situações, a inserção individual tende a ser mais demorada. Realizar uma carga-rápida possibilita a construção de índices com melhor eficiência e em menor tempo, pois há a disponibilidade de todos os dados no instante da criação da estrutura de índices, possibilitando explorar as propriedades do conjunto como um todo. Os Sistemas Gerenciadores de Base de Dados oferecem operações de carga-rápida dos dados nos métodos tradicionais, as quais devem ser supridas também nos Métodos de Acesso Métricos. Neste trabalho, são apresentadas três abordagens, uma técnica para carga-rápida dos dados em Métodos de Acesso Métricos e foi desenvolvido um algoritmo baseado nessa técnica para construir uma Slim-tree. Este é o primeiro algoritmo de carga-rápida baseada em amostragem que sempre produz uma Slim-tree válida, portanto é o primeiro descrito na literatura que pode ser incluído em um Sistema Gerenciador de Base de Dados. Os experimentos descritos neste trabalho mostram que o algoritmo proposto mantém bom agrupamento dos dados e supera o desempenho dos métodos de inserção seqüencial levando em conta tanto o desempenho de construção quanto à eficiência para realizar consultas / The similarity degree between data elements is the primordial factor for information retrieval in databases that handle complex data, such as genetic sequences, time series and multimedia objects (long images, audio, videos, texts). To answer these queries in a reduced time, it is necessary methods that use metrics to evaluate the similarity between elements. These methods are known as Metric Access Methods. The most known Metric Access Methods in the literature are the M-tree and the Slim-tree. There are two ways to build index in any access method: inserting element one by one or using the bulk-load operation. The first build type is very common and required for all kinds of dynamic access methods. The bulk-load operations are used for bigger datasets, as for example, in the recovery of backups and re-creation of database indexes. In these situations, the individual insertion takes much time. The bulk-load operation makes it possible to construct indexes more efficiently and faster, because it has the availability of the whole data when the index structure are created, and thus, it is possible to explore the properties of the whole set. Database Management Systems offer bulk-load operations for the traditional methods, so it is important that they can be also supplied for Metric Access Methods. This work presents three bulk-loading approaches and it proposes a technique to bulk-load data into Metric Access Methods. An algorithm based on this technique was developed to construct a Slim-tree. This is the first bulk-load algorithm based on sampling that always produces a valid Slim-tree, therefore is the first one described in literature that can be enclosed in a Database Management System. The experiments show that this algorithm keeps good clustering of data and in such a way that it surpasses the performance of sequential insertion, taking into account the construction performance and the efficiency to perform queries

Made available in DSpace on 2014-06-12T15:53:26Z (GMT). No. of bitstreams: 2 arquivo5133_1.pdf: 5742440 bytes, checksum: b8acaf8765518dc4580f06ca970cc072 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2002 / Um método de acesso multidimensional (MAM) é uma estrutura de indexação voltada ao suporte de objetos espaciais, especialmente de retângulos. O principal objetivo de um MAM é propiciar uma rápida obtenção dos objetos espaciais que satisfazem um certo relacionamento topológico, métrico ou direcional. Neste sentido, o espaço indexado é organizado de tal forma que, por exemplo, a recuperação dos retângulos de dados contidos em uma área particular requeira apenas o acesso aos retângulos próximos a esta área, em oposição à análise do conjunto completo de retângulos armazenados em memória secundária. Um MAM, portanto, é projetado como um caminho otimizado aos dados espaciais e o seu uso melhora significativamente o desempenho de sistemas gerenciadores de banco de dados espaciais no processamento de consultas. Nesta tese, nós investigamos o desempenho de um conjunto de MAM, a maioria dos quais tem sido identificado na literatura como um MAM muito eficiente no suporte a consultas espaciais de seleção. Este grupo consiste dos seguintes métodos de acesso: R-tree, R-tree Greene, R+-tree, Hilbert R-tree, SR-tree e três variantes da R* -tree chamadas de R* -tree CR (i.e., close reinsert), de R* -tree FR (isto é, far reinsert) e de R* -tree WR (isto é, without reinsertion). A comparação do desempenho destes MAM foi realizada visando-se analisar prioritariamente a influência do fator distribuição espacial dos dados. Neste sentido, nós propusemos uma metodologia de avaliação de desempenho que permite a geração de um conjunto de tipos de distribuição espacial com diferentes características, as quais tornam possível que a influência do fator distribuição espacial dos dados seja analisada sob diferentes perspectivas, desde uma fraca até uma forte influência. Por meio de diversos testes de desempenho, nós observamos de que forma a distribuição espacial dos dados afetou os custos de inserção e de armazenamento de novas entradas no índice espacial, além do custo de point queries, intersection range queries, enclosure range queries e containment range queries. Com relação a estas consultas espaciais de seleção, os resultados de desempenho mostraram que a R+-tree foi a melhor estrutura de indexação espacial para poin queries e enclosure range queries, ao passo que as variantes da R* -tree produziram os melhores resultados de desempenho para intersection e containment range queries. Por outro lado, os métodos Hilbert R-tree e SR-tree geraram um baixo desempenho para as quatro consultas espaciais investigadas. No entanto, em testes de desempenho adicionais, os quais modificaram tanto o tamanho quanto o formato dos retângulos de dados, os métodos de acesso Hilbert R-tree e SR-tree geraram resultados competitivos, particularmente para intersection e containment range queries

Os sistemas Gerenciadores de Bases de Dados (SGBDs) foram desenvolvidos para manipular domínios de dados numéricos e/ou pequenas seqüencias de caracteres (palavras) e não foram projetados prevendo a manipulação de dados complexos, como por exemplo dados multimídia. Os operadores em domínios de dados que requisitam a relação de ordem têm pouca utilidade para manipular operações que envolvem dados complexos. Uma classe de operadores que se adequa melhor para manipular esses dados são os operadores por similaridade: consulta por abrangência (``range queries') e consulta de vizinhos mais próximos (``k-nearest neighbor queries'). Embora muitos resultados já tenham sido obtidos na elaboração de algoritmos de busca por similaridade, todos eles consideram uma única função para a medida de similaridade, que deve ser universalmente aplicável a todos os pares de elementos do conjunto de dados. Este projeto propõe explorar a possibilidade de trabalhar com estruturas de dados concebidas dentro dos conceitos de dados em domínios métricos, mas que admitam o uso de uma função de distância adaptável, ou seja, que mude para determinados grupos de objetos, dependendo de algumas características universais, e assim permitindo acomodar características que sejam particulares a algumas classes de imagens e não de todo o conjunto delas, classificando as imagens em uma hierarquia de tipos, onde cada tipo está associado a uma função de distância diferente e vetores de características diferentes, todos indexados numa mesma árvore. / The DBMS were developed to manipulate data in numeric domains and short strings, not considering the manipulation of complex data, like multimidia data. The operators em data domain which requests for the total order property have no use to handle complex data. An operator class that fit well to handle this type of data are the similarity operators: range query and nearest neighbor query. Although many results have been shown in research to answer similarity queries, all use only one distance function to measure the similarity, which must be applicable to all pairs of elements of the set. The goal of this work is to explore the possibility of deal with complex data in metric domains, that uses a suitable distance function, that changes its behavior for certain groups of data, depending of some universal features, allowing them to use specific features of some classes of data, not shared for the entire set. This flexibility will allow to reduce the set of useful features of each element in the set individually, relying in the values obtainded for one or few features extracted in first place. This values will guide the others important features to extract from data.

Os sistemas Gerenciadores de Bases de Dados (SGBDs) foram desenvolvidos para manipular domínios de dados numéricos e/ou pequenas seqüencias de caracteres (palavras) e não foram projetados prevendo a manipulação de dados complexos, como por exemplo dados multimídia. Os operadores em domínios de dados que requisitam a relação de ordem têm pouca utilidade para manipular operações que envolvem dados complexos. Uma classe de operadores que se adequa melhor para manipular esses dados são os operadores por similaridade: consulta por abrangência (``range queries') e consulta de vizinhos mais próximos (``k-nearest neighbor queries'). Embora muitos resultados já tenham sido obtidos na elaboração de algoritmos de busca por similaridade, todos eles consideram uma única função para a medida de similaridade, que deve ser universalmente aplicável a todos os pares de elementos do conjunto de dados. Este projeto propõe explorar a possibilidade de trabalhar com estruturas de dados concebidas dentro dos conceitos de dados em domínios métricos, mas que admitam o uso de uma função de distância adaptável, ou seja, que mude para determinados grupos de objetos, dependendo de algumas características universais, e assim permitindo acomodar características que sejam particulares a algumas classes de imagens e não de todo o conjunto delas, classificando as imagens em uma hierarquia de tipos, onde cada tipo está associado a uma função de distância diferente e vetores de características diferentes, todos indexados numa mesma árvore. / The DBMS were developed to manipulate data in numeric domains and short strings, not considering the manipulation of complex data, like multimidia data. The operators em data domain which requests for the total order property have no use to handle complex data. An operator class that fit well to handle this type of data are the similarity operators: range query and nearest neighbor query. Although many results have been shown in research to answer similarity queries, all use only one distance function to measure the similarity, which must be applicable to all pairs of elements of the set. The goal of this work is to explore the possibility of deal with complex data in metric domains, that uses a suitable distance function, that changes its behavior for certain groups of data, depending of some universal features, allowing them to use specific features of some classes of data, not shared for the entire set. This flexibility will allow to reduce the set of useful features of each element in the set individually, relying in the values obtainded for one or few features extracted in first place. This values will guide the others important features to extract from data.