Unsupervised Segmentation of Markov Random Field Modeled Textured Images Using Selectionist Relaxation.
AbstractAmong the existing texture segmentation methods, those relying on Markov random fields have retained substantial interest and have proved to be very efficient in supervised mode. The use of Markov random fields in unsupervised mode is, however, hampered by the parameter estimation problem. The recent solutions proposed to overcome this difficulty rely on assumptions about the shapes of the textured regions or about the number of textures in the input image that may not be satisfied in practice. In this paper, an evolutionary approach, selectionist relaxation, is proposed as a solution to the problem of segmenting Markov random field modeled textures in unsupervised mode. In selectionist relaxation, the computation is distributed among a population of units that iteratively evolves according to simple and local evolutionary rules. A unit is an association between a label and a texture parameter vector. The units whose likelihood is high are allowed to spread over the image and to replace the units that receive lower support from the data. Consequently, some labels are growing while others are eliminated. Starting with an initial random population, this evolutionary process eventually results in a stable labelization of the image, which is taken as the segmentation. In this work, the generalized Ising model is used to represent textured data. Because of the awkward nature of the partition function in this model, a high-temperature approximation is introduced to allow the evaluation of unit likelihoods. Experimental results on images containing various synthetic and natural textures are reported.
INTRODUCTION
Textured image segmentation consists in partitioning an image into regions that are
homogeneous with regards to some texture measure. Texture description is an important
issue with respect to this task. Existing texture segmentation methods are
commonly classified according to the texture description they rely on. In structural
methods, textures are assumed to consist of structural elements obeying placement
rules. In feature based methods, a vector of texture features is computed for each
pixel. In stochastic model-based methods, textures are assumed to be realizations of
two-dimensional stochastic processes such as, for example, Markov random fields.
Among the existing texture segmentation methods [30], those based on Markov
random fields [23, 15] have retained substantial attention. Markov random fields are
attractive because they yield local and parsimonious texture descriptions. Past studies
have also shown the efficiency of Markov random fields in texture modeling, com-
pression, and classification [12, 6, 5]. Besides, the use of texture models presents a
methodological advantage. Textured images can be generated according to the specified
model so that the segmentation method can be evaluated independently of the
adequacy of the underlying texture characterization.
Texture segmentation using Markov random fields can be achieved through maximum
likelihood labelization [8]. Besides their ability to model textured data, Markov
random fields can also be used to incorporate a priori knowledge concerning the properties
of the labels themselves [15, 13, 14, 8, 27]. Segmentation is then achieved by
searching the labelization that maximizes the posterior probability of the labeling conditioned
on the data. This optimization problem can be solved using the Gibbs Sampler
combined with simulated annealing [16].
However, the parameter estimation problem is a crucial issue for methods based
on Markov random fields, and their performance depends on the availability of correct
parameter estimates [15]. These methods work well in supervised mode, wherein
the number of textures and their associated parameters are known, or can be esti-
mated, beforehand. In unsupervised mode, when such knowledge is not available, a
circular problem arises [26, 22]: parameter estimates are needed to segment the image,
while homogeneous texture samples, which can be provided in the form of an already
segmented image, are needed to compute these estimates.
Different solutions to this problem have been proposed. A first approach consists
in assuming that the shapes of the textured regions are such that the image can be
divided into a number of homogeneously textured blocks. Each such block provides
a parameter estimate. The number of textures and their associated parameters are
determined by applying a clustering algorithm on the parameter estimate set. These
final estimates are used to compute the segmentation that optimizes a criterion such as
the likelihood criterion [9, 29], the a posteriori probability criterion [26, 22, 29], or the
classification error criterion [26]. Conversely, a second approach consists in iterating
an estimation/segmentation cycle [24, 33]. Given a candidate number of textures and
an initial random set of texture parameters, a first segmentation is computed. Texture
parameters are then recomputed using the current segmentation. This cycle is repeated
several times until convergence. The whole procedure is repeated with different candidate
numbers of textures, and the number that optimizes a model fitting criterion is
retained as the true number of regions [33].
These solutions are feasible for images that contain large textured regions or that
contain only a limited number of textured regions. In practice, these conditions may not
be satisfied. Moreover, besides the parameter estimation problem, relaxation methods
based on Markov random fields are often computationally expensive. The problem
of segmenting textures modeled using Markov random fields indeed represents a large
combinatorial search problem.
In this work, a genetic algorithm based approach is adopted to overcome some of
the aforementioned difficulties of existing methods. Genetic algorithms [21, 18] are
stochastic search methods inspired by the conception that natural evolution is an optimization
procedure, which, if simulated, can be applied to solve artificial optimization
problems. In a genetic algorithm, a population of candidate solutions, initially generated
at random, undergoes a simulated evolutionary process, whereby solutions of
increasing quality progressively appear. Each generation, a new population is computed
from the previous one through a two-step cycle. During the first step, good
solutions are selected and duplicated to replace bad ones. During the second step,
new solutions are generated by recombining and mutating the solutions that have been
selected. Consequently, good solutions are progressively spreading within the popu-
lation, while being permanently exploited to build possibly better solutions. Genetic
algorithms are attractive in combinatorial problems because they achieve an efficient,
parallel exploration of the search space (which in particular may avoid being stuck in
local optima), while requiring minimum information on the function to be optimized
(in particular, the derivatives are not required) [18].
In the standard genetic algorithm [18], the population is panmictic, i.e., each individual
can compete or recombine with any other one in the population. Alternatively, in
distributed genetic algorithms, each individual is constrained to interact with a limited
number of other individuals. In coarse-grained distributed genetic algorithms [32, 10],
the population is divided into several subpopulations submitted to their own genetic
algorithm, and periodically exchanging some of their individuals. In fine-grained distributed
genetic algorithms [28, 25, 31, 11], the population is mapped onto a grid
whereupon a neighborhood system is defined to constrain interactions among individ-
uals. The purpose of distributed genetic algorithms is to increase the quality of the
obtained solutions, in particular by avoiding premature convergence to non-optimal
solutions, and to reduce the time needed to obtain the solutions.
The method presented herein is an unsupervised segmentation method whereby the
transformation of an input image into an output segmented image is computed by a
population of units that are mapped onto the image. Initially generated at random,
the population is iteratively updated and reorganizes through a fine-grained distributed
genetic algorithm. Consequently, a sequence of segmented images is generated. This
sequence progressively converges to a stable labelization, which is taken as the resulting
segmented image. This method, called selectionist relaxation to emphasize the role of
selection, has been previously applied to the unsupervised gray-level image segmentation
problem [1]. It is shown here how selectionist relaxation can be generalized to the
unsupervised textured image segmentation problem.
In this work, textures are represented using the generalized Ising model [16], also
known as the Derin-Elliott model [14]. With this model, the likelihood of a texture
window, the evaluation of which is required in selectionist relaxation, is not computable
in practice because of the intractability of the partition function. An approximation
of the partition function is therefore introduced to overcome this problem.
The organization of the paper is as follows. Background on the Markov random field
approach to texture modeling is given in Section 2. The approximation of the partition
function is set out in Section 3. Selectionist relaxation is presented in Section 4. Results
on synthesized texture patches are reported in Section 5. Section 6 is devoted to a final
discussion and conclusion.
s

