Made available in DSpace on 2014-06-12T15:59:03Z (GMT). No. of bitstreams: 2 arquivo4823_1.pdf: 1258995 bytes, checksum: c83e73b81e30c352afae5e1805a2c9c2 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Uma das maneiras mais eficientes (notadamente do ponto de vista computacional) empregada pela humanidade para a representação da informação tem sido através da forma de texto, ou seja, através de cadeias unidimensionais de símbolos (ou caracteres) tomados sobre conjuntos discretos finitos (ou alfabetos). As fecundas teorias, técnicas e algoritmos destinados ao processamento de texto têm ocupado um papel central em diversos âmbitos da Ciência da Computação, constituindo-se, sobretudo ao longo das últimas três décadas, em um campo de particular interesse no seio da grande área de Algoritmos e Estruturas de Dados. Grande parte do recente interesse com respeito ao processamento de texto deve-se ao emergente ramo da ciência denominado Biologia Molecular Computacional, que, a grosso modo, comporta o estudo, através de técnicas matemáticas e computacionais, da estrutura e da função dos artefatos bio-moleculares respons´aveis pela conformação e pelas atividades fisiológicas dos organismos vivos. A confluência dos problemas de Biologia Molecular e de processamento de textos dá-se na medida em que as estruturas macromoleculares fundamentais (DNA, RNA e proteínas) podem ser representadas através de cadeias (muito longas) de caracteres tomados sobre alfabetos (curtos) específicos. O problema fundamental relacionado ao processamento de cadeias corresponde à determinação das ocorrências, exatas ou aproximadas, de um determinado padrão em um dado texto problema do casamento de padrões problema esse que admite inúmeras variações. Os problemas de casamento de padrões podem ser particionados em duas grandes categorias com respeito ao conhecimento prévio ou não do texto a ser examinado. Os algoritmos clássicos destinados à resolução do problema do casamento de padrões dizem respeito ao caso no qual o texto não é conhecido previamente. Nesse caso, cada um dos seus caracteres deve ser examinado pelo menos uma vez, o que resulta em soluções de custo, no mínimo, linearmente proporcional ao tamanho do texto. Se, todavia, o texto a ser examinado é conhecido a priori, então ele pode ser pré-processado (tipicamente em tempo linear), dando origem a uma estrutura auxiliar (tipicamente de tamanho linear) denominada índice, contra a qual os padrões podem então ser confrontados para que as suas ocorrências sejam determinadas. Nesse caso, o custo da solução ótima do problema é linearmente proporcional ao comprimento do padrão (em geral, muito menor do que o texto). Em Biologia Molecular Computacional, frequentemente estamos interessados em localizar as ocorrências de uma determinada subsequência molecular (ou motif ) dentro de estruturas maiores. Esses motifs representam, em geral, regiões altamente conservadas, i.e., pouco afetadas por mutações, que desempenham funções biológicas específicas. Esse problema de localização de motifs limita-se com o problema do casamento de padrões e pode ser abordado através das mesmas técnicas. Em outras situações, todavia, estamos interessados não em localizar motifs mas sim em inferi-los. Isto é, dado um conjunto de sequências moleculares, queremos descobrir que subsequências aparecem repetidas emuma quantidade significativa dessas sequências de maneira suficientemente conservada e que, portanto, possuem uma boa probabilidade de representar um objeto biológico de particular interesse. Neste trabalho, nos propomos a reunir em uma obra única, boa parte da informação fundamental dispersa na literatura acerca dos principais índices completos conhecidos, com ênfase nas suas propriedades estruturais. Nossa apresentação não intenciona ser estritamente panorâmica e, portanto, algum sacrif´ıcio da fluência deve ser depositado no altar do rigor matemático. Além disso, apresentamos uma análise crítica da adequa ção e desempenho das estruturas de índice estudadas para a resolução do problema da inferência de motifs através de algoritmos exatos e combinatórios

