BACKGROUND: Establishment and maintenance of DNA methylation throughout the genome is an important epigenetic mechanism that regulates gene expression whose disruption has been implicated in human diseases like cancer. It is therefore crucial to know which genes, or other genomic features of interest, exhibit significant discordance in DNA methylation between two phenotypes. We have previously proposed an approach for ranking genes based on methylation discordance within their promoter regions, determined by centering a window of fixed size at their transcription start sites. However, we cannot use this method to identify statistically significant genomic features and handle features of variable length and with missing data. RESULTS: We present a new approach for computing the statistical significance of methylation discordance within genomic features of interest in single and multiple test/reference studies. We base the proposed method on a well-articulated hypothesis testing problem that produces p- and q-values for each genomic feature, which we then use to identify and rank features based on the statistical significance of their epigenetic dysregulation. We employ the information-theoretic concept of mutual information to derive a novel test statistic, which we can evaluate by computing Jensen-Shannon distances between the probability distributions of methylation in a test and a reference sample. We design the proposed methodology to simultaneously handle biological, statistical, and technical variability in the data, as well as variable feature lengths and missing data, thus enabling its wide-spread use on any list of genomic features. This is accomplished by estimating, from reference data, the null distribution of the test statistic as a function of feature length using generalized additive regression models. Differential assessment, using normal/cancer data from healthy fetal tissue and pediatric high-grade glioma patients, illustrates the potential of our approach to greatly facilitate the exploratory phases of clinically and biologically relevant methylation studies. CONCLUSIONS: The proposed approach provides the first computational tool for statistically testing and ranking genomic features of interest based on observed DNA methylation discordance in comparative studies that accounts, in a rigorous manner, for biological, statistical, and technical variability in methylation data, as well as for variability in feature length and for missing data.

BACKGROUND: DNA methylation is a stable form of epigenetic memory used by cells to control gene expression. Whole genome bisulfite sequencing (WGBS) has emerged as a gold-standard experimental technique for studying DNA methylation by producing high resolution genome-wide methylation profiles. Statistical modeling and analysis is employed to computationally extract and quantify information from these profiles in an effort to identify regions of the genome that demonstrate crucial or aberrant epigenetic behavior. However, the performance of most currently available methods for methylation analysis is hampered by their inability to directly account for statistical dependencies between neighboring methylation sites, thus ignoring significant information available in WGBS reads. RESULTS: We present a powerful information-theoretic approach for genome-wide modeling and analysis of WGBS data based on the 1D Ising model of statistical physics. This approach takes into account correlations in methylation by utilizing a joint probability model that encapsulates all information available in WGBS methylation reads and produces accurate results even when applied on single WGBS samples with low coverage. Using the Shannon entropy, our approach provides a rigorous quantification of methylation stochasticity in individual WGBS samples genome-wide. Furthermore, it utilizes the Jensen-Shannon distance to evaluate differences in methylation distributions between a test and a reference sample. Differential performance assessment using simulated and real human lung normal/cancer data demonstrate a clear superiority of our approach over DSS, a recently proposed method for WGBS data analysis. Critically, these results demonstrate that marginal methods become statistically invalid when correlations are present in the data. CONCLUSIONS: This contribution demonstrates clear benefits and the necessity of modeling joint probability distributions of methylation using the 1D Ising model of statistical physics and of quantifying methylation stochasticity using concepts from information theory. By employing this methodology, substantial improvement of DNA methylation analysis can be achieved by effectively taking into account the massive amount of statistical information available in WGBS data, which is largely ignored by existing methods.

