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.

L'imagerie hyperspectrale, grâce à un nombre élevé de bandes spectrales très fines et contigües, est capable d'associer àchaque pixel d'une image une signature spectrale caractéristique du comportement réflectif du matériau ou du mélange dematériaux présents dans ce pixel. La plupart des algorithmes de classification tirent profit de cette grande profusiond'information spectrale mais exploitent très peu l'information contextuelle existant entre les pixels appartenant à un mêmevoisinage. L'objectif de cette thèse est de réaliser de nouveaux algorithmes utilisant simultanément les informations spectraleet spatiale à des fins de classification et d'étudier la complémentarité de ces deux types d'information dans divers contextes.Dans cette optique nous avons développé trois scénarios de classification sensiblement différents, chacun étant adapté à untype d'application particulier.Nous avons tout d'abord développé un procédé d'extraction puis de classification vectorielle d'un ensemble de caractéristiquesspectrales et spatiales. Les caractéristiques spectrales sont extraites au moyen de méthodes visant à réduire la dimension desimages hyperspectrales tout en conservant une majorité de l'information utile. Les caractéristiques spatiales sont quant àelles produites par l'intermédiaire d'outils de caractérisation de la texture (matrices de co-occurrence et spectres de texture)ou de la forme (profils morphologiques). Nous nous sommes ensuite intéressés à la modélisation markovienne et avonsentrepris d'adapter un algorithme de classification de type Conditional Random Field à un contexte hyperspectral. Notretroisième et dernière approche s'appuie sur une segmentation préalable de l'image afin de réaliser une classification parzones et non plus par pixels.L'information spectrale pure permet de regrouper efficacement des pixels présentant des signatures spectrales similaires etsuffit généralement dans le cadre de problèmes de classification ne faisant intervenir que des classes sémantiquement trèsprécises, liées à un unique type de matériau. Les classes plus générales (utilisées par exemple pour des applicationsd'aménagement des sols) se composent en revanche de plusieurs matériaux parfois communs à plusieurs classes et agencésselon des motifs qui se répètent. Caractérisables à la fois spatialement et spectralement, ces classes sont susceptibles d'êtreplus complètement décrites par une utilisation simultanée de ces deux types d'information. Pour conclure cette étude, nousavons effectué une comparaison des trois méthodes d'intégration de l'information spatiale au processus de classification selonles trois critères sont la précision de classification, la complexité algorithmique et la robustesse / Thanks to a high number of thin and contiguous spectral bands, the hyperpectral imagery can associate to each pixel of animage a spectral signature representing the reflective behaviour of the materials composing the pixel. Most of theclassification algorithms use this great amount of spectral information without noticing the contextual information betweenthe pixels that belong to the same neighborhood. This study aims to realize new algorithms using simultaneously the spectraland spatial informations in order to classify hyperspectral images, and to study their complementarity in several contexts. Forthis purpose, we have developped three different classification scenarios, each one adapted to a particular type of application.The first scenario consists in a vectorial classification processus. Several spectral and spatial characteristics are extracted andmerged in order to form a unique data set, which is classified using a Support Vector Machine method or a Gaussian MixingModel algorithm. The spectral characteristics are extracted using dimension reduction method, such as PCA or MNF, while thespatial characteristics are extracted using textural characterization tools (co-occurrence matrices and texture spectra) ormorphological tools (morphological profiles). For the second scenario, we adapted a Conditional Random Field algorithm tothe hyperspectral context. Finally, the last scenario is an area-wise classification algorithm relying on a textural segmentationmethod as a pre-processing step.The spectral information is generally sufficient to deal with semantically simple classes, linked to a unique type of material.Complex classes (such as ground amenagment classes) are composed of several materials which potentially belong to morethan one class. Those classes can be characterized both spectrally and spatially, which means that they can be morecompletly described using both spectral and spatial informations. To conclude this study, we compared the threespectral/spatial classification scenarios using three criterions : classification accuracy, algorithmic complexity and strength.

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.