Submitted by Kamila Costa (kamilavasconceloscosta@gmail.com) on 2015-06-15T22:12:07Z No. of bitstreams: 1 Dissertacao-Wheidima C de Melo.pdf: 2703087 bytes, checksum: e6e1c33a03cbfdb7ab483f0f6f9e6dc7 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-16T15:15:11Z (GMT) No. of bitstreams: 1 Dissertacao-Wheidima C de Melo.pdf: 2703087 bytes, checksum: e6e1c33a03cbfdb7ab483f0f6f9e6dc7 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-16T15:16:09Z (GMT) No. of bitstreams: 1 Dissertacao-Wheidima C de Melo.pdf: 2703087 bytes, checksum: e6e1c33a03cbfdb7ab483f0f6f9e6dc7 (MD5) / Made available in DSpace on 2015-06-16T15:16:09Z (GMT). No. of bitstreams: 1 Dissertacao-Wheidima C de Melo.pdf: 2703087 bytes, checksum: e6e1c33a03cbfdb7ab483f0f6f9e6dc7 (MD5) Previous issue date: 2014-06-27 / Não Informada / Traditionally, electromyographic signals are compressed to one-dimensional techniques, which are specifically developed for this purpose. However, some studies have shown that the compression of biological signals such as images, via its pre-processing and rearrangement on a two-dimensional array, can lead to good results. The present work an investigation of the compression electromyographic signals like images, three main contributions: the use of new encoders, the development of new pre-processing techniques and modification of the coding core of a specific compressor, so that existing redundancies are better exploited. With respect to the pre-processing of the signal, two new techniques are introduced: ordering a percentage difference and targeting similarity which have the potential to increase the performance of encoded pictures. Optionally for compression of electromyographic signals, propose to the high efficiency video coding encoder, which features state of the art in video compression. Furthermore, an investigation of the paradigm that uses recurrence multiscale standards, known as multidimensional multiscale parser, is also presented. In summary, the encoder adapts to working with the biological signal by replacing its prediction techniques to improve the exploitation of redundancy, the result of which is termed Bio-MMP. The experiments performed with real electromyographic signals show that the proposed techniques are effective, providing better results than the state of the art in the literature. / Tradicionalmente, sinais eletromiográficos são comprimidos com técnicas unidimensionais, que são desenvolvidas especificamente para esse fim. No entanto, alguns trabalhos têm demonstrado que a compressão de sinais biológicos como imagens, através do seu pré-processamento e rearranjo em uma matriz bidimensional, pode levar a bons resultados. O presente trabalho apresenta uma investigação sobre a compressão de sinais eletromiográficos como imagens, com três principais contribuições: a utilização de novos codificadores, o desenvolvimento de novas técnicas de pré-processamento e a modificação do núcleo de codificação de um compressor específico, de modo que as redundâncias existentes sejam melhor exploradas. No que diz respeito ao pré-processamento do sinal, duas novas técnicas são introduzidas: a ordenação por diferença percentual e a segmentação por similaridade, que apresentam o potencial de aumentar o desempenho do codificados de imagens. Como opção para compressão de sinais eletromiográficos, propõem-se o codificador high efficiency video coding, que apresenta o estado da arte em compressão de vídeo. Além disso, uma investigação do paradigma que utiliza recorrência de padrões multiescalas, conhecido como multidimensional multiscale parser, também é apresentada. Em resumo, adapta-se o codificador para trabalhar com o sinal biológico, através da substituição das suas técnicas de predição, de modo a melhorar a exploração de redundâncias, cujo resultado é denominado de MMP-Bio. Os experimentos realizado com sinais eletromiográficos reais mostram que as técnicas propostas são eficazes, proporcionando resultados superiores ao estado da arte presente na literatura.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-05-08T12:54:39Z No. of bitstreams: 1 DissDRGP.pdf: 2915023 bytes, checksum: 6dc48dd58772bd3d2917206ca9a92646 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-10T14:04:50Z (GMT) No. of bitstreams: 1 DissDRGP.pdf: 2915023 bytes, checksum: 6dc48dd58772bd3d2917206ca9a92646 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-10T14:04:57Z (GMT) No. of bitstreams: 1 DissDRGP.pdf: 2915023 bytes, checksum: 6dc48dd58772bd3d2917206ca9a92646 (MD5) / Made available in DSpace on 2017-05-10T14:09:36Z (GMT). No. of bitstreams: 1 DissDRGP.pdf: 2915023 bytes, checksum: 6dc48dd58772bd3d2917206ca9a92646 (MD5) Previous issue date: 2016-07-13 / Não recebi financiamento / Users do not usually read privacy policies from online services. Among the main reasons for that is the fact that such policies are long and commonly hard to understand, which makes the user lose interest in reading them carefully. In this scenario, users are prone to agree to the policies terms without knowing what kind of data is being collected and why. This dissertation discusses how the policies' content may be presented in a more friendly way, showing information about data collection and usage in a table herein called Privacy Label. The Privacy Label is a table with lines named according to data collection terms and columns named according to expressions that reveal how the data is used by the service. The table content shows if the policy collects a particular data to a particular usage. To generate the Privacy Label, a study was made in a set of privacy policies to identify which terms repeat more often along the texts. To do so, we used techniques to find keywords, and from these keywords we were able to create privacy categories. The categories define which kind of data is being collected and why, which are represented by cells in the Privacy Label. Using word comparison techniques, a privacy policy can be analyzed and important information can be extracted by comparing its terms with the terms from the privacy categories. For each category we find, we show it in the Privacy Label. To assess the proposed approach we developed an application prototype, herein called PPMark, that analyzes a particular privacy policy, extract its keywords and generates the Privacy Label automatically. The information extracted was analyzed regarding its quality using three metrics: precision, recall and f-measure. The results show that the approach is a viable functional alternative to generate the Privacy Label and present privacy policies in a friendly manner. There are evidences of time saving by using our approach, which facilitates the process of decision making. / Comumente, os usuários não leem as políticas de privacidade dos serviços online que utilizam. Entre as principais causas estão os textos longos, muitas vezes de difícil compreensão, desestimulando o interesse pela leitura atenciosa e integral. Neste cenário, os usuários, muitas vezes, concordam com os termos sem saber os tipos de dados que estão sendo coletados e o porquê. Esta dissertação discute como o conteúdo das políticas de privacidade pode ser apresentado de forma mais sintética para o usuário, com as informações sobre a coleta e a utilização dos dados sendo exibidas em uma tabela, denominada Rótulo de Privacidade. O Rótulo de Privacidade é uma tabela com linhas nomeadas por termos de coleta de dados e colunas nomeadas por expressões que denotam finalidade das coletas. O conteúdo da tabela informa se a política contempla a coleta de dados para a finalidade especificada. Para ser possível a geração do Rótulo de Privacidade, foi feito um estudo em um conjunto de políticas de privacidade para verificar quais termos mais se repetem nos textos. Para isto foram utilizadas técnicas para encontrar palavras-chave e com estas foram criadas categorias de privacidade. As categorias definem tipos de dados coletados e propósitos da coleta, que no Rótulo de Privacidade são representados pelas células da tabela. Utilizando técnicas de comparação de palavras, uma política de privacidade a ser lida pelo usuário pode ser analisada pela abordagem, extraindo informações importantes por meio das comparações de seus termos com os termos das categorias de privacidade elaboradas. Para cada categoria encontrada na política de privacidade, a informação é ilustrada no Rótulo de Privacidade. Para a avaliação da abordagem proposta, foi desenvolvido um protótipo de uma aplicação, denominada PPMark, que analisa uma particular política de privacidade, extrai as palavras-chave e gera o Rótulo de Privacidade de forma automatizada. As informações extraídas foram analisadas quanto à qualidade utilizandose três métricas que são empregadas para a avaliação de classificadores, sendo elas precisão, recall e f-measure. Os resultados mostraram que a abordagem proposta é uma alternativa funcional para o preenchimento do Rótulo de Privacidade e a apresentação das políticas de privacidade. Há evidências de economia de tempo com a leitura e entendimento das políticas, possibilitando suporte para a tomada de decisões.

Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-08-30T19:22:34Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Israel Batista Freitas da Silva.pdf: 1433243 bytes, checksum: 5b1ac5501cae385e4811343e1426e6c9 (MD5) / Made available in DSpace on 2017-08-30T19:22:34Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Israel Batista Freitas da Silva.pdf: 1433243 bytes, checksum: 5b1ac5501cae385e4811343e1426e6c9 (MD5) Previous issue date: 2016-12-12 / CNPQ, FACEPE. / Hoje em dia, há um exponencial crescimento do volume de informação no mundo. Esta explosão cria uma demanda por técnicas mais eficientes de indexação e consulta de dados, uma vez que, para serem úteis, eles precisarão ser manipuláveis. Casamento de padrões se refere à busca de um texto menor (padrão) em um texto muito maior (texto), reportando a quantidade de ocorrências e/ou as localizações das ocorrências. Para tal, pode-se construir uma estrutura chamada índice que pré-processará o texto e permitirá que consultas sejam feitas eficientemente. A eficiência prática de um índice, além da sua eficiência teórica, pode definir o quão utilizado ele será, e isto está diretamente ligado a como ele se comporta nas arquiteturas dos computadores atuais. O principal objetivo deste estudo é analisar o uso da estrutura Wavelet Tree como índice avaliando o impacto da reorganização interna dos seus dados quanto à localidade espacial e, assim propor formas de organização que reduzam efetivamente a quantidade de cache misses ocorridos na execução de operações neste índice. Através de análises empíricas com dados simulados e dados textuais obtidos de dois repositórios públicos, avaliou-se alguns aspectos de cinco tipos de organizações para os dados da estrutura com o objetivo de compará-las quanto ao tempo de execução e quantidade de cache misses ocorridos. Adicionalmente, uma análise teórica da complexidade da quantidade de cache misses ocorridos para operação de consulta de um padrão é descrita para uma das organizações propostas. Dois experimentos realizados sugerem comportamentos assintóticos para duas das organizações analisadas. Um terceiro experimento executado mostra que, para quatro das cinco organizações apresentadas, houve uma sistemática redução na quantidade de cache misses ocorridos para a cache de menor nível. Entretanto a redução de cache misses para cache de menor nível não se refletiu integralmente numa diferença no tempo de execução das operações, tendo sido esta menos significativa, nem na quantidade de cache misses ocorridos na cache de maior nível, onde houveram variações positivas e negativas.Os resultados obtidos permitem concluir que a escolha de uma representação adequada pode acarretar numa melhora significativa de utilização da cache. Diferentemente do modelo teórico, o custo de acesso à memória responde apenas por uma fração do tempo de computação das operações sobre as Wavelet Trees, pelo que a diminuição no número de cache misses não se traduziu integralmente no tempo de execução. No entanto, este fator pode ser crítico em situações mais extremas de utilização de memória. / Today, there is an exponential growth in the volume of information in the world. This increase creates the demand for more efficient indexing and querying techniques, since, to be useful, that data needs to be manageable. Pattern matching means searching for a string (pattern) in a much bigger string (text), reporting the number of occurrences and/or its locations. To do that, we need to build a data structure known as index. This structure will preprocess the text to allow for efficient queries. The adoption of an index depends heavily on its efficiency, and this is directly related to how well it performs on current machine architectures. The main objective of this work is to analyze the Wavelet Tree data structure as an index, assessing the impact of its internal organization with respect to spatial locality, and propose ways to organize its data as to reduce the amount of cache misses incurred by its operations. We performed an empirical analysis using both real and simulated textual data to compare the running time and cache behavior of Wavelet Trees using five different proposals of internal data layout. A theoretical analysis about the cache complexity of a query operation is also presented for the most efficient layout. Two experiments suggest good asymptotic behavior for two of the analyzed layouts. A third experiment shows that for four of the five layouts, there was a systematic reduction in the number of cache misses for the lowest level cache. Despite this, this reduction was not reflected in the runtime, neither in the performance for the highest level cache. The results obtained allow us to conclude that the choice of a suitable layout can lead to a significant improvement in cache usage. Unlike the theoretical model, however, the cost of memory access only accounts for a fraction of the operations’ computation time on the Wavelet Trees, so the decrease in the number of cache misses did not translate fully into gains in the execution time. However, this factor can still be critical in more extreme memory utilization situations.