Figure

1: Neighborhoods and cliques. A. The spatial extent of the neighborhood of
a site s depends on the order of the model. At order n, the neighborhood contains
all the sites that are assigned a digit less than or equal to n. B. The 10 clique types
associated to a second-order model. Cliques with non-zero potential in the model used
in this paper are shown in gray.
The input image is assumed to contain several textures, each of which is considered as
a realization of a Markov random field [23]. Further, the same model is used for all
textures, because it is assumed that these textures are different instances of the same
texture model.
2.1 Markov/Gibbs random fields
Consider the two-dimensional set of sites
NC g, wherein NR and NC are the numbers of rows and columns of the texture image,
respectively. A collection of subsets of sites defines a
neighborhood system if it satisfies the following two conditions: (1) 8s 2
clique is either a single site or a set of mutually neighboring
sites. The set of cliques is
being the number of different clique types.
Neighborhood structures and clique types are illustrated in Fig. 1.
A texture sample is considered herein as a realization of a random field
s is a random variable taking values in a discrete set
being the number of gray levels in the image. A realization x of
X is called a configuration. The state space of X
. The restriction of
a configuration to a subset R of S is noted xR . A collection of real-valued functions
defined
on\Omega and such that VR (x) only depends on xR is called a
potential. Further, V is a neighbor potential if 8x
According to the Hammersley-Clifford theorem [2], the random field X is a Markov
random field on S with respect to a neighborhood system N if and only if its distribution
on\Omega is a Gibbs distribution induced by a neighbor potential, that is to say
8x
is the energy of configuration x and the normalizing
constant
y2\Omega expf\GammaE(y)g is the partition function.
2.2 Generalized Ising model
Various Markov random field texture models have been proposed, each of which being
defined by its associated potential: the autologistic model [20], the autobinomial model
[12], the autonormal (Gaussian Markov random field) model [4] and the generalized
Ising model [16, 14, 17].
Despite its simplicity, we have retained this last model to work with in this work.
Indeed, the first step in our work is to test the feasibility of applying selectionist
relaxation to segment images that contain Markov random field samples, regardless of
whether the model is able or not to capture the complexity of natural textures.
The generalized Ising model is a pairwise interaction model [15]: only those cliques
that contain no more than 2 sites have non zero potentials. Singleton potentials are
set to zero so that the first-order histogram is uniform. Because we use a second-order
model, the effective number of clique types is clique types are shown in
gray in Fig. 1-B). For a pair clique the potential function is given by
is the parameter associated to clique type i, and
which case ffi xsxr = 1. Letting the vector of model parameters,
the energy of any configuration x can be written as
wherein the vector defined by
3 PARTITION FUNCTION APPROXIMATION
As described in the next section, selectionist relaxation requires that, given any w \Theta
w window W and any candidate vector model parameters, the
likelihood of a configuration xW is practically computable. Letting
\Omega W denote the state space of XW , this likelihood is given by:
Considering the generalized Ising model, the exact computation of the likelihood cannot
be achieved in practice: the partition function ZW (B) neither has a simple analytical
form, nor can be computed. This would involve calculating the energy of all possible
configurations over W , which is computationally intractable because of the huge
number of such configurations.
We therefore propose an approximation of the partition function. It consists in
approximating each of the terms in the expression of ZW (B) using its second-order
expansion:
The approximated terms are then summed up over y
2\Omega W . It is shown in the Appendix
how, assuming the window W has a toroidal structure, the resulting expression

