An analytical and experimental study of the performance of Markovrandom fields applied to textured images using small samples

We investigate to what extent textures can be distinguished using conditional Markov fields and small samples. We establish that the least square (LS) estimator is the only reasonable choice for this task, and we prove its asymptotic consistency and normality for a general class of random fields that includes Gaussian Markov fields as a special case. The performance of this estimator when applied to textured images of real surfaces is poor if small boxes are used (20x20 or less). We investigate the nature of this problem by comparing the behavior predicted by the rigorous theory to the one that has been experimentally observed. Our analysis reveals that 20x20 samples contain enough information to distinguish between the textures in our experiments and that the poor performance mentioned above should be attributed to the fact that conditional Markov fields do not provide accurate models for textured images of many real surfaces. A more general model that exploits more efficiently the information contained in small samples is also suggested.     

Discrete Markov image modeling and inference on the quadtree

Noncasual Markov (or energy-based) models are widely used in early vision applications for the representation of images in high-dimensional inverse problems. Due to their noncausal nature, these models generally lead to iterative inference algorithms that are computationally demanding. In this paper, we consider a special class of nonlinear Markov models which allow one to circumvent this drawback. These models are defined as discrete Markov random fields (MRF) attached to the nodes of a quadtree. The quadtree induces causality properties which enable the design of exact, noniterative inference algorithms, similar to those used in the context of Markov chain models. We first introduce an extension of the Viterbi algorithm which enables exact maximum a posteriori (MAP) estimation on the quadtree. Two other algorithms, related to the MPM criterion and to Bouman and Shapiro's (1994) sequential-MAP (SMAP) estimator are derived on the same hierarchical structure. The estimation of the model hyper parameters is also addressed. Two expectation-maximization (EM)-type algorithms, allowing unsupervised inference with these models are defined. The practical relevance of the different models and inference algorithms is investigated in the context of image classification problem, on both synthetic and natural images.     

基于时空马尔可夫随机场的运动目标分割技术

复杂场景下的运动目标分割技术是近年来多媒体通信技术研究的热点之一。文中提出一种基于时空马尔可地随机场模型的运动目标分割技术。首先建立运动序列图像的时空马尔可夫随机场模型并且构造其相应的能量耗费函数,通过模型可以提出期望的空间属性。然后利用迭代条件模型（ＩＣＭ）算法实现最大后验概率（ＭＡＰ）估算问题。最后利用形态滤波的方法对分割结果进行修正。模拟实验结果证明,该方法能够有效地抑制图像的噪声,对于运动     

An improvement to the interacting multiple model (IMM) algorithm

Computing the optimal conditional mean state estimate for a jump Markov linear system requires exponential complexity, and hence, practical filtering algorithms are necessarily suboptimal. In the target tracking literature, suboptimal multiple-model filtering algorithms, such as the interacting multiple model (IMM) method and generalized pseudo-Bayesian (GPB) schemes, are widely used for state estimation of such systems. We derive a reweighted interacting multiple model algorithm. Although the IMM algorithm is an approximation of the conditional mean state estimator, our algorithm is a recursive implementation of a maximum a posteriori (MAP) state sequence estimator. This MAP estimator is an instance of a previous version of the EM algorithm known as the alternating expectation conditional maximization (AECM) algorithm. Computer simulations indicate that the proposed reweighted IMM algorithm is a competitive alternative to the popular IMM algorithm and GPB methods     

Minimax nonparametric classification. II. Model selection foradaptation

For pt.I see ibid., vol.45, no.7, p.2271-84 (1999). We study nonparametric estimation of a conditional probability for classification based on a collection of finite-dimensional models. For the sake of flexibility, different types of models, linear or nonlinear, are allowed as long as each satisfies a dimensionality assumption. We show that with a suitable model selection criterion, the penalized maximum-likelihood estimator has a risk bounded by an index of resolvability expressing a good tradeoff among approximation error, estimation error, and model complexity. The bound does not require any assumption on the target conditional probability and can be used to demonstrate the adaptivity of estimators based on model selection. Examples are given with both splines and neural nets, and problems of high-dimensional estimation are considered. The resulting adaptive estimator is shown to behave optimally or near optimally over Sobolev classes (with unknown orders of interaction and smoothness) and classes of integrable Fourier transform of gradient. In terms of rates of convergence, the performance is the same as if one knew which of them contains the true conditional probability in advance. The corresponding classifier also converges optimally or nearly optimally simultaneously over these classes     

