Texture synthesis and classification using Markov and Gibbs random field models

TEXTURE SYNTHESIS AND CLASSIFICATION USING MARKOV AND GIBBS RANDOM FIELD MODELS SUMMARY In daily life, we have to make decisions by looking at the images in various areas. For example, in medical area, to classify normal and abnormal pulmanory patterns or to identify the illness by using medical images. In an airport, to control the air-traffic with radar signals. In the petroleum industry, to find an undergi'ound reservoir of crude oil via aerial photography. These or like these seperate events can be collected under a subject named image analysis. Image analysis is concerned with manipulation and analysis of pattern by computer. Its major subareas include image formation, enhancement, restoration, reconstruction, segmentation, coding and compression, texture analysis, shape analysis, representation, matching, description and recognition. There is no universal way to do image analysis because of both data- dependent and goal-oriented. In this thesis, we deal with two-dimensional digital image that can be represented by an NxN matrix, or latis, whose elements (called pixel) have integral values from 0 up to G-l correspondig to the brightness levels (gray levels). In these digital image, the gray level of a pixel is highly dependent on its geometric neighboring pixels, but is nearly independent of remote pixels. Markov random fields (MRFs) [33 have been found to be rich models for various areas in image analysis due to the dependency among pixels in spatial neighborhoods. Thus, the classical problems of texture synthesis [7], [13], texture classification [8], image segmentation, image restoration [4], [22], and image compression [14], have been attacked with MRFs.The goal of this thesİB is to make, under the theorem giving that MRFs and GRFs having the same neighborhood system are equilavent, a systematic study on the applications using these fields, and to examine carefully and compare the present sampling and parameter estimation algorithms, and finally, to classify textures by using the feature vectors. We designed a computer program for achieving all of them on personel computer. In texture modelling using MRFs, a texture is assumed to be a realisation of a stochastic process which is governed by some parameters. In texture synthesis, an algorithm that generates a texture based on a few model parameters is desired. To represent a digital texture by a few model parameters is one goal of data compression. The establishment of an image model does not have a unique rule, but it should be at least based on some property of an image. Markov random field models assume that the intensity at each pixel in an image depends on its "neighboring pixels" but is independent of other pixels. An image is viewed as a coloring of a lattice. An MRF is a probability space whose probability measure, defined on the sample space consisting of all possible colorings of a lattice, satisfies positivity, the Markov Property, and homogeneity [31. Markov random fields have been extensively used for modeling images [7], [8], [12], [13], because of the natural coincidence between the local dependency of a model and the local dependency of neighboring pixels. Derin and Kelly [17] published a paper which describes Discrete-Index Markov-Type Random Processes. The building of an MRF model should follow two principles. The MRF should naturally match the properties of a class of images and should be mathematically tractable. If an MRF generates images whose pixels have integral values, it is discrete, other-wise it is continuous. For example, an auto- binomial MRF [3] is a discrete MRF, and auto-normal MRF [3] is a continuous MRF. The studies in the literature show that discrete Markov random fields are more natural to digital textures but less mathematically tractable than continuous Markov random fields. Texture is an important characteristic for the analysis of many types of images. It can be seen in allimages from multi-spectral scanner images to microscopic images of cell cultures or tissue samples. Despite a precise definition of texture, it can be defined a structural patterns of surfaces of objects such that wood, sand, grass. In the literatui'e, textures are examined in two categories: structural textures, consisting of textons arranged according to certain placement rules, frequently appear in the studies of human vision. A structural texture is shown in Figure A. Statistical textures that we deal with in this thesis can be viewed as images in which pixels are obtained by some stochastic processes. A statistical texture is shown in Figure B. Another basic problem in image synthesis is to extract textural features [24]. Textural features can be descriptive or generative. Also, Markov random field model parameters can be thought a feature vector describing the texture [9], Descriptive textural features characterise some properties of textures corresponding to visual perception like coarseness, contrast, directionality, line- likeness, regularity and roughness [35]. Haralick [24], Wesska [37], and Conners and Harlow [11], survey and compare descriptive textural features. Descriptive textural features can not be used to produce a texture. Generative textural features can be used not only to describe a texture but also to generate a texture. There are many applications in image processing in which texture synthesis is useful. For example, if a region of a picture is missing or highly corrupted by noise, an artificial texture can be generated to replace the missing data. In image coding applications, if a texture can be generated with a few parameters, we can send these parameters to remote places instead of the whole texture image. Texture synthesis means texture generation by computer. In the literature, many algorithms have been suggested for generating a vai'iety of textures based on: 1) Mosaic models [1], 2) Fractal models [3], 3) Syntactic models [31], 4) Time series models [14], [27], [32], 5) Markov random field models [6], [12], [25] XXFigure A Example of structural text ure Figure B Exaaple of statistical texture 111Model-based texture synthesis involves three problems. First, develop an "efficient" algorithm based on the given model to generate textures. Second, develop a robust estimator for model parameters based on a single texture. Third, develop a statistic to measure the correspondence between the given texture and a model with estimated parameters. Markov random fields were first proposed as texture models by Hassner and Sklansky [25]. They investigated Besag's auto- logistic MRFs [3] in binary texture synthesis. Cross [12] extended Hassner and Sklansky' s work to model natural textures with eight colors, from Brodats's book [5], by using the auto-binomial model [3]. Chellappa [6] used the auto-normal model (also referred to as a Gaussian Markov random field) and simultaneous autoregressive (SAR) model [3] to model natural textures. Recently, Derin and Elliott [15], [16], extended the Ising model [29] to model textures with more than two colors. In summary, Markov random fields are particularly useful for modelling homogeneous textures whose neighboring pixels have a high dependence but remote pixels are nearly independent. Texture classification which is a classical problem of image analysis can be stated as follows. Given ni texture samples (training textures) from texture class i, 1 £ i £ K, extract textural features and establish a decision rule, based on the selected features, which can efficiently classify an unknown texture into one of the K categories. Although a simple and computationally efficient method is desired, there is no universal way to select textural features for classification and recognition. Textural features can be derived from gray level co- occurance matrices [23], [34], gray level run lengths [37], gray level differences [37], Fourier power spectra [37], spatial filtering [21], [30], and Markov random field model fitting [8], [9], [18], [26], [28]. Van Gool [36] gives a good survey of texture classification methods. Tamura [35] proposed six textural features, namely, corseness, contrast, directionality, line- likeness, regularity, and roughness, which correspond to visual perception. A classifier is a decision rule designed to efficiently assign an unknown texture to one of the known categories based on the extracted textural xiiifeatures. The 1-NN, quadratic, Fisher's linear classifiers are commonly used in pattern recognition [20]. The design of a classifier should consider the relationship between the number of features and the number of training samples [20]. Recognition rate is a commonly used index to evaluate a classifier in pattern recognition. In texture classification, recognition rate is used not only to evaluate a classifier but also to evaluate the textural features. The purpose of segmentation which we did not deal with in this thesis is to partition an image into "meaningful" components. The definition of a "meaningful component" is a function of the problem being considered. Segmentation algorithms based on Markov random fields have been investigated and developed [4], [15], [16], [22]. The segmentation problem can be stated as: Given an observed image y, find a coloring x, of pixels in y which optimizes specified criteria. There are two basic approaches: 1) Iterative pixel labeling approach : Individually la bel pixels one by one until some criteria are achieved. The most commonly used criterion is a maximum a posteriori (MAP) probability. The goal is to find an x which maximizes P(x|y)=P(y|x)P(x)/P(y) over all possible x's [22]. 2) Region classification approach : An image is parti tioned into several regions such that each region is assumed to be a realization of a single Markov random field model with known parameters or a combination of two Markov random fields models. How to partition on image into regions represented by Markov random fields is the most important problem. Derin [15], [16] developed a segmentation algorithm, called a dynamic programming on a strip, to labels pixels. The final goal of image segmentation is to automatically recognize the regions in an image. Image restoration is a process which attempts to reconstruct or recover an image that has been degraded by using some knowledge of the degradation phenomenon. It has many fields of applications, including space and biomedical imagery. Knowledge of the degradation phenomenon is crucial to restoration. xivIn this thesis, Chapter 2 gives a background of Gibbs Random field and Markov random field, Chapter 3 characterizes sampling algorithms for discrete GRFs and MRFs, Chapter 4 explaines parameter estimation methods and goodness-of-fit problems, Chapter 5 represents the texture classification and recognition methods, and Chapter 6 summarises and discusses results. XV