Graphical model, the marriage between graph theory and probability theory, has been drawing increasing attention because of its many attractive features. In this paper, we consider the problem of learning the structure of graphical model based on observed data through a greedy forward-backward algorithm and with the use of learned model to classify the data into different categories. We establish the graphical model associated with a binary Ising Markov random field. And model selection is implemented by adding and deleting edges between nodes. Our experiments show that: compared with previous methods, the proposed algorithm has better performance in terms of correctness rate and model selection. / text

The art of reconstructing a real-world scene digitally has been on the mind of researchers for decades. Recently, it has attracted more and more attention from companies seeing a chance to bring this kind of technology to the market. Digital reconstruction of buildings in particular is a niche that has both potential and room for improvement. With this background, this thesis will present the design and evaluation of a pipeline made to find and correct approximately flat surfaces in architectural scenes. The scenes are 3D-reconstructed triangle meshes based on RGB images. The thesis will also comprise an evaluation of a few different components available for doing this, leading to a choice of best components. The goal is to improve the visual quality of the reconstruction. The final pipeline is designed with two blocks - one to detect initial plane seeds and one to refine the detected planes. The first block makes use of a multi-label energy formulation on the graph that describes the reconstructed surface. Penalties are assigned to each vertex and each edge of the graph based on the vertex labels, effectively describing a Markov Random Field. The energy is minimized with the help of the alpha-expansion algorithm. The second block uses heuristics for growing the detected plane seeds, merging similar planes together and extracting deviating details. Results on several scenes are presented, showing that the visual quality has been improved while maintaining accuracy compared with ground truth data. / Konsten att digitalt rekonstruera en verklig miljö har länge varit intressant för forskare. Nyligen har området även tilldragit sig mer och mer uppmärksamhet från företag som ser en möjlighet att föra den här typen av teknik till produkter på marknaden. I synnerhet är digital rekonstruktion av byggnader en nisch som har både stor potential och möjlighet till förbättring. Med denna bakgrund så presenterar detta examensarbete designen för och utvärderingen av en pipeline som skapats för att detektera och rätta till approximativt platta regioner i arkitektoniska miljöer. Miljöerna är 3D-rekonstruerade triangelmeshar skapade från RGB-bilder. Examensarbetet omfattar även utvärdering av olika komponenter för att uppnå detta, som avslutas med att de mest lämpliga komponenterna presenteras. Målet i korthet är att förbättra den visuella kvaliteten av en rekonstruerad modell. Den slutgiltiga pipelinen består av två övergripande block - ett för att detektera initiala plan och ett för att förbättra de funna planen. Det första blocket använder en multi-label energiformulering på grafen som beskriver den rekonstruerade ytan. Straffvärden tilldelas varje vertex och varje båge i grafen baserade på varje vertex label. På så sätt beskriver grafen ett Markov Random Field. Energin är sedan minimerad med alpha-expansion-algoritmen. Det andra blocket använder heuristiker för att låta planen växa, slå ihop närliggande plan och för att extrahera avvikande detaljer. Resultat på flera miljöer presenteras också för att påvisa att den visuella kvaliteten har förbättrats utan att rekonstruktionens noggrannhet har försämrats jämfört med ground truth-data.

This memo describes the initial results of a project to create a self-supervised algorithm for learning object segmentation from video data. Developmental psychology and computational experience have demonstrated that the motion segmentation of objects is a simpler, more primitive process than the detection of object boundaries by static image cues. Therefore, motion information provides a plausible supervision signal for learning the static boundary detection task and for evaluating performance on a test set. A video camera and previously developed background subtraction algorithms can automatically produce a large database of motion-segmented images for minimal cost. The purpose of this work is to use the information in such a database to learn how to detect the object boundaries in novel images using static information, such as color, texture, and shape. This work was funded in part by the Office of Naval Research contract #N00014-00-1-0298, in part by the Singapore-MIT Alliance agreement of 11/6/98, and in part by a National Science Foundation Graduate Student Fellowship.