Figure

2: Plot of the relative approximation error as a function of temperature. The
error was numerically determined with the following conditions: W is a 3 \Theta 3 window,
the number of gray levels is and the parameter set is B
of the partition function can be rearranged and simplified. This eventually leads to the
following approximated partition function:
~
wherein g is the number of gray levels and w is the number of sites in the
window W . It should be noted that the approximation is not only valid in the second-order
model case, but stands for any order of the model.
This approximation can be interpreted as a high-temperature approximation of the
partition function. Up to now, the temperature T of the Gibbs distribution (1) has
indeed been considered as incorporated in the energy, but if we define
then, from (2), the energy can be rewritten as
The error due to the approximation (3) vanishes as E(y; B) ! 0. From (6), this clearly
happens when T ! 1. The dependency on T of the resulting approximation error is
illustrated in Fig. 2, which plots the relative error defined by
T has been made explicit here only for the sake of the demonstration. In the
remainder of the paper, we return to the use of B (instead of B   and T ), considering
T as an implicit scaling factor: the condition fi i - 1, which will be imposed to keep
the approximation error small enough, will be interpreted as an absorption of T within
the parameters themselves, according to (5).
input
image
image
output
algorithm
s
s
s

Figure

3: Selectionist relaxation. The unit U s assigned to site s consists of a feature
vector B s and of a label L s . The fitness of U s depends on how well B s matches the
data in the input window W s . The genetic algorithm applied to the population of
units results in a relaxation process, whereby highly fitted units spread over the image,
replacing badly fitted ones. In this process, unit U s primarily interacts with the units
located within its neighborhood N s . At the end of the process, the resulting segmented
image is build by attributing to each site s the corresponding label L s .
4.1 Outline of the method
Selectionist relaxation is an unsupervised segmentation method whereby the transformation
of an input image into an output image is computed by a population of units
that iteratively evolves through a distributed genetic algorithm (Fig. 3).
Each unit is an association between a candidate feature vector and a label. The
latter is used to label the unit pixel. The former is used to assign a fitness value
to the unit. The fitness of a unit is a measure of the matching between its feature
vector and the data in the image window whereupon the unit is centered. The features
that compose unit feature vectors are arbitrarily chosen on the basis of the desired
segmentation type. For example, pixel matrices were used as feature vectors for grey-level
image segmentation [1]. Here, it is proposed that texture segmentation can be
achieved using texture model parameters as feature vectors.
The population of units iteratively evolves through the application of genetic operators
[18]: the units whose feature vectors find good support from image data are
selected, recombined and mutated. These mechanisms allow units with high fitness
values to spread over their neighborhood by replacing the neighboring units that do
not fit the local image data. Additionally, some units can jump over large distances to
invade distant regions with similar characteristics. This results in a mixed local/distant
parameters
label

