Uma das etapas mais importantes da análise de imagens e, que conta com uma enorme quantidade de aplicações, é a segmentação. No entanto, uma boa parte das técnicas tradicionais apresenta alto custo computacional, dificultando sua aplicação em imagens de alta resolução como, por exemplo, as imagens de ninhais de aves do Pantanal que também serão analisadas neste trabalho. Diante disso, é proposta uma nova abordagem de segmentação que combina algoritmos de detecção de comunidades, pertencentes à teoria das redes complexas, com técnicas de extração de superpixels. Tal abordagem é capaz de segmentar imagens de alta resolução mantendo o compromisso entre acurácia e tempo de processamento. Além disso, como as imagens de ninhais analisadas apresentam características peculiares que podem ser mais bem tratadas por técnicas de segmentação por textura, a técnica baseada em Markov Random Fields (MRF) é proposta, como um complemento à abordagem de segmentação inicial, para realizar a identificação final das aves. Por fim, devido à importância de avaliar quantitativamente a qualidade das segmentações obtidas, um nova métrica de avaliação baseada em ground-truth foi desenvolvida, sendo de grande importância para a área. Este trabalho contribuiu para o avanço do estado da arte das técnicas de segmentação de imagens de alta resolução, aprimorando e desenvolvendo métodos baseados na combinação de redes complexas com superpixels, os quais alcançaram resultados satisfatórios com baixo tempo de processamento. Além disso, uma importante contribuição referente ao censo demográfico de aves por meio da análise de imagens aéreas de ninhais foi viabilizada por meio da aplicação da técnica de segmentação MRF. / Segmentation is one of the most important steps in image analysis with a large range of applications. However, some traditional techniques exhibit high computational costs, hindering their application in high resolution images such as the images of birds nests from Pantanal, one of Brazilian most important wetlands. Therefore, we propose a new segmentation approach that combines community detection algorithms, originated from the theory of the complex networks, with superpixels extraction techniques. This approach is capable of segmenting high resolution images while maintaining the trade-off between accuracy and processing time. Moreover, as the nest images exhibit peculiar characteristics that can be better dealt with texture segmentation techniques, the Markov Random Fields (MRF) technique is proposed, as a complement to the initial approach, to perform the final identification of the birds. Finally, due to the importance of the quantitatively evaluation of the segmentation quality, a new evaluation metric based on ground-truth was developed, being of great importance to the segmentation field. This work contributed to the state of art of high resolution images segmentation techniques, improving and developing methods based on combination of complex networks and superpixels, which generated satisfactory results within low processing time. Moreover, an important contribution for the birds census by the analysis of aerial images of birds nests was made possible by application of the MRF technique.

En kunskapsgraf lagrar information från webben i form av relationer mellan olika entiteter. En kunskapsgrafs kvalité bestäms av hur komplett den är och dess noggrannhet. Dessvärre har många nuvarande kunskapsgrafer brister i form av saknad fakta och inkorrekt information. Nuvarande lösningar av länkförutsägelser mellan entiteter har problem med skalbarhet och hög arbetskostnad. Denna uppsats föreslår ett deklarativt regelbaserat probabilistiskt ramverk för att utföra länkförutsägelse. Systemet involverar en regelutvinnande modell till ett “hinge-loss Markov random fields” för att föreslå länkar. Vidare utvecklades tre strategier för regeloptimering för att förbättra reglernas kvalité. Jämfört med tidigare lösningar så bidrar detta arbete till att drastiskt reducera arbetskostnader och en mer spårbar modell. Varje metod har utvärderas med precision och F-värde på NELL och Freebase15k. Det visar sig att strategin för regeloptimering presterade bäst. MAP-uppskattningen för den bästa modellen på NELL är 0.754, vilket är bättre än en nuvarande spjutspetsteknologi graphical model(0.306). F-värdet för den bästa modellen på Freebase15k är 0.709. / The knowledge graph stores factual information from the web in form of relationships between entities. The quality of a knowledge graph is determined by its completeness and accuracy. However, most current knowledge graphs often miss facts or have incorrect information. Current link prediction solutions have problems of scalability and high labor costs. This thesis proposed a declarative rule-based probabilistic framework to perform link prediction. The system incorporates a rule-mining model into a hingeloss Markov random fields to infer links. Moreover, three rule optimization strategies were developed to improve the quality of rules. Compared with previous solutions, this work dramatically reduces manual costs and provides a more tractable model. Each proposed method has been evaluated with Average Precision or F-score on NELL and Freebase15k. It turns out that the rule optimization strategy performs the best. The MAP of the best model on NELL is 0.754, better than a state-of-the-art graphical model (0.306). The F-score of the best model on Freebase15k is 0.709.

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ų.

