Comments on Cross and Jain, Markov Random Field Texture Models

G.Cross and A.Jain, "Markov Random Field Texture Models," IEEE Trans PAMI, 5(1):25-39,1983.

Abstract

We consider a texture to be a stochastic, possibly periodic, two-dimensional image field. A texture model is a mathematical procedure capable of producing and describing a textured image. We explore the use of Markov random fields as texture models. The binomial model, where each point in the texture has a binomial distribution with parameter controlled by its neighbors and "number of tries" equal to the number of gray levels, was taken to be the basic model for the analysis. A method of generating samples from the binomial model is given, followed by a theoretical and practical analysis of the method's convergence. Examples show how the parameters of the Markov random field control the strength and direction of the clustering in the image. The power of the binomial model to produce blurry, sharp, line-like, and blob-like textures is demonstrated. Natural texture samples were digitized and their parameters were estimated under the Markov random field model. A hypothesis test was used for an objective assessment of goodness-of-fit under the Markov random field model. Overall, microtextures fit the model well. The estimated parameters of the natural textures were used as input to the generation procedure. The synthetic microtextures closely resembled their real counterparts, while the regular and inhomogeneous textures did not.

Summary of the paper

The paper illustrates the use of MRFs with binomial conditional probabilities as a texture model; in this critique we will call this a " bMRF ". Textures are synthesized and exhibited using this model to gain a feel for its generative power and the role of the parameters. Several natural textures are then fit using this model. The paper compares (second order) statistics of particular textures to those predicted by bMRFs with parameters fit to these textures in order to evaluate the goodness of fit of the bMRF model to the textures. The Chi-squared test ("could the generated statistics have come from the distribution derived from the actual texture") is satisfied in some but not all cases. Lastly, the best fitting bMRF models are used to synthesize textures, which are visually compared to their source textures.

Cross and Jain appears to be one of the first papers that shows the result of fitting MRFs to real textures. The math in this paper appears in the Besag paper in the references (one of the main primary MRF references). Besag discusses and illustrates parameter estimation for some choices of conditional probability and some choices of data (wheat plots) but does not visually compare real and estimated data. Hassner and Sklansky in the references discusses the use of MRFs for texture and shows several limited synthetic examples; they discuss but do not attempt the fitting of MRFs to real textures.

Definition of Texture

The paper's definition of texture appears to be a "stochastic image field" (see first sentence of abstract) that can in some cases be modeled using a bMRF. The authors do not feel that the bMRF model is good for all textures; for example, Table 4 shows that some of the considered textures cannot be statistically captured by the bMRF model.

General Comments

The paper attempts to communicate both the types of textures which bMRFs are capable of modeling and those which bMRFs are not. This is done both by showing an array of textures generated with manually selected parameters, and by attempting to estimate and model real textures. They point out the importance of objectively evaluating the goodness of fit of the models to the original textures, and attempt to do so.

Discussion Topics

How does the modeling power of these bMRFs compare to GMRFs?
What can be said about the relation between neighborhood size and the range of spatial correlation generated by a MRF?
How are the first-order statistics (histogram) matched using Cross and Jain's algorithm?

Clarifications and Corrections

The large equation in the middle of p.28 has several mistakes but is not as incorrect as it looks. Since this equation is unlabeled we will call it the VeryWide equation. In the numerator, the first X should be a Y; at the end of both the numerator and denominator, Y(N) should be Y(M=N^2):

p(Y)         p(Y(i)=y(i) | X(1),X(2),...,X(i-1),Y(i+1),...,Y(M))
---  =  Prod -----------------------------------------------------
p(X)         p(X(i)=x(i) | X(1),X(2),...,X(i-1),Y(i+1),...,Y(M))

The part on the right of the conditional is the same in both numerator and denominator.

In VeryWide, Y is a "new" image and X is an "old" image; the equation gives the relative probability of these two configurations. The new configuration may be completely different, or it may differ only in one pixel. In the latter case, i.e. Y(i) equal to X(i) except in one location, the equation gives the relative probability needed by the Metropolis algorithm (Fig. 2) to test whether it should accept a proposed pixel exchange. In this case the equation is simple as well: it reduces to the conditional probability of the new pixel divided by the c.p. of the old pixel (each conditioned on the identical neighborhood values).

The derivation of VeryWide comes from repeated application of (A::) P(a&b) = P(a|b)P(b), or (B::) P(b)=P(a&b)/P(a|b) Start with P(X): this is the simultaneous probability of the image having a particular set of pixel values, i.e., P(X(1)==g1 & X(2)==g2 ...). Rewrite the 'and' using A::

P(X) = P(x(n) | x(1),...,x(n-1)) P(x(1),...,x(n-1))

The first factor is given directly by the MRF, but the second is not. To factor it, rewrite it using B:: (with 'b' named 'y'):

P(x(1),...,x(n-1)) = P(x(1),...,x(n-1), y(n)) / P(y(n) | x(1),...,x(n-1))

Now substitute this version back into VeryWide and repeat the same factoring procedure on the right hand factor until VeryWide results.

comments by John Lewis (zilla@interval.com) and John Woodfill (woodfill@interval.com)