Discrete-index Markov-type random processes

Discrete-index Markov-type random processes in one and two dimensions are considered, with emphasis on two-dimensional processes (or fields). Important classes of Markov-type models, their properties, and their relationship are described. Although some new results are given, the authors mainly present a systematic study and grouping of processes according to two fundamental Markov-type properties: strict-sense Markov, defined in terms of conditional probabilities, and wide-sense Markov, defined in terms of linear minimum-mean-square error estimates. Classes of models having special cases of the fundamental properties, including many models which are widely used to represent images are obtained by specifying the index set, the conditioning set used to define the Markov property, and the process distribution. The relationships between unilateral and bilateral models in each class are carefully investigated. Particular attention is given to simultaneous autoregressive models which are shown to be both strict-sense and wide-sense Markov. Classification of processes according to their Markov-type properties helps to clarify the consequences of and relationships between different model assumptions     

Simulation Model of Mission Effectiveness for Military Systems

Mission effectiveness, the probability of successfully accomplishing the mission, is a practical measure of a unit's usefulness. Each unit has 2 s-independent components (hardware and operator) in series. Mission effectiveness for a particular sortie and unit is determined by finding the joint probability measure of the following 4 factors: the availability of the unit at the beginning of a sortie; the sortie-reliability of the unit; the conditional probability of successful performance of the unit in a given environment; and the conditional probability of the successful operator performance during a sortie as a function of time since last retraining. A computer simulation model is developed. It is more general and practical than Markov models, since the simulation model can directly handle any empirical probability distributions for the random variables whereas the Markov approach is limited to the exponential distribution. The simulation model appears to be a semi-Markov model where each transition is a regeneration point.     

A Bayesian estimation approach for speech enhancement using hiddenMarkov models

A Bayesian estimation approach for enhancing speech signals which have been degraded by statistically independent additive noise is motivated and developed. In particular, minimum mean square error (MMSE) and maximum a posteriori (MAP) signal estimators are developed using hidden Markov models (HMMs) for the clean signal and the noise process. It is shown that the MMSE estimator comprises a weighted sum of conditional mean estimators for the composite states of the noisy signal, where the weights equal the posterior probabilities of the composite states given the noisy signal. The estimation of several spectral functionals of the clean signal such as the sample spectrum and the complex exponential of the phase is also considered. A gain-adapted MAP estimator is developed using the expectation-maximization algorithm. The theoretical performance of the MMSE estimator is discussed, and convergence of the MAP estimator is proved. Both the MMSE and MAP estimators are tested in enhancing speech signals degraded by white Gaussian noise at input signal-to-noise ratios of from 5 to 20 dB     

Expectation maximization algorithms for MAP estimation of jumpMarkov linear systems

In a jump Markov linear system, the state matrix, observation matrix, and the noise covariance matrices evolve according to the realization of a finite state Markov chain. Given a realization of the observation process, the aim is to estimate the state of the Markov chain assuming known model parameters. Computing conditional mean estimates is infeasible as it involves a cost that grows exponentially with the number of observations. We present three expectation maximization (EM) algorithms for state estimation to compute maximum a posteriori (MAP) state sequence estimates [which are also known as Bayesian maximum likelihood state sequence estimates (MLSEs)]. The first EM algorithm yields the MAP estimate for the entire sequence of the finite state Markov chain. The second EM algorithm yields the MAP estimate of the (continuous) state of the jump linear system. The third EM algorithm computes the joint MAP estimate of the finite and continuous states. The three EM algorithms optimally combine a hidden Markov model (HMM) estimator and a Kalman smoother (KS) in three different ways to compute the desired MAP state sequence estimates. Unlike the conditional mean state estimates, which require computational cost exponential in the data length, the proposed iterative schemes are linear in the data length     

CRFNet: Context ReFinement Network used for semantic segmentation

Recent semantic segmentation frameworks usually combine low-level and high-level context information to achieve improved performance. In addition, postlevel context information is also considered. In this study, we present a Context ReFinement Network (CRFNet) and its training method to improve the semantic predictions of segmentation models of the encoder–decoder structure. Our study is based on postprocessing, which directly considers the relationship between spatially neighboring pixels of a label map, such as Markov and conditional random fields. CRFNet comprises two modules: a refiner and a combiner that, respectively, refine the context information from the output features of the conventional semantic segmentation network model and combine the refined features with the intermediate features from the decoding process of the segmentation model to produce the final output. To train CRFNet to refine the semantic predictions more accurately, we proposed a sequential training scheme. Using various backbone networks (ENet, ERFNet, and HyperSeg), we extensively evaluated our model on three large-scale, real-world datasets to demonstrate the effectiveness of our approach.     

