A segmentação é um passo importante em praticamente todas as tarefas que envolvem processamento de imagens digitais. Devido à variedade de imagens e diferentes necessidades da segmentação, a automação da segmentação não é uma tarefa trivial. Em muitas situações, abordagens interativas, nas quais o usuário pode intervir para guiar o processo de segmentação, são bastante úteis. Abordagens baseadas na transformação watershed mostram-se adequadas para a segmentação interativa de imagens: o watershed a partir de marcadores possibilita que o usuário marque as regiões de interesse na imagem; o watershed hierárquico gera uma hierarquia de partições da imagem sendo analisada, hierarquia na qual o usuário pode navegar facilmente e selecionar uma particular partição (segmentação). Em um trabalho prévio, propomos um método que integra as duas abordagens de forma que o usuário possa combinar os pontos fortes dessas duas formas de interação intercaladamente. Apesar da versatilidade obtida ao se integrar as duas abordagens, as hierarquias construídas dificilmente contêm partições interessantes e o esforço de interação necessário para se obter um resultado desejado pode ser muito elevado. Nesta tese propomos um método, baseado em aprendizagem computacional, que utiliza imagens previamente segmentadas para tentar adaptar uma dada hierarquia de forma que esta contenha partições mais próximas de uma partição de interesse. Na formulação de aprendizagem computacional, diferentes características da imagem são associadas a possíveis contornos de regiões, e esses são classificados como contornos que devem ou não estar presentes na partição final por uma máquina de suporte vetorial previamente treinada. A hierarquia dada é adaptada de forma a conter uma partição que seja consistente com a classificação obtida. Essa abordagem é particularmente interessante em cenários nos quais lotes de imagens similares ou sequências de imagens, como frames em sequências de vídeo ou cortes produzidas por exames de diagnóstico por imagem, precisam ser segmentadas. Nesses casos, é esperado que, a cada nova imagem a ser segmentada, o esforço de interação necessário para se obter a segmentação desejada seja reduzido em relação ao esforço que seria necessário com o uso da hierarquia original. Para não dependermos de experimentos com usuários na avaliação da redução no esforço de interação, propomos e utilizamos um modelo de interação que simula usuários humanos no contexto de segmentação hierárquica. Simulações deste modelo foram comparadas com sequências de interação observadas em experimentos com usuários humanos. Experimentos com diferentes lotes e sequências de imagens mostram que o método é capaz de reduzir o esforço de interação. / Segmentation is an important step in nearly all tasks involving digital image processing. Due to the variety of images and segmentation needs, automation of segmentation is not a trivial task. In many situations, interactive approaches in which the user can intervene to guide the segmentation process, are quite useful. Watershed transformation based approaches are suitable for interactive image segmentation: the watershed from markers allows the user to mark the regions of interest in the image; the hierarchical watershed generates a hierarchy of partitions of the image being analyzed, hierarchy in which the user can easily navigate and select a particular partition (segmentation). In a previous work, we have proposed a method that integrates the two approaches so that the user can combine the strong points of these two forms of interaction interchangeably. Despite the versatility obtained by integrating the two approaches, the built hierarchies hardly contain interesting partitions and the interaction effort needed to obtain a desired outcome can be very high. In this thesis we propose a method, based on machine learning, that uses images previously segmented to try to adapt a given hierarchy so that it contains partitions closer to the partition of interest. In the machine learning formulation, different image features are associated to the possible region contours, and these are classified as ones that must or must not be present in the final partition by a previously trained support vector machine. The given hierarchy is adapted to contain a partition that is consistent with the obtained classification. This approach is particularly interesting in scenarios where batches of similar images or sequences of images, such as frames in video sequences or cuts produced by imaging diagnosis procedures, need to be segmented. In such cases, it is expected that for each new image to be segmented, the interaction effort required to achieve the desired segmentation is reduced relative to the effort that would be required when using the original hierarchy. In order to do not depend on experiments with users in assessing the reduction in interaction effort, we propose and use an interaction model that simulates human users in the context of hierarchical segmentation. Simulations of this model were compared with interaction sequences observed in experiments with humans users. Experiments with different bacthes and image sequences show that the method is able to reduce the interaction effort.

