Estruturas do tipo linha/curva (line-like, curve-like), alongadas e ramificadas são comumente encontradas nos ecossistemas que conhecemos. Na biomedicina e na biociências, por exemplo, diversas aplicações podem ser observadas. Justamente por este motivo, extrair este tipo de estrutura em imagens é um constante desafio em problemas de análise de imagens. Porém, diversas dificuldades estão envolvidas neste processo. Normalmente as características espectrais e espaciais destas estruturas podem ser muito complexas e variáveis. Especificamente as mais \"finas\" são muito frágeis a qualquer tipo de processamento realizado na imagem e torna-se muito fácil a perda de informações importantes. Outro problema bastante comum é a ausência de parte das estruturas, seja por motivo de pouca resolução, ou por problemas de aquisição, ou por casos de oclusão. Este trabalho tem por objetivo explorar, descrever e desenvolver técnicas de detecção/segmentação de estruturas finas e ramificadas. Diferentes métodos são utilizados de forma combinada, buscando uma melhor representação topológica e perceptual das estruturas e, assim, melhores resultados. Grafos são usados para a representação das estruturas. Esta estrutura de dados vem sendo utilizada com sucesso na literatura na resolução de diversos problemas em processamento e análise de imagens. Devido à fragilidade do tipo de estrutura explorado, além das técnicas de processamento de imagens, princípios de visão computacional são usados. Busca-se, desta forma, obter um melhor \"entendimento perceptual\" destas estruturas na imagem. Esta informação perceptual e informações contextuais das estruturas são utilizadas em um modelo de campos aleatórios de Markov, buscando o resultado final da detecção através de um processo de otimização. Finalmente, também propomos o uso combinado de diferentes modalidades de imagens simultaneamente. Um software é resultado da implementação do arcabouço desenvolvido e o mesmo é utilizado em duas aplicações para avaliar a abordagem proposta: extração de estradas em imagens de satélite e extração de raízes em imagens de perfis de solo. Resultados do uso da abordagem proposta na extração de estradas em imagens de satélite mostram um melhor desempenho em comparação com método existente na literatura. Além disso, a técnica de fusão proposta apresenta melhora significativa de acordo com os resultados apresentados. Resultados inéditos e promissores são apresentados na extração de raízes de plantas. / Line- curve-like, elongated and ramified structures are commonly found inside many known ecosystems. In biomedicine and biosciences, for instance, different applications can be observed. Therefore, the process to extract this kind of structure is a constant challenge in image analysus problems. However, various difficulties are involved in this process. Their spectral and spatial characteristics are usually very complex and variable. Considering specifically the thinner ones, they are very \"fragile\" to any kind of process applied to the image, and then, it becomes easy the loss of crucial data. Another very common problem is the absence of part of the structures, either because of low image resolution and image acquisition problems or because of occlusion problems. This work aims to explore, describe and develop techniques for detection/segmentation of thin and ramified structures. Different methods are used in a combined way, aiming to reach a better topological and perceptual representation of the structures and, therefore, better results. Graphs are used to represent the structures. This data structure has been successfully used in the literature for the development of solutions for many image processing and analysis problems. Because of the fragility of the kind of structures we are dealing with, some computer vision principles are used besides usual image processing techniques. In doing so, we search for a better \"perceptual understanding\" of these structures in the image. This perceptual information along with contextual information about the structures are used in a Markov random field, searching for a final detection through an optimization process. Lastly, we propose the combined use of different image modalities simultaneously. A software is produced from the implementation of the developed framework and it is used in two application in order to evaluate the proposed approach: extraction of road networks from satellite images and extraction of plant roots from soil profile images. Results using the proposed approach for the extraction of road networks show a better performance if compared with an existent method from the literature. Besides that, the proposed fusion technique presents a meaningful improvement according to the presented results. Original and promising results are presented for the extraction of plant roots from soil profile images.

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.