Reconhecimento de objetos é uma aplicação básica da área de processamento de imagens e visão computacional. O procedimento comum do reconhecimento consiste em achar ocorrências de uma imagem modelo numa outra imagem a ser analisada. Consequentemente, se as imagens apresentarem mudanças no ponto de vista da câmera o algoritmo normalmente falha. A invariância a pontos de vista é uma qualidade que permite reconhecer um objeto, mesmo que este apresente distorções resultantes de uma transformação em perspectiva causada pela mudança do ponto de vista. Uma abordagem baseada na simulação de pontos de vista, chamada ASIFT, tem sido recentemente proposta no entorno desta problemática. O ASIFT é invariante a pontos de vista, no entanto falha na presença de padrões repetitivos e baixo contraste. O objetivo de nosso trabalho é utilizar uma variante da técnica de simulação de pontos de vista em combinação com a técnica de extração dos coeficientes de Fourier de projeções radiais e circulares (FORAPRO), para propor um algoritmo invariante a pontos de vista, e robusto a padrões repetitivos e baixo contraste. De maneira geral, a nossa proposta resume-se nas seguintes fases: (a) Distorcemos a imagem, variando os parâmetros de inclinação e rotação da câmera, para gerar alguns modelos e conseguir a invariância a deformações em perspectiva, (b) utilizamos cada como modelo a ser procurado na imagem, para escolher o que melhor case, (c) realizamos o casamento de padrões. As duas últimas fases do processo baseiam-se em características invariantes por rotação, escala, brilho e contraste extraídas pelos coeficientes de Fourier. Nossa proposta, que chamamos AFORAPRO, foi testada com 350 imagens que continham diversidade nos requerimentos, e demonstrou ser invariante a pontos de vista e ter ótimo desempenho na presença de padrões repetitivos e baixo contraste. / Object recognition is a basic application from the domain of image processing and computer vision. The common process recognition consists of finding occurrences of an image query in another image to be analyzed A. Consequently, if the images changes viewpoint in the camera it will normally result in the algorithm failure. The invariance viewpoints are qualities that permit recognition of an object, even if this present distortion resultant of a transformation of perspective is caused by the change in viewpoint. An approach based on viewpoint simulation, called ASIFT, has recently been proposed surrounding this issue. The ASIFT algorithm is invariant viewpoints; however there are flaws in the presence of repetitive patterns and low contrast. The objective of our work is to use a variant of this technique of viewpoint simulating, in combination with the technique of extraction of the Coefficients of Fourier Projections Radials and Circulars (FORAPRO), and to propose an algorithm of invariant viewpoints and robust repetitive patterns and low contrast. In general, our proposal summarizes the following stages: (a) We distort the image, varying the parameters of inclination and rotation of the camera, to produce some models and achieve perspective invariance deformation, (b) use as the model to be search in the image, to choose the that match best, (c) realize the template matching. The two last stages of process are based on invariant features by images rotation, scale, brightness and contrast extracted by Fourier coefficients. Our approach, that we call AFORAPRO, was tested with 350 images that contained diversity in applications, and demonstrated to have invariant viewpoints, and to have excellent performance in the presence of patterns repetitive and low contrast.

