Random field models in image analysis

Image models are useful in quantitatively specifying natural constraints and general assumptions about the physical world and the imaging process. This review paper explains how Gibbs and Markov random field models provide a unifying theme for many contemporary problems in image analysis. Random field models permit the introduction of spatial context into pixel labeling problems, such as segmentation and restoration. Random field models also describe textured images and lead to algorithms for generating textured images, classifying textures, and segmenting textured images. In spite of some impressive model-based image restoration and texture segmentation results reported in the literature, a number of fundamental issues remain unexplored, such as the specification of MRF models, modeling noise processes, performance evaluation, parameter estimation, the phase transition phenomenon, and the comparative analysis of alternative procedures. The literature of random field models is filled with great promise, but a better mathematical understanding of these issues is needed as well as efficient algorithms for applications. These issues need to be resolved before random field models will be widely accepted as general tools in the image processing community.     

Random field models in image analysis*

Image models are useful in quantitatively specifying natural constraints and general assumptions about the physical world and the imaging process. This review paper explains how Gibbs and Markov random field models provide a unifying theme for many contemporary problems in image analysis. Random field models permit the introduction of spatial context into pixel labeling problems, such as segmentation and restoration. Random field models also describe textured images and lead to algorithms for generating textured images, classifying textures and segmenting textured images. In spite of some impressive model-based image restoration and texture segmentation results reported in the literature, a number of fundamental issues remain unexplored, such as the specification of MRF models, modeling noise processes, performance evaluation, parameter estimation, the phase transition phenomenon and the comparative analysis of alternative procedures. The literature of random field models is filled with great promise, but a better mathematical understanding of these issues is needed as well as efficient algorithms for applications. These issues need to be resolved before random field models will be widely accepted as general tools in the image-processing community.     

REVERSIBLE JUMP MARKOV CHAIN MONTE CARLO METHODS AND SEGMENTATION ALGORITHMS IN HIDDEN MARKOV MODELS

We consider hidden Markov models with an unknown number of regimes for the segmentation of the pixel intensities of digital images that consist of a small set of colours. New reversible jump Markov chain Monte Carlo algorithms to estimate both the dimension and the unknown parameters of the model are introduced. Parameters are updated by random walk Metropolis–Hastings moves, without updating the sequence of the hidden Markov chain. The segmentation (i.e. the estimation of the hidden regimes) is a further aim and is performed by means of a number of competing algorithms. We apply our Bayesian inference and segmentation tools to digital images, which are linearized through the Peano–Hilbert scan, and perform experiments and comparisons on both synthetic images and a real brain magnetic resonance image.     

Bayesian texture segmentation of weed and crop images using reversible jump Markov chain Monte Carlo methods

Summary. A Bayesian method for segmenting weed and crop textures is described and implemented. The work forms part of a project to identify weeds and crops in images so that selective crop spraying can be carried out. An image is subdivided into blocks and each block is modelled as a single texture. The number of different textures in the image is assumed unknown. A hierarchical Bayesian procedure is used where the texture labels have a Potts model (colour Ising Markov random field) prior and the pixels within a block are distributed according to a Gaussian Markov random field, with the parameters dependent on the type of texture. We simulate from the posterior distribution by using a reversible jump Metropolis–Hastings algorithm, where the number of different texture components is allowed to vary. The methodology is applied to a simulated image and then we carry out texture segmentation on the weed and crop images that motivated the work.     

The double chain markov model

In the class of discrete time Markovian processes, two models are widely used, the Markov chain and the hidden Markov model. A major difference between these two models lies in the relation between successive outputs of the observed variable. In a visible Markov chain, these are directly correlated while in hidden models they are not. However, in some situations it is possible to observe both a hidden Markov chain and a direct relation between successive observed outputs. Unfortunately, the use of either a visible or a hidden model implies the suppression of one of these hypothesis. This paper prsents a Markovian model under random environment called the Double Chain Markov Model which takes into account the maijn features of both visible and hidden models. Its main purpose is the modeling of non-homogeneous time-series. It is very flexible and can be estimated with traditional methods. The model is applied on a sequence of wind speeds and it appears to model data more successfully than both the usual Markov chains and hidden Markov models.     

Markov Random Fields with Higher-order Interactions

