Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-10T19:02:01Z No. of bitstreams: 1 TeseDO.pdf: 5356561 bytes, checksum: b2dfa29e88731d9e552bdb0ce8eda412 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T12:02:00Z (GMT) No. of bitstreams: 1 TeseDO.pdf: 5356561 bytes, checksum: b2dfa29e88731d9e552bdb0ce8eda412 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T12:02:05Z (GMT) No. of bitstreams: 1 TeseDO.pdf: 5356561 bytes, checksum: b2dfa29e88731d9e552bdb0ce8eda412 (MD5) / Made available in DSpace on 2016-10-21T12:02:11Z (GMT). No. of bitstreams: 1 TeseDO.pdf: 5356561 bytes, checksum: b2dfa29e88731d9e552bdb0ce8eda412 (MD5) Previous issue date: 2016-06-24 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Pattern recognition techniques have been widely studied and disseminated in order to develop ways to improve the e ectiveness of the pattern classi ers using labeled samples. However, such techniques usually work following the premise that the samples are independent and identically distributed in the feature space, taking into account only the local properties of the image and no information about the correlations between neighboring pixels are employed. The Optimum-Path Forest (OPF) classi er models the instances as the nodes of a graph, being the problem now is reduced to a partition of this graph. Although there are approaches that consider the context in the pattern recognition process, there is no such version for Optimum-Path Forest up to date. Thus, one of the main goal of the presented thesis is to propose a contextual version for the OPF classi er, which would employes contextual informations to support the data classi cation task using methods based on information theory and Markov Random Fields for such purpose. Since the Markov models are parameter-dependent and it is not a straightforward task to nd out the optimal values for such parameters because can assume in nite solutions, another contribution of this work is to propose an approach for modeling the process of nd out the parameters as a optimization problem, being the tness function to be maximized is the OPF accuracy over a labeled set. The results obtained by contextual classi cation were better than traditional classi cation results, as well as the optimization methods applied seemed to be a good alternative to ne-tune parameters of the Markov models as well. / Técnicas de reconhecimento de padrões em imagens foram amplamente estudadas e difundidas com o intuito de desenvolver maneiras para melhorar a eficácia dos classificadores de padrões utilizando amostras rotuladas. Contudo, muitas dessas técnicas classificam seguindo a premissa de que as instâncias são independentes e identicamente distribuídas no espaço de características, levando-se em consideração apenas as propriedades locais da imagem e nenhuma informação sobre as correlações entre pixels vizinhos são utilizadas. O classificador Floresta de Caminhos Ótimos modela as instâncias como sendo os nós de um grafo, sendo que o problema agora é reduzido para um particionamento desse grafo. Embora existam abordagens que levam em consideração o contexto no processo de reconhecimento de padrões, ainda não existe nenhuma versão do classificador Floresta de Caminhos Ótimos nesse sentido. Assim sendo, um dos objetivos principais da presente tese de doutorado _e propor uma versão contextual para a técnica Floresta de Caminhos Ótimos, a qual faria uso então de informações contextuais para auxiliar na tarefa de classificação de dados utilizando métodos baseados em Teoria da Informação e Campos Aleatórios Markovianos para tal finalidade. Uma vez que os modelos Markovianos são dependentes de parâmetros e não é possível encontrar o valor ótimo, pois podem assumir infinitas soluções, uma outra principal contribuição deste trabalho é propor uma abordagem. para modelar o processo de encontrar tais parâmetros como sendo um problema de otimização, em que a função de aptidão a ser maximizada é a acurasse da técnica Floresta de Caminhos Ótimos sobre um conjunto rotulado. Os resultados obtidos foram melhores para classificação contextual do que para o método de classificação tradicional, bem como também os métodos de otimização aplicados demonstraram ser uma boa alternativa para a definição dos parâmetros dos modelos Markovianos.