Recent improvements in structural genomics efforts have greatly increased the number of hypothetical proteins in the Protein Data Bank. Several computational methodologies have been developed to determine the function of these proteins but none of these methods have been able to account successfully for the diversity in the sequence and structural conformations observed in proteins that have the same function. An additional complication is the flexibility in both the protein active site and the ligand. In this dissertation, novel approaches to deal with both the ligand flexibility and the diversity in stereochemistry have been proposed. The active site analysis problem is formalized as a classification problem in which, for a given test protein, the goal is to predict the class of ligand most likely to bind the active site based on its stereochemical nature and thereby define its function. Traditional methods that have adapted a similar methodology have struggled to account for the flexibility observed in large ligands. Therefore, I propose a novel fragment-based approach to dealing with larger ligands. The advantage of the fragment-based methodology is that considering the protein-ligand interactions in a piecewise manner does not affect the active site patterns, and it also provides for a way to account for the problems associated with flexible ligands. I also propose two feature-based methodologies to account for the diversity observed in sequences and structural conformations among proteins with the same function. The feature-based methodologies provide detailed descriptions of the active site stereochemistry and are capable of identifying stereochemical patterns within the active site despite the diversity. Finally, I propose a Markov Random Field approach to combine the individual ligand fragment classifications (based on the stereochemical descriptors) into a single multi-fragment ligand class. This probabilistic framework combines the information provided by stereochemical features with the information regarding geometric constraints between ligand fragments to make a final ligand class prediction. The feature-based fragment identification methodology had an accuracy of 84% across a diverse set of ligand fragments and the mrf analysis was able to succesfully combine the various ligand fragments (identified by feature-based analysis) into one final ligand based on statistical models of ligand fragment distances. This novel approach to protein active site analysis was additionally tested on 3 proteins with very low sequence and structural similarity to other proteins in the PDB (a challenge for traditional methods) and in each of these cases, this approach successfully identified the cognate ligand. This approach addresses the two main issues that affect the accuracy of current automated methodologies in protein function assignment.

This memo describes the initial results of a project to create aself-supervised algorithm for learning object segmentation from videodata. Developmental psychology and computational experience havedemonstrated that the motion segmentation of objects is a simpler,more primitive process than the detection of object boundaries bystatic image cues. Therefore, motion information provides a plausiblesupervision signal for learning the static boundary detection task andfor evaluating performance on a test set. A video camera andpreviously developed background subtraction algorithms canautomatically produce a large database of motion-segmented images forminimal cost. The purpose of this work is to use the information insuch a database to learn how to detect the object boundaries in novelimages using static information, such as color, texture, and shape.This work was funded in part by the Office of Naval Research contract#N00014-00-1-0298, in part by the Singapore-MIT Alliance agreement of11/6/98, and in part by a National Science Foundation Graduate StudentFellowship.

New view synthesis (NVS) is the problem of generating a novel image of a scene, given a set of calibrated input images of the scene, i.e. their viewpoints, and also that of the output image, are known. The problem is generally ill-posed---a large number of scenes can generate a given set of images, therefore there may be many equally likely (given the input data) output views. Some of these views will look less natural to a human observer than others, so prior knowledge of natural scenes is required to ensure that the result is visually plausible. The aim of this thesis is to compare and improve upon the various Markov random field} and conditional random field prior models, and their associated maximum a posteriori optimization frameworks, that are currently the state of the art for NVS and stereo (itself a means to NVS). A hierarchical example-based image prior is introduced which, when combined with a multi-resolution framework, accelerates inference by an order of magnitude, whilst also improving the quality of rendering. A parametric image prior is tested using a number of novel discrete optimization algorithms. This general prior is found to be less well suited to the NVS problem than sequence-specific priors, generating two forms of undesirable artifact, which are discussed. A novel pairwise clique image prior is developed, allowing inference using powerful optimizers. The prior is shown to perform better than a range of other pairwise image priors, distinguishing as it does between natural and artificial texture discontinuities. A dense stereo algorithm with geometrical occlusion model is converted to the task of NVS. In doing so, a number of challenges are novelly addressed; in particular, the new pairwise image prior is employed to align depth discontinuities with genuine texture edges in the output image. The resulting joint prior over smoothness and texture is shown to produce cutting edge rendering performance. Finally, a powerful new inference framework for stereo that allows the tractable optimization of second order smoothness priors is introduced. The second order priors are shown to improve reconstruction over first order priors in a number of situations.

The mapping of sea ice is an important task for understanding global climate and for safe shipping. Currently, sea ice maps are created by human analysts with the help of remote sensing imagery, including synthetic aperture radar (SAR) imagery. While the maps are generally correct, they can be somewhat subjective and do not have pixel-level resolution due to the time consuming nature of manual segmentation. Therefore, automated sea ice mapping algorithms such as the multivariate iterative region growing with semantics (MIRGS) sea ice image segmentation algorithm are needed. MIRGS was designed to work with one-channel single-polarization SAR imagery from the RADARSAT-1 satellite. The launch of RADARSAT-2 has made available two-channel dual-polarization SAR imagery for the purposes of sea ice mapping. Dual-polarization imagery provides more information for distinguishing ice types, and one of the channels is less sensitive to changes in the backscatter caused by the SAR incidence angle parameter. In the past, this change in backscatter due to the incidence angle was a key limitation that prevented automatic segmentation of full SAR scenes. This thesis investigates techniques to make use of the dual-polarization data in MIRGS. An evaluation of MIRGS with RADARSAT-2 data was performed and showed that some detail was lost and that the incidence angle caused errors in segmentation. Several data fusion schemes were investigated to determine if they can improve performance. Gradient generation methods designed to take advantage of dual-polarization data, feature space fusion using linear and non-linear transforms as well as image fusion methods based on wavelet combination rules were implemented and tested. Tuning of the MIRGS parameters was performed to find the best set of parameters for segmentation of dual-polarization data. Results show that the standard MIRGS algorithm with default parameters provides the highest accuracy, so no changes are necessary for dual-polarization data. A hierarchical segmentation scheme that segments the dual-polarization channels separately was implemented to overcome the incidence angle errors. The technique is effective but requires more user input than the standard MIRGS algorithm.