The role intrinsic statistical fluctuations play in creating avalanches--patterns of complex bursting activity with scale-free properties--is examined in leaky Markovian networks. Using this broad class of models, we develop a probabilistic approach that employs a potential energy landscape perspective coupled with a macroscopic description based on statistical thermodynamics. We identify six important thermodynamic quantities essential for characterizing system behavior as a function of network size: the internal potential energy, entropy, free potential energy, internal pressure, pressure, and bulk modulus. In agreement with classical phase transitions, these quantities evolve smoothly as a function of the network size until a critical value is reached. At that value, a discontinuity in pressure is observed that leads to a spike in the bulk modulus demarcating loss of thermodynamic robustness. We attribute this novel result to a reallocation of the ground states (global minima) of the system's stationary potential energy landscape caused by a noise-induced deformation of its topographic surface. Further analysis demonstrates that appreciable levels of intrinsic noise can cause avalanching, a complex mode of operation that dominates system dynamics at near-critical or subcritical network sizes. Illustrative examples are provided using an epidemiological model of bacterial infection, where avalanching has not been characterized before, and a previously studied model of computational neuroscience, where avalanching was erroneously attributed to specific neural architectures. The general methods developed here can be used to study the emergence of avalanching (and other complex phenomena) in many biological, physical and man-made interaction networks.

Experimental construction of biochemical reaction systems that model cellular behavior often leads to kinetic parameter values that do not satisfy important thermodynamic constraints, thus resulting in models that are not physically realizable. In this paper, we propose a method that takes thermodynamically infeasible published kinetic parameter values and recomputes a new set of thermodynamically consistent values. The method is based on formulating and implementing an appropriate constrained optimization problem by assuming that the molecular dynamics produced by the published values are “noisy” versions of the corresponding dynamics produced by the thermodynamically consistent “true” values.

BACKGROUND: Estimating the rate constants of a biochemical reaction system with known stoichiometry from noisy time series measurements of molecular concentrations is an important step for building predictive models of cellular function. Inference techniques currently available in the literature may produce rate constant values that defy necessary constraints imposed by the fundamental laws of thermodynamics. As a result, these techniques may lead to biochemical reaction systems whose concentration dynamics could not possibly occur in nature. Therefore, development of a thermodynamically consistent approach for estimating the rate constants of a biochemical reaction system is highly desirable. RESULTS: We introduce a Bayesian analysis approach for computing thermodynamically consistent estimates of the rate constants of a closed biochemical reaction system with known stoichiometry given experimental data. Our method employs an appropriately designed prior probability density function that effectively integrates fundamental biophysical and thermodynamic knowledge into the inference problem. Moreover, it takes into account experimental strategies for collecting informative observations of molecular concentrations through perturbations. The proposed method employs a maximization-expectation-maximization algorithm that provides thermodynamically feasible estimates of the rate constant values and computes appropriate measures of estimation accuracy. We demonstrate various aspects of the proposed method on synthetic data obtained by simulating a subset of a well-known model of the EGF/ERK signaling pathway, and examine its robustness under conditions that violate key assumptions. Software, coded in MATLAB®, which implements all Bayesian analysis techniques discussed in this paper, is available free of charge at http://www.cis.jhu.edu/~goutsias/CSS%20lab/software.html. CONCLUSIONS: Our approach provides an attractive statistical methodology for estimating thermodynamically feasible values for the rate constants of a biochemical reaction system from noisy time series observations of molecular concentrations obtained through perturbations. The proposed technique is theoretically sound and computationally feasible, but restricted to quantitative data obtained from closed biochemical reaction systems. This necessitates development of similar techniques for estimating the rate constants of open biochemical reaction systems, which are more realistic models of cellular function.