Multiresolution Gauss-Markov random field models for texturesegmentation

This paper presents multiresolution models for Gauss-Markov random fields (GMRFs) with applications to texture segmentation. Coarser resolution sample fields are obtained by subsampling the sample field at fine resolution. Although the Markov property is lost under such resolution transformation, coarse resolution non-Markov random fields can be effectively approximated by Markov fields. We present two techniques to estimate the GMRF parameters at coarser resolutions from the fine resolution parameters, one by minimizing the Kullback-Leibler distance and another based on local conditional distribution invariance. We also allude to the fact that different GMRF parameters at the fine resolution can result in the same probability measure after subsampling and present the results for first- and second-order cases. We apply this multiresolution model to texture segmentation. Different texture regions in an image are modeled by GMRFs and the associated parameters are assumed to be known. Parameters at lower resolutions are estimated from the fine resolution parameters. The coarsest resolution data is first segmented and the segmentation results are propagated upward to the finer resolution. We use the iterated conditional mode (ICM) minimization at all resolutions. Our experiments with synthetic, Brodatz texture, and real satellite images show that the multiresolution technique results in a better segmentation and requires lesser computation than the single resolution algorithm.     

Convergence of the maximum a posteriori path estimator in hiddenMarkov models

In a hidden Markov model (HMM) the underlying finite-state Markov chain cannot be observed directly but only by an additional process. We are interested in estimating the unknown path of the Markov chain. The most widely used estimator is the maximum a posteriori path estimator (MAP path estimator). It can be calculated effectively by the Viterbi (1967) algorithm as is, e.g., frequently done in the field of coding theory, correction of intersymbol interference, and speech recognition. We investigate (component-wise) convergence of the MAP path estimator. Convergence is shown under the condition of unbounded likelihood ratios. This condition is satisfied in the important case of HMMs with additive white Gaussian noise. We also prove convergence, if the Markov chain has two states. The so-called Viterbi paths are an important tool for obtaining these results     

Markov Random Fields with Asymmetric Interactions for Modelling Spatial Context in Structured Scene Labelling

In this paper we propose a Markov random field with asymmetric Markov parameters to model the spatial and topological relationships between objects in structured scenes. The field is formulated in terms of conditional probabilities learnt from a set of training images. A locally consistent labelling of new scenes is achieved by relaxing the Markov random field directly using these conditional probabilities. We evaluate our model on a varied collection of several hundred hand-segmented images of buildings. The incorporation of spatial information is shown to improve greatly the performance of some trivial classifiers.     

Signal Interpretation of Multifunction Radars: Modeling and Statistical Signal Processing With Stochastic Context Free Grammar

Multifunction radars (MFRs) are sophisticated sensors with complex dynamical modes that are widely used in surveillance and tracking. Because of their agility, a new solution to the interpretation of radar signal is critical to aircraft survivability and successful mission completion. The MFRs' three main characteristics that make their signal interpretation challenging are: i) MFRs' behavior is mission dependent, that is, selection of different radar tasks in similar tactic environment given different policies of operation; ii) MFRs' control mechanism is hierarchical and their top level commands often require symbolic representation; and iii) MFRs are event driven and difference and differential equations are often not adequate. Our approach to overcome these challenges is to employ knowledge-based statistical signal processing with syntactic domain knowledge representation: a signal-to-symbol transformer maps raw radar pulses into abstract symbols, and a symbolic inference engine interprets the syntactic structure of the symbols and estimates the state of the MFR. In particular, we model MFRs as systems that "speak" a language that can be characterized by a Markov modulated stochastic context free grammar (SCFG). We demonstrate that SCFG, modulated by a Markov chain, serves as an adequate knowledge representation of MFRs' dynamics. We then deal with the statistical signal interpretation, the threat evaluation, of the MFR signal. Two statistical estimation algorithms for MFR signal are derived - a maximum likelihood sequence estimator to estimate the system state, and a maximum likelihood parameter estimator to infer the system parameter values. Based on the interpreted radar signal, the interaction dynamics between the MFR and the target is studied and the control of the aircraft's maneuvering models is implemented.     