Discrete-state Markov random fields on regular arrays have played a significant role in spatial statistics and image analysis. For example, they are used to represent objects against background in computer vision and pixel-based classification of a region into different crop types in remote sensing. Convenience has generally favoured formulations that involve only pairwise interactions. Such models are in themselves unrealistic and, although they often perform surprisingly well in tasks such as the restoration of degraded images, they are unsatisfactory for many other purposes. In this paper, we consider particular forms of Markov random fields that involve higher-order interactions and therefore are better able to represent the large-scale properties of typical spatial scenes. Interpretations of the parameters are given and realizations from a variety of models are produced via Markov chain Monte Carlo. Potential applications are illustrated in two examples. The first concerns Bayesian image analysis and confirms that pairwise-interaction priors may perform very poorly for image functionals such as number of objects, even when restoration apparently works well. The second example describes a model for a geological dataset and obtains maximum-likelihood parameter estimates using Markov chain Monte Carlo. Despite the complexity of the formulation, realizations of the estimated model suggest that the representation is quite realistic.     

Disagreement Loop and Path Creation/Annihilation Algorithms for Binary Planar Markov Fields with Applications to Image Segmentation

Abstract. We introduce a class of Gibbs–Markov random fields built on regular tessellations that can be understood as discrete counterparts of Arak–Surgailis polygonal fields. We focus first on consistent polygonal fields, for which we show consistency, Markovianity and solvability by means of dynamic representations. Next, we develop disagreement loop as well as path creation and annihilation dynamics for their general Gibbsian modifications, which cover most lattice‐based Gibbs–Markov random fields subject to certain mild conditions. Applications to foreground–background image segmentation problems are discussed.     

Spatial hidden Markov models and species distributions

A spatial hidden Markov model (SHMM) is introduced to analyse the distribution of a species on an atlas, taking into account that false observations and false non-detections of the species can occur during the survey, blurring the true map of presence and absence of the species. The reconstruction of the true map is tackled as the restoration of a degraded pixel image, where the true map is an autologistic model, hidden behind the observed map, whose normalizing constant is efficiently computed by simulating an auxiliary map. The distribution of the species is explained under the Bayesian paradigm and Markov chain Monte Carlo (MCMC) algorithms are developed. We are interested in the spatial distribution of the bird species Greywing Francolin in the south of Africa. Many climatic and land-use explanatory variables are also available: they are included in the SHMM and a subset of them is selected by the mutation operators within the MCMC algorithm.     

Variational Bayes for estimating the parameters of a hidden Potts model

Hidden Markov random field models provide an appealing representation of images and other spatial problems. The drawback is that inference is not straightforward for these models as the normalisation constant for the likelihood is generally intractable except for very small observation sets. Variational methods are an emerging tool for Bayesian inference and they have already been successfully applied in other contexts. Focusing on the particular case of a hidden Potts model with Gaussian noise, we show how variational Bayesian methods can be applied to hidden Markov random field inference. To tackle the obstacle of the intractable normalising constant for the likelihood, we explore alternative estimation approaches for incorporation into the variational Bayes algorithm. We consider a pseudo-likelihood approach as well as the more recent reduced dependence approximation of the normalisation constant. To illustrate the effectiveness of these approaches we present empirical results from the analysis of simulated datasets. We also analyse a real dataset and compare results with those of previous analyses as well as those obtained from the recently developed auxiliary variable MCMC method and the recursive MCMC method. Our results show that the variational Bayesian analyses can be carried out much faster than the MCMC analyses and produce good estimates of model parameters. We also found that the reduced dependence approximation of the normalisation constant outperformed the pseudo-likelihood approximation in our analysis of real and synthetic datasets.     

Bayesian analysis of dynamic magnetic resonance breast images

Summary.  We describe an integrated methodology for analysing dynamic magnetic resonance images of the breast. The problems that motivate this methodology arise from a collaborative study with a tumour institute. The methods are developed within the Bayesian framework and comprise image restoration and classification steps. Two different approaches are proposed for the restoration. Bayesian inference is performed by means of Markov chain Monte Carlo algorithms. We make use of a Metropolis algorithm with a specially chosen proposal distribution that performs better than more commonly used proposals. The classification step is based on a few attribute images yielded by the restoration step that describe the essential features of the contrast agent variation over time. Procedures for hyperparameter estimation are provided, so making our method automatic. The results show the potential of the methodology to extract useful information from acquired dynamic magnetic resonance imaging data about tumour morphology and internal pathophysiological features.     

Nonparametric Bayesian analysis for multi-site hidden Markov model