In this thesis we propose to use a penalized maximum conditional likelihood criterion to estimate the graph of a general discrete Markov random field. We prove the almost sure convergence of the estimator of the graph in the case of a finite or countable infinite set of variables. Our method requires minimal assumptions on the probability distribution and contrary to other approaches in the literature, the usual positivity condition is not needed. We present several examples with a finite set of vertices and study the performance of the estimator on simulated data from theses examples. We also introduce an empirical procedure based on k-fold cross validation to select the best value of the constant in the estimators definition and show the application of this method in two real datasets. / Nesta tese propomos um critério de máxima verossimilhança penalizada para estimar o grafo de dependência condicional de um campo aleatório Markoviano discreto. Provamos a convergência quase certa do estimador do grafo no caso de um conjunto finito ou infinito enumerável de variáveis. Nosso método requer condições mínimas na distribuição de probabilidade e contrariamente a outras abordagens da literatura, a condição usual de positividade não é necessária. Introduzimos alguns exemplos com um conjunto finito de vértices e estudamos o desempenho do estimador em dados simulados desses exemplos. Também propomos um procedimento empírico baseado no método de validação cruzada para selecionar o melhor valor da constante na definição do estimador, e mostramos a aplicação deste procedimento em dois conjuntos de dados reais.

Road Networks play an important role in various applications such as urban and rural planning, infrastructure planning, transportation management, vehicle navigation. Extraction of Roads from Remote Sensed satellite images for updating road database in geographical information systems (GIS) is generally done manually by a human operator. However, manual extraction of roads is time consuming and labor intensive process. In the existing literature, there are a great number of researches published for the purpose of automating the road extraction process. However, automated processes still yield some erroneous and incomplete results and human intervention is still required. The aim of this research is to propose a framework for road network extraction from high spatial resolution multi-spectral imagery (MSI) to improve the accuracy of road extraction systems. The proposed framework begins with a spectral classification using One-class Support Vector Machines (SVM) and Gaussian Mixture Models (GMM) classifiers. Spectral Classification exploits the spectral signature of road surfaces to classify road pixels. Then, an iterative template matching filter is proposed to refine spectral classification results. K-medians clustering algorithm is employed to detect candidate road centerline points. Final road network formation is achieved by Markov Random Fields. The extracted road network is evaluated against a reference dataset using a set of quality metrics.

This thesis explores synthesis by example as a paradigm for rendering real-world phenomena. In particular, phenomena that can be visually described as texture are considered. We exploit, for synthesis, the self-repeating nature of the visual elements constituting these texture exemplars. Techniques for unconstrained as well as constrained/controllable synthesis of both image and video textures are presented. For unconstrained synthesis, we present two robust techniques that can perform spatio-temporal extension, editing, and merging of image as well as video textures. In one of these techniques, large patches of input texture are automatically aligned and seamless stitched with each other to generate realistic looking images and videos. The second technique is based on iterative optimization of a global energy function that measures the quality of the synthesized texture with respect to the given input exemplar. We also present a technique for controllable texture synthesis. In particular, it allows for generation of motion-controlled texture animations that follow a specified flow field. Animations synthesized in this fashion maintain the structural properties like local shape, size, and orientation of the input texture even as they move according to the specified flow. We cast this problem into an optimization framework that tries to simultaneously satisfy the two (potentially competing) objectives of similarity to the input texture and consistency with the flow field. This optimization is a simple extension of the approach used for unconstrained texture synthesis. A general framework for example-based synthesis and rendering is also presented. This framework provides a design space for constructing example-based rendering algorithms. The goal of such algorithms would be to use texture exemplars to render animations for which certain behavioral characteristics need to be controlled. Our motion-controlled texture synthesis technique is an instantiation of this framework where the characteristic being controlled is motion represented as a flow field.