Figure

4: Unit U s is made of a vector B of texture model parameters
and of a label L s .
label spreading process that eventually leads to a stable label configuration, which is
taken as the resulting segmentation.
4.2 Units
As illustrated in Fig. 3, each site s of the input image has an associated unit U s . U s
is a couple U candidate vector of texture
model parameters and L s is a label (Fig. 4).
A collection of units is called a population (because selectionist
relaxation is an iterative method, units or population of units will be indexed with
time whenever this is necessary). L s is the label assigned to site s. The output of the
algorithm, the segmented image, is stands for
the stopping time step.
Each unit U s is assigned a fitness value f(U s ), which quantifies how well the unit
matches, according to the texture model, the w \Theta w texture window W s centered on site
s. The likelihood P measure of this match. However, with the
generalized Ising model, this criterion cannot be retained because of the aforementioned
awkwardness of the partition function. Instead, f(U s ) is defined as the approximated
likelihood:
ZWs (B s ) is the approximated partition function given in (4).
Using this approximation constrains the domain wherein unit parameters may be
reliably searched for by the genetic algorithm. Unsatisfactory segmentation results are
indeed expected if the fitness function is unreliable, due to a large approximation error.
As explained in Section 3, this error vanishes as the parameters go to zero. Thus unit
parameters must be initially close to zero (constraint on initialization), and they must
stay close to zero during the whole run (constraint on mutation). How close to zero the
parameters must be to yield good segmentation results is determined experimentally.
How these constraints are taken into account in the algorithm is explained in the
following subsection.
Selectionist relaxation implements a fine-grained distributed genetic algorithm.
This means that the population is spatially organized, each unit primarily interacting
with its neighboring units. For the unit at site s, these are the units located within
the j \Theta j window N s centered on site s (Fig. 3). Units located on the borders of the
image have fewer neighbors than interior units.
selection crossover/mutation
states

Figure

5: Selection, crossover and mutation are state-dependent. The population is
here in a state with three coexisting labels, corresponding to three subpopulations
of units. Their boundaries are shown as thin broken lines. Left. The sites whose
neighborhood (dark gray) crosses a label boundary have state 1 (light gray); the others
have state 0 (white). Middle. Selection at sites with state 0 only involves neighboring
units, while it additionally involves a randomly picked unit at sites with state 1. Right.
Only units with state 0 undergo crossover with a neighbor and mutation.
Each unit is attributed a binary value, called its state, which depends on the labels
of its neighbors. The state S s of unit U s is defined as follows:
This variable allows to discriminate units according to their distance from units with
different labels. As relaxation proceeds, some units spread over the image by being
copied from site to site, and so do their associated labels. Consequently, homogeneously
labeled regions are growing. As illustrated in Fig. 5 (Left ), units located in
the neighborhood of a boundary between two or more such regions have state 1, while
units located inwards these regions have state 0. As explained in the next subsec-
tion, in selectionist relaxation, genetic operators (selection, crossover and mutation)
are state-dependent.
4.3 Algorithm
Initialization. The first step in selectionist relaxation consists in creating the initial
population U(0) as follows. For each unit U s , each component fi s;i of its parameter
vector B s is assigned a value sampled from the uniform distribution over the interval
As explained in the previous subsection, the parameter initialization domain
is constrained because the fitness function relies on the approximation of the partition
Accordingly, ffi must be chosen small enough so that the approximation error
is acceptable. In the experiments reported in the next section, the simple rule
has been used with success.
Unit label L s is chosen as the raster scan index of site s. Consequently, there are
initially as many labels as there are pixels in the image, and all sites are in state 1.
Relaxation cycle. After the population of units has been initialized, selectionist
relaxation consists in repeating a two-step relaxation cycle until the stopping criterion
crossover
mutation