Este projeto de doutorado apresenta uma nova abordagem MAP-MRF para a classificação contextual de imagens multiespectrais utilizando combinação de modelos de Campos Aleatórios Markovianos definidos em sistemas de ordens superiores. A modelagem estatística para o problema de classificação segue o paradigma Bayesiano, com a definição de um modelo Markoviano para os dados observados (Gaussian Markov Random Field multiespectral) e outro modelo para representar o conhecimento a priori (Potts). Nesse cenário, o parâmetro β do modelo de Potts atua como um parâmetro de regularização, tendo papel fundamental no compromisso entre as observações e o conhecimento a priori, de modo que seu correto ajuste é necessário para a obtenção de bons resultados. A introdução de sistemas de vizinhança de ordens superiores requer a definição de novos métodos para a estimação dos parâmetros dos modelos Markovianos. Uma das contribuições desse trabalho é justamente propor novas equações de pseudo-verossimilhança para a estimação desses parâmetros no modelo de Potts em sistemas de segunda e terceira ordens. Apesar da abordagem por máxima pseudo-verossimilhança ser amplamente utilizada e conhecida na literatura de campos aleatórios, pouco se conhece acerca da acurácia dessa estimação. Foram derivadas aproximações para a variância assintótica dos estimadores propostos, caracterizando-os completamente no caso limite, com o intuito de realizar inferências e análises quantitativas sobre os parâmetros dos modelos Markovianos. A partir da definição dos modelos e do conhecimento dos parâmetros, o próximo estágio é a classificação das imagens multiespectrais. A solução para esse problema de inferência Bayesiana é dada pelo critério de estimação MAP, onde a solução ótima é determinada maximizando a probabilidade a posteriori, o que define um problema de otimização. Como não há solução analítica para esse problema no caso de prioris Markovianas, algoritmos iterativos de otimização combinatória foram empregados para aproximar a solução ótima. Nesse trabalho, adotam-se três métodos sub-ótimos: Iterated Conditional Modes, Maximizer of the Posterior Marginals e Game Strategy Approach. Porém, é demonstrado na literatura que tais métodos convergem para máximos locais e não globais, pois são altamente dependentes de sua condição inicial. Isto motivou o desenvolvimento de uma nova abordagem para combinação de classificadores contextuais, que utiliza múltiplas inicializações simultâneas providas por diferentes classificadores estatísticos pontuais. A metodologia proposta define um framework MAP-MRF bastante robusto para solução de problemas inversos, pois permite a utilização e a integração de diferentes condições iniciais em aplicações como classificação, filtragem e restauração de imagens. Como medidas quantitativas de desempenho, são adotados o coeficiente Kappa de Cohen e o coeficiente Tau de Kendall para verificar a concordância entre as saídas dos classificadores e a verdade terrestre (amostras pré-rotuladas). Resultados obtidos mostram que a inclusão de sistemas de vizinhança de ordens superiores é de fato capaz de melhorar significativamente não apenas o desempenho da classificação como também a estimação dos parâmetros dos modelos Markovianos, reduzindo tanto o erro de estimação quanto a variância assintótica. Além disso, a combinação de classificadores contextuais através da utilização de múltiplas inicializações simultâneas melhora significativamente o desempenho da classificação se comparada com a abordagem tradicional com apenas uma inicialização. / This work presents a novel MAP-MRF approach for multispectral image contextual classification by combining higher-order Markov Random Field models. The statistical modeling follows the Bayesian paradigm, with the definition of a multispectral Gaussian Markov Random Field model for the observations and a Potts MRF model to represent the a priori knowledge. In this scenario, the Potts MRF model parameter (β) plays the role of a regularization parameter by controlling the tradeoff between the likelihood and the prior knowledge, in a way that a suitable tunning for this parameter is required for a good performance in contextual classification. The introduction of higher-order MRF models requires the specification of novel parameter estimation methods. One of the contributions of this work is the definition of novel pseudo-likelihood equations for the estimation of these MRF parameters in second and third order neighborhood systems. Despite its widely usage in practical MRF applications, little is known about the accuracy of maximum pseudo-likelihood approach. Approximations for the asymptotic variance of the proposed MPL estimators were derived, completely characterizing their behavior in the limiting case, allowing statistical inference and quantitative analysis. From the statistical modeling and having the model parameters estimated, the next step is the multispectral image classification. The solution for this Bayesian inference problem is given by the MAP criterion, where the optimal solution is obtained by maximizing the a posteriori distribution, defining an optimization problem. As there is no analytical solution for this problem in case of Markovian priors, combinatorial optimization algorithms are required to approximate the optimal solution. In this work, we use three suboptimal methods: Iterated Conditional Modes, Maximizer of the Posterior Marginals and Game Strategy Approach, a variant approach based on non-cooperative game theory. However, it has been shown that these methods converge to local maxima solutions, since they are extremelly dependent on the initial condition. This fact motivated the development of a novel approach for combination of contextual classifiers, by making use of multiple initializations at the same time, where each one of these initial conditions is provided by different pointwise pattern classifiers. The proposed methodology defines a robust MAP-MRF framework for the solution of general inverse problems since it allows the use and integration of several initial conditions in a variety of applications as image classification, denoising and restoration. To evaluate the performance of the classification results, two statistical measures are used to verify the agreement between the classifiers output and the ground truth: Cohens Kappa and Kendalls Tau coefficient. The obtained results show that the use of higher-order neighborhood systems is capable of significantly improve not only the classification performance, but also the MRF parameter estimation by reducing both the estimation error and the asymptotic variance. Additionally, the combination of contextual classifiers through the use of multiple initializations also improves the classificatoin performance, when compared to the traditional single initialization approach.