Textual information within digital media can be used in many areas such as, indexing and structuring of media databases, in the aid of visually impaired, translation of foreign signs and many more. This said, mainly text can be separated into two categories in digital media as, overlay-text and scene-text. In this thesis localization and recognition of video text regardless of its category in digital media is investigated. As a necessary first step, framework of a complete system is discussed. Next, a comparative analysis of feature vector and classification method pairs is presented. Furthermore, multi-part nature of text is exploited by proposing a novel Markov Random Field approach for the classification of text/non-text regions. Additionally, better localization of text is achieved by introducing bounding-box extraction method. And for the recognition of text regions, a handprint based Optical Character Recognition system is thoroughly investigated. During the investigation of text recognition, multi-hypothesis approach for the segmentation of background is proposed by incorporating k-Means clustering. Furthermore, a novel dictionary-based ranking mechanism is proposed for recognition spelling correction. And overall system is simulated on a challenging data set. Also, a through survey on scene-text localization and recognition is presented. Furthermore, challenges are identified and discussed by providing related work on them. Scene-text localization simulations on a public competition data set are also provided. Lastly, in order to improve recognition performance of scene-text on signs that are affected from perspective projection distortion, a rectification method is proposed and simulated.

A feature of minimizing images of a class of binary Markov random field energies is introduced and proved. Using this, the collection of minimizing images of levels of higher order, levelable MRF energies is shown to be a monotone collection. This implies that these images can be combined to give minimizing images of the MRF energy itself. Due to the recent developments, second and third order binary MRF energies of the mentioned class are known to be exactly minimized by maximum flow/minimum cut computations on appropriately constructed graphs. With the aid of these developments an exact and efficient algorithm to minimize levelable second and third order MRF energies, which is composed of a series of maximum flow/minimum cut computations, is proposed and applications of the proposed algorithm to image restoration are given.

The Hilbert space of probability mass functions (pmf) is introduced in this thesis. A factorization method for multivariate pmfs is proposed by using the tools provided by the Hilbert space of pmfs. The resulting factorization is special for two reasons. First, it reveals the algebraic relations between the involved random variables. Second, it determines the conditional independence relations between the random variables. Due to the first property of the resulting factorization, it can be shown that channel decoders can be employed in the solution of probabilistic inference problems other than decoding. This approach might lead to new probabilistic inference algorithms and new hardware options for the implementation of these algorithms. An example of new inference algorithms inspired by the idea of using channel decoder for other inference tasks is a multiple-input multiple-output (MIMO) detection algorithm which has a complexity of the square-root of the optimum MIMO detection algorithm. Keywords: The Hilbert space of pmfs, factorization of pmfs, probabilistic inference, MIMO detection, Markov random fields iv

Vaizdų analizė šiomis dienomis yra labai svarbi dėl plataus pritaikymo daugelyje mokslo ir pramonės sričių. Vienas iš vaizdų analizės įrankių – objekto atpažinimas (klasifikavimas) (angl. pattern recognition). Statistinis objekto atpažinimas, paremtas Bajeso diskriminantinėmis funkcijomis – šio darbo objektas. Sprendžiama problema – optimalus klasifikavimas stacionaraus Gauso atsitiktinio lauko (GRF) stebinio, į vieną iš dviejų klasių, laikant, kad jis yra priklausomas nuo mokymo imties ir atsižvelgiant į jo ryšius su mokymo imtimi. Pateikta klasifikavimo procedūra, kuri Gauso atsitiktinio lauko stebinius klasifikuoja optimaliai. Yra pasiūlytas naujas klasifikavimo su mokymu metodas, kuris duoda geresnius rezultatus, lyginant su įprastai naudojamomis Bajeso diskriminantinėmis funkcijomis. Metodas realizuotas R sistemos aplinkoje ir tikrinamas eksperimentų būdu, atstatant vaizdus, sugadintus erdvėje koreliuoto triukšmo. Tokia situacija pasitaiko natūraliai, pavyzdžiui, degant miškui dūmai uždengia nuotolinio stebėjimo vaizdą, gautą iš palydovo. Taip pat tokia situacija gana dažna esant debesuotumui. Esant tokiai situacijai erdvinės priklausomybės įvedimas į klasifikacijos problemą pasiteisina. Pateiktos (išvestos) analitinės klaidų tikimybių išraiškos Bajeso diskriminantinėms funkcijoms, kurios yra kaip šių funkcijų veikimo kriterijus. Ištirta klaidų tikimybių priklausomybė nuo statistinių parametrų reikšmių. / Image analysis is very important because of its usage in many different areas of science and industry. Pattern recognition (classification) is a tool used in image analysis. Statistical pattern recognition, based on Bayes discriminant functions is the object of this work. The main problem is to classify stationary Gaussian random field observation into one off two classes, considering, that it is dependant on training sample ant taking in to account the relationship with training sample. The new supervised classification method, based on Bayes discriminant functions, is proposed and it gives better results comparing with other commonly used Bayes discriminant functions. Method is programmed with R program and investigated experimentally, reconstructing images corrupted by spatially correlated noise. Such situation occurs naturally, for example, during the forest fire smoke covers the remotely sensed image, gathered from the satellite. Also such situation is often during cloudy days. During such situation the incorporation of the spatial dependences into the classification problem is useful. Analytical error rates of Bayes discriminant functions are presented (derived), which are the criterion of these functions. Also, the dependences on statistical parameters are investigated for these error rates.