BACKGROUND: Sensitivity analysis is an indispensable tool for the analysis of complex systems. In a recent paper, we have introduced a thermodynamically consistent variance-based sensitivity analysis approach for studying the robustness and fragility properties of biochemical reaction systems under uncertainty in the standard chemical potentials of the activated complexes of the reactions and the standard chemical potentials of the molecular species. In that approach, key sensitivity indices were estimated by Monte Carlo sampling, which is computationally very demanding and impractical for large biochemical reaction systems. Computationally efficient algorithms are needed to make variance-based sensitivity analysis applicable to realistic cellular networks, modeled by biochemical reaction systems that consist of a large number of reactions and molecular species. RESULTS: We present four techniques, derivative approximation (DA), polynomial approximation (PA), Gauss-Hermite integration (GHI), and orthonormal Hermite approximation (OHA), for analytically approximating the variance-based sensitivity indices associated with a biochemical reaction system. By using a well-known model of the mitogen-activated protein kinase signaling cascade as a case study, we numerically compare the approximation quality of these techniques against traditional Monte Carlo sampling. Our results indicate that, although DA is computationally the most attractive technique, special care should be exercised when using it for sensitivity analysis, since it may only be accurate at low levels of uncertainty. On the other hand, PA, GHI, and OHA are computationally more demanding than DA but can work well at high levels of uncertainty. GHI results in a slightly better accuracy than PA, but it is more difficult to implement. OHA produces the most accurate approximation results and can be implemented in a straightforward manner. It turns out that the computational cost of the four approximation techniques considered in this paper is orders of magnitude smaller than traditional Monte Carlo estimation. Software, coded in MATLAB, which implements all sensitivity analysis techniques discussed in this paper, is available free of charge. CONCLUSIONS: Estimating variance-based sensitivity indices of a large biochemical reaction system is a computationally challenging task that can only be addressed via approximations. Among the methods presented in this paper, a technique based on orthonormal Hermite polynomials seems to be an acceptable candidate for the job, producing very good approximation results for a wide range of uncertainty levels in a fraction of the time required by traditional Monte Carlo sampling.

We discuss several issues pertaining to the use of stochastic biochemical systems for modeling transcriptional regulation in single cells. By appropriately choosing the system state, we can model transcriptional regulation by a hidden Markov model (HMM). This opens the possibility of using well-known techniques for the statistical analysis and stochastic control of HMMs to mathematically and computationally study transcriptional regulation in single cells. Unfortunately, in all but a few simple cases, analytical characterization of the statistical behavior of the proposed HMM is not possible. Moreover, analysis by Monte Carlo simulation is computationally cumbersome. We discuss several techniques for approximating the HMM by one that is more tractable. We employ simulations, based on a biologically relevant transcriptional regulatory system, to show the relative merits and limitations of various approximation techniques and provide general guidelines for their use.

This paper introduces a novel approach for image analysis based on the notion of multiscale connectivity. We use the proposed approach to design several novel tools for object-based image representation and analysis which exploit the connectivity structure of images in a multiscale fashion. More specifically, we propose a nonlinear pyramidal image representation scheme, which decomposes an image at different scales by means of multiscale grain filters. These filters gradually remove connected components from an image that fail to satisfy a given criterion. We also use the concept of multiscale connectivity to design a hierarchical data partitioning tool. We employ this tool to construct another image representation scheme, based on the concept of component trees, which organizes partitions of an image in a hierarchical multiscale fashion. In addition, we propose a geometrically-oriented hierarchical clustering algorithm which generalizes the classical single-linkage algorithm. Finally, we propose two object-based multiscale image summaries, reminiscent of the well-known (morphological) pattern spectrum, which can be useful in image analysis and image understanding applications.

A novel notion of connectivity for grayscale images is introduced, defined by means of a binary connectivity assigned at image-level sets. In this framework, a grayscale image is connected if all level sets below a prespecified threshold are connected. The proposed notion is referred to as grayscale level connectivity and includes, as special cases, other well-known notions of grayscale connectivity, such as fuzzy grayscale connectivity and grayscale blobs. In contrast to those approaches, the present framework does not require all image-level sets to be connected. Moreover, a connected grayscale object may contain more than one regional maximum. Grayscale level connectivity is studied in the rigorous framework of connectivity classes. The use of grayscale level connectivity in image analysis applications, such as object extraction, image segmentation, object-based filtering, and hierarchical image representation, is discussed and illustrated.

An unsupervised iterative scheme is proposed for land mine detection in heavily cluttered scenes. This scheme is based on iterating hybrid multispectral filters that consist of a decorrelating linear transform coupled with a nonlinear morphological detector. Detections extracted from the first pass are used to improve results in subsequent iterations. The procedure stops after a predetermined number of iterations. The proposed scheme addresses several weaknesses associated with previous adaptations of morphological approaches to land mine detection. Improvement in detection performance, robustness with respect to clutter inhomogeneities, a completely unsupervised operation, and computational efficiency are the main highlights of the method. Experimental results reveal excellent performance.