A segmentação é um passo importante em praticamente todas as tarefas que envolvem processamento de imagens digitais. Devido à variedade de imagens e diferentes necessidades da segmentação, a automação da segmentação não é uma tarefa trivial. Em muitas situações, abordagens interativas, nas quais o usuário pode intervir para guiar o processo de segmentação, são bastante úteis. Abordagens baseadas na transformação watershed mostram-se adequadas para a segmentação interativa de imagens: o watershed a partir de marcadores possibilita que o usuário marque as regiões de interesse na imagem; o watershed hierárquico gera uma hierarquia de partições da imagem sendo analisada, hierarquia na qual o usuário pode navegar facilmente e selecionar uma particular partição (segmentação). Em um trabalho prévio, propomos um método que integra as duas abordagens de forma que o usuário possa combinar os pontos fortes dessas duas formas de interação intercaladamente. Apesar da versatilidade obtida ao se integrar as duas abordagens, as hierarquias construídas dificilmente contêm partições interessantes e o esforço de interação necessário para se obter um resultado desejado pode ser muito elevado. Nesta tese propomos um método, baseado em aprendizagem computacional, que utiliza imagens previamente segmentadas para tentar adaptar uma dada hierarquia de forma que esta contenha partições mais próximas de uma partição de interesse. Na formulação de aprendizagem computacional, diferentes características da imagem são associadas a possíveis contornos de regiões, e esses são classificados como contornos que devem ou não estar presentes na partição final por uma máquina de suporte vetorial previamente treinada. A hierarquia dada é adaptada de forma a conter uma partição que seja consistente com a classificação obtida. Essa abordagem é particularmente interessante em cenários nos quais lotes de imagens similares ou sequências de imagens, como frames em sequências de vídeo ou cortes produzidas por exames de diagnóstico por imagem, precisam ser segmentadas. Nesses casos, é esperado que, a cada nova imagem a ser segmentada, o esforço de interação necessário para se obter a segmentação desejada seja reduzido em relação ao esforço que seria necessário com o uso da hierarquia original. Para não dependermos de experimentos com usuários na avaliação da redução no esforço de interação, propomos e utilizamos um modelo de interação que simula usuários humanos no contexto de segmentação hierárquica. Simulações deste modelo foram comparadas com sequências de interação observadas em experimentos com usuários humanos. Experimentos com diferentes lotes e sequências de imagens mostram que o método é capaz de reduzir o esforço de interação. / Segmentation is an important step in nearly all tasks involving digital image processing. Due to the variety of images and segmentation needs, automation of segmentation is not a trivial task. In many situations, interactive approaches in which the user can intervene to guide the segmentation process, are quite useful. Watershed transformation based approaches are suitable for interactive image segmentation: the watershed from markers allows the user to mark the regions of interest in the image; the hierarchical watershed generates a hierarchy of partitions of the image being analyzed, hierarchy in which the user can easily navigate and select a particular partition (segmentation). In a previous work, we have proposed a method that integrates the two approaches so that the user can combine the strong points of these two forms of interaction interchangeably. Despite the versatility obtained by integrating the two approaches, the built hierarchies hardly contain interesting partitions and the interaction effort needed to obtain a desired outcome can be very high. In this thesis we propose a method, based on machine learning, that uses images previously segmented to try to adapt a given hierarchy so that it contains partitions closer to the partition of interest. In the machine learning formulation, different image features are associated to the possible region contours, and these are classified as ones that must or must not be present in the final partition by a previously trained support vector machine. The given hierarchy is adapted to contain a partition that is consistent with the obtained classification. This approach is particularly interesting in scenarios where batches of similar images or sequences of images, such as frames in video sequences or cuts produced by imaging diagnosis procedures, need to be segmented. In such cases, it is expected that for each new image to be segmented, the interaction effort required to achieve the desired segmentation is reduced relative to the effort that would be required when using the original hierarchy. In order to do not depend on experiments with users in assessing the reduction in interaction effort, we propose and use an interaction model that simulates human users in the context of hierarchical segmentation. Simulations of this model were compared with interaction sequences observed in experiments with humans users. Experiments with different bacthes and image sequences show that the method is able to reduce the interaction effort.