Image analysis is very important because of its usage in many different areas of science and industry. Pattern recognition (classification) is a tool used in image analysis. Statistical pattern recognition, based on Bayes discriminant functions is the object of this work. The main problem is to classify stationary Gaussian random field observation into one off two classes, considering, that it is dependant on training sample ant taking in to account the relationship with training sample. The new supervised classification method, based on Bayes discriminant functions, is proposed and it gives better results comparing with other commonly used Bayes discriminant functions. Method is programmed with R program and investigated experimentally, reconstructing images corrupted by spatially correlated noise. Such situation occurs naturally, for example, during the forest fire smoke covers the remotely sensed image, gathered from the satellite. Also such situation is often during cloudy days. During such situation the incorporation of the spatial dependences into the classification problem is useful. Analytical error rates of Bayes discriminant functions are presented (derived), which are the criterion of these functions. Also, the dependences on statistical parameters are investigated for these error rates. / Vaizdų analizė šiomis dienomis yra labai svarbi dėl plataus pritaikymo daugelyje mokslo ir pramonės sričių. Vienas iš vaizdų analizės įrankių – objekto atpažinimas (klasifikavimas) (angl. pattern recognition). Statistinis objekto atpažinimas, paremtas Bajeso diskriminantinėmis funkcijomis – šio darbo objektas. Sprendžiama problema – optimalus klasifikavimas stacionaraus Gauso atsitiktinio lauko (GRF) stebinio, į vieną iš dviejų klasių, laikant, kad jis yra priklausomas nuo mokymo imties ir atsižvelgiant į jo ryšius su mokymo imtimi. Pateikta klasifikavimo procedūra, kuri Gauso atsitiktinio lauko stebinius klasifikuoja optimaliai. Yra pasiūlytas naujas klasifikavimo su mokymu metodas, kuris duoda geresnius rezultatus, lyginant su įprastai naudojamomis Bajeso diskriminantinėmis funkcijomis. Metodas realizuotas R sistemos aplinkoje ir tikrinamas eksperimentų būdu, atstatant vaizdus, sugadintus erdvėje koreliuoto triukšmo. Tokia situacija pasitaiko natūraliai, pavyzdžiui, degant miškui dūmai uždengia nuotolinio stebėjimo vaizdą, gautą iš palydovo. Taip pat tokia situacija gana dažna esant debesuotumui. Esant tokiai situacijai erdvinės priklausomybės įvedimas į klasifikacijos problemą pasiteisina. Pateiktos (išvestos) analitinės klaidų tikimybių išraiškos Bajeso diskriminantinėms funkcijoms, kurios yra kaip šių funkcijų veikimo kriterijus. Ištirta klaidų tikimybių priklausomybė nuo statistinių parametrų reikšmių.