Turn?» ..._ ..__.__ LIB R A R Y Michigan State University This is to certify that the thesis entitled Markov Random Field Texture Models presented by George Robert Cross has been accepted towards fulfillment of the requirements for P’\' ‘ D ' C({M’L'va’lf 5(1)! GWQ ‘1’ degree in M \IquQ-"l (7?be Major professor Date H/ iL/S’C’ 0-7639 S w: 25¢ per day per item RETURNING LIBRARY MATERIALS: Place in book return to remove charge from circulation records MARKOV RANDOM FIELD TEXTURE MODELS BY George Robert Cross A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1980 ABSTRACT MARKOV RANDOM FIELD TEXTURE MODELS BY George Robert Cross 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. A detailed account of the current literature about texture models is given, along with a discussion of the intuitive notions of texture. 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 9 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. This represents the first use of the binomial model for image analysis and the first application of the binomial model for any purpose. A method of generating samples from the binomial model is given followed by a theoretical and practical analysis of its 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 images is demonstrated. Natural texture samples were digitized and their parameters were estimated under the Markov Random Field model. The use of a hypothesis test' for an objective assessment of goodness-of-fit under the Markov Random Field model is a key feature of this investigation. Overall, highly random textures fit the model well. The estimated parameters of the natural textures were used as input to the generation procedure. The synthetic micro-textures closely resemble their real counterparts, while the regular and inhomogeneous textures do not. Co-occurrence matrices of binary, first-order Markov Random Field textures were computed as a function of the field parameters. There is a good correspondence between the predicted matrices and the observed matrices on numerous samples. Ala realistic_appraisal of the Markov “f as a texture model is accompanied by a for future study. Random list of To Ellen ii ACKNOWLEDGEMENTS I thank my major professor Anil K. Jain for his help and encouragement during the preparation of this thesis andr more important, for guiding me toward a career in Computer Science. Professor Richard Dubes deserves special recognition for his careful reading of numerous preliminary drafts and suggestions for improvement. I also thank Professors Page and Mandrekar for serving on my committee and Professor Hedges for welcoming me into the department. Thanks are due in addition to the PR/IP Laboratory graduate students for their assistance during the hectic days of thesis preparation: Neal Wyseo Steve Smith, Wei-Chung Lin, and Gautam Biswas. The partial support of NSF Grant ECS-8007106 is also gratefully acknowledged. iii TABLE OF CONTENTS LIST OF TABLES ................................... vii LIST OF FIGURES ..3............................... viii LIST OF SYMBOLS .................................. x CHAPTER 1. INTRODUCTION ......................... 1 1.1 Intuitive Notions of Texture ............. 2 1.2 Texture Formation Paradigms .............. 6 1.3 Vision Research About Texture ............ 8 1.3.1 Julesz' Work on Texture .............. 9 1.3.2 Marr's Work on Texture Vision ........ 13 1.4 Applications of Texture .................. 14 1.5 Organization Of the ThESTS ooooooooooooooo 20 CHAPTER 2 TEXTURE MODELS ...............5......... 21 2.1 Introduction ............................. 21 2.2 Stochastic Texture Modelling ............. 26 2.2.1 Ouantized Continuous Models .......... 27 2.2.2 Time Series Models ................... 29 2.2.3 Fractal Textures ..................... 30 2.2.4 Random Mosaic Models ................. 32 20205 Syntactic MethOdS oooooooooooooooooooo 37 iv 2. 2. 2.3 CHAPTER 3.5 3. 3. 3. 3. 3.6 CHAPTER 4.1 4.2 4.3 CHAPTER 2.6 Linear MOdELS oooooooooooooooooooooooo 207 Markov MOdElS oooooooooooooooooooooooo Summary oooooooooooooooooooooooooooooooooo 3. MARKOV RANDOM FIELDS ................. Introduction ............................. Definitions and Theorems ................. Further Assumptions ...................... Order Dependence ......................... Specific Models .......................... 5.1 Binary Model ......................... 5.2 Binomial Model ....................... 5.3 Other Auto-Models .................... 5.4 Other Lattice Models ................. 3.5.4.1 Strauss Model .................... 3.5.4.2 Helberry-Galbraith Fields ........ Summary oooooooooooooooooooooooooooooooooo 4. SIMULATION of MARKOV RANDOM FIELDS ... Introduction ............................. Definitions .............................. Simulation Procedure ..................... Convergence Properties ................... Examples of Textures ..................... Summary nooooooooooooooooooooooooooooooooo 5. MODELLING NATURAL TEXTURES ........... 38 4O 42 44 44 45 49 51 59 61 61 62 62 65 66 67 67 7O 78 5.1 5.2 5.3 Introduction ooooooooooooooooooooooooooooo Estimation Of Parameters ooooooooooooooooo HypotheSTS Testing ooooooooooooooooooooooo 504 DeSCertTon Of the Data oooooooooooooooooo 5.5 Evaluation Of the Fit oooooooooooooooooooo 5.5.1 Binary Texture Results ooooooooooooooo 5. 5.6 5.2 Binomial Texture ReSULtS ooooooooooooo Texture Matching Experiments ............. 50601 Binary Textures oooooooooooooooooooooo 50602 Binomial Textures oooooooooooooooooooo 5.7 Summary oooooooooooooooooooooooooooooooooo CHAPTER 6.1 6.2 6.3 6.4 6.5 CHAPTER 7.1 7.2 6. CO-OCCURRENCE MATRICES ............... Introduction ............................. Joint Probability Formulation ............ Join Count Statistics .................... Experimental Results ..................... summary oooooooooooooooooooooooooooooooooo 7. CONCLUSIONS AND DISCUSSION ........... summary oooooooooooooooooooooooooooooooooo DISCUSSION ooooooooooooooooooooooooooooooo 70201 Advantages ooooooooooooooooooooooooooo 7.2.2 Disadvantages and Limitations ........ 7.3 Suggestions for Future Research .......... LIST OF REFERENCES 0.0.0.0.........COOCOOOCOIOOOOO vi 93 100 104 107 107 121 126 126 135 141 142 142 144 147 155 160 161 161 164 167 169 173 10. 11. 12. 14. 15. LIST OF TABLES Textures Used in the StUdy ooooooooooooooooooo Isotropic. First-Order. Binary Tests ......... Anisotropic. First-Order. Binary Tests ....... Isotropic. First-Order. Binary Tests on Second-Order SpaCTnQ oooooooooooooooooooooo Anisotropic. First-Order. Binary Tests on Second-Order Spacing oooooooooooooooooooooo First-Order (Isotropic). Second-Order (ISOtrODTC), Binary Tests oooooooooooooooooooo First-Order (Isotropic). Seconqurder (Anisotropic). Binary Tests oooooooooooooooooo First-Order (Anisotropic). Second-Order (Isotropic). Binary Tests oooooooooooooooooooo First-Order (Anisotropic). Second-Order (Anisotropic). Binary Tests oooooooooooooooooo Best-Fitting Binary Texture Models ........... Eight Gray Level. First-Order(Anisotropic). Second-Order(Isotropic) Tests oooooooooooooooo Eight Gray Level. First-Order(Anisotropic). Second-Order(IsotrOpic) Tests oooooooooooooooo Best-Fitting Eight-Gray Level Texture Models . Binary Texture Characteristics ............... Errors in Co-Occurrence Predictions .......... 106 112 113 114 115 116 117 119 120 123 124 125 128 159 10. 11. 12. 13. 14. 15. 16. LIST OF FIGURES Brick Hall ................................... Coarse Gravel ................................ Venetian Blinds .............................. Rag Rug ...................................... Repetitions of a Random Texture .............. Squared Distances to the Point X ............. Orders Retative to the Point X .....-......... First-Order Neighbors ........................ Second-Order Neighbors ....................... Constituents of the S(i.k) ................... Conditional Probabilities for the Welberry-Galbraith Field ooooooooooooooooooooo Algorithm for Generating a Markov Random Field ................................. Convergence of b(1..) ........................ Behavior of the Number of Exchanges .......... Isotropic First-Order Textures ............... Anisotropic Line Textures .................... Ordered Pattern .............................. Diagonal Inhibition Textures ................. Isotropic Inhibition Textures ................ Clustered Texture with 4-gray Levels ......... viii 12 52 54 56 60 65 77 80 81 87 88 88 89 90 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. Clustered Textures with 16 and 32 Gray Levels. ooooooooooooooooooooooo'oooooooooooooo Horizontal Texture with 16 Gray Levels ....... Attraction-Reoulsion Textures with 16 Gray Levels ............................... First-Order Coding Pattern ................... Second-Order Coding Pattern .................. Third- or Fourth-Order Coding Pattern ........ Example of a Chi-Square Test ................. Non-Markovian Periodic Texture ............... Real and Synthetic Binary Textures ........... Real and Synthetic Eight Level Textures ...... Expected and Observed Co-Occurrence Probabilities oooooooooooooooooooooooooooooooo ix 90 91 91 96 97 99 103 110 131 138 158 fines; b(i,.) b(i9k) 881 BB? BN1 SW? C F f(niisj) G Y(1) Y(2) m(j95) LIST OF SYMBOLS Markov Random Field Parameter for {0.1} variables Markov Random Field Parameter for {-1.1} variables Markov Random Field ith-order isotropy parameter Markov Random Field ith-order. kth direction parameter Horizontal black-black join count Vertical black-black join count Horizontal black-white join count Vertical black-white ioin count Co-occurrence matrix Clique function First-passage probability Number of gray levels Markov Random Field horizontal clustering parameter Markov Random Field vertical clustering parameter Lattice or image Mean recurrence times N olivi) {q(j)} my S {S(i)} S(i9k) 5(T) U1 U2 V(i9j) ”WI ””2 N81 W82 5 Xlisj) Z 9 Image dimension Transition probability Coloring probability Conditional probability of X9 given its neighbors Limiting distribution Log probability ratio Markov Random Field mean States of Markov chain Sum of neighbors at order iv direction k Weighted neighborhood sum Binomial model parameter Horizontal join count Vertical ioin count Interaction parameter Horizontal white-white join count Vertical white-white join count Horizontal white-black join count Vertical white-black join count Coloring Gray level at point (i.j) Partition function Coloring of all zeroes CHAPTER 1. INTRODUCTION Image modelling is a central part of an image understanding system. It is also the core of classical image processing: image restoration [6]. and two-dimensional filtering [423. The subject of image modelling involves the construction of models or procedures for the specification of images. These models serve a dual role in that they can describe images that are observed and also can serve to generate synthetic images from the model parameters. We will be concerned with a specific type of image model. the class of texture models. Understanding texture is an essential oart of understanding human vision. In this thesis. we will explore the use of a Markov Random Field model for the generation and analysis of textured images. The goal of the research is to produce a texture analysis and synthesis system which will take as input a stochastic texture. analyze its parameters according to the Markov Random Field model. and then generate a textured image that both resembles the input texture visually and matches it closely from a statistical point of view. This can be considered a kind of Turing test for image generation [1003. in that the proof of the viability of the system will be to produce textures that cannot be distinguished by humans from their real counterparts. We will not perform a rigorous psychological study of the correspondence. but will concentrate on the statistical evaluation of the goodness of fit of the observed texture and the generated texture. 1.1 Intuitive Notions of Texture We mention a study by Tamura et al. [983 which attempted to find statistical features corresponding to the usual attributes of texture. Although the study had limited success. the textural attributes identified serve as a useful framework for the discussion that follows. The study delimited six attributes: coarseness. contrast. directionality. line-likeness. regularity. and roughness. Coarseness refers to the size of the cells (areas of near equal brightness) present in the picture. A fine grain picture has small cells. whereas a coarse picture has large cells. Large areas of equal brightness are significant visual cues. 0‘ The contrast of a picture is determined by local Ivariation in gray tone. A low-contrast picture nay have all the gray scale values present. but has few transitions from near black to near white in object boundaries. Before proceSsing a picture. we often normalize the contrast and modify its histogram so that an equal number of pixels is present at each gray level. Moreover. the gray scale is then adjusted so that G levels occur at equally spaced intervals from 0 (black) to 255 (white). Such a transformation distorts the natural contrast in the image and negates the value of this feature. Directionality refers to whether we perceive the trend of the image to be vertical. horizontal. skewed. or non-directional. The bricks picture. Figure 1. is clearly directional. while the gravel image. figure 2. is non-directional. Line-likeness refers to the presence of lines in the picture. It is contrasted to a blob-like effect. where there are clusters of equal brightness and of circular shape. Some images have a mixture of both. Figure 3 is an image of Venetian blinds and has a definite line-like structure. Eigugg 13 Brick Wall E1935; g; Coarse Gravel Eigggg g; Venetian Blinds £12932 3; pac; Rug Regularity refers to whether the image is highly random or not. An image of a rag rug. Figure 4. is clearly regular. whereas the picture of gravel. Figure 2. is irregular. Finally. roughness describes a tactile attribute of texture rather than a visual one per se. But a rough surface is also visibly rough. and real pictures show surface contours that we would expect to feel rough if we could touch them. 1.2 Texture Formation Paradigms There is no universally accepted definition for texture. Part of the difficulty in giving a definition of texture is the extremely large number of attributes of texture that we would like to subsume under a definition. Moreover. some of these attributes are aooarently contradictory. The first definition is that a texture is a periodic. stochastic gray-scale image. Examples of such textures include cloth. tiles. and bricks. The second definition of texture is any stochastic gray-scale image. This includes such textures as grass. sand. and clouds. Most texture research can be characterized by the underlying assumptions made about the texture formation process. There are two major assumptions. and the choice of the assumption depends primarily on the type of textures to be considered in the study. The first assumption. which is called the placement rule viewpoint. was explained by posenfeld and others [86]. [111]. In this model. a. texture is composed of small primitives. These primitives may be of varying or deterministic shape. such as circles. hexagons. or even dot patterns. The textured image is formed from the primitives by placement rules which specify how the primitives are oriented. both on the image field and with respect~ to each other. Examples of such textures include tilinos of the plane. cellular structures like tissue samples. or the picture of bricks. Figure 1. Notice that no two bricks are identical. but there is a uniformity to their placement. There is a random aspect to the brick picture in that the shading of the individual bricks varies. The image of gravel. Figure 2. is not appropriately described by a placement model. The key feature of this image is the coloring and distribution of the cells (areas of near-equal brightness). The primitives are very random in shape and cannot be easily described. The second viewpoint regarding texture generation processes involves the stochastic assumption. We have already seen that the placement 'rule paradigm for textures may include a random aspect. In the stochastic point of view. however. we take a more extreme position and consider that the texture is a sample from a probability distribution on the image space. The image space is usually an N by N grid and the value at each grid point is a random variable in the range {091100096-1}0 1.3 Vision Research about Texture In this section. we will describe what vision researchers have found to be the important constituents of human texture vision. Although machine perception need not be an emulator of the human visual system. the success of human vision in discriminating textures merits attention. In addition. since we are interested in performing automatically tasks that are currently done by humans. such as radiographic screening. we should be guided by the cues and sensitivities of the human visual system. 1.3.1 Julesz' Work on Texture Julesz' investigations of texture span twenty years. Besides the study of texture perception itself. he has studied texture's role in binocular or stereoptic perception. motion perception. and color perception [573. He will examine only the work on texture itself. Early in his work. dulesz decided that it is appropriate to examine perception of textures without visual cues. He uses random dot patterns controlled by analogs of one-dimensional Markov processes and Gaussian processes. Because of this. his work has limited applicability to textures generated according to placement rule schemes. His work is also concentrated on "pure perception." which means perception in the absence of higher-order scrutiny. When he speaks of "effortless discrimination." he refers to the process of deciding whether two textures are the same after seeing them for only 100 milliseconds. If they are seen for a longer time than that. higher-order conceptual processes take over. One of the key features that he identified in texture perception is cluster formation [56]. This is related to image coarseness in the sense mentioned earlier in section 10 1.1. He found that the human visual system acts as a slicer or thresholding device in clustering intensity values. For example. if the image contains the gray levels 0. 1. 2. and 3. then it is not possible for clusters to form consisting of the gray level sets {0.2} and {1.3}. Further. cluster detection is central to the entire perceptual process. from the lowest level aggregation up to the higher order mental processes. The aspect of dulesz' work that has captured the most attention is the conjecture that the human visual system cannot effortlessly discriminate textures that agree in their second-order statistics [54]. [55]. E583. E59]. [60]. The first-order statistics are simply the proportions of the pixels at each gray level. The proportions control whether we see the picture as a black object on a white background or vice versa. Julesz has found that we can effortlessly perceive a first-order difference between textures within fairly narrow ranges [54]: this work is related to the classical figure-ground problem and numerous optical illusions [35]. The second-order statistics involve the joint probability that a randomly thrown rod of length r will fall on the image in such a way that one of its endpoints lands on a pixel of color i while the other lands on a pixel of color j. 11 Similarily. third-order statistics have to do with triangles and the configuration of gray levels at the vertices after a similar random experiment. The conjecture that the second-order description (which of course implies the first-order statistics) determines our discrimination ability has held up remarkably well with only a few classes of unusual textures that confound it [58]. Another aspect of texture that dulesz investigated [57] is that periodicity of a texture is only observable if the frequency is large compared to the size of the picture. For example. it is all but impossible to notice that Figure 5a consists of the same texture repeated four times. whereas it is immediately obvious that Figure 5b consists of repetitions of the same random structure. The difference is that Figure 5b consists of sixteen repetitions of a 16 by 16 picture in a frame size of 128 by 128. whereas Figure 5a consists of only four repetitions of a 64 by 64 picture in the same frame size of 128 by 128. Julesz' work has been extended by a number of researchers. notabiy Pratt ef al. [83]. It is now generally assumed that- the second-order statistics are 12 yxag‘xYXxfi-ifi; -..-.6 4 w‘ was Wm?) gflfigk‘r A . " g ‘ ‘qy‘fi ‘ 3‘, 4‘ "9'7: i ) Em. « $3}in ”K‘sf“ My I.) «9‘ 1’ «’3 J; :3‘¢;«_“ kg‘Ya‘: ‘w‘y 964433;: a; Figure 5. Repetitions of Random Textures: (a) Four repetitions (b) Sixteen repetitions. sufficient in a pattern recognition environment to discriminate between textures. There is still much work to be done in the sense that the second-order probabilities must be combined in some way to provide features for recognition of the textures. The previously discussed work of Tamura et al. [98] is such an attempt. as is the continuing efforts of Conners and Harlow [23] to define a texture recognition feature set from the second-order statistics. It is possible to use third-order statistics in texture discrimination even though the human visual system does not appear to make use of them. The difficulty lies in attempting to estimate 13 the third-order parameters given a relatively small texture field. such as a field of size 64 by 64. Moreover. the storage requirements for maintaining frequency statistics on the large number of possible configurations are enormous. 1.3.2 Marr's Work on Texture Vision The ultimate goal of Marc's research. is a comprehensive computational theory of vision. Such a theory can be implemented with a computer. which will. in fact. emulate the human visual system. His plan revolves around the "primal sketch" E68]. [693. The primal sketch is produced from the original intensity values received at the retina. The primal sketch consists of measurements on the strengths and characteristics of the following primitives: edges. lines or bars. and blobs. These primitives are quantified further by the predicates of orientation. size (length. width. diameter. or aspect ratio if appropriate). contrast. position. and terminal points. This is in general agreement with the work of Caelli and dulesz E18]. [19] in describing the processing at early levels in the visual system. 14 Marr asserts that once the primal sketch is computed. it can then be analyzed to find objects or regions of interest. This is done by aggregating the primitives which are close in some sense. We may thus characterize his overall approach as "bottom-up." in the sense that we do not begin with high-level knowledge of the scene or preconceptions of the objects present. The recognition of objects using the primal sketch model is based on using the texture information to define the objects. rather than considering the texture to be noisy background. 1.4 Applications of Texture There are essentially four areas of image processing in which texture plays an important role. We offer this discussion as justification of our interest in the production of synthetic textures. As a side benefit. such generation procedures may help in furthering our understanding of human perception. According to Julesz C5739 ... to solve the problem of visual texture generation of familiar surfaces is important for both theoretical and practical uses. I can only hope that in the near future scientists will learn to clarify the enigmatic problem of familiar textures. 15 (i) Classification_ Suppose. for example. that we have a series of pictures of mineral samples that we would like to classify into groups based on the type of mineral represented. The true class of some training samples is generally known and could be provided by geologists. Such images have a special structure characteristic of the mineral. but the structure is not deterministic like a tiling. We would like to specify some features of the image in order to classify it. There are obvious differences in distribution of grain size. gray tone. and even color. Studies of this type have been done by Haralick [46] on sandstone samples and by Weszka et al. [106] on terrain samples. (ii) Image Segmentation Segmenting an image means dividing it into homogeneous regions such that each region has some significance. Typically. the regions are connected and we have some a 951951 idea of what we are looking for or what might be present in the image. For example. we may wish to segment a LANDSAT image into land-use categories by means of texture analysis. Nevatia [76] uses the 16 assumption that the objects of interest have strong boundaries and the textured background is composed of short line segments to extract the boundaries of a small toy tank from the background of grass. Thompson E°93 uses a generalized edge operator to define texture borders and is successsful in finding the boundaries between two regions with differing textures. A linear approach to segmentation of textured regions is taken by Deguchi and Morishita [26]. which we will discuss in detail in chapter 2. (iii) Realism in Computer Graphics Computer graphics differs from image processing in that its goal is the production of images frOm a description. whereas image processing is concerned with the modification and interpretation of real-world images. Although high resolution. color. raster-graphics displays capable of producing realistic images are available. the existing algorithms cannot produce the desired realism. Texture gives important information on the depth and orientation of an object. besides being an intrinsic feature of realistic objects [643. [78]. A number of approaches have been taken. mostly related to mapping a 17 flat textured image onto the skeleton of a three-dimensional object and then displaying a perspective view. Catmull E20]. [21] describes a procedure for wrapping photographs of texture onto objects to produce textured surfaces. Blinn [14]. [15] uses a patch of texture to tesselate the image. Csuri et al. [25] extend the basic patch idea to include the specification of structure for the patch in terms of reflectance values at each pixel. This allows more realistic shading and permits the simulation of the appearance of the textured patch under the generated illumination. They intend to extend their model to include some randomness in the patches. Dungan [293 has coupled height data from Defense Mapping Agency maps with an overlay identifying terrain segments (trees. lakes. etc) to simulate the appearance of the ground scene to a viewer in an airplane. As the applications of computer graphics grow. the importance of an understanding of texture will also increase. In fact. the generation of natural textures will likely play a more important role than the recognition of textures. 18 (iv) Picture Encoding The final area where texture generation and analysis has application is in picture. encoding. If we can generate a texture with a few parameters that is indistinguishable from an observed texture. then we have effectively compressed the enormous amount of data in the original texture to the parameter vector. By analogy. this is tantamount to knowing an algorithm for the generation of normal deviates rather than carrying an enormous pre-printed book listing millions of samples from a normal population. Such a procedure has application to the previously mentioned graphics problems in that we could artificially generate background scenes from descriptions defined by textural parameters. Such scenes are presently generated by a hybrid graphics and image processing procedure of mapping photographs onto the graphics skeletons. Some work has already used texture synthesis in the pure information theory context of reducing the total number of bits needed to store the picture. Modestino and Fries [75] encode a picture according to a poisson line model. while Delp et al. [27] use a Gaussian model. In 19 both cases. the image is partitioned into small squares. The texture of each square is estimated and the few parameters of the texture are stored instead of the 256 gray levels of the observed texture. Since the picture is reconstructable by the same model that was used to estimate it. the picture can be approximately reconstructed square by square from the estimated parameters. 20 1.5 Organization of the Thesis Chapter 2 contains a review of texture models that have appeared in the literature and further specifies the levels of texture modelling. Chapter 3 describes the ’specifics of the Markov Random Field theory needed to understand the models that we use in generating and fitting textures. Chapter 4 details the generation procedure for obtaining a texture sample from a distribution specified by a parameter set. In chapter 5. we give our results in fitting a variety of models to a sample of textures from the Brodatz texture album [17]. Chapter 6 gives theoretical results in deriving vtextural features from the model parameters. such as the co-occurrence matrices for Markov Random Field textures. Finally. chapter 7 gives our conclusions and directions for future research. CHAPTER 2. TEXTURE MODELS 2.1 Introduction By a model of a texture. we mean a mathematical process which creates or describes the textured image. The goal of texture modelling is the description of the image; real textures can be compared to generated textures as a test of the validity or utility of the model. The test can take the form of a psychological study or of a statistical assessment of goodness of fit. A secondary goal of texture modelling is classification of textures. The numerical parameters of the model can be used as features to classify the texture. There is a distinction between model-based studies and attempts to find good features for the classification of textures. In a model-based environment. we have the capability to produce. for example. textures that match observed textures. In a feature-based texture analysis. the textural features are measured without an ideal or representative texture in mind. 21 22 Texture modelling can be approached at three levels. The highest level. which we call} the knowledge representation level. uses our understanding of the physical scene in order to describe the textured image. For example. consider the set of textured images of wood grain observed in samples {T(e}). where 9 is the angle at which the cut was made in the tree to form the wood sample. Because trees grow in concentric rings. the ideal appearance of such samples T(9) varies continuously from an image of concentric circles (when 9 is O) to ellipses. and finally to parallel lines (when 9 is 90 degrees). This ideal image is. of course. corrupted by noise. degraded by irregularities in the circles. and. perhap. distorted from the expected image by the presence of knots. We do have. however. an ideal image for specifying membership in the class defined by 9. Such a model was used in automatic drafting [1083. Once we have this ideal model. the classification problem can be attacked. In the present example. the classification problem has been reduced to the relatively trivial one of circle and line detection along with estimation of the aspect ratio of the ellipses. Thus. our structural description of the expected image permits us to identify observable features. 0n the other hand. the 23 knowledge used in one domain of images may not be applied easily to other areas. Models constructed for the texture of corn fields from satellite photographs may not be of much use in constructing a model for the appearance of wheat fields or even corn fields grown in other countries under different cultivation regimes. The success of the knowledge representation approach is limited by our capability to generalize. The bottom level of texture modelling is called the feature-based level. In fact. it is possible to make a case for not calling feature-based. studies modelling at all. We assume that the textures are samples from some unknown probability distribution over a lattice or grid L. representing the image. which has dimension N by N. The objective is to find features that correctly classify a texture into one of the texture classes represented by a set of different probability distributions. A survey of the well-known and commonly used texture features that have been investigated appears in a recent report [47]. Texture features include the image autocorrelation function [62]. which has been found to have visual significance. An influential paper by Haralick [45] describes the use of features computed from the gray level 24 co-occurrence matrices. The (r.s) entry in a co-occurrence matrix is the probability that a point of the image (i.j) has gray value r while point (k.l) has gray value 5. where k = i + dx. and l = j + dy. The increments dx and dy are constant over the individual matrices and we compute a set of matrices indexed by the increments (dx.dy). If G is the number of distinct gray levels in the image. then the co-occurrence matrices are of size G by G. Haralick [45] defines some 14 features based on the co-occurrence matrices. We mention three of them. Let R be the number of pairs of grid positions that were used to compute the co-occurrence matrix C with entries c(i.j) corresponding to the displacement (dx.dy). The angular second moment feature fl is defined by 6-1 6-1 \ \ 2 \ \ / c(i.i)\ f1 = --------- / / \ r / / / and measures the homogeneity of the image. Large values of f1 indicate the presence of many dominant gray level transitions in the image. The contrast feature is given 25 by f2 G-1 \ 2 \ 2 \ n \ / c(i.j)\ f2 = ----- "" / / \ r / / / n = 0 li-3l=n and is a measure of the local correlation. Small values of f2 correspond to images with little local variation. Finally. the correlation feature f3 measures the linear dependence in the image: 6-1 6-1 \ \ t \ \ f3 = (ijc(i.j)/R) - Uny / / ------------------- / / SxSy i = 0 i = 0 where Ux and Uy are the means and Sx and Sy are the standard deviations of the marginal distributions associated with c(i.j)/R. The feature f3 is large if the correlation in the direction expressed by (dx.dy) is large. 26 Several studies have shown that features based on co-occurrence matrices perform reasonably well in classifying some textures. E106]. E231. Conners and Harlow [241 have theoretically evaluated co-occurrence features in distinguishing Markov scan textures. Other features that have been used with some success include gray level run lengths E37]. edge per unit area [861. E87]. extrema in gray scale height [86]. and encoded maxima along scan lines [743. 2.2 Stochastic Texture Modelling We now turn our attention to the middle level of texture modelling. the stochastic process approach. We use the term stochastic process in a loose sense to describe a random procedure used to generate an image. There is some inevitable overlap between the stochastic process approach and the knowledge representation point of view since we try to find a stochastic process for the modelling of the image that is physically meaningful and related to the textures which we are modelling. We use more prior information about the texture in the stochastic process approach than in the feature-based approach. In the stochastic process approach. brightness levels or pixel gray values are the random variables. The level 27 X(i.j) at some point (i.j) is not independent of the levels at other points in the image. In fact our principal concern is about the correlations between the {X(i.j)}. This section is subdivided into discussions about the major classes of texture models that have appeared in the literature. A short description of each type is given. along with some indication of the class of textures that can be handled by the model. 2.2.1 Quantized Continuous Models Suppose that we have M points in the unit square. We impose an N by N grid on the unit square and then count the number of points that fall in each grid square. Such a grid can now be quantized by a scale change to form an image in the usual sense. with a gray scale in the range from 0 to 6-1. The value of G can be either the maximum number of points that fall into a grid square or we may choose G a pgiggi and then use a quantizing function to map the accumulated grid counts to levels from 0 to G-1. 28 A wide variety of continuous_processes. including the multivariate normal distribution. are available to form such images. 0n the other hand. much greater generality can be achieved by the use of spatial processes as explained by Ripley £841 or Matern [701. Following Ripley [84]. a realization of a spatial process is a countable set of points without limit points. For each measurable set A. let Z(A) be the number of points of a realization that fall in the set A. If A is a bounded set. then Z(A) is finite. The process is described by the set of random variables (Z(A)! A is a bounded Borel set}. If the process is second order. translation invariant. and rotation invariant. then Ripley calls the process a 'model'. These latter assumptions are for mathematical tractability. Ripley remarks that the first and second moments of a spatial model should be sufficient to distinguish realizations and justifies this by the work of Julesz [54]. who found that. for the most part. textures with the same second-order statistics were indistinguishable by human vision (see chapter 1). The continuous models of Ripley [84] can be broadly delimited on a scale of clustered. random. and inhibitory. Let U be a set of unit area. The intensity of the process 29 is called x and we assUme that EEZ(U)J = x . For a given A. we would expect a concentration of nearest neighbor distances for a clustered process at levels far below that for a random (i.e. Poisson) process. Similarly. an inhibitory model has a concentration of nearest neighbor distances far above that expected for the random process. One kind of inhibitory model is called hard core. in that we do not allow any points less than a. distance 2r apart. where r is a positive parameter of the process called the inhibition distance. The discretization of continuous processes as image models of texture has not been explored except for a brief mention in [90] and some simulation in [11]. Some results in discrete analogs of continuous processes appear in Rogers' monograph on retail trade [85]. but no direct application to images was made. 2.2.2 Time Series Models McCormick and Jayaramamurthy [66] have developed a model of texture based on a time series forecasting technique. A time series is. of course. a one-dimensional sequence of random variables indexed by a parameter which is usually associated with time. To make such a sequence 30 into an N by N image. the time series is broken up into pieces of size N and then stacked as rows of an image. McCormick and dayaramamurthy use the auto-regressive integrated moving average process (ARIMA) to simulate textures. The parameters are estimated from real textures. They exhibited some success in generating textures characterized by long streaky lines such as the cheesecloth picture in Brodatz [17]. image 0105. The applicability of this model to isotropic textures. i.e.. ones with random or irregular globular clusters. is dubious. It is. however. an appropriate model for line-like textures. as they are able to satisfy the criterion expressed in Chapter 1 that the texture synthesis process be successful in the production of an image that the viewer might think was a real texture. 2.2.3 Fractal Textures The term fractal was coined by Mandelbrot [67] to describe point sets or stochastic processes whose Hausdorff dimension exceeds their topological dimension. The topological dimension of a point set usually corresponds to our intuitive notion of dimension but 31 differs for certain pathological cases. As we should expect. the topological dimension of a countable set of points is 0. of a line is 1. and of a plane is 2. A discussion of the definition and the development of the theory of topological dimension is given by Hurewicz and Wallman [51]; a more modern treatment with considerable detail on special cases of dimension in abstract spaces is given by Pears C81]. The Hausdorff dimension of a set is always at least as large as its topological dimension. Sets that are extremely irregular. such as nowhere-differentiable curves and surfaces. have Hausdorff dimensions which exceed their topological dimensions. For example. the Cantor set has Hausdorff dimension equal to lOGZ/log3. though its topological dimension is- 0. Moreover. the Hausdorff dimension of a set in Euclidean D-space can be a fractional value but is always less than or equal to D [51]. A fractal set process can generate a texture in a number of ways. Mandelbrot [671 exhibits some Brownian textures. These are simulations of mountain ranges Z=f(X.Y) over the X-Y plane such that every plane cut in a direction perpendicular to the X-Y plane gives an ordinary planar Brownian function. The displayed image is produced by simulating a Light source at an angle of 60 degrees 32 with the resultant shadow effects. and viewing angle of 25 degrees. The pictures look like irregular surfaces. such as lunar lanscapes. Other textured images can be obtained by dropping on a plane circles whose radii vary according to a random variable with a Pareto distribution. with the exponent in the density function playing the role of the Hausdorff dimension. Work is needed in the estimation of the fit between natural textures and fractal textures before fractal models can be utilized as true texture models rather than just pattern generation processes. In_ addition. further work is needed on the estimation of the Hausdorff dimension of stochastic processes. For the appropriate background see Billingsley C12]. [13]. 2.2.4 Random Mosaic Models A tiling or tesselation of the plane is a collection {A} of disjoint sets whose union is the entire plane. The elements of {A} are called cells. A mosaic is a tesselation combined with a function H from {A} to the finite set of gray levels {0.1.....G-1} which is constant on each cell: H is called the coloring function. 33 We may speak of random tesselations where the tesselations are determined by some random process or where the H function is probabilistic. for example controlled by a discrete Markov process. We generally only deal with mosaics on bounded sets; such mosaics can be achieved by taking a full planar mosaic and intersecting C with the bounded set and restricting the coloring function. Such a restriction is the true environment for the image processing applications. yet it is usually easier to deal with the theory in the infinite plane case and hope that the bounded set lattice is large enough to allow reasonable approximation. In a sense. the mosaic models generalize the standard notion of a digitized image. The pixels of an image correspond to the cells of a mosaic. but the mosaic models allow us to consider cells that are much larger and of different shape. Ahuja [2] makes a distinction between region-based models and pixel-based models. The appeal of the region-based models is that they have the virtues of the stochastic approach along with some of the strength of the placement paradigm in describing large primitives. For example. the bricks picture. Figure 1. is an example of a macro-texture appropriately described by a region-based model. The relatively fine-grained gravel 34 picture. Figure 2. is a micro-texture. best suited to a pixel-based model. The cells can be generated in a number of ways. We follow current literature [75]. E89]. E90] and discuss the possible patterns. (i) Random Checkerboard: A checkerboard is oriented at an angle 6 to the x-axis. (ii) Occupancy Model: Use any ‘spatial ,point process to generate a realization in the plane. Define the cells V(p). indexed by the points p of the realization by the relation: V(p) = {g on the planel d(q.p) minimal among b). Each point of the plane is a member of exactly one V(p) since the realizations have no limit points. This model is also called the Voronoi polygon model. (iii) Poisson Lines: Distribute lines isotropically over the plane using a Poisson process to generate the radii (distance from line to origin) and the angle the line makes with the x-axis. The polygons determined by the lines are convex and constitute the cells of the mosaic. 35 (iv) Bombing Patterns: Let B be a convex set (this restriction is not necessary but makes the process mathematically tractable). The set B is placed on the plane with random orientation at a point x which is determined by a "marked" Poisson process. Marking a process means that we enumerate each point in a realization and assign it a positive integer. We assume that the copies of the bomb B are of one color. say black. while the plane is white. The cells of the mosaic are then the components of the bombing process. After the bombing is over. the plane can be recolored using any coloring function for the components. (v) dohnson-Mehl: Points are dropped on the plane using a marked process and the cells are formed by growth from these "seed" points. Unlike the occupancy model. the resulting cells need not be convex. This model is appropriate as a physical model for crystal growth in metallurgical applications. but has proven to be mathematically intractable for expressing auto-correlations and other features. (vi) Dead Leaves: The dead leaves model is similar to the bombing model except that the boundary of the bombing shape is retained and the boundaries of previously dropped 36 "leaves" are removed. The final pattern resembles the appearance of leaves on the forest floor with many full outlines of the shapes visible and many partial shapes. This model is discussed by Serra C93]. The mosaic models discussed above can be subsumed into a more general theory of random sets called Mathematical Morphology. The theory is under continuing development by a number of European workers and has seen considerable application in the metallurgical area. See the work of Serra [92]. Matheron E71]. E72]. and Giger E403. Serra calls this general class of models Boolean models. The Boolean model starts with a realization of a Poisson process and takes each point to be a growth center. The primary grain is a random set. usually convex. the randomness being controlled by a growth process. It is clear that this very general growth process can include the above mosaic models. Algebraic operations. including the familiar operations of union. intersection and specialized operations called dilation and erosion. allow the specification of composite models. Special hardware is available to perform the set Operations along with the estimation of model parameters [63]. C91]. C95]. [96]. The advantage of some of the mosaic models is that the theoretical autocorrelations can be computed from a knowledge of the process parameters. By fitting the observed autocorrelation to the theoretical autocorrelation for the proposed model. features such as cell size distribution can be inferred without having to segment the image. Julesz [543 has found that the distribution of plateau regions of constant gray level is a very important consideration in texture discrimination. so any model that effectively models cell size contributes to our understanding of texture. 2.2.5 Syntactic Methods The syntactic approach to texture. like the stochastic methods. can be dichotomized into modelling and classification efforts. Ehrich and Foith E303. bolstered by the success of syntactic methods in waveform analysis. have used syntactic methods to encode textures as mountain ranges whose heights are associated with gray levels. The encoded texture can then be used in classification experiments. 38 Our notion of a model includes the capability to synthesize samples from a textural class. Lu and Pu [65]. take this approach and encode 9 by 9 squares of a texture as a primitive in a stochastic grammar and then link the squares together to form an image. Some success is reported in generating Brodatz E17] textures that have a fairly regular structure. such as the picture of reptile skin. We suspect that difficulty would be experienced in using this method to synthesize micro-textures such as sand or grass. Other problems include the extension to multiple gray levels. but the principal problem is the estimation (or in this context. grammatical inference) of the model parameters. 2.2.6 Linear Models Following a procedure analagous to a linear filtering model. Deguchi and Morishita E26] assume a texture model of the form: X('iyj) = A(D!G)X("D.1'O) 4' 5(191) (9.0) (not (090)) where X(i.j) is the gray level at point (i.j). and the 39 E(i.j) are i.i.d Gaussian variables with zero mean. The local neighborhood is a rectangle of dimension 2m+1 by 2n+1. The A(p.q) parameters are estimated by minimizing the expected difference between the estimated X(i.j) and the observed X(i.j). This approach is fairly similar to the classical analysis of Whittle [107]. but Whittle was only interested in estimating the parameters in an applied statistics context' for testing the hypothesis of no interaction between the site variables. When we begin an estimation problem. we do not know what value of m and n to choose. Hence. we must consider them parameters of the model which must be estimated. Deguchi and Morishita use a procedure due to Akaike [4]. E5] in a time series context to estimate m and n in an optimal manner. Textures following the above model can be generated by a filtering scheme. Generate independent Gaussian variables at each site. Then use the filter coefficients A(p.q) to create a new image by summing over the neighborhoods (it is. of course. possible to use an FFT algorithm to do this faster). The real values at each point of the lattice can then be quantized. 4o Deguchi and Morishita do not generate any textures from the above model. Their purpose is to segment the textured regions of an image. One example is the location of small regions. called "defects". whose texture differs from that of a background texture. To locate the defects. first estimate the A(p.q) parameters for the entire image. Since the defect regions are presumed small. they will not significantly influence the estimation of the A(p.q) parameters. The error between the predicted pixel values using linear estimation and the true value is calculated for each pixel in a 2m by 2n neighborhood. If the error exceeds a preset threshold. then the pixel is presumed to belong to the defect region. Variations on this theme are presented for other segmentation experiments. 2.2.7 Markov Models The term "Markov" is loosely applied to any model where the probability of any particular gray level at a site (i.j) does not depend on pixels beyond a "small" neighborhood of (i.j). We may express this by the relation: 41 p(X(i.j)=k|given all other sites) = p(X(i.j)=k|values at neighbors). The term "neighbors" is defined topologically and can be enforced as any configuration surrounding a given pixel. Following Besag [103. or Hammersley [443. a Markov‘ Random Field obeys the above neighborhood condition along with two other conditions. The first is called positivity and says that any assignment of colors to the lattice (integers in the range {0.1.....G-1}) has non-zero probability. The other condition is called homogeneity and says that the conditional probabilities are unaffected by the actual coordinates of the site: only the neighborhood values matter. The Markov Random Field model has been briefly investigated by Hassner and Sklansky E48]. [493. [50]. Their work was limited to an exposition of the equivalence between the Gibbs field and Markov Random Field expressions for the conditional probability distributions (see Spitzer [94] for the proof) and generation of a few examples of textures. Moreover. they limited their attention to the binary case. 42 An alternative to the use of the full two-dimensional Markov Random Field for images is to traverse the lattice along a scan line and provide a direct analog to the usual Markov chain [1]. Connors and Harlow E24] generated textures according to a simple Markov chain on the rows. which produces streaky line textures but ignores the correlations between pixels in neighboring rows. Haralick and Yokoyama E110] generated essentially one-dimensional textures using scans. but provided some correlations between neighboring rows by considering changes in the features computed from the co-occurrence matrices. 2.3 Summary We have defined a texture model to be a process capable of generating or describing a texture. The types of processes capable of modelling texture were delimited as knowledge-based descriptions. stochastic processes. and feature-based descriptions. We concentrated on the middle level stochastic process models and surveyed the models available. These include discretized continuous models. time-series. fractals. random mosaics. syntactic methods. linear models. and Markov models. Each model was found to be useful for certain classes of textures. It is as inappropriate to assume that one class of generation procedures can generate all textures as it is to assume that the Gaussian distribution can explain all data. CHAPTER 3. MARKOV RANDOM FIELDS 3.1 Introduction The brightness level at a point in an image is highly dependent on the brightness levels of neighboring points unless the image is simply random noise. In this chapter. we explain a precise model of this dependence. called the Markov Random Field. The notion of near-neighbor dependence is all-pervasive in image processing. Focusing directly on this property is a promising approach to the overall problem of micro-textures. The Markov Random Field has had a long history. beginning with Ising's 1925 thesis [53] on ferromagnetism. Although it did not prove to be a realistic model for magnetic domains. it is approximately correct for phase-separated alloys. idealized gases. and some crystals [77]. The model has traditionally been applied to the case of either Gaussian or binary variables on a lattice. Besag's paper [103 allows a natural extension to the case of variables that have integer ranges. either bounded or unbounded. These extensions. coupled with estimation procedures. permit the application of the Markov Random Field to image and texture analysis. 44 45 3.2 Definitions and'Theorems Our exposition follows Besag C101 and Bartlett [7]. As before. let X(i.j) denote the brightness level at a point (i.j) on the N by N lattice L. We simplify the labelling of the X(i.j) to be X(i). i = 1.2.....M where M 1: Let L be a lattice. A c lorigg f L “-6-.— (or a go oging g: L with G Levels) denoted X is a function from the points of L to the set {0.1.....G-1}. The notation Q denotes the function that assigns each point of the lattice to 0. Before defining a special type of probability on the set of all 1. we first give the notion of neighbor. Note that the definition does not imply that the neighbors of a point are necessarily close in terms of distance. Definition 3.2: The point j is said to be a agigflggg of the point i if p(X(i)IX!1).X(2).....X(i-1).X(i+1)....X(M)) depends on X(j). 46 Now we can give the definition of a Markov Random Field. ngini iog 333: A Mggkgg Rand m ielg is a joint probabili y density on the set of all possible colorings K of the lattice L subject to the following conditions: 1.Positivity: p(§) > O for all X- 2.Markovianity: p(X(i)l All points in lattice except i) = p(X(i)l Neighbors of i) 3.Homogeneity: p(X(i)| Neighbors of i) depends only on the configuration of neighbors and is translation invariant (with respect to translates with the same neighborhood configuration). We would like to delimit insofar as possible the kind of probability distributions that represent Markov Random Fields. This is the content of the Hammersley-Clifford theorem. We first need a definition. Definition 3:4: A gliggg is a set of points that consists of either a single point or has the property that each point in the set is a neighbor of every other point in the set. 47 It will prove to be convenient to consider the distribution function in terms of the ratio of p(5) to p(Q). Define the quantity 0(5) by: (3.1) m1) = Ln0 for all j \ b. q(j) = 1 3 \ c. q(i)p(i.i) = c(i) / i Under these conditions we have 1.Each state S(i) is positive 2.The set {q(i)} is unique is satisfying a. QbO’C. 3. lim p(niiyi) = q(j) = 1/m(j.j) n->°° conditions 73 95931: See Feller (p393. [313). D Theorem 4.1 justifies the use of Limiiigg gigigibgiigg as a description of the set {q(i)}. we describe a procedure for transforming a given Markov chain with transition matrix P* = {0*(i’i)} to another chain with transition matrix P = {p(iqj)} such that the new chain has limiting distribution {0(1)}. Ihggggm gig: Consider a symmetric, aperiodic. irreducible Markov chain with transition matrix P*. Let {d(j)} be a set of positive numbers with sum 1. Then the Markov chain with transition matrix D has limit distribution {0(1)}, where P is defined by: o*(i.i)q(i)/q(i) if q(i)>q(i) p(ivi) = p*(iyi) if q(i)2q(i) \ p(igi) = p*(i9i) + o*(i,i)(1 - q(i)/q(i)) / where the ' on the summation means summation over all indices j with q(j)/q(i) less than 1. 74 95991: See Hammersley [433. D To apply theorem 4.2 to the problem of generating a sample from a Markov Random Field. we need to identify the constituents of the Markov chain. The relevant pieces are: gigig sgi: All colorings X of the lattice L. Maigii 31: p*(i.j) = 1/2. 2 is the total number of colorings. igiiii: The limiting distribution value for the state i should be p(X). where p(.) is the joint probability mass function over the set of all colorings. In chapter 6, we will study the joint probability formulation of a Markov Random Field in detail. The expression is unwieldy but we do not actually need to use it. because the actual numbers {q(i)} are never needed in the calculation of the p(i.j) in theorem 4.2; we need only examine the Set of ratios {d(j)/q(i)} = {v(i)/0(1)}. Following Besag [10]. we have 75 l-i heore 33;: Let 5 and i be two colorings of ithe Markov Random Field lattice L. Then: M p(I) p(X(i)=Y(i)IX(1)9X(2)9...,X(i-1)9Y(i+1)ooo.Y(N)) p(X) p(X(i)=x(i)|X(1),X(2)9...,X(i-1)9Y(i+1)g...Y(N)) 1 ggggiz‘See Besag [10], p195. D In general, we are interested in textures with the same number of pixels at each gray level. Such textures are the output of a histogram-flattening procedure such as the Equal Probability Quantizing algorithm described by Haralick [453. It is therefore appropriate to limit our state set to those colorings 3 which have a uniform histogram. In practice. this is done by starting with an image that is generated by coloring the point (i.j) with level k. where k is chosen with equal probability from the set £09192.....G-1}. The convergence to the limit distribution is unaffected by the choice of initial configuration: only the rate at which equilibrium is reached depends on the choice of the initial configuration. Given a state (i.e. colorino ) X! we choose the next X except that the gray values of state 1 to be the same as two randomly selected points are interchanged. In the 76 notation of theorem 4.2. all p*(1.j) are equal. so~we need only look at q(j)/q(i) = p(1)/p(z) = r.' The algorithm is diagrammed in Figure 12. This algorithm was used by Flinn C333 and was invented by Metropolis et al. [733. Any initial assignment of gray levels to the points of the image can be made. One possibility is to choose the next state 1 as 5 with one pixel changed at random. This allows us to begin with any histogram whatsoever and reach states {S(i)} with the desired frequency. The other side of this problem is that the choice of parameters of the Markov Random Field determines the expected histogram. This means that if we arrange to make the histogram to be uniform when. in fact. the parameters do not determine a Markov Random Field with a uniform histogram. the procedure will converge to a Markov Random Field with different parameters than intended. In a practical sense. this is not a significant problem since we usually want to generate a texture that resembles a given texture. He can generate a texture starting with exactly the same histogram as the given texture and use the measured parameters from the sample. 77 until STABLE choose two sites X(1). X(2) with different gray levels compute p(z)/p(§) = r switch X(l) get random number 2 and X(2) 1 V ... + ...—..-.— 4y —__.——__ it -—..._.——_. 4....-—_. +>——._... 9—“... 4y I switch X(l) I and X(2) l I 4l._..—.———._.—-—_-—————.———-——.——-———-——.———-———_—_—.——__._——_ it 4}———————_——.—.——————_ 4..._—_._.—- .0.._—_ .p———.—. .0. 4|._____ + _..____._. 4y _____..._ 4y 1>—--‘—-—- Eigggg lg Algorithm for generating Markov Random Field with joint probability function p(z). The coloring I is obtained from the coloring X by switching the values of the points X(l) and X(2). 78 4.4 Convergence Properties Theorem 4.2 guarantees that the application of the algorithm in Figure 12 will eventually result in a lattice in a state i with the frequency controlled by 9(1). The practical question is how long this will take. We first need to define a time-dimension for the simulation. Suppose the lattice is N by N and let M=N**2. We consider M attempted exchanges or switches to constitute one iiggaiigg. Notice that this ignores attempted exchanges between pixels of the same color. We have experimental guidelines for the number of iterations required to achieve a lattice that matches the input parameters. In general. it was observed that in 10 iterations or less either the number of changes per iteration drops to one percent of M or the measured parameters match the input parameters within about 5 percent. These guideleines define the variable "STABLE" in Figure 12. On a PDP-ll/34 computer. the time required for one iteration on a 64 by 64 image was two to three minutes depending on the number of gray levels. 79 We give an example of the convergence for a specific case. We want to simulate a first-order Markov Random Field with binary variables with parameters a = -z. b(1..) = 1 on a 128 by 128 lattice. The notation follows equation (3.11) of chapter 3. The estimated parameters b(1..) 'are shown plotted against number of iterations in Figure 13. The value of the parameter a is not shown because. as will be proven later. in the uniform histogram case. a is -2b(1..). The graph flattens rather quickly and stays within 0.05 of the intended value of 1.0 for b(1..). Figure 14 shows the number of changes observed per 256 attempted exchanges. as the estimates were made every 1/64 iteration. Thus. although in an iteration of M attempted exchanges we are still observing nearly M/2 changes. the chain is near equilibrium as the observed model parameters are within a small tolerance of the intended parameters. 80 LL: IMHT F—o C3¢ E 0 _ 5.] ‘ ‘00 Eigggg lg: Convergence of b(1..). 81 JHHMHHWWWWHP _ _ _ ootoom ooiowfl oa,ocfl 00.0mm 00 am a: om_ wmozqzu 3 DJ E. u Pu a a . a. m3 Exchanges. Behavior of Number of 82 4.5 Examples of Textures We present some examples of textures generated according to various settings of Markov Random Field parameters. These images are representative of the kind of results that can be achieved but are not necessarily attempts to imitate real textures. They should rather be considered to be an 'alphabet' of Markov RandOm Field textures. In chapter 5. we exhibit generated textures matching observed textures. (i) Clustering effects Figure 15 shows a series of 64 by 64 binary textures with various degrees of clustering. This is an isotropic. first-order model as represented by equations (3.6) and (3.7). Figure 15a represents binary 'noise' in the sense that each pixel has probability .5 of being black and .5 of being white independently of all other pixels. In Markov Random Field terms. this means a is 0 and b(1.1) = b(1.2) = 0. The value of b(1.1) is increased from 0 in Figure 15a to 3.5 in Figure 15h. The increase in clustering is clearly visible. 83 (ii) Anisotropic Effects Figure 16 shows extreme anisotropy in first-order and second-order models on a 64 by 64 lattice. In Figure 16b. a = -2.0. b(1.1) = 1.93. and b(1.2) = .16. The quantity b(1.1) controls the horizontal clustering so there is a large amount of line-likeness in that direction. As b(1.2) is non-negative. a small amount of vertical clustering is present. resulting in thickened and noisy horizontal lines. Contrast this with Figure 16a. which has parameters b(1.1) = -2. and b(1.2) = 2.1. The value of b(1.2) causes vertical clustering. similar in intensity to the horizontal clustering of Figure 16b. The significant difference is that the negative value of the parameter b(1.1) forces 'clean' vertical lines with virtually no horizontal clustering. The decidedly diagonal effect of Figure 16c results from the use of a second-order structure. The clustering in the Nw-SE direction is pronounced since the parameter in this direction is 1.9 while the parameters in all other directions are quite small. 84 (iii) Ordered Patterns Many of the applications of the Ising model involve studying the checkerboard-like patterns obtained with negative clustering parameters. In this sense. a perfect checkerboard is ordered and represents a limit state for a an alloy or magnet [77]. This is illustrated by Figure 17. which has b(1.1) = -2.25. b(1.2) = -2.16 on a 64 by 64 lattice. The most likely configuration is a black pixel surrounded by four white pixels or vice versa. (iv) Attraction-Repulsion Effects An attraction-repulsion process involves ' having low-order parameters positive resulting in clustering but high-order parameters negative in order to inhibit the growth of clusters. If high-order parameters were also positive. large clusters would result. whereas negative high-order parameters yields small clusters. Figure 18 shows the effect of anisotropic clustering with inhibition. The first-order parameters of Figure 18a are approximately 0. which accounts for an immediate visual impression of randomness. On closer examination. there are many short horizontal and vertical lines. but 85 very -few diagonal joins. The lack of diagonal joins is a result of negative second-order diagonal parameters. In Figure 18b. the first-order clustering parameters b(1.1) and b(1.2) have been increased. resulting in longer horizontal and vertical lines. Figure 19 shows two isotropic attraction-repulsion textures. These are the result of positive first and second-order parameters and negative third and fourth-order parameters. As a consequence of 'the high-order inhibition. the cluster size is relatively smaller than one would expect if the third- and fourth-order parameters were zero. (v) Multiple Gray Scale Textures The binary textures above illustrate the essential features of the visual attributes of a Markov Random Field but are fundamentally unrealistic as textures. We now turn our attention to the binomial model. We follow the notation of section 3.5. It should be noted that many of these images appear blurry and out of focus. This effect is not due to the reproduction process but is intrinsic to the model. If 86 there is no inhibition (via negative high-order parameters). then the binomial model tends to have smooth transitions from black to white. The binomial distribution is unimodal and. as a consequence. values above and below the mean gray value are highly probable also. This results in a tapering of the gray scale around maxima and minima. Such a tapering as one moves away from black or white points has an effect similar to a neighborhood averaging or low-pass filter. Figure '20 shows a 4-gray level picture with considerable clustering. Figure 20a is isotropic and first-order. whereas Figure 20b is second-order anisotropic with diagonal clustering. Figures 213 and 21b represent typical multiple gray scale pictures with isotropic fourth-order clustering. Figure 22 shows a pattern similar to Figure 16. but with 32 gray levels. The resemblance to wood-grain is apparent. Figures 23a and 23b show the result of attraction-repulsion processes with multiple gray levels. Figure 23a has the appearance of reticulated photographic film due to strong third and fourth-order inihibition. The diagonality in Figure 23b is a result of strong repulsion in some directions and clustering in others. 87 55:51:? Eigggg ii: Isotropic First Order Textures. The b(1..) parameters are: _(§_)_ 0.0. La; 0.50. igi 0.75. gg; 1.1. 121 1.26. ii; 1.52. igi 1.79. ihi 3.0. In all cases. the a parameter is -2b(1..). 88 Eigggg i6: Anisotropic Line Textures. The parameters are igi a: -0.26. b(1.1) = -2.. b(1.2) = 2.1. b(2.1) = 0.13. b(2.2) = 0.015. ibi a: -2.04. b(1.1) = 1.93. b(1.2) = 0.16. b(2.1) = 0.07. b(2.2) = 0.02. (c) a = -1.9. b(1.1) = -0.1. b(1.2): 0.1 . b(2.1)= 1.9 . b(292)= '000750 Figure i1: Ordered Pattern. The parameters are a = 5.09. b(1.1) = -2.25. b(1.2) = -2.16. am?" “'I[ iagonal Inhibition Textures. The parameters .19. b(1.1) = -0.088. b(1.2) = -0.009. b(2.1) are 2g: 3'- : -1. b(2.2) 2.05. b(1.2) Figure 1 : D ‘ 2 -1. (b) a =0.16. b(1.1) = 2.06. b(1.2) = '2.03. b(2.2) = -2.10. Eigggg 19: Isotropic Inhibition Textures. The parameter values EFe: 1a; a :-o.97. b(1..) = 0.94, b(2..) = 0.94. b(3..) = -o.42, b(4..) : - -o.49. 5g; a = -4.6, b(1..) 2.52, b(2..) = 2.17. b(3..) = -0.78. b(qyo) = ”0.850 90 Eigggg gg: Clustered Textures with 4-Gray Levels. The parameters are (a) a = -2. b(1..) = 1.0. 3g; a = -2. b(1..) = 1.0, b(291) : 1.0 b(2’2) = 0000 Eigggg 2i: Clustered Textures with 16 and 32 Gray Levels. The parameters are igi 16 levels. a = -2.0. b(1..) = b(2..) : b(3..) : b(4..) = 0.05. 1g; 32 levels. a = -2009 b(1..) : b(290) = b(3..) : b(490) : 0.050 91 Eigggg 22: Horizontal Texture with 16 Gray Levels. The parameters are a = -2.0. b(1.1) = 0.08. b(1.2) = 1.0. Eigggg 23: Attraction-repulsion Textures with 16 Gray Levels. The parameters are igi a = -2. b(1..) = b(2..) : 029 b(390) = b(4oo) : ”001. b) a = ‘2! b(1,.) 30029 5.-.. b(291) ‘ '202. b(292) = .2. b(391) = '0.059 b(392) = 0.059 b(4.1) = -0.05. b(4.2) = 0.05. 4.6 Summary We have reviewed the notion of a Markov chain and seen how to obtain a new Markov chain with desired limit distribution from a relatively arbitrary chain. This construction led directly to an algorithm for the generation of Markov Random Fields with specified parameters. An example of the convergence of the procedure was given. along with some guidelines on the number of' iterations required to obtain a Markov Random Field with the desired parameters. Finally. we presented a catalog of textures generated according to various settings of the model parameters. CHAPTER 5. MODELLING OF NATURAL TEXTURES 5.1 Introduction In previous chapters. we have discussed the probabilistic structure of Markov Random Fields and have shown how samples from Markov Random Fields can be generated. One of the principal contributions of this thesis is the implementation of a statistical measure of the correspondence between an observed texture and a texture model. No prior study has performed this kind of evaluation. All prior studies in texture modelling have considered a model adequate if its parameters yielded good classification in pattern recognition experiments or if it was found to be the best-fitting among a number of models tested. For example. Deguchi and Morishita E263 determine the best size for a neighborhood in an auto-regressive scheme. but do not give any overall guidelines on when the auto-regressive scheme fits the observed texture. We first explain the method used to estimate the Markov Random Field parameters and perform hypothesis tests. This is followed by the results of testing textures from the Brodatz texture album [173 for a fit to various Markov Random Field texture models. The final 93 94 section shows textures generated synthetically in an effort to match natural textures. 5.2 Estimation of Parameters Following the notation of equations (3.12) and (3.13). this section explains the estimation of the parameter set {b(i.k)} from a textured sample using the binomial model. The binary model is a special case of the binomial model and is not handled separately. The technique used to estimate the parameters is Maximum Likelihood Estimation. Let p(Xl.) denote the conditional probability p(X=xl Neighbors of X). where X is a point of the lattice L. The usual log likelihood is given by (5.1) l = ln(p(X|.)) where the summation extends over all points of the lattice. 95 It is difficult to maximize l as stated in equation (5.1) since the summands are not independent. Besag [9] provided a solution to this problem. Instead of forming l as a sum over all points of the lattice. the lattice is partitioned into disjoint sets of points called g_gigg§. Each coding is chosen so that its points are independent. This can be done by adequately spacing the X points so that if X(i) and X(i) are two points in a coding. then X(i) is not a neighbor of X(j) in the Markov Random Field sense. The number of codings required depends on the order of the process. We would like each coding to be as large as possible because the larger the coding. the more samples are available to estimate the parameters. A first-order process requires at least two codings for estimation purposes. as shown in figure 24. A second-order process requires spacing so that three by three neighborhoods do not interfere. This yields four codings as shown in Figure 25. Third- and fourth-order processes require separation of three units since they are based on five by five neighborhoods. as shown in Figure 26. There are nine codings in this case. 96 III:IATIII:IAYIII:IA+IIIiIATIIIIIA+IIIII¢ IIIII¢ _ 2 1 2 1 2 1 n 2 . III¢ Illll¢ Iii... III.. III... I'll." III._. 1 2 1 2 1 2 _ 1 _ IIII¢ III-... III... III.. IIIAT III... IIIt. 2 1 2 1 2 1 2 I'll: IIIAT ill: ill... Iii-vii. I'l'lAv 'liav 1 2 1 2 1 2 1 III-IA. Ill-Ii. I'll: ill... .Illullli. IIIAv III... 2 1 2 1 2 1 2 I:IIL.I:IILTIIIILTIIIIL+IIIIL+IIIiLvliIILT 1 2 1 2 1 2 1 . . IIIII1+IIIIILvl|iZIAvIII:I1+IIIII.+IIIIIATIIIII¢ . . 2 — 1 2 1 . 2 1 - 2 . . . ii|+ Iiii. iI'Av iii... iiiav iii... ilixv _ . . 1 . 2 1 2 . 1 2 . 1 . . . III... III¢ IIIAT III+ III¢ III+ III¢ . _ . 2 - 1 2 1 . 2 1 - 2 . . _ Iii+ Iiit. Ilia. IIIII+ Illi¢ III.’ III._. . — . 1 - 2 1 2 _ 1 2 _ 1 . _ _ III... III-IA. III.. III.’ IIIAT III+ IIIAV are two There I I I + I I I 2 1 I I I 1 I I I Pattern. 2 I I I 1 Coding A v I 1 l 2 I g 23 First-Order gs labelled 1 and 2. 2 +-—-+--—+---+-_—+---+---+—--+---+---+—-_+ _--¢---+---+---+- £192: codin I I I I I I 97 IIII :- 'IIII4 IIIILY IIIIlv Ill-Ill! t4 III: I'll. AV Illllll AT IllzlAvIIIllL I'll'l AT I'll; III:IATI:II|A IIIIIA IIIA 2 III._ 1 IIIA 2 III:IA -—-+-—-+---+--—+---+ 1 IIII|+ IIIIIL T T Y 1 7 Y T v IIIIII¢ IIIII¢ ..J 'IIII¢ III ¢ IIIIIA 4 +---+---+---+-- I I 3 I 2 I 1 2 +-—-+---+_--+---+—--+—--+-—-+-—-+--—+_-- IIIII¢ IIIIiv I I I 3 I I I +-—-+---+-—-+_- 4 3 4 3 4 4 3 T IIIII+.IIII.+.IIII.+IIIII - 2 . . 'II. + IIIII¢ III: III: I'l'|¢ 4 llllll: 1Q 2 I I I +---+---+---+---+_-—+_--+---+---+---¢--- I I 1 I 4 +---+---+---+---+_-_+---+_--+---+-——+-—-+ There are four 0 n r e t t a P g n .1 .d 0 I PV4 ' r 3 e d 9 P 2 O . 9 d 1 n 0 d C e P... Q.[ e by 5.3 9;I~ S 8.9 P-n UT... Qfic i_0 F_C 98 I:III¢ IIIII¢ IIIILv II" 47 III Av IIIILT IIIII¢ IIIILT IIII;V IIIILT IIIII+IIIII¢ 7 I I I 7 I 8 I I I I I I I I 9 I I I 8 I I I 7 9 +---+---+--_+_-—+_-—+---+---+-—-+--_+--- I I I 7 I 8 I I 1 3 2 III" III" I I I 2 I 3 I I I I 1 I 3 ¢ ¢ ¢ ¢ A w— +---+---+-_-+---+- IIIILV IIIILT I I I . IIIILY IIII+ IIIII¢ IIIILV IIIILv IIIILT IIIILT IIII;T IIIIL+ IIII; III:IA III:IA IIIIIA IIIIIA IIIIIIA IIIIL IIIIA IIIIIA IIII; IIIII: T v T v I I I 7 I 8 I I .L v +---+---+---+_- IIIII¢ IIIILV xv IIII¢ IIIIIAY IIIII¢ Ill]; 7 I I I +---+---+---+---+— There or Fourth-Order Coding Pattern. 5192:: aé Third- are nine codings LabeLled 1-9. 99 The actual estimation procedure is straightforward. Let [(i) be the log likelihood for the ith coding? (5.2) [(i) = ln(D(XI.)) XV where the summation extends over all points X' in the coding i. In equation (5.2), p(XI.) depends on the order of the Markov Random Field whose parameters are being estimated. We seek to maximize l(i). This is done by finding values of the parameters a and {b(i.k)} so that (5.3) Blli)/Ba = 0 and alli)/bb(jgk) = 0 for j = 1,29,...gr and k : 1.2 where r is the order of the process. If the process is isotropic at some order i. then we only consider derivatives with respect to b(jq.) in equation (5.3). The system of equations (5.3) is solved numerically by the usual multivariable extension of Newton's method [52]. We omit the routine expression 4or the derivatives 100 in equation (5.3) and the second partials that are needed in Newton's method. The stopping criterion for the iteration process was fifteen iterations. or a change in the magnitude of successive parameter estimate vectors of less than 10E-06. Except for a few cases among the natural and synthetic texture samples. ten iterations sufficed to provide a residual of less than 10E-06. This is fortunate. since each iteration of Newton's method in the multivariate case effectively requires the inversion of a matrix of size equal to the number of parameters, which could be as many as nine for fourth-order anisotropic textures. An estimate of the parameter vector is obtained for each coding. Our final estimate of the parameters is the average value over all the codings. On a POP-11/34 computer an unoptimized estimation procedure requires thirty seconds per coding for binary textures and eighty seconds per coding for eight gray level textures. These timings are averages for textures of size 64 by 64. 5.3 Hypothesis Testing Note that we really have only one sample from the unknown distribution p(X) on the set of colorings of the 101 lattice L. From the conditional probability point of view. each observed configuration of neighbors and the value of the center point X is a sample. In this sense. we have M = N**2/k samples of the conditional density p(xl.) for the N by N lattice L. where k is the number of codings. We can then perform a chi-square test of the fit between the expected frequencies for each center pixel and the observed frequency. The expected frequencies are computed using the estimated parameters with an appropriate reduction in degrees of freedom. An example of a chi-square test is shown in Figure 27. The null hypothesis is: H0: The texture is a sample from a Markov Random Field with the estimated parameter set {a.b(i.k)} while the alternative hypothesis is simply the negation of H0. The estimated parameters for the example shown in Figure 27 are a = -4.26. b(1.1) = 2.70. and b(1.2) = 1.5. The number of cells is G. the number of gray levels. times the number of observed neighborhood configurations. The example is a first-order. anisotropic binary lattice. so there are 2*9 cells possible and all were observed. The entries in the table are of the form 'observed(expected)' and the expected entry is computed using the conditional 102 probability distribution with the estimated parameters. The degrees of freedom are computed by means of the formula: (5.4) df = (G-1)*Nc - E where G is the number of gray levels. No is the number of neighborhood configurations (in Figure 27. each neighborhood configuration is a row). and E is the number of estimated parameters. In the example of Figure 27. there are two gray levels. nine neighborhood corfigurations and three estimated parameters. so we have (2-1)*9-3 = 6 df. We also use the convention of having at least one expected observation per cell. Thisresults in a reduction in the number of cells and degrees of freedom. Since we are performing a number of tests on the same data (one on each of k codings). there is a great likelihood of having the hypothesis of a fit to a Markov Random Field scheme accepted on some codings and rejected on others. The results of the tests are not independent. If they were independent. and we performed k tests at a level a . then the probability of no rejections would be (1' d )**I(o 103 s<1.1) 5(1.2) x = o x = 1 I o I--- o I 525( 621.)I 5( 9.)I I o I 1 I 240( 244.)I 20¢ 1e.)I I o I 2 I 14( 17.)I 8( 5.)I I 1 I o I 79( 80.)I 18( 17.)I I 1 I--- 1 I 93( 91.)I 85( 87.)I I 1 I--- 2 I 21( 14.>I 52< 59.)I I 2 I o I 4( 3.3I e< 9.)I I 2 I--- 1 I 12: 17.)I 244< 239.)I I 2 I--- 2 I ‘8( 8.)I 512< 512.)I -r 7 Ficure 21 Example of a Chi-Square Test. This is a binary 64 by 64 texture. A first-order anisotropic scheme was fitted. The results of coding number 1 are shown above. Chi-square is 12.30957. on 6 df. Besag [10] suggests a conservative solution to the problem of ambiguous results. Suppose the most significant result we observed over k codings was exactly at level p. The overall significance of the set of tests is then taken to be kp. For example. in a first-order isotropic scheme we obtained two chi-squared values of 7.78 (p=0.10) and 11.3 (p=0.01) on 3 df. The value 11.3 104 has exact significance level of 0.01. Since there are two codings. we take our overall significance level to be exactly 0.02 = 2*0.01. and would reject the null hypothesis at the 5 percent level. In the tables in section 5.5. we have given the number of "conservative" rejections at the five percent level for each scheme along with the number of samples of each texture that had 091.....k rejections over k codings at the five percent level. This second tabulation leads to a "liberal" rejection policy of rejecting a Markov Random Field fit if any coding is rejected. 5.4 Description of the Data The study of natural textures was based on twelve pictures from the Brodatz texture album [17]. The plates used are given in Table 1. Each plate was photographed on 35mm film to form 24mm by 36mm slides. The slides were digitized in such a way that the small dimension occupied slightly over 256 pixels of the 480 by 640 image of Spatial Data Eyecom system. The 256 by 256 images were split into sixteen non-overlapping 64 by 64 subimages and also into four 128 by 128 non-overlapping subimages. The gray scale of each subimage was reduced from 256 gray 105 levels to both two and eight gray levels using Equal Probability Quantizing E453. Table 1: Textures ref Name Brick Hall Ceiling Tile Pressed Cork Calf Fur Grass Lawn Handmade Paper pebbles Beach Sand Straw Screening Water (1) Hood Grain Wood Grain (2) 106 Used in the Study. r to the Brodatz texture album [173. 312:: flames: D94 D86 04 D93 D9 031 029 069 D70 The plate numbers 107 5.5 Evaluation of the Fit The textures were evaluated for their fit to various models. The purpose of this analysis was twofold. First. we need to validate that the Markov Random Field model is generally applicable to 'textured images. The second objective is to formulate some general guidelines {on how to choose an appropriate model. in terms of order and the degree of anisotropy and isotropy. to generate specific types of textures. 5.5.1 Binary Texture Results Except for the screen texture. some first- or second-order model was able to give at least ten acceptances. under the previously mentioned conservative decision rule. for each texture sample. Detailed analysis of the screen texture samples showed very few distinct neighborhood configurations. This is a consequence of its regularity. The few neighborhood configurations dominate the computation of the Markov Random Field parameters. However. the low frequency neighbor probabilities are not properly controlled by these parameters. resulting in large chi-square values. Essentially. the histogram is so skewed toward these configurations that the positivity ‘108 condition of section 3.2 is nearly violated. As an example of this. Figure 28 consists of 64 repetitions of a random sixteen by sixteen pattern. It was analyzed on the basis of first- and second-order isotropic and anisotropic models. Because' of the repetitions. there are very few different configurations of neighbors. ”nly 42 different ones appear out of a possible 81 in a second-order anisotropic scheme. Chi-squared values are in the range 1000-3000 on 20-40 degrees of freedom. depending on the model. The estimated parameters vary wildly from coding to coding. For example. on a second-order anisotropic scheme. the parameter a was estimated as 0.02. 0.8. -0.243. 0.325. The b(1.1) estimates were 0.376. -0.469. +0.469. and -0.567. Similar variability was present in all the parameters. Tables 2 through 9 give the results of testing binary texture samples under a number of models. A test against a first-order model results in two hypothesis tests. one for each coding. There are sixteen subimages of each texture and each may be rejected on zero. one. or two codings at the five percent level. The number of subimages which had each number of rejections is recorded 109 in the last three columns of tables 2 and 3. Also listed is the number of conservative acceptances. of which there are a maximum of sixteen possible. For an appreciation of the difference between the conservative and the liberal rule. compare the number of conservative acceptances with the number of subimages which had no rejections. Tables 4 through 9 parallel the format of tables 2 and 3 except that they represent tests performed using the second-order codings. There is a possibiity of zero. one. two. three. or four rejections per subimage. as there are four codings. Besag [10] makes the point that one cannot compare the fit of a second-order model to the fit of a first-order model unless the same coding scheme is used in both cases. From Tables 2 and 3. it would appear that the first order scheme fits very well. but in many cases it is inferior to a second-order scheme when considered on the same coding. Table 10 gives the best results on second-order coding for each of the binary textures. The general good fit of the first order model should be reconciled with the fact that there are only two codings rather than the four for a second-order scheme. which means that fewer rejections are likely. 110 ifiifiit’? ngHImI \_I-r 1‘1- 'filv "Iv: 4- -. . '-. 41 Figure 28: Non-Markovian Periodic Texture. This is a 64 by 64 section of a 128 by 128 texture. The basic pattern is 16 by 16 and is repeated 64 times over the image. We have limited our attention to the case of 64 by 64 textures. Although third-order estimates can be made which give good visual results in texture generation experiments explained later. we cannot reliably perform a chi-square test of them on the 64 by 64 lattice. The number of cells with only one member is very large since the number of possible cells with a fully anisotropic third-order model is 729 while there are only about 585 in a single third-order coding (there are 9 codings in all). 111 Our preferred choices for the best-fitting model are based on a simple rule: choose the model that gives the We would not consider a fit to be adequate unless the majority of samples from the texture class fit the model. 112 Table 2: Isotropic. First-Order. Binary Tests. The parameters estimated are a. b(1..). Texture Name Conservative Rejections at 0.05 level Acceptances g 1 2 _ Brick 14 10 6 0 Ceiling Tile 10 9 4 3 Cork 14 12 3 1 Fur 5 2 11 3 Grass 15 12 3 1 Paper 16 12 4 0 Pebbles 14 10 6 0 Sand 15 14 1 1 Screen 0 0 2 14 Water 10 9 7 0 Wood (1) 9 8 8 0 Wood (2) 9 6 9 1 113 Table 3: Anisotropic. First-Order. Binary Tests. The parameters estimated are a. b(1.1). b(1.2). Texture Name Conservative Rejections at 0.05 level Acceptances Brick ' 11 11 5 0 Ceiling Tile » 11 6 7 3 Cork 11 10 5 1 Fur 6 5 8 3 Grass 13 11 4 1 Paper 13 13 3 0 Pebbles 11 9 5 2 Sand 15 12 3 1 Screen 1 0 5 11 Water 8 8 7 1 Hood (1) 9 7 4 5 Hood (2) 4 2 9 5 114 Table 3: Isotropic. First-Order. Binary Tests. on second-order spacing. The parameters are a. b(1..). Texture Name Conservative Rejections at 0.05 level Acceptances Brick 16 13 3 0 0 0 Ceiling Tile 16 11 4 1 0 0 Cork . 14 12 3 1 0 0 Fur 11 8 3 5 0 0 Grass 15 11 4 1 0 0 Paper 15 14 2 0 0 0 Pebbles 14 10 6 0 0 0 Sand 14 12 4 0 0 0 Screen 0 0 1 1 5 9 Water 11 10 2 3 1 0 Wood (1) 13 10 6 0 0 0 Hood (2) 13 6 9 1 0 0 115 Table 5: Anisotropic. First-Order. Binary Tests. on second-order spacing. The parameters are a. b(1.1). b(1.2). Texture Name Conservative Rejections at 0.05 level Acceptances Q 1 2 3 5 Brick 9 6 8 2 0 0 Ceiling Tile 15 11 4 1 0 0 Cork 12 10 4 2 0 0 Fur 10 9 3 3 1 0 Grass 16 11 4 1 0 0' Paper 14 10 6 0 0 0 Pebbles 11 9 1 6 0 0 Sand 14 10 5 1 0 0 Screen 2 0 2 3 6 5 Water 11 9 6 1 0 0 Wood (1) 12 7 7 2 0 0 Hood (2) 11 3 10 3 0 0 116 Binary Tests. The parameters are a. b(1..). b(2..). Texture Name Conservative Rejections at 0.05 level Acceptances 1 2 _ 3 Brick 5 1 3 7 3 2 Ceiling Tile 12 9 4 2 1 0 Cork 11 6 6 4 0 0 Fur 12 7 8 1 0 0 Grass 13 12 3 1 0 0 Paper 11 8 6 2 0 0 Pebbles 11 , e 6 2 2 0 Sand 14 9 5 2 0 0 Screen 0 0 3 0 2 11 Water 12 7 5 3 1 0 Hood (1) 10 5 8 3 0 0 Wood (2) 10 7 6 1 2 0 117 1292; 1: First-Order (Isotropic). Second-Order (Anisotropic) Binary Tests. The parameters are a. b(1..). b(2.1). b(2.2). Texture Name Conservative Rejections at 0.05 level Acceptances g 1 2 3 3 Brick 5 3 6 4 3 0 Ceiling Tile 13 10 5 1 0 0 Cork 14 11 5 0 0 0 Fur 10 7 8 1 0 0 Grass 15 11 5 0 0 .0 Paper 13 12 4 0 0 0 Pebbles 11 9 4 0 2 1 Sand 14 12 4 0 0 0 Screen 3 3 1 1 11 0 Water 13 11 4 1 0 0 Wood (1) 13 9 5 2 0 0 Wood (2) _ 12 11 3 1 0 0 118 122;; 8: First-Order (Anisotropic). Second-Order (Isotropic) Binary Tests. The parameters are a. b(1.1). b(112)’ b(29o). Texture Name Conservative Rejections at 0.05 level Acceptances g 1 2 2 3 Brick 2 0 7 4 3 2 Ceiling Tile 12 11 2 1 2 0 Cork 9 3 6 6 1 0 Fur 9 7 7 2 0 0 Grass 14 9 4 2 1 0 Paper 11 6 4 2 4 0 Pebbles 10 9 2 3 1 1 Sand 12 11 4 1 0 0 Screen 4 2 2 5 1 6 Water 13 7 9 0 0 0 Wood (1) 10 7 6 3 0 0 ()1 \D H H D Wood (2) 13 12212 2 = 119 First-Order (Anisotropic) Binary Tests. b(1.2). b(2.1). Texture Name Brick Ceiling Tile Cork Fur Grass Paper Pebbles Sand Screen Hater Hood (1) Hood (2) b(292). Conservative Acceptances 6 13 14 11 15 12 14 U! 14 14 (Anisotropic). The parameters Rejections at Q .1. 4 7 3 2 10 4 2 o 11 4 1 o a s 2 o 10 4 2 o 11 4 1' 0 11 2 1 1 14 2 0 0 10 3 3 0 13 2 1 0 Second-Order are a. b(1.1). 0.05 LEVEL 4 0 0 120 : Best-fitting Binary Texture Models. In the ow. 'I' means that the fewest rejections were obtained by using isotropic estimation. while 'A' signifies the best results were obtained using anisotropic parameters. The symbol '---' in the second-order column signifies that the best results were obtained using a first-order model. Texture Name L'irst Second Acceptances 70rder Order Brick I --- , 16 Ceiling Tile I --- 16 Cork I A 14 Fur _ I I 12 Grass A --- 16 Paper I --- 15 Pebbles I --- 14 Sand A A 14 Screen A A 5 Water A A 14 Wood (1) A A 14 Wood (2) A A 14 121 5.5.2 Binomial Texture Results With the experience gained from the binary fits. we limited our attention to four samples from each of the eight gray leVel pictures. First-order models yielded consistently negative results. The binomial model is unable to effectively model bimodal or uniform conditional probabilities. The binomial model always has a peak at exactly one value for any choice of 6. Also. if there are two likely gray values which are not contiguous. then no choice of the e parameter can yield the correct probabilities. As in the binary case. third-order analysis cannot be performed on samples of size 64 by 64 for eight gray level textures. In the matching experiments. estimation was performed for third-order textures using 128 by 128 samples. Even this is barely enough. and results in about thirty percent collapsing of the cells when the cells are pooled to force expectations of at least one per cell. A first-order model with anisotropy can have as many as 225 cells. while a full third-order model with anisotropy can use as many as 225**3 cells. Of course. the number of cells is limited by the number of points on the lattice. 122 Tables 11 and 12 give the results of fitting eight-color models to four samples from each texture class. The format is analagous to Tables 2 through 9. except that only four samples per texture class were used. As in the case of the binary textures. good results were obtained for all but the inhomogeneous textures: Hater. Hood. and Pebbles. The binomial model has difficulty in handling large areas of equal brightness. All of the textures which did not fit the model well are either blotchy or regular. like the image of the screen. Fine-grained textures can be handled and. as we shall see. generated by the binomial model easily. The best results of the two sets are shown in Table 13. 123 I§b1g 11: Eight gray level. First-order(Anisotropic). Second-order(Anisotropic). The parameters are a. b(1.1). b(1.2). b(2.l)9 and b(292). Texture Name Conservative Rejections at 0.05 level Acceptances 1 2 1 3 Brick 0 0 0 0 0 4 Ceiling Tile 2 1 3 0 0 0 Cork 4 3 1 0 0 0 Fur 1 1 2 0 1 0 Grass 3 3 1 0 0 0 Paper 4 3 1 0 0 0 Pebbles 0 0 0 0 0 4 Sand 4 4 0 0 0 0 Screen 0 0 0 0 0 4 Water 0 0 0 1 0 1 Hood (1) 1 0 0 0 0 4 Wood (2) 0 0 0 0 0 4 124 12213 12: Eight gray level. First-order(Isotropic). Second-order(Anisotropic). The parameters are a. b(1..). b(291). and b(292). Texture Name Conservative Rejections at 0.05 level Acceptances 1 2 1 3 Brick 3 0 2 2 0 0 Ceiling Tile 3 3 1 0 0 0 Cork 1 1 0 1 1 1 Fur 4 4 0 0 0 0 Grass 3 1 2 1 0 0 Paper 3 2 2 0 0 0 .Pebbles o o o n o 4 Sand 4 2 2 0 0 0 Screen 0 0 0 0 0 4 Mater 0 0 0 0 0 4 Wood (1) 0 0 0 0 0 4 Hood (2) 0 0 0 0 0 4 125 12913 11: Best-fitting Eight-gray level Texture Models. In the table below. '1' means that the fewest rejections were obtained by using isotropic estimation. while 'A' signifies the best results were obtained using anisotropic parameterss. The symbol '---' indicates that neither model was appropriate. Texture Name First Second Acceptances Order Order Brick A I 3 Ceiling Tile A I 3 Cork A A 4 Fur I A 4 Grass A A 4 Paper A A 4 Pebbles --- --- 0 Sand A A 4 Screen --- --- 0 Water --- --- 0 Hood (1) A A 1 Hood (2) --- --- 0 126 5.6 Texture Matching Experiments This section examines the viability of the Markov Random Field as a supervised texture generation procedure. The input texture is measured using the Maximum Likelihood approach described in section 5.3. The results of that evaluation are used as the input to the generation procedure in Figure 12. As mentioned in section 5.5. the third-order model on a 64 by 64 texture cannot be reliably fitted since it causes too many empty or near-empty cells. Limited experimentation showed that if the image size was increased to 128 by 128. a sensible chi-square estimate could be made. though the parameters did not change.very much from the estimates made on the 64 by 64 textures. 5.6.1 Binary Textures Binary textures have far simpler structures than multi-gray level textures. If they are not regular. like a tiling of the plane by polygons. then we can describe their general appearance by a few general characteristics. This is really an abbreviated list of the intuitive textural attributes defined in the first chapter. 127 (i) Directionality: Vertical. Horizontal. Diagonal. or None. (ii) Cluster size: Large. Medium. or Small (iii) Homogeneity: Homogeneous or Inhomogeneous. Inhomogeneous images have different characteristics in different parts of the picture. (iv) Special Features: Regularity. Line-likeness. Blob-likeness. Table 14 illustrates rough characterization on the basis of one 64 by 64 sample of the features given above. We can use this guide to evaluate our success in matching the generated textures. of course. we would like to be able to say that one texture “looks like" another. but we need some way of quantifying this correspondence. Figure 29 shows the results of generating the twelve textures from the estimated parameters. The parameters used to generate the synthetic textures were obtained by averaging the parameter estimates from each of the codings of a single subimage. The choice of subimage was arbitrary. A third-order estimate was used in all cases except for the pictures of Mood grain(1) and Pebbles. In these two 128 1221; 13: Binary Texture Characteristics Cluster 1251252 212211122 Size Bricks Vertical Ceiling Vertical Cork Diagonal Fur None Grass Diagonal Paper Diagonal. Pebbles None Sand None Screen Vertical Hater Vertical Nood(1) Horiz. Nood(2) Horiz. Large Small Small Large Small Small Large Medium Small Medium Large Large Low High High High Hihg Low High High Low Low Special Eeatsces Regular None None None None None Blobs None Lines. dots None Blobs Blobs 129 cases. a first-order model gave better visual results. First-order models tend to form in blob-like aggregations and cannot correctly characterize fine-structured textures. Moreover. they are inadequate in showing any directionality except vertical and horizontal. The clear failures are: Bricks: The regularity and neat rectangles are not present. Cluster size is close to correct along with the overall vertical structure. The regularity occurs at an order of around 20 pixels. and there is little chance of capturing such a structure from a 64 by 64 picture. Fur.wood (1). Wood (2): The inhomogeneity is missed in the synthetic examples. What remains of these pictures after binary quantization can hardly be called a texture. The images are estimated to be fine-structured rather than clean. blob-like shapes like pebbles. because their noise component modifies the estimate so that third-order inhibition is used in the generation. This is an unfortunate consequence of the estimation procedure. It is possible that a preliminary smoothing might help in getting a more correct estimate. In all cases. the directionality is correctly simulated in these textures. 130 The remaining nine textures are reasonably approximated by the simulated textures. In the pictures of Cork. Grass. and Paper. diagonality is the overriding feature and this is correctly modelled. The screen image_ is remarkably similar to the original. The third-order repulsion effect provides the curious checkerboard effects along the lines in both the original and the generated texture. Without this inhibition effect. the image would resemble the vertical images shown in Figure 16. 131 Eigggg 22 Real and Synthetic Binary Textures: £21 Binary Bricks 1211 Synthetic Binary Bricks _(_p__)_ Binary Ceiling tile 5311 Synthetic Binary Ceiling Tile 121 Binary Cork 1511 Synthetic Binary Cork 1g; Binary Fur 5g1; Synthetic 1211 Synthetic 1 Synthetic Binary Paper Binary Binary Grass 519252 22 ...Continwsg! 1.91 Binary Pebbles 19.1.18ynthetic Binary Pebbles (h) Binary Sand 1511 Synthetic Binary Sand 11; Binary Screen 1111 Synthetic Binary Screen Figure 22 Continued: 111Binary Water £111Synthetic Binary Water 121 Binary wood Grain(l) £511 synthetic Binary Hood Grain(1). 111 Binary Wood Grain(2) 1111 Synthetic Binary Wood Grain(2). 5.6.2 Binomial Texture Matching The same basic data set of Brodatz 0173 textures was used in the binomial matching experiments as was used in the binary experiments. The pictures were quantized to have eight gray levels using histogram equalization. However. during the estimation of the third-order Markov Random Field parameter set. it was found that far too many cells were empty or contained only a single member when the image size was 64 by 64. Therefore. a 128 by 128 image size was used for both estimation and matching. In all cases. a third-order model was estimated and used to generate the synthetic textures. Numerically. the Markov Random Field parameters of the estimated binomial textures are very similar. which accounts for the similar appearance of the generated textures. He have omitted some of the obvious failures: Water. Hood Grain (1). Hood Grain (2). and Pebbles. Hhen considered as an eight-gray level image. these textures take on a distinctly inhomogenous appearance. At this size. they look like pictures of obiects. whereas the generated textures look like a fine-grain field. The Markov Random Field always results in a homogeneous covering of the image. which cannot result in a blotchy 136 image unless the parameters are extreme. As'an example. the fur pictures. Figure 30a and 30a1. show the result of an inhomogeneity in the image. The other clear failure is the Bricks picture. As in the binary case. the Bricks image has a regular structure. The Markov Random Field can only detect a hint of a vertical structure. This is shown in Figures 30b and 30b1. Ceiling tile. Cork. Grass. Paper. and Sand are handled adequately. Missing are the large black holes in the synthetic ceiling tile picture. but there are some dense black patches. The distinctly three-dimensional appearance of the the handmade paper. admittedly a tactile property. is not captured either. The Screen texture has the general line-like quality. but lacks the straightness present in the original. This could be corrected. but the estimated parameters of the screen texture do not support the further inhibition needed to straighten out the lines and keep them narrow rather than fuzzy. 137 The model seems to be adequate for duplicating the micro-textures. but is incapable of handling strong regularity or cloud-like inhomogeneities. These experiments should be taken as an exploration of the limits of a purely statistical approach to texture without any 2 251251 knowledge at all. For example. if we knew that the Bricks picture was supposed to have rectangles of a certain size and orientation. then we could start with them as an outline and then fill in the rectangles with a Markov Random Field. 138 Real and Synthetic Eight Level Textures 121 Fur ' Fur 121 Bricks 1211 Synthetic Bricks g Tile 1911 Synthetic Ceiling Tile 519252 39 222112222: 121 Cork 1211 Synthetic Cork (e) Grass 1e ) Synthetic Grass 111 Paper 1:11 Synthetic 140 Figure 30 ggggigggg: 191 Sand 191) Synthetic Sand Iii-Ezreeh 1h11 Synthetic Screen 141 5.7 Summary We have explained the estimation procedure for the Markov Random Field parameters. Hypothesis testing was presented as a method of objective evaluation of the fit between a texture model and a texture. We computed the fit between Markov Random Field textures and a collection of samples from the Brodatz texture album [17]. Experiments in the generation of textures that matched real images were performed. with some successes and explainable failures. CHAPTER 6. CO-OCCURRENCE MATRICES 6.1 Introduction Features based on co-occurrence matrices continue to play an important role in texture analysis [243. [88]. In a model-based approach. we would like to determine the distribution of these features as a function of the model parameters. If we knew these distributions. then we could. at least in principle. determine the discriminative capability of classification algortithms based on the co-occurrence features. As an example. let 2(1) and 3(2) be two distinct parameter vectors for a texture model. Suppose further that the mean. S = EE2:X(i)J. is the same for textures from either the class defined by 2(1) or the one defined by 3(2). Then any classification scheme based solely on S would be unable to discriminate between textures from the two classes. A study along these lines was performed Iby Conners and Harlow [24]. They created textures using a one-dimensional Markov process. The Markov process specifies the probability that a pixel with gray level i follows a pixel with gray level j in a row. The rows of the image are uncorrelated. This texture model provides a 142 143 method of computing co-occurrence matrices from the transition matrix of the process. Texture algorithms can be compared on their capability of distinguishing textures with different transition matrices. The difference between the above study and prior comparative studies [1063 is that Conners's study did not compare the texture analysis algorithms on the basis of their performance on a texture database. but rather predicted their performance on texture classes defined by model parameters. Empirical studies certainly are of, interest to users of texture analysis algorithms. but they guide in the selection of textural recognition algorithms only insofar as the results of the empirical study can be generalized to new data. Our purpose in this chapter is to begin a theoretical calculation of textural feature distributions based on Markov Random Field parameters. JWe limit our attention to_ _the case of binary. first-order Markov Random Fields. 144 6.2 Joint Probability Formulation This section defines the variables we need to calculate the co-occurrence matrices. We assume that the binary variables take values in {-1.1}. Following Bartlett [7]. we have the following expression for the» joint probability mass function: (6.1) p(X) = Zexp( -GS(§) -Y(1)U1(§) - Y(2)U2(§)) where \ (6.2) S(X) = X(r.s) / (P95) \ (6.3) U1(§) = X(r.s)X(r-1.s) / (r.s) \ (6.4) u2(x) : X(r.s)X(r.s-1). / 145 The lattice is assumed to have a periodic boundary. The quantity Z in equation (6.1) is called the partition function. It depends on a. Y(1). and Y(2) and is a normalizing constant .30 that p(X) is a valid probability mass function. The quantity EES(§)] is called the mean of the process. If the value of a is zero. then EES(§)] is also zero. This is not hard to show. For each coloring 5. let -1 denote the negative of 5. in the sense that the value of each point X(r.s) of the lattice L is reversed in sign. Then my = -s<-x>. but 01(1) = U1(-§). and 02(5) = U2(-5). Since the quantity a is zero. we see from equation (6.1) that p(X) = p(-X). Hence. we conclude that Ets(2)) = logZ(Y(1).Y(2)) - lqu(Y(1)-¢(1).Y(2)-¢(2)). From equation (6.6). we obtain (6.7) EEUI] : (8K(¢(1)’¢(2))/3¢(1))I¢(1):¢(2):O 148 : alogZ(Y(1).Y(2))/6Y(1) and (6.8) ECU2] = alqu(Y(1).Y(2))/3Y(2). It is thus possible to compute the expectation and moments (or even approximate the distribution by a cumulant expansion) of U1 and U2. In this approach. we require knowledge of the partition function Z. Onsager E79] caLCUlated the exact value of Z for the case a = 0. This is is lonly case for which analytical results are available. The somewhat unwieldy exact Z can be closely approximated by the more compact form given by Kac and Ward [61]. When N is large and even. and the lattice has a periodic boundary then we can write (6.9) logZ(Y(1).Y(2)) = N(cosh(Y(1))+cosh(Y(2)) N N/2 \ \ + logH(r.s) / / s=1 r=1 where 149 H(r.s) = (1+x**2)(1+y**2) + 2y(x**2-1)cos(2nr/N) + 2x(y**2-1)cos(2ns/N) and x = -tanh(Y(1)). y = -tanh(Y(2)). The expression for the expectation of U1 or U2 is (6.10) EEUi] = Ntanh(Y(i)) N N/2 (---- :---- 1 aH(r.s) / / LIFE? 3???? -221" '22}- and the variances are given by (6.11) VarEUi] = Nsech2Y(i) \ \ 1 §H(r.s) 1 3H(r.s) / / H(r.s) av(i)2 H2(r.s) 8Y(i) We are now in a position to compute the co-occurrence matrices. We need to define the join counts for the case of variables in the form {0.1}. Each lattice point X(r.s) has a left-hand neighbor X(r-1.s) and a lower neighbor X(r.s-l). assuming the boundary is periodic. We can then define the following set of numbers. in a manner consistent with current practice E80]: 881 = number of times a black pixel has a black left-hand neighbor. WW1 : number of times a white pixel has a white left-hand neighbor. 8W1 = number of times a black pixel has a white left-hand neighbor. W81 = number of times a white pixel has a black left-hand neighbor. The quantities B82. WW2. 8W2. and W82 are defined in the same way except that "left-hand" is replaced with "lower." It is clear that on an,N by N lattice we have (6.12) 881 + WW1 + 8W1 + ”81 = N**2 151 and (6.13) 882 + ”“2 + 8H2 + H82 = N**2 The co-occurrence matrices can be expressed. at least for displacements of (0.1) and (1.0). in frequency form from equations (6.12) and (6.13). On a torus. the (-1.0) and (1.0) co-occurrence matrices are the same. Their common form is: 881 8W1 (6.14) C(1.0) = W81 WWI The (0.1) and (O.-1J co-occurrence matrix is: (6.15) C(0.1) = To compute these quantities from U1 and U2. observe that (6.15) U1 = 881 + WW1 - 8W1 - W81 (6.16) U2 = 882 + WW2 - 8W2 - W82. Combining equation (6.12) with (6.15) and equation (6.13) with (6.16). we obtain 152 (6.17) 881 + WNl = (N**2 + U1)/2 (6.18) 882 + WW2 = (N**2 + U2)/2. The final step in the computation rests on two assumptions. The first assumption is that the number of BB joins is closely approximated by the number of WW joins. Intuitively. this means that if the black pixels are clustered. the white pixels must also be clustered. The following proposition and its corollary establish that. from a Markov Random Field point of view. the clustering parameters for white and black are the same. Egggggitigg 6:1: Suppose a first-order Markov Random Field has conditional parameters a. b(1.1). and b(1.2). Then the Markov Random Field obtained by reversing each coloring of each realization has parameter set {a*.b*(1.1).b*(1.2)}. where 8* = -a ' 2b(1.1) - 2b(1.2)9 b*(1.1) = b(1.1). b*(1.2) = b(1.2). 3599:: Let p denote the conditional probability distribution of the original field and p* the conditional probability of the field obtained by reversing realizations. Let S*(1.1) and S*(1.2) denote the neighbor 153 sums in the reversed lattice (the quantities {S(i.k)} were defined in section 3.5.1). Then we have. p(X=0IS(1.1).S(192)) = D*(X=1IS*(1.1)=2-S(1.1).S*(1.2)=2-S(1.2)). This means. following equations (3.11) and (3.12). that 1 (1 + exp(a + b(1.1)S(1.1) + b(1.2)S(1.2)) exp(a* t b*(1.1)(2-S(1.1)) + b*(1.2)(2-S(1.2)) 1 + exp(a* + b*(1.1)(2-S(1.1)) + b*(1.2)(2-S(1.2)). After some simplification. we obtain the relation that (6.19) 0 = a + b(1.1)S(1.1) + b(1.2)S(1.2) 4» a. + b*(1.1)(2-S(1.1)) + b‘(1.2)(2-S(1.2n Equation (6.19) actually represents nine equations depending on the three values of S(1.1) and the three values of S(1.2). The only consistent solution is a* = a " 2b(1.1) - 2b(1!2)9 b*(1.1) = b(1.1). b*(192) = b(1.2). 0 As an immediate consequence. in the equalized histogram case we can be more specific: 154 Qgro 1251 221: If a binary. first-order Markov Random Field has parameter 4:0. then the parameters of the reversed field are the same as the parameters of the original field. Egoof: a* = -a - 2b(1.1) -2b(1.2). But in the equalized histogram case a = - b(1.1) - b(1.2) so a* = -a +2a=a.EI The second assumption needed to complete the computation is that the number of BW joins is closely approximated by the number of WB ioins. Intuitively. this means that the conditional probability of a black pixel having a white neighbor is the same as the conditional probability of a white pixel having a black neighbor. This is a consequence of the equal clustering between black and white pixels. along with approximately equal numbers of white and black pixels. Combining all of this. we obtain the final version of the co-occurrence matrices in frequency form: 155 N**2 + U1 N**2 - U1 4 4 (6.20) C(1.0) = N**2 - U1 N**2 + U1 4 4 N**2 + U2 N**2 - 02 4 4 (6.21) C(0.1) = N**2 - U2 N**2 + U2 4 4 6.4 Experimental Results In order to test the adequacy of the approximations inherent in equations (6.20) and (6.21). we.simulated a number of Markov Random Fields with various parameters and measured the correspondence between the expected and observed co-occurrence matrices. The first set of simulations inVOLVes 200 samples of 64 by 64 isotropic Markov Random Field textures with b(1..) parameters in the range 0 to 1. The high values closely approximate natural textures. A scatter-plot of the results of the expected and observed results appears in Figure 31. The horizontal axis is the clustering 156 parameter b(1..). The vertical axis is the value of the c(0.0) entry (probability of a black-black join) in the C(1.0) co-occurrence matrix. The curve drawn in is a plot of the expected value of the c(0.0) entry plotted as function of b(1..). computed using equation (6.20). The second set of simulations involves a series {of anisotropic textures with parameters b(1.1) and b(1.2) varying independently over the range 0 to 1.0 by increments of .1. Each texture was estimated under the first-order anisotropic model. The values of the C(O.1) and the C(1.0) co-occurrence matrices were recorded for each texture. The estimated parameters of the Markov Random Field were used to compute U1 and U2 using equation (6.10). The co-occurrence matrices were then approximated using equations (6.20) and (6.21). The difference between the observed value of the probability of a black-black join and the approximated value is shown below in Table 15. There is a total of 128 co-occurrence matrices (two per texture). The mean error between the expected and observed black-black probability is 0.0135 over the 128 matrices. The average error is about three percent with a maximum error of eight percent. This error is entirely reasonable: the variance of the. join count in the isotropic case 84.6. with an expectation of 1211. 158 66.. as o >H. :mmmomp. 66.2.5.3 De. \I ...: Q. QC, m. . LO Q or Co-occurrence and Observed Expected 159 12919 1;: Errors in Co-occurrence Predictions. The error column represents the difference between the predicted black-black join probability and the observed. Error Frequency Greater than 0.04 2 0.03 to 0.04 10 0.02 to 0.03 20 0.01 to 0.02 39 0.005 to 0.01 25 0.001 to 0.005 26 Less than 0.001 6 121 l 128 160 6.5 Summary We have formulated the joint probability form for binary Markov Random Fields. The partition function was shown to be the cumulant generating function for the horizontal and vertical join counts. Co-occurrence statistics were computed from the join counts. Finally. experiments showed good correspondence between the predicted co-occurrence matrices and the observed on a number of simulations. CHAPTER 7. CONCLUSIONS AND DISCUSSION 7.1 Summary Texture is defined as a stochastic. possibly periodic. two-dimensional image field. We reviewed the important aspects of texture and discussed vision research applicable to texture. The significant applications of texture analysis and synthesis were explained: classification. image segmentation. realism in computer graphics. and picture encoding. A texture model was defined as a mathematical procedure capable of producing and describing a textured image. The models which have been used were summarized in some detail. Included were discretized continuous models. time-series. fractals. random mosaics. syntactic models. linear models. and Markov models. Each was found to be appropriate for some but not all types of textures. The focus of this research was on the Markov Random Field model for texture. with special attention to the selection of an appropriate conditional distribution for the points of a lattice. The binomial model. where each point in the texture has a binomial distribution with 161 162 parameter 9 controlled by its neighbors and "number of tries" equal to G. the number of gray levels. was-taken to be the basic model for all the analysis. This represents the first use of the binomial model for image analysis and seems to be the first application of the binomial model for any purpose whatsoever. A method of generating samples from a binomial or binary model was given. The colorings X of a lattice were identified with the states of a Markov chain. Convergence of the generation procedure was taken to mean that the equilibrium distribution of the Markov chain was the same as the set of probabilities {p(1)}. The practical aspect of the rate of convergence was discussed and an example was given to show that a Markov Random Field image with desired parameters is obtained rather quickly. The Markov Random Field parameters control the strength and direction of the clustering of the image. Samples of various types of textures were exhibited to show the effects of various input parameters. These included line-likeness. blob-likeness. coarseness. and directionality. The power of the binomial model to simulate blurry or sharp images was demonstrated. Numerous types of images were found to require an 163 attraction-repulsion effect in the sense that the low-order Markov Random Field parameters were positive. causing clustering. while high-order parameters were negative. resulting in a fine structure of small clusters. In order to determine the relevance of the binomial model to real textures. samples from the Brodatz texture album [17] were digitized. Overall. the micro-textures. grass. sand. cork. ceiling tile. and paper. obeyed the Markov Random Field model well. The use of a hypothesis test for the objective evaluation of the correspondence of the model to the sample was a major feature of this investigation. Using the estimation procedure for Markov Random Fields. the parameters of the natural textures were measured. The measured parameters were used as input to the texture generation procedure. This was an attempt to see how‘ far the statistical approach alone could be carried in the absence of any structural information about the texture. Micro-textures were successfully generated while the regular and inhomogeneous textures bore little resemblance to their synthetic counterparts. 164 An investigation was begun of the connection between the distribution of the usual statistics used for texture analysis and the Markov Random Field model. The co-occurrence matrices of binary. first-order Markov Random Fields were computed as a function of lthe field parameters. Good correspondence was noted between the co-occurrence matrices of sample textured images and the matrices predicted from their Markov Random Field parameters. 7.2 Discussion This section is divided into two parts. The first part cites the advantages of the Markov Random Field image model and the second part details the limitations and defects of the model. 7.2.1 Advantages The positive aspects of the Markov Random Field model are given below. Comparisions are made with other texture models. 165 (i) The model is fully two-dimensional and does not assume a causal (unilateral) dependence. Many texture models are one-dimensional. such as time series E66] or simple Markov scan-line textures [24]. It is essential. at least in principle. that a texture model be capable of describing spatial interaction over the plane in all directions. In fact. the Markov Random Field can even be adapted for use on irregular or triangular lattices by application of the Hammersley-Clifford theorem [103. (ii) The texture parameters are measurable from samples and the appropriateness of the model can be assessed objectively by a hypothesis test. Contrast this with the texture generation process of Yokoyama and Haralick [1093. Their growth model represents a pattern generation process which certainly adds to our understanding of images. but we have no way of testing the sample image for correspondence to the model. Moreover. the Markov Random Field model allows the fitting of the sample texture directly to the model parameters. The current state of most models requires indirect fits by using variograms and correlation matches [90]. E26]. 166 (iii) The model parameters themselves are sufficient to generate images. The joint probability mass function p(X) is sufficiently peaked so that textured image samples governed by it resemble each other visually. In a purely feature-based approach. we do not have the capability to generate images from features because the features do not uniquely define a texture class. (iv) The pattern formation process. though specified locally. implies a global pattern. The consistency conditions enforced by the Markov Random Field cause a pattern over_the entire lattice. As Besag explains in the discussion of his lattice model paper. [103: Incidentally. the fact that a scheme is formally described as "locally interactive" does not imply that the patterns it produces are local in nature (cf. the extreme case of long-range order in the Ising model). (v) The patterns formed are realistic. The binomial model allows natural smooth peaks and valleys in the gray level height field over the plane. Sharp or blurry images can be controlled by the amount of high-order inhibition. Contrast this to the Poisson checkerboard with uniformly colored blocks and sharp boundaries [75]. If the assumption of uniform cell coloring is dropped from the 167 mosaic models. then their parameters cannot be estimated by currently available means. (vi) The patterns generated by varying the model parameters can be studied and classified. The results of chapter 4 show the visual significance of the parameter settings. Directionality. coarseness. gray level distribution. and sharpness can all be controlled by choice of the parameters. (vii) The parameter estimation procedure can be implemented in a parallel algorithm. Each parameter estimate is performed on disjoint codings. each of which can be processed separately and then averaged to form the final result. Even the hypothesis tests could be done in parallel. 7.2.2 Disadvantages and Limitations The Markov Random Field model has the following disadvantages. most of which are common to any purely stochastic approach to texture: 168 (i) Regular textures are not modelled very well. The only successful regular textures produced were the one-pixel wide checkerboard. Figure 17. or the screen. Figure 29i. The screen texture is really a one-dimensional texture consisting of highly correlated rows. The Markov Random Field approach is unable to provide the texture of regular cloth. a regular tiling. or the highly repetitive texture shown in Figure 29. (ii) The textural primitives of the Markov Random Field are non-geometric. The shape of the cells in a Markov Random Field has a distribution determined by the parameters. We cannot enforce any geometrical conditions or force things as triangular shapes to appear. such as is possible in a bombing model [903. We can only control the clustering characteristics: size. aspect ratio. density. and orientation. (iii) Large images are required to get good parameter estimates. It would appear that third-order estimates require at least 128 by 128 pictures for eight gray level textures. When the gray scale is two or four. 64 by 64 seems to be enough. Low cell frequencies discourage the use of the chi-square test in these cases. In fact. the chi-square test is really based on the variance and some 169 other type of test may be more appropriate for testing third-order statistics. (iv) The theoretical properties of the model are. in general. difficult to obtain. For example. the theoretical auto-correlation is known only numerically in the first-order binary case [33] and even less is known for higher-order models unless some stringent simplifying assumptions are made like b(1..) = b(2..) [28]. 7.3 Suggestions For Future Research Listed below are areas for investigation that extend the work in this thesis. All use the Markov Random Field model in some way. (i) Obtain numerically (or analytically) the autocorrelation and higher-order co-occurrence matrices. This is neeeded to complete the theoretical study begun in chapter 6. Special attention is needed for the case of more than two gray levels. (ii) Expand the data base of texture samples. The Brodatz texture samples certainly do not exhaust the possibilities of the model. It may be possible. for 170 example. to use the Markov Random Field model as a method of modelling film grain noise [363. The binomial model textures have a distinctly biomedical flavor and may be of use in modelling images obtained by microscopy. (iii) For the binary case. it is possible to apply the estimation procedure to the case of pictures thresholded at other than the fifty percent point of the histogram. Rosenfeld [883 has begun a productive investigation using the twenty-five percent point as a threshold. The clusters are smaller and carry more of the the structure of the picture without enormous. randomly linked clusters. (iv) Consider other conditional distributions. Besag [10] lists auto-normal and auto-poisson as possible candidates. (v) Try the full second-order model. as exoressed in equation (3.9). This may provide sufficient information about the image without any need to go as far as the third-order. The full second-order model has only four codings. which is a distinct computational advantage. 171 (vi) Image encoding experiments can be performed in a manner similar to those performed by Modestino and Fries [75]. The appropriate block size for the reconstructed mosaic could be as small as 32 by 32. It is conceivable that even a smaller size could be used as long as the process does not require high-order parameters. One of the problems in generating entire images with a single set of parameters is that the image generated is homogeneous. but the target image is not. Using a mosaic approach could compensate for this. (vii) Use Welberry-Galbraith type Markov Random Fields as explained in section 3.5.4.2. (viii) Apply the Markov Random Field model in a hierarchical manner. First. estimate the parameters on the given resolution. Next. consider the lattice of dimension half the original dimension by either averaging non-overlapping two by two neighborhoods or simply selecting every other point. The reduced lattice parameters are then estimated and the process is repeated to get a sequence of parameter vectors which may describe the structure of the image better than a single set. 172 (ix) Texture segmentation experiments can be performed by dividing the lattice into 32 by 32 non-overlapping blocks and estimating the Markov Random Field parameters on each block. It is possible to perform a hypothesis test for equality of parameters [103 and this could be used to determine the region membership. (x) A test of homogeneity is needed. The Markov Random Field model assumes homogeneity in the image. Some verification of this should be made before estimating the parameters and assessing the goodness-of-fit. LIST OF REFERENCES LIST OF REFERENCES [1] Abend.K.. Harley.T.J.. and Kanal.L.N.. 'Classification of Binary Random Patterns.' IEEE Transactions on Information Theory. IT-11. 1965. 538-544. C23 Ahuja.N.. 'Connectivity in Lattices and Mosaics.’ Proceedings of the 4th International Joint Conference on Pattern Recognition. Kyoto. Japan. November. 1978. 488-493. [3] Ahuja.N.. Mosaic Models for Image Analysis and Synthesis. Ph.D. dissertation. Department .of Computer Science. University of Maryland. College Park. Maryland. 1979. E4] Akaike.H.. 'Fitting Autoregressive Model for Prediction.' Annals of the Institute of Mathematical Statistics. 21. 1969. 243-247. [53 Akaike.H.. 'Statistical Predictor Identification.’ Annals of the Institute of Mathematical Statistics. 22. 1970. 203-217. [63 Andrews.H.C.. and Hunt.B.R.. Digital Image Restoration. Prentice Hall. Englewood Cliffs. New Jersey. 1977. [7] 8artlett.M.S.. The Statistical Analysis of Spatial Pattern. Chapman and Hall. London. 1976. [8] Beck.J. 'Perceptual groupings Produced by Line Figures.' Perception and Psychophysics. 2. 1967. 491-495. 173 174 [9] Besag.J.E.. 'On the Statistical Analysis of Nearest Neighbor Systems.' Colloquia Mathematica Societatis. Janos Bolyai. Ninth European Meeting of Statisticians. Budapest.” 101-105. 1972. E10] Besag.J.. 'Spatial Interaction and the Statistical Analysis of Lattice Systems (with Discussion).' Journal of the Royal Statistical Society. Series B. 36. 1974. 192-236. [11] Beucher.S.. 'Random Processes Simulations on the Texture Analyser.’ Geometrical Probability. Lecture Notes in Biomathematics. No. 23. Springer Verlag. Berlin. 1978. 311-321. [123 Billingsley.P.. 'Hausdorff Dimension in Probability Theory.' Illinois Journal of Mathematics. 1960. 187-207. [13] Billingsley.P.. 'Hausdorff Dimension in Probability Theory II.‘ Illinois Journal of Mathematics. 1961. 291-298. [14] 8linn.J.F.. and Newell.M.E.. 'Texture and Reflection in Computer Generated Images.’ Communications of the ACM. 19. 542. 1976. C15] 8linn.J.F.. 'Simulation of Wrinkled Surfaces.' Computer Graphics. 12(3). 286. 1978. E16] Bortz.A.B.. Kalos.M.H.. Lebowitz.J.L.. and Zendejas.M.A.. 'Time Evolution of a Ouenched Binary Alloy: Computer Simulation of a Two-Dimensional Model System.’ Physical Review B. 10. 535-541. 1974. E17] Brodatz.P.. Textures. Dover. New York. 1966. E18] Caelli.T.. and Julesz.B.. 'On Perceptual Analyzers Underlying Visual Texture Discrimination.’ Biological Cybernetics. 28. 167-175. 1978. 175 E19] Caelli.T.. and Julesz.B.. 'On Perceptual Analyzers Underlying Visual Texture Oiscrimination.' Biological Cybernetics. 29. 201-214. 1978. E20] Catmull.E.. 'Computer Display of Curved Surfaces.' Proceedings of the Conference on Computer Graphics. Pattern Recognition. Data Structures. IEEE Publication 75CH0981-1C. 11-17. 1975. [21] Catmull.E.. and Smith.A.R.. '3-D Transformations of Images in Scanline Order.’ Proceedings of the Siggraph Conference. Seattle. 279-285. July. 1980. E22] Cliff.A.D.. and Ord.J.K.. 'Model Building and The Analysis of Spatial Pattern in Human Geography.‘ Journal of the Royal Statistical Society. Series B. 37. 1975. 297-348. [23] Conners.R.W.. 'Towards a set of Statistical Features which Measure Visually Perceivable Qualities of Textures.' Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing. Chicago. Illinois. August. 1979. 382-390. [24] Conners.R.W.. and Harlow.C.A.. 'A Theoretical Comparison of Texture Algorithms.’ IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-2. 1980. 204-222. [25] Csuri.C.. Hackathorn.R.. Parent.R.. Carlson.W.. and Howard.M.. 'Towards an Interactive High Visual Complexity Animation System.' Computer Graphics. 13. 289-299. 1979. C26] Deguchi.K.. and Morishita.I.. 'Texture Characterization and Texture-based Image Partitioning using Two-Dimensional Linear Estimation Techniques.‘ IEEE Transactions on Information Theory. C-27. 1978. 738-745. [27] Delp.E.J.. Kashyap.R.L.. Mitchell.O.R.. and Abhyankar.R.B.. 'Image Modelling with a Seasonal Autoregressive Time Series with Applications to Data Compression.’ Proceedings of the IEEE Computer Society 176 Conference on Pattern Recognition and Image Processing. Chicago. Illinois. 1978. 100-104. [28] Domb.C.. 'Ising Model.' in Phase Transitions and Critical Phenomena. C. Domb and M.S. Green. editors. Academic Press. New York. 1974. [29] Dungan.W. 'A Terrain and Cloud Computer _Generation Model.' Computer Graphics. 13(2). 1979. 143-150. [30] Ehrich.R.W.. and Foith.J.P.. 'A View of Texture Topology and Texture Description.’ Computer Graphics and Image Processing. 8. 1978. 174-202. [31] Feller.W.. An Introduction to Probability Theory and its Applications. Volume 1. 3rd Edition. John Wiley and Sons. New York. 1968. E32] Flinn.P.A.. and McManus.G.M.. 'Monte Carlo Calculation of the Order-Disorder Transformation in the Body-Centered Cubic Lattice.’ Physical Review. 124. 54-59. 1961. E33] Flinn.P.A.. 'Monte Carlo Calculation of Phase Separation in a 2-Dimensional Ising System.' Journal of Statistical Physics. 10. 89-97. 1974. E34] Fosdick.L.D.. 'Calculation of Order Parameters in a Binary Alloy by the Monte Carlo Method.’ Physical Review. 116. 565-573. 1959. [35] Frisch.H.L.. and Julesz.B.. 'Figure-Ground Perception and Random Geometry.’ Perception and Psychophysics. 1. 1966. 389-398. [363 Froehlich.G.K.. Walkup.J.F.. and Asher.R.B.. 'Optimal Estimation in Signal-Dependent Film-Grain Noise.’ Proceedings of ICO-11 Conference. Madrid. 1978. 367-369. 177 E37] Galloway.M.. 'Texture Analysis using Gray Level Run Lengths.’ COmputer Graphics and Image Processing. 4. 1974. 172-199. [38] Galbraith. R.F. and Walley.D.. 'On a Two-Dimensional Binary‘ Process.’ Journal of Applied Probability. 13. 548-557. 1976. [3°] Galbraith. R.F. and Walley.D.. 'Ergodic- Properties of a Two-Dimensional Binary Process.’ Journal of Applied Probability. 17. 124-133. 1980. E40] Giger.H.. 'Rasterbare Texturen.' Zeitschrift fur Angewandte Mathematik und Physik. 26. 1975. 521-536. [41] Gonzalez.R.C.. and Wintz.P.. Digital Image Processing. Addison-Wesley. Reading. Massachusetts. 1977. E42] Hall.E.L.. Computer Image Processing and Recognition. Academic Press. New York. 1980. E43] Hammersley.J.M.. and Handscomb.D.C.. Monte Carlo Methods. Methuen and Company. London. 1964. E44] Hammersley.J.M.. 'Stochastic Models for the Distribution of Particles in Space.’ Supplement to Advances in Applied Probability. 1972. 47-68. [45] Haralick.R.M.. Shanmugam.K.. and Dinstein.I.. 'Textural Features for Image Classification.’ IEEE Transactions on Systems. Man. and Cybernetics. SMC-3. 1973. 610-621. [46] Haralick.R.M.. and Shanmugam.K.. 'Computer Classification of Reservoir Sandstones.’ IEEE Transactions on Geoscience Electronics. GE-11. 1973. 171-177. [47] Haralick.R.M.. 'Statistical and Structural Approaches to Texture.‘ Proceedings of the 4th International Joint Conference on Pattern Recognition. Kyoto. Japan. November. 178 1978. 45-69. [48] Hassner.M.. and Sklansky.J.. 'Markov Random Field Models of Digitized Image Texture.' Proceedings of the 4th International Joint Conference on Pattern Recognition. Kyoto. Japan. November. 1978. 538-540. [49] Hassner.M.. and Sklansky.J.. 'Markov Random Fields as Models of Digitized Image Texture.’ Proceedings of the IEEE Conference on Pattern Recognition and Image Processing. Chicago. Illinois. 1978. 346-351. [50] Hassner.M.. and Sklansky.J.. 'The Use of Markov Random Fields as Models of Texture.' University of California School of Engineering. Irvine. Irvine. California. Technical Report TP79-11. September. 1979. E51] Hurewicz.W.. and Wallman.H. Dimension Theory. Princeton University Press. Princeton. New Jersey. 1941. E52] Isaacson.E.. and Keller.H.B.. Analysis of Numerical Methods. John Wiley and Sons. Inc. New York. 1966. C53] Ising.E.. Zeitscrift Physik. 31. 253. 1925. C54] Julesz.B.. 'Visual Pattern Discrimination.’ IRE Transactions on Information Theory. IT-8. 1962. 84-97. [55] Julesz.B.. 'Texture and Visual Perception.' Scientific American. 212. 1965. 38-54. [56] Julesz.B. 'Cluster Formation at Various Perceptual Levels.‘ in Proceedings of the International Conference on Methodologies of Pattern Recognition. Hawaii. January. 1968. S. Watanabe. Editor. Academic Press. New York. 297“3150 C57] Julesz.B.. Foundations of Cyclopean Perception. University of Chicago Press. Chicago. Illinois. 1971. 179 E58] Julesz.B.. Frisch.H.L.. Gilbert.E.N.. and Sheop.L.A.. 'Inability of Humans to Discriminate Between Visual Textures that Agree in Second-Order Statistics - Revisited.' Perception. 2. 1973. 391-405. [59] Julesz.B.. 'Experiments in the Visual Perception of Texture.’ Scientific American. 232. 1975. 34-43. [60] Julesz.B.. Gilbert.E.N.. and Victor.J.D.. 'Visual Discrimination of Textures with Identical Third Order Statistics.‘ Biological Cybernetics. 31. 137-140. 1978. [61] Kac.M.. and Ward.J.C.. 'A Combinatorial Solution of the Two-Dimensional Ising Problem.’ Physical Review. 98. 1332-1337. 1952. , [62] Kaizer. H.. A Quantification of Textures on Aerial Photographs. Boston University Research Laboratories. Technical Note 121. 1955. AD69484. E63] Klein.J.C.. and Serra.J.. 'The Texture Analyser.‘ Journal of Microscopy. 95. pt. 2. 1972. 349-356.' [64] Kraft.A.L.. and Winnick.W.A.. 'The Effect of Pattern and Texture Gradient on Slant and Shape Judgments.’ Perception and Psychophysics. 2. 1967. 141-147. [65] Lu.S.Y. and Fu.K.S.. 'A Syntactic Approach to Texture Analysis.’ Computer Graphics and Image Processing .7. 1978. 303-330. [66] McCormick.B.H.. and Jayaramamurthy.S.N.. 'Time Series Model for Texture Synthesis.’ International Journal of Computer and Information Sciences. 3. 1974. 329-343. [673 Mandelbrot.B.B.. Fractals- Form. Chance. Dimension. W.H. Freeman and Company. San Francisco. 1977. 180 E68] Marr.D. 'Analyzing Natural Images: a Computational Theory of Texture Vision.' Cold Spring Harbor Symposium on Quantative Biology. 40. 647-662. 1976. [693 Marr.D.. 'Early Processing of Visual Information.' Philosophical Transactions of the Royal Society of London. Series 8.. 275. 483-519. 1976. E70] Matern.B.. 'Spatial Variation.’ Medd. Statens Skogforskningsinstitut. Stockholm. 36(5). 1-144. 1960. E71] Matheron.G.. Elements pour une Theorie des Mileux Poreux. Masson. Paris. 1967. E72] Matheron.G.. The Theory of Regionalized Variables and its Applications. Les Cahiers du Centre de Morphologie Mathematique de Fountainbleau. 5. 1971. E73] Metropolis.N.. Rosenbluth.A.W.. Rosenbluth.M.N.. Teller.A.H.. and Teller.E.. 'Equations of State Calculations by Fast Computing Machines.’ Journal of Chemical Physics. 21. 1087-1091. 1953. C74] Mitchell.O.R.. Meyers.C.R.. and Boyne.W.. 'A Max-Min Measure for Image Texture Analysis.' IEEE Transactions on Computers. C-26. 1977. 408-414. [75] Modestino.J.W.. and Fries.R.W.. 'Stochastic Models for Images and Applications.' Pattern Recognition and Signal Processing. C.H. Chen(Ed.). Sitjhoff and Noordhoff. Alphen aan den Rijn. The Netherlands. [76] Nevatia.R.. 'Locating Object Boundaries in Textured Environments.‘ IEEE Transactions on Computers. C-25. 1170-1175. 1976. [77] Newell.G.F.. and Montroll.E.W.. 'On the Theory of the Ising Model of Ferromagnetism.’ Reviews of Modern Physics. 25. 1953. 353-389. 181 E78] Newman.W.M.. and Sproull.R.F.. Principles of Interactive Computer Graphics. Mc-Graw Hill. New York. 1979. _ ' E79] Onsager.L.. 'Crystal Statistics I: A 2-Dimensional Model with an Order-Disorder Transition.‘ Physical Review. 65. 117-149. 1944. [80] Ord.J.K.. and Cliff.A.D.. Spatial Autocorrelation. Pion. London. 1973. [813 Pears.A.R.. Dimension Theory of General Spaces. Cambridge University Press. Cambridge. 1975. C82] Pickard.D.K.. 'A Curious Binary Lattice Process.‘ Journal of Applied Probability. 14. 717-731. 1977. C83] Pratt.W.K.. Faugeras.O.D.. and Gagalowicz.A.. 'Visual Discrimination of Stochastic Texture Fields.‘ IEEE Transactions on Systems. Man. and Cybernetics. SMC-B. 1978. 796-804. [84] Ripley.B.D.. 'Modelling Spatial Patterns.' Journal of the Royal Statistical Society. Series B. 8. 1977. 172-212. [853 Rogers.A. Statistical Analysis of Spatial Dispersion. Pion Ltd.. London. 1974. [86] Rosenfeld.A.. and Troy.A.. 'Visual Texture Analysis.’ TR 70-116. University of Maryland. June. 1970. [873 Rosenfeld.A.. and Thurston.M.. 'Edge and Curve Detection for Visual Scene Analysis.' IEEE Transactions on Computers. C-20. 1971. 562-569. [88] Rosenfeld.A.. 'Some Recent Developments in Texture Analysis.’ Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing. Chicago. Illinois. August. 1979. 618-622. 182 [893 Schacter.B.. Rosenfeld.A.. and Davis.L.S.. 'Random Mosaic Models for Textures.' IEEE Transactions on Systems. Man. and Cybernetics. SMC-8 1978. 694-702. [90] Schacter.B.. and Ahuja.N.. 'Random Pattern Generation Processes.’ Computer Graphics and Image Processing. 10. 1979. 95-114. [913 Serra.J.. 'Stereology and Structuring Elements.‘ Journal of Microscopy. 95. pt. 1. 1972. 99-103. [92] Serra.J.. and Verchery.G.. 'Mathematical Morphology Applied to Fiber Composite Materials.‘ Film Science and Technology. 6. 1973. 141-158. [93] Serra.J. Boolean Model and Random Sets. Centre de Morphologie Mathematique. Ecole des Mines de Paris. Report N-614. 1979. E94] Spitzer.F.. ' Markov Random Fields and Gibbs Ensembles.' American Mathematics Monthly. 78. 142-154. 1971. E95] Sternberg.S.R.. 'Parallel Architectures for Image Processing.' Proceedings of the 3rd International IEEE COMPSAC. Chicago. 1979. E96] Sternberg.S.R.. 'Language and Architecture for Parallel Image Processing.' Proceedings of the Conference on Pattern Recognition in Practice. Amsterdam. The Netherlands. May. 1980. E97] Strauss.D.J.. 'Clustering on Coloured Lattices.’ Journal of Applied Probability. 14. 135-143. 1977. E98] Tamura.H.. Mori.S.. and Yamawaki.T.. 'Textural Features Corresponding to Visual Perception.’ IEEE Transactions on Systems. Man. and Cybernetics. SMC-8. 1978. 460-473. 183 [993 Thompson.W.8.. 'Textural Boundary Analysis.‘ IEEE Transactions on Computers. C-24. 1977. 272-276. [100] Turing.A.M.. 'Computing Machinery and Intelligence.' Mind. 59. 433-460. 1950. C101] Verhagen.A.M.W.. 'A 3-parameter Isotropic Distribution' of Atoms and the Hard Core Lattice Gas.’ Proceeedings of the Royal Society. Series A. 1977. [102] Welberry.T.R.. 'A 2-Dimensional Model of Crystal Growth Disorder.' Journal of Applied Crystallography. 6. 87-96. 1977. [1033 Welberry.T.R. and Galbraith.R.F.. 'The Effect of Non-linerity on a 2-Dimensional Model of Crystal Growth Disorder.‘ Journal of Applied Crystallography. 8. 636-644. 1975. C104] Welberry.T.R.. 'Solution of Crystal Growth Disorder Models by Imposition of Symmmetry.' Proceedings of the Royal Society. Series A. 353. 363-376. 1977. [105] Welberry.T.R.. and Miller.G.H.. 'An Approximation to a Two-Dimensional Binary Process.’ Journal of Applied Probability. 14. 862-868. 1977. [106] Weszka.J.. Dyer.C. and Rosenfeld.A.. 'A Comparative Study of Texture Measures for Terrain Classification.‘ IEEE Transactions on Systems. Man. and Cybernetics. SMC-6. 1976. 269-285. [107] Whittle.P.. 'On Stationary Processes in the Plane.’ Biometrika. 41. 1954. 434-449. [108] Yessios.C.I.. 'Computer Drafting of Stones. Wood. Plant. and Ground Materials.’ Computer Graphics. 13(2). 1979. 190-198. 184 [1093 Yokoyama.R.. and Haralick.R.M.. 'Texture Snynthesis using a Growth Model.' Computer Graphics and Image Processing. 8. 1978. 369-381. [1103 Yokoyama.R.. and Haralick.R.M.. 'Texture Pattern Image Generation by Regular Markov Chain.’ Pattern Recognition. 11. 1979. 225-234. [111] Zucker.S.w.. 'On the Faundations of Texture: A Transformation Aoproach.‘ TR-331. University of Maryland. September 1974. E "1111 Jul/WTTTTTQTMI“ 0704