The hidden Markov model (HMM) provides an attractive framework for modeling long-term persistence in a variety of applications including pattern recognition. Unlike typical mixture models, hidden Markov states can represent the heterogeneity in data and it can be extended to a multivariate case using a hierarchical Bayesian approach. This article provides a nonparametric Bayesian modeling approach to the multi-site HMM by considering stick-breaking priors for each row of an infinite state transition matrix. This extension has many advantages over a parametric HMM. For example, it can provide more flexible information for identifying the structure of the HMM than parametric HMM analysis, such as the number of states in HMM. We exploit a simulation example and a real dataset to evaluate the proposed approach.     

A Bayesian HMM with random effects and an unknown number of states for DNA copy number analysis

Hidden Markov models (HMMs) have been shown to be a flexible tool for modelling complex biological processes. However, choosing the number of hidden states remains an open question and the inclusion of random effects also deserves more research, as it is a recent addition to the fixed-effect HMM in many application fields. We present a Bayesian mixed HMM with an unknown number of hidden states and fixed covariates. The model is fitted using reversible-jump Markov chain Monte Carlo, avoiding the need to select the number of hidden states. We show through simulations that the estimations produced are more precise than those from a fixed-effect HMM and illustrate its practical application to the analysis of DNA copy number data, a field where HMMs are widely used.     

Performance of Robust RA Estimator for Bidimensional Autoregressive Models

The additive AR-2D model has been successfully related to the modeling of satelital images both optic and of radar of synthetic opening. Having in mind the errors that are produced in the process of captation and quantification of the image, an interesting subject, is the robust estimation of the parameters in this model. Besides the robust methods in image models are also applied in some important image processing situations such as segmentation by texture and image restoration in the presence of outliers. This paper is concerned with the development and performance of the robust RA estimator proposed by Ojeda (1998) for the estimation of parameters in contaminated AR-2D models. Here, we implement this estimator and we show by simulation study that it has a better performance than the classic least square estimator and the robust M and GM estimators in an additive outlier contaminated image model.     

Approximate computations for binary Markov random fields and their use in Bayesian models

Discrete Markov random fields form a natural class of models to represent images and spatial datasets. The use of such models is, however, hampered by a computationally intractable normalising constant. This makes parameter estimation and a fully Bayesian treatment of discrete Markov random fields difficult. We apply approximation theory for pseudo-Boolean functions to binary Markov random fields and construct approximations and upper and lower bounds for the associated computationally intractable normalising constant. As a by-product of this process we also get a partially ordered Markov model approximation of the binary Markov random field. We present numerical examples with both the pairwise interaction Ising model and with higher-order interaction models, showing the quality of our approximations and bounds. We also present simulation examples and one real data example demonstrating how the approximations and bounds can be applied for parameter estimation and to handle a fully Bayesian model computationally.     

Experiments with maximum likelihood method for image motion deblurring

Relative motion between the camera and the object results in the recording of a motion-blurred image. Under certain idealized conditions, such blurring can be mathematically corrected. We refer to this as ‘motion deblurring’. We start with some idealized assumptions under which the motion deblurring problem is a linear inverse problem with certain positivity constraints; LININPOS problems, for short. Such problems, even in the case of no statistical noise, can be solved using the maximum likelihood/EM approach in the following sense. If they have a solution, the ML/EM iterative method will converge to it; otherwise, it will converge to the nearest approximation of a solution, where ‘nearest’ is interpreted in a likelihood sense or, equivalently, in a Kullback-Leibler information divergence sense. We apply the ML/EM algorithm to such problems and discuss certain special cases, such as motion along linear or circular paths with or without acceleration. The idealized assumptions under which the method is developed are hardly ever satisfied in real applications, so we experiment with the method under conditions that violate these assumptions. Specifically, we experimented with an image created through a computer-simulated digital motion blurring corrupted with noise, and with an image of a moving toy cart recorded with a 35 mm camera while in motion. The gross violations of the idealized assumptions, especially in the toy cart example, led to a host of very difficult problems which always occur under real-life conditions and need to be addressed. We discuss these problems in detail and propose some ‘engineering solutions' that, when put together, appear to lead to a good methodology for certain motion deblurring problems. Some of the issues we discuss, in various degrees of detail, include estimating the speed of motion which is referred to as ‘blur identification’; non-zero-background artefacts and pre- and post- processing of the images to remove such artefacts; the need to ‘stabilize’ the solution because of the inherent ill-posedness of the problem; and computer implemetation.     

Semiparametric hidden Markov model with non-parametric regression