Reconhecimento de objetos é uma aplicação básica da área de processamento de imagens e visão computacional. O procedimento comum do reconhecimento consiste em achar ocorrências de uma imagem modelo numa outra imagem a ser analisada. Consequentemente, se as imagens apresentarem mudanças no ponto de vista da câmera o algoritmo normalmente falha. A invariância a pontos de vista é uma qualidade que permite reconhecer um objeto, mesmo que este apresente distorções resultantes de uma transformação em perspectiva causada pela mudança do ponto de vista. Uma abordagem baseada na simulação de pontos de vista, chamada ASIFT, tem sido recentemente proposta no entorno desta problemática. O ASIFT é invariante a pontos de vista, no entanto falha na presença de padrões repetitivos e baixo contraste. O objetivo de nosso trabalho é utilizar uma variante da técnica de simulação de pontos de vista em combinação com a técnica de extração dos coeficientes de Fourier de projeções radiais e circulares (FORAPRO), para propor um algoritmo invariante a pontos de vista, e robusto a padrões repetitivos e baixo contraste. De maneira geral, a nossa proposta resume-se nas seguintes fases: (a) Distorcemos a imagem, variando os parâmetros de inclinação e rotação da câmera, para gerar alguns modelos e conseguir a invariância a deformações em perspectiva, (b) utilizamos cada como modelo a ser procurado na imagem, para escolher o que melhor case, (c) realizamos o casamento de padrões. As duas últimas fases do processo baseiam-se em características invariantes por rotação, escala, brilho e contraste extraídas pelos coeficientes de Fourier. Nossa proposta, que chamamos AFORAPRO, foi testada com 350 imagens que continham diversidade nos requerimentos, e demonstrou ser invariante a pontos de vista e ter ótimo desempenho na presença de padrões repetitivos e baixo contraste. / Object recognition is a basic application from the domain of image processing and computer vision. The common process recognition consists of finding occurrences of an image query in another image to be analyzed A. Consequently, if the images changes viewpoint in the camera it will normally result in the algorithm failure. The invariance viewpoints are qualities that permit recognition of an object, even if this present distortion resultant of a transformation of perspective is caused by the change in viewpoint. An approach based on viewpoint simulation, called ASIFT, has recently been proposed surrounding this issue. The ASIFT algorithm is invariant viewpoints; however there are flaws in the presence of repetitive patterns and low contrast. The objective of our work is to use a variant of this technique of viewpoint simulating, in combination with the technique of extraction of the Coefficients of Fourier Projections Radials and Circulars (FORAPRO), and to propose an algorithm of invariant viewpoints and robust repetitive patterns and low contrast. In general, our proposal summarizes the following stages: (a) We distort the image, varying the parameters of inclination and rotation of the camera, to produce some models and achieve perspective invariance deformation, (b) use as the model to be search in the image, to choose the that match best, (c) realize the template matching. The two last stages of process are based on invariant features by images rotation, scale, brightness and contrast extracted by Fourier coefficients. Our approach, that we call AFORAPRO, was tested with 350 images that contained diversity in applications, and demonstrated to have invariant viewpoints, and to have excellent performance in the presence of patterns repetitive and low contrast.