Este projeto de doutorado apresenta uma nova abordagem MAP-MRF para a classificação contextual de imagens multiespectrais utilizando combinação de modelos de Campos Aleatórios Markovianos definidos em sistemas de ordens superiores. A modelagem estatística para o problema de classificação segue o paradigma Bayesiano, com a definição de um modelo Markoviano para os dados observados (Gaussian Markov Random Field multiespectral) e outro modelo para representar o conhecimento a priori (Potts). Nesse cenário, o parâmetro β do modelo de Potts atua como um parâmetro de regularização, tendo papel fundamental no compromisso entre as observações e o conhecimento a priori, de modo que seu correto ajuste é necessário para a obtenção de bons resultados. A introdução de sistemas de vizinhança de ordens superiores requer a definição de novos métodos para a estimação dos parâmetros dos modelos Markovianos. Uma das contribuições desse trabalho é justamente propor novas equações de pseudo-verossimilhança para a estimação desses parâmetros no modelo de Potts em sistemas de segunda e terceira ordens. Apesar da abordagem por máxima pseudo-verossimilhança ser amplamente utilizada e conhecida na literatura de campos aleatórios, pouco se conhece acerca da acurácia dessa estimação. Foram derivadas aproximações para a variância assintótica dos estimadores propostos, caracterizando-os completamente no caso limite, com o intuito de realizar inferências e análises quantitativas sobre os parâmetros dos modelos Markovianos. A partir da definição dos modelos e do conhecimento dos parâmetros, o próximo estágio é a classificação das imagens multiespectrais. A solução para esse problema de inferência Bayesiana é dada pelo critério de estimação MAP, onde a solução ótima é determinada maximizando a probabilidade a posteriori, o que define um problema de otimização. Como não há solução analítica para esse problema no caso de prioris Markovianas, algoritmos iterativos de otimização combinatória foram empregados para aproximar a solução ótima. Nesse trabalho, adotam-se três métodos sub-ótimos: Iterated Conditional Modes, Maximizer of the Posterior Marginals e Game Strategy Approach. Porém, é demonstrado na literatura que tais métodos convergem para máximos locais e não globais, pois são altamente dependentes de sua condição inicial. Isto motivou o desenvolvimento de uma nova abordagem para combinação de classificadores contextuais, que utiliza múltiplas inicializações simultâneas providas por diferentes classificadores estatísticos pontuais. A metodologia proposta define um framework MAP-MRF bastante robusto para solução de problemas inversos, pois permite a utilização e a integração de diferentes condições iniciais em aplicações como classificação, filtragem e restauração de imagens. Como medidas quantitativas de desempenho, são adotados o coeficiente Kappa de Cohen e o coeficiente Tau de Kendall para verificar a concordância entre as saídas dos classificadores e a verdade terrestre (amostras pré-rotuladas). Resultados obtidos mostram que a inclusão de sistemas de vizinhança de ordens superiores é de fato capaz de melhorar significativamente não apenas o desempenho da classificação como também a estimação dos parâmetros dos modelos Markovianos, reduzindo tanto o erro de estimação quanto a variância assintótica. Além disso, a combinação de classificadores contextuais através da utilização de múltiplas inicializações simultâneas melhora significativamente o desempenho da classificação se comparada com a abordagem tradicional com apenas uma inicialização. / This work presents a novel MAP-MRF approach for multispectral image contextual classification by combining higher-order Markov Random Field models. The statistical modeling follows the Bayesian paradigm, with the definition of a multispectral Gaussian Markov Random Field model for the observations and a Potts MRF model to represent the a priori knowledge. In this scenario, the Potts MRF model parameter (β) plays the role of a regularization parameter by controlling the tradeoff between the likelihood and the prior knowledge, in a way that a suitable tunning for this parameter is required for a good performance in contextual classification. The introduction of higher-order MRF models requires the specification of novel parameter estimation methods. One of the contributions of this work is the definition of novel pseudo-likelihood equations for the estimation of these MRF parameters in second and third order neighborhood systems. Despite its widely usage in practical MRF applications, little is known about the accuracy of maximum pseudo-likelihood approach. Approximations for the asymptotic variance of the proposed MPL estimators were derived, completely characterizing their behavior in the limiting case, allowing statistical inference and quantitative analysis. From the statistical modeling and having the model parameters estimated, the next step is the multispectral image classification. The solution for this Bayesian inference problem is given by the MAP criterion, where the optimal solution is obtained by maximizing the a posteriori distribution, defining an optimization problem. As there is no analytical solution for this problem in case of Markovian priors, combinatorial optimization algorithms are required to approximate the optimal solution. In this work, we use three suboptimal methods: Iterated Conditional Modes, Maximizer of the Posterior Marginals and Game Strategy Approach, a variant approach based on non-cooperative game theory. However, it has been shown that these methods converge to local maxima solutions, since they are extremelly dependent on the initial condition. This fact motivated the development of a novel approach for combination of contextual classifiers, by making use of multiple initializations at the same time, where each one of these initial conditions is provided by different pointwise pattern classifiers. The proposed methodology defines a robust MAP-MRF framework for the solution of general inverse problems since it allows the use and integration of several initial conditions in a variety of applications as image classification, denoising and restoration. To evaluate the performance of the classification results, two statistical measures are used to verify the agreement between the classifiers output and the ground truth: Cohens Kappa and Kendalls Tau coefficient. The obtained results show that the use of higher-order neighborhood systems is capable of significantly improve not only the classification performance, but also the MRF parameter estimation by reducing both the estimation error and the asymptotic variance. Additionally, the combination of contextual classifiers through the use of multiple initializations also improves the classificatoin performance, when compared to the traditional single initialization approach.