Figure

Crossover and mutation. Top, Crossover between unit U s and a neighboring
unit U r . The crossover position k is chosen at random. Bottom, Mutation of unit U s .
Mutation position l and mutation amount m are chosen at random. Unit labels are
not shown because they are not affected by crossover nor by mutation.
is met. Each time step t, the population U computed by, first, applying
selection to the population U (t) and, second, by applying crossover and mutation to
the selected population.
The operators are state-dependent (Fig. 5). During selection at a site with state 0,
competition only involves the neighboring units. At a site with state 1, it additionally
involves a remote unit. This mechanism allows spatially distant units to interact, and
was introduced so that a same texture can be assigned a unique label even though
it appears in different disconnected regions. Without this mechanism, such a texture
would be assigned as many labels as it forms separate regions, because labels would
exclusively be propagated from one site to the next. During the second step of the
cycle, crossover and mutation are applied only to units with state 0. This prevents
the label boundaries that are formed as relaxation proceeds from being perturbed and
disrupted by sudden fitness changes.
Each of the three operators synchronously affects all image sites. They are described
in detail below for a generic site s.
ffl Selection. The selection scheme implemented in selectionist relaxation is local
tournament selection [31], a variant of tournament selection [19]: the unit whose
fitness is the highest in a subpopulation U s of population U is selected to replace
the unit at site s. As said before, selection is state-dependent (Fig. 5, Middle):
where r is a randomly picked site. Once U s is build, the unit with the greatest
fitness value in U s is selected to replace the unit at site s:
ffl Crossover. If S does not undergo crossover (Fig. 5, Right ).
Otherwise, a neighboring unit U r ; r 2 N s , is randomly picked. Then, one component
in the parameter vector B s is chosen and is assigned the corresponding
value of the parameter vector B r (Fig. 6, Top).
ffl Mutation. As for crossover, unit U s does not undergo mutation whenever S
1. Otherwise, a parameter index l 2 randomly chosen and a value
m sampled from the uniform distribution in the interval [\Gamma- l
s ] is added to the
corresponding parameter fi s;l of U s (Fig. 6, Bottom). Two constraints are imposed
on mutation through - l
s . First, mutation amplitude must be small compared
to the initial parameter range ffi. Second, preliminary experiments have shown
that a texture dependent mutation scheme leads to better results than a texture
independent one. These constraints are taken into account by letting
The first term, ffl ffi, enforces the first constraint, provided ffl is small. In the
experiments reported in the next section, ffl is set to 0:02. The second term makes
mutation amplitude depend on the local texture configuration by allowing greater
mutation amplitude when j- l j is small. This occurs when there is some ambiguity
in the texture along clique type l, since by definition, j- l j small means that about
half of the cliques of type l contribute by +1 while the other half contribute by
\Gamma1. It experimentally appeared that a greater mutation amplitude was beneficial
to overcome such ambiguities.
5.1 Experimental setup
The results reported in this section illustrate selectionist relaxation segmentation of
images containing textures that are realizations of the generalized Ising model presented
in Section 2. The images contain 8 gray levels and are 256 \Theta 256 pixels wide. Texture
samples were synthesized using the Gibbs Sampler [16] for 100 steps.
For each test image, selectionist relaxation was run for 300 time steps. Each unit has
8 neighbors (j = 3). The only externally tuned parameter is w, which defines the size of
the texture window that is used to compute each unit fitness. As explained in Section 4,
w automatically determines the initial parameter range as well as the mutation range.
The number of textures and their associated parameters are automatically determined
by the algorithm through simulated evolution among the population of units.
Segmentation results are evaluated by visual examination and by computing the
error rate. Misclassified pixels are determined as follows: for each region of the true
segmentation, the label which is the most represented over that region in the segmented
image is determined. The pixels that are assigned another label are considered as
misclassified. The error rate is the percentage of misclassified pixels over the whole
image.
5.2 Segmentation results
Fig. 7 displays the segmentation result for an image that contains two textures spatially
arranged according to a simple geometry. Texture windows used to evaluate the fitness
of the units are w wide. The segmentation of an image containing the same
two textures arranged in a more complex fashion is illustrated on Fig. 8. Though
more complex, the two textures still form connected regions. Fig. 9 shows that the
same textures can also be correctly segmented when they form spatially disconnected
regions. This example proves that, though selectionist relaxation mainly proceeds by
propagating labels over nearest neighboring sites, spatially separated blobs of the same