The problem of parameter estimation for a binary Markov random field, from a given realization, is addressed. A strongly consistent estimator for the clique potentials, based on morphological erosions, is proposed. Experimental results demonstrate the effectiveness of the proposed approach.

Mathematical morphology is a geometric approach in image processing and analysis with a strong mathematical flavor. Originally, it was developed as a powerful tool for shape analysis in binary and, later, grey-scale images. But it was soon recognized

The authors consider the problem of estimating the parameters of a binary Markov random field from a given realization. They propose a consistent estimator of the clique potentials that can be implemented by means of morphological erosions. Experimental results demonstrate the effectiveness of the proposed approach.

Interest in multiresolution techniques for signal processing and analysis is increasing steadily. An important instance of such a technique is the so-called pyramid decomposition scheme. This paper presents a general theory for constructing linear as well as nonlinear pyramid decomposition schemes for signal analysis and synthesis. The proposed theory is based on the following ingredients: 1) the pyramid consists of a (finite or infinite) number of levels such that the information content decreases toward higher levels and 2) each step toward a higher level is implemented by an (information-reducing) analysis operator, whereas each step toward a lower level is implemented by an (information-preserving) synthesis operator. One basic assumption is necessary: synthesis followed by analysis yields the identity operator, meaning that no information is lost by these two consecutive steps. Several examples of pyramid decomposition schemes are shown to be instances of the proposed theory: a particular class of linear pyramids, morphological skeleton decompositions, the morphological Haar pyramid, median pyramids, etc. Furthermore, the paper makes a distinction between single-scale and multiscale decomposition schemes, i.e., schemes without or with sample reduction. Finally, the proposed theory provides the foundation of a general approach to constructing nonlinear wavelet decomposition schemes and filter banks.

For pt.I see ibid., vol.9, no.11, p.1862-76 (2000). In its original form, the wavelet transform is a linear tool. However, it has been increasingly recognized that nonlinear extensions are possible. A major impulse to the development of nonlinear wavelet transforms has been given by the introduction of the lifting scheme by Sweldens (1995, 1996, 1998). The aim of this paper, which is a sequel to a previous paper devoted exclusively to the pyramid transform, is to present an axiomatic framework encompassing most existing linear and nonlinear wavelet decompositions. Furthermore, it introduces some, thus far unknown, wavelets based on mathematical morphology, such as the morphological Haar wavelet, both in one and two dimensions. A general and flexible approach for the construction of nonlinear (morphological) wavelets is provided by the lifting scheme. This paper briefly discusses one example, the max-lifting scheme, which has the intriguing property that preserves local maxima in a signal over a range of scales, depending on how local or global these maxima are.

A new class of Gibbs random fields (GRFs) is proposed capable of modeling geometrical constraints in images by means of mathematical morphology. The proposed approach, known as morphologically constrained GRFs, models images by means of their size density. Since the size density is a multiresolution statistical summary, morphologically constrained GRFs explicitly incorporate multiresolution information into image modeling. Important properties are studied and their implication to texture synthesis and analysis is discussed. Statistical inference can be easily implemented by means of mathematical morphology. This allows the design of a computationally simple morphological Bayes classifier which produces excellent results in classifying natural textures.

The stochastic pyramid transform is a multiresolution structure that decomposes a random signal into a collection of random detail signals on a pyramid. The detail signals have a significantly simpler structure. It is however difficult to analytically calculate their probability distribution. In this paper, we propose a (vector quantization based) statistical inference technique that fits the detail signals to given data. An explicit dependence structure is introduced between each level of the pyramid and the coarse level immediately above it. The potential of this approach is illustrated with a simple example.

We have been developing general multiresolution signal decomposition schemes that unify traditional (linear) approaches and allow use of nonlinear filtering techniques in the decomposition. This paper summarizes our approach and provides several simple examples. Some of these examples are known in the literature (e.g., Haar pyramid and wavelet) and some of them are new (e.g., morphological Haar pyramid and wavelet).