Uma das etapas mais importantes da análise de imagens e, que conta com uma enorme quantidade de aplicações, é a segmentação. No entanto, uma boa parte das técnicas tradicionais apresenta alto custo computacional, dificultando sua aplicação em imagens de alta resolução como, por exemplo, as imagens de ninhais de aves do Pantanal que também serão analisadas neste trabalho. Diante disso, é proposta uma nova abordagem de segmentação que combina algoritmos de detecção de comunidades, pertencentes à teoria das redes complexas, com técnicas de extração de superpixels. Tal abordagem é capaz de segmentar imagens de alta resolução mantendo o compromisso entre acurácia e tempo de processamento. Além disso, como as imagens de ninhais analisadas apresentam características peculiares que podem ser mais bem tratadas por técnicas de segmentação por textura, a técnica baseada em Markov Random Fields (MRF) é proposta, como um complemento à abordagem de segmentação inicial, para realizar a identificação final das aves. Por fim, devido à importância de avaliar quantitativamente a qualidade das segmentações obtidas, um nova métrica de avaliação baseada em ground-truth foi desenvolvida, sendo de grande importância para a área. Este trabalho contribuiu para o avanço do estado da arte das técnicas de segmentação de imagens de alta resolução, aprimorando e desenvolvendo métodos baseados na combinação de redes complexas com superpixels, os quais alcançaram resultados satisfatórios com baixo tempo de processamento. Além disso, uma importante contribuição referente ao censo demográfico de aves por meio da análise de imagens aéreas de ninhais foi viabilizada por meio da aplicação da técnica de segmentação MRF. / Segmentation is one of the most important steps in image analysis with a large range of applications. However, some traditional techniques exhibit high computational costs, hindering their application in high resolution images such as the images of birds nests from Pantanal, one of Brazilian most important wetlands. Therefore, we propose a new segmentation approach that combines community detection algorithms, originated from the theory of the complex networks, with superpixels extraction techniques. This approach is capable of segmenting high resolution images while maintaining the trade-off between accuracy and processing time. Moreover, as the nest images exhibit peculiar characteristics that can be better dealt with texture segmentation techniques, the Markov Random Fields (MRF) technique is proposed, as a complement to the initial approach, to perform the final identification of the birds. Finally, due to the importance of the quantitatively evaluation of the segmentation quality, a new evaluation metric based on ground-truth was developed, being of great importance to the segmentation field. This work contributed to the state of art of high resolution images segmentation techniques, improving and developing methods based on combination of complex networks and superpixels, which generated satisfactory results within low processing time. Moreover, an important contribution for the birds census by the analysis of aerial images of birds nests was made possible by application of the MRF technique.

Thesis (MScEng (Electrical and Electronic Engineering))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: In this thesis we present GrMPy, a library of classes and functions implemented in Python, designed for implementing graphical models. GrMPy supports both undirected and directed models, exact and approximate probabilistic inference, and parameter estimation from complete and incomplete data. In this thesis we outline the necessary theory required to understand the tools implemented within GrMPy as well as provide pseudo-code algorithms that illustrate how GrMPy is implemented. / AFRIKAANSE OPSOMMING: In hierdie verhandeling bied ons GrMPy aan,'n biblioteek van klasse en funksies wat Python geim- plimenteer word en ontwerp is vir die implimentering van grafiese modelle. GrMPy ondersteun beide gerigte en ongerigte modelle, presies eenbenaderde moontlike gevolgtrekkings en parameterskat- tings van volledige en onvolledige inligting. In hierdie verhandeling beskryf ons die nodige teorie wat benodig word om die hulpmiddels wat binne GrMPy geimplimenteer word te verstaan sowel as die pseudo-kodealgoritmes wat illustreer hoe GrMPy geimplimenteer is.

Nous présentons une approche de reconnaissance d'écriture manuscrite à partir de champs de Markov cachés et fondée sur une analyse entièrement bidimensionnelle de l'écriture. Son originalité réside dans la combinaison d'une analyse fenêtrée de l'image, d'une modélisation markovienne et dans la mise en oeuvre de la programmation dynamique 2D qui permet un décodage rapide et optimal des champs de Markov. Un aspect important de ces travaux est la méthodologie de développement employée qui est centrée sur l'évaluation systématique des apports algorithmiques et des paramètres utilisés. Ces algorithmes sont en partie empruntés aux techniques utilisées dans le domaine de la reconnaissance de la parole et sont très génériques.<br /><br />L'approche proposée est validée sur deux applications correspondant à des bases de données standard et librement disponibles. L'application de cette méthode extrêmement générique à une tâche de reconnaissance de chiffres manuscrits a permis d'obtenir des résultats comparables à ceux de l'état de l'art. L'application à une tâche de reconnaissance de mots manuscrits a permis de confirmer que l'extension de cette approche à des tâches plus complexes était naturelle.<br /><br />L'ensemble de cette recherche a démontré la validité de l'approche développée qui apparaît comme candidate au statut d'approche standard pour plusieurs problèmes de vision. En outre, elle ouvre la voie à de très nombreux développements concernant la tâche de traitement de l'écriture manuscrite et des améliorations significatives pourraient encore être apportées en recourant à d'autres principes issus du traitement de la parole et du langage. D'autres tâches comme la segmentation d'image devraient tirer avantage de la robustesse et de la faculté d'apprentissage de la modélisation que nous proposons.