The mapping of sea ice is an important task for understanding global climate and for safe shipping. Currently, sea ice maps are created by human analysts with the help of remote sensing imagery, including synthetic aperture radar (SAR) imagery. While the maps are generally correct, they can be somewhat subjective and do not have pixel-level resolution due to the time consuming nature of manual segmentation. Therefore, automated sea ice mapping algorithms such as the multivariate iterative region growing with semantics (MIRGS) sea ice image segmentation algorithm are needed. MIRGS was designed to work with one-channel single-polarization SAR imagery from the RADARSAT-1 satellite. The launch of RADARSAT-2 has made available two-channel dual-polarization SAR imagery for the purposes of sea ice mapping. Dual-polarization imagery provides more information for distinguishing ice types, and one of the channels is less sensitive to changes in the backscatter caused by the SAR incidence angle parameter. In the past, this change in backscatter due to the incidence angle was a key limitation that prevented automatic segmentation of full SAR scenes. This thesis investigates techniques to make use of the dual-polarization data in MIRGS. An evaluation of MIRGS with RADARSAT-2 data was performed and showed that some detail was lost and that the incidence angle caused errors in segmentation. Several data fusion schemes were investigated to determine if they can improve performance. Gradient generation methods designed to take advantage of dual-polarization data, feature space fusion using linear and non-linear transforms as well as image fusion methods based on wavelet combination rules were implemented and tested. Tuning of the MIRGS parameters was performed to find the best set of parameters for segmentation of dual-polarization data. Results show that the standard MIRGS algorithm with default parameters provides the highest accuracy, so no changes are necessary for dual-polarization data. A hierarchical segmentation scheme that segments the dual-polarization channels separately was implemented to overcome the incidence angle errors. The technique is effective but requires more user input than the standard MIRGS algorithm.

Random heterogeneous, scale-dependent structures can be observed from many image sources, especially from remote sensing and scientific imaging. Examples include slices of porous media data showing pores of various sizes, and a remote sensing image including small and large sea-ice blocks. Meanwhile, rather than the images of phenomena themselves, there are many image processing and analysis problems requiring to deal with \emph{discrete-state} fields according to a labeled underlying property, such as mineral porosity extracted from microscope images, or an ice type map estimated from a sea-ice image. In many cases, if discrete-state problems are associated with heterogeneous, scale-dependent spatial structures, we will have to deal with complex discrete state fields. Although scale-dependent image modeling methods are common for continuous-state problems, models for discrete-state cases have not been well studied in the literature. Therefore, a fundamental difficulty will arise which is how to represent such complex discrete-state fields. Considering the success of hidden field methods in representing heterogenous behaviours and the capability of hierarchical field methods in modeling scale-dependent spatial features, we propose a Hidden Hierarchical Markov Field (HHMF) approach, which combines the idea of hierarchical fields with hidden fields, for dealing with the discrete field modeling challenge. However, to define a general HHMF modeling structure to cover all possible situations is difficult. In this research, we use two image application problems to describe the proposed modeling methods: one for scientific image (porous media image) reconstruction and the other for remote-sensing image synthesis. For modeling discrete-state fields with a spatially separable complex behaviour, such as porous media images with nonoverlapped heterogeneous pores, we propose a Parallel HHMF model, which can decomposes a complex behaviour into a set of separated, simple behaviours over scale, and then represents each of these with a hierarchical field. Alternatively, discrete fields with a highly heterogeneous behaviour, such as a sea-ice image with multiple types of ice at various scales, which are not spatially separable but arranged more as a partition tree, leads to the proposed Tree-Structured HHMF model. According to the proposed approach, a complex, multi-label field can be repeatedly partitioned into a set of binary/ternary fields, each of which can be further handled by a hierarchical field.

Images are liable to being corrupted by noise when they are processed for many applications such as sampling, storage and transmission. In this thesis, we propose a method of image restoration for image corrupted by a white Gaussian noise. This method is based upon Gauss-Markov random field model combined with a technique of image segmentation. As a result, the image can be restored by MAP estimation. In the approach of Gauss-Markov random field model, the image is restored by MAP estimation implemented by simulated annealing or deterministic search methods. By image segmentation, the region parameters and the power of generating noise can be obtained for every region. The above parameters are important for MAP estimation of the Gauss-Markov Random field model. As a summary, we first segment the image to find the important region parameters and then restore the image by MAP estimation with using the above region parameters. Finally, the intermediate image is restored again by the conventional Gauss-Markov random field model method. The advantage of our method is the clear edges by the first restoration and deblured images by the second restoration.