We revisit the problem of non-linear image filtering by means of maximum-a-posteriori (MAP) estimation and mathematical morphology. Based on "mild" modeling assumptions, we bound the optimal MAP estimate from above and below and provide explicit morphological expressions for such bounds. The derived bounds can be easily calculated and effectively used to design a fast MAP algorithm.

We propose a class of Gibbs random fields which incorporate geometric information into stochastic image modeling by means of morphological constraints. This class is shown to be capable of modeling shapes with given morphological size density. Simulation examples illustrate some model properties.

We present new results on the problem of morphologically sampling binary images and image operators, thus enhancing the morphological sampling theory of Heijmans and Toet. These include sampling composite operators and approximating continuous translation invariant erosions, openings, and closings by discrete erosions, openings, and closings, respectively. The results presented in this paper have been already used in a theory of morphologically sampling random binary images modeled as random closed sets.

We present an analysis of previously proposed Monte Carlo algorithms for estimating the partition function of a Gibbs random field. We show that this problem reduces to estimating one or more expectations of suitable functionals of the Gibbs states with respect to properly chosen Gibbs distributions. As expected, the resulting estimators are consistent. Certain generalizations are also provided. We study computational complexity with respect to grid size and show that Monte Carlo partition function estimation algorithms can be classified into two categories: E-type algorithms that are of exponential complexity and P-type algorithms that are of polynomial complexity, Turing reducible to the problem of sampling from the Gibbs distribution. E-type algorithms require estimating a single expectation, whereas, P-type algorithms require estimating a number of expectations with respect to Gibbs distributions which are chosen to be sufficiently "close" to each other. In the latter case, the required number of expectations is of polynomial order with respect to grid size. We compare computational complexity by using both theoretical results and simulation experiments. We determine the most efficient E-type and P-type algorithms and conclude that P-type algorithms are more appropriate for partition function estimation. We finally suggest a practical and efficient P-type algorithm for this task.

We theoretically formulate the problem of processing continuous-space binary random fields by means of mathematical morphology. This may allow us to employ mathematical morphology to develop new statistical techniques for the analysis of binary random images. Since morphological transformations of continuous-space binary random fields are not measurable in general, we are naturally forced to employ intermediate steps that require generation of an equivalent random closed set. The relationship between continuous-space binary random fields and random closed sets is thoroughly investigated. As a byproduct of this investigation, a number of useful new results, regarding separability of random closed sets, are presented. Our plan, however, suffers from a few technical problems that are prominent in the continuous case. As an alternative, we suggest morphological discretization of binary random fields, random closed sets, and morphological operators, thereby effectively implementing our problem in the discrete domain.

Modeling image data by means of random fields and developing statistical techniques for the processing and analysis of these random fields is an important problem in image processing and analysis. We theoretically formulate the problem of processing binary random fields by means of mathematical morphology. This may allow us employ mathematical morphology in order to develop new statistical techniques for the processing and analysis of random shapes modeled as binary random fields. Since morphological transformations of continuous space binary random fields are not measurable in general, we employ intermediate steps which require generation of an equivalent random closed set. The relationship between binary random fields and random closed sets is thoroughly investigated. As a by-product of this investigation, a number of useful new results, regarding separability of random closed sets, are presented.

This paper presents a unifying approach to the problem of morphologically processing image sequences (or, equivalently, vector-valued images) by means of lattice theory, thus providing a mathematical foundation for vector morphology. Lattice theory is an abstract algebraic tool that has been extensively used as a theoretical framework for scalar morphology (i.e., mathematical morphology applied on single images). Two approaches to vector morphology are discussed. According to the first approach, vector morphology is viewed as a natural extension of the well-known scalar morphology. This approach formalizes and generalizes Wilson's matrix morphology and shows that the latter is a direct consequence of marginal vector ordering. The derivation of the second approach is more delicate and requires careful treatment. This approach is a direct consequence of a vector transformation followed by marginal ordering. When the vector transformation is the identity transformation, the two approaches are equivalent. A number of examples demonstrate the applicability of the proposed theory in a number of image processing and analysis problems.