A Posteriori Probability Distances Between Finite-Alphabet Hidden Markov Models

In this correspondence, we consider a probability distance problem for a class of hidden Markov models (HMMs). The notion of conditional relative entropy between conditional probability measures is introduced as an a posteriori probability distance which can be used to measure the discrepancy between hidden Markov models when a realized observation sequence is observed. Using a measure change technique, we derive a representation for conditional relative entropy in terms of the parameters of the HMMs and conditional expectations given measurements. With this representation, we show that this distance can be calculated using an information state approach     

Multiscale Bayesian segmentation using a trainable context model

Multiscale Bayesian approaches have attracted increasing attention for use in image segmentation. Generally, these methods tend to offer improved segmentation accuracy with reduced computational burden. Existing Bayesian segmentation methods use simple models of context designed to encourage large uniformly classified regions. Consequently, these context models have a limited ability to capture the complex contextual dependencies that are important in applications such as document segmentation. We propose a multiscale Bayesian segmentation algorithm which can effectively model complex aspects of both local and global contextual behavior. The model uses a Markov chain in scale to model the class labels that form the segmentation, but augments this Markov chain structure by incorporating tree based classifiers to model the transition probabilities between adjacent scales. The tree based classifier models complex transition rules with only a moderate number of parameters. One advantage to our segmentation algorithm is that it can be trained for specific segmentation applications by simply providing examples of images with their corresponding accurate segmentations. This makes the method flexible by allowing both the context and the image models to be adapted without modification of the basic algorithm. We illustrate the value of our approach with examples from document segmentation in which test, picture and background classes must be separated.     

Adaptive nonlinear filters for narrow-band interference suppressionin spread-spectrum CDMA systems

This paper presents a novel nonlinear filter and parameter estimator for narrow band interference suppression in code division multiple access spread-spectrum systems. As in the article by Rusch and Poor (1994), the received sampled signal is modeled as the sum of the spread-spectrum signal (modeled as a finite state independently identically distributed (i.i.d.) process-here we generalize to a finite state Markov chain), narrow-band interference (modeled as a Gaussian autoregressive process), and observation noise (modeled as a zero-mean white Gaussian process). The proposed algorithm combines a recursive hidden Markov model (HMM) estimator, Kalman filter (KF), and the recursive expectation maximization algorithm. The nonlinear filtering techniques for narrow-band interference suppression presented in Rusch and Poor and our proposed HMM-KF algorithm have the same computational cost. Detailed simulation studies show that the HMM-KF algorithm outperforms the filtering techniques in Rusch and Poor. In particular, significant improvements in the bit error rate and signal-to-noise ratio (SNR) enhancement are obtained in low to medium SNR. Furthermore, in simulation studies we investigate the effect on the performance of the HMM-KF and the approximate conditional mean (ACM) filter in the paper by Rusch and Poor, when the observation noise variance is increased. As expected, the performance of the HMM-KF and ACM algorithms worsen with increasing observation noise and number of users. However, HMM-KF significantly outperforms ACM in medium to high observation noise     

Multiresolution image classification by hierarchical modeling withtwo-dimensional hidden Markov models

This paper treats a multiresolution hidden Markov model for classifying images. Each image is represented by feature vectors at several resolutions, which are statistically dependent as modeled by the underlying state process, a multiscale Markov mesh. Unknowns in the model are estimated by maximum likelihood, in particular by employing the expectation-maximization algorithm. An image is classified by finding the optimal set of states with maximum a posteriori probability. States are then mapped into classes. The multiresolution model enables multiscale information about context to be incorporated into classification. Suboptimal algorithms based on the model provide progressive classification that is much faster than the algorithm based on single-resolution hidden Markov models     

Automatic Image Annotation Based on Generalized Relevance Models

This paper presents a generalized relevance model for automatic image annotation through learning the correlations between images and annotation keywords. Different from previous relevance models that can only propagate keywords from the training images to the test ones, the proposed model can perform extra keyword propagation among the test images. We also give a convergence analysis of the iterative algorithm inspired by the proposed model. Moreover, to estimate the joint probability of observing an image with possible annotation keywords, we define the inter-image relations through proposing a new spatial Markov kernel based on 2D Markov models. The main advantage of our spatial Markov kernel is that the intra-image context can be exploited for automatic image annotation, which is different from the traditional bag-of-words methods. Experiments on two standard image databases demonstrate that the proposed model outperforms the state-of-the-art annotation models.