The hidden Markov model regression (HMMR) has been popularly used in many fields such as gene expression and activity recognition. However, the traditional HMMR requires the strong linearity assumption for the emission model. In this article, we propose a hidden Markov model with non-parametric regression (HMM-NR), where the mean and variance of emission model are unknown smooth functions. The new semiparametric model might greatly reduce the modeling bias and thus enhance the applicability of the traditional hidden Markov model regression. We propose an estimation procedure for the transition probability matrix and the non-parametric mean and variance functions by combining the ideas of the EM algorithm and the kernel regression. Simulation studies and a real data set application are used to demonstrate the effectiveness of the new estimation procedure.     

Experiments with maximum likelihood method for image motion deblurring

Relative motion between the camera and the object results in the recording of a motion-blurred image. Under certain idealized conditions, such blurring can be mathematically corrected. We refer to this as 'motion deblurring'. We start with some idealized assumptions under which the motion deblurring problem is a linear inverse problem with certain positivity constraints; LININPOS problems, for short. Such problems, even in the case of no statistical noise, can be solved using the maximum likelihood/EM approach in the following sense. If they have a solution, the ML/EM iterative method will converge to it; otherwise, it will converge to the nearest approximation of a solution, where 'nearest' is interpreted in a likelihood sense or, equivalently, in a Kullback-Leibler information divergence sense. We apply the ML/EM algorithm to such problems and discuss certain special cases, such as motion along linear or circular paths with or without acceleration. The idealized assumptions under which the method is developed are hardly ever satisfied in real applications, so we experiment with the method under conditions that violate these assumptions. Specifically, we experimented with an image created through a computer-simulated digital motion blurring corrupted with noise, and with an image of a moving toy cart recorded with a 35 mm camera while in motion. The gross violations of the idealized assumptions, especially in the toy cart example, led to a host of very difficult problems which always occur under real-life conditions and need to be addressed. We discuss these problems in detail and propose some 'engineering solutions' that, when put together, appear to lead to a good methodology for certain motion deblurring problems. Some of the issues we discuss, in various degrees of detail, include estimating the speed of motion which is referred to as 'blur identification'; non-zero-background artefacts and pre- and post- processing of the images to remove such artefacts; the need to 'stabilize' the solution because of the inherent ill-posedness of the problem; and computer implemetation.     

On the use of quasi-likelihood for estimation in hidden-Markov random fields

This paper illustrates the use of quasi-likelihood methods of inference for hidden Markov random fields. These are simple to use and can be employed under circumstances where only the model form and its covariance structure are specified. In particular they can be used to derive the same estimating equations as the E-M algorithm or change of measure methods, which make full distributional assumptions.     

Image segmentation using voronoi polygons and MCMC, with application to muscle fibre images

We investigate a Bayesian method for the segmentation of muscle fibre images. The images are reasonably well approximated by a Dirichlet tessellation, and so we use a deformable template model based on Voronoi polygons to represent the segmented image. We consider various prior distributions for the parameters and suggest an appropriate likelihood. Following the Bayesian paradigm, the mathematical form for the posterior distribution is obtained (up to an integrating constant). We introduce a Metropolis-Hastings algorithm and a reversible jump Markov chain Monte Carlo algorithm (RJMCMC) for simulation from the posterior when the number of polygons is fixed or unknown. The particular moves in the RJMCMC algorithm are birth, death and position/colour changes of the point process which determines the location of the polygons. Segmentation of the true image was carried out using the estimated posterior mode and posterior mean. A simulation study is presented which is helpful for tuning the hyperparameters and to assess the accuracy. The algorithms work well on a real image of a muscle fibre cross-section image, and an additional parameter, which models the boundaries of the muscle fibres, is included in the final model.     

A Loss Function Model for the Restoration of Grey Level Images

Common loss functions used for the restoration of grey scale images include the zero–one loss and the sum of squared errors. The corresponding estimators, the posterior mode and the posterior marginal mean, are optimal Bayes estimators with respect to their way of measuring the loss for different error configurations. However, both these loss functions have a fundamental weakness: the loss does not depend on the spatial structure of the errors. This is important because a systematic structure in the errors can lead to misinterpretation of the estimated image. We propose a new loss function that also penalizes strong local sample covariance in the error and we discuss how the optimal Bayes estimator can be estimated using a two-step Markov chain Monte Carlo and simulated annealing algorithm. We present simulation results for some artificial data which show improvement with respect to small structures in the image.