Image segmentation is an essential tool to enhance the ability of computer systems to efficiently perform elementary cognitive tasks such as detection, recognition and tracking. In this thesis we concentrate on the investigation of two fundamental topics in the context of image segmentation: spectral clustering and seeded image segmentation. We introduce two new algorithms for those topics that, in summary, rely on Laplacian-based operators, spectral graph theory, and minimization of energy functionals. The effectiveness of both segmentation algorithms is verified by visually evaluating the resulting partitions against state-of-the-art methods as well as through a variety of quantitative measures typically employed as benchmark by the image segmentation community. Our spectral-based segmentation algorithm combines image decomposition, similarity metrics, and spectral graph theory into a concise and powerful framework. An image decomposition is performed to split the input image into texture and cartoon components. Then, an affinity graph is generated and weights are assigned to the edges of the graph according to a gradient-based inner-product function. From the eigenstructure of the affinity graph, the image is partitioned through the spectral cut of the underlying graph. Moreover, the image partitioning can be improved by changing the graph weights by sketching interactively. Visual and numerical evaluation were conducted against representative spectral-based segmentation techniques using boundary and partition quality measures in the well-known BSDS dataset. Unlike most existing seed-based methods that rely on complex mathematical formulations that typically do not guarantee unique solution for the segmentation problem while still being prone to be trapped in local minima, our segmentation approach is mathematically simple to formulate, easy-to-implement, and it guarantees to produce a unique solution. Moreover, the formulation holds an anisotropic behavior, that is, pixels sharing similar attributes are preserved closer to each other while big discontinuities are naturally imposed on the boundary between image regions, thus ensuring better fitting on object boundaries. We show that the proposed approach significantly outperforms competing techniques both quantitatively as well as qualitatively, using the classical GrabCut dataset from Microsoft as a benchmark. While most of this research concentrates on the particular problem of segmenting an image, we also develop two new techniques to address the problem of image inpainting and photo colorization. Both methods couple the developed segmentation tools with other computer vision approaches in order to operate properly. / Segmentar uma image é visto nos dias de hoje como uma prerrogativa para melhorar a capacidade de sistemas de computador para realizar tarefas complexas de natureza cognitiva tais como detecção de objetos, reconhecimento de padrões e monitoramento de alvos. Esta pesquisa de doutorado visa estudar dois temas de fundamental importância no contexto de segmentação de imagens: clusterização espectral e segmentação interativa de imagens. Foram propostos dois novos algoritmos de segmentação dentro das linhas supracitadas, os quais se baseiam em operadores do Laplaciano, teoria espectral de grafos e na minimização de funcionais de energia. A eficácia de ambos os algoritmos pode ser constatada através de avaliações visuais das segmentações originadas, como também através de medidas quantitativas computadas com base nos resultados obtidos por técnicas do estado-da-arte em segmentação de imagens. Nosso primeiro algoritmo de segmentação, o qual ´e baseado na teoria espectral de grafos, combina técnicas de decomposição de imagens e medidas de similaridade em grafos em uma única e robusta ferramenta computacional. Primeiramente, um método de decomposição de imagens é aplicado para dividir a imagem alvo em duas componentes: textura e cartoon. Em seguida, um grafo de afinidade é gerado e pesos são atribuídos às suas arestas de acordo com uma função escalar proveniente de um operador de produto interno. Com base no grafo de afinidade, a imagem é então subdividida por meio do processo de corte espectral. Além disso, o resultado da segmentação pode ser refinado de forma interativa, mudando-se, desta forma, os pesos do grafo base. Experimentos visuais e numéricos foram conduzidos tomando-se por base métodos representativos do estado-da-arte e a clássica base de dados BSDS a fim de averiguar a eficiência da metodologia proposta. Ao contrário de grande parte dos métodos existentes de segmentação interativa, os quais são modelados por formulações matemáticas complexas que normalmente não garantem solução única para o problema de segmentação, nossa segunda metodologia aqui proposta é matematicamente simples de ser interpretada, fácil de implementar e ainda garante unicidade de solução. Além disso, o método proposto possui um comportamento anisotrópico, ou seja, pixels semelhantes são preservados mais próximos uns dos outros enquanto descontinuidades bruscas são impostas entre regiões da imagem onde as bordas são mais salientes. Como no caso anterior, foram realizadas diversas avaliações qualitativas e quantitativas envolvendo nossa técnica e métodos do estado-da-arte, tomando-se como referência a base de dados GrabCut da Microsoft. Enquanto a maior parte desta pesquisa de doutorado concentra-se no problema específico de segmentar imagens, como conteúdo complementar de pesquisa foram propostas duas novas técnicas para tratar o problema de retoque digital e colorização de imagens.