The topic of Markov Random Fields (MRFs) has been well studied in the past, and has found practical use in various image processing, and machine learning applications. Where coding is concerned, MRF specific schemes have been largely unexplored. In this thesis, an overview is given of recent developments and challenges in the lossless coding of MRFs. Specifically, we concentrate on difficulties caused by computational intractability due to the partition function of the MRF. One proposed solution to this problem is to segment the MRF with a cutset, and encode the components separately. Using this method, arithmetic coding is possible via the Belief Propagation (BP) algorithm. We consider two cases of the BP algorithm: MRFs with only simple cliques, and MRFs with complex cliques. In the latter case, we study a minimum radius condition requirement for ensuring that all cliques are accounted for during coding. This condition also simplifies the process of conditioning on observed sites. Finally, using these results, we develop a systematic procedure of clustering and choosing cutsets. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2013-08-12 14:50:00.596

This thesis is devoted to the development of graph-based methods that address several of the most fundamental computer vision problems, such as segmentation, tracking, shape matching and 3D model inference. The first contribution of this thesis is a unified, single-shot optimization framework for simultaneous segmentation, depth ordering and multi-object tracking from monocular video sequences using a pairwise Markov Random Field (MRF). This is achieved through a novel 2.5D layered model where object-level and pixel-level representations are seamlessly combined through local constraints. Towards introducing high-level knowledge, such as shape priors, we then studied the problem of non-rigid 3D surface matching. The second contribution of this thesis consists of a higher-order graph matching formulation that encodes various measurements of geometric/appearance similarities and intrinsic deformation errors. As the third contribution of this thesis, higher-order interactions were further considered to build pose-invariant statistical shape priors and were exploited for the development of a novel approach for knowledge-based 3D segmentation in medical imaging which is invariant to the global pose and the initialization of the shape model. The last contribution of this thesis aimed to partially address the influence of camera pose in visual perception. To this end, we introduced a unified paradigm for 3D landmark model inference from monocular 2D images to simultaneously determine both the optimal 3D model and the corresponding 2D projections without explicit estimation of the camera viewpoint, which is also able to deal with misdetections/occlusions

Os modelos geoestatísticos bivariados denem funções aleatórias para dois processos estocásticos com localizações espaciais conhecidas. Pode-se adotar a suposição da existência de um campo aleatório gaussiano latente para cada variável aleatória. A suposição de gaussianidade do processo latente é conveniente para inferências sobre parâmetros do modelo e para obtenção de predições espaciais, uma vez que a distribuição de probabilidade conjunta para um conjunto de pontos do processo latente é também gaussiana. A matriz de covariância dessa distribuição deve ser positiva denida e possuir a estrutura de variabilidade espacial entre e dentre os atributos. Gelfand et al. (2004) e Diggle e Ribeiro Jr. (2007) propuseram estratégias para estruturar essa matriz, porém não existem muitos relatos sobre o uso e avaliações comparativas entre essas abordagens. Neste trabalho foi conduzido um estudo de simulação de modelos geoestatísticos bivariados em conjunto com estimação por máxima verossimilhança e krigagem ordinária, sob diferentes congurações amostrais de localizações espaciais. Também foram utilizados dados provenientes da análise de solo de uma propriedade agrícola com 51,8ha de área, onde foram amostradas 67 localizações georeferenciadas. Foram utilizados os valores mensurados de pH e da saturação por bases do solo, que foram submetidas à análise descritiva espacial, modelagens geoestatísticas univariadas, bivariadas e predições espaciais. Para vericar vantagens quanto à adoção de modelos univariados ou bivariados, a amostra da saturação por bases, que possui coleta mais dispendiosa, foi dividida em uma subamostra de modelagem e uma subamostra de controle. A primeira foi utilizada para fazer a modelagem geoestatística e a segunda foi utilizada para comparar as precisões das predições espaciais nas localizações omitidas no processo de modelagem. / Bivariate geostatistical models dene random functions for two stochastic processes with known spatial locations. Existence of a Gaussian random elds can be assumed for each latent random variable. This Gaussianity assumption for the latent process is a convenient one for the inferences on the model parameters and for spatial predictions once the joint distribution for a set of points is multivariate normal. The covariance matrix of this distribution should be positivede nite and to have the spatial variability structure between and among the attributes. Gelfand et al. (2004) and Diggle e Ribeiro Jr. (2007) suggested strategies for structuring this matrix, however there are few reports on comparing approaches. This work reports on a simulation study of bivariate models together with maximum likelihood estimators and spatial prediction under dierent sets of sampling locations space. Soil sample data from a eld with 51.8 hectares is also analyzed with the two soil attributes observed at 67 spatial locations. Data on pH and base saturation were submitted to spatial descriptive analysis, univariate and bivariate modeling and spatial prediction. To check for advantages of the adoption of univariate or bivariate models, the sample of the more expensive variable was divided into a modeling and testing subsamples. The rst was used to t geostatistical models, and the second was used to compare the spatial prediction precisions in the locations not used in the modeling process.