Figure

7: Segmentation of Wave, a 2-textures image. A. True segmentation. B. Input
image. C. Selectionist relaxation segmentation. D. Misclassified pixels.
texture can be assigned the same label. This is because a randomly chosen unit is
systematically involved in the selection process at those sites s such that S s = 1.
Consequently, some units can literally jump over large spatial distances. As illustrated
in Fig. 10, images that contain a larger number of textures can be segmented as well.
In this last case, it was necessary to compute the fitness of the units over larger (w
11 \Theta 11) texture windows, to take into account the coarseness of the different textures.
rates are given in Table 1 (Middle). These are reasonably low, and, as can
be seen in Fig. 7, 8, 9 and 10, errors exclusively occur at the boundaries between
the textured regions. This suggests that comparing error rates among the four cases
is misleading, because the total length of texture boundaries differ among the four
cases. A relative error rate was defined as the number of misclassified pixels divided
by the total length of region boundaries in the true segmentation. According to the
relative error rate (last column in Table 1), it appears that, in spite of the varying
region shape, connectivity, and number, the performance of selectionist relaxation is
relatively constant among the four cases, and, in particular, the relative error rate is
always less than 1. However, using a larger window size (fourth case) seems to result
in an increased number of errors at region boundaries, which is not unexpected.

Figure