Image segmentation is an essential tool to enhance the ability of computer systems to efficiently perform elementary cognitive tasks such as detection, recognition and tracking. In this thesis we concentrate on the investigation of two fundamental topics in the context of image segmentation: spectral clustering and seeded image segmentation. We introduce two new algorithms for those topics that, in summary, rely on Laplacian-based operators, spectral graph theory, and minimization of energy functionals. The effectiveness of both segmentation algorithms is verified by visually evaluating the resulting partitions against state-of-the-art methods as well as through a variety of quantitative measures typically employed as benchmark by the image segmentation community. Our spectral-based segmentation algorithm combines image decomposition, similarity metrics, and spectral graph theory into a concise and powerful framework. An image decomposition is performed to split the input image into texture and cartoon components. Then, an affinity graph is generated and weights are assigned to the edges of the graph according to a gradient-based inner-product function. From the eigenstructure of the affinity graph, the image is partitioned through the spectral cut of the underlying graph. Moreover, the image partitioning can be improved by changing the graph weights by sketching interactively. Visual and numerical evaluation were conducted against representative spectral-based segmentation techniques using boundary and partition quality measures in the well-known BSDS dataset. Unlike most existing seed-based methods that rely on complex mathematical formulations that typically do not guarantee unique solution for the segmentation problem while still being prone to be trapped in local minima, our segmentation approach is mathematically simple to formulate, easy-to-implement, and it guarantees to produce a unique solution. Moreover, the formulation holds an anisotropic behavior, that is, pixels sharing similar attributes are preserved closer to each other while big discontinuities are naturally imposed on the boundary between image regions, thus ensuring better fitting on object boundaries. We show that the proposed approach significantly outperforms competing techniques both quantitatively as well as qualitatively, using the classical GrabCut dataset from Microsoft as a benchmark. While most of this research concentrates on the particular problem of segmenting an image, we also develop two new techniques to address the problem of image inpainting and photo colorization. Both methods couple the developed segmentation tools with other computer vision approaches in order to operate properly. / Segmentar uma image é visto nos dias de hoje como uma prerrogativa para melhorar a capacidade de sistemas de computador para realizar tarefas complexas de natureza cognitiva tais como detecção de objetos, reconhecimento de padrões e monitoramento de alvos. Esta pesquisa de doutorado visa estudar dois temas de fundamental importância no contexto de segmentação de imagens: clusterização espectral e segmentação interativa de imagens. Foram propostos dois novos algoritmos de segmentação dentro das linhas supracitadas, os quais se baseiam em operadores do Laplaciano, teoria espectral de grafos e na minimização de funcionais de energia. A eficácia de ambos os algoritmos pode ser constatada através de avaliações visuais das segmentações originadas, como também através de medidas quantitativas computadas com base nos resultados obtidos por técnicas do estado-da-arte em segmentação de imagens. Nosso primeiro algoritmo de segmentação, o qual ´e baseado na teoria espectral de grafos, combina técnicas de decomposição de imagens e medidas de similaridade em grafos em uma única e robusta ferramenta computacional. Primeiramente, um método de decomposição de imagens é aplicado para dividir a imagem alvo em duas componentes: textura e cartoon. Em seguida, um grafo de afinidade é gerado e pesos são atribuídos às suas arestas de acordo com uma função escalar proveniente de um operador de produto interno. Com base no grafo de afinidade, a imagem é então subdividida por meio do processo de corte espectral. Além disso, o resultado da segmentação pode ser refinado de forma interativa, mudando-se, desta forma, os pesos do grafo base. Experimentos visuais e numéricos foram conduzidos tomando-se por base métodos representativos do estado-da-arte e a clássica base de dados BSDS a fim de averiguar a eficiência da metodologia proposta. Ao contrário de grande parte dos métodos existentes de segmentação interativa, os quais são modelados por formulações matemáticas complexas que normalmente não garantem solução única para o problema de segmentação, nossa segunda metodologia aqui proposta é matematicamente simples de ser interpretada, fácil de implementar e ainda garante unicidade de solução. Além disso, o método proposto possui um comportamento anisotrópico, ou seja, pixels semelhantes são preservados mais próximos uns dos outros enquanto descontinuidades bruscas são impostas entre regiões da imagem onde as bordas são mais salientes. Como no caso anterior, foram realizadas diversas avaliações qualitativas e quantitativas envolvendo nossa técnica e métodos do estado-da-arte, tomando-se como referência a base de dados GrabCut da Microsoft. Enquanto a maior parte desta pesquisa de doutorado concentra-se no problema específico de segmentar imagens, como conteúdo complementar de pesquisa foram propostas duas novas técnicas para tratar o problema de retoque digital e colorização de imagens.

Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Foresting Transform), com funções de conexidade suaves, possuem resultados ótimos, segundo o critério da otimalidade dos caminhos descrito no artigo original da IFT, e têm sido usados com sucesso em várias aplicações, como por exemplo na segmentação de imagens RM de 1.5 Tesla. No entanto, esses métodos carecem de restrições de regularização de borda, podendo gerar segmentações com fronteiras muito irregulares e indesejadas. Eles também não distinguem bem entre bordas similares com orientações opostas, e possuem alta sensibilidade à estimativa dos pesos das arestas do grafo, gerando problemas em imagens com efeitos de inomogeneidade. Nesse trabalho são propostas extensões da IFT, do ponto de vista teórico e experimental, através do uso de funções de conexidade não suaves, para a segmentação interativa de imagens por região. A otimalidade dos novos métodos é suportada pela maximização de energias de corte em grafo, ou como o fruto de uma sequência de iterações de otimização de caminhos em grafos residuais. Como resultados principais temos: O projeto de funções de conexidade mais adaptativas e flexíveis, com o uso de pesos dinâmicos, que permitem um melhor tratamento de imagens com forte inomogeneidade. O uso de grafos direcionados, de modo a explorar a polaridade de borda dos objetos na segmentação por região, e o uso de restrições de forma que ajudam a regularizar a fronteira delineada, favorecendo a segmentação de objetos com formas mais regulares. Esses avanços só foram possíveis devido ao uso de funções não suaves. Portanto, a principal contribuição desse trabalho consiste no suporte teórico para o uso de funções não suaves, até então evitadas na literatura, abrindo novas perpectivas na pesquisa de processamento de imagens usando grafos. / Segmenting an image consist in to partition it into relevant regions for a given application, as to isolate an object of interest in the domain of an image. Segmentation is one of the most fundamental and challenging problems in image processing and computer vision. It has played an important role, for example, in neurology research, involving images of Magnetic Resonance (MR), for the purposes of diagnosis and treatment of diseases related to changes in the anatomy of the human brain. Segmentation methods based on the Image Foresting Transform (IFT), with smooth connectivity functions, have optimum results, according to the criterion of path optimality described in the original IFT paper, and have been successfully used in many applications as, for example, the segmentation of MR images of 1.5 Tesla. However, these methods present a lack of boundary regularization constraints and may produce segmentations with quite irregular and undesired boundaries. They also do not distinguish well between similar boundaries with opposite orientations, and have high sensitivity to the arc-weight estimation of the graph, producing poor results in images with strong inhomogeneity effects. In this work, we propose extensions of the IFT framework, from the theoretical and experimental points of view, through the use of non-smooth connectivity functions for region-based interactive image segmentation. The optimality of the new methods is supported by the maximization of graph cut energies, or as the result of a sequence of paths optimizations in residual graphs. We have as main results: The design of more adaptive and flexible connectivity functions, with the use of dynamic weights, that allow better handling of images with strong inhomogeneity. The use of directed graphs to exploit the boundary polarity of the objects in region-based segmentation, and the use of shape constraints that help to regularize the segmentation boundary, by favoring the segmentation of objects with more regular shapes. These advances were only made possible by the use of non-smooth functions. Therefore, the main contribution of this work is the theoretical support for the usage of non-smooth functions, which were until now avoided in literature, opening new perspectives in the research of image processing using graphs.

Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Foresting Transform), com funções de conexidade suaves, possuem resultados ótimos, segundo o critério da otimalidade dos caminhos descrito no artigo original da IFT, e têm sido usados com sucesso em várias aplicações, como por exemplo na segmentação de imagens RM de 1.5 Tesla. No entanto, esses métodos carecem de restrições de regularização de borda, podendo gerar segmentações com fronteiras muito irregulares e indesejadas. Eles também não distinguem bem entre bordas similares com orientações opostas, e possuem alta sensibilidade à estimativa dos pesos das arestas do grafo, gerando problemas em imagens com efeitos de inomogeneidade. Nesse trabalho são propostas extensões da IFT, do ponto de vista teórico e experimental, através do uso de funções de conexidade não suaves, para a segmentação interativa de imagens por região. A otimalidade dos novos métodos é suportada pela maximização de energias de corte em grafo, ou como o fruto de uma sequência de iterações de otimização de caminhos em grafos residuais. Como resultados principais temos: O projeto de funções de conexidade mais adaptativas e flexíveis, com o uso de pesos dinâmicos, que permitem um melhor tratamento de imagens com forte inomogeneidade. O uso de grafos direcionados, de modo a explorar a polaridade de borda dos objetos na segmentação por região, e o uso de restrições de forma que ajudam a regularizar a fronteira delineada, favorecendo a segmentação de objetos com formas mais regulares. Esses avanços só foram possíveis devido ao uso de funções não suaves. Portanto, a principal contribuição desse trabalho consiste no suporte teórico para o uso de funções não suaves, até então evitadas na literatura, abrindo novas perpectivas na pesquisa de processamento de imagens usando grafos. / Segmenting an image consist in to partition it into relevant regions for a given application, as to isolate an object of interest in the domain of an image. Segmentation is one of the most fundamental and challenging problems in image processing and computer vision. It has played an important role, for example, in neurology research, involving images of Magnetic Resonance (MR), for the purposes of diagnosis and treatment of diseases related to changes in the anatomy of the human brain. Segmentation methods based on the Image Foresting Transform (IFT), with smooth connectivity functions, have optimum results, according to the criterion of path optimality described in the original IFT paper, and have been successfully used in many applications as, for example, the segmentation of MR images of 1.5 Tesla. However, these methods present a lack of boundary regularization constraints and may produce segmentations with quite irregular and undesired boundaries. They also do not distinguish well between similar boundaries with opposite orientations, and have high sensitivity to the arc-weight estimation of the graph, producing poor results in images with strong inhomogeneity effects. In this work, we propose extensions of the IFT framework, from the theoretical and experimental points of view, through the use of non-smooth connectivity functions for region-based interactive image segmentation. The optimality of the new methods is supported by the maximization of graph cut energies, or as the result of a sequence of paths optimizations in residual graphs. We have as main results: The design of more adaptive and flexible connectivity functions, with the use of dynamic weights, that allow better handling of images with strong inhomogeneity. The use of directed graphs to exploit the boundary polarity of the objects in region-based segmentation, and the use of shape constraints that help to regularize the segmentation boundary, by favoring the segmentation of objects with more regular shapes. These advances were only made possible by the use of non-smooth functions. Therefore, the main contribution of this work is the theoretical support for the usage of non-smooth functions, which were until now avoided in literature, opening new perspectives in the research of image processing using graphs.

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.