Nonparametric Markov Random Field
Models for Natural Texture Images
BEng(Honours), Electrical and Communications Engineering University of Tasmania, Australia
Rupert D. Paget
Cooperative Research Centre for
Sensor Signal and Information Processing,
Department of Computer Science & Electrical Engineering,
The University of Queensland,
St Lucia, Queensland 4072, Australia.
S
CIENTIA
LABORE
AC
Submitted as a requirement for the degree of
Doctor of Philosophy (Ph.D.),
The University of Queensland,
February 1999.
Abstract
T he underlying aim of this research is to investigate the mathematical descriptions
of homogeneous textures in digital images for the purpose of segmentation and
recognition. The research covers the problem of testing these mathematical descrip-
tions by using them to generate synthetic realisations of the homogeneous texture for
subjective and analytical comparisons with the source texture from which they were
derived. The application of this research is in analysing satellite or airborne images
of the Earth’s surface. In particular, Synthetic Aperture Radar (SAR) images often
exhibit regions of homogeneous texture, which if segmented, could facilitate terrain
classification.
In this thesis we present noncausal, nonparametric, multiscale, Markov random
field (MRF) models for recognising and synthesising texture. The models have the
ability to capture the characteristics of, and to synthesise, a wide variety of tex-
tures, varying from the highly structured to the stochastic. For texture synthesis,
we introduce our own novel multiscale approach incorporating a new concept of local
annealing. This allows us to use large neighbourhood systems to model complex nat-
ural textures with high order statistical characteristics. The new multiscale texture
synthesis algorithm also produces synthetic textures with few, if any, phase disconti-
nuities. The power of our modelling technique is evident in that only a small source
image is required to synthesise representative examples of the source texture, even
when the texture contains long-range characteristics. We also show how the high-
dimensional model of the texture may be modelled with lower dimensional statistics
without compromising the integrity of the representation. We then show how these
models – which are able to capture most of the unique characteristics of a texture
– can be for the “open-ended” problem of recognising textures embedded in a scene
containing previously unseen textures. Whilst this technique was developed for the
practical application of recognising different terrain types from Synthetic Aperture
Radar (SAR) images, it has applications in other image processing tasks requiring
texture recognition.
ii
Key words
• Markov Random Fields;
• Gibbs Distributions;
• Parametric Estimation;
• Nonparametric Estimation;
• Parzen Window Density Estimator;
• ANOVA Model;
• Texture Modelling;
• Texture Synthesis;
• Open Ended Texture Classification;
• Multi-resolution;
• High-order Statistics;
• Stochastic Relaxation;
• Deterministic Relaxation;
• Multiscale Relaxation;
• Simulated Annealing;
• Parallel Processing;
• Discriminant Analysis;
• Wilcoxon Test;
• Kruskal-Wallis Statistic;
• Terrain Mapping;
• Synthetic Aperture Radar.
Contents
1 Introduction
1.1 What is texture? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Human perception of texture
. . . . . . . . . . . . . . . . . .
1.1.2 Computer analysis of texture
. . . . . . . . . . . . . . . . . .
1.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1
Satellite images . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2
Synthetic aperture radar (SAR) images . . . . . . . . . . . . .
1.2.3 Terrain mapping . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.4 Research purpose . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Modelling texture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
2
4
5
5
6
8
8
9
1.3.1
Ideal texture model . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Testing the ideal texture model
. . . . . . . . . . . . . . . . . 11
1.3.3 Open-ended classifier . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Building a texture model . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Determining structure of the model
. . . . . . . . . . . . . . . 14
1.4.2 Fitting the model to the texture . . . . . . . . . . . . . . . . . 16
1.5 Our texture model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.1
Synthesising realistic examples of texture . . . . . . . . . . . . 18
1.5.2 Open-ended classification of texture . . . . . . . . . . . . . . . 18
1.6 Outline of thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iii
iv
CONTENTS
2 Background
21
2.1 Texture models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.2 Applications for texture models . . . . . . . . . . . . . . . . . 25
2.1.3 Performance of texture models . . . . . . . . . . . . . . . . . . 26
2.1.4 Accuracy of texture models
. . . . . . . . . . . . . . . . . . . 27
2.2 Hypothesis: high order statistics are required to model texture . . . . 29
2.3 Markov random field (MRF) model
. . . . . . . . . . . . . . . . . . . 30
2.3.1 Problems in using MRF models . . . . . . . . . . . . . . . . . 33
2.4 Nonparametric Markov random field . . . . . . . . . . . . . . . . . . 34
2.4.1 Advantages in using nonparametric MRF models
. . . . . . . 36
3 MRF Model
37
3.1 Random field preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 General Markov random field model . . . . . . . . . . . . . . . . . . . 39
3.3 Gibbs distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 The N -Potential V . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 MRF — Gibbs distribution equivalence . . . . . . . . . . . . . . . . . 46
3.4.1 Proof 1: by G. Grimmett . . . . . . . . . . . . . . . . . . . . . 46
3.4.2 Proof 2: by J. Besag . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Factorisation of the probability distribution . . . . . . . . . . . . . . 49
4 Parametric MRF Model
53
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Auto-models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1
Ising model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2 Auto-binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.3 Auto-logistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
CONTENTS
v
4.2.4 Auto-binomial . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.5 Derin-Elliott . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2.6 Auto-normal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Parameter estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3.1 Maximum likelihood estimator . . . . . . . . . . . . . . . . . . 60
4.3.2 Monte Carlo maximum likelihood estimator
. . . . . . . . . . 63
4.3.3 Maximum pseudo-likelihood estimator
. . . . . . . . . . . . . 64
4.3.4 Coding scheme and other estimators
. . . . . . . . . . . . . . 66
4.4 Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4.1 Optimisation by simulated annealing . . . . . . . . . . . . . . 71
4.5 Goodness-of-fit testing . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Nonparametric MRF Model
75
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Multi-dimensional histogram . . . . . . . . . . . . . . . . . . . . . . . 77
5.3 Parzen window density estimator
. . . . . . . . . . . . . . . . . . . . 80
5.3.1 Required sample size for given accuracy . . . . . . . . . . . . 83
5.4 Alternative nonparametric estimators . . . . . . . . . . . . . . . . . . 84
5.4.1 Adaptive kernel estimator
. . . . . . . . . . . . . . . . . . . . 84
5.4.2 Adaptive bin estimator . . . . . . . . . . . . . . . . . . . . . . 84
5.5 Multi-dimensional histogram compression . . . . . . . . . . . . . . . . 88
5.5.1 Unsupervised clustering . . . . . . . . . . . . . . . . . . . . . 89
5.5.2 Basis functions
. . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.5.3 Adaptation for histogram compression . . . . . . . . . . . . . 93
5.6 Goodness-of-fit testing . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6 Strong Nonparametric MRF Model
97
6.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Strong MRF theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
vi
CONTENTS
6.3 Proof 1 of Proposition 6.1 . . . . . . . . . . . . . . . . . . . . . . . . 101
6.4 Proof 2 of Proposition 6.1 . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5 Equivalence with ANOVA model
. . . . . . . . . . . . . . . . . . . . 111
6.6 Estimation of the strong LCPDF . . . . . . . . . . . . . . . . . . . . 113
6.7 Goodness-of-fit testing . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7 Synthesising Texture
119
7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.2 Multiscale relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2.1 Averaging approach . . . . . . . . . . . . . . . . . . . . . . . . 126
7.2.2 Decimation approach . . . . . . . . . . . . . . . . . . . . . . . 127
7.3 Pixel temperature function . . . . . . . . . . . . . . . . . . . . . . . . 128
7.4 Site visitation sequence . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.4.1 Exchange
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.4.2
Seeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.4.3 Parallelised relaxation . . . . . . . . . . . . . . . . . . . . . . 136
7.5 Edge effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.6 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7.6.1 Approximations made in the interest of speed . . . . . . . . . 139
7.7 Synthesised textures
. . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8 Classifying Texture
147
8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.2 Bayesian paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
8.3 Open-ended classification . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.3.1 Probability measurement . . . . . . . . . . . . . . . . . . . . . 153
8.3.2 Multiscale probability measurement . . . . . . . . . . . . . . . 155
8.4 Boundaries and edges . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.5 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
CONTENTS
vii
8.5.1 Approximations made in the interest of speed . . . . . . . . . 160
8.6 Open-ended classification of textures
. . . . . . . . . . . . . . . . . . 160
8.6.1 Comparative assessment of performance
. . . . . . . . . . . . 165
8.7 Practical application . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9 Discussion and Conclusion
173
9.1 Advantages
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.2 Limitations
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.3 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
A Extracting the Local Clique Set
179
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
A.2 Neighbourhoods and their cliques . . . . . . . . . . . . . . . . . . . . 180
A.3 Extraction of the local clique set . . . . . . . . . . . . . . . . . . . . . 181
A.3.1 Method 1: growing the clique tree . . . . . . . . . . . . . . . . 182
A.3.2 Method 2: reading cliques from the tree
. . . . . . . . . . . . 182
A.4 Clique tree theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
A.5 Discussion and conclusion . . . . . . . . . . . . . . . . . . . . . . . . 185
B Synthesised Textures
187
B.1 Textures synthesised with various neighbourhoods . . . . . . . . . . . 187
B.2 Textures synthesised with various multiscales . . . . . . . . . . . . . . 355
B.3 Textures synthesised with various clique sets . . . . . . . . . . . . . . 365
C Classified Textures
391
C.1 Open ended classification of texture . . . . . . . . . . . . . . . . . . . 391
C.2 Open ended classification of terrain . . . . . . . . . . . . . . . . . . . 424
C.3 Open ended classification as a medical diagnostic
. . . . . . . . . . . 429
Bibliography
431