8: Segmentation of Spiral, a 2-textures image. A. True segmentation. B.
Input image. C. Selectionist relaxation segmentation. D. Misclassified pixels.
5.3 Estimated parameters
The issue naturally arises of the extent to which the parameters of the units that are
found through selectionist relaxation on a given texture match the true parameters
of that texture (i.e., the parameters that were used to synthesize the original tex-
ture). These parameter sets will be respectively referred to as B units and B true . Any
attempt to assess the correctness of B units with regards to B true is however hampered
by the constraints imposed on B units because of the partition function approximation.
As previously mentioned, B units must be considered as containing both the estimated
parameters of the texture (B estim ) and the temperature
B estim can thus be determined from B units (and subsequently compared to B true
T is known. The problem is that T is only implicit, and, consequently, unknown.
However, under the assumption that the estimated parameters are correct (i.e. assuming
the criterion

Figure

9: Segmentation of Blobs, a 2-textures image. A. True segmentation. B. Input
image. C. Selectionist relaxation segmentation. D. Misclassified pixels.
Using this criterion, a value of T can be computed and B estim can be determined
from B units . The textures can also be resynthesized using B estim and compared to the
originals.
This has been done for the Wave experiment reported in Fig. 7. For each texture,
the vector B units is computed by averaging unit parameters over all the units whose
label is the most represented label on that texture. Table 2 gives theoretical, unit, and
estimated parameters for each texture. Comparing B estim with B true shows that the
relative parameter values are acceptable for texture L, but are far from the original for
texture U. The textures resynthesized using estimated parameters are shown in Fig. 11.
In this work, selectionist relaxation is proposed as a new method for segmenting images
that contain textures modeled using Markov random fields. Using a high temperature
approximation of the partition function, the ability of selectionist relaxation to segment
samples of the generalized Ising model has been demonstrated. Selectionist relaxation
is unsupervised in so far as knowledge concerning the number of textures and their
associated parameters is not required beforehand. Estimation of these unknowns and

Figure

10: Segmentation of Rose, a 8-textures image. A. True segmentation. B. Input
image. C. Selectionist relaxation segmentation. D. Misclassified pixels.
segmentation are achieved simultaneously. The algorithmic complexity of the method
neither depends on the number of textures nor on the number of gray levels.
Several solutions to the problem of segmenting Markov modeled textured images in
unsupervised mode have been proposed [26, 22, 9, 33, 29]. These methods rest upon
the assumptions that the image contains only a limited number of textured regions or
that the shapes of the textured regions are such that the image can be divided into non-overlapping
blocks, the majority of which is homogeneous so that texture parameters
can be estimated on each such block. Selectionist relaxation loosens these constraints
since no assumption is made neither on the number of regions nor on the shapes of
these regions.
Relaxing these assumptions results in an increased difficulty. The problem can be
decomposed into three subproblems to be solved simultaneously. They respectively
consist in the determination of: (1) the number of different textured regions (which is
naturally bounded by the number of pixels in the input image); (2) the corresponding
set of model parameter vectors; (3) the optimal labelization of the data. It is noted
that the trivial solution, which consists in assigning a different label to each pixel,
is not observed. Partial suboptimal solutions, in which several labels are assigned
to a same region, are not observed either. On the contrary, the number of regions
Image
Wave 0.26 0.47
Spiral 3.40 0.52
Blobs 3.07 0.49
Rose 2.09 0.87

Table

1: Segmentation errors. percentage of misclassified pixels.
number of misclassified pixels divided by the total length of region boundaries in the
true segmentation.
Texture Parameters Temperature
true 1.000 -1.000 -1.400 -1.400
true -1.000 -1.000 -1.400 -1.400

Table

2: Comparison between actual texture parameters and unit parameters found
by selectionist relaxation (case of the Wave experiment reported in Fig. 7). Left : U
and L refer to the upper and to the lower textures in Fig. 7, respectively. Middle:
parameters used to synthesize the original textures (B true ), unit parameters (B units ),
and estimated parameters (B estim determined using criterion (7)
and used to compute B estim from B units .
has been correctly identified in all our experiments. This suggests that, though no
priors are imposed on the labels, regularizing constraints are implicitly incorporated
into the algorithm. The issue of identifying these constraints is the matter for further
investigations.
Though it is unsupervised, the method is not, however, fully data-driven, since the
size w of the texture window used to compute the fitness of the units has to be specified
by the user. Tuning this parameter is easy because it is in natural correspondence with
the coarseness of the textures. The coarser the textures are, the greater the size of the
window should be to insure that it contains enough information to yield reliable fitness
values. As a counterpart, this may affect segmentation accuracy, since large errors
are expected to occur at region boundaries when using large windows. The results
reported here show that in most cases, the spatial extent of boundary misclassifications
is unexpectedly small compared to the size of the window.
A comparison between actual texture parameters and parameters estimated through
selectionist relaxation has been done. For the first texture (texture L in Table 2),
estimated parameters agree with actual parameters. For the second texture (texture U),
the estimation is less satisfactory. Though correct signs and roughly correct absolute
values are obtained, pairwise parameter ratios within the estimated parameter set
and within the true parameter set largely differ. We propose that this may result
from several, possibly non-exclusive, causes. First, it can be argued that error in
parameter estimation results from the high temperature approximation of the partition
function. However, if this were systematically true, then correct parameters would not

Figure

11: Textures resynthesized using estimated parameters. A. Original patch (same
as Fig. 7-A). B. Reconstructed patch: the textures have been resynthesized using the
estimated parameters (given in Table 2).
be obtained for texture L. Second, the size w of window W may be too small, and
texture U may be more sensitive to this parameter because it is coarser than texture L.
Third, the computation of B estim relies on the assumption that all the parameters are at
the same temperature. This is certainly far from being a correct assumption, because
the mutation range is texture- and parameter-dependent, so that the parameters do not
evolve at the same rate. Texture U is such that the mutation range on fi 1 is, on average,
larger than the mutation range on the other parameters, while texture L is such that
the mutation range is roughly parameter-independent, because this texture is isotropic.
Fourth, it is also likely that sampling bias in the procedure used to synthesize the
textures is stronger for texture U than for texture L. This is confirmed by experiments
in which parameters were estimated (using maximum pseudo-likelihood estimation [3])
on 100 \Theta 100 homogeneous texture samples (data not shown). Pairwise parameter ratios
were in good agreement between estimated and actual parameter sets for texture L,
but not for texture U.
It has been suggested that the performance of the generalized Ising model on a
texture classification task was poorer than the performance of the autobinomial and
autonormal models [7]. It has also been argued that using either of these two other
models was better for natural texture segmentation [22]. We are currently trying to
apply selectionist relaxation to natural texture segmentation using more appropriate
models than the generalized Ising model. If the assumption that was made here is
valid, i.e., if the ability of the method to segment Markov random field texture samples
is independent of any particular model, then selectionist relaxation will appear as a
promising approach towards unsupervised texture image segmentation.
A



Given a window W and a set of texture parameters the problem is
to obtain an approximated, manageable expression of the partition function ZW (B).
For simplicity, and without loss of generality, the case considered here. The
partition function to be approximated is thus
x2\Omega expf\GammaE(x; B)g
is the set of all possible configurations over S, n being the number of
sites in S and being the set of gray level values. Remember that
is the set of all cliques in S, C i being the set of type i cliques. Under the
assumption that the grid S is toroidal, the number of cliques of each type equals the
number of sites: jC
For the generalized Ising model, the energy of a configuration can be written as
, the vector being defined by
with, for any clique
Approximating each term in the sum Z(B) by its second-order expansion (3) yields
the approximated partition function:
~
with
x2\Omega E(x; B);
The problem is now to rearrange Z 1 and Z 2 as functions of the fi i s (Z 0 is a constant
equals to g n ). These calculations rely on some preliminary results that are given in the
next subsection.
A.1 Preliminary results
For any clique c 2 C, and for any two cliques c 1 6= c 2 , one can show that
A.2 Calculation of
Using the definitions of Z 1 (B), E(x; B) and - i (x) leads to
which, together with (9), yields
A.3 Calculation of
Proceeding as for Z 1 (B) leads to
The problem is now to compute the coefficients
These coefficients are calculated by distinguishing, for each clique c 1 , those cliques
c 2 that are equal to c 1 from those that differ from c 1 , and then using (10) and (11). In
the expression of w ii , there will be only one clique c In
the expression of cliques c 2 necessarily differ from c 1 , since they belong
to different clique types. This gives
ng n\Gamma2
With these coefficients, the following expression of finally obtained
Collecting (8), (12) and (13) leads to the expression of the approximated partition
function given in (4).

ACKNOWLEDGMENTS

The authors would like to thanks Evelyne Lutton; her comments on an earlier version
of this work greatly contributed to improve the presentation of the paper and were
very much appreciated.



--R

Unsupervised image segmentation using a distributed genetic algorithm.
Spatial interaction and the statistical analysis of lattice systems.
On the statistical analysis of dirty pictures.

Classification of textures using Gaussian Markov random fields.
Texture synthesis and compression using Gaussian-Markov random field models
Markov random fields for texture classification.
Simple parallel hierarchical and relaxation algorithms for segmenting noncausal Markovian random fields.
Maximum likelihood unsupervised textured image segmentation.
Distributed genetic algorithms for the floorplan design problem.
Studies in Artificial Evolution.
Markov random field texture models.
Segmentation of textured images using Gibbs random fields.
Modeling and segmentation of noisy and textured images using Gibbs random fields.
Random field models in image analysis.
Stochastic relaxation
Probabilistic models of digital region maps based on Markov random fields with short- and long-range interaction
Genetic Algorithms in Search
A comparative analysis of selection schemes used in genetic algorithms.
The use of Markov random fields as models of texture.
Adaptation in Natural and Artifical Systems: An Introductory Analysis with Applications to Biology
Texture segmentation based on a hierarchical Markov random field model.
Markov Random Fields and Their Applications
Simultaneous parameter estimation and segmentation of Gibbs random fields using simulated annealing.

Unsupervised texture segmentation using Markov random field models.
Stochastic and deterministic networks for texture segmentation.
Parallel genetic algorithms
Gibbs random fields
du Buf.
A massively parallel genetic algorithm.
Distributed genetic algorithms.
Unsupervised segmentation of noisy and textured images using Markov random fields.
--TR

--CTR
C.-T. Li, Multiresolution image segmentation integrating Gibbs sampler and region merging algorithm, Signal Processing, v.83 n.1, p.67-78, January
Eun Yi Kim , Se Hyun Park , Sang Won Hwang , Hang Joon Kim, Video sequence segmentation using genetic algorithms, Pattern Recognition Letters, v.23 n.7, p.843-863, May 2002
J. Veenman , Marcel J. T. Reinders , Eric Backer, A Maximum Variance Cluster Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1273-1280, September 2002
genetic algorithms;unsupervised texture segmentation;selectionist relaxation;partition function approximation;markov/gibbs random fields