No description available.

Casamento de padrões de pontos em Espaços Euclidianos é um dos problemas fundamentais em reconhecimento de padrões, tendo aplicações que vão desde Visão Computacional até Química Computacional. Sempre que dois padrões complexos estão codi- ficados em termos de dois conjuntos de pontos que identificam suas características fundamentais, sua comparação pode ser vista como um problema de casamento de padrões de pontos. Este trabalho propõe uma abordagem unificada para os problemas de casamento exato e inexato de padrões de pontos em Espaços Euclidianos de dimensão arbitrária. No caso de casamento exato, é garantida a obtenção de uma solução ótima. Para casamento inexato (quando ruído está presente), resultados experimentais confirmam a validade da abordagem. Inicialmente, considera-se o problema de casamento de padrões de pontos como um problema de casamento de grafos ponderados. O problema de casamento de grafos ponderados é então formulado como um problema de inferência Bayesiana em um modelo gráfico probabilístico. Ao explorar certos vínculos fundamentais existentes em padrões de pontos imersos em Espaços Euclidianos, provamos que, para o casamento exato de padrões de pontos, um modelo gráfico simples é equivalente ao modelo completo. É possível mostrar que inferência probabilística exata neste modelo simples tem complexidade polinomial para qualquer dimensionalidade do Espaço Euclidiano em consideração. Experimentos computacionais comparando esta técnica com a bem conhecida baseada em relaxamento probabilístico evidenciam uma melhora significativa de desempenho para casamento inexato de padrões de pontos. A abordagem proposta é signi- ficativamente mais robusta diante do aumento do tamanho dos padrões envolvidos. Na ausência de ruído, os resultados são sempre perfeitos. / Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise, the results are always perfect.

Casamento de padrões de pontos em Espaços Euclidianos é um dos problemas fundamentais em reconhecimento de padrões, tendo aplicações que vão desde Visão Computacional até Química Computacional. Sempre que dois padrões complexos estão codi- ficados em termos de dois conjuntos de pontos que identificam suas características fundamentais, sua comparação pode ser vista como um problema de casamento de padrões de pontos. Este trabalho propõe uma abordagem unificada para os problemas de casamento exato e inexato de padrões de pontos em Espaços Euclidianos de dimensão arbitrária. No caso de casamento exato, é garantida a obtenção de uma solução ótima. Para casamento inexato (quando ruído está presente), resultados experimentais confirmam a validade da abordagem. Inicialmente, considera-se o problema de casamento de padrões de pontos como um problema de casamento de grafos ponderados. O problema de casamento de grafos ponderados é então formulado como um problema de inferência Bayesiana em um modelo gráfico probabilístico. Ao explorar certos vínculos fundamentais existentes em padrões de pontos imersos em Espaços Euclidianos, provamos que, para o casamento exato de padrões de pontos, um modelo gráfico simples é equivalente ao modelo completo. É possível mostrar que inferência probabilística exata neste modelo simples tem complexidade polinomial para qualquer dimensionalidade do Espaço Euclidiano em consideração. Experimentos computacionais comparando esta técnica com a bem conhecida baseada em relaxamento probabilístico evidenciam uma melhora significativa de desempenho para casamento inexato de padrões de pontos. A abordagem proposta é signi- ficativamente mais robusta diante do aumento do tamanho dos padrões envolvidos. Na ausência de ruído, os resultados são sempre perfeitos. / Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise, the results are always perfect.

Casamento de padrões de pontos em Espaços Euclidianos é um dos problemas fundamentais em reconhecimento de padrões, tendo aplicações que vão desde Visão Computacional até Química Computacional. Sempre que dois padrões complexos estão codi- ficados em termos de dois conjuntos de pontos que identificam suas características fundamentais, sua comparação pode ser vista como um problema de casamento de padrões de pontos. Este trabalho propõe uma abordagem unificada para os problemas de casamento exato e inexato de padrões de pontos em Espaços Euclidianos de dimensão arbitrária. No caso de casamento exato, é garantida a obtenção de uma solução ótima. Para casamento inexato (quando ruído está presente), resultados experimentais confirmam a validade da abordagem. Inicialmente, considera-se o problema de casamento de padrões de pontos como um problema de casamento de grafos ponderados. O problema de casamento de grafos ponderados é então formulado como um problema de inferência Bayesiana em um modelo gráfico probabilístico. Ao explorar certos vínculos fundamentais existentes em padrões de pontos imersos em Espaços Euclidianos, provamos que, para o casamento exato de padrões de pontos, um modelo gráfico simples é equivalente ao modelo completo. É possível mostrar que inferência probabilística exata neste modelo simples tem complexidade polinomial para qualquer dimensionalidade do Espaço Euclidiano em consideração. Experimentos computacionais comparando esta técnica com a bem conhecida baseada em relaxamento probabilístico evidenciam uma melhora significativa de desempenho para casamento inexato de padrões de pontos. A abordagem proposta é signi- ficativamente mais robusta diante do aumento do tamanho dos padrões envolvidos. Na ausência de ruído, os resultados são sempre perfeitos. / Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise, the results are always perfect.

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.