Multiscale techniques require that signals are fitted to pyramid structures, with each level of the pyramid corresponding to a reduced-resolution approximation of the signal. Unlike deterministic pyramids, stochastic pyramids can be applied to signals characterized by some form of uncertainty. A number of fundamental properties of stochastic pyramids are studied, and advantages and disadvantages of various pyramid structures are discussed. Furthermore, the stochastic pyramid transform is proposed, as a solution to all problems associated with traditional stochastic pyramids. We briefly argue that this transform naturally leads to the multigrid Monte Carlo method, proposed by Goodman and Sokal (1989), which is mainly used to generate Markov random field images.>

We review and compare a number of linear and nonlinear pyramidal image decomposition techniques which are based on the approach proposed by Burt and Adelson (IEEE Trans. Comm. 31, 1983, 532-540). We argue that the design of a proper Burt-Adelson type pyramidal decomposition technique is directly related to the design of an optimal (nonlinear in general) image predictor. However, determining such a predictor is not possible in general. We propose four prediction constraints, which uniquely identify the "optimal" predictor as being a morphological opening. This choice naturally leads to one of the morphological image decomposition algorithms proposed by Heijmans and Toet (Comput. Vision Graphics Image Process. Image Understanding, 54, 1991, 384-400). By using an experimental analysis, based on a collection of four images with a broad spectrum of structural detail, we are able to study the behavior of six pyramidal image representation and compression techniques, and demonstrate the superiority (in terms of compression performance and computational simplicity) of the Heijmans-Toet algorithm.

A Monte Carlo simulation technique for estimating the partition function of a general Gibbs random field image is proposed. By expressing the partition function as an expectation, an importance sampling approach for estimating it using Monte Carlo simulations is developed. As expected, the resulting estimators are unbiased and consistent. Computations can be performed iteratively by using simple Monte Carlo algorithms with remarkable success, as demonstrated by simulations. The work concentrates on binary, second-order Gibbs random fields defined on a rectangular lattice. However, the proposed methods can be easily extended to more general Gibbs random fields. Their potential contribution to optimal parameter estimation and hypothesis testing problems for general Gibbs random field images using a likelihood approach is anticipated.>

The authors present a new Monte Carlo simulation technique for the estimation of the partition function of a general Markov random field (MRF), which results in unbiased, consistent and asymptotically efficient estimates. This technique gives extremely accurate results, as demonstrated by simulations. Use of more efficient algorithms can boost the performance and accuracy of the method, and yield more reliable estimates.>

We exploit the relationship between a general Gibbs random field and a mutually compatible Gibbs random field image, we investigate the possibility of approximating a general Gibbs random field by a mutually compatible Gibbs random field, and we study the consequences of such an approximation. This study is important, since, in some cases, various problems related to the modeling of images via Gibbs random fields may be simplified by restricting our interest to a special and convenient class of Gibbs random fields, the class of mutually compatible Gibbs random fields. A general analysis is presented, which results in some interesting conclusions about the desired relationship. We consider two approaches to the approximation problem. The first approach, which is more accurate, can be easily applied to the case of binary images. For nonbinary images this approach becomes cumbersome, since it requires the solution of a large system of nonlinear equations. The second approach, which is simpler but less accurate, is based on the direct relationship between the parameters of a general Gibbs random field and the parameters of a mutually compatible Gibbs random field. Simulation examples demonstrate various aspects of our analysis.

A theoretical analysis of morphological filters for the optimal restoration of noisy binary images is presented. The problem is formulated in a general form, and an optimal solution is obtained by using fundamental tools from mathematical morphology and decision theory. Consideration is given to the set-difference distance function as a measure of comparison between images. This function is used to introduce the mean-difference function as a quantitative measure of the degree of geometrical and topological distortion introduced by morphological filtering. It is proved that the class of alternating sequential filters is a set of parametric, smoothing morphological filters that best preserve the crucial structure of input images in the least-mean-difference sense.>