A identificação de regiões cromossômicas, ou blocos de dependência dentro do genoma humano, que são transmitidas em conjunto para seus descendentes (haplótipos) tem sido um desafio e alvo de várias iniciativas de pesquisa, muitas delas utilizando dados de plataformas de marcadores moleculares do tipo SNP (Single Nucleotide Polymorphisms - SNPs), com alta densidade dentro do DNA humano. Este trabalho faz uso de uma modelagem estocástica de campos Markovianos de alcance variável, em uma amostra estratificada de diferentes populações, para encontrar blocos de SNPs, independentes entre si, estruturando assim o genoma em regiões ilhadas de dependência. Foram utilizados dados públicos de SNPs de diferentes populações mundiais (projeto HapMap), além de uma amostra da população brasileira. As regiões de dependência configuram janelas de influência as quais foram usadas para caracterizar as diferentes populações de acordo com sua ancestralidade e os resultados obtidos mostraram que as janelas da população brasileira têm, em média, tamanho maior, evidenciando a sua história recente de miscigenação. É também proposta uma otimização da função de verossimilhança do problema para obter as janelas de consenso maximais de todas as populações. Dada uma determinada janela de consenso, uma medida de distância apropriada para variáveis categóricas, é adotada para medir sua homogeneidade/heterogeneidade. Janelas homogêneas foram identificadas na região HLA (Human Leukocyte Antigen) do genoma, a qual está associada à resposta imunológica. O tamanho médio dessas janelas foi maior do que a média encontrada no restante do cromossomo, confirmando a alta dependência existente nesta região, considerada como bastante conservada na evolução humana. Finalmente, considerando a distribuição dos SNPs entre as populações nas janelas mais heterogêneas, a Análise de Correspondência foi aplicada na construção de um classificador capaz de determinar o percentual relativo de ancestralidade de um indivíduo, o qual, submetido à validação, obteve uma eficiência de 90% de acerto da população originária. / The identification of chromosome regions, or dependency blocks in the human genome, that are transmitted together to offspring (haploids) has been a challenge and object of several research initiatives, many of them using platforms of molecular markers such as SNP (Single Nucleotide Polymorphisms), with high density inside the human DNA. This work makes use of a stochastic modeling of Markov random fields, in a stratified sample of different populations, to find SNPs blocks, independent of each other, thus structuring the genome in stranded regions of dependency. Public data from different worldwide populations were used (HapMap project), beyond a Brazilian population. The dependence regions constitute windows of influence which were used to characterize the different populations according of their ancestry and the results showed that the Brazilian populations windows have, on average, a bigger size, showing their recent history of admixture. It is also proposed an optimization of likelihood function of the problem for the maximal windows of consensus from all populations. Given a particular window of consensus, a distance measure appropriated to categorical variables, it is adopted to evaluate its homogeneity/heterogeneity. Homogeneous windows were identified within region of genome called HLA (Human Leukocyte Antigen), which is associated with the immune response. The average size of these windows was bigger than the average found in the rest of the chromosome, confirming the high dependence verified in this region, considered highly conserved in the human evolution. Finally, considering the distribution of the SNPs among the populations in the most heterogeneous windows, the Correspondence Analysis was applied to build a classifier able to determine, for a given individual, the ancestry proportion from each population considered, which, submitted to a validation, obtained a 90% accuracy of the original population.

Orientadores: Christophe Frédéric Gallesco, Serguei Popov / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-22T17:31:03Z (GMT). No. of bitstreams: 1 VasquezMercedes_ClaudiaEdith_M.pdf: 743991 bytes, checksum: 587d04d1b7b45c75dd5eeea766258b02 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Mestrado / Estatistica / Mestra em Estatística