Casamento de padrões de pontos é um problema fundamental em reconhecimento de padrões. O objetivo é encontrar uma correspondência entre dois conjuntos de pontos, associados a características relevantes de objetos ou entidades, mapeando os pontos de um conjunto no outro. Este problema está associado a muitas aplicações, como por exemplo, reconhecimento de objetos baseado em modelos, imagens estéreo, registro de imagens, biometria, entre outros. Para encontrar um mapeamento, os objetos são codificados por representações abstratas, codificando as características relevantes consideradas na comparação entre pares de objetos. Neste trabalho, objetos são representados por grafos, codificando tanto as características `locais\' quanto as relações espaciais entre estas características. A comparação entre objetos é guiada por uma formulação de atribuição quadrática, que é um problema NP-difícil. Para estimar uma solução, duas técnicas de casamento entre grafos são propostas: uma baseada em grafos auxiliares, chamados de grafos deformados; e outra baseada em representações `esparsas\', campos aleatórios de Markov e propagação de crenças. Devido as suas respectivas limitações, as abordagens são adequadas para situações específicas, conforme mostrado neste documento. Resultados envolvendo as duas abordagens são ilustrados em quatro importantes aplicações: casamento de imagens de gel eletroforese 2D, segmentação interativa de imagens naturais, casamento de formas, e colorização assistida por computador. / Point set matching is a fundamental problem in pattern recognition. The goal is to match two sets of points, associated to relevant features of objects or entities, by finding a mapping, or a correspondence, from one set to another set of points. This issue arises in many applications, e.g. model-based object recognition, stereo matching, image registration, biometrics, among others. In order to find a mapping, the objects can be encoded by abstract representations, carrying relevant features which are taken into account to compare pairs of objects. In this work, graphs are adopted to represent the objects, encoding their `local\' features and the spatial relations between these features. The comparison of two given objects is guided by a quadratic assignment formulation, which is NP-hard. In order to estimate the optimal solution, two approximations techniques, via graph matching, are proposed: one is based on auxiliary graphs, called deformed graphs; the other is based on `sparse\' representations, Markov random fields and belief propagation. Due to their respective limitations, each approach is more suitable to each specific situation, as shown in this document. The quality of the two approaches is illustrated on four important applications: 2D electrophoresis gel matching, interactive natural image segmentation, shape matching, and computer-assisted colorization.