Various theoretical and computational issues about the algorithms' behavior are addressed. The concept of relative entropy is introduced as the primary analytical tool, and convergence of the simulation algorithms is discussed in terms of the relative entropy. This approach allows a view of the simulation of Gibbs random field images as a constrained, convex optimization problem, and it results in a systematic study of various Monte Carlo simulation algorithms under a common analytical framework. The problems of proper initialization, of maximizing the rate of convergence at each iteration, and of minimizing the rejection rate are discussed. A computational comparison of various Monte Carlo simulation algorithms is also presented.>

The performance of various matrix features in classifying synthetic and natural textures is compared by using the features directly in a maximum likelihood texture classifier. The matrix texture features examined are the spatial gray-level dependence matrix (SGLDM), the neighboring gray-level dependence matrix (NGLDM) and the neighboring spatial gray-level dependence matrix (NSGLDM). It is shown that, in general, for natural textures that are stochastic in nature, any of the texture features based on the NGLDM for distance (d) equal to 1 would be good choices as measures for texture classification. The parameter alpha should be chosen to maximize classification performance. For d=1, these measures require much fewer computations than the SGLDM with comparable performance. Also, the NGLDM-based measure require fewer computations for d=1 than for larger distances. For highly structured textures that may be characterized by large primitive elements, the NSGLDM can be used to extract texture information at larger distances while maintaining its relative computational efficiency.>

The relationship between a general Gibbs random field image and a mutually compatible Gibbs random field image is exploited. The possibility of approximating a general Gibbs random field by a mutually compatible Gibbs random field is investigated, and the consequences of such a representation are studied. It is shown that substantial computational savings can be obtained if a Monte Carlo algorithm is initialized, for the simulation of Gibbs random field images, with the resulting approximation. The fact that an efficient maximum-likelihood estimation procedure can be developed for the estimation of a general Gibbs random field, in the cases of reasonable unilateral approximation, is also demonstrated. Many problems related to the modeling of images with Gibbs random fields can be approximately solved by restricting interest to the class of mutually compatible Gibbs random fields.>

A general theory for the morphological representation of discrete and binary images is presented. Particular cases of the general scheme are shown to yield a number of useful image representations. The effect of noise degradation is studied. It is proven that, under certain assumptions, the general reduced morphological skeleton is the best morphological representation among a collection of invertible morphological image representations. This representation results in a minimal upper-bound on the average probability of error of reconstructing a binary image from its noisy representation.>

A general theory for the morphological representation of discrete and binary images is presented. The theory relies on the generation of a set of nonoverlapping segments of an image by repeated erosions and set transformations, which in turn produces a decomposition that guarantees exact reconstruction. The morphological image-representation transform and its properties are examined, with focus on the relationship between the transform and some existing shape-analysis tools, thus introducing the transform as the basis of a unified geometrical image analysis. Particular cases of the general representation scheme are shown to yield a number of useful image representations which are directly related to various forms of digital morphological skeletons. Also considered is the relationship between the transform and the various forms of morphological skeletons.>

The authors present the class of semi-Markov random fields and deal, in particular, with the subclass of discrete-valued, nonsymmetric half-plane, unilateral Markov random fields. A hierarchical nonstationary-mean nonstationary-variance (NMNV) image model is proposed for the modeling of nonstationary and noisy images. This model seems to be advantageous as compared to a regular NMNV model because it statistically incorporates the correlation between pixels around the boundary of two adjacent regions. The hierarchical NMNV model leads to the development of an optimal algorithm that allows the simultaneous segmentation and model estimation of measured images. Although no theoretical result is available for the consistency of the estimated model parameters, the method seems to work sufficiently well for the examples considered.>