A identificação de regiões cromossômicas, ou blocos de dependência dentro do genoma humano, que são transmitidas em conjunto para seus descendentes (haplótipos) tem sido um desafio e alvo de várias iniciativas de pesquisa, muitas delas utilizando dados de plataformas de marcadores moleculares do tipo SNP (Single Nucleotide Polymorphisms - SNPs), com alta densidade dentro do DNA humano. Este trabalho faz uso de uma modelagem estocástica de campos Markovianos de alcance variável, em uma amostra estratificada de diferentes populações, para encontrar blocos de SNPs, independentes entre si, estruturando assim o genoma em regiões ilhadas de dependência. Foram utilizados dados públicos de SNPs de diferentes populações mundiais (projeto HapMap), além de uma amostra da população brasileira. As regiões de dependência configuram janelas de influência as quais foram usadas para caracterizar as diferentes populações de acordo com sua ancestralidade e os resultados obtidos mostraram que as janelas da população brasileira têm, em média, tamanho maior, evidenciando a sua história recente de miscigenação. É também proposta uma otimização da função de verossimilhança do problema para obter as janelas de consenso maximais de todas as populações. Dada uma determinada janela de consenso, uma medida de distância apropriada para variáveis categóricas, é adotada para medir sua homogeneidade/heterogeneidade. Janelas homogêneas foram identificadas na região HLA (Human Leukocyte Antigen) do genoma, a qual está associada à resposta imunológica. O tamanho médio dessas janelas foi maior do que a média encontrada no restante do cromossomo, confirmando a alta dependência existente nesta região, considerada como bastante conservada na evolução humana. Finalmente, considerando a distribuição dos SNPs entre as populações nas janelas mais heterogêneas, a Análise de Correspondência foi aplicada na construção de um classificador capaz de determinar o percentual relativo de ancestralidade de um indivíduo, o qual, submetido à validação, obteve uma eficiência de 90% de acerto da população originária. / The identification of chromosome regions, or dependency blocks in the human genome, that are transmitted together to offspring (haploids) has been a challenge and object of several research initiatives, many of them using platforms of molecular markers such as SNP (Single Nucleotide Polymorphisms), with high density inside the human DNA. This work makes use of a stochastic modeling of Markov random fields, in a stratified sample of different populations, to find SNPs blocks, independent of each other, thus structuring the genome in stranded regions of dependency. Public data from different worldwide populations were used (HapMap project), beyond a Brazilian population. The dependence regions constitute windows of influence which were used to characterize the different populations according of their ancestry and the results showed that the Brazilian populations windows have, on average, a bigger size, showing their recent history of admixture. It is also proposed an optimization of likelihood function of the problem for the maximal windows of consensus from all populations. Given a particular window of consensus, a distance measure appropriated to categorical variables, it is adopted to evaluate its homogeneity/heterogeneity. Homogeneous windows were identified within region of genome called HLA (Human Leukocyte Antigen), which is associated with the immune response. The average size of these windows was bigger than the average found in the rest of the chromosome, confirming the high dependence verified in this region, considered highly conserved in the human evolution. Finally, considering the distribution of the SNPs among the populations in the most heterogeneous windows, the Correspondence Analysis was applied to build a classifier able to determine, for a given individual, the ancestry proportion from each population considered, which, submitted to a validation, obtained a 90% accuracy of the original population.

<p>The main part of this thesis is concerned with detailed explanation of a newly proposed Markov random field-based de-interlacing algorithm. Previous works, assume a first or higher-order Markovian spatial inter-dependency between the pixel intensity values. In accord with the specific interpolation problem in hand, they try to approximate the Markov random field parameters using available original pixels. Then using the approximate model, they define an objective function such as energy function of the MRF to be optimized. The efficiency and accuracy of the optimization step is as important as the effectiveness of definition of the cost (objective function) as well as the MRF model.\\ \indent The major concept that distinguishes the newly proposed algorithm with the aforementioned MRF-based models is the definition of the MRF not over the intensity domain but over interpolator (interpolation method) domain. Unlike previous MRF-based models which try to estimate a two-dimensional array of pixel values, this new method estimates an MRF of interpolation function (interpolators) associated with the 2-D array of pixel intensity values.\\ \indent With some modifications, one can utilize the proposed model in different related fields such as image and video up-conversion, view interpolation and frame-rate up-conversion. To prove this potential of the proposed MRF-based model, we extend it to an image up-scaling algorithm. This algorithm uses a simplified version of the proposed MRF-based model for the purpose of image up-scaling by a factor of two in each spatial direction. Simulation results prove that the proposed model obtains competing performance results when applied in the two interpolation problems of video de-interlacing and image up-scaling.</p> / Master of Applied Science (MASc)