Casamento de padrões de pontos é um problema fundamental em reconhecimento de padrões. O objetivo é encontrar uma correspondência entre dois conjuntos de pontos, associados a características relevantes de objetos ou entidades, mapeando os pontos de um conjunto no outro. Este problema está associado a muitas aplicações, como por exemplo, reconhecimento de objetos baseado em modelos, imagens estéreo, registro de imagens, biometria, entre outros. Para encontrar um mapeamento, os objetos são codificados por representações abstratas, codificando as características relevantes consideradas na comparação entre pares de objetos. Neste trabalho, objetos são representados por grafos, codificando tanto as características `locais\' quanto as relações espaciais entre estas características. A comparação entre objetos é guiada por uma formulação de atribuição quadrática, que é um problema NP-difícil. Para estimar uma solução, duas técnicas de casamento entre grafos são propostas: uma baseada em grafos auxiliares, chamados de grafos deformados; e outra baseada em representações `esparsas\', campos aleatórios de Markov e propagação de crenças. Devido as suas respectivas limitações, as abordagens são adequadas para situações específicas, conforme mostrado neste documento. Resultados envolvendo as duas abordagens são ilustrados em quatro importantes aplicações: casamento de imagens de gel eletroforese 2D, segmentação interativa de imagens naturais, casamento de formas, e colorização assistida por computador. / Point set matching is a fundamental problem in pattern recognition. The goal is to match two sets of points, associated to relevant features of objects or entities, by finding a mapping, or a correspondence, from one set to another set of points. This issue arises in many applications, e.g. model-based object recognition, stereo matching, image registration, biometrics, among others. In order to find a mapping, the objects can be encoded by abstract representations, carrying relevant features which are taken into account to compare pairs of objects. In this work, graphs are adopted to represent the objects, encoding their `local\' features and the spatial relations between these features. The comparison of two given objects is guided by a quadratic assignment formulation, which is NP-hard. In order to estimate the optimal solution, two approximations techniques, via graph matching, are proposed: one is based on auxiliary graphs, called deformed graphs; the other is based on `sparse\' representations, Markov random fields and belief propagation. Due to their respective limitations, each approach is more suitable to each specific situation, as shown in this document. The quality of the two approaches is illustrated on four important applications: 2D electrophoresis gel matching, interactive natural image segmentation, shape matching, and computer-assisted colorization.