A unified theory for the mathematical description of Gibbs random fields that answers some important theoretical and practical questions about their statistical behavior is presented. The local transfer function is introduced, and the joint probability measure of the general Gibbs random field is derived in terms of this function. The resulting probability structure is required to satisfy the property of mutual compatibility. A necessary and sufficient condition for a Gibbs random field to be mutually compatible is developed and used to prove that a mutually compatible Gibbs random field is a unilateral Markov random field. The existence of some special nontrivial cases of Gibbs random fields that are mutually compatible is demonstrated. Conditions on the translation invariance and isotropy of the general Gibbs random field with a free boundary are studied. The class of Gibbs random fields with a homogeneous local transfer function and the class of horizontally and vertically translation-invariant Gibbs random fields are introduced and treated. The concept of a translation-invariant Gibbs random field is also explored. The problem of the statistical inference of mutually compatible Gibbs random fields is discussed.>

The author presents two interesting discrete-valued random fields for the statistical modeling and analysis of random images. The first random field, the mutually compatible Gibbs random field, is a special nontrivial case of a general Gibbs random field, whereas the second random field, the semi-Markov random field is a non-Markovian generalization of a mutually compatible Gibbs random field.>

Presents a unified theory for the description of Gibbs images that allows one to answer some very important theoretical and practical questions about their statistical behavior. The author first introduces the local transfer function and derives the Gibbs measure in terms of this function. He restricts the derived probability structure to satisfy the property of mutual compatibility thus resulting in the subclass of mutually compatible Gibbs images. The author reviews their properties and briefly discusses various issues related to their simulation and identification. Simulation results from the area of texture analysis and synthesis are presented, in order to demonstrate various aspects of the theory.>

An optimal algorithm for the detection of noisy filtered discrete semi-Markov chains is presented. Estimation of the underlying model parameters is also considered. For a given path of the discrete semi-Markov chain the optimum estimates of the model parameters obtained by the maximum likelihood method are expressed as functions of the path. These functions are then used to derive a single maximum a posteriori criterion for the optimal detection of the unknown single path. The final optimization is carried out numerically by a combination of gradient, divide-and-conquer, and search techniques. This set of techniques is referred to as the integer most likely search detector. Experimental results, using synthetic data, demonstrate the potential of the algorithm.>

In this paper we examine the problem of image segmentation of noisy images. We consider a doubly stochastic image model. The image is assumed to be the sum of the realizations of two independent random fields: the uncorrupted image and the noise field, consisting of independent, identically distributed, Gaussian random variables. The image segmentation technique employed here is a technique in which the image is represented by a semi-Markov random field corrupted by additive white noise. An adaptive Bayesian parameter estimation/image detection algorithm is developed. This algorithm allows us to estimate the unknown image and its underlying parameters in an optimal manner. We demonstrate the potential of the proposed algorithm in the case of the smoothing/segmentation of two 4-gray level real images.

In this paper we present a one-dimensional normal-incidence inversion procedure for reflection seismic data. A lossless layered system is considered which is characterized by reflection coefficients and traveltimes. A priori knowledge for the unknown parameters, in the form of statistics, is incorporated into a nonuniform layered system, and a maximum a posteriori estimation procedure is used for the estimation of the system's unknown parameters (i.e., we assume a random reflector model) from noisy and band-limited data. Our solution to the inverse problem includes a downward continuation procedure for estimation of the states of the system. The state sequences are composed of overlapping wavelets. We show that estimation of the unknown parameters of a layer is equivalent to estimation of the amplitude and detection of the time delay of the first wavelet in the upgoing state sequence of the layer. A suboptimal maximum-likelihood deconvolution procedure is employed to perform estimation and detection. The most desirable features of the proposed algorithm are its layer-recursive structure and its ability to process noisy and band-limited data.

We derive and implement a maximum-likelihood detection and estimation algorithm based on the same channel and statistical models used by Kormylo and Mendel [1], that leads to less computations than the approach presented by Chi, Mendel and Hampson [2]. We introduce a single generalized likelihood function and we develop the Multiple-Most-Likely Replacement (MMLR) detector. This detector is computationally faster compared with the Single-Most-Likely Replacement (SMLR) detector developed by Kormylo and Mendel [3]. We demonstrate good performance of our algorithm for a synthetic data example.