Estimation of Distribution Algorithms (EDAs) belong to the class of population based optimisation algorithms. They are motivated by the idea of discovering and exploiting the interaction between variables in the solution. They estimate a probability distribution from population of solutions, and sample it to generate the next population. Many EDAs use probabilistic graphical modelling techniques for this purpose. In particular, directed graphical models (Bayesian networks) have been widely used in EDA. This thesis proposes an undirected graphical model (Markov Random Field (MRF)) approach to estimate and sample the distribution in EDAs. The interaction between variables in the solution is modelled as an undirected graph and the joint probability of a solution is factorised as a Gibbs distribution. The thesis describes a model of fitness function that approximates the energy in the Gibbs distribution, and shows how this model can be fitted to a population of solutions to estimate the parameters of the MRF. The estimated MRF is then sampled to generate the next population. This approach is applied to estimation of distribution in a general framework of an EDA, called Distribution Estimation using Markov Random Fields (DEUM). The thesis then proposes several variants of DEUM using different sampling techniques and tests their performance on a range of optimisation problems. The results show that, for most of the tested problems, the DEUM algorithms significantly outperform other EDAs, both in terms of number of fitness evaluations and the quality of the solutions found by them. There are two main explanations for the success of DEUM algorithms. Firstly, DEUM builds a model of fitness function to approximate the MRF. This contrasts with other EDAs, which build a model of selected solutions. This allows DEUM to use fitness in variation part of the evolution. Secondly, DEUM exploits the temperature coefficient in the Gibbs distribution to regulate the behaviour of the algorithm. In particular, with higher temperature, the distribution is closer to being uniform and with lower temperature it concentrates near some global optima. This gives DEUM an explicit control over the convergence of the algorithm, resulting in better optimisation.

L’imagerie hyperspectrale est très largement employée en télédétection pour diverses applications, dans le domaine civil comme dans le domaine militaire. Une image hyperspectrale est le résultat de l’acquisition d’une seule scène observée dans plusieurs longueurs d’ondes. Par conséquent, chacun des pixels constituant cette image est représenté par un vecteur de mesures (généralement des réflectances) appelé spectre. Une étape majeure dans l’analyse des données hyperspectrales consiste à identifier les composants macroscopiques (signatures) présents dans la région observée et leurs proportions correspondantes (abondances). Les dernières techniques développées pour ces analyses ne modélisent pas correctement ces images. En effet, habituellement ces techniques supposent l’existence de pixels purs dans l’image, c’est-à-dire des pixels constitué d’un seul matériau pur. Or, un pixel est rarement constitué d’éléments purs distincts l’un de l’autre. Ainsi, les estimations basées sur ces modèles peuvent tout à fait s’avérer bien loin de la réalité. Le but de cette étude est de proposer de nouveaux algorithmes d’estimation à l’aide d’un modèle plus adapté aux propriétés intrinsèques des images hyperspectrales. Les paramètres inconnus du modèle sont ainsi déduits dans un cadre Bayésien. L’utilisation de méthodes de Monte Carlo par Chaînes de Markov (MCMC) permet de surmonter les difficultés liées aux calculs complexes de ces méthodes d’estimation. / Hyperspectral imagery has been widely used in remote sensing for various civilian and military applications. A hyperspectral image is acquired when a same scene is observed at different wavelengths. Consequently, each pixel of such image is represented as a vector of measurements (reflectances) called spectrum. One major step in the analysis of hyperspectral data consists of identifying the macroscopic components (signatures) that are present in the sensored scene and the corresponding proportions (concentrations). The latest techniques developed for this analysis do not properly model these images. Indeed, these techniques usually assume the existence of pure pixels in the image, i.e. pixels containing a single pure material. However, a pixel is rarely composed of pure spectrally elements, distinct from each other. Thus, such models could lead to weak estimation performance. The aim of this thesis is to propose new estimation algorithms with the help of a model that is better suited to the intrinsic properties of hyperspectral images. The unknown model parameters are then infered within a Bayesian framework. The use of Markov Chain Monte Carlo (MCMC) methods allows one to overcome the difficulties related to the computational complexity of these inference methods.